A basic estimate in multiplicative number theory (particularly if one is using the Granville-Soundararajan “pretentious” approach to this subject) is the following inequality of Halasz (formulated here in a quantitative form introduced by Montgomery and Tenenbaum).
Theorem 1 (Halasz inequality) Let be a multiplicative function bounded in magnitude by , and suppose that , , and are such that
As a qualitative corollary, we conclude (by standard compactness arguments) that if
as . In the more recent work of this paper of Granville and Soundararajan, the sharper bound
is obtained (with a more precise description of the term).
The usual proofs of Halasz’s theorem are somewhat lengthy (though there has been a recent simplification, in forthcoming work of Granville, Harper, and Soundarajan). Below the fold I would like to give a relatively short proof of the following “cheap” version of the inequality, which has slightly weaker quantitative bounds, but still suffices to give qualitative conclusions such as (2).
Theorem 2 (Cheap Halasz inequality) Let be a multiplicative function bounded in magnitude by . Let and , and suppose that is sufficiently large depending on . If (1) holds for all , then
The non-optimal exponent can probably be improved a bit by being more careful with the exponents, but I did not try to optimise it here. A similar bound appears in the first paper of Halasz on this topic.
The idea of the argument is to split as a Dirichlet convolution where is the portion of coming from “small”, “medium”, and “large” primes respectively (with the dividing line between the three types of primes being given by various powers of ). Using a Perron-type formula, one can express this convolution in terms of the product of the Dirichlet series of respectively at various complex numbers with . One can use based estimates to control the Dirichlet series of , while using the hypothesis (1) one can get estimates on the Dirichlet series of . (This is similar to the Fourier-analytic approach to ternary additive problems, such as Vinogradov’s theorem on representing large odd numbers as the sum of three primes.) This idea was inspired by a similar device used in the work of Granville, Harper, and Soundarajan. A variant of this argument also appears in unpublished work of Adam Harper.
I thank Andrew Granville for helpful comments which led to significant simplifications of the argument.
— 1. Basic estimates —
We need the following basic tools from analytic number theory. We begin with a variant of the classical Perron formula.
Proposition 3 (Perron type formula) Let be an arithmetic function bounded in magnitude by , and let . Assume that the Dirichlet series is absolutely convergent for . Then
Proof: By telescoping series (and treating the contribution of trivially), it suffices to show that
whenever .
The left-hand side can be written as
where . We now introduce the mollified version
of , where
and is a fixed smooth function supported on that equals at the origin. Basic Fourier analysis then tells us that is a Schwartz function with total mass one. This gives the crude bound
for any . For or , we use the bound (say) to arrive at the bound
for we again use and write
and use the Lipschitz bound for to obtain
for such . Putting all these bounds together, we see that
for all . In particular, we can write (3) as
The expression is bounded by when , is bounded by when , is bounded by when or , and is bounded by otherwise. From these bounds, a routine calculation (using the hypothesis ) shows that
and so it remains to show that
Writing
where
we see from the triangle inequality and the support of that
But from integration by parts we see that , and the claim follows.
Next, we recall a standard mean value estimate for Dirichlet series:
Proposition 4 ( mean value estimate) Let be an arithmetic function, and let . Assume that the Dirichlet series is absolutely convergent for . Then
Proof: This follows from Lemma 7.1 of Iwaniec-Kowalski; for the convenience of the reader we reproduce the short proof here. Introducing the normalised sinc function , we have
But a standard Fourier-analytic computation shows that vanishes unless , in which case the integral is , and the claim follows.
Now we recall a basic sieve estimate:
Proposition 5 (Sieve bound) Let , let be an interval of length , and let be a set of primes up to . If we remove one residue class mod from for every , the number of remaining natural numbers in is at most .
Proof: This follows for instance from the fundamental lemma of sieve theory (see e.g. Corollary 19 of this blog post). (One can also use the Selberg sieve or the large sieve.)
Finally, we record a standard estimate on the number of smooth numbers:
Proposition 6 Let and , and suppose that is sufficiently large depending on . Then the number of natural numbers in which have no prime factor larger than is at most .
Proof: See Corollary 1.3 of this paper of Hildebrand and Tenenbaum. (The result also follows from the more classical work of Dickman.) We sketch a short proof here due to Kevin Ford. Let denote the set of numbers that are “smooth” in the sense that they have no prime factor larger than . It then suffices to prove the bound
since the contribution of those less than (say) is negligible, and for the other values of , is comparable to . Writing , we can rearrange the left-hand side as
By the prime number theorem, the contribution to of those is , and the contribution of those with consists only of prime powers, which contribute . Combining these estimates, we can get a bound of the form
where is a quantity to be chosen later. Thus we can bound the left-hand side of (4) by
which by Euler products can be bounded by
By the mean value theorem applied to the function , we can bound by for . By Mertens’ theorem, we thus get a bound of
If we make the choice , we obtain the required bound (4).
— 2. Proof of theorem —
By increasing as necessary we may assume that (say). Let be small parameters (depending on ) to be optimised later; we assume to be sufficiently large depending on . Call a prime small if , medium if , and large if . Observe that for any we can factorise as a Dirichlet convolution
where
- is the restriction of to those natural numbers whose prime factors are all small;
- is the restriction of to those natural numbers whose prime factors are all medium;
- is the restriction of to those natural numbers whose prime factors are all large.
It is convenient to remove the Dirac function from , so we write
and split
Note that is the restriction of to those numbers whose prime factors are all small or medium. By Proposition 6, the number of such can certainly be bounded by if is sufficienty large. Thus the contribution of this term to (5) is .
Similarly, is the restriction of to those numbers which contain at least one large prime factor, but no medium prime factors. By Proposition 5 the number of such is bounded by if is sufficiently large. Thus the contribution of this term to (5) is , and hence
Note that is only supported on numbers whose prime factors do not exceed , so the Dirichlet series of is absolutely convergent for and is equal to , where are the Dirichlet series of respectively. Since is bounded in magnitude by (being a restriction of ), we may apply Proposition 3 and conclude (for large enough, and discarding the denominator) that
We now record some estimates:
Lemma 7 For sufficiently large , we have
and
Proof: We just prove the former inequality, as the latter is similar. By Proposition 4, we have
The term vanishes unless , and we have , so we can bound the right-hand side by
The inner summand is bounded by and supported on those that are not divisible by any small primes. From Proposition 5 and Mertens’ theorem we conclude that
and thus
as desired.
We also have an estimate:
Lemma 8 For sufficiently large , we have
for all .
Proof: From Euler products, Mertens’ theorem, and (1) we have
as desired.
Applying Hölder’s inequality, we conclude that
Setting and we obtain the claim.
24 comments
Comments feed for this article
24 November, 2015 at 8:17 am
normsinc
Is there a typo in the introduction of the normalised sinc function sinc(pi*x) = sin(pi*x) / (pi*x)? Should this be sinc(x) = sin(pi*x) / (pi*x) to match the wikipedia notation for normalised sinc?
[Corrected, thanks – T.]
25 November, 2015 at 2:15 am
Anonymous
There may be a typo in the inequality (1) in Theorem 1. As it is stated now, as soon as (1) holds for some M it holds for any larger M’, and therefore the term could be made arbitrarily small in the conclusion of the theorem. Also, the fact that (1) requires a bound from above does not seem consistent with the corollary stated right after Theorem 1.
25 November, 2015 at 7:38 am
pybienvenu
Indeed, in (1) this should be .
[Corrected, thanks – T.]
25 November, 2015 at 8:28 am
John Mangual
Does Halasz inequality imply the prime number theorem?
25 November, 2015 at 8:47 am
Terence Tao
The prime number theorem is equivalent to the assertion that . Applying Halasz’s inequality, we see that to prove the prime number theorem, one needs to obtain a non-trivial lower bound on for any real , which is equivalent to the non-vanishing of . This is not surprising since the other proofs of the PNT already demonstrate the equivalence of the PNT with the lack of zeroes of zeta on the line . Of course, one still has to establish the non-vanishing of , and for this one can use any of the standard techniques, e.g. one can use the inequality together with an upper bound for (or equivalently, an upper bound for ).
In the pretentious approach to multiplicative number theory, Halasz’s inequality is basically used as a replacement for complex methods (such as those based on Perron’s formula), but does not directly address the most difficult part of the theory, which is to determine the location of the zeroes of various zeta and L-functions.
25 November, 2015 at 11:21 am
John Mangual
There were a few conceptual leaps in understanding the prime number theorem, if at all.
Even though diverges, any twist is finite . This is a very myopic – or astigmatic – way of looking at numbers; things are very blurry . All of these averages together prove the prime number theorem.
There are a few ways to show in the book Titchmarsh. If I read them again, I might understand why that trig equality is so special here. IDK
I am also reminded of contest problems where we try to "paint" all real numbers which certain restrictions on rectangles, or triangles, or related pairs of points. Then the objective is to prove function must be 0.
What are mains is an "engine" which turns estimates of the zeta function into estimate about primes. Halasz inequality requires some multiplicative function with and somehow you estimate the averages in (1) and out pops this averaging result.
A priori if we add a bunch of complex numbers we can't assume the average is zero can we?
25 November, 2015 at 10:17 am
Anonymous
Do you think a different approach can be made in a less “pretentious” way?
25 November, 2015 at 12:34 pm
Anonymous
Is condition (1) “natural” in some sense? (i.e. is it based on some motivation from which it “naturally” follows in more or less systematic way ?)
25 November, 2015 at 1:09 pm
Terence Tao
One can view the quantity as a measure of “distance” between two multiplicative functions ; in the language of Granville and Soundarajan, this quantity measures the extent to which “pretends” to be like or vice versa. (With the square root, this distance obeys the triangle inequality.) The condition (1) is then asserting that the function does not pretend to be like any of the Archimedean characters .
Using the Euler product formula , the condition (1) is also basically equivalent to an upper bound on the magnitude of the Dirichlet series of on the line segment , which is already known (through the Perron formula) to be closely tied to the problem of obtaining asymptotics for .
26 November, 2015 at 8:04 am
Anonymous
This seems to motivate the following generalization of condition (1):
Let denote for the minimum of the LHS of (1) with its denominator generalized to .
This may give (for ) generalized versions of theorems 1, 2.
Moreover, any additional information on possible meromorphic continuation of the Dirichlet series of into the half plane , may help to improve further the estimates.
26 November, 2015 at 7:28 am
jessemckeown
In the “cheap” version, is the algebraic term really meant to be 1/T ? for the interesting Ts, this is rather smaller than the “pretentious” version. (o.t.o.h, I suppose the interest is more for small M, where we get a lot for very little?)
26 November, 2015 at 8:44 am
Terence Tao
Yes, 1/T appears to be the natural dependence on T (as one also sees from the Granville-Soundararajan refinement of the original Halasz inequality, mentioned in the blog post); this type of error also shows up for instance in the truncated Perron formula (up to logarithmic losses, at least).
28 November, 2015 at 8:33 am
Bittu
Terry sir,I am a big fan of yours.I was proposing that calculus requires functions but most of the things around us are so irregular that a proper fitting function can’t be given to it.Can you develop a superior language than calculus please.
[See https://en.wikipedia.org/wiki/Generalized_function -T.]
29 November, 2015 at 6:15 am
Anonymous
There seems to be a few typos still. Right after the heading “2. Proof of theorem” there is “By increasing M ias necessary…” Then about half a page below that “By Proopsition 5 th enumber…”
[Corrected, thanks – T.]
1 December, 2015 at 10:27 am
Kevin Ford
A short proof of Proposition 6 can be found here: http://www.math.uiuc.edu/~ford/sieve_notes_smoothnumbers.pdf
[Thanks for reminding me of your nice proof, I have added a version of it to the text. -T.]
2 December, 2015 at 7:37 am
Kevin Ford
I don’t claim any originality in the proof. It just combines the method of Wirsing (logarithmic weights) with the “Rankin trick” (introducing the parameter $\rho$), both quite useful elementary tools for studying sums of multiplicative functions.
1 December, 2015 at 6:16 pm
Anonymous
Dear Terry,
I’m always worry of you.I consider you like my brother.There’s recently a man claims to solve Riemann hypothesis but not give any proof.I never believe him.Terry, even yourself,a great genius, also very hard to struggle with Riemann.I advice you should’nt devote your result of Riemann early.It’s
dangerous .He certainly plagiarizes.This is a tip trick to trap you.At that time, he will have three things: money, fame, girls.The sixth sense tells me know about this.
Best regards,
2 December, 2015 at 5:03 pm
Zak
I was curious which part of the above argument fails to achieve the better quantitative bounds, and what kind of ideas are needed for improvements.
2 December, 2015 at 8:07 pm
Terence Tao
Adam Harper has an unpublished variant of this argument (from a few years back) which obtains the sharp bound. I think the main additional idea is to use the trick (which Kevin attributed to Wirsing in this comment thread) of summing in place of , and then decomposing as a triple convolution. (As far as I know, though, Adam has not yet made this argument publicly available.)
17 February, 2020 at 2:58 am
Mallesham
There is typo in the proof Lemma 8.
[Can you be more precise about this? – T.]
21 February, 2020 at 3:18 am
Mallesham
In the fourth and fifth lines of the proof of Lemma 8, I think it should be exponential of sum over primes instead of product over primes.
[Corrected, thanks – T.]
11 July, 2021 at 8:33 pm
irvingxryang
for proof of Lemma 7, in the second line of expressions, you missed a term 1/n_2
[Corrected, thanks – T.]
22 May, 2024 at 7:57 am
Anonymous
I think the proof of Lemma 8 is probably wrong, though the result is right. In the second last inequality of your proof, the log log should be 2 loglog . If you drop these negative terms, which has at most a constant contribution in the initial Euler expansion, you would obtain the loglog as desired.
22 May, 2024 at 9:54 am
Terence Tao
Can you clarify? I don’t see any log log terms in the proof of Lemma 8.