MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Let $S(k)$ denote the smallest integer such that there exists a k-term arithmetic progression of primes among the integers $[1,S(k)]$. Green and Tao have an unpublished note that gives a very large upper bound for $S(k)$. Conversely, an elementary argument (sketched below) gives the lower bound $S(k) > (k-1)e^{k}$. My question is, can this lower bound be improved at all?

By considering how the AP reduces mod $p$, it is easy to see that if $q$ is the step of a $k$-term AP of primes then every prime less than $k$ must divide $q$. Thus we have that $S(k) > (k-1) \prod_{p_{i} \leq k } p_{i}$. By taking logarithms and applying the prime number theorem we have that $\prod_{p_{i} \leq k } p_{i} ~ e^{k}$. This gives $S(k) > (k-1)e^{k}$.

Update: As Thomas Bloom points out, the inequality I record isn't true for small $k$. I should have written something more along the lines of $S(k) >(k-1)e^{k-o(k)}$ or $S(k) = \Omega((k-1)e^{k})$ since we know that $psi(x) > x$ infinitely often. The spirit of my question is, are there any arguments (presumably using more sophisticated machinery) that produces a better lower bound (here, I'll accept either bounds that hold for all k, or just infinitely many k).

share|cite|improve this question
I think you need to replace your '\Prod's by '\prod' – Thomas Bloom Dec 12 '09 at 12:03
Also, there is a trivial counterexample to your lower bound: 5, 11, 17, 23, 29 is a 5-term AP in [1,30] but $30\leq4e^5$. Presumably the problem is that the PNT only applies asymptotically, and it may not have bitten by the time S(k) occurs. – Thomas Bloom Dec 12 '09 at 12:08

I doubt that you can do substantially better than $\text{log}~S(k) > k$; actually, Granville believes that $\text{log}~S(k) = O(k~\text{log}~k)$.

"Combinatorially speaking," the given lower bound seems asymptotically tight (i.e., if we only use local information and PNT). But heuristically the combinatorial arguments seem to work really well when it comes to questions about additive patterns -- I'm sure there are counterexamples, but I don't know them off the top of my head.

Of course it may not be hard to improve on the $(k-1)$ factor.

share|cite|improve this answer

I'm not sure that your elementary argument is correct. Not only does the PNT not bite fast enough, but also the fact that every prime less than $k$ must divide $q$ gives only that $S(k)>(k-1)\prod_{p_i< k}p_i$, or (using the primorial notation) $S(k)>(k-1)(k-1)\#$. It is easy to show that $n\#>n$, and hence we get the lower bound $$S(k)>(k-1)^2$$ Let $l=\lfloor \log_2(k-1)\rfloor$. Then it is slightly harder (e.g. see to show that $$(k-1)\#>\frac{(k-1)^l}{2^{l(l+1)/2}} $$

This gives us $$S(k)>\frac{(k-1)^{l+1}}{2^{l(l+1)/2}}>(k-1)^{(l+1)/2} $$ I'm not sure (barring using improved bounds for the primorial) whether these methods can get anything better.

You can regain your original $\prod_{p_i\leq k}p_i$ if you can rule out the possibility that the AP can start with $k$ itself, and this then gives you a lower bound $$S(k)>(k-1)k^{(l-1)/2}$$ where $l=\lfloor\log_2k\rfloor$.

Update: Of course, you can also gain a slight improvement by noting that the first term of the AP must be at least k, and hence $$S(k)>k+(k-1)^{(l+1)/2}$$ since if we write our AP as $a,a+q,...,a+(k-1)q$then we're trying to find a lower bound for $a+(k-1)q$. This combines our best known bounds for both $a$ and $q$. I suspect that asymptotically $q$ will behave like $k\#$, and so the $e^k$ is best possible, and the $(k-1)$ factor is fixed, so any improvements must come from better lower bounds for $a$, but these would be negligible compared to $e^k$. In summary, I think your given lower bound is essentially best possible.

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.