INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A13

ON THE AVERAGE ORDERS OF A CLASS OF DIVISOR FUNCTIONS

Roger Woodford^{1}

Department of Mathematics, University of British Columbia, Vancouver, British Columbia V6T 1Z2,

Canada

                            rogerw@math.ubc.ca

Received: 8/14/06, Revised: 1/23/07, Accepted: 3/11/07, Published: 3/20/07

Abstract

We compute the average orders and study the distribution of values of a class of divisor functions defined by symmetric polynomials on the multi-set of prime factors of a number. These generalize those we have previously defined. The simplest case of these functions is the sum of prime factors with repetition function, whose average order has been computed in various ways by Alladi and Erdős, LeVan,and Kerawala.

1. Introduction

Let us begin by consolidating some notation. Let ℕ_{0} denote the set of nonnegative integers. In [13] we considered the functions s_{k} defined as follows:

Definition 1 Let k ∈ ℕ_{0}. Define s_{k} : ℕ_{0} → ℕ_{0} as follows: if n = 0, then s_{k}(0) = 0, for all k. For n > 0, if k = 0, s_{k}(n) = 1. If k > 0, and n = p_{1} ⋯ p_{r}, where r = Ω(n) is the number of prime factors (with multiplicity) of n, then

s_{k}(n) = ∑ p_{i_{1}} ⋯ p_{i_{k}},

where the sum is taken over all products of k prime factors from the multi-set {p_{1}, …, p_{r}}.

These functions are mere special cases of a larger class of functions:

Definition 2 Let k, ℓ ∈ ℕ_{0}. We define s_{k,ℓ}(0) = 0. If n = p_{1} ⋯ p_{r} ∈ ℕ, where the p_{i} are primes, not necessarily distinct, then

s_{k,ℓ}(n) = ∑_{1≤i_{1}<...<i_{k}≤k}(p_{i_{1}} ⋯ p_{i_{k}})^{ℓ}.

1The author is operating under an NSERC CGS D research grant

We write the function s_{1,k} as e_{k}. The function s_{0,k} ≡ 1.

The special case when k = ℓ = 1, i.e. the sum of prime factors with repetition function, has been studied in other contexts. Denote this function by s. Lal [10] observes that the sequence of iterates n, s(n), s(s(n)), …, for n ≥ 5 always terminates in a prime number p ≥ 5. Based on empirical evidence, he conjectures that corresponding to a fixed such prime, the set

{n ∈ ℕ : s^{(i)}(n) = p for some i ≥ 0}

has a positive asymptotic density. Here we are writing s^{(i)}(n) for the ith iterate of n by s.

Alladi and Erdős [1] show that s(n) is uniformly distributed modulo 2 by proving that

∑_{n≤x}(−1)^{s(n)} = o(x).

Since s(n) ≡ e_{k}(n) (mod 2) for any k ∈ ℕ, this result clearly extends to e_{k}(n).

Gupta [4] shows that for a given m,

max {n ∈ ℕ : s(n) = m} = t · 3^{⌊m/3⌋},

where t = 1, 4/3, or 2; according as m ≡ 0, 1, or 2 (mod 3).

The size of the set e_{k}^{(−1)}(n) is equal to the number of partitions of n into kth powers of primes, p_{ℙ^{(k)}}(n). Bateman and Erdős [2] have shown that the number of partitions into primes p_{ℙ}(n) is strictly increasing, and Hardy and Ramanujan [5] first demonstrated the asymptotic formula

log p_{ℙ^{(k)}}(n) ∼ (k + 1) [Γ (\frac{1}{k} + 2) ζ (\frac{1}{k} + 1)]^{k/(k+1)} [\frac{n}{log^{k} n}]^{1/(k+1)} .

From this it is easily seen that the functions e_{k}(n) attain all sufficiently high values, for any k ∈ ℕ. We have shown [13] that s_{2}(n) does as well.

In Section 3 of the present paper, we shall prove the asymptotic formula

∑_{n≤x} s_{k,ℓ}(n) ∼ \frac{ζ(ℓ + 1)x^{ℓ+1}(log log x)^{k−1}}{(ℓ + 1)(k − 1)! log x} ,  (1)

for k, ℓ ≥ 1 fixed, with a precise error term included. Section 2 is devoted to e_{k}(n), and, in addition to proving (1) in this case, we study the distribution of values of these functions.

2. Statistical Results for e_{k}

2.1 The Average Order of e_{k}

Theorem 2 For k ∈ ℕ, ∑_{n≤x} e_{k}(n) = \frac{ζ(k + 1)x^{k+1}}{(k + 1) log x} + O (\frac{x^{k+1} log log x}{log^{2} x}) .

The average order of s itself is studied by Alladi and Erdős [1] by comparing it to the average order of the largest prime factor dividing n. The asymptotic in Theorem 2 (without the error term included) has been advanced by Kerawala [9] and LeVan [11]. We shall make precise LeVan’s sketch of the proof. First we require a lemma.

Lemma 1 For x ≥ 2, and k, ℓ ∈ ℕ_{0} we have ∑_{p≤x} \frac{p^{k}}{log^{ℓ} p} = \frac{x^{k+1}}{(k + 1) log^{ℓ+1} x} + O (\frac{x^{k+1}}{log^{ℓ+2} x}) .

The proof of Lemma 1 follows from a simple application of Riemann-Stieltjes integration and integration by parts.

Proof of Theorem 2. We have

∑_{n≤x} e_{k}(n) = ∑_{p≤x} ∑_{i=1}^{∞} p^{k} ⌊\frac{x}{p^{i}} ⌋ = ∑_{p≤x} p^{k} ⌊\frac{x}{p}⌋ + ∑_{i=2}^{∞} ∑_{p≤x^{1/i}} p^{k} ⌊\frac{x}{p^{i}} ⌋ .  (2)

As we shall see, the first term contributes the greater portion to the sum:

∑_{p≤x} p^{k} ⌊\frac{x}{p}⌋ = ∑_{i≤x/2} ∑_{\frac{x}{i+1} <p≤ \frac{x}{i}} ip^{k} = ∑_{i≤x/2} ∑_{p≤x/i} p^{k}

= ∑_{i≤x/2} (\frac{(x/i)^{k+1}}{(k + 1) log (x/i)} + O (\frac{(x/i)^{k+1}}{log^{2} (x/i)})) .  (3)

Let Σ_{1} = ∑_{i≤log^{2} x} \frac{1}{i^{k+1} log (x/i)} and Σ_{2} = ∑_{log^{2} x<i≤x/2} \frac{1}{i^{k+1} log (x/i)} so that

∑_{i≤x/2} \frac{1}{i^{k+1} log (x/i)} = Σ_{1} + Σ_{2}.

We have that

Σ_{1} ≥ \frac{1}{log x} ∑_{i≤log^{2} x} \frac{1}{i^{k+1}} = \frac{1}{log x} (ζ(k + 1) − ∑_{i>log^{2} x} \frac{1}{i^{k+1}} )

= \frac{1}{log x} (ζ(k + 1) + O (\frac{1}{log^{2k} x})) = \frac{ζ(k + 1)}{log x} + O (\frac{1}{log^{2k+1} x}) .

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A13 4

On the other hand,

Σ_{1} ≤ ∑_{i≤log^{2} x} \frac{1}{i^{k+1}(log x − 2 log log x)} = \frac{1}{log x} (1 + O (\frac{log log x}{log x})) ∑_{i≤log^{2} x} \frac{1}{i^{k+1}}

= \frac{1}{log x} (1 + O (\frac{log log x}{log x})) (ζ(k + 1) + O (\frac{1}{log^{2k} x}))

= \frac{ζ(k + 1)}{log x} + O (\frac{log log x}{log^{2} x}) .

Combining these results we have that

Σ_{1} = \frac{ζ(k + 1)}{log x} + O (\frac{log log x}{log^{2} x}) .  (4)

The sum Σ_{2} is negligible by comparison:

Σ_{2} = ∑_{log^{2} x<i≤x/2} \frac{1}{i^{k+1} log (x/i)} ≪ ∑_{i>log^{2} x} \frac{1}{i^{k+1}} ≪ ∫_{log^{2} x}^{∞} \frac{1}{t^{k+1}} dt ≪ \frac{1}{log^{2k} x}.  (5)

Now we need to bound the error term in (3):

∑_{i≤x/2} \frac{1}{i^{k+1} log^{2} (x/i)} = O (∫_{1}^{x/2} \frac{dt}{t^{2} log^{2} x/t})

= O (∫_{1}^{√\overline{x}} \frac{dt}{t^{2} log^{2} x/t} + ∫_{√\overline{x}}^{x/2} \frac{dt}{t^{2} log^{2} x/t})

= O (\frac{4}{log^{2} x} ∫_{1}^{√\overline{x}} \frac{dt}{t^{2}} + ∫_{√\overline{x}}^{x/2} \frac{dt}{t^{2}})

= O (\frac{1}{log^{2} x})  (6)

Hence by (4), (5), and (6), we have that

∑_{p≤x} p^{k} ⌊\frac{x}{p}⌋ = \frac{ζ(k + 1)x^{k+1}}{(k + 1) log x} + O (\frac{x^{k+1} log log x}{log^{2} x}) .

To conclude the proof, we need to bound the second term in (2):

∑_{i=2}^{∞} ∑_{p≤x^{1/i}} p^{k} ⌊\frac{x}{p^{i}} ⌋ ≤ x ∑_{i=2}^{∞} ∑_{p≤x^{1/i}} \frac{p^{k}}{p^{i}} ≤ x ∑_{p≤\sqrt{x}} \frac{p^{k−1}}{p − 1} ≤ 2x ∑_{p≤\sqrt{x}} p^{k−2}

= \begin{cases}O(x log log x), if k = 1; \\ O (\frac{x^{\frac{k+1}{2}}}{log x} ) , if k > 1. \end{cases}

Note that for the k = 1 case, x log log x = O (\frac{x^{2} log log x}{log^{2} x}) , and for the k > 1 case,

\frac{x^{\frac{k+1}{2}}}{log x} = O (\frac{x^{k+1} log log x}{log^{2} x}) . □

2.2 The Distribution of Values of e_{k}

In this section we shall relate e_{k}(n) to the largest prime factor dividing n, which we denote by P (n). The following trivial identity turns out to be rather useful in deriving some statistical properties for e_{k}:

P (n)^{k} ≤ e_{k}(n) ≤ P (n)^{k}Ω(n).  (7)

Definition 3 Let

b_{k}(x, y) = #{n ≤ x : e_{k}(n) ≤ y},  (8)

Ψ(x, y) = #{n ≤ x : P (n) ≤ y}.  (9)

So b_{k}(x, y) is the number of partitions into k-th powers of primes whose sum is less than or equal to y, and whose product of parts is less than or equal to x. We wish to relate the two quantities defined above. To do so, we state the following well-known fact concerning the function Ω(n), which counts the number of prime factors with repetition of n. The proof is by analogy with [8], p.30.

#\{n ≤ x : |Ω(n) − log log n| > (log log n)^{3/4}\} = O (\frac{x}{\sqrt{log log x}}) .  (10)

Theorem 3 There is an absolute constant c_{1} > 0 such that the following inequalities hold:

Ψ (x, (\frac{y}{log log x + (log log x)^{3/4}} )^{1/k}) − \frac{c_{1}x}{\sqrt{log log x}} ≤ b_{k}(x, y) ≤ Ψ(x, y^{1/k}). (11)

Proof. By equation (7), we have that

#{n ≤ x : P (n)^{k}Ω(n) ≤ y} ≤ b_{k}(x, y) ≤ #{n ≤ x : P (n)^{k} ≤ y}.

This implies the second inequality. By (10), there is an absolute positive constant c_{1} such

that #\{n ≤ x : |Ω(n) − log log n| ≤ (log log n)^{3/4}\} ≥ x (1 − \frac{c_{1}}{\sqrt{log log x}}) . Given this, we have the following chain of inequalities:

#{n ≤ x : P (n)^{k}Ω(n) ≤ y} ≥#{n ≤ x : P (n)^{k}Ω(n) ≤ y, and
Ω(n) ≤ log log n + (log log n)^{3/4}}
≥#[{n ≤ x : P (n)^{k}(log log n + (log log n)^{3/4}) ≤ y}
∩ {n ≤ x : Ω(n) ≤ log log n + (log log n)^{3/4}}]
≥#{n ≤ x : P (n)^{k}(log log x + (log log x)^{3/4}) ≤ y}
+ #{n ≤ x : |Ω(n) − log log n| ≤ (log log n)^{3/4}} − x
≥Ψ (x, (\frac{y}{log log x + (log log x)^{3/4}} )^{1/k}) − \frac{c_{1}x}{\sqrt{log log x}},

and the theorem is proved. □

The “Dickman function” ρ(u) is defined to be the unique continuous solution to the differential-difference equation

uρ′(u) = −ρ(u − 1) (u > 1),

satisfying the initial condition ρ(u) = 1 (0 ≤ u ≤ 1). The Dickman function is nonnegative for u > 0, and decreasing for u > 1. This definition and description is taken from [7], an extensive survey of work done on the function Ψ(x, y).

It is also true that ρ(u) is convex on (1, ∞). By the functional equation, it is apparent that lim_{u→1^{+}} ρ′(u) = −1. It follows that

ρ(a + b) ≥ ρ(a) − b, for a ≥ 1, b ≥ 0.  (12)

De Bruijin [3] proved that

Ψ(x, y) = xρ(u) [1 + O (\frac{log (u + 1)}{log y})]  (13)

holds uniformly for u = log x/ log y in the range

y ≥ 2, 1 ≤ u ≤ (log y)^{3/5−ϵ}.  (14)

This has since been improved by Hildebrand [6] to the range

y ≥ 2, 1 ≤ u ≤ exp ((log y)^{3/5−ϵ}).  (15)

For the next theorem, we are interested in the range y = x^{α/k}, and hence u = k/α.

Theorem 4 Let 0 < α < 1, and let k ∈ ℕ be fixed constants. Then

b_{k}(x, x^{α}) ∼ Ψ(x, x^{α/k}) ∼ ρ (\frac{k}{α}) x.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A13 7

In fact, we have

b_{k}(x, x^{α}) = ρ (\frac{k}{α}) x + O (\frac{x}{\sqrt{log log x}}) .

Proof. Note that for x ≥ 2^{k/α}, we are within the range (15). Consequently (13) applies:

Ψ(x, x^{α/k}) = xρ (\frac{k}{α}) [1 + O (\frac{1}{log x})] .

Furthermore, the second inequality of Theorem 3 gives us b_{k}(x, x^{α}) ≤ Ψ(x, x^{α/k}). Similarly, the first inequality from Theorem 3 yields:

Ψ (x, (\frac{x^{α}}{2 log log x})^{1/k}) − \frac{c_{1}x}{\sqrt{log log x}} ≤ b_{k}(x, x^{α}),

since Ψ(x, y) is increasing in y.

For x sufficiently large, (13) gives

Ψ (x, (\frac{x^{α}}{2 log log x})^{1/k}) = xρ (\frac{log x}{(α/k) log x − (1/k) log(2 log log x)}) [1 + O (\frac{log (u + 1)}{log y})] ,

where, in this instance,

y = (\frac{x^{α}}{2 log log x})^{1/k}

and

u = \frac{log x}{log y} = \frac{log x}{(α/k) log x − (1/k) log(2 log log x)}

= (\frac{k}{α}) \frac{1}{1 − (1/α) log(2 log log x)/ log x}.

The identity \frac{1}{1−a} < 1 + 2a holds for 0 < a < 1/2. So if x is chosen sufficiently large such that 0 < \frac{log(2 log log x)}{α log x} < \frac{1}{2}, then u < \frac{k}{α} + \frac{2k log(2 log log x)}{α^{2} log x}. Hence, since ρ(u) decreases on (1, ∞), we have

Ψ (x, (\frac{x^{α}}{2 log log x})^{1/k}) ≥ xρ (\frac{k}{α} + \frac{2k log(2 log log x)}{α^{2} log x}) [1 + O (\frac{1}{log x})]

= xρ (\frac{k}{α} + \frac{2k log(2 log log x)}{α^{2} log x}) + O (\frac{x}{log x})

≥ xρ (\frac{k}{α}) − \frac{2kx log(2 log log x)}{α^{2} log x} + O (\frac{x}{log x})

= xρ (\frac{k}{α}) + O (\frac{x log log log x}{log x}) , using equation (12). Combining this information with Theorem 3 we obtain the following inequalities:

xρ (\frac{k}{α})+O (\frac{x}{\sqrt{log log x}})≤Ψ (x, (\frac{x^{α}}{2 log log x})^{1/k})≤ b_{k}(x, x^{α})

≤ Ψ(x, x^{α/k}) = xρ (\frac{k}{α})+O (\frac{x}{log x}) ,

which proves the theorem. □

3. Average Order of s_{k,ℓ}

We now devote our attention to equation (1). We have already proved the k = 1 case, so henceforth we shall assume that k ≥ 2.

Theorem 5 The average order of s_{k,ℓ}(n) has the following expression:

∑_{n≤x} s_{k,ℓ}(n) = ∑_{r=1}^{k} ∑_{p_{1}<...<p_{r}} ∑_{\begin{matrix}i_{1}+···+i_{r}=k \\ i_{1},... ,i_{r}>0 \end{matrix}}(p_{1}^{i_{1}} ⋯ p_{r}^{i_{r}})^{ℓ} ×

( ∑_{j_{1},... ,j_{r}=1}^{∞} \binom{j_{1} − 1}{i_{1} − 1} ⋯ \binom{j_{r} − 1}{i_{r} − 1} ⌊\frac{x}{p_{1}^{j_{1}} ⋯ p_{r}^{j_{r}}} ⌋) .

Proof. The terms in the sum ∑_{n≤x} s_{k,ℓ}(n) are products of k ℓ-th powers of primes, not necessarily distinct. In other words, an arbitrary term is of the form (p_{1}^{i_{1}} ⋯ p_{r}^{i_{r}})^{ℓ}, where r ≤ k, p_{1} < … < p_{r}, i_{1}, …, i_{r} > 0, and i_{1} + ⋯ + i_{r} = k. Fix (p_{1}^{i_{1}} ⋯ p_{r}^{i_{r}})^{ℓ}. We shall count the number of times this expression occurs in the sum.

By the inclusion-exclusion principle, the number of n ≤ x such that p_{1}^{j_{1}}, …, p_{r}^{j_{r}}||n is

⌊\frac{x}{p_{1}^{j_{1}} ⋯ p_{r}^{j_{r}}} ⌋ − (⌊\frac{x}{p_{1}^{j_{1}+1}p_{2}^{j_{2}} ⋯ p_{r}^{j_{r}}} ⌋ + ⌊\frac{x}{p_{1}^{j_{1}}p_{2}^{j_{2}+1} ⋯ p_{r}^{j_{r}}} ⌋ + ⋯ + ⌊\frac{x}{p_{1}^{j_{1}}p_{2}^{j_{2}} ⋯ p_{r}^{j_{r}+1}} ⌋)

+ ⋯ + (−1)^{r} ⌊\frac{x}{p_{1}^{j_{1}+1} ⋯ p_{r}^{j_{r}+1}} ⌋ ,

which we write as β(j_{1}, …, j_{r}). Each such n contributes \binom{j_{1}}{i_{1}} ⋯ \binom{j_{r}}{i_{r}} copies of (p_{1}^{i_{1}} ⋯ p_{r}^{i_{r}})^{ℓ} to the sum ∑_{n≤x} s_{k}(n). Thus (p_{1}^{i_{1}} ⋯ p_{r}^{i_{r}})^{ℓ} occurs

∑_{j_{1},... ,j_{r}=1}^{∞} \binom{j_{1}}{i_{1}} ⋯ \binom{j_{r}}{i_{r}}β(j_{1}, …, j_{r})

times. We make the following claim:

∑_{j_{1},... ,j_{r}=1}^{∞} \binom{j_{1}}{i_{1}} ⋯ \binom{j_{r}}{i_{r}}β(j_{1}, …, j_{r}) = ∑_{j_{1},... ,j_{r}=1}^{∞} \binom{j_{1} − 1}{i_{1} − 1} ⋯ \binom{j_{r} − 1}{i_{r} − 1} ⌊\frac{x}{p_{1}^{j_{1}} ⋯ p_{r}^{j_{r}}} ⌋ . (16)

To prove (16), first note that ⌊_{\frac{x}{p_{1}^{j_{1}}···p_{r}^{jr}}} ⌋ occurs

\binom{j_{1}}{i_{1}} ⋯ \binom{j_{r}}{i_{r}} − (\binom{j_{1} − 1}{i_{1}}\binom{j_{2}}{i_{2}} ⋯ \binom{j_{r}}{i_{r}} + ⋯ + \binom{j_{1}}{i_{1}}\binom{j_{2}}{i_{2}} ⋯ \binom{j_{r} − 1}{i_{r}})

+ ⋯ + (−1)^{r}\binom{j_{1} − 1}{i_{1}}\binom{j_{2} − 1}{i_{2}} ⋯ \binom{j_{r} − 1}{i_{r}}

times in the left hand side. But an induction on r, with the identity

\binom{j}{i} − \binom{j − 1}{i} = \binom{j − 1}{i − 1}  (17)

being the r = 1 case, gives us

\binom{j_{1}}{i_{1}} ⋯ \binom{j_{r}}{i_{r}} − (\binom{j_{1} − 1}{i_{1}}\binom{j_{2}}{i_{2}} ⋯ \binom{j_{r}}{i_{r}} + ⋯ + \binom{j_{1}}{i_{1}}\binom{j_{2}}{i_{2}} ⋯ \binom{j_{r} − 1}{i_{r}})

+ ⋯ + (−1)^{r}\binom{j_{1} − 1}{i_{1}}\binom{j_{2} − 1}{i_{2}} ⋯ \binom{j_{r} − 1}{i_{r}} = \binom{j_{1} − 1}{i_{1} − 1} ⋯ \binom{j_{r} − 1}{i_{r} − 1}.  (18)

Indeed, suppose that (18) holds for r − 1. Denote the left-hand side of (18) by C_{r}. We need

to show that C_{r} = \binom{j_{1} − 1}{i_{1} − 1} ⋯ \binom{j_{r} − 1}{i_{r} − 1}. But factoring, the identity (17), and the induction

hypothesis give us that

C_{r} = \binom{j_{r}}{i_{r}}C_{r−1} − \binom{j_{r} − 1}{i_{r}}C_{r−1} = C_{r−1}\binom{j_{r} − 1}{i_{r} − 1} = \binom{j_{1} − 1}{i_{1} − 1} ⋯ \binom{j_{r−1} − 1}{i_{r−1} − 1}\binom{j_{r} − 1}{i_{r} − 1}.

Thus, the claim (16) is proved. The theorem follows by summing over all values of r from 1 to k, all possible r-tuples of primes, and for each such r-tuple, all r-tuples (i_{1}, …, i_{r}) satisfying i_{j} > 0 for j = 1, …, r, and i_{1} + ⋯ + i_{r} = k. □

We will first investigate the part of the sum in Theorem 5 corresponding to r = k, and hence i_{1} = … = i_{k} = 1. To do so, we require some generalizations of the prime number theorem. These are taken from Nathanson [12], pp.313-319, however we also include precise error terms.

Let π_{k}(x) = #{n ≤ x : Ω(n) = ω(n) = k} and π_{k}^{∗}(x) = #{n ≤ x : Ω(n) = k}. That is, π_{k}(x) counts the number of n ≤ x that are products of exactly k distinct prime factors, and π_{k}^{∗}(x) counts the number of n ≤ x which have k prime factors with repetition. Note that π_{1}(x) = π_{1}^{∗}(x) = π(x). For k ≥ 2, we have that

π_{k}(x) = \frac{x(log log x)^{k−1}}{(k − 1)! log x} + O (\frac{x(log log x)^{k−2}}{log x} ) ,  (19)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A13 10

and

0 ≤ π_{k}^{∗}(x) − π_{k}(x) ≪ \frac{x(log log x)^{k−2}}{log x} .  (20)

The first result can be used to prove the next lemma via Riemann-Stieltjes integration. Lemma 6 Let u ≥ 0, and k ≥ 2. Then

∑_{\begin{matrix}n≤x \\ ω(n)=Ω(n)=k \end{matrix}} n^{u} = \frac{x^{u+1}(log log x)^{k−1}}{(u + 1)(k − 1)! log x} + O (\frac{x^{u+1}(log log x)^{k−2}}{log x} ) .

For r = k, we have the following:

∑_{p_{1}<...<p_{k}}(p_{1} ⋯ p_{k})^{ℓ} ∑_{j_{1},... ,j_{k}=1}^{∞} ⌊\frac{x}{p_{1}^{j_{1}} ⋯ p_{k}^{j_{k}}} ⌋ = ∑_{p_{1}<...<p_{k}}(p_{1} ⋯ p_{k})^{ℓ} ⌊\frac{x}{p_{1} ⋯ p_{k}} ⌋
+ ∑_{p_{1}<...<p_{k}}(p_{1} ⋯ p_{k})^{ℓ} ∑_{\begin{matrix}j_{1},... ,j_{k}=1 \\ j_{1}···j_{k}>1 \end{matrix}}^{∞} ⌊\frac{x}{p_{1}^{j_{1}} ⋯ p_{k}^{j_{k}}} ⌋ .  (21)

We further focus by looking at the first term on the right-hand side of (21), that is, the term corresponding to j_{1} = … = j_{k} = 1. Making use of Lemma 6, we have

∑_{p_{1}<...<p_{k}}(p_{1} ⋯ p_{k})^{ℓ} ⌊\frac{x}{p_{1} ⋯ p_{k}} ⌋ = ∑_{m≤x/2^{k}} ∑_{\begin{matrix}p_{1}<...<p_{k} \\ \frac{x}{m+1} <p_{1}···p_{k}≤ \frac{x}{m} \end{matrix}} m(p_{1} ⋯ p_{k})^{ℓ}
= ∑_{m≤x/2^{k}} ∑_{\begin{matrix}p_{1}<...<p_{k} \\ p_{1}···p_{k}≤x/m \end{matrix}}(p_{1} ⋯ p_{k})^{ℓ}
=\frac{x^{ℓ+1}}{(ℓ + 1)(k − 1)!} ∑_{m≤x/2^{k}} \frac{(log log (x/m))^{k−1}}{m^{ℓ+1} log (x/m)}
+ O (x^{ℓ+1} ∑_{m≤x/2^{k}} \frac{(log log (x/m))^{k−2}}{m^{ℓ+1} log (x/m)} ) .  (22)

Now

∑_{m≤x/2^{k}} \frac{(log log (x/m))^{k−1}}{m^{ℓ+1} log (x/m)} = ∑_{m≤log^{2} x} \frac{(log log (x/m))^{k−1}}{m^{ℓ+1} log (x/m)} + ∑_{log^{2} x<m≤x/2^{k}} \frac{(log log (x/m))^{k−1}}{m^{ℓ+1} log (x/m)} . (23)

For m ∈ [1, log^{2} x],

\frac{(log log (x/m))^{k−1}}{m^{ℓ+1} log (x/m)} ≤ \frac{(log log x)^{k−1}}{m^{ℓ+1}(log x − 2 log log x)} = \frac{(log log x)^{k−1}}{m^{ℓ+1} log x} (1 + O (\frac{log log x}{log x})) ,

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A13 11

which implies that

∑_{m≤log^{2} x} \frac{(log log (x/m))^{k−1}}{m^{ℓ+1} log (x/m)} ≤\frac{(log log x)^{k−1}}{log x} (1 + O (\frac{log log x}{log x})) ∑_{m≤log^{2} x} \frac{1}{m^{ℓ+1}}
=\frac{(log log x)^{k−1}}{log x} (1 + O (\frac{log log x}{log x}))

× ζ(ℓ + 1) (1 + O (\frac{1}{log^{2ℓ} x}))

=\frac{ζ(ℓ + 1)(log log x)^{k−1}}{log x} + O (\frac{(log log x)^{k}}{log^{2} x} ) .  (24)

On the other hand, for m ∈ [1, log^{2} x] we have

\frac{(log log (x/m))^{k−1}}{m^{ℓ+1} log (x/m)} ≥ \frac{(log (log x − 2 log log x))^{k−1}}{m^{ℓ+1} log x} = \frac{(log log x + log (1 − \frac{2 log log x}{log x}))^{k−1}}{m^{ℓ+1} log x}

= \frac{(log log x + O (\frac{log log x}{log x}))^{k−1}}{m^{ℓ+1} log x}

= \frac{(log log x)^{k−1} + O (\frac{(log log x)^{k−1}}{log x} )}{m^{ℓ+1} log x},

and so

∑_{m≤log^{2} x} \frac{(log log (x/m))^{k−1}}{m^{ℓ+1} log (x/m)} ≥ \frac{(log log x)^{k−1}}{log x} (ζ(ℓ + 1) + O (\frac{1}{log^{2ℓ} x})) + O (\frac{(log log x)^{k−1}}{log^{2} x} )
= \frac{ζ(ℓ + 1)(log log x)^{k−1}}{log x} + O (\frac{(log log x)^{k−1}}{log^{2} x} ) .  (25)

Combining (24) and (25) we have that

∑_{m≤log^{2} x} \frac{(log log (x/m))^{k−1}}{m^{ℓ+1} log (x/m)} = \frac{ζ(ℓ + 1)(log log x)^{k−1}}{log x} + O (\frac{(log log x)^{k}}{log^{2} x} ) .  (26)

Now we must bound the second term on the right-hand side of (23).

∑_{log^{2} x<m≤x/2^{k}} \frac{(log log (x/m))^{k−1}}{m^{ℓ+1} log (x/m)} ≪ ∑_{log^{2} x<m≤x/2^{k}} \frac{(log log x)^{k−1}}{m^{ℓ+1}} ≪ \frac{(log log x)^{k−1}}{log^{2} x} .

A similar argument shows that

∑_{m≤x/2^{k}} \frac{(log log (x/m))^{k−2}}{m^{ℓ+1} log (x/m)} ≪ \frac{(log log x)^{k−2}}{log x} .  (27)

This we use to bound the error term in (22).

Applying this information to (22) we have that

∑_{p_{1}<...<p_{k}}(p_{1} ⋯ p_{k})^{ℓ} ⌊\frac{x}{p_{1} ⋯ p_{k}} ⌋ =\frac{x^{ℓ+1}}{(ℓ + 1)(k − 1)!} ×

(\frac{ζ(ℓ + 1)(log log x)^{k−1}}{log x} + O (\frac{(log log x)^{k}}{log^{2} x} ))

+ O (\frac{x^{ℓ+1}(log log x)^{k−2}}{log x} )

=\frac{ζ(ℓ + 1)x^{ℓ+1}(log log x)^{k−1}}{(ℓ + 1)(k − 1)! log x} + O (\frac{x^{ℓ+1}(log log x)^{k−2}}{log x} ) . (28)

This is the main term in ∑_{n≤x} s_{k,ℓ}(n). To complete the computation of the sum, we need only bound all that remains. We will first complete the case when r = k, by bounding the second term in the right-hand side of (21):

∑_{p_{1}<...<p_{k}}(p_{1} ⋯ p_{k})^{ℓ} ∑_{\begin{matrix}j_{1},... ,j_{k}=1 \\ j_{1}···j_{k}>1 \end{matrix}}^{∞} ⌊\frac{x}{p_{1}^{j_{1}} ⋯ p_{k}^{j_{k}}} ⌋

≪ x ∑_{\begin{matrix}p_{1}<...<p_{k} \\ p_{1}^{2}p_{2}···p_{k}≤x \end{matrix}}(p_{1} ⋯ p_{k})^{ℓ} ∑_{\begin{matrix}j_{1},... ,j_{k}=1 \\ j_{1}···j_{k}>1 \end{matrix}}^{∞} \frac{1}{p_{1}^{j_{1}} ⋯ p_{k}^{j_{k}}}

≪ x ∑_{\begin{matrix}p_{1}<...<p_{k} \\ p_{1}^{2}p_{2}···p_{k}≤x \end{matrix}}(p_{1} ⋯ p_{k})^{ℓ} (\frac{1}{(p_{1} − 1) ⋯ (p_{k} − 1)} − \frac{1}{p_{1} ⋯ p_{k}} )

≪ x ∑_{\begin{matrix}p_{1}<...<p_{k} \\ p_{1}^{2}p_{2}···p_{k}≤x \end{matrix}} \frac{(p_{1} ⋯ p_{k})^{ℓ}}{p_{1}^{2}p_{2} ⋯ p_{k}}

≪ x ∑_{p≤x^{\frac{1}{k+1}}} (p^{ℓ−2} ∑_{\begin{matrix}n≤x/p \\ ω(n)=Ω(n)=k−1 \end{matrix}} n^{ℓ−1})

≪ x ∑_{p≤x^{\frac{1}{k+1}}} (p^{ℓ−2} \frac{(x/p)^{ℓ}(log log (x/p))^{k−2}}{log (x/p)} )

= x^{ℓ+1} ∑_{p≤x^{\frac{1}{k+1}}} \frac{(log log (x/p))^{k−2}}{p^{2} log (x/p)}

≪ \frac{x^{ℓ+1}(log log x)^{k−2}}{log x} .  (29)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A13 13

Let us now bound the terms of Theorem 5 corresponding to r < k. We require the following power series identity:

∑_{n=j}^{∞} \binom{n − 1}{j − 1}x^{n} = (\frac{x}{1 − x})^{j} ,

which holds for |x| < 1. We have

∑_{r=1}^{k−1} ∑_{p_{1}<...<p_{r}} ∑_{\begin{matrix}i_{1}+···+i_{r}=k \\ i_{1},... ,i_{r}>0 \end{matrix}}(p_{1}^{i_{1}} ⋯ p_{r}^{i_{r}})^{ℓ} ( ∑_{j_{1},... ,j_{r}=1}^{∞} \binom{j_{1} − 1}{i_{1} − 1} ⋯ \binom{j_{r} − 1}{i_{r} − 1} ⌊\frac{x}{p_{1}^{j_{1}} ⋯ p_{r}^{j_{r}}} ⌋)

≪ x ∑_{r=1}^{k−1} ∑_{\begin{matrix}i_{1}+···+i_{r}=k \\ i_{1},... ,i_{r}>0 \end{matrix}} ∑_{\begin{matrix}p_{1}<...<p_{r} \\ p_{1}^{i_{1}}···p_{r}^{ir} ≤x \end{matrix}}(p_{1}^{i_{1}} ⋯ p_{r}^{i_{r}})^{ℓ} ∏_{m=1}^{r} ∑_{j_{m}=i_{m}}^{∞} \binom{j_{m} − 1}{i_{m} − 1}\frac{1}{p^{j_{m}}}

= x ∑_{r=1}^{k−1} ∑_{\begin{matrix}i_{1}+···+i_{r}=k \\ i_{1},... ,i_{r}>0 \end{matrix}} ∑_{\begin{matrix}p_{1}<...<p_{r} \\ p_{1}^{i_{1}}···p_{r}^{ir} ≤x \end{matrix}}(p_{1}^{i_{1}} ⋯ p_{r}^{i_{r}})^{ℓ} ∏_{m=1}^{r} (\frac{1}{p_{m} − 1})^{i_{m}}

≪ x ∑_{r=1}^{k−1} ∑_{\begin{matrix}i_{1}+···+i_{r}=k \\ i_{1},... ,i_{r}>0 \end{matrix}} ∑_{\begin{matrix}p_{1}<...<p_{r} \\ p_{1}^{i_{1}}···p_{r}^{ir} ≤x \end{matrix}}(p_{1}^{i_{1}} ⋯ p_{r}^{i_{r}})^{ℓ−1}

= x ∑_{\begin{matrix}n≤x \\ ω(n)<k=Ω(n) \end{matrix}} n^{ℓ−1}

= x ∫_{2^{−}}^{x} t^{ℓ−1} d(π_{k}^{∗}(t) − π_{k}(t)).  (30)

Applying integration by parts to (30), and using the bound (20), we have that

∑_{r=1}^{k−1} ∑_{p_{1}<...<p_{r}} ∑_{\begin{matrix}i_{1}+···+i_{r}=k \\ i_{1},... ,i_{r}>0 \end{matrix}}(p_{1}^{i_{1}} ⋯ p_{r}^{i_{r}})^{ℓ} × ( ∑_{j_{1},... ,j_{r}=1}^{∞} \binom{j_{1} − 1}{i_{1} − 1} ⋯ \binom{j_{r} − 1}{i_{r} − 1} ⌊\frac{x}{p_{1}^{j_{1}} ⋯ p_{r}^{j_{r}}} ⌋)
≪ \frac{x^{ℓ+1}(log log x)^{k−2}}{log x} .  (31)

Combining Theorem 5 with (28), (29), and (31), we have proved the following theorem: Theorem 7 Let k ≥ 2, and let ℓ ≥ 1. Then

∑_{n≤x} s_{k,ℓ}(n) = \frac{ζ(ℓ + 1)x^{ℓ+1}(log log x)^{k−1}}{(ℓ + 1)(k − 1)! log x} + O (\frac{x^{ℓ+1}(log log x)^{k−2}}{log x} ) .

Acknowledgements I would like to thank my supervisor, Dr. Izabella Laba, for her guidance, as well as Dr. Greg Martin, for invaluable knowledge and insights.

References

[1] Alladi, K., and Erdos, P., On an additive arithmetic function, Pacific J. Math., 71 (2), (1977), 275-294.

[2] Bateman, P. T. and Erdos, P., Partitions into primes, Publ. Math. (Debrecen), 4 (1956), 198–200.

[3] de Bruijn, N. G., On the number of positive integers ≤ x and free of prime factors > y, Nederl. Akad. Wetensch. Proc. Ser. A 54 (1951), 50-60.

[4] Gupta, H., Products of parts in partitions into primes, Res. Bull. Panjab. Univ. (N.S.), 21 (1970), 251-253.

[5] Hardy, G. H. and Ramanujan, S., Asymptotic formulae for the distribution of integers of various types, Proc. London Math. Soc., Ser. 2, 16 (1916), 112-132.

[6] Hildebrand, A., On the number of positive integers ≤ x and free of prime factors > y, J. Number Theory 22 (1986), 289-307.

[7] Hildebrand, A. and Tenenbaum, G., Integers without large prime factors, J. Theorie des Nombres de Bordeaux, 5 (1993), 411-484.

[8] Iwaniec, H. and Kowalski, E., Analytic Number Theory, Colloquium Publications 53, American Mathematical Society, Providence, 2004.

[9] Kerawala, S. M., A note on the orders of two arithmetic functions F (n, k) and F^{∗}(n, k), J. Natur. Sci. and Math. 9 (1969), 105-107.

[10] Lal, M., Iterates of a Number-Theoretic Function, Mathematics of Computation 23 (1968), 181-183.

[11] LeVan, Marijo O., On the order of F (x, r), J. Natur. Sci. and Math. 10 (1970), 163–166.

[12] Nathanson, M., Elementary Methods in Number Theory, Springer, New York-Berlin-Heidelberg-Hong Kong-London-Milan-Paris-Tokyo, 2000.

[13] Woodford, R., A Variation on Perfect Numbers, Integers: Electronic Journal of Combinatorial Number Theory, 4 (2004), A11.