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

Normal heuristics give that number of k-term arithmetic progressions in [1,N] should be about


for some constant $c_k$ dependent on k. The paper of Green and Tao gives a similar lower bound for all k (with a much worse constant, but still), and recent work by Green, Tao and Ziegler have established the correct asymptotic for k=3 and k=4.

I am looking for a reference which establishes an upper bound for all k - I'm sure I've heard of one, but I can't find mention of the relevant paper anywhere. Of course, if there is a simple proof, that would appreciated as well.

That is, I am looking for a reference and/or proof which establishes that the number of k-term arithmetic progressions of primes in [1,N] is at most \[c_k'\frac{N^2}{\log^kN}\]

for some constant $c_k'$.

share|cite|improve this question
up vote 13 down vote accepted

Well, any standard upper bound sieve (e.g. Selberg sieve, combinatorial sieve, beta sieve, etc.) will give this type of result. I'm not sure where you can find an easily citeable formulation, though. One can get this bound from Theorem D.3 of this paper of Ben and myself on page 67 (see in particular the remark at the bottom of that page). But this is certainly not the first place where such a bound appears. (The Goldston-Yildirim papers will give this result too, but this is also not the first place either.)

share|cite|improve this answer

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.