Erdős conjecture on arithmetic progressions

In 1936, Erdős and Turán made the weaker conjecture that any set of integers with positive natural density contains infinitely many three-term arithmetic progressions.^[1] This was proven by Klaus Roth in 1952, and generalized to arbitrarily long arithmetic progressions by Szemerédi in 1975 in what is now known as Szemerédi's theorem.

In a 1976 talk titled "To the memory of my lifelong friend and collaborator Paul Turán," Paul Erdős offered a prize of US$3000 for a proof of this conjecture.^[2] In 1996 he raised the prize to US$5000.^[3]

Erdős' conjecture on arithmetic progressions can be viewed as a stronger version of Szemerédi's theorem. Because the sum of the reciprocals of the primes diverges, the Green–Tao theorem on arithmetic progressions is a special case of the conjecture.

The weaker claim that A must contain infinitely many arithmetic progressions of length 3 is a consequence of an improved bound in Roth's theorem. A 2016 paper by Bloom^[4] proved that if ${\displaystyle A\subset \{1,...,N\}}$ contains no non-trivial three-term arithmetic progressions then ${\displaystyle |A|\ll N(\log {\log {N}})/\log {N}}$.

In 2020 a preprint by Bloom and Sisask^[5] improved the bound to ${\displaystyle |A|\ll N/(\log {N})^{1+c}}$ for some absolute constant ${\displaystyle c>0}$ .

In 2023 a new bound of ${\displaystyle \exp(-c(\log N)^{1/12})N}$^[6][7][8] was found by computer scientists Kelley and Meka, with an exposition given in more familiar mathematical language by Bloom and Sisask,^[9][10] who have since improved the exponent of the Kelly-Meka bound to ${\displaystyle \beta =1/9}$, and conjectured ${\displaystyle \beta =5/41}$, in a preprint.^[11]

• Problems involving arithmetic progressions
• List of sums of reciprocals
• List of conjectures by Paul Erdős
• Müntz–Szász theorem