# What is the status on this conjecture on arithmetic progressions of primes?

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$$.)

• Interesting conjecture. I am sure it is open. Jan 28, 2017 at 23:05
• I am not aware of anything in that direction. Even $P(p)\geq 3$ sounds difficult to me. Jan 28, 2017 at 23:12
• Regarding $p=11$: the smallest sequence is $11+n\times 210\times 7315048$ for $0\le n \le 10$. Jan 29, 2017 at 13:47
• 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 Jan 31, 2017 at 0:24
• 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$. Jan 31, 2017 at 5:37

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).
• It's not the $k$-tuples conjecture which you have to use here, but rather Dickson's conjecture. Aug 12, 2018 at 10:43