You are currently browsing the tag archive for the ‘multiplicative number theory’ tag.

Let us call an arithmetic function ${f: {\bf N} \rightarrow {\bf C}}$ ${1}$-bounded if we have ${|f(n)| \leq 1}$ for all ${n \in {\bf N}}$. In this section we focus on the asymptotic behaviour of ${1}$-bounded multiplicative functions. Some key examples of such functions include:

• The Möbius function ${\mu}$;
• The Liouville function ${\lambda}$;
• Archimedean” characters ${n \mapsto n^{it}}$ (which I call Archimedean because they are pullbacks of a Fourier character ${x \mapsto x^{it}}$ on the multiplicative group ${{\bf R}^+}$, which has the Archimedean property);
• Dirichlet characters (or “non-Archimedean” characters) ${\chi}$ (which are essentially pullbacks of Fourier characters on a multiplicative cyclic group ${({\bf Z}/q{\bf Z})^\times}$ with the discrete (non-Archimedean) metric);
• Hybrid characters ${n \mapsto \chi(n) n^{it}}$.

The space of ${1}$-bounded multiplicative functions is also closed under multiplication and complex conjugation.

Given a multiplicative function ${f}$, we are often interested in the asymptotics of long averages such as

$\displaystyle \frac{1}{X} \sum_{n \leq X} f(n)$

for large values of ${X}$, as well as short sums

$\displaystyle \frac{1}{H} \sum_{x \leq n \leq x+H} f(n)$

where ${H}$ and ${x}$ are both large, but ${H}$ is significantly smaller than ${x}$. (Throughout these notes we will try to normalise most of the sums and integrals appearing here as averages that are trivially bounded by ${O(1)}$; note that other normalisations are preferred in some of the literature cited here.) For instance, as we established in Theorem 58 of Notes 1, the prime number theorem is equivalent to the assertion that

$\displaystyle \frac{1}{X} \sum_{n \leq X} \mu(n) = o(1) \ \ \ \ \ (1)$

as ${X \rightarrow \infty}$. The Liouville function behaves almost identically to the Möbius function, in that estimates for one function almost always imply analogous estimates for the other:

Exercise 1 Without using the prime number theorem, show that (1) is also equivalent to

$\displaystyle \frac{1}{X} \sum_{n \leq X} \lambda(n) = o(1) \ \ \ \ \ (2)$

as ${X \rightarrow \infty}$. (Hint: use the identities ${\lambda(n) = \sum_{d^2|n} \mu(n/d^2)}$ and ${\mu(n) = \sum_{d^2|n} \mu(d) \lambda(n/d^2)}$.)

Henceforth we shall focus our discussion more on the Liouville function, and turn our attention to averages on shorter intervals. From (2) one has

$\displaystyle \frac{1}{H} \sum_{x \leq n \leq x+H} \lambda(n) = o(1) \ \ \ \ \ (3)$

as ${x \rightarrow \infty}$ if ${H = H(x)}$ is such that ${H \geq \varepsilon x}$ for some fixed ${\varepsilon>0}$. However it is significantly more difficult to understand what happens when ${H}$ grows much slower than this. By using the techniques based on zero density estimates discussed in Notes 6, it was shown by Motohashi and that one can also establish \eqref. On the Riemann Hypothesis Maier and Montgomery lowered the threshold to ${H \geq x^{1/2} \log^C x}$ for an absolute constant ${C}$ (the bound ${H \geq x^{1/2+\varepsilon}}$ is more classical, following from Exercise 33 of Notes 2). On the other hand, the randomness heuristics from Supplement 4 suggest that ${H}$ should be able to be taken as small as ${x^\varepsilon}$, and perhaps even ${\log^{1+\varepsilon} x}$ if one is particularly optimistic about the accuracy of these probabilistic models. On the other hand, the Chowla conjecture (mentioned for instance in Supplement 4) predicts that ${H}$ cannot be taken arbitrarily slowly growing in ${x}$, due to the conjectured existence of arbitrarily long strings of consecutive numbers where the Liouville function does not change sign (and in fact one can already show from the known partial results towards the Chowla conjecture that (3) fails for some sequence ${x \rightarrow \infty}$ and some sufficiently slowly growing ${H = H(x)}$, by modifying the arguments in these papers of mine).
The situation is better when one asks to understand the mean value on almost all short intervals, rather than all intervals. There are several equivalent ways to formulate this question:

Exercise 2 Let ${H = H(X)}$ be a function of ${X}$ such that ${H \rightarrow \infty}$ and ${H = o(X)}$ as ${X \rightarrow \infty}$. Let ${f: {\bf N} \rightarrow {\bf C}}$ be a ${1}$-bounded function. Show that the following assertions are equivalent:

• (i) One has

$\displaystyle \frac{1}{H} \sum_{x \leq n \leq x+H} f(n) = o(1)$

as ${X \rightarrow \infty}$, uniformly for all ${x \in [X,2X]}$ outside of a set of measure ${o(X)}$.

• (ii) One has

$\displaystyle \frac{1}{X} \int_X^{2X} |\frac{1}{H} \sum_{x \leq n \leq x+H} f(n)|\ dx = o(1)$

as ${X \rightarrow \infty}$.

• (iii) One has

$\displaystyle \frac{1}{X} \int_X^{2X} |\frac{1}{H} \sum_{x \leq n \leq x+H} f(n)|^2\ dx = o(1) \ \ \ \ \ (4)$

as ${X \rightarrow \infty}$.

As it turns out the second moment formulation in (iii) will be the most convenient for us to work with in this set of notes, as it is well suited to Fourier-analytic techniques (and in particular the Plancherel theorem).

Using zero density methods, for instance, it was shown by Ramachandra that

$\displaystyle \frac{1}{X} \int_X^{2X} |\frac{1}{H} \sum_{x \leq n \leq x+H} \lambda(n)|^2\ dx \ll_{A,\varepsilon} \log^{-A} X$

whenever ${X^{1/6+\varepsilon} \leq H \leq X}$ and ${\varepsilon>0}$. With this quality of bound (saving arbitrary powers of ${\log X}$ over the trivial bound of ${O(1)}$), this is still the lowest value of ${H}$ one can reach unconditionally. However, in a striking recent breakthrough, it was shown by Matomaki and Radziwill that as long as one is willing to settle for weaker bounds (saving a small power of ${\log X}$ or ${\log H}$, or just a qualitative decay of ${o(1)}$), one can obtain non-trivial estimates on far shorter intervals. For instance, they show

Theorem 3 (Matomaki-Radziwill theorem for Liouville) For any ${2 \leq H \leq X}$, one has

$\displaystyle \frac{1}{X} \int_X^{2X} |\frac{1}{H} \sum_{x \leq n \leq x+H} \lambda(n)|^2\ dx \ll \log^{-c} H$

for some absolute constant ${c>0}$.

In fact they prove a slightly more precise result: see Theorem 1 of that paper. In particular, they obtain the asymptotic (4) for any function ${H = H(X)}$ that goes to infinity as ${X \rightarrow \infty}$, no matter how slowly! This ability to let ${H}$ grow slowly with ${X}$ is important for several applications; for instance, in order to combine this type of result with the entropy decrement methods from Notes 9, it is essential that ${H}$ be allowed to grow more slowly than ${\log X}$. See also this survey of Soundararajan for further discussion.

Exercise 4 In this exercise you may use Theorem 3 freely.

• (i) Establish the upper bound

$\displaystyle \frac{1}{X} \sum_{n \leq X} \lambda(n)\lambda(n+1) < 1-c$

for some absolute constant ${c>0}$ and all sufficiently large ${X}$. (Hint: if this bound failed, then ${\lambda(n)=\lambda(n+1)}$ would hold for almost all ${n}$; use this to create many intervals ${[x,x+H]}$ for which ${\frac{1}{H} \sum_{x \leq n \leq x+H} \lambda(n)}$ is extremely large.)

• (ii) Show that Theorem 3 also holds with ${\lambda(n)}$ replaced by ${\chi_2 \lambda(n)}$, where ${\chi_2}$ is the principal character of period ${2}$. (Use the fact that ${\lambda(2n)=-\lambda(n)}$ for all ${n}$.) Use this to establish the corresponding lower bound

$\displaystyle \frac{1}{X} \sum_{n \leq X} \lambda(n)\lambda(n+1) > -1+c$

to (i).

(There is a curious asymmetry to the difficulty level of these bounds; the upper bound in (ii) was established much earlier by Harman, Pintz, and Wolke, but the lower bound in (i) was only established in the Matomaki-Radziwill paper.)

The techniques discussed previously were highly complex-analytic in nature, relying in particular on the fact that functions such as ${\mu}$ or ${\lambda}$ have Dirichlet series ${{\mathcal D} \mu(s) = \frac{1}{\zeta(s)}}$, ${{\mathcal D} \lambda(s) = \frac{\zeta(2s)}{\zeta(s)}}$ that extend meromorphically into the critical strip. In contrast, the Matomaki-Radziwill theorem does not rely on such meromorphic continuations, and in fact holds for more general classes of ${1}$-bounded multiplicative functions ${f}$, for which one typically does not expect any meromorphic continuation into the strip. Instead, one can view the Matomaki-Radziwill theory as following the philosophy of a slightly different approach to multiplicative number theory, namely the pretentious multiplicative number theory of Granville and Soundarajan (as presented for instance in their draft monograph). A basic notion here is the pretentious distance between two ${1}$-bounded multiplicative functions ${f,g}$ (at a given scale ${X}$), which informally measures the extent to which ${f}$ “pretends” to be like ${g}$ (or vice versa). The precise definition is

Definition 5 (Pretentious distance) Given two ${1}$-bounded multiplicative functions ${f,g}$, and a threshold ${X>0}$, the pretentious distance ${\mathbb{D}(f,g;X)}$ between ${f}$ and ${g}$ up to scale ${X}$ is given by the formula

$\displaystyle \mathbb{D}(f,g;X) := \left( \sum_{p \leq X} \frac{1 - \mathrm{Re}(f(p) \overline{g(p)})}{p} \right)^{1/2}$

Note that one can also define an infinite version ${\mathbb{D}(f,g;\infty)}$ of this distance by removing the constraint ${p \leq X}$, though in such cases the pretentious distance may then be infinite. The pretentious distance is not quite a metric (because ${\mathbb{D}(f,f;X)}$ can be non-zero, and furthermore ${\mathbb{D}(f,g;X)}$ can vanish without ${f,g}$ being equal), but it is still quite close to behaving like a metric, in particular it obeys the triangle inequality; see Exercise 16 below. The philosophy of pretentious multiplicative number theory is that two ${1}$-bounded multiplicative functions ${f,g}$ will exhibit similar behaviour at scale ${X}$ if their pretentious distance ${\mathbb{D}(f,g;X)}$ is bounded, but will become uncorrelated from each other if this distance becomes large. A simple example of this philosophy is given by the following “weak Halasz theorem”, proven in Section 2:

Proposition 6 (Logarithmically averaged version of Halasz) Let ${X}$ be sufficiently large. Then for any ${1}$-bounded multiplicative functions ${f,g}$, one has

$\displaystyle \frac{1}{\log X} \sum_{n \leq X} \frac{f(n) \overline{g(n)}}{n} \ll \exp( - c \mathbb{D}(f, g;X)^2 )$

for an absolute constant ${c>0}$.

In particular, if ${f}$ does not pretend to be ${1}$, then the logarithmic average ${\frac{1}{\log X} \sum_{n \leq X} \frac{f(n)}{n}}$ will be small. This condition is basically necessary, since of course ${\frac{1}{\log X} \sum_{n \leq X} \frac{1}{n} = 1 + o(1)}$.

If one works with non-logarithmic averages ${\frac{1}{X} \sum_{n \leq X} f(n)}$, then not pretending to be ${1}$ is insufficient to establish decay, as was already observed in Exercise 11 of Notes 1: if ${f}$ is an Archimedean character ${f(n) = n^{it}}$ for some non-zero real ${t}$, then ${\frac{1}{\log X} \sum_{n \leq X} \frac{f(n)}{n}}$ goes to zero as ${X \rightarrow \infty}$ (which is consistent with Proposition 6), but ${\frac{1}{X} \sum_{n \leq X} f(n)}$ does not go to zero. However, this is in some sense the “only” obstruction to these averages decaying to zero, as quantified by the following basic result:

Theorem 7 (Halasz’s theorem) Let ${X}$ be sufficiently large. Then for any ${1}$-bounded multiplicative function ${f}$, one has

$\displaystyle \frac{1}{X} \sum_{n \leq X} f(n) \ll \exp( - c \min_{|t| \leq T} \mathbb{D}(f, n \mapsto n^{it};X)^2 ) + \frac{1}{T}$

for an absolute constant ${c>0}$ and any ${T > 0}$.

Informally, we refer to a ${1}$-bounded multiplicative function as “pretentious’; if it pretends to be a character such as ${n^{it}}$, and “non-pretentious” otherwise. The precise distinction is rather malleable, as the precise class of characters that one views as “obstructions” varies from situation to situation. For instance, in Proposition 6 it is just the trivial character ${1}$ which needs to be considered, but in Theorem 7 it is the characters ${n \mapsto n^{it}}$ with ${|t| \leq T}$. In other contexts one may also need to add Dirichlet characters ${\chi(n)}$ or hybrid characters such as ${\chi(n) n^{it}}$ to the list of characters that one might pretend to be. The division into pretentious and non-pretentious functions in multiplicative number theory is faintly analogous to the division into major and minor arcs in the circle method applied to additive number theory problems; see Notes 8. The Möbius and Liouville functions are model examples of non-pretentious functions; see Exercise 24.

In the contrapositive, Halasz’ theorem can be formulated as the assertion that if one has a large mean

$\displaystyle |\frac{1}{X} \sum_{n \leq X} f(n)| \geq \eta$

for some ${\eta > 0}$, then one has the pretentious property

$\displaystyle \mathbb{D}( f, n \mapsto n^{it}; X ) \ll \sqrt{\log(1/\eta)}$

for some ${t \ll \eta^{-1}}$. This has the flavour of an “inverse theorem”, of the type often found in arithmetic combinatorics.
Among other things, Halasz’s theorem gives yet another proof of the prime number theorem (1); see Section 2.

We now give a version of the Matomaki-Radziwill theorem for general (non-pretentious) multiplicative functions that is formulated in a similar contrapositive (or “inverse theorem”) fashion, though to simplify the presentation we only state a qualitative version that does not give explicit bounds.

Theorem 8 ((Qualitative) Matomaki-Radziwill theorem) Let ${\eta>0}$, and let ${1 \leq H \leq X}$, with ${H}$ sufficiently large depending on ${\eta}$. Suppose that ${f}$ is a ${1}$-bounded multiplicative function such that

$\displaystyle \frac{1}{X} \int_X^{2X} |\frac{1}{H} \sum_{x \leq n \leq x+H} f(n)|^2\ dx \geq \eta^2.$

Then one has

$\displaystyle \mathbb{D}(f, n \mapsto n^{it};X) \ll_\eta 1$

for some ${t \ll_\eta \frac{X}{H}}$.

The condition ${t \ll_\eta \frac{X}{H}}$ is basically optimal, as the following example shows:

Exercise 9 Let ${\varepsilon>0}$ be a sufficiently small constant, and let ${1 \leq H \leq X}$ be such that ${\frac{1}{\varepsilon} \leq H \leq \varepsilon X}$. Let ${f}$ be the Archimedean character ${f(n) = n^{it}}$ for some ${|t| \leq \varepsilon \frac{X}{H}}$. Show that

$\displaystyle \frac{1}{X} \int_X^{2X} |\frac{1}{H} \sum_{x \leq n \leq x+H} f(n)|^2\ dx \asymp 1.$

Combining Theorem 8 with standard non-pretentiousness facts about the Liouville function (see Exercise 24), we recover Theorem 3 (but with a decay rate of only ${o(1)}$ rather than ${\log^{-c} H}$). We refer the reader to the original paper of Matomaki-Radziwill (as well as this followup paper with myself) for the quantitative version of Theorem 8 that is strong enough to recover the full version of Theorem 3, and which can also handle real-valued pretentious functions.

With our current state of knowledge, the only arguments that can establish the full strength of Halasz and Matomaki-Radziwill theorems are Fourier analytic in nature, relating sums involving an arithmetic function ${f}$ with its Dirichlet series

$\displaystyle {\mathcal D} f(s) := \sum_{n=1}^\infty \frac{f(n)}{n^s}$

which one can view as a discrete Fourier transform of ${f}$ (or more precisely of the measure ${\sum_{n=1}^\infty \frac{f(n)}{n} \delta_{\log n}}$, if one evaluates the Dirichlet series on the right edge ${\{ 1+it: t \in {\bf R} \}}$ of the critical strip). In this aspect, the techniques resemble the complex-analytic methods from Notes 2, but with the key difference that no analytic or meromorphic continuation into the strip is assumed. The key identity that allows us to pass to Dirichlet series is the following variant of Proposition 7 of Notes 2:

Proposition 10 (Parseval type identity) Let ${f,g: {\bf N} \rightarrow {\bf C}}$ be finitely supported arithmetic functions, and let ${\psi: {\bf R} \rightarrow {\bf R}}$ be a Schwartz function. Then

$\displaystyle \sum_{n=1}^\infty \sum_{m=1}^\infty \frac{f(n)}{n} \frac{\overline{g(m)}}{m} \psi(\log n - \log m) = \frac{1}{2\pi} \int_{\bf R} {\mathcal D} f(1+it) \overline{{\mathcal D} g(1+it)} \hat \psi(t)\ dt$

where ${\hat \psi(t) := \int_{\bf R} \psi(u) e^{itu}\ du}$ is the Fourier transform of ${\psi}$. (Note that the finite support of ${f,g}$ and the Schwartz nature of ${\psi,\hat \psi}$ ensure that both sides of the identity are absolutely convergent.)

The restriction that ${f,g}$ be finitely supported will be slightly annoying in places, since most multiplicative functions will fail to be finitely supported, but this technicality can usually be overcome by suitably truncating the multiplicative function, and taking limits if necessary.

Proof: By expanding out the Dirichlet series, it suffices to show that

$\displaystyle \psi(\log n - \log m) = \frac{1}{2\pi} \int_{\bf R} \frac{1}{n^{it}} \frac{1}{m^{-it}} \hat \psi(t)\ dt$

for any natural numbers ${n,m}$. But this follows from the Fourier inversion formula ${\psi(u) = \frac{1}{2\pi} \int_{\bf R} e^{-itu} \hat \psi(t)\ dt}$ applied at ${u = \log n - \log m}$. $\Box$
For applications to Halasz type theorems, one sets ${g(n)}$ equal to the Kronecker delta ${\delta_{n=1}}$, producing weighted integrals of ${{\mathcal D} f(1+it)}$ of “${L^1}$” type. For applications to Matomaki-Radziwill theorems, one instead sets ${f=g}$, and more precisely uses the following corollary of the above proposition, to obtain weighted integrals of ${|{\mathcal D} f(1+it)|^2}$ of “${L^2}$” type:

Exercise 11 (Plancherel type identity) If ${f: {\bf N} \rightarrow {\bf C}}$ is finitely supported, and ${\varphi: {\bf R} \rightarrow {\bf R}}$ is a Schwartz function, establish the identity

$\displaystyle \int_0^\infty |\sum_{n=1}^\infty \frac{f(n)}{n} \varphi(\log n - \log y)|^2 \frac{dy}{y} = \frac{1}{2\pi} \int_{\bf R} |{\mathcal D} f(1+it)|^2 |\hat \varphi(t)|^2\ dt.$

In contrast, information about the non-pretentious nature of a multiplicative function ${f}$ will give “pointwise” or “${L^\infty}$” type control on the Dirichlet series ${{\mathcal D} f(1+it)}$, as is suggested from the Euler product factorisation of ${{\mathcal D} f}$.

It will be convenient to formalise the notion of ${L^1}$, ${L^2}$, and ${L^\infty}$ control of the Dirichlet series ${{\mathcal D} f}$, which as previously mentioned can be viewed as a sort of “Fourier transform” of ${f}$:

Definition 12 (Fourier norms) Let ${f: {\bf N} \rightarrow {\bf C}}$ be finitely supported, and let ${\Omega \subset {\bf R}}$ be a bounded measurable set. We define the Fourier ${L^\infty}$ norm

$\displaystyle \| f\|_{FL^\infty(\Omega)} := \sup_{t \in \Omega} |{\mathcal D} f(1+it)|,$

the Fourier ${L^2}$ norm

$\displaystyle \| f\|_{FL^2(\Omega)} := \left(\int_\Omega |{\mathcal D} f(1+it)|^2\ dt\right)^{1/2},$

and the Fourier ${L^1}$ norm

$\displaystyle \| f\|_{FL^1(\Omega)} := \int_\Omega |{\mathcal D} f(1+it)|\ dt.$

One could more generally define ${FL^p}$ norms for other exponents ${p}$, but we will only need the exponents ${p=1,2,\infty}$ in this current set of notes. It is clear that all the above norms are in fact (semi-)norms on the space of finitely supported arithmetic functions.

As mentioned above, Halasz’s theorem gives good control on the Fourier ${L^\infty}$ norm for restrictions of non-pretentious functions to intervals:

Exercise 13 (Fourier ${L^\infty}$ control via Halasz) Let ${f: {\bf N} \rightarrow {\bf C}}$ be a ${1}$-bounded multiplicative function, let ${I}$ be an interval in ${[C^{-1} X, CX]}$ for some ${X \geq C \geq 1}$, let ${R \geq 1}$, and let ${\Omega \subset {\bf R}}$ be a bounded measurable set. Show that

$\displaystyle \| f 1_I \|_{FL^\infty(\Omega)} \ll_C \exp( - c \min_{t: \mathrm{dist}(t,\Omega) \leq R} \mathbb{D}(f, n \mapsto n^{it};X)^2 ) + \frac{1}{R}.$

(Hint: you will need to use summation by parts (or an equivalent device) to deal with a ${\frac{1}{n}}$ weight.)

Meanwhile, the Plancherel identity in Exercise 11 gives good control on the Fourier ${L^2}$ norm for functions on long intervals (compare with Exercise 2 from Notes 6):

Exercise 14 (${L^2}$ mean value theorem) Let ${T \geq 1}$, and let ${f: {\bf N} \rightarrow {\bf C}}$ be finitely supported. Show that

$\displaystyle \| f \|_{FL^2([-T,T])}^2 \ll \sum_n \frac{1}{n} (\frac{T}{n} \sum_{m: |n-m| \leq n/T} |f(m)|)^2.$

Conclude in particular that if ${f}$ is supported in ${[C^{-1} N, C N]}$ for some ${C \geq 1}$ and ${N \gg T}$, then

$\displaystyle \| f \|_{FL^2([-T,T])}^2 \ll C^{O(1)} \frac{1}{N} \sum_n |f(n)|^2.$

In the simplest case of the logarithmically averaged Halasz theorem (Proposition 6), Fourier ${L^\infty}$ estimates are already sufficient to obtain decent control on the (weighted) Fourier ${L^1}$ type expressions that show up. However, these estimates are not enough by themselves to establish the full Halasz theorem or the Matomaki-Radziwill theorem. To get from Fourier ${L^\infty}$ control to Fourier ${L^1}$ or ${L^2}$ control more efficiently, the key trick is use Hölder’s inequality, which when combined with the basic Dirichlet series identity

$\displaystyle {\mathcal D}(f*g) = ({\mathcal D} f) ({\mathcal D} g)$

gives the inequalities

$\displaystyle \| f*g \|_{FL^1(\Omega)} \leq \|f\|_{FL^2(\Omega)} \|g\|_{FL^2(\Omega)} \ \ \ \ \ (5)$

and

$\displaystyle \| f*g \|_{FL^2(\Omega)} \leq \|f\|_{FL^2(\Omega)} \|g\|_{FL^\infty(\Omega)} \ \ \ \ \ (6)$

The strategy is then to factor (or approximately factor) the original function ${f}$ as a Dirichlet convolution (or average of convolutions) of various components, each of which enjoys reasonably good Fourier ${L^2}$ or ${L^\infty}$ estimates on various regions ${\Omega}$, and then combine them using the Hölder inequalities (5), (6) and the triangle inequality. For instance, to prove Halasz’s theorem, we will split ${f}$ into the Dirichlet convolution of three factors, one of which will be estimated in ${FL^\infty}$ using the non-pretentiousness hypothesis, and the other two being estimated in ${FL^2}$ using Exercise 14. For the Matomaki-Radziwill theorem, one uses a significantly more complicated decomposition of ${f}$ into a variety of Dirichlet convolutions of factors, and also splits up the Fourier domain ${[-T,T]}$ into several subregions depending on whether the Dirichlet series associated to some of these components are large or small. In each region and for each component of these decompositions, all but one of the factors will be estimated in ${FL^\infty}$, and the other in ${FL^2}$; but the precise way in which this is done will vary from component to component. For instance, in some regions a key factor will be small in ${FL^\infty}$ by construction of the region; in other places, the ${FL^\infty}$ control will come from Exercise 13. Similarly, in some regions, satisfactory ${FL^2}$ control is provided by Exercise 14, but in other regions one must instead use “large value” theorems (in the spirit of Proposition 9 from Notes 6), or amplify the power of the standard ${L^2}$ mean value theorems by combining the Dirichlet series with other Dirichlet series that are known to be large in this region.
There are several ways to achieve the desired factorisation. In the case of Halasz’s theorem, we can simply work with a crude version of the Euler product factorisation, dividing the primes into three categories (“small”, “medium”, and “large” primes) and expressing ${f}$ as a triple Dirichlet convolution accordingly. For the Matomaki-Radziwill theorem, one instead exploits the Turan-Kubilius phenomenon (Section 5 of Notes 1, or Lemma 2 of Notes 9)) that for various moderately wide ranges ${[P,Q]}$ of primes, the number of prime divisors of a large number ${n}$ in the range ${[P,Q]}$ is almost always close to ${\log\log Q - \log\log P}$. Thus, if we introduce the arithmetic functions

$\displaystyle w_{[P,Q]}(n) = \frac{1}{\log\log Q - \log\log P} \sum_{P \leq p \leq Q} 1_{n=p} \ \ \ \ \ (7)$

then we have

$\displaystyle 1 \approx 1 * w_{[P,Q]}$

and more generally we have a twisted approximation

$\displaystyle f \approx f * fw_{[P,Q]}$

for multiplicative functions ${f}$. (Actually, for technical reasons it will be convenient to work with a smoothed out version of these functions; see Section 3.) Informally, these formulas suggest that the “${FL^2}$ energy” of a multiplicative function ${f}$ is concentrated in those regions where ${f w_{[P,Q]}}$ is extremely large in a ${FL^\infty}$ sense. Iterations of this formula (or variants of this formula, such as an identity due to Ramaré) will then give the desired (approximate) factorisation of ${{\mathcal D} f}$.
Read the rest of this entry »

In analytic number theory, it is a well-known phenomenon that for many arithmetic functions ${f: {\bf N} \rightarrow {\bf C}}$ of interest in number theory, it is significantly easier to estimate logarithmic sums such as

$\displaystyle \sum_{n \leq x} \frac{f(n)}{n}$

than it is to estimate summatory functions such as

$\displaystyle \sum_{n \leq x} f(n).$

(Here we are normalising ${f}$ to be roughly constant in size, e.g. ${f(n) = O( n^{o(1)} )}$ as ${n \rightarrow \infty}$.) For instance, when ${f}$ is the von Mangoldt function ${\Lambda}$, the logarithmic sums ${\sum_{n \leq x} \frac{\Lambda(n)}{n}}$ can be adequately estimated by Mertens’ theorem, which can be easily proven by elementary means (see Notes 1); but a satisfactory estimate on the summatory function ${\sum_{n \leq x} \Lambda(n)}$ requires the prime number theorem, which is substantially harder to prove (see Notes 2). (From a complex-analytic or Fourier-analytic viewpoint, the problem is that the logarithmic sums ${\sum_{n \leq x} \frac{f(n)}{n}}$ can usually be controlled just from knowledge of the Dirichlet series ${\sum_n \frac{f(n)}{n^s}}$ for ${s}$ near ${1}$; but the summatory functions require control of the Dirichlet series ${\sum_n \frac{f(n)}{n^s}}$ for ${s}$ on or near a large portion of the line ${\{ 1+it: t \in {\bf R} \}}$. See Notes 2 for further discussion.)

Viewed conversely, whenever one has a difficult estimate on a summatory function such as ${\sum_{n \leq x} f(n)}$, one can look to see if there is a “cheaper” version of that estimate that only controls the logarithmic sums ${\sum_{n \leq x} \frac{f(n)}{n}}$, which is easier to prove than the original, more “expensive” estimate. In this post, we shall do this for two theorems, a classical theorem of Halasz on mean values of multiplicative functions on long intervals, and a much more recent result of Matomaki and Radziwiłł on mean values of multiplicative functions in short intervals. The two are related; the former theorem is an ingredient in the latter (though in the special case of the Matomaki-Radziwiłł theorem considered here, we will not need Halasz’s theorem directly, instead using a key tool in the proof of that theorem).

We begin with Halasz’s theorem. Here is a version of this theorem, due to Montgomery and to Tenenbaum:

Theorem 1 (Halasz-Montgomery-Tenenbaum) Let ${f: {\bf N} \rightarrow {\bf C}}$ be a multiplicative function with ${|f(n)| \leq 1}$ for all ${n}$. Let ${x \geq 3}$ and ${T \geq 1}$, and set

$\displaystyle M := \min_{|t| \leq T} \sum_{p \leq x} \frac{1 - \hbox{Re}( f(p) p^{-it} )}{p}.$

Then one has

$\displaystyle \frac{1}{x} \sum_{n \leq x} f(n) \ll (1+M) e^{-M} + \frac{1}{\sqrt{T}}.$

Informally, this theorem asserts that ${\sum_{n \leq x} f(n)}$ is small compared with ${x}$, unless ${f}$ “pretends” to be like the character ${p \mapsto p^{it}}$ on primes for some small ${y}$. (This is the starting point of the “pretentious” approach of Granville and Soundararajan to analytic number theory, as developed for instance here.) We now give a “cheap” version of this theorem which is significantly weaker (both because it settles for controlling logarithmic sums rather than summatory functions, it requires ${f}$ to be completely multiplicative instead of multiplicative, it requires a strong bound on the analogue of the quantity ${M}$, and because it only gives qualitative decay rather than quantitative estimates), but easier to prove:

Theorem 2 (Cheap Halasz) Let ${x}$ be an asymptotic parameter goingto infinity. Let ${f: {\bf N} \rightarrow {\bf C}}$ be a completely multiplicative function (possibly depending on ${x}$) such that ${|f(n)| \leq 1}$ for all ${n}$, such that

$\displaystyle \sum_{p \leq x} \frac{1 - \hbox{Re}( f(p) )}{p} \gg \log\log x. \ \ \ \ \ (1)$

Then

$\displaystyle \frac{1}{\log x} \sum_{n \leq x} \frac{f(n)}{n} = o(1). \ \ \ \ \ (2)$

Note that now that we are content with estimating exponential sums, we no longer need to preclude the possibility that ${f(p)}$ pretends to be like ${p^{it}}$; see Exercise 11 of Notes 1 for a related observation.

To prove this theorem, we first need a special case of the Turan-Kubilius inequality.

Lemma 3 (Turan-Kubilius) Let ${x}$ be a parameter going to infinity, and let ${1 < P < x}$ be a quantity depending on ${x}$ such that ${P = x^{o(1)}}$ and ${P \rightarrow \infty}$ as ${x \rightarrow \infty}$. Then

$\displaystyle \sum_{n \leq x} \frac{ | \frac{1}{\log \log P} \sum_{p \leq P: p|n} 1 - 1 |}{n} = o( \log x ).$

Informally, this lemma is asserting that

$\displaystyle \sum_{p \leq P: p|n} 1 \approx \log \log P$

for most large numbers ${n}$. Another way of writing this heuristically is in terms of Dirichlet convolutions:

$\displaystyle 1 \approx 1 * \frac{1}{\log\log P} 1_{{\mathcal P} \cap [1,P]}.$

This type of estimate was previously discussed as a tool to establish a criterion of Katai and Bourgain-Sarnak-Ziegler for Möbius orthogonality estimates in this previous blog post. See also Section 5 of Notes 1 for some similar computations.

Proof: By Cauchy-Schwarz it suffices to show that

$\displaystyle \sum_{n \leq x} \frac{ | \frac{1}{\log \log P} \sum_{p \leq P: p|n} 1 - 1 |^2}{n} = o( \log x ).$

Expanding out the square, it suffices to show that

$\displaystyle \sum_{n \leq x} \frac{ (\frac{1}{\log \log P} \sum_{p \leq P: p|n} 1)^j}{n} = \log x + o( \log x )$

for ${j=0,1,2}$.

We just show the ${j=2}$ case, as the ${j=0,1}$ cases are similar (and easier). We rearrange the left-hand side as

$\displaystyle \frac{1}{(\log\log P)^2} \sum_{p_1, p_2 \leq P} \sum_{n \leq x: p_1,p_2|n} \frac{1}{n}.$

We can estimate the inner sum as ${(1+o(1)) \frac{1}{[p_1,p_2]} \log x}$. But a routine application of Mertens’ theorem (handling the diagonal case when ${p_1=p_2}$ separately) shows that

$\displaystyle \sum_{p_1, p_2 \leq P} \frac{1}{[p_1,p_2]} = (1+o(1)) (\log\log P)^2$

and the claim follows. $\Box$

Remark 4 As an alternative to the Turan-Kubilius inequality, one can use the Ramaré identity

$\displaystyle \sum_{p \leq P: p|n} \frac{1}{\# \{ p' \leq P: p'|n\} + 1} - 1 = 1_{(p,n)=1 \hbox{ for all } p \leq P}$

(see e.g. Section 17.3 of Friedlander-Iwaniec). This identity turns out to give superior quantitative results than the Turan-Kubilius inequality in applications; see the paper of Matomaki and Radziwiłł for an instance of this.

We now prove Theorem 2. Let ${Q}$ denote the left-hand side of (2); by the triangle inequality we have ${Q=O(1)}$. By Lemma 3 (for some ${P = x^{o(1)}}$ to be chosen later) and the triangle inequality we have

$\displaystyle \sum_{n \leq x} \frac{\frac{1}{\log \log P} \sum_{p \leq P: p|n} f(n)}{n} = Q \log x + o( \log x ).$

We rearrange the left-hand side as

$\displaystyle \frac{1}{\log\log P} \sum_{p \leq P} \frac{f(p)}{p} \sum_{m \leq x/p} \frac{f(m)}{m}.$

We now replace the constraint ${m \leq x/p}$ by ${m \leq x}$. The error incurred in doing so is

$\displaystyle O( \frac{1}{\log\log P} \sum_{p \leq P} \frac{1}{p} \sum_{x/P \leq m \leq x} \frac{1}{m} )$

which by Mertens’ theorem is ${O(\log P) = o( \log x )}$. Thus we have

$\displaystyle \frac{1}{\log\log P} \sum_{p \leq P} \frac{f(p)}{p} \sum_{m \leq x} \frac{f(m)}{m} = Q \log x + o( \log x ).$

But by definition of ${Q}$, we have ${\sum_{m \leq x} \frac{f(m)}{m} = Q \log x}$, thus

$\displaystyle [1 - \frac{1}{\log\log P} \sum_{p \leq P} \frac{f(p)}{p}] Q = o(1). \ \ \ \ \ (3)$

From Mertens’ theorem, the expression in brackets can be rewritten as

$\displaystyle \frac{1}{\log\log P} \sum_{p \leq P} \frac{1 - f(p)}{p} + o(1)$

and so the real part of this expression is

$\displaystyle \frac{1}{\log\log P} \sum_{p \leq P} \frac{1 - \hbox{Re} f(p)}{p} + o(1).$

By (1), Mertens’ theorem and the hypothesis on ${f}$ we have

$\displaystyle \sum_{p \leq x^\varepsilon} \frac{(1 - \hbox{Re} f(p)) \log p}{p} \gg \log\log x^\varepsilon - O_\varepsilon(1)$

for any ${\varepsilon > 0}$. This implies that we can find ${P = x^{o(1)}}$ going to infinity such that

$\displaystyle \sum_{p \leq P} \frac{(1 - \hbox{Re} f(p)) \log p}{p} \gg (1-o(1))\log\log P$

and thus the expression in brackets has real part ${\gg 1-o(1)}$. The claim follows.

The Turan-Kubilius argument is certainly not the most efficient way to estimate sums such as ${\frac{1}{n} \sum_{n \leq x} f(n)}$. In the exercise below we give a significantly more accurate estimate that works when ${f}$ is non-negative.

Exercise 5 (Granville-Koukoulopoulos-Matomaki)

• (i) If ${g}$ is a completely multiplicative function with ${g(p) \in \{0,1\}}$ for all primes ${p}$, show that

$\displaystyle (e^{-\gamma}-o(1)) \prod_{p \leq x} (1 - \frac{g(p)}{p})^{-1} \leq \sum_{n \leq x} \frac{g(n)}{n} \leq \prod_{p \leq x} (1 - \frac{g(p)}{p})^{-1}.$

as ${x \rightarrow \infty}$. (Hint: for the upper bound, expand out the Euler product. For the lower bound, show that ${\sum_{n \leq x} \frac{g(n)}{n} \times \sum_{n \leq x} \frac{h(n)}{n} \ge \sum_{n \leq x} \frac{1}{n}}$, where ${h}$ is the completely multiplicative function with ${h(p) = 1-g(p)}$ for all primes ${p}$.)

• (ii) If ${g}$ is multiplicative and takes values in ${[0,1]}$, show that

$\displaystyle \sum_{n \leq x} \frac{g(n)}{n} \asymp \prod_{p \leq x} (1 - \frac{g(p)}{p})^{-1}$

$\displaystyle \asymp \exp( \sum_{p \leq x} \frac{g(p)}{p} )$

for all ${x \geq 1}$.

Now we turn to a very recent result of Matomaki and Radziwiłł on mean values of multiplicative functions in short intervals. For sake of illustration we specialise their results to the simpler case of the Liouville function ${\lambda}$, although their arguments actually work (with some additional effort) for arbitrary multiplicative functions of magnitude at most ${1}$ that are real-valued (or more generally, stay far from complex characters ${p \mapsto p^{it}}$). Furthermore, we give a qualitative form of their estimates rather than a quantitative one:

Theorem 6 (Matomaki-Radziwiłł, special case) Let ${X}$ be a parameter going to infinity, and let ${2 \leq h \leq X}$ be a quantity going to infinity as ${X \rightarrow \infty}$. Then for all but ${o(X)}$ of the integers ${x \in [X,2X]}$, one has

$\displaystyle \sum_{x \leq n \leq x+h} \lambda(n) = o( h ).$

Equivalently, one has

$\displaystyle \sum_{X \leq x \leq 2X} |\sum_{x \leq n \leq x+h} \lambda(n)|^2 = o( h^2 X ). \ \ \ \ \ (4)$

A simple sieving argument (see Exercise 18 of Supplement 4) shows that one can replace ${\lambda}$ by the Möbius function ${\mu}$ and obtain the same conclusion. See this recent note of Matomaki and Radziwiłł for a simple proof of their (quantitative) main theorem in this special case.

Of course, (4) improves upon the trivial bound of ${O( h^2 X )}$. Prior to this paper, such estimates were only known (using arguments similar to those in Section 3 of Notes 6) for ${h \geq X^{1/6+\varepsilon}}$ unconditionally, or for ${h \geq \log^A X}$ for some sufficiently large ${A}$ if one assumed the Riemann hypothesis. This theorem also represents some progress towards Chowla’s conjecture (discussed in Supplement 4) that

$\displaystyle \sum_{n \leq x} \lambda(n+h_1) \dots \lambda(n+h_k) = o( x )$

as ${x \rightarrow \infty}$ for any fixed distinct ${h_1,\dots,h_k}$; indeed, it implies that this conjecture holds if one performs a small amount of averaging in the ${h_1,\dots,h_k}$.

Below the fold, we give a “cheap” version of the Matomaki-Radziwiłł argument. More precisely, we establish

Theorem 7 (Cheap Matomaki-Radziwiłł) Let ${X}$ be a parameter going to infinity, and let ${1 \leq T \leq X}$. Then

$\displaystyle \int_X^{X^A} \left|\sum_{x \leq n \leq e^{1/T} x} \frac{\lambda(n)}{n}\right|^2\frac{dx}{x} = o\left( \frac{\log X}{T^2} \right), \ \ \ \ \ (5)$

for any fixed ${A>1}$.

Note that (5) improves upon the trivial bound of ${O( \frac{\log X}{T^2} )}$. Again, one can replace ${\lambda}$ with ${\mu}$ if desired. Due to the cheapness of Theorem 7, the proof will require few ingredients; the deepest input is the improved zero-free region for the Riemann zeta function due to Vinogradov and Korobov. Other than that, the main tools are the Turan-Kubilius result established above, and some Fourier (or complex) analysis.

Analytic number theory is often concerned with the asymptotic behaviour of various arithmetic functions: functions ${f: {\bf N} \rightarrow {\bf R}}$ or ${f: {\bf N} \rightarrow {\bf C}}$ from the natural numbers ${{\bf N} = \{1,2,\dots\}}$ to the real numbers ${{\bf R}}$ or complex numbers ${{\bf C}}$. In this post, we will focus on the purely algebraic properties of these functions, and for reasons that will become clear later, it will be convenient to generalise the notion of an arithmetic function to functions ${f: {\bf N} \rightarrow R}$ taking values in some abstract commutative ring ${R}$. In this setting, we can add or multiply two arithmetic functions ${f,g: {\bf N} \rightarrow R}$ to obtain further arithmetic functions ${f+g, fg: {\bf N} \rightarrow R}$, and we can also form the Dirichlet convolution ${f*g: {\bf N} \rightarrow R}$ by the usual formula

$\displaystyle f*g(n) := \sum_{d|n} f(d) g(\frac{n}{d}).$

Regardless of what commutative ring ${R}$ is in used here, we observe that Dirichlet convolution is commutative, associative, and bilinear over ${R}$.

An important class of arithmetic functions in analytic number theory are the multiplicative functions, that is to say the arithmetic functions ${f: {\bf N} \rightarrow {\bf R}}$ such that ${f(1)=1}$ and

$\displaystyle f(nm) = f(n) f(m)$

for all coprime ${n,m \in {\bf N}}$. A subclass of these functions are the completely multiplicative functions, in which the restriction that ${n,m}$ be coprime is dropped. Basic examples of completely multiplicative functions (in the classical setting ${R={\bf C}}$) include

• the Kronecker delta ${\delta}$, defined by setting ${\delta(n)=1}$ for ${n=1}$ and ${\delta(n)=0}$ otherwise;
• the constant function ${1: n \mapsto 1}$ and the linear function ${n \mapsto n}$ (which by abuse of notation we denote by ${n}$);
• more generally monomials ${n \mapsto n^s}$ for any fixed complex number ${s}$ (in particular, the “Archimedean characters” ${n \mapsto n^{it}}$ for any fixed ${t \in {\bf R}}$), which by abuse of notation we denote by ${n^s}$;
• Dirichlet characters ${\chi}$;
• the Liouville function ${\lambda}$;
• the indicator function of the ${z}$smooth numbers (numbers whose prime factors are all at most ${z}$), for some given ${z}$; and
• the indicator function of the ${z}$rough numbers (numbers whose prime factors are all greater than ${z}$), for some given ${z}$.

Examples of multiplicative functions that are not completely multiplicative include

• the Möbius function ${\mu}$;
• the divisor function ${\tau}$ (also referred to as ${d}$);
• more generally, the higher order divisor functions ${\tau_k(n) = \sum_{d_1,\dots,d_k: d_1 \dots d_k = n} 1}$ for ${k \geq 1}$;
• the Euler totient function ${\phi}$;
• the number of roots ${n \mapsto \# \{ a \in {\bf Z}/n{\bf Z}: P(a) = 0\}}$ of a given polynomial ${P}$ defined over ${{\bf Z}}$;
• more generally, the point counting function ${n \mapsto V[{\bf Z}/n{\bf Z}]}$ of a given algebraic variety ${V}$ defined over ${{\bf Z}}$ (closely tied to the Hasse-Weil zeta function of ${V}$);
• the function ${r: n \mapsto r(n)}$ that counts the number of representations of ${n}$ as the sum of two squares;
• more generally, the function that maps a natural number ${n}$ to the number of ideals in a given number field ${K}$ of absolute norm ${n}$ (closely tied to the Dedekind zeta function of ${K}$).

These multiplicative functions interact well with the multiplication and convolution operations: if ${f,g: {\bf N} \rightarrow R}$ are multiplicative, then so are ${fg}$ and ${f * g}$, and if ${\psi}$ is completely multiplicative, then we also have

$\displaystyle \psi (f*g) = (\psi f) * (\psi g). \ \ \ \ \ (1)$

Finally, the product of completely multiplicative functions is again completely multiplicative. On the other hand, the sum of two multiplicative functions will never be multiplicative (just look at what happens at ${n=1}$), and the convolution of two completely multiplicative functions will usually just be multiplicative rather than completley multiplicative.

The specific multiplicative functions listed above are also related to each other by various important identities, for instance

$\displaystyle \delta * f = f; \quad \mu * 1 = \delta; \quad 1 * 1 = \tau; \quad \phi * 1 = n$

where ${f}$ is an arbitrary arithmetic function.

On the other hand, analytic number theory also is very interested in certain arithmetic functions that are not exactly multiplicative (and certainly not completely multiplicative). One particularly important such function is the von Mangoldt function ${\Lambda}$. This function is certainly not multiplicative, but is clearly closely related to such functions via such identities as ${\Lambda = \mu * L}$ and ${L = \Lambda * 1}$, where ${L: n\mapsto \log n}$ is the natural logarithm function. The purpose of this post is to point out that functions such as the von Mangoldt function lie in a class closely related to multiplicative functions, which I will call the derived multiplicative functions. More precisely:

Definition 1 A derived multiplicative function ${f: {\bf N} \rightarrow R}$ is an arithmetic function that can be expressed as the formal derivative

$\displaystyle f(n) = \frac{d}{d\varepsilon} F_\varepsilon(n) |_{\varepsilon=0}$

at the origin of a family ${f_\varepsilon: {\bf N}\rightarrow R}$ of multiplicative functions ${F_\varepsilon: {\bf N} \rightarrow R}$ parameterised by a formal parameter ${\varepsilon}$. Equivalently, ${f: {\bf N} \rightarrow R}$ is a derived multiplicative function if it is the ${\varepsilon}$ coefficient of a multiplicative function in the extension ${R[\varepsilon]/(\varepsilon^2)}$ of ${R}$ by a nilpotent infinitesimal ${\varepsilon}$; in other words, there exists an arithmetic function ${F: {\bf N} \rightarrow R}$ such that the arithmetic function ${F + \varepsilon f: {\bf N} \rightarrow R[\varepsilon]/(\varepsilon^2)}$ is multiplicative, or equivalently that ${F}$ is multiplicative and one has the Leibniz rule

$\displaystyle f(nm) = f(n) F(m) + F(n) f(m) \ \ \ \ \ (2)$

for all coprime ${n,m \in {\bf N}}$.

More generally, for any ${k\geq 0}$, a ${k}$-derived multiplicative function ${f: {\bf N} \rightarrow R}$ is an arithmetic function that can be expressed as the formal derivative

$\displaystyle f(n) = \frac{d^k}{d\varepsilon_1 \dots d\varepsilon_k} F_{\varepsilon_1,\dots,\varepsilon_k}(n) |_{\varepsilon_1,\dots,\varepsilon_k=0}$

at the origin of a family ${f_{\varepsilon_1,\dots,\varepsilon_k}: {\bf N} \rightarrow R}$ of multiplicative functions ${F_{\varepsilon_1,\dots,\varepsilon_k}: {\bf N} \rightarrow R}$ parameterised by formal parameters ${\varepsilon_1,\dots,\varepsilon_k}$. Equivalently, ${f}$ is the ${\varepsilon_1 \dots \varepsilon_k}$ coefficient of a multiplicative function in the extension ${R[\varepsilon_1,\dots,\varepsilon_k]/(\varepsilon_1^2,\dots,\varepsilon_k^2)}$ of ${R}$ by ${k}$ nilpotent infinitesimals ${\varepsilon_1,\dots,\varepsilon_k}$.

We define the notion of a ${k}$-derived completely multiplicative function similarly by replacing “multiplicative” with “completely multiplicative” in the above discussion.

There are Leibniz rules similar to (2) but they are harder to state; for instance, a doubly derived multiplicative function ${f: {\bf N} \rightarrow R}$ comes with singly derived multiplicative functions ${F_1, F_2: {\bf N} \rightarrow R}$ and a multiplicative function ${G: {\bf N} \rightarrow R}$ such that

$\displaystyle f(nm) = f(n) G(m) + F_1(n) F_2(m) + F_2(n) F_1(m) + G(n) f(m)$

for all coprime ${n,m \in {\bf N}}$.

One can then check that the von Mangoldt function ${\Lambda}$ is a derived multiplicative function, because ${\delta + \varepsilon \Lambda}$ is multiplicative in the ring ${{\bf C}[\varepsilon]/(\varepsilon^2)}$ with one infinitesimal ${\varepsilon}$. Similarly, the logarithm function ${L}$ is derived completely multiplicative because ${\exp( \varepsilon L ) := 1 + \varepsilon L}$ is completely multiplicative in ${{\bf C}[\varepsilon]/(\varepsilon^2)}$. More generally, any additive function ${\omega: {\bf N} \rightarrow R}$ is derived multiplicative because it is the top order coefficient of ${\exp(\varepsilon \omega) := 1 + \varepsilon \omega}$.

Remark 1 One can also phrase these concepts in terms of the formal Dirichlet series ${F(s) = \sum_n \frac{f(n)}{n^s}}$ associated to an arithmetic function ${f}$. A function ${f}$ is multiplicative if ${F}$ admits a (formal) Euler product; ${f}$ is derived multiplicative if ${F}$ is the (formal) first logarithmic derivative of an Euler product with respect to some parameter (not necessarily ${s}$, although this is certainly an option); and so forth.

Using the definition of a ${k}$-derived multiplicative function as the top order coefficient of a multiplicative function of a ring with ${k}$ infinitesimals, it is easy to see that the product or convolution of a ${k}$-derived multiplicative function ${f: {\bf N} \rightarrow R}$ and a ${l}$-derived multiplicative function ${g: {\bf N} \rightarrow R}$ is necessarily a ${k+l}$-derived multiplicative function (again taking values in ${R}$). Thus, for instance, the higher-order von Mangoldt functions ${\Lambda_k := \mu * L^k}$ are ${k}$-derived multiplicative functions, because ${L^k}$ is a ${k}$-derived completely multiplicative function. More explicitly, ${L^k}$ is the top order coeffiicent of the completely multiplicative function ${\prod_{i=1}^k \exp(\varepsilon_i L)}$, and ${\Lambda_k}$ is the top order coefficient of the multiplicative function ${\mu * \prod_{i=1}^k \exp(\varepsilon_i L)}$, with both functions taking values in the ring ${C[\varepsilon_1,\dots,\varepsilon_k]/(\varepsilon_1^2,\dots,\varepsilon_k^2)}$ of complex numbers with ${k}$ infinitesimals ${\varepsilon_1,\dots,\varepsilon_k}$ attached.

It then turns out that most (if not all) of the basic identities used by analytic number theorists concerning derived multiplicative functions, can in fact be viewed as coefficients of identities involving purely multiplicative functions, with the latter identities being provable primarily from multiplicative identities, such as (1). This phenomenon is analogous to the one in linear algebra discussed in this previous blog post, in which many of the trace identities used there are derivatives of determinant identities. For instance, the Leibniz rule

$\displaystyle L (f * g) = (Lf)*g + f*(Lg)$

for any arithmetic functions ${f,g}$ can be viewed as the top order term in

$\displaystyle \exp(\varepsilon L) (f*g) = (\exp(\varepsilon L) f) * (\exp(\varepsilon L) g)$

in the ring with one infinitesimal ${\varepsilon}$, and then we see that the Leibniz rule is a special case (or a derivative) of (1), since ${\exp(\varepsilon L)}$ is completely multiplicative. Similarly, the formulae

$\displaystyle \Lambda = \mu * L; \quad L = \Lambda * 1$

are top order terms of

$\displaystyle (\delta + \varepsilon \Lambda) = \mu * \exp(\varepsilon L); \quad \exp(\varepsilon L) = (\delta + \varepsilon \Lambda) * 1,$

and the variant formula ${\Lambda = - (L\mu) * 1}$ is the top order term of

$\displaystyle (\delta + \varepsilon \Lambda) = (\exp(-\varepsilon L)\mu) * 1,$

which can then be deduced from the previous identities by noting that the completely multiplicative function ${\exp(-\varepsilon L)}$ inverts ${\exp(\varepsilon L)}$ multiplicatively, and also noting that ${L}$ annihilates ${\mu*1=\delta}$. The Selberg symmetry formula

$\displaystyle \Lambda_2 = \Lambda*\Lambda + \Lambda L, \ \ \ \ \ (3)$

which plays a key role in the Erdös-Selberg elementary proof of the prime number theorem (as discussed in this previous blog post), is the top order term of the identity

$\displaystyle \delta + \varepsilon_1 \Lambda + \varepsilon_2 \Lambda + \varepsilon_1\varepsilon_2 \Lambda_2 = (\exp(\varepsilon_2 L) (\delta + \varepsilon_1 \Lambda)) * (\delta + \varepsilon_2 \Lambda)$

involving the multiplicative functions ${\delta + \varepsilon_1 \Lambda + \varepsilon_2 \Lambda + \varepsilon_1\varepsilon_2 \Lambda_2}$, ${\exp(\varepsilon_2 L)}$, ${\delta+\varepsilon_1 \Lambda}$, ${\delta+\varepsilon_2 \Lambda}$ with two infinitesimals ${\varepsilon_1,\varepsilon_2}$, and this identity can be proven while staying purely within the realm of multiplicative functions, by using the identities

$\displaystyle \delta + \varepsilon_1 \Lambda + \varepsilon_2 \Lambda + \varepsilon_1\varepsilon_2 \Lambda_2 = \mu * (\exp(\varepsilon_1 L) \exp(\varepsilon_2 L))$

$\displaystyle \exp(\varepsilon_1 L) = 1 * (\delta + \varepsilon_1 \Lambda)$

$\displaystyle \delta + \varepsilon_2 \Lambda = \mu * \exp(\varepsilon_2 L)$

and (1). Similarly for higher identities such as

$\displaystyle \Lambda_3 = \Lambda L^2 + 3 \Lambda L * \Lambda + \Lambda * \Lambda * \Lambda$

which arise from expanding out ${\mu * (\exp(\varepsilon_1 L) \exp(\varepsilon_2 L) \exp(\varepsilon_3 L))}$ using (1) and the above identities; we leave this as an exercise to the interested reader.

An analogous phenomenon arises for identities that are not purely multiplicative in nature due to the presence of truncations, such as the Vaughan identity

$\displaystyle \Lambda_{> V} = \mu_{\leq U} * L - \mu_{\leq U} * \Lambda_{\leq V} * 1 + \mu_{>U} * \Lambda_{>V} * 1 \ \ \ \ \ (4)$

for any ${U,V \geq 1}$, where ${f_{>V} = f 1_{>V}}$ is the restriction of a multiplicative function ${f}$ to the natural numbers greater than ${V}$, and similarly for ${f_{\leq V}}$, ${f_{>U}}$, ${f_{\leq U}}$. In this particular case, (4) is the top order coefficient of the identity

$\displaystyle (\delta + \varepsilon \Lambda)_{>V} = \mu_{\leq U} * \exp(\varepsilon L) - \mu_{\leq U} * (\delta + \varepsilon \Lambda)_{\leq V} * 1$

$\displaystyle + \mu_{>U} * (\delta+\varepsilon \Lambda)_{>V} * 1$

which can be easily derived from the identities ${\delta = \mu_{\leq U} * 1 + \mu_{>U} * 1}$ and ${\exp(\varepsilon L) = (\delta + \varepsilon \Lambda)_{>V} * 1 + (\delta + \varepsilon \Lambda)_{\leq V} + 1}$. Similarly for the Heath-Brown identity

$\displaystyle \Lambda = \sum_{j=1}^K (-1)^{j-1} \binom{K}{j} \mu_{\leq U}^{*j} * 1^{*j-1} * L \ \ \ \ \ (5)$

valid for natural numbers up to ${U^K}$, where ${U \geq 1}$ and ${K \geq 1}$ are arbitrary parameters and ${f^{*j}}$ denotes the ${j}$-fold convolution of ${f}$, and discussed in this previous blog post; this is the top order coefficient of

$\displaystyle \delta + \varepsilon \Lambda = \sum_{j=1}^K (-1)^{j-1} \binom{K}{j} \mu_{\leq U}^{*j} * 1^{*j-1} * \exp( \varepsilon L )$

and arises by first observing that

$\displaystyle (\mu - \mu_{\leq U})^{*K} * 1^{*K-1} * \exp(\varepsilon L) = \mu_{>U}^{*K} * 1^{*K-1} * \exp( \varepsilon L )$

vanishes up to ${U^K}$, and then expanding the left-hand side using the binomial formula and the identity ${\mu^{*K} * 1^{*K-1} * \exp(\varepsilon L) = \delta + \varepsilon \Lambda}$.

One consequence of this phenomenon is that identities involving derived multiplicative functions tend to have a dimensional consistency property: all terms in the identity have the same order of derivation in them. For instance, all the terms in the Selberg symmetry formula (3) are doubly derived functions, all the terms in the Vaughan identity (4) or the Heath-Brown identity (5) are singly derived functions, and so forth. One can then use dimensional analysis to help ensure that one has written down a key identity involving such functions correctly, much as is done in physics.

In addition to the dimensional analysis arising from the order of derivation, there is another dimensional analysis coming from the value of multiplicative functions at primes ${p}$ (which is more or less equivalent to the order of pole of the Dirichlet series at ${s=1}$). Let us say that a multiplicative function ${f: {\bf N} \rightarrow R}$ has a pole of order ${j}$ if one has ${f(p)=j}$ on the average for primes ${p}$, where we will be a bit vague as to what “on the average” means as it usually does not matter in applications. Thus for instance, ${1}$ or ${\exp(\varepsilon L)}$ has a pole of order ${1}$ (a simple pole), ${\delta}$ or ${\delta + \varepsilon \Lambda}$ has a pole of order ${0}$ (i.e. neither a zero or a pole), Dirichlet characters also have a pole of order ${0}$ (although this is slightly nontrivial, requiring Dirichlet’s theorem), ${\mu}$ has a pole of order ${-1}$ (a simple zero), ${\tau}$ has a pole of order ${2}$, and so forth. Note that the convolution of a multiplicative function with a pole of order ${j}$ with a multiplicative function with a pole of order ${j'}$ will be a multiplicative function with a pole of order ${j+j'}$. If there is no oscillation in the primes ${p}$ (e.g. if ${f(p)=j}$ for all primes ${p}$, rather than on the average), it is also true that the product of a multiplicative function with a pole of order ${j}$ with a multiplicative function with a pole of order ${j'}$ will be a multiplicative function with a pole of order ${jj'}$. The situation is significantly different though in the presence of oscillation; for instance, if ${\chi}$ is a quadratic character then ${\chi^2}$ has a pole of order ${1}$ even though ${\chi}$ has a pole of order ${0}$.

A ${k}$-derived multiplicative function will then be said to have an underived pole of order ${j}$ if it is the top order coefficient of a multiplicative function with a pole of order ${j}$; in terms of Dirichlet series, this roughly means that the Dirichlet series has a pole of order ${j+k}$ at ${s=1}$. For instance, the singly derived multiplicative function ${\Lambda}$ has an underived pole of order ${0}$, because it is the top order coefficient of ${\delta + \varepsilon \Lambda}$, which has a pole of order ${0}$; similarly ${L}$ has an underived pole of order ${1}$, being the top order coefficient of ${\exp(\varepsilon L)}$. More generally, ${\Lambda_k}$ and ${L^k}$ have underived poles of order ${0}$ and ${1}$ respectively for any ${k}$.

By taking top order coefficients, we then see that the convolution of a ${k}$-derived multiplicative function with underived pole of order ${j}$ and a ${k'}$-derived multiplicative function with underived pole of order ${j'}$ is a ${k+k'}$-derived multiplicative function with underived pole of order ${j+j'}$. If there is no oscillation in the primes, the product of these functions will similarly have an underived pole of order ${jj'}$, for instance ${\Lambda L}$ has an underived pole of order ${0}$. We then have the dimensional consistency property that in any of the standard identities involving derived multiplicative functions, all terms not only have the same derived order, but also the same underived pole order. For instance, in (3), (4), (5) all terms have underived pole order ${0}$ (with any Mobius function terms being counterbalanced by a matching term of ${1}$ or ${L}$). This gives a second way to use dimensional analysis as a consistency check. For instance, any identity that involves a linear combination of ${\mu_{\leq U} * L}$ and ${\Lambda_{>V} * 1}$ is suspect because the underived pole orders do not match (being ${0}$ and ${1}$ respectively), even though the derived orders match (both are ${1}$).

One caveat, though: this latter dimensional consistency breaks down for identities that involve infinitely many terms, such as Linnik’s identity

$\displaystyle \Lambda = \sum_{i=0}^\infty (-1)^{i} L * 1_{>1}^{*i}.$

In this case, one can still rewrite things in terms of multiplicative functions as

$\displaystyle \delta + \varepsilon \Lambda = \sum_{i=0}^\infty (-1)^i \exp(\varepsilon L) * 1_{>1}^{*i},$

so the former dimensional consistency is still maintained.

I thank Andrew Granville, Kannan Soundararajan, and Emmanuel Kowalski for helpful conversations on these topics.

One of the basic problems in analytic number theory is to obtain bounds and asymptotics for sums of the form

$\displaystyle \sum_{n \leq x} f(n)$

in the limit ${x \rightarrow \infty}$, where ${n}$ ranges over natural numbers less than ${x}$, and ${f: {\bf N} \rightarrow {\bf C}}$ is some arithmetic function of number-theoretic interest. (It is also often convenient to replace this sharply truncated sum with a smoother sum such as ${\sum_n f(n) \psi(n/x)}$, but we will not discuss this technicality here.) For instance, the prime number theorem is equivalent to the assertion

$\displaystyle \sum_{n \leq x} \Lambda(n) = x + o(x)$

where ${\Lambda}$ is the von Mangoldt function, while the Riemann hypothesis is equivalent to the stronger assertion

$\displaystyle \sum_{n \leq x} \Lambda(n) = x + O(x^{1/2+o(1)}).$

It is thus of interest to develop techniques to estimate such sums ${\sum_{n \leq x} f(n)}$. Of course, the difficulty of this task depends on how “nice” the function ${f}$ is. The functions ${f}$ that come up in number theory lie on a broad spectrum of “niceness”, with some particularly nice functions being quite easy to sum, and some being insanely difficult.

At the easiest end of the spectrum are those functions ${f}$ that exhibit some sort of regularity or “smoothness”. Examples of smoothness include “Archimedean” smoothness, in which ${f(n)}$ is the restriction of some smooth function ${f: {\bf R} \rightarrow {\bf C}}$ from the reals to the natural numbers, and the derivatives of ${f}$ are well controlled. A typical example is

$\displaystyle \sum_{n \leq x} \log n.$

One can already get quite good bounds on this quantity by comparison with the integral ${\int_1^x \log t\ dt}$, namely

$\displaystyle \sum_{n \leq x} \log n = x \log x - x + O(\log x),$

with sharper bounds available by using tools such as the Euler-Maclaurin formula (see this blog post). Exponentiating such asymptotics, incidentally, leads to one of the standard proofs of Stirling’s formula (as discussed in this blog post).

One can also consider “non-Archimedean” notions of smoothness, such as periodicity relative to a small period ${q}$. Indeed, if ${f}$ is periodic with period ${q}$ (and is thus essentially a function on the cyclic group ${{\bf Z}/q{\bf Z}}$), then one has the easy bound

$\displaystyle \sum_{n \leq x} f(n) = \frac{x}{q} \sum_{n \in {\bf Z}/q{\bf Z}} f(n) + O( \sum_{n \in {\bf Z}/q{\bf Z}} |f(n)| ).$

In particular, we have the fundamental estimate

$\displaystyle \sum_{n \leq x: q|n} 1 = \frac{x}{q} + O(1). \ \ \ \ \ (1)$

This is a good estimate when ${q}$ is much smaller than ${x}$, but as ${q}$ approaches ${x}$ in magnitude, the error term ${O(1)}$ begins to overwhelm the main term ${\frac{x}{q}}$, and one needs much more delicate information on the fractional part of ${\frac{x}{q}}$ in order to obtain good estimates at this point.

One can also consider functions ${f}$ which combine “Archimedean” and “non-Archimedean” smoothness into an “adelic” smoothness. We will not define this term precisely here (though the concept of a Schwartz-Bruhat function is one way to capture this sort of concept), but a typical example might be

$\displaystyle \sum_{n \leq x} \chi(n) \log n$

where ${\chi}$ is periodic with some small period ${q}$. By using techniques such as summation by parts, one can estimate such sums using the techniques used to estimate sums of periodic functions or functions with (Archimedean) smoothness.

Another class of functions that is reasonably well controlled are the multiplicative functions, in which ${f(nm) = f(n) f(m)}$ whenever ${n,m}$ are coprime. Here, one can use the powerful techniques of multiplicative number theory, for instance by working with the Dirichlet series

$\displaystyle \sum_{n=1}^\infty \frac{f(n)}{n^s}$

which are clearly related to the partial sums ${\sum_{n \leq x} f(n)}$ (essentially via the Mellin transform, a cousin of the Fourier and Laplace transforms); for this post we ignore the (important) issue of how to make sense of this series when it is not absolutely convergent (but see this previous blog post for more discussion). A primary reason that this technique is effective is that the Dirichlet series of a multiplicative function factorises as an Euler product

$\displaystyle \sum_{n=1}^\infty \frac{f(n)}{n^s} = \prod_p (\sum_{j=0}^\infty \frac{f(p^j)}{p^{js}}).$

One also obtains similar types of representations for functions that are not quite multiplicative, but are closely related to multiplicative functions, such as the von Mangoldt function ${\Lambda}$ (whose Dirichlet series ${\sum_{n=1}^\infty \frac{\Lambda(n)}{n^s} = -\frac{\zeta'(s)}{\zeta(s)}}$ is not given by an Euler product, but instead by the logarithmic derivative of an Euler product).

Moving another notch along the spectrum between well-controlled and ill-controlled functions, one can consider functions ${f}$ that are divisor sums such as

$\displaystyle f(n) = \sum_{d \leq R; d|n} g(d) = \sum_{d \leq R} 1_{d|n} g(d)$

for some other arithmetic function ${g}$, and some level ${R}$. This is a linear combination of periodic functions ${1_{d|n} g(d)}$ and is thus technically periodic in ${n}$ (with period equal to the least common multiple of all the numbers from ${1}$ to ${R}$), but in practice this periodic is far too large to be useful (except for extremely small levels ${R}$, e.g. ${R = O(\log x)}$). Nevertheless, we can still control the sum ${\sum_{n \leq x} f(n)}$ simply by rearranging the summation:

$\displaystyle \sum_{n \leq x} f(n) = \sum_{d \leq R} g(d) \sum_{n \leq x: d|n} 1$

and thus by (1) one can bound this by the sum of a main term ${x \sum_{d \leq R} \frac{g(d)}{d}}$ and an error term ${O( \sum_{d \leq R} |g(d)| )}$. As long as the level ${R}$ is significantly less than ${x}$, one may expect the main term to dominate, and one can often estimate this term by a variety of techniques (for instance, if ${g}$ is multiplicative, then multiplicative number theory techniques are quite effective, as mentioned previously). Similarly for other slight variants of divisor sums, such as expressions of the form

$\displaystyle \sum_{d \leq R; d | n} g(d) \log \frac{n}{d}$

or expressions of the form

$\displaystyle \sum_{d \leq R} F_d(n)$

where each ${F_d}$ is periodic with period ${d}$.

One of the simplest examples of this comes when estimating the divisor function

$\displaystyle \tau(n) := \sum_{d|n} 1,$

which counts the number of divisors up to ${n}$. This is a multiplicative function, and is therefore most efficiently estimated using the techniques of multiplicative number theory; but for reasons that will become clearer later, let us “forget” the multiplicative structure and estimate the above sum by more elementary methods. By applying the preceding method, we see that

$\displaystyle \sum_{n \leq x} \tau(n) = \sum_{d \leq x} \sum_{n \leq x:d|n} 1$

$\displaystyle = \sum_{d \leq x} (\frac{x}{d} + O(1))$

$\displaystyle = x \log x + O(x). \ \ \ \ \ (2)$

Here, we are (barely) able to keep the error term smaller than the main term; this is right at the edge of the divisor sum method, because the level ${R}$ in this case is equal to ${x}$. Unfortunately, at this high choice of level, it is not always possible to always keep the error term under control like this. For instance, if one wishes to use the standard divisor sum representation

$\displaystyle \Lambda(n) = \sum_{d|n} \mu(d) \log \frac{n}{d},$

where ${\mu}$ is the Möbius function, to compute ${\sum_{n \leq x} \Lambda(n)}$, then one ends up looking at

$\displaystyle \sum_{n \leq x} \Lambda(n) = \sum_{d \leq x} \mu(d) \sum_{n \leq x:d|n} \log \frac{n}{d}$

$\displaystyle = \sum_{d \leq x} \mu(d) ( \frac{n}{d} \log \frac{n}{d} - \frac{n}{d} + O(\log \frac{n}{d}) )$

From Dirichlet series methods, it is not difficult to establish the identities

$\displaystyle \lim_{s\rightarrow 1^+} \sum_{n=1}^\infty \frac{\mu(n)}{n^s} = 0$

and

$\displaystyle \lim_{s \rightarrow 1^+} \sum_{n=1}^\infty \frac{\mu(n) \log n}{n^s} = -1.$

This suggests (but does not quite prove) that one has

$\displaystyle \sum_{n=1}^\infty \frac{\mu(n)}{n} = 0 \ \ \ \ \ (3)$

and

$\displaystyle \sum_{n=1}^\infty \frac{\mu(n)\log n}{n} = -1 \ \ \ \ \ (4)$

in the sense of conditionally convergent series. Assuming one can justify this (which, ultimately, requires one to exclude zeroes of the Riemann zeta function on the line ${\hbox{Re}(s)=1}$, as discussed in this previous post), one is eventually left with the estimate ${x + O(x)}$, which is useless as a lower bound (and recovers only the classical Chebyshev estimate ${\sum_{n \leq x} \Lambda(n) \ll x}$ as the upper bound). The inefficiency here when compared to the situation with the divisor function ${\tau}$ can be attributed to the signed nature of the Möbius function ${\mu(n)}$, which causes some cancellation in the divisor sum expansion that needs to be compensated for with improved estimates.

However, there are a number of tricks available to reduce the level of divisor sums. The simplest comes from exploiting the change of variables ${d \mapsto \frac{n}{d}}$, which can in principle reduce the level by a square root. For instance, when computing the divisor function ${\tau(n) = \sum_{d|n} 1}$, one can observe using this change of variables that every divisor of ${n}$ above ${\sqrt{n}}$ is paired with one below ${\sqrt{n}}$, and so we have

$\displaystyle \tau(n) = 2 \sum_{d \leq \sqrt{n}: d|n} 1 \ \ \ \ \ (5)$

except when ${n}$ is a perfect square, in which case one must subtract one from the right-hand side. Using this reduced-level divisor sum representation, one can obtain an improvement to (2), namely

$\displaystyle \sum_{n \leq x} \tau(n) = x \log x + (2\gamma-1) x + O(\sqrt{x}).$

This type of argument is also known as the Dirichlet hyperbola method. A variant of this argument can also deduce the prime number theorem from (3), (4) (and with some additional effort, one can even drop the use of (4)); this is discussed at this previous blog post.

Using this square root trick, one can now also control divisor sums such as

$\displaystyle \sum_{n \leq x} \tau(n^2+1).$

(Note that ${\tau(n^2+1)}$ has no multiplicativity properties in ${n}$, and so multiplicative number theory techniques cannot be directly applied here.) The level of the divisor sum here is initially of order ${x^2}$, which is too large to be useful; but using the square root trick, we can expand this expression as

$\displaystyle 2 \sum_{n \leq x} \sum_{d \leq n: d | n^2+1} 1$

which one can rewrite as

$\displaystyle 2 \sum_{d \leq x} \sum_{d \leq n \leq x: n^2+1 = 0 \hbox{ mod } d} 1.$

The constraint ${n^2+1=0 \hbox{ mod } d}$ is periodic in ${n}$ with period ${d}$, so we can write this as

$\displaystyle 2 \sum_{d \leq x} ( \frac{x}{d} \rho(d) + O(\rho(d)) )$

where ${\rho(d)}$ is the number of solutions in ${{\bf Z}/d{\bf Z}}$ to the equation ${n^2+1 = 0 \hbox{ mod } d}$, and so

$\displaystyle \sum_{n \leq x} \tau(n^2+1) = 2x \sum_{d \leq x} \frac{\rho(d)}{d} + O(\sum_{d \leq x} \rho(d)).$

The function ${\rho}$ is multiplicative, and can be easily computed at primes ${p}$ and prime powers ${p^j}$ using tools such as quadratic reciprocity and Hensel’s lemma. For instance, by Fermat’s two-square theorem, ${\rho(p)}$ is equal to ${2}$ for ${p=1 \hbox{ mod } 4}$ and ${0}$ for ${p=3 \hbox{ mod } 4}$. From this and standard multiplicative number theory methods (e.g. by obtaining asymptotics on the Dirichlet series ${\sum_d \frac{\rho(d)}{d^s}}$), one eventually obtains the asymptotic

$\displaystyle \sum_{d \leq x} \frac{\rho(d)}{d} = \frac{3}{2\pi} \log x + O(1)$

and also

$\displaystyle \sum_{d \leq x} \rho(d) = O(x)$

and thus

$\displaystyle \sum_{n \leq x} \tau(n^2+1) = \frac{3}{\pi} x \log x + O(x).$

Similar arguments give asymptotics for ${\tau}$ on other quadratic polynomials; see for instance this paper of Hooley and these papers by McKee. Note that the irreducibility of the polynomial will be important. If one considers instead a sum involving a reducible polynomial, such as ${\sum_{n \leq x} \tau(n^2-1)}$, then the analogous quantity ${\rho(n)}$ becomes significantly larger, leading to a larger growth rate (of order ${x \log^2 x}$ rather than ${x\log x}$) for the sum.

However, the square root trick is insufficient by itself to deal with higher order sums involving the divisor function, such as

$\displaystyle \sum_{n \leq x} \tau(n^3+1);$

the level here is initially of order ${x^3}$, and the square root trick only lowers this to about ${x^{3/2}}$, creating an error term that overwhelms the main term. And indeed, the asymptotic for such this sum has not yet been rigorously established (although if one heuristically drops error terms, one can arrive at a reasonable conjecture for this asymptotic), although some results are known if one averages over additional parameters (see e.g. this paper of Greaves, or this paper of Matthiesen).

Nevertheless, there is an ingenious argument of Erdös that allows one to obtain good upper and lower bounds for these sorts of sums, in particular establishing the asymptotic

$\displaystyle x \log x \ll \sum_{n \leq x} \tau(P(n)) \ll x \log x \ \ \ \ \ (6)$

for any fixed irreducible non-constant polynomial ${P}$ that maps ${{\bf N}}$ to ${{\bf N}}$ (with the implied constants depending of course on the choice of ${P}$). There is also the related moment bound

$\displaystyle \sum_{n \leq x} \tau^m(P(n)) \ll x \log^{O(1)} x \ \ \ \ \ (7)$

for any fixed ${P}$ (not necessarily irreducible) and any fixed ${m \geq 1}$, due to van der Corput; this bound is in fact used to dispose of some error terms in the proof of (6). These should be compared with what one can obtain from the divisor bound ${\tau(n) \ll n^{O(1/\log \log n)}}$ and the trivial bound ${\tau(n) \geq 1}$, giving the bounds

$\displaystyle x \ll \sum_{n \leq x} \tau^m(P(n)) \ll x^{1 + O(\frac{1}{\log \log x})}$

for any fixed ${m \geq 1}$.

The lower bound in (6) is easy, since one can simply lower the level in (5) to obtain the lower bound

$\displaystyle \tau(n) \geq \sum_{d \leq n^\theta: d|n} 1$

for any ${\theta>0}$, and the preceding methods then easily allow one to obtain the lower bound by taking ${\theta}$ small enough (more precisely, if ${P}$ has degree ${d}$, one should take ${\theta}$ equal to ${1/d}$ or less). The upper bounds in (6) and (7) are more difficult. Ideally, if we could obtain upper bounds of the form

$\displaystyle \tau(n) \ll \sum_{d \leq n^\theta: d|n} 1 \ \ \ \ \ (8)$

for any fixed ${\theta > 0}$, then the preceding methods would easily establish both results. Unfortunately, this bound can fail, as illustrated by the following example. Suppose that ${n}$ is the product of ${k}$ distinct primes ${p_1 \ldots p_k}$, each of which is close to ${n^{1/k}}$. Then ${n}$ has ${2^k}$ divisors, with ${\binom{n}{j}}$ of them close to ${n^{j/k}}$ for each ${0 \ldots j \leq k}$. One can think of (the logarithms of) these divisors as being distributed according to what is essentially a Bernoulli distribution, thus a randomly selected divisor of ${n}$ has magnitude about ${n^{j/k}}$, where ${j}$ is a random variable which has the same distribution as the number of heads in ${k}$ independently tossed fair coins. By the law of large numbers, ${j}$ should concentrate near ${k/2}$ when ${k}$ is large, which implies that the majority of the divisors of ${n}$ will be close to ${n^{1/2}}$. Sending ${k \rightarrow \infty}$, one can show that the bound (8) fails whenever ${\theta < 1/2}$.

This however can be fixed in a number of ways. First of all, even when ${\theta<1/2}$, one can show weaker substitutes for (8). For instance, for any fixed ${\theta > 0}$ and ${m \geq 1}$ one can show a bound of the form

$\displaystyle \tau(n)^m \ll \sum_{d \leq n^\theta: d|n} \tau(d)^C \ \ \ \ \ (9)$

for some ${C}$ depending only on ${m,\theta}$. This nice elementary inequality (first observed by Landreau) already gives a quite short proof of van der Corput’s bound (7).

For Erdös’s upper bound (6), though, one cannot afford to lose these additional factors of ${\tau(d)}$, and one must argue more carefully. Here, the key observation is that the counterexample discussed earlier – when the natural number ${n}$ is the product of a large number of fairly small primes – is quite atypical; most numbers have at least one large prime factor. For instance, the number of natural numbers less than ${x}$ that contain a prime factor between ${x^{1/2}}$ and ${x}$ is equal to

$\displaystyle \sum_{x^{1/2} \leq p \leq x} (\frac{x}{p} + O(1)),$

which, thanks to Mertens’ theorem

$\displaystyle \sum_{p \leq x} \frac{1}{p} = \log\log x + M+o(1)$

for some absolute constant ${M}$, is comparable to ${x}$. In a similar spirit, one can show by similarly elementary means that the number of natural numbers ${m}$ less than ${x}$ that are ${x^{1/m}}$-smooth, in the sense that all prime factors are at most ${x^{1/m}}$, is only about ${m^{-cm} x}$ or so. Because of this, one can hope that the bound (8), while not true in full generality, will still be true for most natural numbers ${n}$, with some slightly weaker substitute available (such as (7)) for the exceptional numbers ${n}$. This turns out to be the case by an elementary but careful argument.

The Erdös argument is quite robust; for instance, the more general inequality

$\displaystyle x \log^{2^m-1} x \ll \sum_{n \leq x} \tau(P(n))^m \ll x \log^{2^m-1} x$

for fixed irreducible ${P}$ and ${m \geq 1}$, which improves van der Corput’s inequality (8) was shown by Delmer using the same methods. (A slight error in the original paper of Erdös was also corrected in this latter paper.) In a forthcoming revision to my paper on the Erdös-Straus conjecture, Christian Elsholtz and I have also applied this method to obtain bounds such as

$\displaystyle \sum_{a \leq A} \sum_{b \leq B} \tau(a^2 b + 1) \ll AB \log(A+B),$

which turn out to be enough to obtain the right asymptotics for the number of solutions to the equation ${\frac{4}{p}= \frac{1}{x}+\frac{1}{y}+\frac{1}{z}}$.

Below the fold I will provide some more details of the arguments of Landreau and of Erdös.

Given a positive integer $n$, let $d(n)$ denote the number of divisors of n (including 1 and n), thus for instance d(6)=4, and more generally, if n has a prime factorisation

$n = p_1^{a_1} \ldots p_k^{a_k}$ (1)

then (by the fundamental theorem of arithmetic)

$d(n) = (a_1+1) \ldots (a_k+1)$. (2)

Clearly, $d(n) \leq n$.  The divisor bound asserts that, as $n$ gets large, one can improve this trivial bound to

$d(n) \leq C_\varepsilon n^\varepsilon$ (3)

for any $\varepsilon > 0$, where $C_\varepsilon$ depends only on $\varepsilon$; equivalently, in asymptotic notation one has $d(n) = n^{o(1)}$.  In fact one has a more precise bound

$\displaystyle d(n) \leq n^{O( 1/ \log \log n)} = \exp( O( \frac{\log n}{\log \log n} ) )$. (4)

The divisor bound is useful in many applications in number theory, harmonic analysis, and even PDE (on periodic domains); it asserts that for any large number n, only a “logarithmically small” set of numbers less than n will actually divide n exactly, even in the worst-case scenario when n is smooth.  (The average value of d(n) is much smaller, being about $\log n$ on the average, as can be seen easily from the double counting identity

$\sum_{n \leq N} d(n) = \# \{ (m,l) \in {\Bbb N} \times {\Bbb N}: ml \leq N \} = \sum_{m=1}^N \lfloor \frac{N}{m}\rfloor \sim N \log N$,

or from the heuristic that a randomly chosen number m less than n has a probability about 1/m of dividing n, and $\sum_{m.  However, (4) is the correct “worst case” bound, as I discuss below.)

The divisor bound is elementary to prove (and not particularly difficult), and I was asked about it recently, so I thought I would provide the proof here, as it serves as a case study in how to establish worst-case estimates in elementary multiplicative number theory.

[Update, Sep 24: some applications added.]