Let $ N_\chi(\alpha,T)$ be the number of zeros of $L(s=\sigma+it,\chi) = \sum \frac{\chi(n)}{n^s}$ where $c > 0$ and $(\sigma,t) $ are in the rectangle $ [\alpha,1] \times [-T,T]$.

In various papers one can read an estimate of the number of zeros over all L-functions:

$$ \sum_{\chi \mod q} N_\chi(\alpha,T) \ll T^{c(1-\alpha)} $$

How does this imply the prime number theorem for arithmetic progressions?

$$ \sum_{1 \leq q \leq Q} \sum_{\chi} \left| \sum_x^{x+h}\chi(p) \log p \right| \ll h \cdot e^{\large -a \frac{\log x}{\log Q}}$$

I hardly recognize this as the statement there are infinitely many primes in any arithmetic sequence

Since this is a statement about all characters $\chi$ how do we get a single arithmetic sequence $n = aq+b$?

I am a non-expert and I suspect results like these are not 100% clear to people outside that field.

Similar in spirit, does the Polya-Vinogradov inequality imply PNT for arithmetic sequences? That may be a separate question.

  • $\begingroup$ hey @John, I don't understand your double sum, could you please write it precisely ? $\endgroup$
    – reuns
    Mar 6, 2016 at 8:26

3 Answers 3


Firstly, a general comment: as understanding of a mathematical problem deepens, it is common (and even expected) for the most mathematically natural formulation of a given problem (or class of problems) to become "hardly recognisable" as arising from the formulation of the problem that historically motivated work in this area. For instance, the classical Greek problems of trisecting the angle or doubling the cube by straightedge and compass became transformed into part of the Galois theory of field extensions, whereas the superficially similar classical Greek question of squaring the circle by straightedge and compass has now instead become part of transcendence theory. These fields have since transformed further, for instance in modern algebraic geometry one can think of Galois theory as a special case of the theory of schemes (and their fundamental groups). These transformations arise because the mathematical tools and insights that one slowly acquires to attack these problems are often naturally abstracted using a formalism which often has no direct connection to the historical motivations of the problem, other than that the historical problem happens to be transformable to a special case of a much broader (and often much more interesting, ultimately) class of questions that the formalism is well equipped to handle.

Now for the specific question at hand. The first insight, fundamental to modern analytic number theory, is that historical number-theoretic questions such as "how can I show that there infinitely many primes of the form $X$?" should be thought of as special cases of the much more general problem "How can I obtain good asymptotics or bounds for sums of the form $\sum_p f(p)$, where $p$ ranges over primes?". The original problem can be viewed as the special case where $f(p)$ is the indicator function $1_X$ associated to the property $X$; however the latter problem is in a much more general, flexible, and powerful framework, because of all the tools we have to compare one sum with another. For instance, rather than doing a naive unweighted count $\sum_p 1_X(p)$, one could work with more general weighted sums such as $\sum_p \frac{1_X(p)}{p}$, $\sum_p \frac{1_X(p)}{p^s}$, $\sum_p 1_X(p) \log p$, etc. which may be more advantageous to work with. In the case of Dirichlet's theorem on arithmetic progressions, a key insight of Dirichlet himself was that the multiplicative Fourier expansion

$$ 1_{a \hbox{ mod } q}(n) = \frac{1}{\phi(q)} \sum_\chi \overline{\chi(a)} \chi(n)$$

allowed one to convert the original question of primes into arithmetic progressions $a \hbox{ mod } q$ into what turned out to ultimately be a much more interesting question, namely the estimation of Dirichlet character sums over primes, such as $\sum_{x \leq p \leq x+h} \chi(p) \log p$. Basically, the more upper bounds one has on these sums for non-principal Dirichlet characters, the more easily one is able to control historically interesting statistics such as $\sum_{x \leq p \leq x+h: p = a \hbox{ mod } q} 1$ in terms of the principal character $\chi_0(n) := 1_{(n,q)=1}$, which relatively easy to work with.

The main reason that one prefers to work with characters over arithmetic progressions is because the former has much better multiplicative structure than the latter, allowing the full power of multiplicative number theory to be brought into play. Indeed, the next great insight of Dirichlet was that character sums and products over primes were closely tied to the associated Dirichlet $L$-function, through identities such the Euler product formula

$$ L(s,\chi) = \prod_p (1 - \frac{\chi(p)}{p^s})^{-1}$$

(which encodes the fundamental theorem of arithmetic and the multiplicative nature of the Dirichlet character $\chi$) or the log-derivative of this formula,

$$ -\frac{L'(s,\chi)}{L(s,\chi)} = \sum_{j=1}^\infty \sum_p \frac{\chi(p)^j}{p^{sj}} \log p.$$

In the latter formula one can already begin seeing why it is in fact natural to weight primes by characters and by the logarithmic weight $\log p$. (Actually, the most convenient way to package all this information is to replace sums over primes with sums over natural numbers weighted by the von Mangoldt function.)

Through complex analysis tools such as the residue theorem, we know that the behaviour of the meromorphic function $-\frac{L'(s,\chi)}{L(s,\chi)}$ is controlled by the location of the zeroes of the Dirichlet $L$-function $L(s,\chi)$. Putting all this together, we now see that the key question one needs to resolve to understand primes in arithmetic progressions is where the zeroes of $L(s,\chi)$ are. For instance, Dirichlet's original proof of his theorem ultimately reduced matters to showing that $s=1$ is not a zero of this function. Through various "explicit formulae", one can make this connection much more manifest, for instance the von Mangoldt explicit formula for the Dirichlet L-function basically reads

$$ \sum_{p \leq X} \chi(p) \log p + \dots = - \sum_\rho \frac{X^\rho}{\rho} + \dots$$

where $\rho$ ranges over zeroes of $L(s,\chi)$, and the $\dots$ conceal some lower order terms which I will omit here (together with the issue of how to interpret the infinite sum on the RHS, or whether one should truncate it to a finite sum) for simplicity. Combining such formulae with the multiplicative Fourier expansion mentioned earlier gives some useful direct connection between primes in arithmetic progressions and zeroes of $L$-functions. (This connection is sometimes popularly referred to as "the music of the primes", particularly in the $q=1$ case. Actually, with an appropriately "adelic" mindset, the $q=1$ case and $q>1$ cases can be unified into what is arguably an even more natural, albeit abstract, formalism, but that is perhaps a story for another time.)

One thing that the explicit formula reveals is that the zeroes $\rho$ that are of large real part, $\operatorname{Re}(s) > \alpha$, will have an outsize impact on the distribution of the primes. Ideally, to get the most out of the explicit formula, we would like no zeroes whatsoever to the right of the critical line $\operatorname{Re}(s)=\frac{1}{2}$ (which is where all known zeroes of Dirichlet L-functions reside), and this is the main reason why the generalised Riemann hypothesis (GRH) is such a prized objective. Of course, we can't prove GRH, but in some applications we can make do with weaker density theorems that don't entirely prohibit zeroes from appearing to the right of the critical line, but at least limit how many of them can do so, which can still lead to reasonable upper bounds on various error terms that arise when using the explicit formula. As it turns out, the closer one gets to the line $\operatorname{Re}(s)=1$, the easier it is to exclude zeroes, and indeed it is known that there are no zeroes on or to the right of this line. For $\alpha < 1$, we have thus far been unable to prevent an infinity of zeroes from lying in the infinite strip $\{ s: \operatorname{Re}(s) > \alpha \}$, but we have at least been able to get non-trivial bounds for the zeroes in rectangles such as $\{ s: \operatorname{Re}(s) > \alpha; 0 \leq \operatorname{Im}(s) < T\}$, and this, together with suitably truncated versions of a suitable explicit formula, turns out to be good enough (after some calculation) to control primes in various arithmetic progressions, as is done in the paper of Gallagher you are citing.

One might start with Davenport's multiplicative number theory book for an introduction to all this, in particular to the proof of the prime number theorem in arithmetic progressions with classical error term which uses the same general strategy as in Gallagher's paper but is somewhat easier to execute (one only needs the classical zero free region for the Dirichlet L-function, rather than the more difficult zero density estimates used by Gallagher). As mentioned in GH's answer, Iwaniec-Kowalski gives a more modern and advanced treatment of these topics. I also like Montgomery's CBMS book.

As for the Polya-Vinogradov estimate, it is certainly of some relevance in bounding character sums, which in turn can be used to control L-functions, but it is generally not the most convenient tool to use for this purpose (for instance, the original formulation of the inequality is concerned with sharply truncated character sums, whereas smoothed character sums are often more natural to work with for the purposes of understanding L-functions). Nevertheless there is certainly a close kinship. For instance the Fourier inversion used to prove Polya-Vinogradov is closely tied to the Poisson formula proof of the functional equation for the Dirichlet L-function.

  • $\begingroup$ Someday this style will feel more natural. For now I will use the outline you have provided. Thank you for writing this! $\endgroup$ Dec 27, 2015 at 18:46
  • 1
    $\begingroup$ "For α<1 , we have thus far been able to prevent an infinity of zeroes from lying in the infinite strip {s:Re(s)>α}." That would be a really big hit. Waiting for your paper on that. $\endgroup$
    – Fan Zheng
    Dec 28, 2015 at 3:24
  • 1
    $\begingroup$ Typo corrected. $\endgroup$
    – Terry Tao
    Dec 28, 2015 at 3:49
  • $\begingroup$ Very nicely explained. I like especially "convert the original question [...] into what turned out to ultimately be a much more interesting question". $\endgroup$
    – GH from MO
    Dec 28, 2015 at 4:02

I cannot comment, due to low reputation but here are three comments:

  • Polya-Vinogradov does not imply the PNT, or the PNT in arithmetic progressions.
  • The statement that you identify as the PNT is a variant of Bombieri-Vinogradov. That's a "PNT on average over arithmetic progressions having high modulus". By the way the bound you quote is false, as there is at most square-root cancellation in the sum.
  • Finally, zero-density theorems do imply Bombieri-Vinogradov although this is the old-fashioned way of getting there. A more modern way is through the large sieve, and Siegel-Walfisz. Note that zero density theorems follow from the large sieve. You can look at the original paper's of Bombieri (for example) for the implication.
  • $\begingroup$ The bound I quite is from one of Gallagher's Large Sieve papers. I am concluding their language is either inconsistent or false. $\endgroup$ Dec 26, 2015 at 20:54
  • $\begingroup$ Can you quote the paper? $\endgroup$
    – lkjasd
    Dec 26, 2015 at 20:56
  • $\begingroup$ Is there a way to prove PNT for arithmetic progressions using the methods in this paper? Or maybe I should just Bombieri-Vinogradov as a subsitute eudml.org/doc/142061 $\endgroup$ Dec 27, 2015 at 2:55
  • 1
    $\begingroup$ Gallagher's paper only claims the bound given in the original post under the additional hypotheses that $x/Q \leq h \leq x$ and $\exp(\log^{1/2} x) \leq Q \leq x^b$ for some constant $b > 0$. Also it is assumed that there is no Siegel zero. $\endgroup$
    – Terry Tao
    Dec 27, 2015 at 6:23

First of all, the zero density estimate you quote should have a $q$-dependence on the right hand side (as it is false without it). The corrected estimate implies much more than the PNT for arithmetic progressions, namely:

  1. a version of the PNT for arithmetic progressions and short intervals;
  2. a good upper bound for the first prime in an arithmetic progression.

This topic is well discussed in Iwaniec-Kowalski: Analytic number theory, see especially Chapters 10 and 18 there. Another useful source is Huxley: The distribution of prime numbers.

Roughly speaking, the number of primes lying in an arithmetic progression and an interval can be expressed from character sums over the primes (as discovered by Dirichlet), which in turn can be expressed via the Mellin transform as sums over the zeros of Dirichlet $L$-functions (as discovered by Riemann). The zero density estimate locates the zeros to some extent, hence it enables a rather precise evaluation of the prime count in question.

Regarding your second question, I don't know of a way of using the Pólya-Vinogradov inequality to count primes in arithmetic progressions.

  • $\begingroup$ As you can see I am having much difficulty understanding the relationship betweent the various theorems. Graduatelly I am learning the names of the standard books, like Iwaniec-Kowalski or Davenport or Montomery-Vaughn which have almost everything I want to know. Even if it's classical by the modern standard. $\endgroup$ Dec 27, 2015 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.