Erdős' conjecture on arithmetic progressions, often referred to as the Erdős–Turán conjecture, is a conjecture in arithmetic combinatorics (not to be confused with the Erdős–Turán conjecture on additive bases).
It states that if the sum of the reciprocals of the members of a set A of positive integers diverges, then A contains arbitrarily long arithmetic progressions.
Formally, the conjecture states that if A is a large set in the sense that
then A contains arithmetic progressions of any given length, meaning that for every positive integer k there are an integer a and a non-zero integer c such that
In 1936, Erdős and Turán made the weaker conjecture that any set of integers with positive natural density contains infinitely many 3 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.
[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
contains no non-trivial three-term arithmetic progressions then
In 2020 a preprint by Bloom and Sisask[5] improved the bound to
exp ( − c ( log
[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