Roth's theorem on arithmetic progressions is a result in additive combinatorics concerning the existence of arithmetic progressions in subsets of the natural numbers.
A subset A of the natural numbers is said to have positive upper density if Roth's theorem on arithmetic progressions (infinite version): A subset of the natural numbers with positive upper density contains a 3-term arithmetic progression.An alternate, more qualitative, formulation of the theorem is concerned with the maximum size of a Salem–Spencer set which is a subset of
Roth's theorem on arithmetic progressions (finitary version):
The first result in this direction was Van der Waerden's theorem in 1927, which states that for sufficiently large N, coloring the integers
[2] Later on in 1936 Erdős and Turán conjectured a much stronger result that any subset of the integers with positive density contains arbitrarily long arithmetic progressions.
[4] In 1953, Roth partially resolved the initial conjecture by proving they must contain an arithmetic progression of length 3 using Fourier analytic methods.
The original proof given by Roth used Fourier analytic methods.
In 1953, Roth used Fourier analysis to prove an upper bound of
produced a large coefficient in step 1 to show that one of these subprogressions must have a density increment: Lemma 2: Let
Also, note that when we pass to a subprogression, the size of our set decreases by a cube root.
Unfortunately, this technique does not generalize directly to larger arithmetic progressions to prove Szemerédi's theorem.
An extension of this proof eluded mathematicians for decades until 1998, when Timothy Gowers developed the field of higher-order Fourier analysis specifically to generalize the above proof to prove Szemerédi's theorem.
These numbers form an arithmetic progression in the listed order.
then tells us this progression must be trivial: the elements listed above are all equal.
Since then it has been extended in multiple fashions to create new and interesting results.
Furstenberg and Katznelson[7] used ergodic theory to prove a multidimensional version and Leibman and Bergelson[8] extended it to polynomial progressions as well.
Most recently, Green and Tao proved the Green–Tao theorem which says that the prime numbers contain arbitrarily long arithmetic progressions.
Since the prime numbers are a subset of density 0, they introduced a "relative" Szemerédi theorem which applies to subsets with density 0 that satisfy certain pseudorandomness conditions.
Later on Conlon, Fox, and Zhao[9][10] strengthened this theorem by weakening the necessary pseudorandomness condition.
diverges must contain arithmetic progressions of length 3; this is the first non-trivial case of another conjecture of Erdős postulating that any such set must in fact contain arbitrarily long arithmetic progressions.
The bound from the original proof of Roth's theorem showed that for some constant
Over the years this bound has been continually lowered by Szemerédi,[12] Heath-Brown,[13] Bourgain,[14][15] and Sanders.
[16][17] The current (July 2020) best bound is due to Bloom and Sisask[11] who have showed the existence of an absolute constant c>0 such that In February 2023 a preprint[18][19] (later published[20]) by Kelley and Meka gave a new bound of:
Four days later, Bloom and Sisask published a preprint giving an exposition of the result[21] (later published[22]), simplifying the argument and yielding some additional applications.
[23] There has also been work done on the other end, constructing the largest set with no 3-term arithmetic progressions.
The best construction has barely been improved since 1946 when Behrend[24] improved on the initial construction by Salem and Spencer and proved Due to no improvements in over 70 years, it is conjectured that Behrend's set is asymptotically very close in size to the largest possible set with no 3-term progressions.
In 1995, Roy Mesuhlam[26] used a similar technique to the Fourier-analytic proof of Roth's theorem to show that
[27] In 2016, Ernie Croot, Vsevolod Lev, Péter Pál Pach, Jordan Ellenberg and Dion Gijswijt developed a new technique based on the polynomial method to prove that
, discovered in December 2023 by Google DeepMind researchers using a large language model (LLM).
[31] Another generalization of Roth's theorem shows that for positive density subsets, there not only exists a 3-term arithmetic progression, but that there exist many 3-APs all with the same common difference.