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.



How do estimates on $N_\chi(\alpha,T)$ lead to the Dirichlet prime number theorem for arithmetic sequences?
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](https://en.wikipedia.org/wiki/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.


