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$ uhmm, I'm not sure, maybe its not well define the way I wrote it, but I guess it doesn't matter. $\endgroup$ – Jorge Jan 28 '17 at 22:14
  • 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 '17 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$ – Yaakov Baruch Jan 29 '17 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 '17 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$ – Włodzimierz Holsztyński Jan 31 '17 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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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