Chapter 27

Probabilistic Number Theory

We say that an arithmetic function f is additive if

(27.1)  f(mn) = f(m) + f(n)

whenever (m, n) = 1. The values of an additive function are determined by its values on prime-powers, since

(27.2)  f(n) = ∑_{p^{k}∥n} f(p^{k}) .

If the identity (27.1) holds for all pairs m, n, then we say that f is totally additive. If f is additive and f(p^{k}) = f(p) for all p and all k ≥ 1, then we say that f is strongly additive. For example, log n and Ω(n) are totally additive functions, log n/φ(n) and ω(n) are strongly additive, while Ω(n) − ω(n) and log d(n) are additive but neither totally additive nor strongly additive.

In sieve theory we have seen that things do not always work out as one would expect on probabilistic grounds. However, we find that the distribution of the values of an additive function follow the natural probabilistic model very closely. Suppose that f is an additive function. The asymptotic density of integers n for which p^{k}∥n is p^{−k}(1 − 1/p). It is with this ‘probability’ that the term f(p^{k}) is one of the terms in the sum (27.2). Accordingly, for each prime number p we define a random variable X_{p} that has the distribution

(27.3)  \begin{aligned}P (X_{p} = f(p^{k})) & = \frac{1}{p^{k}} (1 − \frac{1}{p})  (k = 1, 2, …) \\ P (X_{p} = 0) & = 1 − \frac{1}{p} . \end{aligned}

If p and q are distinct primes, then by the Chinese remainder theorem we see that the asymptotic density of the integers n for which both p^{k}∥n and q^{ℓ}∥n is p^{−k}(1 − 1/p)q^{−ℓ}(1 − 1/q). Hence the two events p^{k}∥n and q^{ℓ}∥n are asymptotically independent. Thus it is natural to take the random variables X_{p} to be independent, and we set

(27.4)  X = ∑_{p} X_{p} .

This sum either converges almost always or almost nowhere. When it converges almost always, we find that the values of f have a limiting distribution that is the same as the distribution of X. When it converges almost nowhere, f does not have a limiting distribution.

We have already encountered a scattering of results concerning a few additive functions. In §2.3 we estimated the mean of ω(n), and also its variance about its mean. In §2.4 we determined the distribution of the additive function Ω(n) − ω(n) by calculating the mean value of the multiplicative function z^{Ω(n)−ω(n)}. In §7.4 we put

α_{n} = \frac{Ω(n) − log log n}{\sqrt{log log n}},

and found that the distribution of α_{n} is asymptotically normal with mean 0 and variance 1. In this chapter we are more concerned with developing a general theory than with special examples.

27.1 The Turán–Kubilius inequality

Turán (1934) showed (cf Theorem 2.12) that

∑_{n≤}(ω(n) − log log x)^{2} ≪ x log log x,

and Kubilius (1955) generalized this to arbitrary additive functions.

Suppose that f is an additive function. Then

∑_{n≤x} f(n) = ∑_{n≤x} ∑_{p^{k}∥n} f(p^{k})

= ∑_{p^{k}≤x} f(p^{k}) ∑_{\begin{matrix}n≤x \\ p^{k}∥n \end{matrix}} 1

= ∑_{p^{k}≤x} f(p^{k})([\frac{x}{p^{k}} ] − [\frac{x}{p^{k+1}} ])

= x ∑_{p^{k}≤x} \frac{f(p^{k})}{p^{k}}(1 − \frac{1}{p}) + O( ∑_{p^{k}≤x} |f(p^{k})|) . (27.5)

For ease of reference, we set

(27.6)  A(x) = A(f, x) = ∑_{p^{k}≤x} \frac{f(p^{k})}{p^{k}}(1 − \frac{1}{p}) .

We anticipate that the variance of f about its mean should not be much more than

(27.7)  B(x) = B(f, x) = ∑_{p^{k}≤x} \frac{|f(p^{k})|^{2}}{p^{k}} .

By Cauchy’s inequality,

∑_{p^{k}≤x} |f(p^{k})| ≤ B(x)^{1/2}( ∑_{p^{k}≤x} p^{k})^{1/2} ≪ B(x)^{1/2} \frac{x}{\sqrt{log x}} .

Thus from (27.5) we see that

(27.8)  ∑_{n≤x} f(n) = A(x)x + O(B(x)^{1/2}x(log x)^{−1/2}) .

As concerns the potential size of A(x) relative to B(x), we note by Cauchy’s inequality that

|A(x)|^{2} ≤ ( ∑_{p^{k}≤x} \frac{|f(p^{k})|^{2}}{p^{k}} )( ∑_{p^{k}≤x} \frac{1}{p^{k}} )

≪ B(x) log log x . (27.9)

We now show that B(x) is within a constant factor of being an upper bound for the variance of the values of f about its mean.

Theorem 27.1 (The Turán–Kubilius inequality) Suppose that f is an additive function, and let A(x) and B(x) be defined as in (27.6) and (27.7). Then

(27.10)  ∑_{n≤x} (f(n) − A(x))^{2} ≪ xB(x) .

The implicit constant in the above is absolute—independent of both f and x. From (27.9) we see that

∑_{n≤x} |A(x)|^{2} ≪ xB(x) log log x,

and by (27.10) it follows that also

∑_{n≤x} |f(n)|^{2} ≪ xB(x) log log x .

Thus we see that (27.10) is never more than a factor of log log x from being trivial. Despite this lack of quantitative depth, the Turán–Kubilius inequality turns out to be a quite useful result.

Proof We expand the sum on the left hand side, and obtain three terms. The simplest is

(27.11)  \begin{aligned}T_{0} & = ∑_{n≤x} |A(x)|^{2} = |A(x)|^{2}[x] = |A(x)|^{2}x + O(|A(x)|^{2}) \\ & = x|A(x)|^{2} + O(B(x) log log x) \end{aligned}

4 Probabilistic Number Theory by (27.9). The intermediate term is T_{1} = −2ℜ\overline{A(x)} ∑_{n≤x} f(n). Thus by (27.8),

T_{1} = −2|A(x)|^{2}x + O(|A(x)|B(x)^{1/2}x(log x)^{−1/2}),

and by (27.9) this is (27.12) = −2|A(x)|^{2}x + O(B(x)x(log x)^{−1/2}(log log x)^{1/2}) . Finally,

T_{2} = ∑_{n≤x} |f(n)|^{2} = ∑_{n≤x} ∑_{p^{k}∥n} f(p^{k}) ∑_{q^{ℓ}∥n} \overline{f}(q^{ℓ}) = ∑_{p^{k}≤x} ∑_{q^{ℓ}≤x} f(p^{k})\overline{f}(q^{ℓ}) ∑_{\begin{matrix}n≤x \\ p^{k}∥n \\ q^{ℓ}∥n \end{matrix}} 1

where q denotes a prime number. The contribution of those terms for which p = q is

(27.13)  T′_{2} = ∑_{p^{k}≤x} |f(p^{k})|^{2}([\frac{x}{p^{k}} ] − [\frac{x}{p^{k+1}} ]) ≤ xB(x) .

The remaining terms contribute

T′′_{2} = ∑_{\begin{matrix}p^{k}q^{ℓ}≤x \\ p≠q \end{matrix}} f(p^{k})\overline{f}(q^{ℓ})([\frac{x}{p^{k}q^{ℓ}} ] − [\frac{x}{p^{k+1}q^{ℓ}} ] − [\frac{x}{p^{k}q^{ℓ+1}} ] + [\frac{x}{p^{k+1}q^{ℓ+1}} ])

= x ∑_{p^{k}q^{ℓ}≤x} \frac{f(p^{k})}{p^{k}} \frac{\overline{f}(q^{ℓ})}{q^{ℓ}}(1 − \frac{1}{p})(1 − \frac{1}{q}) (27.14)

+ O( ∑_{p^{k}q^{ℓ}≤x} |f(p^{k})\overline{f}(q^{ℓ})|) + O(x ∑_{p^{k+ℓ}≤x} \frac{|f(p^{k})\overline{f}(p^{ℓ})|}{p^{k+ℓ}}) . (27.15)

By Cauchy’s inequality the first error term is

≪ ( ∑_{p^{k}q^{ℓ}≤x} \frac{|f(p^{k})|^{2}|f(q^{ℓ})|^{2}}{p^{k}q^{ℓ}} )^{1/2}( ∑_{p^{k}q^{ℓ}≤x} p^{k}q^{ℓ})^{1/2} .

Here the first sum is ≤ B(x)^{2}, and the second sum is

≤ x ∑_{\begin{matrix}n≤x \\ ω(n)≤2 \end{matrix}} 1 ≪ x^{2}(log x)^{−1} log log x

by (7.54). By Cauchy’s inequality the second error term in (27.15) is

≪ x( ∑_{p^{k+ℓ}≤x} \frac{|f(p^{k})|^{2}}{p^{k+ℓ}} )^{1/2}( ∑_{p^{k+ℓ}≤x} \frac{|f(p^{ℓ})|^{2}}{p^{k+ℓ}} )^{1/2} = x ∑_{p^{k}≤x} \frac{|f(p^{k})|^{2}}{p^{k}} ∑_{\begin{matrix}ℓ \\ p^{ℓ}≤x/p^{k} \end{matrix}} \frac{1}{p^{ℓ}} ≪ xB(x) .

27.1 The Turán–Kubilius inequality 5

The expression (27.14) is

= x|A(x)|^{2} − x ∑_{\begin{matrix}p^{k}≤x \\ q^{ℓ}≤x \\ p^{k}q^{ℓ}>x \end{matrix}} \frac{f(p^{k})}{p^{k}} \frac{\overline{f}(q^{ℓ})}{q^{ℓ}}(1 − \frac{1}{p})(1 − \frac{1}{q}) .

By Cauchy’s inequality the sum on the right is

≤ ( ∑_{\begin{matrix}p^{k}≤x \\ q^{ℓ}≤x \\ p^{k}q^{ℓ}>x \end{matrix}} \frac{|f(p^{k})|^{2}}{p^{k}} \frac{|f(q^{ℓ}|^{2})}{q^{ℓ}})^{1/2}( ∑_{\begin{matrix}p^{k}≤x \\ q^{ℓ}≤x \\ p^{k}q^{ℓ}>x \end{matrix}} \frac{1}{p^{k}q^{ℓ}} )^{1/2} .

Here the first sum is ≤ B(x)^{2}, and the second sum is

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

On assumbling our estimates we deduce that

T′′_{2} = x|A(x)|^{2} + O(x(B(x))) .

The stated result now follows by combining this with (27.11–13). □

27.1 Exercises

1. Show that almost all integers n have (1/2 + o(1)) log log n prime factors ≡ 1 (mod 4).

2. Let k be a fixed positive integer. Show that d_{k}(n) = (log n)^{(1+o(1)) log k} for almost all integers.

3. Show that

∑_{n≤x} Ω(n)Ω(n + k) = x(log log x)^{2} + cx log log x + O(x)

where

c =

4. Show that ∑_{n≤x} (ω(n^{2} + 1) − log log n)^{2} ≪ x log log x.

5. Show that ∑_{p≤x} (ω(p + 1) − log log p)^{2} ≪ x log log x.

6. Suppose that f is an additive function, and let A(x) and B(x) be defined as in (27.6) and (27.7).

(a) Show that if n ≤ x, then

|A(n) − A(x)|^{2} ≤ B(x) ∑_{n<p^{k}≤x} \frac{1}{p^{k}} .

(b) Show that

∑_{n≤x} |A(n) − A(x)|^{2} ≪ B(x)x/ log x .

(c) Conclude that

∑_{n≤x} |f(n) − A(n)|^{2} ≪ xB(x) .

7. (a) Show that

| ∑_{p^{k}≤x} \frac{f(p^{k})}{p^{k+1}} |^{2} ≪ B(x) .

(b) Show that

| ∑_{\begin{matrix}p^{k}≤x \\ k>1 \end{matrix}} \frac{f(p^{k})}{p^{k}} |^{2} ≪ B(x) .

(c) Put A′(x) = ∑_{p≤x} f(p)/p. Show that if f is an additive function, then

∑_{n≤x} |f(n) − A′(x)|^{2} ≪ xB(x) .

8. The Kubilius class ℋ consists of those additive functions f with the two properties

(i) B(f, x) → ∞ as x → ∞;

(ii)  ∑_{x^{1/2}<p^{k}≤x} \frac{|f(p^{k})|^{2}}{p^{k}} = o(B(x))  (x → ∞).

Show that if f ∈ ℋ, then

∑_{n≤x} |f(n) − A(x)|^{2} = (1 + o(1))xB(x)

as x → ∞.

9. Let f(n) = log n.

(a) Show that A(x) = log x + O(1).

(b) Show that B(x) = \frac{1}{2}(log x)^{2} + O(log x).

(c) Deduce that f ∉ ℋ.

(d) Show that ∑_{n≤x} |f(n) − A(x)|^{2} ≪ x.

10. Suppose that f is strongly additive, so that f(n) = ∑_{p|n} f(p) for all n. Consider the bilinear form inequality

(27.16)  ∑_{n≤x} | ∑_{p|n} f(p) − ∑_{p≤x} \frac{f(p)}{p}|^{2} ≤ Δ ∑_{p≤x} \frac{|f(p)|^{2}}{p}

in the variables f(p).

(a) By the change of variables g(p) = f(p)/\sqrt{p}, show that the above is equivalent to the bilinear form inequality

(27.17)  ∑_{n≤x} | ∑_{p|n} g(p)p^{1/2} − ∑_{p≤x} \frac{g(p)}{p^{1/2}} |^{2} ≤ Δ ∑_{p≤x} |g(p)|^{2} .

(b) Use Theorem F.1 to show that the above is equivalent to the bilinear form inequality

(27.18)  ∑_{p≤x} p| ∑_{\begin{matrix}n≤x \\ p|n \end{matrix}} h(n) − \frac{1}{p} ∑_{n≤x} h(n)|^{2} ≤ Δ ∑_{n≤x} |h(n)|^{2}

in the variables h(n).

(c) Apply the large sieve, as discussed in §19.3 to show that

∑_{p≤x^{1/2}} p| ∑_{\begin{matrix}n≤x \\ p|n \end{matrix}} h(n) − \frac{1}{p} ∑_{n≤x} h(n)|^{2} ≪ x ∑_{n≤x} |h(n)|^{2} .

(d) Show that if x^{1/2} < p ≤ x, then

| ∑_{\begin{matrix}n≤x \\ p|n \end{matrix}} h(n)|^{2} ≪ \frac{x}{p} ∑_{\begin{matrix}n≤x \\ p|n \end{matrix}} |h(n)|^{2} .

(e) Show that

∑_{x^{1/2}<p≤x} p| ∑_{\begin{matrix}n≤x \\ p|n \end{matrix}} h(n)|^{2} ≪ x ∑_{n≤x} |h(n)|^{2} .

(f) Show that

∑_{x^{1/2}<p≤x} \frac{1}{p}| ∑_{n≤x} h(n)|^{2} ≪ x ∑_{n≤x} |h(n)|^{2} .

(g) Deduce that (27.18) and hence also (27.16) holds with Δ ≪ x.

27.2 Mean values of multiplicative functions

Let f be a multiplicative function, which is to say that f(mn) = f(m)f(n) whenever (m, n) = 1. Hence f(n) = ∏_{p^{k}∥n} f(p^{k}). We let ℳ_{0} denote the class of those multiplicative functions f for which |f(n)| ≤ 1 for all n. Our object is to characterize those members of ℳ_{0} that have an asymptotic mean value. If f is a real-valued additive function, then e(tf(n)) ∈ ℳ_{0}, so an ability to compute mean values of multiplicative functions will help us to determine the Fourier transform of the distribution of additive functions. We begin with several simple results concerning (not necessarily multiplicative) arithmetic functions.

Theorem 27.2 If f(n) = ∑_{d|n} g(d), if the series ∑_{d=1}^{∞} g(d)/d converges, say to a, and if ∑_{d≤x} |g(d)| = o(x) as x → ∞, then

(27.19)  S(x) = ∑_{n≤x} f(n) = ax + o(x) .

Proof Clearly

S(x) = ∑_{n≤x} ∑_{d|n} g(d) = ∑_{d≤x} g(d)[x/d] = x ∑_{d≤x} g(d)/d + O( ∑_{d≤x} |g(d)|).

Thus we have the stated result. □

Corollary 27.3 (Wintner) If f(n) = ∑_{d|n} g(d) and ∑_{d=1}^{∞} |g(d)|/d < ∞, then (27.19) holds with a = ∑_{d=1}^{∞} g(d)/d.

Proof From the hypothesis that ∑_{d=1}^{∞} |g(d)|/d < ∞, it follows by partial summation that ∑_{d≤x} |g(d)| = o(x). □

Corollary 27.4 If f is multiplicative, if

(27.20)  ∑_{p} \frac{|1 − f(p)|}{p} < ∞,

and if

∑_{\begin{matrix}p^{k} \\ k>1 \end{matrix}} \frac{|f(p^{k})|}{p^{k}} < ∞,

then (27.19) holds with

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

Proof Let g be the multiplicative function for which g(p^{k}) = f(p^{k}) − f(p^{k−1}) for k > 0. Then f(n) = ∑_{d|n} g(d), and

∑_{d=1}^{∞} \frac{|g(d)|}{d} = ∏_{p} (1 + \frac{|f(p) − 1|}{p} + \frac{|f(p^{2}) − f(p)|}{p^{2}} + ⋯) < ∞,

27.2 Mean values of multiplicative functions 9

and thus

∑_{d=1}^{∞} \frac{g(d)}{d} = ∏_{p} (1 + \frac{f(p) − 1}{p} + \frac{f(p^{2}) − f(p)}{p^{2}} + ⋯) = a

where a is defined by (27.21). □

In the same vein we have Theorem 27.5 If f(n) = ∑_{d|n} g(d)h(n/d), if ∑_{m=1}^{∞} |h(m)|/m < ∞, and if ∑_{d≤x} g(d) = bx + o(x), then we have (27.19) with a = b ∑_{m=1}^{∞} h(m)/m.

Here we see that a mean value for g yields one for f, provided that f is near g in the sense that ∑ |h(m)|/m < ∞. If h(1) = 1 and h(m) = 0 for all m > 1, then f = g. Proof Put

r(x) = ∑_{d≤x} g(d) − bx .

Then

S(x) = ∑_{n≤x} ∑_{d|n} g(d)h(n/d) = ∑_{m≤x} h(m) ∑_{d≤x/m} g(d) = bx ∑_{m≤x} h(m)/m + ∑_{m≤x} h(m)r(x/m) .

There is a constant C (depending on g) such that |r(x)| ≤ Cx for all x ≥ 1, and for every ε > 0 there is a δ such that |r(x)| ≤ εx for all x ≥ 1/δ. Thus the second sum above has absolute value not exceeding

εx ∑_{m≤δx} |h(m)|/m + Cx ∑_{δx<m≤x} |h(m)|/m .

Here the first term is ≪ εx, and the second sum is small since it is part of the tail of a convergent series. Thus we have the stated result. □

In Theorem 27.2 we found a connection between the mean value of f and the convergence of the series ∑ g(d)/d, but we find it more productive to pursue the line suggested by Corollary 27.4, which we now sharpen. We begin with two lemmas. Lemma 27.6 If f ∈ ℳ_{0} and S(x) is defined as in (27.19), then

S(x) log x = ∑_{p≤x} f(p)S(x/p) log p + O(x) .

Proof We first observe that

(27.22)  (log x) ∑_{n≤x} f(n) − ∑_{n≤x} f(n) log n = ∑_{n≤x} f(n) log x/n ≪ ∑_{n≤x} log x/n ≪ x .

Furthermore,

∑_{n≤x} f(n) log n = ∑_{n≤x} f(n) ∑_{d|n} Λ(d)

= ∑_{d≤x} Λ(d) ∑_{m≤x/d} f(md)

= ∑_{p≤x}(log p) ∑_{m≤x/p} f(mp) + O(x ∑_{\begin{matrix}p^{k}≤x \\ k>1 \end{matrix}} \frac{log p}{p^{k}})

= ∑_{p≤x} f(p)S(x/p) log p + O( ∑_{p≤x}(log p) ∑_{m≤x/p} |f(mp) − f(m)f(p)|) + O(x) .

Since f(mp) = f(m)f(p) unless p|m, we see that the sum over m ≤ x/p is ≪ x/p^{2}, and so the first error term above is ≪ x. On combining this with (27.22), we obtain the stated result. □

Lemma 27.7 If f ∈ ℳ_{0}, S(x) is defined as in (27.19), and if

(27.23)  ∑_{p} \frac{ℜ(1 − f)}{p} < ∞,

then

S(x) log x = x ∑_{n≤x} \frac{f(n)}{n} + o(x log x) .

Proof We write

(27.24) ∑_{p≤x} f(p)S(x/p) log p = ∑_{p≤x} S(x/p) log p + ∑_{p≤x}(f(p) − 1)S(x/p) log p = T_{1} + T_{2},

say. Here

T_{1} = ∑_{n≤x} f(n)ϑ(x/n) .

By the Prime Number Theorem in the form ϑ(x) = x + O(x/(log x)^{2}), this is

= x ∑_{n≤x} \frac{f(n)}{n} + O( ∑_{n≤x} \frac{x}{n}(log x/n)^{−2}) .

The error term here is O(x).

We observe that |1 − f(p)|^{2} = 1 − 2ℜf(p) + |f(p)|^{2} ≤ 2ℜ(1 − f(p)). Thus by Cauchy’s inequality,

T_{2} ≪ x ∑_{p≤x} |1 − f(p)|\frac{log p}{p} ≪ x( ∑_{p≤x} \frac{log p}{p})^{1/2}( ∑_{p≤x} \frac{ℜ(1 − f(p)) log p}{p})^{1/2} .

Here the first sum on the right hand side is ≪ log x, and the second one is o(log x), in view of the hypothesis (27.23). On combining our estimates we obtain the stated result. □

It is interesting to observe that the identity on the left hand side of (27.22) is equivalent to integrating by parts in Perron’s formula, as

\frac{log x}{2πi} ∫_{c−i∞}^{c+i∞} \frac{F (s)x^{s}}{s} ds = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞} \frac{F (s)x^{s}}{s^{2}} ds − \frac{1}{2πi} ∫_{c−i∞}^{c+i∞} \frac{F′(s)x^{s}}{s} ds .

This is expected to produce a gain, since we expect that F (s)/s is not generally very rapidly changing, while x^{s} is spinning fairly rapidly. Indeed, suppose we tried to do something as simple as using Perron’s formula to show that [x] ≪ x. Since

∫_{−1}^{1} |ζ(1 + α + it)|x^{1+α} dt ≍ x^{1+α} log \frac{1}{α},

we are unable to obtain a bound better than x log log x. On the other hand, if we were to use Perron’s formula to show that ∑_{n≤x} log n ≪ x log x, we fare better, since

∫_{−1}^{1} |ζ′(1 + α + it)|x^{1+α} dt ≍ \frac{x^{1+α}}{α} ,

and we can take α = 1/ log x. In both of these approaches, we would still have the problem that the kernel in Perron’s formula decays only like an inverse first power, but his difficulty could be overcome by smoothing.

Theorem 27.8 (Delange) Suppose that f ∈ ℳ_{0}, and that the series

(27.25)  ∑_{p} \frac{1 − f(p)}{p}

converges. Then (27.19) holds with a given by (27.21).

Since ℜf(p) ≤ |f(p)| ≤ 1, we see that the convergence of the series (27.22) implies that the sum of the real parts is absolutely convergent, just as it was in Corollary 27.4. Thus Theorem 27.8 is stronger by virtue of the fact that we are no longer assuming that the sum of the imaginary parts is absolutely convergent. Given the convergence of the product (27.21), we see that a ≠ 0 unless one of the individual factors vanishes. This happens only in the single case that

(27.26)  f(2^{k}) = −1  (k = 1, 2, 3, …) .

Proof By Abel’s theorem for Dirichlet series (Theorem 1.1), the convergence of the series (27.25) implies that

lim_{σ→1^{+}} ∑_{p} \frac{1 − f(p)}{p^{σ}}

exists. As in the proof of Corollary 27.4, let g be the multiplicative function for which g(p^{k}) = f(p^{k}) − f(p^{k−1}) for k = 1, 2, …, and consider the identity

G(s) = ∏_{p} (1 + \frac{g(p)}{p^{s}} + \frac{g(p^{2})}{p^{2s}} + ⋯)

= exp ( ∑_{p} \frac{g(p)}{p^{s}}) ∏_{p} (1 − \frac{g(p)}{1!p^{s}} + \frac{g(p)^{2}}{2!p^{2s}} − ⋯)(1 + \frac{g(p)}{p^{s}} + \frac{g(p^{2})}{p^{2s}} + ⋯) .

In the second factor above we have the product of two power series in p^{−s}, in which the coefficient of p^{−s} is 0 and for k > 1 the coefficient of p^{−ks} is

∑_{j=0}^{k} \frac{(−g(p))^{j}g(p^{k−j})}{j!} .

If |g(p^{j})| ≤ C for all j, then the above has absolute value not exceeding Ce^{C}. Thus the product is absolutely convergent for σ > 1/2, and uniformly so for σ ≥ 1/2 + δ. Hence the product is a continuous function, and we deduce that

lim_{σ→1^{+}} G(σ) = G(1) = a

where a is defined as in (27.21). For σ > 1, let

(27.27)  F (s) = ∑_{n=1}^{∞} \frac{f(n)}{n^{s}} .

Thus F (s) = ζ(s)G(s) since f(n) = ∑_{d|n} g(d), and hence

F (σ) = \frac{a + o(1)}{σ − 1} (σ → 1^{+}) .

By the Hardy–Littlewood tauberian theorem (Theorem 5.11 with β = 1) it follows that

∑_{n≤x} \frac{f(n)}{n} = (a + o(1)) log x .

The stated result now follows from Lemma 27.7. □

In Theorem 27.8, the mean value is non-zero unless (27.26) holds. In §27.5 we characterize those f ∈ ℳ_{0} with vanishing mean value in terms of the behaviour of the generating Dirichlet series F (s) defined in (27.27).

To prepare for the proof of our next result we establish a variant of the Hardy–Littlewood tauberian theorem.

Lemma 27.9 Suppose that the numbers c(p) are bounded, and that

lim_{σ→1^{+}} ∑_{p} \frac{c(p)}{p^{σ}}

exists and has the (finite) value c. Then ∑_{p} c(p)/p converges, and has the value c.

Proof Put

a(u) = ∑_{e^{u−1}<p≤e^{u}} \frac{c(p)}{p} .

Then a(u) ≪ 1/u for u ≥ 1, and

I(u) = ∫_{0}^{∞} a(u)e^{−δu} du = \frac{1 − e^{−δ}}{δ} ∑_{p} \frac{c(p)}{p^{1+δ}}

tends to c as δ → 0^{+}. Thus by the Hardy–Littlewood tauberian theorem (Theorem 5.7 with β = 0) it follows that ∫_{0}^{U} a(u) du tends to c as U → ∞. But

∫_{0}^{U} a(u) du = ∑_{p≤e^{U}} \frac{c(p)}{p} − ∑_{e^{U−1}<p≤e^{U}} \frac{c(p)}{p}(U − log p),

and the second sum is ≪ 1/U, so ∑_{p} c(p)/p converges to c □

For members of ℳ_{0} with non-zero mean value, we have the following comprehensive result.

Theorem 27.10 (Delange) Suppose that f ∈ ℳ_{0}, and let S(x), the number a, and the function F (s) be defined as in (27.19), (27.21) and (27.27) respectively. Then the following assertions are equivalent:

(a) S(x) ∼ ax and a ≠ 0;

(b) ∑_{n≤x} \frac{f(n)}{n} ∼ a log x and a ≠ 0;

(c) F (σ) ∼ \frac{a}{σ − 1} as σ → 1^{+} and a ≠ 0;

(d) lim_{σ→1^{+}} ∑_{p} \frac{1 − f(p)}{p^{σ}} exists and (27.26) fails;

(e) ∑_{p} \frac{1 − f(p)}{p} converges and (27.26) fails.

Proof We deduce (b) from (a) by partial summation, and similarly deduce (c) from (b). But (c) asserts that lim_{σ→1^{+}} F (σ)/ζ(σ) = a, which is to say that

lim_{σ→1^{+}} ∏_{p} (1 − \frac{1}{p^{σ}} )(1 + \frac{f(p)}{p^{σ}} + \frac{f(p^{2})}{p^{2σ}} + ⋯) = a ≠ 0.

Each factor of the product has modulus not exceeding 1, so if (27.26) were to hold, then the limit would be 0. Thus (27.26) fails and the product is comparable to

exp ( ∑_{p} \frac{1 − f(p)}{p^{σ}}) .

Hence we have (d). That (d) implies (e) is immediate from Lemma 27.9, and that (e) implies (a) follows from Theorem 27.8 □

27.2.1 Exercises

1. Suppose that ∑_{d=1}^{∞} g(d)/d converges, say to a.

(a) Show that ∑_{d≤x} g(d) = o(x).

(b) Suppose also that ∑_{d≤x} |g(d)| ≪ x. Use Axer’s Theorem (Theorem 8.1) to show that ∑_{d≤x} g(d{x/d} = o(x).

(c) Put f(n) = ∑_{d|n} g(d). Under the above hypotheses, show that ∑_{n≤x} f(n) = ax+o(x). (Note that this improves upon Theorem 27.2.)

27.3 The distribution of additive functions

We now employ our understanding of the mean values of multiplicative functions to establish

Theorem 27.11 (Erdős–Wintner) Let f be a real-valued additive function. The following are equivalent:

(a) Each of the following series is convergent:

(27.28)  ∑_{\begin{matrix}p \\ |f(p)|≤1 \end{matrix}} \frac{f(p)}{p},  ∑_{\begin{matrix}p \\ |f(p)|≤1 \end{matrix}} \frac{|f(p)|^{2}}{p} ,  ∑_{\begin{matrix}p \\ |f(p)|>1 \end{matrix}} \frac{1}{p} .

(b)There is an increasing function F (u) such that lim_{u→−∞} F (u) = 0, lim_{n→+∞} = 1, and such that

(27.29)  lim_{N→∞} \frac{1}{N} card\{n ≤ N : f(n) ≤ u\} = F (u),

whenever u is not a point of discontinuity of F.

Since F is increasing, the set of its discontinuities is is at most countable. Later we shall see that if we define F to be right-continuous, so that F (u) = F (u^{+}), then (27.29) holds for all values of u. When (b) holds we may say that F is the asymptotic distribution of f. Given F with the above properties, there is a unique probability measure μ such that F (u) = ∫_{−∞}^{u} 1 dμ. Moreover, we can construct a probability measure μ_{N} that attaches weight 1/N to each of the points f(n) for 1 ≤ n ≤ N. Then (27.29) asserts that

lim_{N→∞} ∫_{−∞}^{u} 1 dμ = ∫_{−∞}^{u} 1 dμ,

which is to say that the measures μ_{N} tend weakly to μ. Our proof of Theorem 27.11 depends on our discussion in §16.5 of the weak convergence of measures.

Proof Suppose that (a) holds. By virtue of Theorem 16.18, in order to show that (b) holds it suffices to show that

(27.30)  μ̂_{N}(t) = ∫_{ℝ} e(−tu) dμ_{N}(u) = \frac{1}{N} ∑_{n=1}^{N} e(−tf(n))

has a limit r(t) as N → ∞, and that r is continuous at t = 0. Let g(n) = g_{t}(n) = e(−tf(n)). Then g ∈ ℳ_{0}, so by Theorem 27.8 the above tends to

(27.31)  r(t) = ∏_{p} (1 − \frac{1}{p})(1 + \frac{e(−tf(p))}{p} + \frac{e(−tf(p^{2}))}{p^{2}} + ⋯)

provided that the sum

(27.32)  ∑_{p} \frac{1 − e(−tf(p))}{p}

converges. The above is

(27.33) = 2πit ∑_{|f(p)|≤1} \frac{f(p)}{p} + ∑_{|f(p)|≤1} \frac{1 − 2πitf(p) − e(−tf(p))}{p} + ∑_{|f(p)|>1} \frac{1 − e(−tf(p))}{p} .

By the hypotheses (a) we see that the first sum is a constant, and that the third sum is absolutely and uniformly convergent. Since e(θ) = 1 + 2πiθ + O(θ^{2}), the second sum is absolutely convergent, and uniformly so for t in a bounded set. Thus the sum (27.32) converges. Moreover, the expression (27.33) tends to 0 as t → 0, so r(t) tends to 1, and hence we have (b).

We now show that (b) implies (a). If the μ_{N} tend weakly to μ, then by Theorem 16.17 it follows that μ̂_{N}(t) → μ̂(t). Since μ̂(t) is continuous and μ̂(0) = 1, it follows from (27.30) that the multiplicative function g_{t} has a non-zero mean value for all t near 0, and that this mean value tends to 1 as t → 0. Hence by Theorem 27.10 we deduce that the sum (27.32) converges for all small t, and tends to 0 as t → 0. Let s(t) denote the real part of the series (27.32). Since each term has non-negative real part, the sum of the real parts is absolutely convergent, and uniformly bounded for |t| ≤ δ. But then

\frac{1}{2δ} ∫_{−δ}^{δ} s(t) dt = ∑_{p} \frac{1}{p}(1 − \frac{sin 2πδf(p)}{2πδf(p)}),

and hence this latter sum is finite. But

1 − \frac{sin θ}{θ} ≫ min(1, θ^{2}),

so the second and third sums in (27.29) are convergent. Hence the second and third sums in (27.33) and convergent, and since the sum (27.32) is convergent, it follows that the first sum in (27.33) is convergent. □

In the next section we shall find that much can be said about the distribution function F of a real-valued additive function f. At this point we content ourselves with the following simple result.

Theorem 27.12 Let f be a real-valued additive function with limiting distribution function F. If the series

(27.34)  ∑_{f(p)≠0} \frac{1}{p}

converges, then each value assumed by f is attained on a set of positive density, so that F has jump discontinuities but is otherwise constant (i.e., the associated measure μ is discrete). If the series diverges, then the distribution function F is continuous, and hence any value of f is assumed only on a set of density 0.

Proof Let 𝒫 denote the set of primes p for which f(p) ≠ 0, let 𝒩_{1} denote the set of positive integers composed entirely of primes p ∈ 𝒫, let 𝒩_{2} denote the set of integers composed entirely of primes p ∉ 𝒫 with each prime occurring with multiplicity > 1, and finally let 𝒩_{3} denote the set of squarefree integers composed entirely of primes p ∉ 𝒫. Each n can be written uniquely in the form n = n_{1}n_{2}n_{3} with n_{i} ∈ 𝒩_{i} and (n_{2}, n_{3}) = 1, and f(n) depends only on n_{1} and n_{2}. The number of n ≤ x with prescribed n_{1} and n_{2} is the number of squarefree n_{3} ≤ x/(n_{1}n_{2}) such that n_{3} ∈ 𝒩_{3} and (n_{2}, n_{3}) = 1. By Corollary 27.4, this is

∼ \frac{x}{n_{1}n_{2}} ∏_{p∈𝒫}(1− \frac{1}{p})∏_{p|n_{2}}(1− \frac{1}{p})∏_{\begin{matrix}p∉𝒫 \\ p∤n_{2} \end{matrix}}(1− \frac{1}{p^{2}} ) = \frac{x}{n_{1}n_{2}} ∏_{p∈𝒫}(1− \frac{1}{p})∏_{p|n_{2}}(1+ \frac{1}{p})^{−1} ∏_{p∉𝒫}(1− \frac{1}{p^{2}} ).

Moreover, these densities sum to 1 as n_{1} and n_{2} range over 𝒩_{1} and 𝒩_{2}.

Now suppose that the series (27.34) diverges. By Theorem 16.19 it suffices to show that

(27.35)  ∫_{−T}^{T} |μ̂(t)|^{2} dt = o(T)

as T → ∞. In the case at hand we know that

(27.36)  μ̂(t) = ∏_{p} (1 − \frac{1}{p})(1 + \frac{e(−tf(p))}{p} + \frac{e(−tf(p^{2}))}{p^{2}} + ⋯) .

Let 𝒫 be a finite set of primes for which f(p) ≠ 0, and put s = ∑_{p∈𝒫} 1/p. In the above product, each prime contributes a factor whose absolute value is ≤ 1. Thus

|μ̂(t)| ≤ ∏_{p∈𝒫} |(1 − \frac{1}{p})(1 + \frac{e(−tf(p))}{p} + ⋯)|

≪ ∏_{p∈𝒫} |1 − \frac{1}{p} + \frac{e(−tf(p))}{p}| ≪ exp ( − 2 ∑_{p∈𝒫} \frac{sin^{2} πtf(p)}{p}) .

Hence by Hölder’s inequality

\frac{1}{2T} ∫_{−T}^{T} |μ̂(t)|^{2} dt ≪ \frac{1}{2T} ∫_{−T}^{T} exp ( − 4 ∑_{p∈𝒫} \frac{sin^{2} πtf(p)}{p}) dt

≤ ∏_{p∈𝒫} (\frac{1}{2T} ∫_{−T}^{T} exp(−4s sin^{2} πtf(p)) dt)^{1/(sp)}.

Suppose that f(p) ≠ 0. The integrand has period 1/|f(p)|, and

f(p) ∫_{0}^{1/f(p)} exp(−4s sin^{2} πtf(p)) dt = ∫_{0}^{1} exp(−4s sin^{2} πt) dt

≤ ∫_{−1/2}^{1/2} exp(−16st^{2}) dt ≤ ∫_{−∞}^{∞} exp(−16st^{2}) dt = \frac{\sqrt{π}}{4\sqrt{s}} .

Hence

\frac{1}{2T} ∫_{−T}^{T} exp(−4s sin^{2} πtf(p)) dt ≤ \frac{1}{\sqrt{s}}

for all sufficiently large T, and so

lim sup_{T →∞} \frac{1}{2T} ∫_{−T}^{T} |μ̂(t)|^{2} dt ≤ \frac{1}{\sqrt{s}} .

By choosing 𝒫 suitably, we may make s as large as we please. Thus we have (27.35), and the proof is complete. □

27.3.1 Exercises

1. (a) Show that log σ(n)/n has a limiting distribution.

(b) Show that this limiting distribution is continuous.

(c) Deduce that the set of perfect numbers (i.e., those for which σ(n) = 2n is a set of density 0.

2. Show that an integer-valued additive function f has a limiting distribution if and only if

∑_{f(p)≠0} \frac{1}{p} < ∞ .

3. Let f be a multiplicative function that takes only positive real values. Show that f has a limiting distribution if and only if each of the following four series converges:

∑_{1/2≤|f(p)|≤2} \frac{1 − f(p)}{p},  ∑_{1/2≤|f(p)|≤2} \frac{|1 − f(p)|^{2}}{p} ,  ∑_{|f(p)|>2} \frac{1}{p},  ∑_{|f(p)|<1/2} \frac{1}{p} .

4. Let f_{1}, …, f_{k} be real-valued additive functions, and put f(n) = (f_{1}(n), …, f_{k}(n)). Give necessary and sufficient conditions that f should have a limiting distribution in ℝ^{k}. Deduce a variant of Theorem 27.11 for complex-valued additive functions.

5. Let f be a real-valued additive function with limiting distribution F, and let μ denote the associated limiting measure. Show that either μ̂(t) is never 0, or that its zeros form an arithmetic progression of the form c(2k + 1) for k ∈ ℤ.

27.4 Applications of probability theory

Let f be a real-valued additive function, and for each prime p let X_{p} denote the random variable defined in (27.3). We take the X_{p} to be independent, and ask whether the random variable X defined in (27.4) exists. In this connection we quote without proof

Kolmogorov’s Three Series Theorem Let Y_{n} be independent random variables. If each of the three series

∑_{n} ∫_{|Y_{n}|≤1} Y_{n},  ∑_{n} ∫_{|Y_{n}|≤1} ∫ |Y_{n}|^{2},  ∑_{n} ∫_{|Y_{n}|>1} 1

converges, then the sum Y = ∑_{n} Y_{n} converges almost everywhere. If any one of these series diverges, then the sum ∑_{n} Y_{n} diverges almost everywhere.

For our sum (27.4), the conditions of Kolmogorov’s theorem are precisely the conditions of Theorem 27.11(a). Hence the random variable X exists precisely when f has a limiting distribution F. In the context of Kolmogorov’s Three Series Theorem, when Y exists its Fourier transform is

Ŷ(t) = ∫ e(−tY) = ∫ ∏_{n} e(−tY_{n}) = ∏_{n} ∫ e(−tY_{n}) = ∏_{n} Ŷ_{n}(t)

by the independence of the Y_{n}. In the case of the variable X, we find that

X̂_{p}(t) = ∫ e(−tX_{p}) = 1 − \frac{1}{p} + e(−tf(p))\frac{1}{p}(1 − \frac{1}{p}) + e(−tf(p^{2}))\frac{1}{p^{2}} (1 − \frac{1}{p}) + ⋯

= (1 − \frac{1}{p})(1 + \frac{e(−tf(p))}{p} + \frac{e(−tf(p^{2}))}{p^{2}} + ⋯),

and hence

X̂(t) = ∏_{p} (1 − \frac{1}{p})(1 + \frac{e(−tf(p))}{p} + \frac{e(−tf(p^{2}))}{p^{2}} + ⋯) .

But this is the same as μ̂(t) given in (27.36), so by the uniqueness of the Fourier transform (Corollary 16.16) it follows that F is the distribution function of X. A great deal is known concerning the distribution function of a sum of random variables, so by appealing to this theory we obtain further information concerning F. In particular, we note the

Law of Pure Types (Jessen–Wintner) Let Y_{n} be independent random variables such that Y = ∑_{n} Y_{n} converges almost everywhere, and suppose that there is a countable set 𝒞 such that P (Y_{n} ∈ 𝒞) = 1 for all n. Then the distribution of Y is of pure type: Either it is discrete, singular, or absolutely continuous.

Hence we see that the distribution function F of a real-valued additive function is of pure type. In Theorem 27.12 we characterized the situation in which the distribution is discrete; this can also be obtained by applying a general theorem of Lévy concerning sums of independent random variables. We have no similar criterion to distinguish between singular and absolutely continuous distributions, although all three types do occur. In particular, the distribution of log φ(n)n is singular, as we now show.

Theorem 27.13 Let μ denote the probability measure such that

lim_{N→∞} \frac{1}{N} card\{n ≤ N : φ(n)/n ≤ c\} = μ((−∞, c]) .

Let α be fixed, 1 < α < e − 1, put I_{k} = [φ(k)/k − 1/k^{α}, φ(k)/k], and set

𝒮 = {x ∈ [0, 1] : x ∈ I_{k} for infinitely many k}.

Then m(𝒮) = 0, and μ(𝒮) = 1.

Here m(𝒮) denotes the Lebesgue measure of 𝒮.

Proof The first assertion is clear, since

𝒮 ⊆ ⋃_{k>K} I_{k}

for any K, so that

m(𝒮) ≤ ∑_{k>K} k^{−α} .

As for the second assertion, we show that for any ε > 0 and any K there is an L such that

(27.37)  μ( ⋃_{K<k≤L} I_{k}) ≥ 1 − ε .

The advantage of this finite form of the assertion is that we can estimate the left hand side by considering densities of set of integers: If 𝒩 = {n : φ(n)/n ∈ ⋃_{K<k≤L} I_{k}}, then d(𝒩) = μ( ⋃_{K<k≤L} I_{k}). In establishing (27.37), we may assume that K is large, for if the above holds for one value of K, then it also holds for all smaller values of K. For a given number n, write n = ∏_{i=1}^{Ω(n)} p_{i} with p_{1} ≤ p_{2} ≤ ⋯ ≤ p_{Ω(n)}, and set d_{r} = ∏_{i≤r} p_{i}. We shall show that if L is sufficiently large, then most integers n have a divisor d_{r}, K < d_{r} ≤ L, such that

\frac{φ(n/d_{r})}{n/d_{r}} ≥ 1 − d_{r}^{−α}.

In this case φ(n)/n ∈ I_{d_{r}}, since

\frac{φ(d_{r})}{d_{r}} ≥ \frac{φ(n)}{n} ≥ \frac{φ(d_{r})}{d_{r}} \frac{φ(n/d_{r})}{n/d_{r}} ≥ \frac{φ(d_{r})}{d_{r}}(1 − d_{r}^{−α}) ≥ \frac{φ(d_{r})}{d_{r}} − d_{r}^{−α} .

Let 𝒩_{0} denote the complementary set of numbers, i.e., the n for which φ(n/d_{r})/(n/d_{r}) < 1 − d_{r}^{−α} for all d_{r} ∈ (K, L]. To estimate the size of 𝒩_{0} we consider various possibilities. Let 𝒩_{1} be the set of n such that the interval (K, log L] contains none of the special divisors d_{r}. Let β = α/2 + (e − 1)/2, so that 1 < α < β < e − 1, and let 𝒩_{2} be the set of numbers nsuch that p_{r+1} < d_{r}^{β} whenever d_{r} ∈ (K, L]. Finally, let 𝒩_{3} be the set of those n such that there is a d_{r} ∈ (K, L] for which p_{r+1} > d_{r}^{β} and φ(n/d_{r})/(n/d_{r}) < 1 − d_{r}^{−α}. The sets 𝒩_{i} possess asymptotic densities, but for our present purpose it suffices to bound their upper asymptotic densities where the upper asymptotic density of a set 𝒜 is

\overline{d}(𝒜) = lim sup_{x→∞} \frac{1}{x} card\{n ≤ x : n ∈ 𝒜\} .

The main estimates to be established are that

(27.39)  \overline{d}(𝒩_{1}) ≪ \frac{log K}{log log L},
(27.40)  \overline{d}(𝒩_{1}^{c}𝒩_{2}) ≪ \frac{1}{log log L},
(27.41)  \overline{d}(𝒩_{3}) ≪ K^{α−e+1} .

Once these estimates are in place, we argue that 𝒩_{2} = 𝒩_{1}𝒩_{2} ∪ 𝒩_{1}𝒩_{2}^{c} ⊆ 𝒩_{1} ∪ 𝒩_{1}^{c}𝒩_{2}. Since \overline{d}(𝒜 ∪ ℬ) ≤ \overline{d}(𝒜) + \overline{d}(ℬ), it follows from (27.39) and (27.40) that

(27.42)  \overline{d}(𝒩_{2}) ≪ \frac{log K}{log log L} .

We also observe that 𝒩_{0}𝒩_{2}^{c} ⊆ 𝒩_{3}. Thus 𝒩_{0} = 𝒩_{0}𝒩_{2} ∪ 𝒩_{0}𝒩_{2}^{c} ⊆ 𝒩_{2} ∪ 𝒩_{3}, so from (27.40) and (27.42) we deduce that

\overline{d}(𝒩_{0}) ≤ \overline{d}(𝒩_{2}) + \overline{(}𝒩_{3}) ≪ K^{α−e+1} + \frac{log K}{log log L} .

Thus \overline{d}(𝒩_{0}) < ε if K is sufficiently large and if L is sufficiently large compared with K.

To prove (27.39), we suppose, as we may, that L > exp(K^{2}). For n ∈ 𝒩_{1}, choose r so that d_{r} < K and d_{r+1} > log L. Thus n = d_{r}m with m composed entirely of primes > (log L)/d_{r}. This decomposition is unique, since d_{r} is composed entirely of primes < K, and m is composed entirely of primes > (log L)/d_{r} > K^{2}/d_{r} ≥ K. Hence

card{n ≤ x : n ∈ 𝒩_{1}} = ∑_{d<K} card{m ≤ x/d : p|m ⟹ p > (log L)/d} .

By the theorem of Eratosthenes–Legendre (Theorem 3.1), this is

∼ x ∑_{d<K} \frac{1}{d} ∏_{p<(log L)/d} (1 − \frac{1}{p}) ≤ x( ∑_{d<K} \frac{1}{d}) ∏_{p<(log L)/K} (1 − \frac{1}{p}) ≪ x\frac{log K}{log((log L)/K)},

so we have (27.39).

As for (27.40), suppose that n ∈ 𝒩_{1}^{c}𝒩_{2} and that d_{r} ∈ (K, L]. Then d_{r+1} = d_{r}p_{r+1} ≤ d_{r}^{1+b}. Thus by induction, if r_{0} is the least r for which d_{r} > K, then

d_{r} ≤ d_{r_{0}}^{(1+b)^{r−r_{0}}} < (log L)^{(1+b)^{r−r_{0}}}

provided that this bound is ≤ L. Set

R = [\frac{log log L − log log log L}{log(1 + b)}] .

Then d_{r} ≤ L for r ≤ r_{0} + R. Let

Ω_{L}(n) = ∑_{\begin{matrix}p^{k}∥n \\ p≤L \end{matrix}} 1 .

Thus Ω_{L}(n) ≥ R if n ∈ 𝒩_{2}. By the Turán–Kubilius inequality (Theorem 27.1),

∑_{n≤x}(Ω_{L}(n) − log log L)^{2} ≪ x log log L .

Let c = 1/ log(1+β). Here c > 1, since 1+β < e, and R > (c−ε) log log L if L is sufficiently large. Thus Ω_{L}(n) − log log L ≫ log log L when n ∈ 𝒩_{2}, and so we have (27.39).

If n ∈ 𝒩_{3}, then we may write n = dm where K < d ≤ L, p|m implies p > d^{β}, and φ(m)/m < 1 − d^{−α}. This decomposition may not be unique, but (27.43)

card{n ≤ x : n ∈𝒩_{3}}

≤ ∑_{K<d≤L} card{m ≤ x/d : p|m ⟹ p > d^{β}, φ(m)/m < 1 − d^{−α}} .

Let

f_{y}(m) = ∑_{\begin{matrix}p|n \\ p>y \end{matrix}} log(1 − 1/p)^{−1} .

This is an additive function with

A(f_{y}, z) ≤ (1 + o(1))(y log y)^{−1}, B(f_{y}, z) ≪ y^{−2}(log y)^{−1} .

Thus if V ≥ 2/(y log y), then by the Turán–Kubilius inequality we see that

card\{m ≤ z : f_{y}(n) > V \} ≪ \frac{z}{V^{2}y^{2} log y} .

On taking z = x/d, y = d^{β}, V = log(1 − d^{−α})^{−1} ≍ d^{α}, we see that the m ≤ x/d for which f_{y}(m) > V includes the m in (27.43), and hence

card{n ≤ x : n ∈ 𝒩_{3}} ≪ x ∑_{K<d≤L} d^{−1+2α−2β}(log d)^{−1} ≪ xK^{2α−2β}(log K)^{−1}.

This gives (27.41), in view of the definition of β. Thus the proof is complete. □

27.4.1 Exercises

27.5 Multiplicative functions with vanishing mean value

Suppose that

(27.44)  S(x) = ∑_{n≤x} f(n) .

If S(x) ≪ x, then by Theorem 1.3 the Dirichlet series

(27.45)  F (s) = ∑_{n=1}^{∞} f(n)n^{−s}

converges for σ > 1, and

F (s) = s ∫_{1}^{∞} S(x)x^{−s−1} dx

for σ > 1. From this formula it is immediate that if S(x) = ax + o(x), then

F (s) = \frac{a}{s − 1} + O(\frac{τ}{σ − 1})

as σ → 1^{+}. This is a simple abelian theorem. In prior discussions of tauberian converses, such as in §5.2, we imposed a bound on the size of f(n) so that S(x) could not change to quickly. In the present context, the hypothesis that |f(n)| ≤ 1 for all n does not yield a converse (cf Exercise 27.5.1.1), but we find that the hypothesis that f ∈ ℳ_{0} is sufficient. The lesson is that for f ∈ ℳ_{0}, the quantity |S(x)| changes more slowly on average than it might under the weaker assumption that |f(n)| ≤ 1.

Theorem 27.14 Suppose that f ∈ ℳ_{0}, let S(x) and F (s) be defined by (27.44) and (27.45), and for α > 0 put

M(α) = ( ∑_{k=−∞}^{∞} \frac{1}{k^{2} + 1} max_{\begin{matrix}σ≥1+α \\ |t−k|≤1/2 \end{matrix}} |F (s)|^{2})^{1/2} .

Then

(27.46)  S(x) ≪ \frac{x}{log x} ∫_{1/ log x}^{1} \frac{M(α)}{α} dα .

From the trivial bound F (s) ≪ 1/(σ − 1) it follows that M(α) ≪ 1/α, and when this is inserted in (27.46) we find that S(x) ≪ x, which is also trivial. However, if for every T we have F (s) = o(1/(σ − 1)) uniformly for |t| ≤ T, then M(α) = o(1/α), and hence S(x) = o(x).

We show below that

(27.47)  M(α) ≫ 1

uniformly for f ∈ ℳ_{0}. Thus the right hand side of (27.46) is ≫ x(log x)^{−1} log log x. That this should be the limit of the method is not surprising, in view of the example considered in Exercise 27.5.1.2, for which f ∈ ℳ_{0}, M(α) ≍ 1, and yet there is a large x for which |S(x)| ≍ x(log x)^{−1} log log x.

To establish (27.47), we write

(27.48)  F (s) = (1 + D(s))G(s)H(s)

where

D(s) = ∑_{k=1}^{∞} \frac{f(2^{k})}{2^{ks}}, G(s) = ∏_{p>2}(1− \frac{f(p)}{p^{s}})^{−1}, H(s) = ∏_{p>2}(1− \frac{f(p)}{p^{s}})(1+ \frac{f(p)}{p^{s}} + \frac{f(p^{2})}{p^{2s}} +⋯).

Here

(1 − \frac{f(p)}{p^{s}})(1 + \frac{f(p)}{p^{s}} + \frac{f(p^{2})}{p^{2s}} + ⋯) = 1 + \frac{f(p^{2}) − f(p)^{2}}{p^{2s}} + \frac{f(p^{3}) − f(p)f(p^{2})}{p^{3s}} + ⋯,

which is 1 plus a quantity whose absolute value does not exceed 2p^{−2σ}(1 − p^{−σ})^{−1}. Thus the product H(s) is absolutely and uniformly convergent for σ ≥ 2/3, and so

(27.49)  log H(s) ≪ 1  (σ ≥ 2/3).

Choose t_{0}, |t_{0}| ≤ π/ log 2, so that f(2)/2^{it_{0}} is positive real. Then ℜf(2)/2^{it} ≥ 0 for |t − t_{0}| ≤ π/(2 log 2), and so |1 + D(s)| ≥ 1/2 for σ ≥ 1, |t − t_{0}| ≤ π/(2 log 2). Also,

∫_{t_{0}−1}^{t_{0}+1} log G(σ + it) dt = ∑_{p>2} ∑_{k=1}^{∞} \frac{f(p)^{k}}{kp^{k(1+α)}} ∫_{t_{0}−1}^{t_{0}+1} p^{−ikt} dt ≪ ∑_{p} ∑_{k=1}^{∞} \frac{1}{k^{2}p^{k} log p} ≪ 1 .

Thus there is an absolute constant c > 0, and a t_{1}, |t_{0} − t_{1}| ≤ 1, such that |1 + D(1 + α + it_{1})| ≥ 1/2 and |G(1 + α + it_{1})| ≥ c, so we have (27.44).

In order to prepare for the proof of Theorem 27.14, we establish Lemma 27.15 For positive integers n let λ_{n} be real, suppose that |a_{n}| ≤ b_{n} for all n, and that ∑_{n=1}^{∞} b_{n} < ∞. Then for any real T_{0} and any T > 0,

∫_{T_{0}−T}^{T_{0}+T} | ∑_{n=1}^{∞} a_{n}e(λ_{n}t)|^{2} dt ≤ 3 ∫_{−T}^{T} | ∑_{n=1}^{∞} b_{n}e(λ_{n}t)|^{2} dt .

Proof It suffices to prove the inequality when T_{0} = 0, for once this is done, the general case follows by replacing a_{n} by a_{n}e(λ_{n}T_{0}). Let K(t) = max(1 − |t|/T, 0). Then

K̂(u) = \frac{1}{T} (\frac{sin πT u}{πu})^{2} ≥ 0,

so

∫_{−∞}^{∞} K(t)| ∑_{n=1}^{∞} a_{n}e(λ_{n}t)|^{2} dt = ∑_{m,n} a_{m}\overline{a_{n}}K̂(λ_{n} − λ_{m})

≤ ∑_{m,n} b_{m}b_{n}K̂(λ_{n} − λ_{m}) = ∫_{−∞}^{∞} K(t)| ∑_{n=1}^{∞} b_{n}e(λ_{n}t)|^{2} dt .

By replacing a_{n} by a_{n}e(λ_{n}T_{0}), we see more generally that

(27.50)  ∫_{−∞}^{∞} K(t − T_{0})| ∑_{n=1}^{∞} a_{n}e(λ_{n}t)|^{2} dt ≤ ∫_{−∞}^{∞} K(t)| ∑_{n=1}^{∞} b_{n}e(λ_{n}t)|^{2} dt .

But χ_{[−T,T]}(t) ≤ K(t + T) + K(t) + K(t − T), so we apply (27.50) three times, with T_{0} = −T, T_{0} = 0, and T_{0} = T, and sum to find that

∫_{−T}^{T} | ∑_{n=1}^{∞} a_{n}e(λ_{n}t)|^{2} dt ≤ 3 ∫_{−∞}^{∞} K(t)| ∑_{n=1}^{∞} b_{n}e(λ_{n}t)|^{2} dt .

This gives the stated result, since K(t) ≤ χ_{[−T,T]}(t). □

Proof of Theorem 27.14 We shall establish the two main estimates

(27.51)  S(x) ≪ \frac{x}{log x} ∫_{1}^{x} \frac{|S(u)|}{u^{2}} du + \frac{x log log x}{log x},

(27.52)  ∫_{1}^{x} \frac{|S(u)| log u}{u^{2}} du ≪ M(2/ log x) log x .

These suffice to give the stated result, since from (27.52) it is evident that

∫_{x^{1/2}}^{x} \frac{|S(u)|}{u^{2}} du ≪ M(2/ log x) ≪ ∫_{1/ log x}^{2/ log x} \frac{M(α)}{α} dα .

We replace x by x^{1/2^{k}} and sum over k to show that

∫_{1}^{x} \frac{|S(u)|}{u^{2}} du ≪ ∫_{1/ log x}^{1} \frac{M(α)}{α} dα .

We insert this in (27.51) to obtain the stated result. The second term in (27.51) can be neglected, in view of (27.47).

To establish (27.51) we first note by Lemma 27.6 that

(27.53)  S(x) log x ≪ x + ∑_{p≤x} |S(x/p)| log p .

Here we have a bound for |S(x)| in terms of S at smaller arguments. The trivial bound for either side is x log x. Thus if it were the case that S(x) were of the order of x, then S(x/p) would have to be of the order of x/p for many primes p. If the primes were exactly uniformly distributed, then the sum over p would be

∫_{1}^{x} |S(x/v)| dv = ∫_{1}^{x} \frac{|S(u)|}{u^{2}} du .

Of course the primes are rather irregularly distributed, but as x varies the points x/p also move, so by averaging over x we can pass to a smoother average of |S|. Suppose that X > Y > Z ≥ 2. Since |S(X) − S(x)| ≤ |X − x| + 1, we see that

|S(X)| log X ≪ \frac{1}{Y} ∫_{X}^{X+Y} |S(x)| log x dx + Y log X .

By (27.53) this is

≪ X + Y log X + \frac{1}{Y} ∫_{X}^{X+Y} ∑_{p≤x} |S(x/p)| log p dx .

We bound the contribution of the smaller primes trivially:

∑_{p≤X/Z} |S(x/p)| log p ≪ x ∑_{p≤X/Z} \frac{log p}{p} ≪ X log X/Z .

As for the contribution of the larger primes, we note that

∫_{X}^{X+Y} ∑_{X/Z<p≤2X} |S(x/p)| log p dx = ∑_{X/Z<p≤2X} ∫_{X}^{X+Y} |S(x/p)| dx log p

= ∑_{X/Z<p≤2X} ∫_{X/p}^{(X+Y)/p} |S(u)| du p log p

= ∫_{1}^{2Z} |S(u)| ∑_{\begin{matrix}X/Z<p≤2X \\ X/u<p≤(X+Y)/u \end{matrix}}p log p du .

Here we can restrict to u ≤ 2Z because the two intervals that p must lie in are disjoint if u > 2Z. In estimating the above, we now drop the condition X/Z < p ≤ 2X. The remaining condition stipulates that p must lie in an interval whose length is Y/u ≥ Y/(2Z) ≥ 2 if Z ≤ Y/4. Thus by the Brun–Titchmarsh inequality (Corollary 3.4) the number of primes in the interval is bounded by the length of the interval divided by the logarithm of its length. Hence the above sum over primes is

≪ \frac{XY log X/u}{u^{2} log Y/u} .

Here the quotient of logarithms is an increasing function of u, so the above is uniformly

≪ \frac{XY log X/(2Z)}{u^{2} log Y/(2Z)} .

We take Y = X/ log X and Z = X/(log X)^{2}, and on assembling our estimates discover that

S(X) log X ≪ X ∫_{1}^{X} \frac{|S(u)|}{u^{2}} du + X log log X .

That is, we have (27.51).

Finally we prove (27.52). Let S_{1}(x) = ∑_{n≤x} f(n) log n. By (27.22) and (27.49) it suffices to show that

(27.54)  ∫_{1}^{x} \frac{|S_{1}(u)|}{u^{2}} du ≪ M(2/ log x) log x .

By the Cauchy–Schwarz inequality,

∫_{1}^{x} \frac{|S_{1}(u)|}{u^{2}} du ≤ ( ∫_{1}^{x} \frac{|S_{1}(u)|^{2}}{u^{3}} du)^{1/2}( ∫_{1}^{x} \frac{1}{u} du)^{1/2} .

It now suffices to show that

(27.55)  ∫_{1}^{∞} \frac{|S_{1}(u)|^{2}}{u^{3+2α}} du ≪ \frac{M(α)^{2}}{α}

for 0 < α ≤ 1, since we obtain (27.54) by taking α = 2/ log x. By Plancherel’s formula as in (5.26), we see that

∫_{1}^{∞} \frac{|S_{1}(u)|^{2}}{u^{3+2α}} du = \frac{1}{2π} ∫_{−∞}^{∞} |\frac{F′(1 + α + it)}{1 + α + it}| dt

≪ ∑_{k=−∞}^{∞} \frac{1}{k^{2} + 1} ∫_{k−1/2}^{k+1/2} |F′(1 + α + it)|^{2} dt .

27.5 Multiplicative functions with vanishing mean value 27

We multiply and divide by |F (1 + α + it)|^{2} to see that the above is

≤ ∑_{k=−∞}^{∞} \frac{1}{k^{2} + 1} ∫_{k−1/2}^{k+1/2} |\frac{F′}{F} (1 + α + it)|^{2} dt max_{|t−k|≤1/2} |F (1 + α + it)|^{2} .

Thus to obtain (27.55) it suffices to show that

(27.56)  ∫_{k−1/2}^{k+1/2} |\frac{F′}{F} (1 + α + it)|^{2} dt ≪ \frac{1}{α} .

By (27.48) we see that

\frac{F′}{F} (s) = \frac{D′(s)}{1 + D(s)} + \frac{G′}{G} (s) + \frac{H′}{H} (s) .

From (27.49) it is evident that \frac{H′}{H} (s) ≪ 1 uniformly for σ ≥ 1. By Lemma 27.15 we see that

∫_{k−1/2}^{k+1/2} |\frac{G′}{G} (1 + α + it)|^{2} dt ≤ 3 ∫_{−1/2}^{1/2} |\frac{ζ′}{ζ} (1 + α + it)|^{2} dt .

If 0 < α ≤ 1, then by Theorem 6.7 this latter integral is

≪ ∫_{−1/2}^{1/2} |α + it|^{−2} dt ≪ \frac{1}{α} .

Clearly D′(s) ≪ 1 for σ ≥ 1. For σ > 1 we write

\frac{1}{1 + D(s)} = ∑_{j=0}^{∞}(−D(s))^{j} .

This is a Dirichlet series whose coefficients do not exceed those of

1 + ∑_{j=1}^{∞} ( ∑_{k=1}^{∞} 2^{−ks})^{j} = 1 + ∑_{j=1}^{∞}(2^{s} − 1)^{−j} = \frac{2^{s} − 1}{2^{s} − 2} .

Hence by Lemma 27.15,

(27.57)  ∫_{k−1/2}^{k+1/2} |1 + D(1 + α + it)|^{−2} dt ≤ 3 ∫_{−1/2}^{1/2} |\frac{2^{1+α+it} − 1}{2^{1+α+it} − 2}|^{2} dt .

Here |2^{1+α+it} − 1| ≍ 1 uniformly for 0 ≤ α ≤ 1, and 2^{1+α+it} − 2 = 2(log 2) ∫_{0}^{α+it} 2^{s} ds .

This integrand has real part ≥ 1/2 for σ ≥ 0 and |t| ≤ π/(3 log 2) = 1.5107867 …, so |2^{1+α+it} − 2| ≫ |α + it| for α ≥ 0 and |t| ≤ 1/2. Thus the right hand side of (27.57) is

≪ ∫_{−1/2}^{1/2} |α + it|^{−2} dt ≪ \frac{1}{α},

so we have (27.56), and the proof is complete. □

The proof just completed depends only on properties of the zeta function in a neighbourhood of s = 1, but if we take f(n) = μ(n), so that F (s) = 1/ζ(s), then the further information that ζ(1 + it) ≠ 0 implies that M(x) = o(x).

We now relate the behaviour of F (s) to the values of f(p).

Theorem 27.16 (Halász) Suppose that f ∈ ℳ_{0}, and let S(x) and F (s) be defined as in (27.44) and (27.45). Then the following are equivalent:

(a) S(x) = o(x) as x → ∞;

(b) For each T > 0, F (s) = o(1/(σ − 1)) as σ → 1^{+} uniformly for |t| ≤ T;

(c) For each fixed t, F (σ + it) = o(1/(σ − 1)) as σ → 1^{+};

(d) For each t, at least one of the following holds:

(27.58) \begin{matrix}(i) & ∑_{p} \frac{1 − ℜ(f(p)p^{−it})}{p} = +∞, \\ (ii) & f(2^{k}) = −2^{ikt} for k = 1, 2, …. \end{matrix}

Moreover, condition (27.58i) holds for all but at most one value of t.

The combined effect of Theorem 27.10 and Theorem 27.16 is rather comprehensive, for if (27.58) fails and

(27.59)  ∑_{p} \frac{ℑ(f(p)p^{−it})}{p}

converges, then by Theorem 27.10 we have

∑_{n≤x} f(n)n^{−it} = ax + o(x)

where

a = ∏_{p} (1 − \frac{1}{p})(1 + \frac{f(p)}{p^{1+it}} + \frac{f(p^{2})}{p^{2+2it}} + ⋯)

is non-zero, and by partial summation,

S(x) = \frac{a}{1 + it}x^{1+it} + o(x) .

In the one remaining case, in which (27.58) fails for some t, and the series (27.56) does not converge for that t, then with more work it can be shown that

(27.60)  S(x) = \frac{x^{1+it}}{1 + it} ∏_{p≤x} (1 − \frac{1}{p})(1 + \frac{f(p)}{p^{1+it}} + \frac{f(p^{2})}{p^{2+2it}} + ⋯) + o(x) .

Proof That (a) implies (b) was the subject of the opening remarks of this section. That (b) implies (a) was established in a strong quantitative form in Theorem 27.14. To see that (c) and (d) are equivalent, we recall the decomposition (27.48). By (27.49) we know that H(s) ≍ 1 uniformly for σ > 1. Also, lim_{σ→1} D(s) = D(1 + it), and 1 + D(1 + it) = 0 if and only if (27.58ii) holds. Finally,

|G(s)(σ − 1)| ≍ |\frac{G(s)}{ζ(σ)}| ≍ exp ( − ∑_{p} \frac{ℜ(1 − f(p)p^{−it})}{p}) .

Here the summands are nonnegative, so the expression is bounded, and tends to 0 if and only if the sum tends to infinity. But since the summands are nonnegative, this is equivalent to (27.58i). Thus (c) and (d) are equivalent. Next we show that (d) implies (b). Suppose first that (27.58i) holds for all t in an interval [T_{1}, T_{2}]. We observe that

F (s)(σ − 1) ≪ exp ( − ∑_{p} \frac{ℜ(1 − f(p)p^{−it})}{p^{σ}}) .

The function on the right hand side decreases to 0 as σ → 1^{+}. Thus we obtain (b) for the interval [T_{1}, T_{2}] by appealing to the following elementary consequence of compactness: If r(σ, t) is continuous in t for each fixed σ > 1, and if for each fixed t ∈ [T_{1}, T_{2}] the function r(σ, t) is monotonically decreasing to 0 as σ → 1^{+}, then r(σ, t) tends to 0 as σ → 1^{+} uniformly for t ∈ [T_{1}, T_{2}]. Now suppose that (27.58i) fails for t = t_{0}, but that (27.58ii) holds for t = t_{0}. Then for |t − t_{0}| ≤ 1 we have

F (s)(σ − 1) ≪ |s − 1 − it_{0}| exp ( − ∑_{p} \frac{ℜ(1 − f(p)p^{−it})}{p^{σ}}) .

Again the right hand side decreases monotonically to 0 as σ → 1^{+}, since (27.58i) holds for 0 < |t − t_{0}| ≤ 1. Thus by the compactness principle again, we have (b) uniformly for |t−t_{0}| ≤ 1. Thus (d) implies (b). Since (b) clearly implies (c), we have shown that (a)–(d) are equivalent.

As for the last assertion, let t_{1} < t_{2} be fixed real numbers, and let 𝒫 be the set of primes p for which arg p^{i(t_{2}−t_{1})} ∈ [2π/3, 4π/3] (mod 2π). That is, if

I_{k} = [exp(2π(k + 1/3)/(t_{2} − t_{1})), exp(2π(k + 2/3)/(t_{2} − t_{1}))],

then 𝒫 consists of those primes such that p ∈ I_{k} for some k. By the Prime Number Theorem we see that ∑_{p∈I_{k}} 1/p ≍ 1/k for all large k. Hence ∑_{p∈𝒫} 1/p = +∞. If ℜ(1 − f(p)p^{−it}) ≤ 1/2, then | arg f(p)p^{−it}| ≤ π/3. If this holds for both t_{1} and t_{2}, then | arg p^{i(t_{1}−t_{2})}| ≤ 2π/3. Thus if p ∈ 𝒫, then the inequality ℜ(1 − f(p)p^{−it_{j}}) ≤ 1/2 fails for at least one value of j, and so

∑_{p∈𝒫} \frac{1}{p} ≤ 2 ∑_{p} \frac{ℜ(1 − f(p)p^{−it_{1}})}{p} + 2 ∑_{p} \frac{ℜ(1 − f(p)p^{−it_{2}})}{p} .

Consequently at most one of the sums on the right is convergent, and the proof is complete. □

Suppose that f ∈ ℳ_{0}. If there is a point of the unit circle |z| = 1 that is not a limit point of the numbers f(p), then for any t ≠ 0 there is a delta such that

∑_{\begin{matrix}p \\ ℜ(1−f(p)p^{−it})>δ \end{matrix}} \frac{1}{p} = +∞,

so (27.58i) holds for all t ≠ 0. In closing we mention a commonly occurring situation.

Corollary 27.17 Suppose that f ∈ ℳ_{0}, and that there is a constant c > 0 such that |ℑf(p)| ≤ c ℜ(1 − f(p)). Then

lim_{x→∞} \frac{1}{x} ∑_{n≤x} f(n)

exists.

Proof In view of the remark made prior to this Corollary, the condition (27.58i) holds for all t ≠ 0. If (27.58) holds when t = 0, then by Theorem 27.16 the mean value tends to 0. Otherwise,

∑_{p} \frac{|1 − f(p)|}{p} ≤ ∑_{p} \frac{ℜ(1 − f(p))| + ℑf(p)|}{p} ≤ (c + 1) ∑_{p} \frac{ℜ(1 − f(p))}{p} < ∞,

so the mean value exists and is non-zero, by Corollary 27.4. □

27.5.1 Exercises

1. Put f(n) = 1 for N < n ≤ 2N, f(n) = 0 otherwise.

(a) By Theorem 1.12, or otherwise, show that F (s) ≪ 1 + τ/N uniformly for σ ≥ 1.

(b) Note that S(x) ≍ x when x = 2N.

2. (Montgomery 1978) (a) Let f_{0}(n) = i^{Ω(n)}. By Theorem 7.18, or otherwise, show that

S_{0}(x) = ∑_{n≤x} f_{0}(n) = cx(log x)^{i−1} + O(x(log x)^{−2})

where

c = \frac{1}{Γ(i)} ∏_{p} (1 − \frac{i}{p})^{−1}(1 − \frac{1}{p})^{i} .

(b) Let F_{0}(s) = ∑_{n=1}^{∞} f_{0}(n)n^{−s}. By means of Theorem 6.7, or otherwise, show that F_{0}(s) ≪ log τ uniformly for σ > 1.

(c) Let f be a totally multiplicative function with

f(p) = \{ \begin{matrix}i & (if ≤ x^{1/2} or p > x), \\ e(θ_{p}) & (for x^{1/2} < p ≤ x) \end{matrix}

where the θ_{p} are to be determined.

(d) Explain why

S(x) = ∑_{\begin{matrix}n≤x \\ p|n ⟹ p≤x^{1/2} \end{matrix}} f_{0}(n) + ∑_{x^{1/2}<p≤x} e(θ_{p})S_{0}(x/p).

(e) Deduce that there is a choice of the θ_{p} such that

|S(x)| = | ∑_{\begin{matrix}n≤x \\ p|n ⟹ p≤x^{1/2} \end{matrix}} f_{0}(n)| + ∑_{x^{1/2}<p≤x} |S_{0}(x/p)|.

(f) Show that

∑_{x^{1/2}<p≤x} |S_{0}(x/p)| ≍ \frac{x log log x}{log x} .

(g) Show that M(α) ≪ 1 uniformly for α > 0.

3. Recall that the ‘negative binomial theorem’ asserts that

(1 − z)^{−r−1} = ∑_{n=0}^{∞} ({n + r \atop n} )z^{n}

for |z| < 1. Here r is any complex number.

(a) Show that if r > −1, then ({n+r \atop n} ) ≥ 0 for all n.

(b) Suppose that f is totally multiplicative, that |f(n)| ≤ 1 for all n, and let F be defined as in (27.45). Show that if q is a positive real number, then

∫_{T_{0}−T}^{T_{0}+T} |F (σ + it)|^{q} dt ≤ 3 ∫_{−T}^{T} |ζ(σ + it)|^{q} dt .

(c) Use (27.48) to show that if f ∈ ℳ_{0} and q > 0, then

∫_{T_{0}−T}^{T_{0}+T} |F (σ + it)|^{q} dt ≪_{q} 3 ∫_{−T}^{T} |ζ(σ + it)|^{q} dt .

4. (Turán) Let f(n) be an integer-valued additive function, and let N(x; q, a) denote the number of n ≤ x such that f(n) ≡ a (mod q).

(a) Show that lim_{x→∞} N(x; , q, a)/x = n(q, a) exists for all a and q.

(b) Show that n(q, a) = 1/q for all a if and only if both the following hold:

(i) For each odd prime p_{1}|q,

∑_{\begin{matrix}p \\ p_{1}|f(p) \end{matrix}} \frac{1}{p} = +∞;

(ii) If 2|q, then

∑_{\begin{matrix}p \\ 2|f(p) \end{matrix}} \frac{1}{p} = +∞

or both of the following hold: f(2^{k}) is odd for all k > 0, and if 4|q, then

∑_{\begin{matrix}p \\ 4|f(p) \end{matrix}} \frac{1}{p} = +∞.