Most of the proofs of Dirichlet's theorem on primes in arithmetic progressions actually give a Mertens-like theorem, and then the (weaker) statement

Chebyshev-like bound : if $(a,q) = 1$ then

$$\sum_{\substack{n \leq X \\ n \equiv a \mod q}} \Lambda(n) \gg_q \frac{X}{\varphi(q)} $$ (the factor $\varphi (q)$ is introduced here only for cosmetic reasons)

There are basically two ways in which this could be strenghtened :

  • for fixed $q$, in the $X$-aspect : this amounts to replace the $\gg $ above by $\sim$, which is exactly the prime number theorem in arithmetic progressions.
  • in the $q$-aspect : one asks for explicit $\epsilon$ (depending on $q$) satisfying $$\sum_{\substack{n \leq X \\ n \equiv a \mod q}} \Lambda(n) \geq \epsilon \frac{X}{\varphi(q)} $$

If complex analysis is allowed, the Siegel-Walfisz solves both problems and gives $\epsilon = 1 - o(1)$ in the range $q \ll \left( \log X \right) ^A $ (for any $A>0$). But I'm especially interested in elementary methods (with the usual meaning of the word "elementary" in this context). Following step by step Dirichlet's proof (or at least one of its modern variants), I managed to prove that $$ \epsilon = e^{- C \varphi(q) \left( \log q \right)^9} $$ is admissible. Apart from the unimportant $\log$ factors, I haven't improved this yet. Hence my questions :

What is the best (known) lower bound on $\epsilon$ that one can reach by elementary methods ?

What is the wider allowed range for $q$ that one gets from the elementary proofs of the prime number in arithmetic progressions ?

References are welcome, I've found none so far.

EDIT : In view of the comments and answers below, I conclude that what I'm asking for is not as classic I thought it was. I summarize the state of the question :

  • there are (relatively easy and) elementary proofs of Siegel's theorem, but deducing from it a Siegel-Walfisz theorem seems to require complex (or Fourier) analysis.

  • No elementary proof of Linnik's theorem exists in the literature, but Micah Milinovich suggests below that A. Granville could have further information on this subject. It may be worth contacting him.

EDIT 2 : My questions are essentially solved by the "anonymous's" comment below. There indeed exists an elementary proof of Linnik's theorem (or at least a proof avoiding most of the complex analysis machinery in original Linnik's proof). The last use of complex analysis originated results lies in the explicit use of $\Psi(X,q,a) = \frac{X-\frac{X^{\beta}}{\beta}}{\varphi(q)} + \text{Error term}$ (according to Andrew Granville, this seems to be fixed, but details are not clear

Thanks for your help !

  • 2
    $\begingroup$ @Igor Rivin: Maybe I am missing something, but OP says "with the usual meaning of elementary in this context", so basically no complex analysis; which seems even more transparent as before complex analyis is mentioned expicitly as 'what not'. $\endgroup$
    – user9072
    Mar 3, 2012 at 0:54
  • 3
    $\begingroup$ I believe that there are now two elementary proofs of Linnik's theorem (in the sense that they avoid zeros of L-functions), one due to Friedlander-Iwaniec and another due to Granville-Soundararajan. I do not think either proof has appeared, but I heard Andrew Granville give a talk on the subject. $\endgroup$ Mar 3, 2012 at 19:11
  • 3
    $\begingroup$ The proof of Friedlander and Iwaniec is in their sieve book, "Opera de cribro" (Chapter 24); however, it does use zeros of L-functions in addition to sieve methods. $\endgroup$ Mar 3, 2012 at 20:17
  • 3
    $\begingroup$ Granville--Sound's "pretentious perspective" is expounded upon in section 3 (Primes in Arithmetic Progressions, without L-functions) of this recent survey: dms.umontreal.ca/%7Eandrew/PDF/ItalySurvey.pdf $\endgroup$
    – Anonymous
    Mar 5, 2012 at 22:17
  • 4
    $\begingroup$ The proof of Linnik's theorem by Granville and Soundararajan can be found here dms.umontreal.ca/~andrew/PDF/OnePage.pdf (see also here dms.umontreal.ca/~andrew/Courses/MAT6627.H11.html). $\endgroup$ Mar 9, 2012 at 20:22

2 Answers 2


There is some very nice recent work of Dimitris Koukoulopoulos who uses "pretentious" methods to prove the Siegel-Walfisz Theorem. A preprint can be found here:


  • 4
    $\begingroup$ The proof of Siegel's theorem in this article is truly elementary (and this provides a simplification of Pintz's previous proof ; so thanks for this interesting reference). But the difficulty here is to turn the information on $L(1,\chi)$ into an estimate for $\Psi(X,q,a)$ : the author doesn't avoid this issue and makes a crucial use of Fourier inversion formula (as an ersatz of Perron's inversion formula). $\endgroup$
    – js21
    Mar 3, 2012 at 16:33
  • 2
    $\begingroup$ This paper is now in the arXiv: front.math.ucdavis.edu/1203.0596 $\endgroup$
    – GH from MO
    Mar 6, 2012 at 19:00

Have a look at equation (5) in

Sur un théorème de Mertens in Manuscripta Mathematica 108 (2002), pages 495--513.

by myself (O. Ramaré). You can find the paper on my web site. I get $\epsilon_q = \exp(-c\sqrt{q}(\log q)^2)$ in an elementary manner. Better would improve on the Siegel zero location. Sorry, but the paper is in french :)

I hope that helps! Olivier

  • $\begingroup$ Bonjour Olivier ! Merci pour ta réponse. J'étais effectivement tombé sur ton article peu après avoir posé cette question il y a cinq ans, et je l'avais donc cité dans le texte que je préparais alors. $\endgroup$
    – js21
    Nov 22, 2017 at 13:03

Your Answer

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

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