One of the basic problems in analytic number theory is to obtain bounds and asymptotics for sums of the form
in the limit , where
ranges over natural numbers less than
, and
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
, but we will not discuss this technicality here.) For instance, the prime number theorem is equivalent to the assertion
where is the von Mangoldt function, while the Riemann hypothesis is equivalent to the stronger assertion
It is thus of interest to develop techniques to estimate such sums . Of course, the difficulty of this task depends on how “nice” the function
is. The functions
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 that exhibit some sort of regularity or “smoothness”. Examples of smoothness include “Archimedean” smoothness, in which
is the restriction of some smooth function
from the reals to the natural numbers, and the derivatives of
are well controlled. A typical example is
One can already get quite good bounds on this quantity by comparison with the integral , namely
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 . Indeed, if
is periodic with period
(and is thus essentially a function on the cyclic group
), then one has the easy bound
In particular, we have the fundamental estimate
This is a good estimate when is much smaller than
, but as
approaches
in magnitude, the error term
begins to overwhelm the main term
, and one needs much more delicate information on the fractional part of
in order to obtain good estimates at this point.
One can also consider functions 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
where is periodic with some small period
. 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 whenever
are coprime. Here, one can use the powerful techniques of multiplicative number theory, for instance by working with the Dirichlet series
which are clearly related to the partial sums (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
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 (whose Dirichlet series
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 that are divisor sums such as
for some other arithmetic function , and some level
. This is a linear combination of periodic functions
and is thus technically periodic in
(with period equal to the least common multiple of all the numbers from
to
), but in practice this periodic is far too large to be useful (except for extremely small levels
, e.g.
). Nevertheless, we can still control the sum
simply by rearranging the summation:
and thus by (1) one can bound this by the sum of a main term and an error term
. As long as the level
is significantly less than
, one may expect the main term to dominate, and one can often estimate this term by a variety of techniques (for instance, if
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
or expressions of the form
where each is periodic with period
.
One of the simplest examples of this comes when estimating the divisor function
which counts the number of divisors up to . 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
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 in this case is equal to
. 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
where is the Möbius function, to compute
, then one ends up looking at
From Dirichlet series methods, it is not difficult to establish the identities
and
This suggests (but does not quite prove) that one has
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 , as discussed in this previous post), one is eventually left with the estimate
, which is useless as a lower bound (and recovers only the classical Chebyshev estimate
as the upper bound). The inefficiency here when compared to the situation with the divisor function
can be attributed to the signed nature of the Möbius function
, 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 , which can in principle reduce the level by a square root. For instance, when computing the divisor function
, one can observe using this change of variables that every divisor of
above
is paired with one below
, and so we have
except when 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
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
(Note that has no multiplicativity properties in
, and so multiplicative number theory techniques cannot be directly applied here.) The level of the divisor sum here is initially of order
, which is too large to be useful; but using the square root trick, we can expand this expression as
which one can rewrite as
The constraint is periodic in
with period
, so we can write this as
where is the number of solutions in
to the equation
, and so
The function is multiplicative, and can be easily computed at primes
and prime powers
using tools such as quadratic reciprocity and Hensel’s lemma. For instance, by Fermat’s two-square theorem,
is equal to
for
and
for
. From this and standard multiplicative number theory methods (e.g. by obtaining asymptotics on the Dirichlet series
), one eventually obtains the asymptotic
and also
and thus
Similar arguments give asymptotics for 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
, then the analogous quantity
becomes significantly larger, leading to a larger growth rate (of order
rather than
) for the sum.
However, the square root trick is insufficient by itself to deal with higher order sums involving the divisor function, such as
the level here is initially of order , and the square root trick only lowers this to about
, 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
for any fixed irreducible non-constant polynomial that maps
to
(with the implied constants depending of course on the choice of
). There is also the related moment bound
for any fixed (not necessarily irreducible) and any fixed
, 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
and the trivial bound
, giving the bounds
for any fixed .
The lower bound in (6) is easy, since one can simply lower the level in (5) to obtain the lower bound
for any , and the preceding methods then easily allow one to obtain the lower bound by taking
small enough (more precisely, if
has degree
, one should take
equal to
or less). The upper bounds in (6) and (7) are more difficult. Ideally, if we could obtain upper bounds of the form
for any fixed , then the preceding methods would easily establish both results. Unfortunately, this bound can fail, as illustrated by the following example. Suppose that
is the product of
distinct primes
, each of which is close to
. Then
has
divisors, with
of them close to
for each
. 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
has magnitude about
, where
is a random variable which has the same distribution as the number of heads in
independently tossed fair coins. By the law of large numbers,
should concentrate near
when
is large, which implies that the majority of the divisors of
will be close to
. Sending
, one can show that the bound (8) fails whenever
.
This however can be fixed in a number of ways. First of all, even when , one can show weaker substitutes for (8). For instance, for any fixed
and
one can show a bound of the form
for some depending only on
. 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 , and one must argue more carefully. Here, the key observation is that the counterexample discussed earlier – when the natural number
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
that contain a prime factor between
and
is equal to
which, thanks to Mertens’ theorem
for some absolute constant , is comparable to
. In a similar spirit, one can show by similarly elementary means that the number of natural numbers
less than
that are
-smooth, in the sense that all prime factors are at most
, is only about
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
, with some slightly weaker substitute available (such as (7)) for the exceptional numbers
. 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
for fixed irreducible and
, 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
which turn out to be enough to obtain the right asymptotics for the number of solutions to the equation .
Below the fold I will provide some more details of the arguments of Landreau and of Erdös.
— 1. Landreau’s argument —
We now prove (9), and use this to show (7).
Suppose first that all prime factors of have magnitude at most
. Then by a greedy algorithm, we can factorise
as the product
of numbers between
and
. In particular, the number
of terms in this factorisation is at most
. By the trivial inequality
we have
and thus by the pigeonhole principle one has
for some . Since
is a factor of
that is at most
, the claim follows in this case (taking
).
Now we consider the general case, in which may contain prime factors that exceed
. There are at most
such factors (counting multiplicity). Extracting these factors out first and then running the greedy algorithm again, we may factorise
where the
are as before, and
is the product of at most
primes. In particular,
and thus
One now argues as before (conceding a factor of , which is acceptable) to obtain (9) in full generality. (Note that this illustrates a useful principle, which is that large prime factors of
are essentially harmless for the purposes of upper bounding
.)
Now we prove (7). From (9) we have
for any , and hence we can bound
by
The inner sum is , where
is the number of roots of
. Now, for fixed
, it is easy to see that
for all primes
, and from Hensel’s lemma one soon extends this to
for all prime powers
. (This is easy when
does not divide the discriminant
of
, as the zeroes of
are then simple. There are only finitely many primes that do divide the discriminant, and they can each be handled separately by Hensel’s lemma and an induction on the degree of
.) Meanwhile, from the Chinese remainder theorem,
is multiplicative. From this we obtain the crude bound
, and so we obtain a bound
This sum can easily be bounded by by multiplicative number theory techniques, e.g. by first computing the Dirichlet series
via the Euler product. This proves (7).
— 2. Erdös’ argument —
Now we prove (6). We focus on the upper bound, as the proof of the lower bound has already been sketched.
We first make a convenient observation: from (7) (with ) and the Cauchy-Schwarz inequality, we see that we have
whenever is a subset of the natural numbers less than
of cardinality
for some sufficiently large
. Thus we have the freedom to restrict attention to “generic”
, where by “generic” we mean “lying outside of an exceptional set of cardinality
for the
specified above”.
Let us now look at the behaviour of for generic
. We first control the total number of prime factors:
This result is consistent with the Hardy-Ramanujan and Erdös-Kac theorems, though it does not quite follow from these results (because lives in quite a sparse set of natural numbers).
Proof: If has more than
prime factors for some
, then
has at least
divisors, thus
. The claim then follows from (7) (with
) and Markov’s inequality, taking
large enough.
Next, we try to prevent repeated prime factors:
Lemma 2 For generic
, the prime factors of
between
and
are all distinct.
Proof: If is a prime between
and
, then the total number of
for which
divides
is
so the total number of that fail the above property is
which is acceptable.
It is difficult to increase the upper bound here beyond , but fortunately we will not need to go above this bound. The lower bound cannot be significantly reduced; for instance, it is quite likely that
will be divisible by
for a positive fraction of
. But we have the following substitute:
Lemma 3 For generic
, there are no prime powers
dividing
with
and
.
Proof: By the preceding lemma, we can restrict attention to primes with
. For each such
, let
be the first power of
exceeding
. Arguing as before, the total number of
for which
divides
is
on the other hand, there are at most primes
to consider. The claim then follows from the union bound.
We now have enough information on the prime factorisation of to proceed. We arrange the prime factors of
in increasing order (allowing repetitions):
Let be the largest integer for which
. Suppose first that
, then as in the previous section we would have
which is an estimate of the form (8), and thus presumably advantageous.
Now suppose that is much larger than
. Since
, this implies in particular that
(say), which forces
and .
For generic , we have at most
distinct prime factors, and each such distinct prime less than
contributes at most
to the product
. We conclude that generically, at least one of these primes
must exceed
, thus we generically have
In particular, we have
for some . This makes the quantity
-smooth, i.e. all the prime factors are at most
. On the other hand, the remaining prime factors
are at least
, and
, so we have
. Thus we can write
as the product of
and at most
additional primes, which implies that
The exponential factor looks bad, but we can offset it by the -smooth nature of
, which is inherited by its factors
. From (10),
is at most
; by using the square root trick, we can restrict
to be at least the square root of
, and thus to be at least
. Also,
divides
, and as such inherits many of the prime factorisation properties of
; in particular,
distinct prime factors, and
has no prime powers
dividing
with
and
.
To summarise, we have shown the following variant of (8):
Lemma 4 (Lowering the level) For generic
, we
for some
, where
is the set of all
-smooth numbers
between
and
with
distinct prime factors, and such that there are no prime powers
dividing
with
and
.
Applying this lemma (and discarding the non-generic ), we can thus upper bound
(up to acceptable errors) by
The level is now less than and we can use the usual methods to estimate the inner sums:
It is at this point that we need some algebraic number theory, and specifically the Landau prime ideal theorem, via the following lemma:
Proof: Let be the number field formed by extending the rationals by adjoining a root
of the irreducible polynomial
. The Landau prime ideal theorem (the generalisation of the prime number theorem to such fields) then tells us (among other things) that the number of prime ideals in
of norm less than
is
. Note that if
is a prime with a simple root
in
, then one can associate a prime ideal in
of norm
defined as
. As long as
does not divide the discriminant, one has
simple roots; but there are only
primes that divide the discriminant. From this we see that
(One can complement this upper bound with a lower bound, since the ideals whose norms are a power of a (rational) prime rather than a prime have only a negligible contribution to the ideal count, but we will not need the lower bound here). By summation by parts we conclude
and (12) follows by standard multiplicative number theory methods (e.g. bounding by computing the Euler product, noting that
whenever
does not divide the discriminant of
, thanks to Hensel’s lemma).
This proposition already deals with the bounded case. For large
we need the following variant:
Proposition 6 For any
, one has
for some absolute constant
.
The bound (11) then follows as a corollary of this proposition. In fact, one expects the -smoothness in the definition of
to induce a gain of about
; see this survey of Granville for extensive discussion of this and related topics.
Proof: If , then we can write
for some primes
. As noted previously, the primes in this product that are less than
each contribute at most
to this product, and there are at most
of these primes, so their total contribution is at most
. Since
, we conclude that the primes that are greater than
in the factorisation of
must multiply to at least
(say). By definition of
, these primes are distinct. By the pigeonhole principle, we can then find
such that there are distinct primes
between
and
which appear in the prime factorisation of
, where
(say); by definition of
, all these primes are distinct and can thus be ordered as
, and we can write
for some
. As the
are bounded, we have
and so we can upper bound by
Using (12) and symmetry we can bound this by
By the prime number theorem (or Mertens’ theorem) we have
Inserting this bound and summing the series using Stirling’s formula, one obtains the claim.
14 comments
Comments feed for this article
24 July, 2011 at 2:39 am
Lilian Matthiesen
Many thanks for this exposition! I would like to add that Erdös’s argument may be used to construct a pseudorandom majorant for the divisor function, as I’ve done in this paper (http://arxiv.org/abs/1011.0019).
25 July, 2011 at 12:15 pm
Mats Granvik
The terms of the von Mangoldt can be expanded into series which have numerators that form a symmetric matrix:
http://math.stackexchange.com/questions/48946/do-these-series-converge-to-the-mangoldt-function
26 July, 2011 at 2:52 pm
Weekly Picks « Mathblogging.org — the Blog
[…] came in. On the non-English side, Series Divergentes portrayed John E. Littlewood (translation), Gaussianos wrote about the magical appearances of Gauss’s Theorem (translation) and Bloghetto started a new series on Pythagoras […]
27 July, 2011 at 3:55 am
poemphychern
楼主您好,请问您上面的公式是怎么编辑的?我是刚注册的,需要安装什么插件吗?怎么安装?
27 July, 2011 at 8:36 am
Terence Tao
See
https://terrytao.wordpress.com/about/
and
http://faq.wordpress.com/2007/02/18/can-i-put-math-or-equations-in-my-posts/
31 July, 2011 at 11:13 am
ImNotSure
Hi Terence,
Nice exposition! I have a question, did you have a typo in formula (1)? it is
or
?
And thanks for this post.
[Corrected, thanks – T.]
31 July, 2011 at 7:25 pm
ImNotSure
You welcome,
You have another typos, but I think that the readers can correct it when they read.
Bye bye.
31 July, 2011 at 10:17 pm
Counting the number of solutions to the Erdös-Straus equation on unit fractions « What’s new
[…] input of the ErdH{o}s divisor bound on expressions of the form for polynomials , discussed in this recent blog post. (Actually, we need to tighten ErdH{o}s’ bound somewhat, to obtain some uniformity in the […]
6 October, 2011 at 4:56 pm
mathsetc
[…] Erdos’ divisor bound (terrytao.wordpress.com) […]
3 November, 2011 at 12:44 pm
Anonymous
There is an error in the formula following (5). The asymptotic for $\tau(n)$ derived using the Dirichlet hyperbola method is given by $\tau(n) = n \log n + (2\gamma -1) n + O(\sqrt(n))$, where $\gamma$ denotes the Euler-Mascheroni constant. If this wasn’t simply a typo, you may have taken the approximation $H_n = \log n + O(1)$ and reduced this to $n H_n = n \log n + O(1)$ (where $H_n$ is the nth harmonic number). One must use, instead, the approximation $H_n = \log n + \gamma + O(n^(-1/2))$. This is where the $\gamma$ becomes significant.
[Corrected, thanks – T.]
1 March, 2012 at 5:25 pm
254B, Notes 7: Sieving and expanders « What’s new
[…] power of here (as in Exercise 4), by using tools such as Landau’s prime ideal theorem; see this previous blog post for some related discussion. Remark 2 The combinatorial sieve is not the only type of sieve used […]
21 June, 2012 at 1:29 pm
Martin Klazar
I think there is a small gap/error in the derivation of the asymptotics for
sum_{n<x}tau(n^2+1). In the displayed formula after "The constraint {n^2+1=0 \hbox{ mod } d} is periodic in {n} with period {d}, so we can write this as…" there instead of the term O(1) it should be correctly, I think, O(rho(d)). This is what one gets by splitting the range d<n<x for n into intervals with length d and a residual interval with length less than d.
(Even without the residual interval one still get this error term due to omitting the floors in [x/d].)
So instead of the trivial sum_{n<x}O(1)=O(x) one gets the sum sum_{n<x}rho(d) and is not done so easily. But one can show with some effort that the last sum is indeed O(x). It is not quite straightforward (for me) because rho(d) is unbounded and may be as large as 2^{omega(d)}.
[Edited, thanks – T.]
10 June, 2013 at 5:33 pm
A combinatorial subset sum problem associated with bounded prime gaps | What's new
[…] from this paper of Shiu or this paper of Barban-Vehov, and can also be proven using the methods in this previous blog post. (The factor of is needed to account for the possibility that is not primitive, while the term […]
5 July, 2015 at 6:32 am
MFH
Hello Terry, the link to Dirichlet Hyperbola Method on planetmath.org does not work any more. I think it should be fixed to http://planetmath.org/dirichlethyperbolamethod
Best wishes,
Maximilian
[Corrected, thanks – T.]