The Green-Tao theorem states that for every $n$, there is an arithmetic sequence of length $n$ consisting of primes.

For primes, $p$, let $P(p)$ be the maximum length of an arithmetic progression of primes whose least element is $p$.

Is it known whether $P(p)=p$ for every prime?

(This clearly generalizes the Green-Tao theorem, asserting that long progressions show up "as soon as possible." Note that $P(p) \leq p$ by viewing the progression mod $p$.)

  • 1
    $\begingroup$ Interesting conjecture. I am sure it is open. $\endgroup$
    – GH from MO
    Jan 28, 2017 at 23:05
  • 5
    $\begingroup$ I am not aware of anything in that direction. Even $P(p)\geq 3$ sounds difficult to me. $\endgroup$
    – GH from MO
    Jan 28, 2017 at 23:12
  • 7
    $\begingroup$ Regarding $p=11$: the smallest sequence is $11+n\times 210\times 7315048$ for $0\le n \le 10$. $\endgroup$ Jan 29, 2017 at 13:47
  • 4
    $\begingroup$ A good question. If true, the proof would have to be very delicate (not at all like the regularity-lemma-like proofs of Green-Tao). If false, I think a proof would be extremely strange. Perhaps current techniques can give some lower bound on $P(p)$, but this too sounds tricky to me. See the following (especially the last page or so) for some discussion of other related results. people.maths.ox.ac.uk/~conlond/green-tao-expo.pdf $\endgroup$
    – Pat Devlin
    Jan 31, 2017 at 0:24
  • 2
    $\begingroup$ I am not sure about the complete history of the problem $\ P(p)=p?\ $ I know that Siemion Fajtlowicz proposed this conjecture in 1991/2 or earlier. At that time I've got an algorithm and coded a program which gave me $\ P(13)=13.\ $ Once again, I am not a specialist, I don't know the full history here. My feeling was that $\ P(17) < 17\ ($ perhaps $\ \le 15).\ $ I feel strongly that $\ P(p) < p\ $ for every prime $\ p>13;\ $ I'd even conjecture that $\ p-P(p)\rightarrow \infty\ $ for $\ p\rightarrow\infty$. $\endgroup$ Jan 31, 2017 at 5:37

1 Answer 1


Yes, this is unknown; it is even unknown (as GH from MO suspected in a comment) whether $P(p) \ge 3$ always. An equivalent statement to $P(p) \ge 3$ is that there exists an integer $x>0$ such $p+x$ and $p+2x$ are both prime. This is a twin-prime-like problem: nobody has ever proved a statement saying that two fixed linear polynomials $ax+b$ and $cx+d$ are infinitely often simultaneously prime, or even that they must generally be simultaneously prime once. (The Green-Tao theorem converts into a statement about linear polynomials $x,x+d,x+2d,...$ in two variables $x$ and $d$; when we fix $p$ here, we have only one variable.)

On the other hand, the prime $k$-tuples conjecture does imply that $P(p)=p$ for every prime $p$: the corresponding polynomials are $p+x,\dots,p+(p-1)x$, and these polynomials form an admissible set (their product is not identically zero modulo any prime).

  • 1
    $\begingroup$ It's not the $k$-tuples conjecture which you have to use here, but rather Dickson's conjecture. $\endgroup$
    – Wojowu
    Aug 12, 2018 at 10:43

Your Answer

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

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