← All problems

Erdős Problem #200 — Longest prime arithmetic progressions

46 years old · documented by

For an integer N≥3N\ge 3, let L(N)L(N) be the largest length of an arithmetic progression of primes contained in {1,…,N}\{1,\ldots,N\}. Explicitly, the progression has first term a prime pp, positive integer common difference dd, and length k≥1k\ge 1, with every term at most NN:

L(N)=max⁡{k≥1:∃ primes p, ∃d∈Z≥1, p+(k−1)d≤N, and p+jd is prime for every 0≤j<k}.L(N)=\max\{k\ge 1:\exists\text{ primes }p,\ \exists d\in\mathbb Z_{\ge 1},\ p+(k-1)d\le N,\ \text{and }p+jd\text{ is prime for every }0\le j<k\}.

The question is whether

lim⁡N→∞L(N)log⁡N=0,\lim_{N\to\infty}\frac{L(N)}{\log N}=0,

where NN tends to infinity through the integers and log⁡\log denotes the natural logarithm. Erdős Problems #200

Background

The broader question of finding long arithmetic progressions among the primes has a long history. A Hardy–Littlewood conjecture from 1923 predicts an asymptotic count for prime progressions of any fixed length. In 1939, van der Corput proved that there are infinitely many three-term arithmetic progressions of primes. These fixed-length results concern existence at each prescribed length, whereas the present question asks how the maximum length available below a growing cutoff compares with log⁡N\log N. The primes contain arbitrarily long arithmetic progressions

The later proof that the primes contain arbitrarily long progressions uses a transference principle: it applies Szemerédi’s theorem to a pseudorandom majorant for the primes, obtained through a set of almost primes. This provides a route from dense-set structure to prime progressions, but its conclusion is existence for each fixed length, not a quantitative estimate for the longest length as a function of NN. The primes contain arbitrarily long arithmetic progressions

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.