Some Remarks on a Paper of L. Toth

Jean-Marie De Koninck Dép. de mathématiques Université Laval Québec, PQ G1V 0A6 Canada

                  jmdk@mat.ulaval.ca

Imre Kátai Computer Algebra Department Eötvös Loránd University Pázmány Péter Sétány I/C 1117 Budapest Hungary

               katai@compalg.inf.elte.hu

Abstract

Consider the functions P (n) := ∑_{k=1}^{n} gcd(k, n) (studied by Pillai in 1933) and P̃(n) := n ∏_{p|n}(2 − 1/p) (studied by Toth in 2009). From their results, one can obtain asymptotic expansions for ∑_{n≤x} P (n)/n and ∑_{n≤x} P̃(n)/n. We consider two wide classes of functions R and U of arithmetical functions which include P (n)/n and P̃(n)/n respectively. For any given R ∈ R and U ∈ U, we obtain asymptotic expansions for ∑_{n≤x} R(n), ∑_{n≤x} U(n), ∑_{p≤x} R(p − 1) and ∑_{p≤x} U(p − 1).

1 Introduction

In 1933, Pillai [6] introduced the function

P (n) := ∑_{k=1}^{n} gcd(k, n)

and showed that

P (n) = ∑_{d|n} dφ(n/d) and ∑_{d|n} P (d) = nτ(n) = ∑_{d|n} σ(d)φ(n/d),

where φ stands for the Euler function and where τ(n) and σ(n) stand for the number of divisors of n and the sum of the divisors of n respectively.

It is easily shown that

P (n) = nτ(n) ∏_{p^{a}∥n} (1 − \frac{a/(a + 1)}{p}) .

In 1985, Chidambaraswamy and Sitaramachandrarao [2] showed that, given an arbitrary ε > 0,

∑_{n≤x} P (n) = e_{1}x^{2} log x + e_{2}x^{2} + O (x^{1+θ+ε}) ,  (1)

where e_{1} = \frac{1}{2ζ(2)} and e_{2} = \frac{1}{2ζ(2)} (2γ − \frac{1}{2} − \frac{ζ′(2)}{ζ(2)}), and where θ is the constant appearing

below in Lemma 5, ζ stands for the Riemann Zeta Function and γ stands for Euler’s constant. Using partial summation, one easily deduces from (1) that

∑_{n≤x} \frac{P (n)}{n} = e_{1}x log x + (2e_{2} − e_{1})x + O (x^{θ+ε}) .  (2)

In [10], Toth introduced the function

P̃(n) = n ∏_{p|n} (2 − \frac{1}{p}) = n · 2^{ω(n)} ∏_{p|n} (1 − \frac{1}{2p}) ,

where ω(n) stands for the number of distinct prime factors of n. Toth obtained an estimate for ∑_{n≤x} P̃(n), analogous to (1) and from which one can easily derive an asymptotic expansion for ∑_{n≤x} P̃(n)/n.

In this paper, we consider two wide classes of arithmetical functions R and U, the first of which includes the function P (n)/n, and the second of which includes P̃(n)/n. Given R ∈ R, we obtain an asymptotic expansion for ∑_{n≤x} R(n); similarly for U ∈ U. We then examine the behavior of ∑_{p≤x} R(p − 1) and ∑_{p≤x} U(p − 1).

More precisely, the class R is made of the following functions R. First, let γ(n) stand for the kernel of n ≥ 2, that is γ(n) = ∏_{p|n} p (with γ(1) = 1). Then, given an arbitrary positive constant c, an arbitrary real number α > 0 and a multiplicative function κ(n) satisfying |κ(n)| ≤ \frac{c}{γ(n)^{α}} for all n ≥ 2, let R ∈ R be defined by

R(n) = R_{κ,c,α}(n) := τ(n) ∑_{d∥n} κ(d) = τ(n) ∏_{p^{a}∥n}(1 + κ(p^{a})).  (3)

Here d∥n means that the sum runs over the unitary divisors of n, that is over all divisors d of n for which (d, n/d) = 1.

It is easily seen that if we let κ(p^{a}) = −\frac{a/(a + 1)}{p}, then the corresponding function R(n)

is precisely P (n)/n.

As for the class of functions U, it is made of the functions

U(n) = U_{h,c,α}(n) := 2^{ω(n)} ∑_{d|n} h(d),  (4)

where h is a multiplicative function satisfying |h(d)| ≤ \frac{c}{γ(d)^{α}} for each integer d ≥ 2, where

α > 0 is a given number. It is easily seen that by taking h(p) = −\frac{1}{2p} and h(p^{a}) = 0 for a ≥ 2, we obtain the particular case U(n) = P̃(n)/n.

Throughout this paper, c_{1}, c_{2}, … denote absolute positive constants.

2 Main results

Theorem 1. Let R be as in (3). For any arbitrary ε > 0, as x → ∞,

T (x) := ∑_{n≤x} R(n) = A_{0}x log x + B_{0}x + O (x^{β}) ,

with

β = \{ \begin{matrix}θ + ε, & if α ≥ 1 − θ; \\ 1 − α + ε, & if α < 1 − θ; \end{matrix}

where θ is the number mentioned in Lemma 5 below and where

A_{0} = ∑_{d≥1} \frac{λ(d)}{d}  and  B_{0} = ∑_{d≥1} \frac{λ(d)}{d}(2γ − 1 − log d),  (5)

the function λ being defined below in (20) and (21).

Theorem 2. Let U be as in (4). As x → ∞,

S(x) := ∑_{n≤x} U(n) = t_{1}x log x + t_{2}x + O (\frac{x}{log x}) ,

where

t_{1} = ∑_{δ=1}^{∞} \frac{h(δ)2^{ω(δ)}B_{1}(δ)η_{δ}}{δ} ∑_{{n=1 \atop γ(n)|δ}}^{∞} \frac{1}{n},

t_{2} = ∑_{{δ=1 \atop b∈G_{δ}}}^{∞} \frac{h(δ)2^{ω(δ)}}{δb} (B_{2}(δ)η_{δ} − 2B_{1}(δ)μ_{δ} − B_{1}(δ)η_{δ} log(δb)),

where B_{1}(δ) and B_{2}(δ) are defined below in Lemma 7, while η_{δ} and μ_{δ} are defined respectively in (35) and (36).

Theorem 3. Let R be as in (3). As x → ∞,

M(x) := ∑_{p≤x} R(p − 1) = K_{1}x + O (\frac{x}{log log x}) ,  (6)

where K_{1} = \frac{1}{2} ∑_{d=1}^{∞} \frac{κ(d)τ(d)c_{d}}{d}, where c_{d} is itself defined in Lemma 15. Theorem 4. Let U be as in (4). As x → ∞,

N(x) := ∑_{p≤x} U(p − 1) = K_{2}x + O (\frac{x}{log log x}) ,  (7)

where K_{2} is a positive constant which may depend on the function κ.

3 Preliminary results

Lemma 5. As x → ∞,

D(x) := ∑_{n≤x} τ(n) = x log x + (2γ − 1)x + O(x^{θ}) (x → ∞), (8)

for some positive constant θ < 1/3. Proof. A proof can be found in the book of Ivić [4], where one can also find a history of the improvements concerning the size of θ. Lemma 6. Given 1 ≤ ℓ < k with gcd(ℓ, k) = 1,

∑_{{n≤x \atop n≡ℓ (mod k)}} τ(n) = A_{1}(k)x log x + A_{2}(k)x + O (k^{7/3}x^{1/3} log x) ,

where

A_{1}(k) = \frac{φ(k)}{k^{2}}, A_{2}(k) = (2γ − 1)\frac{φ(k)}{k^{2}} − \frac{2}{k} ∑_{d|k} \frac{μ(d) log d}{d}.

Proof. This result is due to Tolev [9]. Lemma 7. Given a positive integer k,

∑_{{n≤x \atop (n,k)=1}} τ(n) = B_{1}(k)x log x + B_{2}(k)x + O (k^{10/3}x^{1/3} log x) ,

where B_{1}(k) = (\frac{φ(k)}{k})^{2} and B_{2}(k) = φ(k)A_{2}(k).

Proof. Observing that

∑_{{n≤x \atop gcd(n,k)=1}} τ(n) = ∑_{{ℓ=1 \atop gcd(ℓ,k)=1}}^{k} ∑_{{n≤x \atop n≡ℓ (mod k)}} τ(n),

and using the trivial fact that φ(k) ≤ k, the result follows immediately from Lemma 6.

Lemma 8. Given an arbitrary positive real number α < 1,

∑_{n>x} \frac{1}{nγ(n)^{α}} ≪ \frac{1}{x^{α}} .

Proof. Writing each number n as n = rm, where r and m are the square-full and square-free parts of n respectively with (r, m) = 1, we may write

∑_{n>x} \frac{1}{nγ(n)^{α}} = ∑_{rm>x gcd(r,m)=1 r square-full} \frac{μ^{2}(m)}{rγ(r)^{α}m^{1+α}} = ∑_{r≥1 r square-full} \frac{1}{rγ(r)^{α}} ∑_{{m>x/r \atop gcd(m,r)=1}} \frac{μ^{2}(m)}{m^{1+α}}

≪ ∑_{r≥1 r square-full} \frac{1}{rγ(r)^{α}} \frac{φ(r)}{r} ∫_{x/r}^{∞} \frac{dt}{t^{1+α}} = \frac{1}{x^{α}} ∑_{r≥1 r square-full} \frac{φ(r)}{r^{2}} (\frac{r}{γ(r)})^{α}

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

Lemma 9. Given any fixed number z > 0,

∑_{n≤x} z^{ω(n)} ≪ x log^{z−1} x.  (9)

Remark 10. This result is a weak form of the well known Selberg-Sathe formula

∑_{n≤x} z^{ω(n)} = C(t)x log^{t−1} x + O(x log^{t−2} x),

an estimate which holds uniformly for x ≥ 2 and |t| ≤ 1, where C(t) is a constant depending only on t (see Selberg [7]). Here we give a simple direct proof of (9).

Proof. For each positive integer k, let

π_{k}(x) := #{n ≤ x : ω(n) = k}.

From a classical result of Hardy and Ramanujan [3], we know that

π_{k}(x) ≤ \frac{c_{1}x}{(k − 1)! log x}(log log x + c_{2})^{k−1} (x ≥ 3),

for all k ≥ 1, where c_{1} and c_{2} are some absolute constants. Using this estimate, it follows that

∑_{n≤x} z^{ω(n)} = ∑_{k≥1} π_{k}(x)z^{k} < c_{1}z \frac{x}{log x} ∑_{k≥1} \frac{(z(log log x + c_{2}))^{k−1}}{(k − 1)!}
= c_{1}z \frac{x}{log x}e^{z log log x+zc_{2}} ≪ \frac{x}{log x}e^{z log log x} = x log^{z−1} x,

as required.

Lemma 11. (Brun-Titchmarsh Theorem) Let π(y; k, ℓ) := #{p ≤ y : p ≡ ℓ (mod k)}. Given a fixed positive number β < 1, then, uniformly for k ∈ [1, x^{β}], there exists a positive constant ξ_{1} such that

π(x; k, ℓ) < ξ_{1} \frac{x}{φ(k) log(x/k)}.

Proof. For a proof, see Titchmarsh [8].

Lemma 12. (Bombieri-Vinogradov Theorem). Given an arbitrary positive constant A, and let B = \frac{3}{2}A + 17. Then

∑_{k≤ \frac{\sqrt{x}}{log^{B} x}} max_{gcd(k,ℓ)=1} max_{y≤x} |π(y; k, ℓ) − \frac{li(x)}{φ(k)}| ≪ \frac{x}{log^{A} x}.

Proof. For a proof, see Cheng-Dong [1].

Lemma 13. Given a fixed positive number β < 1, then, uniformly for d ∈ [1, x^{1−β}], there exists a positive constant ξ_{3} such that

∑_{{p≤x \atop p≡1 mod d}} τ(p − 1) ≤ ξ_{3}x\frac{τ(d)}{φ(d)}.

Proof. Since τ(n) ≤ 2 ∑_{{d|n \atop d≤\sqrt{n}}} 1 and τ(mn) ≤ τ(m)τ(n) for all positive integers m, n, it follows

that

E : = ∑_{{p≤x \atop p≡1 (mod d)}} τ(p − 1)

≤ τ(d) ∑_{{p≤x \atop p≡1 (mod d)}} τ(\frac{p − 1}{d})

≤ 2τ(d) ∑_{u≤\sqrt{x/d}} π(x; du, 1).  (10)

On the other hand, since du = \sqrt{d} · u\sqrt{d} ≤ \sqrt{d} · \sqrt{x} ≤ x^{\frac{1}{2} − \frac{β}{2}} · x^{\frac{1}{2}} = x^{1− \frac{β}{2}} , we have, in light of Lemma 11, that

π(x; du, −1) ≤ ξ_{1} \frac{x}{φ(du) log(x/du)} ≤ ξ_{2} \frac{x}{φ(du) log x},  (11)

with ξ_{2} = 2ξ_{1}/β. Using (11) in (10) and keeping in mind that φ(d)φ(u) ≤ φ(du) for positive integers d, u, we obtain that

E ≤ 2ξ_{2} \frac{x}{log x}τ(d) ∑_{u≤\sqrt{x/d}} \frac{1}{φ(du)}

≤ 2ξ_{2} \frac{x}{log x} \frac{τ(d)}{φ(d)} ∑_{u≤\sqrt{x/d}} \frac{1}{φ(u)}

≤ ξ_{3}x\frac{τ(d)}{φ(d)},

for some positive constant ξ_{3}, where we used the fact that ∑_{n≤y} \frac{1}{φ(n)} ≪ log y, thus completing

the proof of the lemma.

Lemma 14. Given fixed numbers A > 0 and κ < α, then

∑_{d≥log^{A} x} \frac{τ(d)}{dγ(d)^{α}} ≪ \frac{1}{log^{Aκ} x}.

Proof. Clearly we have

∑_{d≥log^{A} x} \frac{τ(d)}{dγ(d)^{α}} ≤ ∑_{d≥log^{A} x} \frac{τ(d)}{dγ(d)^{α}} (\frac{d}{log^{A} x})^{κ}
= \frac{1}{log^{Aκ} x} ∑_{d≥log^{A} x} \frac{τ(d)}{d^{1−κ}γ(d)^{α}}
< \frac{1}{log^{Aκ} x} ∏_{p} (1 + \frac{2}{p^{1−κ}p^{α}} + \frac{2}{p^{2(1−κ)}p^{α}} + …)
≪ \frac{1}{log^{Aκ} x},

since the above infinite product converges in light of the fact that κ < α. Lemma 15. Given a fixed positive integer D, then

∑_{{n≤x \atop gcd(n,D)=1}} \frac{1}{φ(n)} = c_{D} log x + O(1),

where

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

Remark 16. Note that the result of Lemma 15 is known in a more precise form (see the book of Montgomery and Vaughan [5, pp. 42–43]). Proof. We first compute the generating series of n/φ(n). We have

∑_{{n=1 \atop gcd(n,D)=1}}^{∞} \frac{n/φ(n)}{n^{s}} = ∏_{p|̸D} (1 + \frac{(1 − 1/p)^{−1}}{p^{s}} + \frac{(1 − 1/p)^{−1}}{p^{2s}} + …)
= \begin{matrix}∏ & p & (1 + \frac{(1−1/p)^{−1}}{p^{s}} + \frac{(1−1/p)^{−1}}{p^{2s}} + …) \\ ∏ & p|D & (1 + \frac{(1−1/p)^{−1}}{p^{s}} + \frac{(1−1/p)^{−1}}{p^{2s}} + …) \end{matrix}
= ζ(s) ∏_{p} (1 − \frac{1}{p^{s}} ) \begin{matrix}∏ & p & (1 + \frac{(1−1/p)^{−1}}{p^{s}} + \frac{(1−1/p)^{−1}}{p^{2s}} + …) \\ ∏ & p|D & (1 + \frac{(1−1/p)^{−1}}{p^{s}} + \frac{(1−1/p)^{−1}}{p^{2s}} + …) \end{matrix}
= ζ(s) ∏_{p} (1 + \frac{1}{p^{s}(p − 1)}) ∏_{p|D} (1 + \frac{p}{(p − 1)(p^{s} − 1)})^{−1} ,

which by Wintner’s Theorem yields

∑_{{n≤x \atop gcd(n,D)=1}} \frac{n}{φ(n)} = c_{D}x + O(x^{1/2} log x),  (12)

where

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

Then, using partial summation, we get that

∑_{{n≤x \atop gcd(n,D)=1}} \frac{1}{φ(n)} = c_{D} + O (\frac{log x}{x^{1/2}}) + ∫_{1}^{x} c_{D} \frac{dt}{t} + O(1) = c_{D} log x + O(1),

as required. Lemma 17. For each integer δ ≥ 2, let G_{δ} be the semigroup generated by the prime factors of δ, i.e. for δ = q_{1}^{α_{1}} … q_{r}^{α_{r}}, let G_{δ} = {q_{1}^{β_{1}} … q_{r}^{β_{r}} : β_{i} ≥ 0}. Then

∑_{n∈G_{δ}} \frac{1}{n} = ∑_{{n=1 \atop γ(n)|δ}}^{∞} \frac{1}{n} ≪ log log δ.

Proof. Using the well known result of Landau

lim sup_{n→∞} \frac{n}{φ(n) log log n} = e^{γ},

we certainly have that there exists some constant C > 0 such that

\frac{n}{φ(n)} < C log log n (n ≥ 3),

from which is follows easily that

∑_{{n=1 \atop γ(n)|δ}}^{∞} \frac{1}{n} = ∏_{p|δ} (1 + \frac{1}{p} + \frac{1}{p^{2}} + …) = ∏_{p|δ} (1 − \frac{1}{p})^{−1}
= \frac{δ}{φ(δ)} < C log log δ,

which proves our result. Lemma 18. Let G_{δ} be as in Lemma 17. Then

∑_{δ=1}^{∞} \frac{|h(δ)|2^{ω(δ)}}{δ} ∑_{b∈G_{δ}} \frac{1}{b} < +∞.

Proof. In light of Lemma 17, the fact that |h(δ)| ≤ \frac{c}{γ(δ)^{α}} and since given any ε > 0, log δ < δ^{ε} provided δ ≥ δ_{0}(ε), we have

∑_{δ=1}^{∞} \frac{|h(δ)|2^{ω(δ)}}{δ} ∑_{b∈G_{δ}} \frac{1}{b} ≪ ∑_{δ=1}^{∞} \frac{|h(δ)|2^{ω(δ)} log log δ}{δ}
≪ ∑_{δ=1}^{∞} \frac{2^{ω(δ)} log log δ}{δγ(δ)^{α}}
≪ ∑_{δ=δ_{0}}^{∞} \frac{2^{ω(δ)}}{δ^{1−ε}γ(δ)^{α}}
< ∏_{p} (1 + \frac{2}{p^{1−ε}p^{α}} + \frac{2}{p^{2−2ε}p^{α}} + …)
= ∏_{p} (1 + \frac{2}{p^{α}(p^{1−ε} − 1)}) < +∞,

provided ε < α.

Lemma 19. Let G_{δ} be as in Lemma 17 and let ρ(x) be a real function which tends to +∞ as x → ∞. Given any fixed positive constant κ < α, we have

Z(x) := ∑_{{ρ(x)<δb≤x \atop b∈G_{δ}}} \frac{h(δ)2^{ω(δ)}}{δb} ≪ \frac{1}{ρ(x)^{κ}} .

Proof. We have

|Z(x)| ≤ ∑_{{δb>ρ(x) \atop b∈G_{δ}}} \frac{|h(δ)| · 2^{ω(δ)}}{δb} = ∑_{{δb>ρ(x) \atop δ<ρ(x)}} + ∑_{{δb>ρ(x) \atop δ≥ρ(x)}} = Z_{1} + Z_{2},  (13)

say. We first estimate Z_{2}. Recalling that |h(δ)| ≤ c/γ(δ)^{α},

Z_{2} ≤ ∑_{δ≥ρ(x)} \frac{|h(δ)| · 2^{ω(δ)}}{δ} ∏_{p|δ} (1 + \frac{1}{p} + \frac{1}{p^{2}} + …)
≤ ∑_{δ=1}^{∞} \frac{|h(δ)| · 2^{ω(δ)}}{δ} ∏_{p|δ} \frac{1}{1 − 1/p} · (\frac{δ}{ρ(x)})^{κ}
≤ \frac{c}{ρ(x)^{κ}} ∑_{δ=1}^{∞} \frac{2^{ω(δ)}}{δ^{1−κ}γ(δ)^{α}} ∏_{p|δ} \frac{1}{1 − 1/p}.  (14)

Define

f(δ) := \frac{2^{ω(δ)}}{δ^{1−κ}γ(δ)^{α}} ∏_{p|δ} \frac{1}{1 − 1/p}.

Clearly f is a multiplicative function with the following values on prime powers:

f(q^{a}) = \frac{2}{q^{α} · q^{a(1−κ)}(1 − 1/q)}.

Moreover, f is such that ∑_{δ=1}^{∞} f(δ) is bounded provided κ < α. Hence, taking this into account in (14), we obtain that

Z_{2} ≪ \frac{1}{ρ(x)^{κ}} .  (15)

We now move on to estimate Z_{1}. We have

Z_{1} ≤ ∑_{δ<ρ(x)} \frac{|h(δ)|2^{ω(δ)}}{δ} ∑_{{b>ρ(x)/δ \atop b∈G_{δ}}} \frac{1}{b} ≤ ∑_{δ<ρ(x)} \frac{|h(δ)|2^{ω(δ)}}{δ} ∑_{b∈G_{δ}} \frac{1}{b} (\frac{bδ}{ρ(x)})^{κ}

= \frac{1}{ρ(x)^{κ}} ∑_{δ<ρ(x)} \frac{|h(δ)|2^{ω(δ)}}{δ^{1−κ}} ∑_{b∈G_{δ}} b^{κ−1}.  (16)

Since

∑_{b∈G_{δ}} b^{κ−1} ≤ ∏_{p|δ} (1 + \frac{1}{p^{1−κ}} + \frac{1}{p^{2(1−κ})} + …) = ∏_{p|δ} (1 − \frac{1}{p^{1−κ}} )^{−1} ,

it follows from (16) and the fact that |h(δ)| ≤ c/γ(δ)^{α}, that

Z_{1} ≤ \frac{c}{ρ(x)^{κ}} ∑_{δ<ρ(x)} \frac{2^{ω(δ)}}{γ(δ)^{α}δ^{1−κ}} ∏_{p|δ} (1 − \frac{1}{p^{1−κ}} )^{−1} = \frac{c}{ρ(x)^{κ}} ∑_{δ<ρ(x)} g(δ),  (17)

say, where g is clearly a multiplicative function whose values at the prime powers are given by

g(q^{a}) = \frac{2}{q^{α} · q^{a(1−κ)}} (1 + \frac{1}{q^{1−κ}} + \frac{1}{q^{2(1−κ})} + …) .

Since we assumed that κ < αand since ∑_{a=1}^{∞} g(q^{a}) < \frac{c_{3}}{q^{α+1−κ}}, with a suitable constant c_{3} > 0,

it follows that

∑_{δ=1}^{∞} g(δ) = ∏_{p}(1 + g(p) + g(p^{2}) + …) < +∞.

Using this information, (17) yields

Z_{1} ≪ \frac{1}{ρ(x)^{κ}} .  (18)

Substituting (15) and (18) in (13), the lemma is proved.

4 Proof of Theorem 1

One can easily see that

F (s) := ∑_{n=1}^{∞} \frac{R(n)}{n^{s}}

can be written as

F (s) = A(s)ζ^{2}(s),  (19)

where

A(s) = ∏_{p} (1 + \frac{λ(p)}{p^{s}} + \frac{λ(p^{2})}{p^{2s}} + …) ,

with

λ(p) = 2κ(p),  λ(p^{2}) = 3κ(p^{2}) − 4κ(p),  (20)

and more generally, for each β ≥ 3, by

λ(p^{β}) = (β + 1)κ(p^{β}) − 2βκ(p^{β−1}) + (β − 1)κ(p^{β−2}).  (21)

Hence,

|λ(p^{β})| ≤ \frac{4βc}{p^{α}} (β ≥ 1).

Consequently,

|λ(d)| ≤ \frac{τ(d)^{c_{4}}}{γ(d)^{α}} ,  (22)

where c_{4} is a suitable constant (c_{4} = 4c will do).

Now observe that, in light of (19) and of Lemma 5,

T (x) = ∑_{d≤x} λ(d)D(x/d)

= ∑_{d≤x} λ(d) (\frac{x}{d} log(\frac{x}{d}) + (2γ − 1)\frac{x}{d}) + O (x^{θ} ∑_{d≤x} \frac{|λ(d)|}{d^{θ}}) .  (23)

It follows from (22) and Lemma 8 that

∑_{d>x} \frac{|λ(d)|}{d} ≤ ∑_{d>x} \frac{cτ(d)^{c_{4}}}{dγ(d)^{α}} ≪ x^{ε−α}.  (24)

Indeed, we have

S_{U} := ∑_{d∈[U,2U]} \frac{τ(d)^{c_{4}}}{dγ(d)} < U^{ε} ∑_{d∈[U,2U]} \frac{1}{dγ(d)} = U^{ε}K_{U},

say, provided U is sufficiently large. Now, from Lemma 8, it follows that K_{U} ≤ \frac{c}{U^{α}}. Hence, if we set U_{j} = 2^{j}x for j = 0, 1, …, then, if x is large enough,

∑_{d>x} \frac{|λ(d)|}{d} ≤ c ∑_{j=0}^{∞} \frac{U_{j}^{ε}}{U_{j}^{α}} = c x^{ε−α} ∑_{j=0}^{∞} \frac{1}{2^{j(α−ε)}} ≪ x^{ε−α}.

Similarly, observing that τ(d)^{c_{4}}(c + log d) ≤ d^{ε} and arguing in a similar way, one can easily proves that

∑_{d>x} \frac{|λ(d)| · |c + log d|}{d} ≪ x^{ε−α}.  (25)

Substituting (24) and (25) in (23), one obtains

T (x) = A_{0}x log x + B_{0}x + O (x^{1−α+ε}) + O (x^{θ} ∑_{d≤x} \frac{|λ(d)|}{d^{θ}}) ,  (26)

where A_{0} = ∑_{d=1}^{∞} \frac{λ(d)}{d} and B_{0} = ∑_{d=1}^{∞} \frac{λ(d)}{d}(2γ − 1 − log d).

Since

∑_{d≤x} \frac{|λ(d)|}{d^{θ}} ≤ ∑_{d≤x} \frac{cτ(d)^{c_{4}}}{d^{θ}γ(d)^{α}} ≤ \{ \begin{matrix}x^{ε}, & if θ + α ≥ 1; \\ x^{1−(θ+α)}, & if θ + α < 1; \end{matrix}

it follows that

x^{θ} ∑_{d≤x} \frac{|λ(d)|}{d^{θ}} ≤ \{ \begin{matrix}x^{θ+ε}, & if θ + α ≥ 1; \\ x^{1−α}, & if θ + α < 1. \end{matrix}

Using this last estimate in (26) completes the proof of Theorem 1.

5 Proof of Theorem 2

Since

∑_{n=1}^{∞} \frac{2^{ω(n)}}{n^{s}} = \frac{ζ^{2}(s)}{ζ(2s)} (ℜ(s) > 1),

we have that

2^{ω(n)} = ∑_{d^{2}e=n} μ(d)τ(e).  (27)

Let G_{δ} be as in the statement of Lemma 17. If δ|n, then let m be the largest divisor of n/δ which is co-prime with δ, and let b = b(δ) ∈ G_{δ} be defined implicitly by n = δ · b · m. Note that with this setup, the numbers m and b are uniquely determined, and we therefore have 2^{ω(n)} = 2^{ω(δ)} · 2^{ω(m)}. Hence,

S(x) = ∑_{δ≤x} h(δ)2^{ω(δ)} ∑_{{b≤x/δ \atop b∈G_{δ}}} ∑_{{m≤ \frac{x}{δb} \atop gcd(m,δ)=1}} 2^{ω(m)}

= ∑_{δ≤x} h(δ)2^{ω(δ)} ∑_{{b≤x/δ \atop b∈G_{δ}}} E_{δ} (\frac{x}{δb}) ,  (28)

say. We therefore need to estimate

E_{k}(X) := ∑_{{n≤X \atop gcd(n,k)=1}} 2^{ω(n)}.

Observe that it follows from (27) that

E_{k}(X) = ∑_{{d≤\sqrt{X} \atop gcd(d,k)=1}} μ(d) ∑_{{d^{2}e≤X \atop gcd(e,k)=1}} τ(e) = ∑_{{d≤\sqrt{X} \atop gcd(d,k)=1}} μ(d)V_{k} (\frac{X}{d^{2}} ) ,  (29)

where

V_{k}(y) := ∑_{{n≤y \atop gcd(n,k)=1}} τ(n),

while we trivially have

E_{k}(X) ≪ X log X.  (30)

We shall now make use of a function ρ(x) satisfying

exp \{\sqrt{log x}\} ≤ ρ(x) ≤ \sqrt{x}  (31)

and which we will later determine more precisely.

We first write (29) as

E_{k}(X) = ∑_{{d≤ρ(X) \atop gcd(d,k)=1}} μ(d)V_{k} (\frac{X}{d^{2}} ) + ∑_{{ρ(X)<d≤\sqrt{X} \atop gcd(d,k)=1}} μ(d)V_{k} (\frac{X}{d^{2}} )
= W_{1}(X) + W_{2}(X),  (32)

say.

It follows from Lemma 7 that

W_{2}(X) ≪ ∑_{ρ(X)<d≤\sqrt{X}} \frac{X}{d^{2}} log(X/d^{2}) ≤ X log X ∑_{d>ρ(X)} \frac{1}{d^{2}}
≪ \frac{X}{ρ(X)} log X ≪ \frac{X}{log X} .  (33)

On the other hand, again using Lemma 7, we have

W_{1}(X) = ∑_{{d≤ρ(X) \atop gcd(d,k)=1}} μ(d) \{B_{1}(k)\frac{X}{d^{2}} log (\frac{X}{d^{2}} )

+B_{2}(k)\frac{X}{d^{2}} + O (k^{10/3} (\frac{X}{d^{2}} )^{1/3} log (\frac{X}{d^{2}} ))\}

= X log XB_{1}(k) ∑_{{d≤ρ(X) \atop gcd(d,k)=1}} \frac{μ(d)}{d^{2}} − 2XB_{1}(k) ∑_{{d≤ρ(X) \atop gcd(d,k)=1}} \frac{μ(d) log d}{d^{2}}
+ XB_{2}(k) ∑_{{d≤ρ(X) \atop gcd(d,k)=1}} \frac{μ(d)}{d^{2}} + O (k^{10/3}X^{1/3} log X) .  (34)

Since

∑_{{d≤ρ(X) \atop gcd(d,k)=1}} \frac{μ(d)}{d^{2}} = ∑_{{d=1 \atop gcd(d,k)=1}}^{∞} \frac{μ(d)}{d^{2}} + O (\frac{1}{ρ(X)}) = \frac{6}{π^{2}} ∏_{p|k} (1 − \frac{1}{p^{2}} )^{−1} + O (\frac{1}{ρ(X)})

= η_{k} + O (\frac{1}{ρ(X)})  (35)

say, and since

∑_{{d≤ρ(X) \atop gcd(d,k)=1}} \frac{μ(d) log d}{d^{2}} = ∑_{{d=1 \atop gcd(d,k)=1}}^{∞} \frac{μ(d) log d}{d^{2}} + O (\frac{1}{ρ(X)}) = μ_{k} + O (\frac{log X}{ρ(X)} ) ,  (36)

say, it follows that (34) can be written as

W_{1}(X) = X log XB_{1}(k)η_{k} − 2XB_{1}(k)μ_{k} + XB_{2}(k)η_{k} + O (\frac{X}{log X} ) + O (k^{10/3}X^{1/3} log X) .

(37)

Let us then write (28) as

S(x) = ∑_{{δb≤ρ(x) \atop b∈G_{δ}}} h(δ)2^{ω(δ)}E_{δ} (\frac{x}{δb}) + ∑_{{ρ(x)<δb≤x \atop b∈G_{δ}}} h(δ)2^{ω(δ)}E_{δ} (\frac{x}{δb})
= Z_{1}(x) + Z_{2}(x),  (38)

say.

First of all, we have using (30) and Lemma 19,

Z_{2}(x) ≪ ∑_{{ρ(x)<δb≤x \atop b∈G_{δ}}} \frac{h(δ)2^{ω(δ)}}{δb} x log(x/δb) ≪ x log x\frac{1}{ρ(x)^{κ}} ≪ \frac{x}{log x}.  (39)

On the other hand, substituting (33) and (37) in (32), we get that Z_{1}(x) from (38) can be written as

Z_{1}(x) = ∑_{{δb≤ρ(x) \atop b∈G_{δ}}} h(δ)2^{ω(δ)} \{\frac{x}{δb} log (\frac{x}{δb}) B_{1}(δ)η_{δ} + (B_{2}(δ)η_{δ} − 2B_{1}(δ)μ_{δ})\frac{x}{δb}

+O (\frac{\frac{x}{δb}}{log(\frac{x}{δb})}) + (δ^{10/3} (\frac{x}{δb})^{1/3} log (\frac{x}{δb}))\}

= x log x ∑_{{δb≤ρ(x) \atop b∈G_{δ}}} \frac{h(δ)2^{ω(δ)}}{δb} B_{1}(δ)η_{δ}

+x ∑_{{δb≤ρ(x) \atop b∈G_{δ}}} \frac{h(δ)2^{ω(δ)}}{δb} (B_{2}(δ)η_{δ} − 2B_{1}(δ)μ_{δ} − B_{1}(δ)η_{δ} log(δb))

+O (x ∑_{{δb≤ρ(x) \atop b∈G_{δ}}} \frac{h(δ)2^{ω(δ)}}{δb log(x/(δb))})

+O ( ∑_{{δb≤ρ(x) \atop b∈G_{δ}}} h(δ)2^{ω(δ)}δ^{10/3} (\frac{x}{δb})^{1/3} log (\frac{x}{δb}))

= (x log x)T_{1}(x) + x T_{2}(x) + O(T_{3}(x)) + O(T_{4}(x)),  (40)

say.

First, it follows from Lemma 18 that

T_{3}(x) ≪ \frac{x}{log x}  (41)

and that

T_{4}(x) ≪ x^{1/3} log x ∑_{δb≤ρ(x)} ∑_{b∈G_{δ}} \frac{h(δ)2^{ω(δ)}}{δb} δ^{4}b^{2/3}

≪ x^{1/3} log x(ρ(x))^{4} ∑_{δ=1}^{∞} ∑_{b∈G_{δ}} \frac{h(δ)2^{ω(δ)}}{δb}
≪ x^{1/3} log x(ρ(x))^{4} ≪ \frac{x}{log x}.  (42)

On the other hand, using Lemma 19, we have

T_{1}(x) = ∑_{{δ=1 \atop b∈G_{δ}}}^{∞} \frac{h(δ)2^{ω(δ)}B_{1}(δ)η_{δ}}{δb} − ∑_{{ρ(x)<δb≤x \atop b∈G_{δ}}} \frac{h(δ)2^{ω(δ)}B_{1}(δ)η_{δ}}{δb}

= t_{1} + O (\frac{1}{ρ(x)^{κ}} ) ,  (43)

say. Similarly, one can prove that

T_{2}(x) = t_{2} + O (\frac{1}{ρ(x)^{κ}} ) ,  (44)

say.

Substituting (41), (42), (43) and (44) in (40), we get

Z_{1}(x) ≪ \frac{x log x}{ρ(x)^{κ}}.  (45)

Gathering (39) and (45) in (38), we obtain

Z(x) ≪ \frac{x log x}{ρ(x)^{κ}}.

Choosing ρ(x), already introduced in (31), in such a way that

\frac{log x}{ρ(x)^{κ}} ≪ \frac{1}{log x}

completes the proof of Theorem 2.

6 Proofs of Theorems 3 and 4

Defining

S_{d}(x) := ∑_{p≤x ; {p≡1 mod d \atop gcd( \frac{p−1}{d} ,d)=1}} τ(p − 1),

it is clear that

M(x) = ∑_{d≤x−1} κ(d)S_{d}(x).  (46)

Moreover, let

E_{d}(x) := ∑_{{p≤x \atop p≡1 (mod d)}} 2^{ω(p−1)}  and  H_{d,δ}(x) := ∑_{p≤x ; {p≡1 (mod d) \atop p≡1 (mod δ^{2})}} τ (\frac{p − 1}{δ^{2}}) .

Since

U(n) = 2^{ω(n)} ∑_{d|n} h(d),

it follows that

N(x) = ∑_{d≤x−1} h(d)E_{d}(x).  (47)

On the other hand, since

2^{ω(n)} = ∑_{δ^{2}e=n} μ(δ)τ(e),

we have

E_{d}(x) = ∑_{δ≤\sqrt{x−1}} μ(δ)H_{d,δ}(x).

It follows from Lemma 13 that

E_{d}(x), S_{d}(x) ≤ c_{5} \frac{τ(d)}{φ(d)}x say, for d ≤ \sqrt{x},  (48)

while it is clear that

∑_{{p≤x \atop p≡1 (mod d)}} τ(p − 1) ≤ τ(d) ∑_{n≤x/d} τ(n) ≤ \frac{c_{6}x log x · τ(d)}{d} for 1 ≤ d ≤ x,

and therefore,

E_{d}(x), S_{d}(x) ≤ c_{7} \frac{τ(d)}{d}x log x.  (49)

Let A be a large constant. We shall now estimate

T_{1} := ∑_{log^{A} x≤d≤x−1} |κ(d)|S_{d}(x) and T_{2} := ∑_{log^{A} x≤d≤x−1} |h(d)|E_{d}(x).

From (48) and (49), we have

T_{1} ≪ x log x ∑_{d≥\sqrt{x}} \frac{τ(d)}{dγ(d)^{α}} + x ∑_{d≥log^{A} x} \frac{τ(d)}{dγ(d)^{α}} = x log x · U_{1} + x · U_{2},  (50)

say. Given a positive constant κ < α, we have that

U_{1} ≤ ∑_{d=1}^{∞} \frac{τ(d)}{dγ(d)^{α}} (\frac{d}{\sqrt{x}})^{κ} = \frac{1}{x^{κ/2}} ∑_{d=1}^{∞} \frac{τ(d)}{γ(d)^{α}d^{1−κ}}

≤ \frac{1}{x^{κ/2}} ∏_{p} (1 + ∑_{a=1}^{∞} \frac{τ(p^{a})}{p^{α} · p^{a(1−κ)}} ) ,  (51)

where this last product, which we denote by Q, is convergent provided κ < α. In a similar way, we obtain

U_{2} ≤ ∑_{d=1}^{∞} \frac{τ(d)}{dγ(d)^{α}} (\frac{d}{log^{A} x})^{κ} ≤ \frac{1}{log^{Aκ} x}Q.  (52)

Substituting (51) and (52) in (50), we get that

T_{1} ≪ \frac{x}{log^{κA−1} x}  (0 < κ < α).  (53)

In a similar manner, we obtain

T_{2} ≪ \frac{x}{log^{κA−1} x}  (0 < κ < α).  (54)

We further define

M_{1}(x) = ∑_{d≤log^{A} x} κ(d)S_{d}(x),  (55)
N_{1}(x) = ∑_{d≤log^{A} x} h(d)E_{d}(x).  (56)

Let us first fix d ≤ log^{A} x and move on to estimate S_{d}(x) and E_{d}(x), by using the Bombieri-Vinogradov Theorem.

It turns out that it is more convenient to estimate

S_{d}(x) − S_{d}(x/2)  and  E_{d}(x) − E_{d}(x/2)

and similarly for x/2, x/2^{2}, … in place of x. This is why, for any fixed integer r ≥ 1, we write

M_{1}(x) = ∑_{d≤log^{A} x} κ(d) ∑_{j=0}^{r} A_{d}(x/2^{j}) + O (\frac{x}{2^{r}} ) + O (\frac{x}{log^{Aκ} x}) ,  (57)

where

A_{d}(x/2^{j}) = S_{d}(x/2^{j}) − S_{d}(x/2^{j+1}).

Similarly, for any fixed integer r ≥ 1, we may write

N_{1}(x) = ∑_{d≤log^{A} x} h(d) ∑_{j=0}^{r} B_{d}(x/2^{j}) + O (\frac{x}{2^{r}} ) + O (\frac{x}{log^{Aκ} x}) ,  (58)

where

B_{d}(x/2^{j}) = E_{d}(x/2^{j}) − E_{d}(x/2^{j+1}).

For now, fix x and set

r := ⌊\frac{Aκ log log x}{log 2}⌋ so that 2^{r} ≈ log^{Aκ} x.  (59)

We now proceed to estimate A_{d}(x) and B_{d}(x). Clearly we have

A_{d}(x) = ∑_{\frac{x}{2} <p≤x ; {gcd( \frac{p−1}{d} ,d)=1 \atop p≡1 (mod d)}} τ(p − 1) = τ(d) ∑_{\frac{x}{2} <p≤x ; {gcd( \frac{p−1}{d} ,d)=1 \atop p≡1 (mod d)}} τ(\frac{p − 1}{d}).  (60)

Observe that

τ(n) = 2#{(u, v) : u < v and uv = n} + θ_{n},

where

θ_{n} = \{ \begin{matrix}1, & if n = square; \\ 0, & otherwise. \end{matrix}

Thus, in light of (60),

A_{d}(x) = τ(d) ∑_{{\frac{x}{2} <p≤x \atop p≡1 (mod d)}} #\{(u, v) : u < v, gcd(uv, d) = 1, uv = \frac{p − 1}{d}\} + O (\sqrt{x}) , (61)

where the error term is there to account for those p for which \frac{p−1}{d} = u^{2}.

It is clear that in the sum appearing in (61), we have u ≤ \sqrt{x}. On the other hand, the contribution of those u’s for which u > \sqrt{x}/(log^{B} x) can be bounded above, using Lemma 11, by

τ(d) ∑_{{\sqrt{x}/(log^{B} x)<u≤\sqrt{x} \atop gcd(u,d)=1}} π(x; du, 1) ≤ c_{8}τ(d)\frac{li(x)}{φ(d)} ∑_{{\sqrt{x}/(log^{B} x)<u≤\sqrt{x} \atop gcd(u,d)=1}} \frac{1}{φ(u)}

≤ c_{9}τ(d)\frac{li(x)}{φ(d)}B log log x,  (62)

where we also used Lemma 15.

Concerning the equation \frac{p−1}{d} = uv, the condition gcd(uv, d) = 1 is satisfied if and only if gcd(u, d) = 1 and v ≡ ℓ (mod d) for some positive integer ℓ co-prime to d, meaning that v = ℓ + dt and p − 1 = du(ℓ + dt) = duℓ + d^{2}ut for some integer t.

In light of these observations and of (62), relation (61) can be replaced by

A_{d}(x) = τ(d) ∑_{{u≤\sqrt{x}/(log^{B} x) \atop gcd(u,d)=1}} ∑_{gcd(ℓ,d)=1} (π(x; d^{2}u, 1 + duℓ) − π(\frac{x}{2}; d^{2}u, 1 + duℓ))

+O (\frac{τ(d)}{φ(d)}(li(x)) log log x) .  (63)

We shall assume that B is sufficiently large to insure that d^{2}u ≤ \sqrt{x}/(log^{Δ} x), for some large number Δ.

Using Lemma 12, (63) becomes

A_{d}(x) = τ(d) (li(x) − li(x/2)) ∑_{{u≤\sqrt{x}/(log^{B} x) \atop gcd(u,d)=1}} ∑_{gcd(ℓ,d)=1} \frac{1}{φ(d^{2}u)}

+O (\frac{τ(d)}{φ(d)}(li(x)) log log x) .

But observe that in the above sum, we have

∑_{gcd(ℓ,d)=1} \frac{1}{φ(d^{2}u)} = \frac{1}{φ(u)} · \frac{φ(d)}{dφ(d)} = \frac{1}{φ(u)} · \frac{1}{d},

so that

A_{d}(x) = \frac{τ(d)}{d} (li(x) − li(x/2)) ∑_{{u≤\sqrt{x}/(log^{B} x) \atop gcd(u,d)=1}} \frac{1}{φ(u)} + O (\frac{τ(d)}{φ(d)}(li(x)) log log x)

= \frac{1}{4} \frac{τ(d)c_{d}}{d} x + O (\frac{x log log x}{log x}) ,  (64)

(c_{d} being the constant appearing in the statement of Lemma 15) where we used Lemma 15 and the fact that

(li(x) − li(x/2)) · (\frac{1}{2} log x − B log log x) = \frac{1}{4}x + O (\frac{x log log x}{log x})

and that

\frac{τ(d)}{φ(d)}li(x) log log x = O (\frac{x log log x}{log x}) .

Substituting (64) in (57) and taking into account the choice of r made in (59), we get

M_{1}(x) = ∑_{d≤log^{A} x} κ(d) ∑_{j=0}^{r} A_{d}(x/2^{j}) + O (\frac{x}{log^{Aκ} x})

= \frac{1}{4} ∑_{d≤log^{A} x} \frac{κ(d)τ(d)c_{d}}{d} ∑_{j=0}^{r} \frac{x}{2^{j}} + O (\frac{x(log log x)^{2}}{log x} )

= \frac{1}{2}x ∑_{d≤log^{A} x} \frac{κ(d)τ(d)c_{d}}{d} + O (\frac{x(log log x)^{2}}{log x} )  (65)

provided A is chosen so that Aκ > 1. Finally, using Lemma 14, recalling the initial formulation of M(x) given in (46) and using (65), we get

M(x) = x\frac{1}{2} ∑_{d=1}^{∞} \frac{κ(d)τ(d)c_{d}}{d} + O (\frac{x(log log x)^{2}}{log x} ) ,

thus completing the proof of Theorem 3.

We now move to complete the proof of Theorem 4. For this, we shall use essentially the same kind of technique to obtain an estimate for E_{d}(x) for d ≤ log^{A} x.

Since

Q_{d,δ}(x) := ∑_{n≤x/δ^{2}} τ(n) ≤ \frac{c_{10}x log x}{δ^{2}},

it follows that

E_{d}(x) = ∑_{δ≤log^{B} x} μ(δ)Q_{d,δ}(x) + O (\frac{x}{d} \frac{1}{log^{2} x}) ,

provided B is sufficiently large.

We shall now estimate Q_{d,δ}(x) assuming that d ≤ log^{A} x and δ ≤ log^{B} x.

We proceed to estimate

B(x) = B_{d,δ}(x) := Q_{d,δ}(x) − Q_{d,δ}(x/2).

We have

B(x) = 2 ∑_{{\frac{x}{2} <p≤x \atop p≡1 (mod δ^{2})}} #\{(u, v) : u < v, uv = \frac{p − 1}{δ^{2}}, d|δ^{2}uv\} + O(\sqrt{x}).

As in the proof of Theorem 3, we can drop in the above solution count those pairs u, v for which u > \sqrt{x}/(log^{Δ} x) for any fixed Δ > 0, arbitrarily large.

Now let K, L ∈ G_{d}. Given u, v such that uv = \frac{p−1}{δ^{2}}, write u = Kũ and v = Lṽ, where gcd(ũ, d) = gcd(ṽ, d) = 1. We then have

\frac{p − 1}{δ^{2}} = KLũṽ.  (66)

And in order to guarantee that gcd(ṽ, d) = 1, we seek ṽ from the arithmetical progression ṽ = ℓ + td with gcd(ℓ, d) = 1. It follows from (66) that

p − 1 = δ^{2}KLũ(ℓ + td) = δ^{2}KLũℓ + δ^{2}KLdũt.

With this set up, we have

B(x) = 2 ∑_{K,L∈G_{d}} ∑_{gcd(ℓ,d)=1} ∑_{{ũ≤(\sqrt{x}/K)/ log^{Δ} x \atop gcd(ũ,d)=1}} (π(x; δ^{2}KLdũ, δ^{2}KLũℓ + 1)

− π(x/2; δ^{2}KLdũ, δ^{2}KLũℓ + 1)) + O(\sqrt{x}).  (67)

First we drop all pairs K, L for which KL > log^{D} x, where D is a fixed large number. Indeed observe that

∑_{{log^{D} x<KL≤x^{1/10} \atop K,L∈G_{d}}} ∑_{ũ≤\sqrt{x}} ∑_{ℓ (mod d)} π(x; δ^{2}KLdũ, δ^{2}KLũℓ + 1)

+ ∑_{{x^{1/10}<KL≤x \atop K,L∈G_{d}}} ∑_{ũ≤\sqrt{x}} \frac{xφ(d)}{δ^{2}KLdũ}

≤ li(x) ∑_{{KL>log^{D} x \atop K,L∈G_{d}}} ∑_{ũ≤\sqrt{x}} \frac{φ(d)}{φ(δ^{2}KLdũ)} + ∑_{{x^{1/10}<KL≤x \atop K<L∈G_{d}}} \frac{x}{KL} \frac{log x}{φ(δ^{2})}

≤ \frac{li(x)}{φ(δ^{2})} · log x · ∑_{{KL>log^{D} x \atop K,L∈G_{d}}} \frac{1}{φ(KL)} + \frac{x log x}{φ(δ^{2})} ∑_{{KL>x^{1/10} \atop K,L∈G_{d}}} \frac{1}{KL}

= \frac{li(x)}{φ(δ^{2})} · log x · H_{δ}(x) + \frac{x log x}{φ(δ^{2})} · J_{δ}(x),  (68)

say.

First of all, using the fact that \frac{1}{φ(n)} ≪ \frac{log log n}{n}, we have, for a fixed κ > 0,

H_{δ}(x) ≤ c_{11} log log log x ∑_{{KL>log^{D} x \atop K,L∈G_{d}}} \frac{1}{KL} ≤ c_{11} log log log x ∑_{{KL>log^{D} x \atop K,L∈G_{d}}} \frac{1}{KL} (\frac{KL}{log^{D} x})^{κ}

≤ c_{11} \frac{log log log x}{log^{Dκ} x} ∏_{p|d} (\frac{1}{1 − \frac{1}{p^{1−κ}}} )^{2} .  (69)

Choosing κ = 1/2 and observing that for d < log^{A} x, we have that ω(d) ≪ \frac{log d}{log log d}. Therefore for such a number d,

∏_{p|d} (\frac{1}{1 − \frac{1}{\sqrt{p}}} )^{2} < c_{12}4^{ω(d)} < (log x)^{ε},

for any ε > 0 arbitrarily small. Using this observation, we may conclude from (69) that

H_{δ}(x) ≤ \frac{c_{13}}{(log x)^{D/3}} ,  (70)

say. Proceeding in a somewhat similar manner, we get that

J_{δ}(x) = ∑_{{KL>x^{1/10} \atop K,L∈G_{d}}} \frac{1}{KL} ≤ ∑_{{KL>x^{1/10} \atop K,L∈G_{d}}} \frac{1}{KL} (\frac{KL}{x^{1/10}} )^{1/2}

≤ \frac{1}{x^{1/20}} ∏_{p|d} \frac{1}{(1 − \frac{1}{\sqrt{p}})^{2}} < \frac{(log x)^{ε}}{x^{1/20}} .  (71)

Estimates (68), (70) and (71) therefore establish that we can drop from the sum in (67) those K, L ∈ G_{d} for which KL > log^{D} x for a large D, the error thus created being no larger

than O (\frac{li(x)}{(log x)^{D/3}} ). In light of these observations and using the fact that φ(δ^{2}KLdũ) =

KLφ(δ^{2}dũ) and that

∑_{{K,L∈G_{d} \atop KL<(log x)^{D}}} \frac{1}{KL} = ∑_{K,L∈G_{d}} \frac{1}{KL} − ∑_{{K,L∈G_{d} \atop KL≥(log x)^{D}}} \frac{1}{KL} = ∏_{p|G_{d}} (1 − \frac{1}{p})^{−2} + O (\frac{li(x)}{(log x)^{D/3}} ) ,

we may write (67) as

B(x) = 2(li(x) − li(x/2)) ∑_{{KL<(log x)^{D} \atop K,L∈G_{d}}} ∑_{{ũ<\sqrt{x}/(log x)^{Δ} \atop gcd(ũ,d)=1}} \frac{φ(d)}{φ(δ^{2}KLdũ)} + O (\frac{li(x)}{(log x)^{D/3}} )

= 2(li(x) − li(x/2)) ∏_{p∈G_{d}} (1 − \frac{1}{p})^{−2} ∑_{{ũ<\sqrt{x}/(log x)^{Δ} \atop gcd(ũ,d)=1}} \frac{φ(d)}{φ(δ^{2}dũ)} + O (\frac{li(x)}{(log x)^{D/3}} ) . (72)

Set

Y_{d}(x) := ∑_{{ũ<\sqrt{x}/(log x)^{Δ} \atop gcd(ũ,d)=1}} \frac{1}{φ(δ^{2}dũ)}.

In order to evaluate Y_{d}(x), we let δ = δ_{1}δ_{2}, where δ_{1} ∈ G_{d}, gcd(δ_{2}, d) = 1, and ũ = ũ_{1} · ũ_{2}, where ũ_{1} ∈ G_{δ_{2}}, gcd(ũ_{2}, dδ_{2}) = gcd(ũ_{2}, dδ) = 1. Then,

φ(δ^{2}dũ) = φ(δ_{1}^{2}δ_{2}^{2}ũ_{1})φ(ũ_{2}) = φ(δ_{1}^{2}d)φ(δ_{2}^{2}ũ_{1})φ(ũ_{2}).

It follows from Lemma 15 that

∑_{{gcd(ũ_{2},dδ)=1 \atop ũ_{2}≤y}} \frac{1}{φ(ũ_{2})} = c_{dδ} log y + O(1).  (73)

Now, the contribution of those ũ_{1} in Y_{d}(x) for which ũ_{1} ∈ G_{δ_{2}} and ũ_{1} > (log x)^{Δ_{0}} is, using (73),

≪ ∑_{{ũ_{1}∈G_{δ_{2}} \atop ũ_{1}>(log x)^{Δ_{0}}}} \frac{1}{φ(δ_{1}^{2}d)} \frac{1}{φ(δ_{2}^{2})ũ_{1}} ∑ \frac{1}{φ(ũ_{2})}

≪ (log x) ∑ \frac{1}{φ(δ_{1}^{2}d)} \frac{1}{φ(δ_{2}^{2})} ∑_{{ũ_{1}∈G_{δ_{2}} \atop ũ_{1}>(log x)^{Δ_{0}}}} \frac{1}{ũ_{1}}

≪ \frac{log x}{φ(δ_{1}^{2}d)φ(δ_{2}^{2})} \frac{1}{(log x)^{Δ_{0}/2}} ∑_{ũ_{1}∈G_{δ_{2}}} \frac{1}{\sqrt{ũ_{1}}}

≪ (log x)^{1−Δ_{0}/2} \frac{1}{δ_{1}^{2}φ(d)φ(δ_{2}^{2})} ∏_{p|δ_{2}} (1 − \frac{1}{\sqrt{p}})^{−1}

≪ (log x)^{1−Δ_{0}/2} \frac{1}{φ(d)} \frac{2^{ω(δ_{2})}}{δ_{1}^{2}δ_{2}^{2}} .

On the other hand, the contribution of those ũ_{1} ≤ (log x)^{Δ_{0}} in Y_{d}(x), as ũ_{2} runs up to y_{0} := \sqrt{x}/((log x)^{C} ũ_{1}), and also using Lemma 15 so that

∑_{{gcd(ũ_{2},dδ)=1 \atop ũ_{2}≤y_{0}}} \frac{1}{φ(ũ_{2})} = \frac{1}{2}c_{dδ} log x + O(log log x),

we get

Y_{d}(x) = \frac{1}{2}c_{dδ}(log x + log log x)\frac{1}{φ(δ_{1}^{2}d)} \frac{1}{φ(δ_{2}^{2})} ∑_{ũ_{1}∈G_{δ_{2}}} \frac{1}{ũ_{1}}

+ O (\frac{2^{ω(δ_{2})}}{δ^{2}φ(d)}(log x)^{1−C_{0}/2}) .  (74)

Observing that φ(δ_{1}^{2}d) = δ_{1}^{2}φ(d) and that

∑_{ũ∈G_{δ_{2}}} \frac{1}{ũ} = ∏_{p|G_{δ_{2}}} (1 − \frac{1}{p})^{−1} = \frac{δ_{2}}{φ(δ_{2})},

(74) becomes

Y_{d}(x) = \frac{1}{2} \frac{c_{dδ}}{φ(d)} \frac{1}{δ_{1}^{2}δ_{2}^{2}} \frac{δ_{2}}{φ(δ_{2})}(log x + log log x)
+O (\frac{2^{ω(δ_{2})}}{δ^{2}φ(d)}(log x)^{1−C_{0}/2}) .  (75)

Using (75) in (72), we obtain

B(x) = (li(x) − li(x/2))\frac{c_{d}δ}{δ_{1}^{2}δ_{2}φ(δ_{2})}(log x + log log x)

+O (\frac{2^{ω(δ_{2})}}{δ^{2}φ(d)}(log x)^{1−C_{0}/2}) .

Finally, summing over d ≤ (log x)^{A} and δ ≤ (log x)^{B}, the theorem follows.

7 Final remarks

It is interesting to inquire about the solutions to the equation

P̃(n) = P̃(n + 1),  (76)

or equivalently

\frac{n}{γ(n)} ∏_{p|n}(2p − 1) = \frac{n + 1}{γ(n + 1)} ∏_{q|n+1}(2q − 1).  (77)

The first 13 solutions are 45, 225, 1125, 2025, 3645, 140 625, 164 025, 257 174, 703 125, 820 125, 1 265 625, 2 657 205 and 3 515 625.

One can easily check that if for some positive integers a and b, the number p = \frac{3^{a}·5^{b}+1}{2} is a prime number, then n = 3^{a} · 5^{b} is a solution of (76), with P̃(n) = 3^{a+1} · 5^{b}. If one could prove that there exist infinitely many primes of this form, it would follow that equation (76) has infinitely many solutions. Interestingly, a computer search establishes that (76) has 37 solutions n < 10^{10} and that 21 of them are of the form n = 3^{a} · 5^{b}.

Moreover, all 37 solutions n_{0} are such that 3^{3} · 5|P̃(n_{0}). To see that 3|n_{0}, proceed as follows. Suppose that 3 |̸ P̃(n_{0}), then, in light of (77), 3 |̸ (2p − 1) for each prime divisor p of n and 3 |̸ (2q − 1) for each prime divisor q of n + 1. This would imply that p ≡ 1 (mod 3) for all p|n (implying that n ≡ 1 (mod 3)) and q ≡ 1 (mod 3) for all q|n + 1 (implying that n + 1 ≡ 1 (mod 3)), a contradiction.

The fact that 3|P̃(n_{0}) clearly implies that 5|P̃(n_{0}).

8 Acknowledgement

The authors would like to thank the referee for some very helpful suggestions which improved the quality of this paper.

References

[1] P. Cheng-Dong, A new mean value theorem and its applications, in Recent Progress in Analytic Number Theory, Vol. 1, (Durham, 1979), Academic Press, 1981, pp. 275–287.

[2] J. Chidambaraswamy and R. Sitaramachandrarao, Asymptotic results for a class of arithmetical functions, Monatsh. Math. 99 (1985), 19–27.

[3] G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number n, Quart. J. Math. 48 (1920), 76–92.

[4] A. Ivić, The Riemann Zeta Function, John Wiley & Sons, New York, 1985.

[5] H. L. Montgomery and R. C. Vaughan, Multiplicative Number Theory I. Classical Theory, Cambridge University Press, 2007.

[6] S. S. Pillai, On an arithmetic function, J. Annamalai Univ. 2 (1933), 243–248.

[7] A. Selberg, Note on a paper by L. G. Sathe, J. Indian Math. Soc. 18 (1954), 83–87.

[8] E. C. Titchmarsh, A divisor problem, Rend. Palermo 54 (1930), 414–429 and 57 (1933), 478–479.

[9] D. I. Tolev, On the divisor problem in arithmetic progressions, C. R. Acad. Bulgare Sci. 41 (1988), 33–36.

[10] L. Toth, A gcd-sum function over regular integers modulo n, J. Integer Sequences 12 (2009), Article 09.2.5.

2000 Mathematics Subject Classification: Primary 11A25; Secondary 11N37. Keywords: gcd-sum function, Dirichlet divisor problem, shifted primes.

Received August 31 2009; revised version received December 29 2009. Published in Journal of Integer Sequences, December 31 2009.

Return to Journal of Integer Sequences home page.