On the Powerful and Squarefree Parts of an Integer

Maurice-Étienne Cloutier, Jean-Marie De Koninck, and Nicolas Doyon Département de mathématiques et de statistique Université Laval Québec G1V 0A6 Canada

          maurice-etienne.cloutier.1@ulaval.ca
                  jmdk@mat.ulaval.ca
              nicolas.doyon@mat.ulaval.ca

Abstract

Any integer n ≥ 2 can be written in a unique way as the product of its powerful part and its squarefree part, that is, as n = mr where m is a powerful number and r a squarefree number, with gcd(m, r) = 1. We denote these two parts of an integer n by pow(n) and sq(n) respectively, setting for convenience pow(1) = sq(1) = 1. We first examine the behavior of the counting functions ∑_{n≤x, sq(n)≤y} 1 and ∑_{n≤x, pow(n)≤y} 1. Letting P (n) stand for the largest prime factor of n, we then provide asymptotic values of A_{y}(x) := ∑_{n≤x, P (n)≤y} pow(n) and B_{y}(x) := ∑_{n≤x, P (n)≤y} sq(n) when y = x^{1/u} with u ≥ 1 fixed. We also examine the size of A_{y}(x) and B_{y}(x) when y = (log x)^{η} for some η > 1. Finally, we prove that A_{y}(x) will coincide with B_{y}(x) in the sense that log(A_{y}(x)/x) = (1 + o(1)) log(B_{y}(x)/x) as x → ∞ if we choose y = 2 log x.

1 Introduction and notation

A powerful number (or square-full number) is a positive integer n such that p^{2} | n for every prime factor p of n. In 1934, Erdős and Szekeres [5] were the first to study the distribution of these numbers. In 1958, Bateman and Grosswald [1] established a very accurate estimate for the number N(x) of powerful numbers not exceeding x, namely

N(x) = C_{2}x^{1/2} + C_{3}x^{1/3} + o(x^{1/6}) (x → ∞),

where C_{2} = \frac{ζ(3/2)}{ζ(3)} ≐ 2.1732 and C_{3} = \frac{ζ(2/3)}{ζ(2)} ≐ −1.4879. Here ζ stands for the Riemann

Zeta Function.

Further estimates and generalizations concerning powerful numbers were later obtained by Ivić and Shiu [8].

On the other hand, a squarefree number is a positive integer n such that p^{2} ∤ n for every prime factor p of n. It is well known (see, for instance, Hardy and Wright [6, pp. 169–170]) that the number Z(x) of squarefree numbers not exceeding x can be written as

Z(x) = ∑_{n≤x} μ^{2}(n) = \frac{6}{π^{2}} x + O (x^{1/2}) ,

where μ stands for the Moebius function.

Interestingly, any integer n ≥ 2 can be written in a unique way as the product of its powerful part and its squarefree part, that is, as n = mr where m is a powerful number and r a squarefree number, with gcd(m, r) = 1. We denote these two parts of an integer n by pow(n) and sq(n) respectively, setting for convenience pow(1) = sq(1) = 1.

In his master’s thesis, Cloutier [2] obtained asymptotic values for ∑_{n≤x} pow(n)^{a} sq(n)^{b}, where a and b are fixed integers. Particular cases of his results yield the following estimates.

∑_{n≤x} pow(n) = \frac{d_{1}}{3} x^{3/2} + O(x^{4/3}),  (1)

∑_{n≤x} sq(n) = \frac{d_{2}}{2} x^{2} + O(x^{3/2}),  (2)

∑_{n≤x} \frac{1}{pow(n)} = d_{2}x + O(x^{1/2}),  (3)

∑_{n≤x} \frac{1}{sq(n)} = d_{1}x^{1/2} + O(x^{1/3}),  (4)

where

d_{1} = ∏_{p} (1 + \frac{2}{p^{3/2}} − \frac{1}{p^{5/2}} ) ≐ 3.52,  (5)

d_{2} = ∏_{p} (1 − \frac{1}{p^{2}} + \frac{1}{p^{3}(p + 1)}) ≐ 0.65.  (6)

In particular, it follows from (1) and (2) that B(x) := ∑_{n≤x} sq(n) is much larger than A(x) := ∑_{n≤x} pow(n) for large values of x. However, letting P (n) stand for the largest prime factor of n, with P (1) = 1, one can easily check that if we set

A_{y}(x) := ∑_{\begin{matrix}n≤x \\ P (n)≤y \end{matrix}} pow(n)  and  B_{y}(x) = ∑_{\begin{matrix}n≤x \\ P (n)≤y \end{matrix}} sq(n),  (7)

then, for small values of y = y(x), we have B_{y}(x) = o(A_{y}(x)) as x → ∞, while for large values of y = y(x), we have A_{y}(x) = o(B_{y}(x)).

Here, after examining the comparative sizes of #{n ≤ x : sq(n) ≤ y} and #{n ≤ x : pow(n) ≤ y}, we show that #{n ≤ x : pow(n) > sq(n)} is asymptotic to cx^{3/4} for some computable constant c > 0. We then provide asymptotic values for A_{y}(x) and B_{y}(x) when y = x^{1/u} with u ≥ 1 fixed. We also examine the size of A_{y}(x) and B_{y}(x) when y = (log x)^{η} for some η > 1. Finally, we establish that if y = 2 log x, then log(A_{y}(x)/x) = (1 + o(1)) log(B_{y}(x)/x) as x → ∞.

Throughout this paper, we let ϕ stand for the Euler totient function, ω(n) for the number of distinct prime factors of n (with ω(1) = 0), Ω(n) for the number of prime factors of n counting their multiplicity (with Ω(1) = 0) and p(n) for the smallest prime factor of n (with p(1) = 1). We shall also be using the function Ψ(x, y) := #{n ≤ x : P (n) ≤ y} defined for 2 ≤ y ≤ x.

Denoting by π(x) the number of prime numbers not exceeding x, we shall be using the prime number theorem in its various forms, in particular as follows:

π(x) = (1 + o(1))\frac{x}{log x}  (x → ∞),  (8)
∏_{p≤z} p = exp{(1 + o(1))z} (z → ∞),  (9)
∑_{p≤x} log p = (1 + o(1))x (x → ∞),  (10)
p_{k} = (1 + o(1))k log k (k → ∞),  (11)

where p_{k} stands for the k-th prime number.

2 The distribution of the values of pow(n) and of sq(n)

We examine the distribution of the values of pow(n) and of sq(n) separately in the following two theorems.

Theorem 1. For 2 ≤ y ≤ x,

∑_{\begin{matrix}n≤x \\ sq(n)≤y \end{matrix}} 1 = 2C_{0} \frac{ζ(3/2)}{ζ(3)}\sqrt{xy} + O (x^{1/3}y^{2/3} log y) ,  (12)

where

C_{0} = ∏_{p} (1 + \frac{1 − 1/p}{p(1 + 1/p^{3/2})}) (1 − \frac{1}{p}) ≐ 0.38.  (13)

Remark 2. It is clear that estimate (12) has some interest only if the error term is of smaller order than the main term, that is, when y log^{6} y = o(x) as x → ∞.

Theorem 3. For 2 ≤ y ≤ x,

∑_{\begin{matrix}n≤x \\ pow(n)≤y \end{matrix}} 1 = x\frac{6}{π^{2}} ∑_{m≤y m powerful} \frac{1}{m ∏_{p|m} (1 + \frac{1}{p})} + O (\sqrt{x} log y) .  (14)

Remark 4. Observe that the main term on the right hand side of (14) is asymptotic to x as y → ∞. Indeed, this follows from the fact that

\frac{6}{π^{2}} lim_{y→∞} ∑_{m≤y m powerful} \frac{1}{m ∏_{p|m} (1 + \frac{1}{p})} = ∏_{p} (1 − \frac{1}{p^{2}} ) ∏_{p} (1 + \frac{1}{p^{2}(1 + \frac{1}{p})} + \frac{1}{p^{3}(1 + \frac{1}{p})} + ⋯)

= ∏_{p} (1 − \frac{1}{p^{2}} ) ∏_{p} (1 + \frac{1}{p^{2} − 1}) = 1.

In order to prove these two theorems, we first establish some preliminary results.

Lemma 5. Given an arbitrary positive integer r,

#\{n ≤ x : n powerful, (n, r) = 1\} = \frac{ϕ(r)}{r} \frac{ζ(3/2)}{ζ(3)} ∏_{p|r} (1 + \frac{1}{p^{3/2}} )^{−1} \sqrt{x}+O (2^{ω(r)}x^{1/3}) , (15)

where the constant implied by the Landau symbol is absolute.

Proof. Using the estimate

∑_{{n≤X \atop (n,r)=1}} 1 = \frac{ϕ(r)}{r}X + O (2^{ω(r)})  uniform for r ≥ 1,  (16)

we have, using the fact that any powerful number n can be written in a unique way as n = a^{2}b^{3} with μ^{2}(b) = 1,

∑_{n≤x ; n powerful ; (n,r)=1} 1 = ∑_{\begin{matrix}a^{2}b^{3}≤x \\ (a,r)=1 \\ (b,r)=1 \end{matrix}} μ^{2}(b) = ∑_{\begin{matrix}b^{3}≤x \\ (b,r)=1 \end{matrix}} μ^{2}(b) ∑_{\begin{matrix}a^{2}≤x/b^{3} \\ (a,r)=1 \end{matrix}} 1

= ∑_{\begin{matrix}b^{3}≤x \\ (b,r)=1 \end{matrix}} μ^{2}(b) (\frac{ϕ(r)}{r} \frac{x^{1/2}}{b^{3/2}} + O (2^{ω(r)}))

= x^{1/2} \frac{ϕ(r)}{r} ∑_{\begin{matrix}b≤x^{1/3} \\ (b,r)=1 \end{matrix}} \frac{μ^{2}(b)}{b^{3/2}} + O (2^{ω(r)}x^{1/3}) .  (17)

Using the fact that

∑_{{b≤x^{1/3} \atop (b,r)=1}} \frac{μ^{2}(b)}{b^{3/2}} = ∑_{{b=1 \atop (b,r)=1}}^{∞} \frac{μ^{2}(b)}{b^{3/2}} + O ( ∑_{b>x^{1/3}} \frac{1}{b^{3/2}} )
= ∏_{p∤r} (1 + \frac{1}{p^{3/2}} ) + O (∫_{x^{1/3}}^{∞} \frac{1}{t^{3/2}} dt)
= ∏_{p∤r} (1 + \frac{1}{p^{3/2}} ) + O (\frac{1}{x^{1/6}} ) ,

we obtain from (17) that

∑_{n≤x ; n powerful ; (n,r)=1} 1 = x^{1/2} \frac{ϕ(r)}{r} (∏_{p∤r} (1 + \frac{1}{p^{3/2}} ) + O (\frac{1}{x^{1/6}} )) + O (2^{ω(r)}x^{1/3})

= x^{1/2} \frac{ϕ(r)}{r} ∏_{p∤r} (1 + \frac{1}{p^{3/2}} ) + O (2^{ω(r)}x^{1/3})
= x^{1/2} \frac{ϕ(r)}{r} \begin{matrix}∏ & p & (1 + \frac{1}{p^{3/2}} ) \\ ∏ & p|r & (1 + \frac{1}{p^{3/2}} ) \end{matrix} + O (2^{ω(r)}x^{1/3}) ,

which proves (15). Lemma 6. Given an arbitrarily small δ > 0, as x → ∞,

∑_{r≤x} \frac{μ^{2}(r)ϕ(r)}{r ∏_{p|r} (1 + \frac{1}{p^{3/2}} )} = C_{0}x + O (x^{\frac{1}{2} +δ}) ,  (18)

where C_{0} is the constant defined in (13). Proof. For s > 1, we have

∑_{n=1}^{∞} \frac{μ^{2}(n)ϕ(n)/(n ∏_{p|n}(1 + \frac{1}{p^{3/2}} ))}{n^{s}} = ∏_{p} (1 + \frac{1 − 1/p}{1 + \frac{1}{p^{3/2}}} \frac{1}{p^{s}} )
= ζ(s) ∏_{p} (1 − \frac{1}{p^{s}} ) ∏_{p} (1 + \frac{1 − 1/p}{1 + \frac{1}{p^{3/2}}} \frac{1}{p^{s}} )
= ζ(s)H(s),

say. Observing that, for any fixed s > \frac{1}{2}, the infinite product H(s) is absolutely convergent, then (18) follows by using Wintner’s theorem (see, for instance, [4, Theorem 6.13 and Problem 6.3]).

As an immediate consequence of this lemma, we obtain the following. Lemma 7. Given an arbitrarily small δ > 0,

∑_{r≤y} \frac{μ^{2}(r)ϕ(r)}{r^{3/2} ∏_{p|r} (1 + \frac{1}{p^{3/2}} )} = 2C_{0}\sqrt{y} + O (y^{\frac{1}{4} +δ}) .

Lemma 8. Given an arbitrary powerful number m,

∑_{{r≤x/m \atop (r,m)=1}} μ^{2}(r) = α(m)x + O (\sqrt{\frac{x}{m}}β(m)) ,

where

α(m) = \frac{6}{π^{2}m} ∏_{p|m} (1 + \frac{1}{p})^{−1}  and  β(m) = ∏_{p|m} (1 − \frac{1}{\sqrt{p}})^{−1} .

Proof. This is relation (1) in the paper of De Koninck, Kátai and Subbarao [3] with a correction by Cloutier [2].

We now have the necessary tools to prove Theorems 1 and 3. Proof of Theorem 1. As a consequence of Lemma 5, we have, as x → ∞,

∑_{\begin{matrix}n≤x \\ sq(n)≤y \end{matrix}} 1 = ∑_{mr≤x ; m powerful ; r≤y ; (m,r)=1} μ^{2}(r) = ∑_{r≤y} μ^{2}(r) ∑_{m≤x/r ; m powerful ; (m,r)=1} 1

= ∑_{r≤y} μ^{2}(r) (\frac{ϕ(r)}{r} \frac{ζ(3/2)}{ζ(3)} ∏_{p|r} (1 + \frac{1}{p^{3/2}} )^{−1} \sqrt{\frac{x}{r}} + O (2^{ω(r)} (\frac{x}{r})^{1/3}))
= \sqrt{x}\frac{ζ(3/2)}{ζ(3)} ∑_{r≤y} \frac{μ^{2}(r)ϕ(r)}{r^{3/2} ∏_{p|r} (1 + \frac{1}{p^{3/2}} )} + O (x^{1/3} ∑_{r≤y} \frac{2^{ω(r)}}{r^{1/3}} )
= \sqrt{x}\frac{ζ(3/2)}{ζ(3)} ∑_{r≤y} \frac{μ^{2}(r)ϕ(r)}{r^{3/2} ∏_{p|r} (1 + \frac{1}{p^{3/2}} )} + O (x^{1/3}y^{2/3} log y) ,

where we used the fact that, since ∑_{r=1}^{∞} \frac{2^{ω(r)}}{r^{s}} = \frac{ζ^{2}(s)}{ζ(2s)} say for s > 1, it follows that

∑_{r≤y} 2^{ω(r)} = \frac{1}{ζ(2)}y log y + O(y),  (19)

implying by partial summation that

∑_{r≤y} \frac{2^{ω(r)}}{r^{1/3}} ≪ y^{2/3} log y.

Using Lemma 7, the proof of Theorem 1 is thus complete. Proof of Theorem 3. Using Lemma 8, we may write

∑_{{n≤x \atop pow(n)≤y}} 1 = ∑_{m≤y m powerful} ∑_{{r≤x/m \atop (r,m)=1}} μ^{2}(r) = x ∑_{m≤y m powerful} α(m) + O ( ∑_{m≤y m powerful} \sqrt{\frac{x}{m}}β(m))
= x\frac{6}{π^{2}} ∑_{m≤y m powerful} \frac{1}{m ∏_{p|m}(1 + \frac{1}{p})} + O (\sqrt{x} ∑_{m≤y m powerful} \frac{β(m)}{\sqrt{m}}) .  (20)

Using the estimate

∑_{m≤y m powerful} \frac{β(m)}{\sqrt{m}} ≤ ∏_{p≤y} (1 + \frac{β(p)}{p^{2/2}} + \frac{β(p)}{p^{3/2}} + ⋯) ≤ ∏_{p≤y} (1 + \frac{1}{p} + O (\frac{1}{p^{3/2}} )) ≪ log y

in (20) completes the proof of Theorem 3.

3 How often is pow(n) larger than sq(n)

In this section, we show that the set of positive integers n such that pow(n) > sq(n) is of zero density. In fact, we show much more. Theorem 9. As x becomes large,

#{n ≤ x : pow(n) > sq(n)} = D_{0}x^{3/4} + O (x^{2/3} log x) ,  (21)

where D_{0} = \frac{4}{3}C_{0} \frac{ζ(3/2)}{ζ(3)} ≐ 1.10.

Proof. We clearly have

#\{n ≤ x : pow(n) > sq(n)\} = ∑_{r≤\sqrt{x}} μ^{2}(r) ∑_{r<m≤x/r m powerful (m,r)=1} 1
= ∑_{r≤\sqrt{x}} μ^{2}(r) ∑_{m≤x/r m powerful (m,r)=1} 1 − ∑_{r≤\sqrt{x}} μ^{2}(r) ∑_{m≤r m powerful (m,r)=1} 1
= T_{1}(x) − T_{2}(x),  (22)

say. On the one hand, using Lemma 5 and (19), we have

T_{1}(x) = \sqrt{x}\frac{ζ(3/2)}{ζ(3)} ∑_{r≤\sqrt{x}} \frac{μ^{2}(r)ϕ(r)}{r^{3/2} ∏_{p|r}(1 + 1/p^{3/2})} + O(x^{1/3} log x)

= 2C_{0} \frac{ζ(3/2)}{ζ(3)}x^{3/4} + O(x^{1/3} log x).  (23)

On the other hand, using (16) and following the same reasoning as in the proof of Lemma 6, we obtain

∑_{m≤r m powerful (m,r)=1} 1 = ∑_{a^{2}b^{3}≤r ; {(a,r)=1 \atop (b,r)=1}} μ^{2}(b) = ∑_{{b^{3}≤r \atop (b,r)=1}} μ^{2}(b) ∑_{{a^{2}≤r/b^{3} \atop (a,r)=1}} 1

= ∑_{{b≤r^{1/3} \atop (b,r)=1}} μ^{2}(b) (\frac{ϕ(r)}{r} \frac{r^{1/2}}{b^{3/2}} + O(2^{ω(r)}))

= \frac{ϕ(r)}{r^{1/2}} ∑_{{b≤r^{1/3} \atop (b,r)=1}} \frac{μ^{2}(b)}{b^{3/2}} + O (2^{ω(r)}r^{1/3})

= \frac{ϕ(r)}{r^{1/2}} \frac{ζ(3/2)}{ζ(3)} ∏_{p|r} (1 + \frac{1}{p^{3/2}} )^{−1} + O (2^{ω(r)}r^{1/3}) .

Using this last estimate, we obtain that

T_{2}(x) = \frac{ζ(3/2)}{ζ(3)} ∑_{r≤\sqrt{x}} \frac{μ^{2}(r)ϕ(r)}{r^{1/2} ∏_{p|r} (1 + \frac{1}{p^{3/2}} )} + O ( ∑_{r≤\sqrt{x}} 2^{ω(r)}r^{1/3})

= \frac{2}{3}C_{0} \frac{ζ(3/2)}{ζ(3)}x^{3/4} + O (x^{2/3} log x) .  (24)

Using (23) and (24) in (22), estimate (21) follows thus completing the proof of Theorem 9.

4 The sums A_{y}(x) and B_{y}(x)

Recall the definitions of A_{y}(x) and B_{y}(x) given in (7) as well as the following.

Definition 10. The Dickman function ρ(u) is the continuous function satisfying ρ(u) = 1 for 0 ≤ u ≤ 1 and uρ′(u) = −ρ(u − 1) for u > 1.

It follows from this definition that

ρ(u) = ρ(k) − ∫_{k}^{u} \frac{ρ(z − 1)}{z}dz.  (25)

Theorem 11. Let y = x^{1/u}, with u ≥ 1 fixed. Then, as x → ∞,

∑_{\begin{matrix}n≤x \\ P (n)≤y \end{matrix}} sq(n) = (1 + o(1))ρ(u)\frac{d_{2}}{2} x^{2}  (26)

and

∑_{\begin{matrix}n≤x \\ P (n)≤y \end{matrix}} pow(n) = (1 + o(1))ρ(u/2)\frac{d_{1}}{3} x^{3/2}.  (27)

Proof. The proof of Theorem 11 is very similar to the proof of the estimate

Ψ(x, x^{1/u}) = (1 + o(1))ρ(u)x (x → ∞),

as performed, for instance, in the book of Tenenbaum [10]. We start by studying the expression

∑_{\begin{matrix}n≤x \\ y<P (n)≤x \end{matrix}} sq(n) = ∑_{y<p≤x} ∑_{\begin{matrix}n≤x \\ P (n)=p \end{matrix}} sq(n)

= ∑_{y<p≤x} ∑_{\begin{matrix}m≤x/p \\ P (m)<p \end{matrix}} sq(mp) + ∑_{y<p≤x} ∑_{\begin{matrix}m≤x/p \\ P (m)=p \end{matrix}} sq(mp)

= Σ_{1}(x) + Σ_{2}(x),  (28)

say.

We first show that Σ_{2}(x) is relatively small and can thus be neglected. Writing m = r · p, we obtain

Σ_{2}(x) = ∑_{y<p≤x} ∑_{\begin{matrix}rp≤x/p \\ P (r)≤p \end{matrix}} sq(rp^{2}) ≤ ∑_{y<p≤x} ∑_{r≤x/p^{2}} sq(r) ≤ ∑_{y<p≤x} ∑_{r≤x/p^{2}} r ≪ x^{2} ∑_{y<p≤x} p^{−4} ≪ \frac{x^{2}}{y^{3}} . (29)

We now turn our attention to the estimation of Σ_{1}(x), which we can write as

Σ_{1}(x) = ∑_{y<p≤x} p ∑_{\begin{matrix}m≤x/p \\ P (m)<p \end{matrix}} sq(m).

In the range 1 ≤ u ≤ 2, the condition m ≤ x/p implies P (m) ≤ x^{1/2} < p, so we can drop the condition P (m) < p. Hence, using equation (2), we obtain, as x → ∞,

Σ_{1}(x) = ∑_{y<p≤x} p ∑_{m≤x/p} sq(m) = (1 + o(1)) ∑_{y<p≤x} p\frac{d_{2}}{2} (\frac{x}{p})^{2}

= (1 + o(1))\frac{d_{2}}{2} x^{2} ∑_{y<p≤x} \frac{1}{p} = (1 + o(1))\frac{d_{2}}{2} x^{2} ∫_{y}^{x} \frac{1}{t log t}dt

= (1 + o(1))\frac{d_{2}}{2} (log u)x^{2}.  (30)

Again using (2) and after substituting (30) and (29) in (28), we obtain that, in the range 1 ≤ u ≤ 2,

∑_{{n≤x \atop P (n)≤y}} sq(n) = ∑_{n≤x} sq(n) − ∑_{{n≤x \atop y<P (n)≤x}} sq(n)

= (1 + o(1))\frac{d_{2}}{2} (1 − log u)x^{2} + O (\frac{x^{2}}{y^{3}} )
= (1 + o(1))\frac{d_{2}}{2} ρ(u)x^{2},  (31)

where we used the fact that ρ(u) = 1 − log u when u ∈ [1, 2].

In order to extend the range of validity of (31) for u > 2, we proceed recursively. Let M ≥ 2 be a positive integer and assume that the asymptotic estimate

∑_{\begin{matrix}n≤x \\ P (n)≤x^{1/u} \end{matrix}} sq(n) = (1 + o(1))\frac{d_{2}}{2} ρ(u)x^{2} holds for any u ∈ [1, M] as x → ∞.  (32)

We will then show that it also holds for u ∈ [M, M + 1].

First observe that, in light of (29), we have

∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x^{1/M} \end{matrix}} sq(n) = ∑_{x^{1/u}<p≤x^{1/M}} ∑_{\begin{matrix}m≤ \frac{x}{p} \\ P (m)≤p \end{matrix}} sq(mp)

= ∑_{x^{1/u}<p≤x^{1/M}} p ∑_{\begin{matrix}m≤ \frac{x}{p} \\ P (m)<p \end{matrix}} sq(m) + O (x^{2−3/u})

= ∑_{x^{1/u}<p≤x^{1/M}} p ( ∑_{\begin{matrix}m≤ \frac{x}{p} \\ P (m)≤p \end{matrix}} sq(m) − ∑_{\begin{matrix}m≤ \frac{x}{p} \\ P (m)=p \end{matrix}} sq(m)) + O (x^{2−3/u})

= ∑_{x^{1/u}<p≤x^{1/M}} p ∑_{\begin{matrix}m≤ \frac{x}{p} \\ P (m)≤p \end{matrix}} sq(m) + O (x^{2−1/u}) .  (33)

Using our induction hypothesis (32), we obtain, as x → ∞,

∑_{x^{1/u}<p≤x^{1/M}} p ∑_{\begin{matrix}m≤ \frac{x}{p} \\ P (m)≤p \end{matrix}} sq(m) = (1 + o(1))\frac{d_{2}}{2} ∑_{x^{1/u}<p≤x^{1/M}} p (\frac{x}{p})^{2} ρ (\frac{log x}{log p} − 1)

= (1 + o(1))\frac{d_{2}}{2} x^{2} ∑_{x^{1/u}<p≤x^{1/M}} \frac{1}{p}ρ (\frac{log x}{log p} − 1)

= (1 + o(1))\frac{d_{2}}{2} x^{2} ∫_{x^{1/u}}^{x^{1/M}} \frac{1}{t log t}ρ (\frac{log x}{log t} − 1) dt. (34)

Setting z = log x/ log t, we obtain dz = \frac{− log x}{t(log t)^{2}} dt, so that \frac{1}{t log t}dt = −\frac{dz}{z} and

\frac{d_{2}}{2} x^{2} ∫_{x^{1/u}}^{x^{1/M}} \frac{1}{t log t}ρ (\frac{log x}{log t} − 1) dt = (1 + o(1))\frac{d_{2}}{2} x^{2} ∫_{M}^{u} \frac{ρ(z − 1)}{z}dz.  (35)

Gathering (33), (34) and (35), we obtain

∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x^{1/M} \end{matrix}} sq(n) = (1 + o(1))\frac{d_{2}}{2} x^{2} ∫_{M}^{u} \frac{ρ(z − 1)}{z}dz.  (36)

From equation (36) and our induction hypothesis (32), we then obtain

∑_{\begin{matrix}n≤x \\ P (n)≤x^{1/u} \end{matrix}} sq(n) = ∑_{{n≤x \atop P (n)≤x^{1/M}}} sq(n) − ∑_{{n≤x \atop x^{1/u}<P (n)≤x^{1/M}}} sq(n)

= (1 + o(1))\frac{d_{2}}{2} x^{2} (ρ(M) − ∫_{M}^{u} \frac{ρ(z − 1)}{z}dz) ,

which, in light of (25), can be replaced by

∑_{\begin{matrix}n≤x \\ P (n)≤x^{1/u} \end{matrix}} sq(n) = (1 + o(1))\frac{d_{2}}{2} x^{2}ρ(u),

thus completing the proof of (26).

We now turn to the proof of (27). We begin by writing

∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x \end{matrix}} pow(n) = Σ_{1}(x) + Σ_{2}(x) + Σ_{3}(x),  (37)

where Σ_{1}(x), Σ_{2}(x), Σ_{3}(x) stand respectively for the three expressions

∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x \\ P (n)∥n \end{matrix}} pow(n),  ∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x \\ P (n)^{2}∥n \end{matrix}} pow(n),  ∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x \\ P (n)^{3}|n \end{matrix}} pow(n).

First observe that, in light of (1),

Σ_{1}(x) = ∑_{x^{1/u}<p≤x} ∑_{\begin{matrix}m≤ \frac{x}{p} \\ P (m)<p \end{matrix}} pow(mp) = ∑_{x^{1/u}<p≤x} ∑_{\begin{matrix}m≤ \frac{x}{p} \\ P (m)<p \end{matrix}} pow(m)
≪ ∑_{x^{1/u}<p≤x} (\frac{x}{p})^{3/2} ≪ x^{3/2} ∑_{t>x^{1/u}} \frac{1}{t^{3/2}} = O (x^{3/2−1/2u}) .

On the other hand, again using (1), we have

Σ_{3}(x) = ∑_{a≥3} ∑_{x^{1/u}<p≤x} ∑_{\begin{matrix}m≤ \frac{x}{p^{a}} \\ P (m)<p \end{matrix}} pow(mp^{a}) ≤ ∑_{a≥3} ∑_{x^{1/u}<p≤x} p^{a} ∑_{m≤ \frac{x}{p^{a}}} pow(m)
≪ x^{3/2} ∑_{a≥3} ∑_{x^{1/u}<p≤x} \frac{1}{p^{a/2}} ≪ ∑_{a≥3} x^{\frac{3}{2} − \frac{1}{u}(\frac{a}{2} −1)} = O (x^{3/2−1/2u}) .

It follows from these two estimates that

Σ_{1}(x) + Σ_{3}(x) = O (x^{3/2−1/2u}) .  (38)

Now estimating Σ_{2}(x) in the range 1 ≤ u ≤ 2, we have, since P (n)^{2} > x,

Σ_{2}(x) = ∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x \\ P (n)^{2}∥n \end{matrix}} pow(n) = 0.  (39)

Recalling (1) and using both (38) and (39) in (37), it follows that, in the range u ∈ [1, 2],

∑_{\begin{matrix}n≤x \\ P (n)≤x^{1/u} \end{matrix}} pow(n) = ∑_{n≤x} pow(n) − ∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x \end{matrix}} pow(n)
= (1 + o(1))\frac{d_{1}}{3} x^{3/2} − (Σ_{1}(x) + Σ_{2}(x) + Σ_{3}(x))
= (1 + o(1))\frac{d_{1}}{3} ρ(u/2)x^{3/2},  (40)

where we used the fact that ρ(u/2) = 1 for u ∈ [1, 2].

In order to extend the range of validity of (40) for u > 2, we will proceed recursively, namely by assuming that the asymptotic estimate

∑_{\begin{matrix}n≤x \\ P (n)≤x^{1/v} \end{matrix}} pow(n) = (1 + o(1))\frac{d_{1}}{3} ρ(v/2)x^{3/2} holds for any v ∈ [1, 2M] as x → ∞ (41)

and then showing that it also holds for u ∈ [2M, 2M + 2]. Indeed we have

∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x^{1/2M} \end{matrix}} pow(n) = ∑_{x^{1/u}<p≤x^{1/2M}} ∑_{\begin{matrix}m≤ \frac{x}{p^{2}} \\ P (m)<p \end{matrix}} pow(mp^{2}) + O (x^{3/2−1/2u})

= ∑_{x^{1/u}<p≤x^{1/2M}} p^{2} ∑_{\begin{matrix}m≤ \frac{x}{p^{2}} \\ P (m)<p \end{matrix}} pow(m) + O (x^{3/2−1/2u})

= ∑_{x^{1/u}<p≤x^{1/2M}} p^{2} ∑_{\begin{matrix}m≤ \frac{x}{p^{2}} \\ P (m)≤p \end{matrix}} pow(m) − S_{1}(x) + O (x^{3/2−1/2u}) (42)

where

S_{1}(x) := ∑_{x^{1/u}<p≤x^{1/2M}} p^{2} ∑_{\begin{matrix}j≤ \frac{x}{p^{3}} \\ P (j)≤p \end{matrix}} pow(jp)

= ∑_{x^{1/u}<p≤x^{1/2M}} p^{2} ( ∑_{\begin{matrix}j≤ \frac{x}{p^{3}} \\ P (j)<p \end{matrix}} pow(j) + ∑_{\begin{matrix}j≤ \frac{x}{p^{3}} \\ P (j)=p \end{matrix}} pow(jp))

≪ ∑_{x^{1/u}<p≤x^{1/2M}} p^{2} ( ∑_{j≤ \frac{x}{p^{3}}} pow(j) + ∑_{a≥1} ∑_{p^{a}k≤ \frac{x}{p^{3}}} p^{a+1} pow(k))

≪ ∑_{x^{1/u}<p≤x^{1/2M}} p^{2} ((\frac{x}{p^{3}} )^{3/2} + ∑_{a≥1} p^{a+1} (\frac{x}{p^{a+3}} )^{3/2})
≪ x^{3/2−1/u},  (43)

where again we used estimate (1). Combining (42) and (43) along with our induction hypothesis (41), it follows that

∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x^{1/2M} \end{matrix}} pow(n) = (1 + o(1))\frac{d_{1}}{3} x^{3/2} ∑_{x^{1/u}<p≤x^{1/2M}} \frac{1}{p}ρ (\frac{log x}{2 log p} − 1) ,

which we can rewrite in its integral form as

∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x^{1/2M} \end{matrix}} pow(n) = (1 + o(1))\frac{d_{1}}{3} x^{3/2} ∫_{x^{1/u}}^{x^{1/2M}} \frac{1}{t log t}ρ (\frac{log x}{2 log t} − 1) dt.  (44)

Setting z = \frac{log x}{2 log t} in (44), we obtain

∑_{\begin{matrix}n≤x \\ x^{1/u}<P (n)≤x^{1/2M} \end{matrix}} pow(n) = (1 + o(1))\frac{d_{1}}{3} x^{3/2} ∫_{M}^{u/2} \frac{1}{z}ρ (z − 1) dz.

From this we get

∑_{\begin{matrix}n≤x \\ P (n)≤x^{1/u} \end{matrix}} pow(n) = (1 + o(1))\frac{d_{1}}{3} x^{3/2} (ρ(M) − ∫_{M}^{u/2} \frac{ρ(z − 1)}{z}dz) ,

which, in light of (25), yields

∑_{\begin{matrix}n≤x \\ P (n)≤x^{1/u} \end{matrix}} pow(n) = (1 + o(1))\frac{d_{1}}{3} x^{3/2}ρ(u/2),

thus proving (27) and completing the proof of Theorem 11.

5 The sizes of A_{y}(x) and B_{y}(x) for small y

In this section, we establish the size of A_{y}(x) and B_{y}(x) when y = (log x)^{η} for some η > 1. We prove the following. Theorem 12. Let η > 1 be fixed. Then, as x → ∞,

∑_{\begin{matrix}n≤x \\ P (n)≤(log x)^{η} \end{matrix}} pow(n) = x^{\frac{3}{2} − \frac{1}{2η} +o(1)}  (45)

and

∑_{\begin{matrix}n≤x \\ P (n)≤(log x)^{η} \end{matrix}} sq(n) = x^{2− \frac{1}{η} +o(1)}.  (46)

As we will soon see, Theorem 12 is a consequence of the following lemmas.

Lemma 13. Given a real number A > 1,

Ψ(x, log^{A} x) = x^{1−1/A+o(1)} (x → ∞).

Proof. This is relation (1.14) in the paper of Granville [7]. Lemma 14. Let η > 1 be fixed. Then, as x → ∞,

F_{η}(x) := #\{n ≤ x : P (n) ≤ (log x)^{η}, n powerful\} = x^{\frac{1}{2}(1− \frac{1}{η})+o(1)}.  (47)

Proof. Since all perfect squares are powerful numbers, we have, using Lemma 13,

F_{η}(x) ≥ #\{n ≤ x^{1/2} : P (n) ≤ (log x)^{η}\} = x^{\frac{1}{2}(1− \frac{1}{η})+o(1)}.  (48)

On the other hand, using Lemma 13 and writing each powerful number n ≤ x as n = a^{2}b^{3}, where b is squarefree, we have for any ε > 0,

F_{η}(x) ≤ ∑_{\begin{matrix}a≤\sqrt{x} \\ P (a)≤(log x)^{η} \end{matrix}} # \{b ≤ \frac{x^{1/3}}{a^{2/3}} : P (b) ≤ (log x)^{η}\}
≤ ∑_{\begin{matrix}a≤x^{\frac{1}{2} −ε} \\ P (a)≤(log x)^{η} \end{matrix}} # \{b ≤ \frac{x^{1/3}}{a^{2/3}} : P (b) ≤ (log x)^{η}\} + ∑_{\begin{matrix}x^{\frac{1}{2} −ε}<a≤\sqrt{x} \\ P (a)≤(log x)^{η} \end{matrix}} x^{\frac{2ε}{3}}
≤ ∑_{\begin{matrix}a≤x^{\frac{1}{2} −ε} \\ P (a)≤(log x)^{η} \end{matrix}} # \{b ≤ \frac{x^{1/3}}{a^{2/3}} : P (b) ≤ (log x)^{η}\} + x^{\frac{2ε}{3}} Ψ(\sqrt{x}, (log x)^{η})
= ∑_{\begin{matrix}a≤x^{\frac{1}{2} −ε} \\ P (a)≤(log x)^{η} \end{matrix}} # \{b ≤ \frac{x^{1/3}}{a^{2/3}} : P (b) ≤ (log x)^{η}\} + x^{\frac{2ε}{3}} · x^{\frac{1}{2} (1− \frac{1}{η})+o(1)}
= S_{1}(x) + x^{\frac{1}{2} (1− \frac{1}{η})+O(ε)},  (49)

say. Then, using Lemma 13 again, we obtain

S_{1}(x) ≤ ∑_{\begin{matrix}a≤x^{\frac{1}{2} −ε} \\ P (a)≤(log x)^{η} \end{matrix}} (\frac{x}{a^{2}} )^{\frac{1}{3} (1− \frac{1}{η})+o(1)} ≤ x^{\frac{1}{3} (1− \frac{1}{η})+o(1)} ∑_{{a≤\sqrt{x} \atop P (a)≤(log x)^{η}}} a^{− \frac{2}{3} (1− \frac{1}{η})}
= x^{\frac{1}{3} (1− \frac{1}{η})+o(1)} ∫_{1}^{√\overline{x}} t^{− \frac{2}{3} (1− \frac{1}{η})}dΨ(t, (log x)^{η})
= x^{\frac{1}{3} (1− \frac{1}{η})+o(1)}( t^{− \frac{2}{3} (1− \frac{1}{η})}Ψ(t, (log x)^{η})|_{1}^{√\overline{x}}

+ \frac{2}{3} (1 − \frac{1}{η}) ∫_{1}^{√\overline{x}} t^{− \frac{2}{3} (1− \frac{1}{η})−1}Ψ(t, (log x)^{η}) dt)

= x^{\frac{1}{3} (1− \frac{1}{η})+o(1)} (t^{− \frac{2}{3} (1− \frac{1}{η})}Ψ(t, (log x)^{η})|_{1}^{√\overline{x}} + \frac{2}{3} (1 − \frac{1}{η}) (I_{1}(x) + I_{2}(x))) (50)

say, where I_{1}(x) = ∫_{1}^{x^{ε}} t^{− \frac{2}{3} (1− \frac{1}{η})−1}Ψ(t, (log x)^{η}) dt and I_{2}(x) = ∫_{x^{ε}}^{√\overline{x}} t^{− \frac{2}{3} (1− \frac{1}{η})−1}Ψ(t, (log x)^{η}) dt. On the one hand,

I_{1}(x) ≤ ∫_{1}^{x^{ε}} t^{− \frac{2}{3} (1− \frac{1}{η})} dt ≪ (x^{ε})^{− \frac{2}{3} (1− \frac{1}{η})} = x^{O(ε)}.  (51)

On the other hand, using Lemma 13,

I_{2}(x) = ∫_{x^{ε}}^{√\overline{x}} t^{− \frac{2}{3} (1− \frac{1}{η})−1} · t^{1− \frac{1}{η} +o(1)} dt ≪ (\sqrt{x})^{\frac{1}{3} (1− \frac{1}{η})+o(1)} .  (52)

Then, combining (51), (52), (50) and (49) as well as using Lemma 13 one more time, we obtain

F_{η}(x) ≪ x^{\frac{1}{3} (1− \frac{1}{η})+o(1)} ((\sqrt{x})^{\frac{1}{3} (1− \frac{1}{η})+o(1)} + \frac{2}{3} (1 − \frac{1}{η}) (\sqrt{x})^{\frac{1}{3} (1− \frac{1}{η})+o(1)}) + x^{\frac{1}{2} (1− \frac{1}{η})+O(ε)}
≪ x^{\frac{1}{3} (1− \frac{1}{η})+o(1)} · x^{\frac{1}{6} (1− \frac{1}{η})+o(1)} + x^{\frac{1}{2} (1− \frac{1}{η})+O(ε)} ≪ x^{\frac{1}{2} (1− \frac{1}{η})+O(ε)},

an estimate which in combination with estimate (48) completes the proof of Lemma 14. Lemma 15. Let η > 1 be fixed. Then, as x → ∞,

G_{η}(x, y) := #\{n ≤ x : pow(n) > y, P (n) ≤ (log x)^{η}\} ≪ (\frac{x}{y^{1/2}} )^{1− \frac{1}{η} +o(1)} .

Proof. Writing each integer n ≤ x as n = m · r, where m and r represent their powerful part and squarefree part, respectively, and using Lemma 13, we get for any ε > 0

G_{η}(x, y) ≤ ∑_{y<m≤x m powerful P (m)≤(log x)^{η}} ∑_{{r≤x/m \atop P (r)≤(log x)^{η}}} μ^{2}(r) ≤ ∑_{y<m≤x m powerful P (m)≤(log x)^{η}} Ψ (\frac{x}{m}, (log x)^{η})
= ∑_{y<m≤x^{1−ε} m powerful P (m)≤(log x)^{η}} Ψ (\frac{x}{m}, (log x)^{η}) + ∑_{x^{1−ε}<m≤x m powerful P (m)≤(log x)^{η}} Ψ (\frac{x}{m}, (log x)^{η})
≤ x^{1− \frac{1}{η} +o(1)} ∑_{y<m≤x^{1−ε} m powerful P (m)≤(log x)^{η}} \frac{1}{m^{1− \frac{1}{η}}} + x^{ε} ∑_{x^{1−ε}<m≤x m powerful P (m)≤(log x)^{η}} 1.

Recalling the definition of F_{η}(x) given in (47), we then have, using Lemma 14,

G_{η}(x, y) ≪ x^{1− \frac{1}{η} +o(1)} ∫_{y}^{x} t^{−1+ \frac{1}{η}} dF_{η}(t) + x^{ε}F_{η}(x)
= x^{1− \frac{1}{η} +o(1)} (t^{−1+ \frac{1}{η}} F_{η}(t)|_{y}^{x} + (1 − \frac{1}{η}) ∫_{y}^{x} t^{−2+ \frac{1}{η}} F_{η}(t) dt) + x^{\frac{1}{2} (1− \frac{1}{η})+O(ε)}
= x^{1− \frac{1}{η} +o(1)} (t^{− \frac{1}{2} (1− \frac{1}{η})}|_{y}^{x} + (1 − \frac{1}{η}) ∫_{y}^{x} t^{− \frac{3}{2} + \frac{1}{2η}} dt) + x^{\frac{1}{2} (1− \frac{1}{η})+O(ε)}
≤ x^{1− \frac{1}{η} +o(1)} (−y^{− \frac{1}{2} (1− \frac{1}{η})} + 2y^{− \frac{1}{2} + \frac{1}{2η}} ) + x^{\frac{1}{2} (1− \frac{1}{η})+O(ε)}
≪ (\frac{x}{y^{1/2}} )^{1− \frac{1}{η} +o(1)} ,

thus completing the proof of Lemma 15.

We now have the necessary tools to prove Theorem 12. Proof of Theorem 12. First observe that, using Lemma 14,

∑_{\begin{matrix}n≤x \\ P (n)≤(log x)^{η} \end{matrix}} pow(n) ≥ ∑_{n≤x P (n)≤(log x)^{η} n powerful} n = ∫_{1}^{x} t dF_{η}(t) dt = t F_{η}(t)|_{1}^{x} − ∫_{1}^{x} F_{η}(t) dt
= t^{1+ \frac{1}{2} (1− \frac{1}{η})+o(1)}|_{1}^{x} − ∫_{1}^{x} t^{\frac{1}{2} (1− \frac{1}{η})+o(1)} dt ≫ x^{\frac{3}{2} − \frac{1}{2η} +o(1)}.  (53)

Similarly, using Lemmas 13 and 14, we have

∑_{\begin{matrix}n≤x \\ P (n)≤(log x)^{η} \end{matrix}} pow(n) ≤ ∑_{m≤x m powerful P (m)≤(log x)^{η}} m ∑_{{r≤x/m \atop P (r)≤(log x)^{η}}} μ^{2}(r) ≤ ∑_{m≤x m powerful P (m)≤(log x)^{η}} mΨ (\frac{x}{m}, (log x)^{η})

= ∑_{m≤x^{1−ε} m powerful P (m)≤(log x)^{η}} m (\frac{x}{m})^{1− \frac{1}{η} +o(1)} + ∑_{x^{1−ε}<m≤x m powerful P (m)≤(log x)^{η}} mΨ (\frac{x}{m}, (log x)^{η})

≤ x^{1− \frac{1}{η} +o(1)} ∑_{m≤x m powerful P (m)≤(log x)^{η}} m^{\frac{1}{η}} + x^{ε} ∑_{m≤x m powerful P (m)≤(log x)^{η}} m

= x^{1− \frac{1}{η} +o(1)} ∫_{1}^{x} t^{\frac{1}{η}} d F_{η}(t) + x^{ε} ∫_{1}^{x} t dF_{η}(x)
≪ x^{1− \frac{1}{η} +o(1)} · x^{\frac{1}{η} + \frac{1}{2} − \frac{1}{2η}} + x^{ε} · x^{\frac{3}{2} − \frac{1}{2η} +o(1)} ≪ x^{\frac{3}{2} − \frac{1}{2η} +O(ε)}.  (54)

Combining (53) and (54) and taking ε arbitrarily small, estimate (45) of Theorem 12 follows. It remains to prove estimate (46). First, using Lemma 13, we have

∑_{\begin{matrix}n≤x \\ P (n)≤(log x)^{η} \end{matrix}} sq(n) ≤ ∑_{\begin{matrix}n≤x \\ P (n)≤(log x)^{η} \end{matrix}} n = ∫_{1}^{x} tdΨ(t, (log x)^{η})

= t Ψ(t, (log x)^{η})|_{1}^{x} − ∫_{1}^{x} Ψ(t, (log x)^{η}) dt
≤ x · x^{1− \frac{1}{η} +o(1)} − ∫_{x^{ε}}^{x} Ψ(t, (log x)^{η}) dt
≪ x^{2− \frac{1}{η} +o(1)}.  (55)

On the other hand, given an arbitrary small number ε > 0, we have, using Lemma 15,

∑_{\begin{matrix}n≤x \\ P (n)≤(log x)^{η} \end{matrix}} sq(n) = ∑_{\begin{matrix}n≤x \\ P (n)≤(log x)^{η} \end{matrix}} \frac{n}{pow(n)} ≥ x^{−ε} ∑_{n≤x ; {P (n)≤(log x)^{η} \atop pow(n)≤x^{ε}}} n ≥ x^{−ε} ∑_{x^{1−ε}<n≤x ; {P (n)≤(log x)^{η} \atop pow(n)≤x^{ε}}} x^{1−ε}

= x^{1−2ε} (Ψ(x, (log x)^{η}) − G_{η}(x, x^{ε}) − Ψ(x^{1−ε}, (log x)^{η}) + G_{η}(x^{1−ε}, x^{ε}))
≫ x^{1−2ε}x^{1− \frac{1}{η} +o(1)} = x^{2− \frac{1}{η} −2ε+o(1)}.  (56)

Since ε can be chosen arbitrarily small, combining (55) and (56), estimate (46) follows, thus completing the proof of Theorem 12.

6 Determining y such that A_{y}(x) and B_{y}(x) are of the same order

In this section, the functions

g(x) := x log x − (x − 1) log(x − 1)

and

h(x) := max_{0<b<1/2} (x log x − (x − b) log(x − b) − 2b log b + (1 − b) log(1 − b) − (1 − 2b) log(1 − 2b)) ,

both defined for real x > 1, play an important role.

Our goal is to show that when y = C log x the expressions log(A_{y}(x)/x) and log(B_{y}(x)/x) are equal to (1 + o(1))h(C)\frac{log x}{log log x} and (1 + o(1))g(C)\frac{log x}{log log x} respectively, so that by choosing C as the solution of h(C) = g(C), both expressions will be asymptotic as x → ∞.

Theorem 16. The estimate

log(A_{y}(x)/x) = (1 + o(1)) log(B_{y}(x)/x) (x → ∞)

holds for y = y(x) = 2 log x.

The proof of Theorem 16 will follow from a series of lemmas.

Lemma 17. The only solution x > 1 to g(x) = h(x) is x = 2, in which case g(2) = h(2) = 2 log 2.

Proof. Clearly, g(2) = 2 log 2. We will prove that g(2) = h(2) and then show that the solution is unique. First observe that

h(2) − g(2) = max_{0<b<1/2} (−(2 − b) log(2 − b) − 2b log b + (1 − b) log(1 − b) − (1 − 2b) log(1 − 2b))
= max_{0<b<1/2} f(b),

say. Differentiating f(b) with respect to b yields

f′(b) = log(2 − b) − 2 log b − log(1 − b) + 2 log(1 − 2b).

We then have

f′(b) = 0 ⟺ \frac{(2 − b)(1 − 2b)^{2}}{b^{2}(1 − b)} = 1 ⟺ (3b − 2)(b^{2} − 3b + 1) = 0,

from which we get b = b_{0} := \frac{3−\sqrt{5}}{2} as the only solution to f′(b) = 0 in (0, 1/2).

It remains to show that f(b_{0}) = 0. This follows directly from the fact that

f(b) = bf′(b) − 2 log(2 − b) + log(1 − b) − log(1 − 2b),

which implies that

f(b_{0}) = 0 ⟺ −2 log(2 − b_{0}) + log(1 − b_{0}) − log(1 − 2b_{0}) = 0
⟺ \frac{1 − b_{0}}{(2 − b_{0})^{2}(1 − 2b_{0})} = 1 ⟺ (2b_{0} − 3)(b_{0}^{2} − 3b_{0} + 1) = 0,

completing the first part of the proof. We also have

g′(x)−h′(x) ≥ (log x − log(x − 1))− max_{0<b< \frac{1}{2}} (log x − log(x − b)) > log (x − \frac{1}{2})−log(x−1) > 0,

so that g(x) is increasing at a faster rate than h(x) and thus proving the solution x = 2 to be unique.

Lemma 18. Given any real number κ > 0,

Ψ(x, κ log x) = exp (g(κ + 1)\frac{log x}{log log x} (1 + O (\frac{1}{log log x}))) .  (57)

Proof. This is the first relation in Granville [7, p. 271].

We now introduce the function

L(x) := \frac{log x}{log log x}.

Lemma 19. Given arbitrary numbers C > D > 0 and integer valued functions a(x) and b(x) satisfying a(x) = (1 + o(1))C L(x) and b(x) = (1 + o(1))D L(x), then, as x → ∞,

\binom{a(x)}{b(x)} = exp \{(1 + o(1))(C log C − D log D − (C − D) log(C − D))L(x)\} .

Proof. Using the well known Stirling formula n! = (1+o(1))n^{n}e^{−n}\sqrt{2πn} as n → ∞, we have, as x → ∞,

\binom{a(x)}{b(x)} = \frac{a(x)!}{b(x)! (a(x) − b(x))!}
= (1 + o(1))\frac{\sqrt{2πa(x)}a(x)^{a(x)}}{\sqrt{2πb(x)}b(x)^{b(x)} · \sqrt{2π(a(x) − b(x))} (a(x) − b(x))^{a(x)−b(x)}}

= (1 + o(1))\frac{1}{\sqrt{2π}} \begin{matrix}√ & \overline{C} \\ \sqrt{D} & \sqrt{(C − D)L(x)} \end{matrix} \frac{((1 + o(1))C)^{a(x)}}{((1 + o(1))D)^{b(x)}((1 + o(1))(C − D))^{a(x)−b(x)}}
= exp {(1 + o(1))(C log C − D log D − (C − D) log(C − D))L(x)} .

Lemma 20. As x → ∞,

∑_{\begin{matrix}n≤x \\ P (n)≤C log x \end{matrix}} sq(n) = xe^{(1+o(1))g(C)L(x)}.

Proof. To prove this result, we proceed in two steps, establishing upper and lower bounds. We start with the upper bound. Let ε > 0 be an arbitrarily small number. It is clear that

∑_{\begin{matrix}n≤x \\ P (n)≤C log x \end{matrix}} sq(n) ≤ x#\{n ≤ x : P (n) ≤ C log x, sq(n) > x^{1−ε}\} + x^{1−ε}Ψ(x, C log x). (58)

It follows from Lemma 18 that

x^{1−ε}Ψ(x, C log x) = o(x).  (59)

Since n = sq(n) pow(n), we have

#{n ≤ x : P (n) ≤ C log x, sq(n) > x^{1−ε}} ≤ E_{1}(x) · E_{2}(x),  (60)

where

E_{1}(x) := #{m ≤ x^{ε} : m powerful, P (m) ≤ C log x},
E_{2}(x) := #{x^{1−ε} < m ≤ x : m squarefree, P (m) ≤ C log x}.

Using Lemma 18, we get

E_{1}(x) ≤ Ψ(x^{ε}, C log x) = e^{O(εL(x))}.  (61)

To estimate E_{2}(x), we will need information on the size of ω(m) for those integers m counted by E_{2}(x). On the one hand,

x^{1−ε} < sq(m) = ∏_{p|sq(m)} p ≤ (C log x)^{ω(sq(m))} ,

which leads to

ω(sq(m)) ≥ (1 − ε) (1 + o (1)) L(x).  (62)

On the other hand, it was proved by Robin [9] that, for n > e^{e},

ω(n) ≤ L(n) + 1.45743\frac{L(n)}{log log n},

with equality when n = ∏_{i=1}^{47} p_{i}. Hence it follows that for all n ≤ x,

ω(sq(n)) ≤ ω(n) ≤ (1 + o(1))L(x) (x → ∞).  (63)

Combining equations (62) and (63), we obtain

ω(sq(n)) = (1 + O (ε)) L(x).  (64)

We can now get an upper bound for E_{2}(x). Equation (64) tells us that there exists δ = δ(ε) > 0 tending to 0 with ε such that

E_{2}(x) ≤ ∑_{(1−δ)L(x)<r<(1+δ)L(x)} #{n ≤ x : P (n) ≤ C log x, ω(n) = r, μ^{2}(n) = 1}
≤ ∑_{(1−δ)L(x)<r<(1+δ)L(x)} (\begin{matrix}π(C log x) \\ r \end{matrix}) = exp \{(g(C) + o(1))L(x)\} ,  (65)

where the last equality follows as in the proof of Lemma 19 after observing that, in light of (8),

π(C log x) = (1 + o(1))\frac{C log x}{log log x} = (1 + o(1))C L(x).

Using (61) and (65) in (60), and then taking into account (59) and (58), we have proven the upper bound implied in Lemma 20.

It remains to prove the lower bound. Let us first choose a squarefree number t < x such that ε log x < p(t) < P (t) ≤ C log x and also satisfying

ω(t) = ℓ_{1}(x) := ⌊(1 − \frac{ε}{2}) L(x)⌋ .

For such an integer t, using (9) and then (11), we have

t = ∏_{p|t} p ≥ ∏_{p≤p_{ω(t)}} p ≥ e^{ω(t) log(ω(t))(1+o(1))} ≥ x^{1− \frac{ε}{2} +o(1)}  (66)

and

t ≤ (C log x)^{ω(t)} ≤ x^{1− \frac{ε}{2} +o(1)}, so that t = x^{1− \frac{ε}{2} +o(1)}.  (67)

Now define p_{t} as the largest prime number such that

t · ∏_{p≤p_{t}} p ≤ x.  (68)

Note that such a prime p_{t} exists because of (67). It follows from (68), using (10), that, as x (and thus t) tends to infinity,

log t + ∑_{p≤p_{t}} log p ≤ log x,

log t + (1 + o(1))p_{t} ≤ log x,

(1 + o(1))p_{t} ≤ log x − (1 − ε/2 + o(1)) log x = (ε/2 + o(1)) log x, where we used (66), thus implying that, if x is sufficiently large,

p_{t} ≤ (\frac{ε}{2} + o(1)) log x < ε log x.

This allows us to choose an integer s_{t} defined by s_{t} := ∏_{p≤p_{t}} p such that, in light of (68), n = s_{t} · t ≤ x. Observe that we also have

\frac{x}{log x} ≤ n = s_{t} · t  (69)

because if we had s_{t}·t < \frac{x}{log x}, then multiplying both side by ε log x would give us ε log x·s_{t}·t < εx < x, which would contradict the definition of p_{t}. Using (69), we therefore have

∑_{\begin{matrix}n≤x \\ P (n)≤C log x \end{matrix}} sq(n) ≥ \frac{x}{log x}# \{t ≤ x : μ^{2}(t) = 1, ε log x < p(t) < P (t) ≤ C log x, ω(t) = ℓ_{1}(x)\}
≥ \frac{x}{log x}\binom{π(C log x) − π(ε log x))}{ℓ_{1}(x)}.  (70)

Finally, observing that as a consequence of (8),

π(C log x) − π(ε log x) = (1 + o(1))CL(x)

and that ℓ_{1}(x) = (1 + o(1))L(x), it follows from (70) and Lemma 19 that

∑_{\begin{matrix}n≤x \\ P (n)≤C log x \end{matrix}} sq(n) ≥ xe^{(g(C)+o(1))L(x)},

thus completing the proof of the lower bound and thereby that of Lemma 20. Lemma 21. As x → ∞, we have

∑_{\begin{matrix}n≤x \\ P (n)≤C log x \end{matrix}} pow(n) = xe^{(1+o(1))h(C)L(x)}.  (71)

Proof. We begin by proving the implied lower bound by using the trivial inequality

∑_{\begin{matrix}n≤x \\ P (n)≤C log x \end{matrix}} pow(n) ≥ \frac{x}{2}# \{\frac{x}{2} < n ≤ x : P (n) ≤ C log x, n powerful\} .  (72)

In this last set, if we focus only on those n = 2^{a} · m with m odd and a ≥ 2, we may write

# \{\frac{x}{2} < n ≤ x : P (n) ≤ C log x, n powerful\}

≥ # \{m ≤ \frac{x}{8} : P (m) ≤ C log x, m odd, powerful\} .

Letting ε > 0 be a small number, we further focus our attention on those integers m ≤ x/8 such that Ω(m) = ℓ_{2}(x) := ⌊(1 − ε)L(x)⌋, implying that we may write

# \{m ≤ \frac{x}{8} : P (m) ≤ C log x, m odd and powerful\}
≥ #\{m ≤ \frac{x}{8} : P (m) ≤ C log x, Ω(m) = ℓ_{2}(x), m odd and powerful\}.  (73)

Note that the two conditions Ω(m) = ℓ_{2}(x) and P (m) ≤ C log x imply that

m ≤ (C log x)^{ℓ_{2}(x)} ≤ x^{(1−ε)(1+o(1))},

thus allowing us to replace m ≤ \frac{x}{8} by m ≥ 1 in the last set appearing in (73).

We now write each integer m in that set as m = s^{2} · t where s = ∏_{p|m} p and t = m/s^{2}. Observe that for each such integer m, we have

Ω(t) = Ω(m) − Ω(s^{2}) = Ω(m) − 2ω(s) = Ω(m) − 2bΩ(m) = (1 − 2b)ℓ_{2}(x)

for some b ∈ (0, 1/2). It follows from these observations that

#{m ≥ 1 : P (m) ≤ C log x, Ω(m) = ℓ_{2}(x), m odd and powerful}
≥ max_{0<b<1/2} ∑_{\begin{matrix}s≥1 \\ μ^{2}(s)=1 \\ P (s)≤C log x \\ ω(s)=bℓ_{2}(x) \\ s odd \end{matrix}} #\{t ≥ 1 : Ω(t) = (1 − 2b)ℓ_{2}(x), p|t ⇒ p|s\}.  (74)

Since ω(s) = bℓ_{2}(x), we obtain

#\{t ≥ 1 : Ω(t) = (1 − 2b)ℓ_{2}(x), p|t ⇒ p|s\} = \binom{Ω(t) + ω(s) − 1}{Ω(t)}
= \binom{(1 − 2b)ℓ_{2}(x) + bℓ_{2}(x) − 1}{(1 − 2b)ℓ_{2}(x)}
= \binom{(1 − b)ℓ_{2}(x) − 1}{(1 − 2b)ℓ_{2}(x)}  (75)

and we also have

#\{s ≥ 1 : μ^{2}(s) = 1, P (s) ≤ C log x, ω(s) = bℓ_{2}(x), s odd\} = \binom{π(C log x) − 1}{bℓ_{2}(x)}. (76)

From estimates (74), (75) and (76), we obtain

#{m ≥ 1 : P (m) ≤ C log x, Ω(m) = ℓ_{2}(x), m odd and powerful }

≥ max_{0<b<1/2} \binom{(1 − b)ℓ_{2}(x) − 1}{(1 − 2b)ℓ_{2}(x)}\binom{π(C log x) − 1}{bℓ_{2}(x)}

= exp ((1 + o(1))h(C)L(x)) ,  (77)

where the last equality follows from Lemma 19. The proof of the lower bound in (71) then follows from (72) and (77).

We now prove the upper bound implied in Lemma 21. Let ε > 0 be small. We start with the trivial inequality

∑_{\begin{matrix}n≤x \\ P (n)≤C log x \end{matrix}} pow(n) ≤ x#\{n ≤ x : pow(n) > x^{1−ε}, P (n) ≤ C log x\} + x^{1−ε}Ψ (x, C log x) . (78)

First observe that, using Lemma 18 and provided that x is large enough, we have

x^{1−ε}Ψ (x, C log x) ≤ x^{1−ε}x^{ε/2} = x^{1−ε/2}.  (79)

On the other hand, writing each integer n ∈ {n ≤ x : pow(n) > x^{1−ε}, P (n) ≤ C log x} as n = pow(n) · sq(n) = m · r, we have

#{n ≤ x : pow(n) > x^{1−ε}, P (n) ≤ C log x} ≤ A(x) × B(x),  (80)

where

A(x) := #{r ≤ x^{ε}, μ^{2}(r) = 1, P (r) ≤ C log x}

and

B(x) := #{m ≤ x : m powerful, P (m) ≤ C log x}.

Using Lemma 18, we obtain

A(x) ≤ Ψ(x^{ε}, C log x) = exp (O(ε)L(x)) .  (81)

Concerning B(x), we have

B(x) ≤ #B_{1}(x) × #B_{2}(x),  (82)

where

B_{1}(x) := {m ≤ x : m powerful, P (m) ≤ ε log x},
B_{2}(x) := {m ≤ x : m powerful, ε log x < p(m) ≤ P (m) ≤ C log x}.

On the one hand, using Lemma 18, we have

#B_{1}(x) ≤ Ψ(x, ε log x) ≤ (\frac{1}{ε})^{π(ε log x)} = exp (O(ε)\frac{log x}{log log x}) .  (83)

On the other hand, for each m ∈ B_{2}(x), we have (ε log x)^{Ω(m)} < m ≤ x, and therefore, for some small δ > 0,

Ω(m) ≤ \frac{log x}{log log x + log ε} = (1 + δ)L(x),

provided x is large enough. It follows that

#B_{2}(x) ≤ # {m ≤ x : P (m) ≤ C log x, Ω(m) < (1 + δ)L(x)}
≤ (1 + δ)L(x) × # {m ≤ x : P (m) ≤ C log x, Ω(m) = ⌊(1 + δ)L(x)⌋}
≤ L(x)^{2}

× max_{0<b<1/2} # {m ≤ x : P (m) ≤ C log x, Ω(m) = ⌊(1 + δ)L(x)⌋ , ω(m) = ⌊bL(x)⌋} .

As we did in the proof of the lower bound, namely when establishing (77), it follows from this last series of inequalities that

max_{0<b<1/2} # {n ≤ x : P (n) ≤ C log x, Ω(n) = ⌊(1 + δ)L(x)⌋ , ω(n) = ⌊bL(x)⌋}

= exp ((1 + o(1))h(C)L(x)) .  (84)

Gathering estimates (82) through (84), we obtain that

B(x) ≤ exp ((1 + O(ε))h(C)L(x)) .  (85)

Collecting estimates (78) through (81) and also (85), the proof of the upper bound implied in Lemma 21 then follows, thus completing the proof of Lemma 21.

Proof of Theorem 16. The proof of Theorem 16 is an immediate consequence of Lemmas 20 and 21.

Remark 22. While Lemma 21 is valid only if y = C log x with C ≥ 1, the domain of validity of Lemma 20 can be extended to y = C log x for any C > 0.

Remark 23. As is shown in [2], considering, for instance, only powers of 2, for any y > 2, we have A_{y}(x) > x/2.

Remark 24. For any ε > 0, if C < 1 − ε and y ≤ C log x, then

B_{y}(x) < (∏_{p<y} p) Ψ(x, y) < e^{C log x+o(1)} = x^{C+o(1)}.

7 Final remarks

Collecting our results from Sections 4, 5 and 6, it is interesting to observe that the behaviors of A_{y}(x) and B_{y}(x) vary greatly depending on the relative size of y = y(x). Indeed, we obtained asymptotic estimates for A_{y}(x) and B_{y}(x) when y = x^{1/u}, as x → ∞, namely

A_{y}(x) = (1 + o(1))ρ(u/2)\frac{d_{1}}{3} x^{3/2} and B_{y}(x) = (1 + o(1))ρ(u)\frac{d_{2}}{2} x^{2}.

In other ranges, we obtained less precise but nevertheless interesting estimates. In particular, when y = (log x)^{η} for some η > 1, we obtained asymptotic formulas for log(A_{y}(x))/ log x and log(B_{y}(x))/ log x, that is,

A_{y}(x) = x^{\frac{3}{2} − \frac{1}{2η} +o(1)} and B_{y}(x) = x^{2− \frac{1}{η} +o(1)} (x → ∞).

For even smaller values of y, that is, when y = y(x) = 2 log x, we obtained

log(A_{y}(x)/x) = (1 + o(1)) log(B_{y}(x)/x) (x → ∞),

since we proved that both A_{y}(x) and B_{y}(x) are equal to x exp ((1 + o(1))2 log 2\frac{log x}{log log x}) as x → ∞.

Gathering our results, we obtain that given any ε > 0, if y < (2 − ε) log x, then B_{y}(x) > A_{y}(x). On the other hand, although we did not prove it, we believe that A_{y}(x) > B_{y}(x) when y > (2 + ε) log x. While this is the case in every range investigated in the paper, a rigorous proof would require studying A_{y}(x) and B_{y}(x) in the ranges not covered by the present work, an interesting challenge.

8 Acknowledgment

The work of the second author was supported in part by a grant from NSERC.

References

[1] P. Bateman and E. Grosswald, On a theorem of Erdős and Szekeres, Illinois J. Math. 2 (1958), 88–98.

[2] M. E. Cloutier, Les parties puissante et libre de carrés d’un entier, Mémoire de maîtrise, Université Laval, 2013.

[3] J.-M. De Koninck, I. Kátai, and M. V. Subbarao, On the index of composition of integers from various sets, Archiv der Mathematik 88 (2007), 524–536.

[4] J.-M. De Koninck and F. Luca, Analytic Number Theory: Exploring the Anatomy of Integers, Graduate Studies in Mathematics, Vol. 134, American Mathematical Society, 2012.

[5] P. Erdős and G. Szekeres, Über die Anzahl der Abelschen Gruppen gegebener Ordnung und ber ein verwandtes zahlentheoretisches Problem, Acta Litt. Sci. Szeged 7 (1934), 95–102.

[6] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., 1979.

[7] A. Granville, Smooth numbers: computational number theory and beyond, Algorithmic Number Theory, MSRI Proceedings 44 (2008), 267–323.

[8] A. Ivić and P. Shiu, The distribution of the powerful numbers, Illinois J. Math. 26 (1982), 576–590.

[9] G. Robin, Estimation de la fonction de Tchebychef θ sur le k-ième nombre premier et grandes valeurs de la fonction ω(n) nombre de diviseurs premiers de n, Acta Arith. 42 (1983), 367–389.

[10] G. Tenenbaum, Introduction à la Théorie Analytique et Probabilistique des Nombres, Collection Échelles, 2008.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11N37. Keywords: powerful numbers, arithmetic function.

Received July 8 2014; revised version received July 31 2014. Published in Journal of Integer Sequences, August 5 2014.

Return to Journal of Integer Sequences home page.