MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 !

share|cite|improve this question
@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'. – user9072 Mar 3 '12 at 0:54
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. – Micah Milinovich Mar 3 '12 at 19:11
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. – Denis Chaperon de Lauzières Mar 3 '12 at 20:17
Granville--Sound's "pretentious perspective" is expounded upon in section 3 (Primes in Arithmetic Progressions, without L-functions) of this recent survey: – Anonymous Mar 5 '12 at 22:17
The proof of Linnik's theorem by Granville and Soundararajan can be found here (see also here – Dimitris Koukoulopoulos Mar 9 '12 at 20:22
up vote 7 down vote accepted

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:

share|cite|improve this answer
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). – js21 Mar 3 '12 at 16:33
This paper is now in the arXiv: – GH from MO Mar 6 '12 at 19:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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