← All problems

Erdős Problem #1187 — Monochromatic progressions constrained by primes

46 years old · traced to

For an integer k≥3k\geq 3, a kk-term arithmetic progression is a sequence x,x+d,…,x+(k−1)dx,x+d,\ldots,x+(k-1)d with positive integers xx and dd. Given any finite coloring c:Z>0→{1,…,r}c:\mathbb{Z}_{>0}\to\{1,\ldots,r\}, where rr is a positive integer, are both of the following assertions true? Erdős (1980), p. 93

There exist x,d∈Z>0 such that every x+jd is prime and c(x)=c(x+d)=⋯=c(x+(k−1)d);There exist x,d∈Z>0 such that d is prime and c(x)=c(x+d)=⋯=c(x+(k−1)d)?\begin{aligned} &\text{There exist }x,d\in\mathbb{Z}_{>0}\text{ such that every }x+jd\text{ is prime and}\ c(x)=c(x+d)=\cdots=c(x+(k-1)d);\\ &\text{There exist }x,d\in\mathbb{Z}_{>0}\text{ such that }d\text{ is prime and}\ c(x)=c(x+d)=\cdots=c(x+(k-1)d)? \end{aligned}

The first assertion requires all progression terms to be prime; the second imposes no primality condition on the terms, only on the common difference. (The answers are, respectively, yes and no.) Erdős (1980), p. 93

Background

The prime-progression question belongs to the line of work on arithmetic progressions among primes and their predicted frequency. Hardy and Littlewood’s 1923 conjecture predicts an asymptotic count for prime progressions of each fixed length. Van der Corput proved in 1939 that there are infinitely many three-term progressions of primes; before Green and Tao’s work, existence for lengths at least four was still unknown. Erdős recorded the coloring questions in his 1980 survey. Green and Tao (2008) Erdős (1980), p. 93

The key mechanism in Green and Tao’s proof is a relative form of Szemerédi’s theorem: a subset of positive relative density in a sufficiently pseudorandomly weighted set inherits long arithmetic progressions. To apply this to primes, they use the WW-trick, restricting to a suitable residue class to remove local obstructions from small prime divisors, and construct a pseudorandom majorant for a modified prime-counting weight. This transfers a dense-set progression theorem to the primes without requiring the primes themselves to have positive density among the integers. Green and Tao (2008)

References

P. Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics 6 (1980), 89–115.

Source: P. Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics 6 (1980), 89–115.

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.