Top Qs
Timeline
Chat
Perspective
Roth's theorem on arithmetic progressions
On the existence of arithmetic progressions in subsets of the natural numbers From Wikipedia, the free encyclopedia
Remove ads
Roth's theorem on arithmetic progressions is a result in additive combinatorics concerning the existence of arithmetic progressions in subsets of the natural numbers. It was first proven by Klaus Roth in 1953.[1] Roth's theorem is a special case of Szemerédi's theorem for the case .
Remove ads
Statement
Summarize
Perspective
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 . Let be the size of the largest subset of which contains no 3-term arithmetic progression.
Roth's theorem on arithmetic progressions (finitary version):
Improving upper and lower bounds on is still an open research problem.
Remove ads
History
Summarize
Perspective
The first result in this direction was Van der Waerden's theorem in 1927, which states that for sufficiently large N, coloring the integers with colors will result in a term arithmetic progression.[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. In 1942, Raphaël Salem and Donald C. Spencer provided a construction of a 3-AP-free set (i.e. a set with no 3-term arithmetic progressions) of size ,[3] disproving an additional conjecture of Erdős and Turán that for some .[4]
In 1953, Roth partially resolved the initial conjecture by proving they must contain an arithmetic progression of length 3 using Fourier analytic methods. Eventually, in 1975, Szemerédi proved Szemerédi's theorem using combinatorial techniques, resolving the original conjecture in full.
Remove ads
Proof techniques
Summarize
Perspective
The original proof given by Roth used Fourier analytic methods. Later on another proof was given using Szemerédi's regularity lemma.
Proof sketch via Fourier analysis
In 1953, Roth used Fourier analysis to prove an upper bound of . Below is a sketch of this proof.
Define the Fourier transform of a function to be the function satisfying
- ,
where .
Let be a 3-AP-free subset of . The proof proceeds in 3 steps.
- Show that a admits a large Fourier coefficient.
- Deduce that there exists a sub-progression of such that has a density increment when restricted to this subprogression.
- Iterate Step 2 to obtain an upper bound on .
Step 1
For functions, define
Counting Lemma Let satisfy . Define . Then .
The counting lemma tells us that if the Fourier Transforms of and are "close", then the number of 3-term arithmetic progressions between the two should also be "close." Let be the density of . Define the functions (i.e the indicator function of ), and . Step 1 can then be deduced by applying the Counting Lemma to and , which tells us that there exists some such that
- .
Step 2
Given the from step 1, we first show that it's possible to split up into relatively large subprogressions such that the character is roughly constant on each subprogression.
Lemma 1: Let . Assume that for a universal constant . Then it is possible to partition into arithmetic progressions with length such that for all .
Next, we apply Lemma 1 to obtain a partition into subprogressions. We then use the fact that produced a large coefficient in step 1 to show that one of these subprogressions must have a density increment:
Lemma 2: Let be a 3-AP-free subset of , with and . Then, there exists a sub progression such that and .
Step 3
We now iterate step 2. Let be the density of after the th iteration. We have that and First, see that doubles (i.e. reach such that ) after at most steps. We double again (i.e reach ) after at most steps. Since , this process must terminate after at most steps.
Let be the size of our current progression after iterations. By Lemma 2, we can always continue the process whenever and thus when the process terminates we have that Also, note that when we pass to a subprogression, the size of our set decreases by a cube root. Therefore
Therefore so as desired.
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.[5]
Proof sketch via graph regularity
From the Szemerédi regularity lemma and counting lemma one obtains the graph removal lemma, and as a corollary the following:
Diamond-free Lemma. Any graph on vertices in which every edge lies in precisely one unique triangle has edges.
Application to Roth’s theorem
First note that a set has a 3-term arithmetic progression iff its reduction modulo does.
Fix with no 3-term AP. Construct a tripartite graph with parts , each a copy of . Add edges as follows:
- to if ;
- to if ;
- to if (since 2 is invertible mod ).
If form a triangle, then . These three numbers form an arithmetic progression in that order with step . Because has no nontrivial 3-term AP, they are equal, so . Therefore, if we fix any two vertices of connected by an edge, every triangle extending this edge must satisfy , yielding a unique choice of the third vertex. Furthermore, such a choice guarantees the existence of the other two edges in that triangle. Thus, the diamond-free lemma applies, and .
Notice now, that each element contributes exactly one edge for each vertex in a part: for instance, for every , there is exactly one such that , so gives exactly edges between and . The same holds for the other two pairs, hence . Consequently,
proving Roth’s theorem.
Remove ads
Extensions and generalizations
Summarize
Perspective
Szemerédi's theorem resolved the original conjecture and generalized Roth's theorem to arithmetic progressions of arbitrary length. Since then it has been extended in multiple fashions to create new and interesting results.
Furstenberg and Katznelson[6] used ergodic theory to prove a multidimensional version and Leibman and Bergelson[7] 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[8][9] strengthened this theorem by weakening the necessary pseudorandomness condition. In 2020, Bloom and Sisask[10] proved that any set such that 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.
Improving bounds
There has also been work done on improving the bound in Roth's theorem. 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,[11] Heath-Brown,[12] Bourgain,[13][14] and Sanders.[15][16] The current (July 2020) best bound is due to Bloom and Sisask[10] who have shown the existence of an absolute constant c>0 such that
In February 2023 a preprint[17][18] (later published[19]) by Kelley and Meka gave a new bound of:
.
Four days later, Bloom and Sisask published a preprint giving an exposition of the result[20] (later published[21]), simplifying the argument and yielding some additional applications. Several months later, Bloom and Sisask obtained a further improvement to , and stated (without proof) that their techniques can be used to show .[22]
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[23] 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.[10] If correct, the Kelley-Meka bound will prove this conjecture.
Roth's theorem in finite fields
As a variation, we can consider the analogous problem over finite fields. Consider the finite field , and let be the size of the largest subset of which contains no 3-term arithmetic progression. This problem is actually equivalent to the cap set problem, which asks for the largest subset of such that no 3 points lie on a line. The cap set problem can be seen as a generalization of the card game Set.
In 1982, Brown and Buhler[24] were the first to show that In 1995, Roy Mesuhlam[25] used a similar technique to the Fourier-analytic proof of Roth's theorem to show that This bound was improved to in 2012 by Bateman and Katz.[26]
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 .[27][28][29]
The best known lower bound is , discovered in December 2023 by Google DeepMind researchers using a large language model (LLM).[30]
Roth's theorem with popular differences
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.
Roth's theorem with popular differences: For all , there exists some such that for every and with there exists some such that
If is chosen randomly from then we would expect there to be progressions for each value of . The popular differences theorem thus states that for each with positive density, there is some such that the number of 3-APs with common difference is close to what we would expect.
This theorem was first proven by Green in 2005,[31] who gave a bound of where is the tower function. In 2019, Fox and Pham recently improved the bound to [32]
A corresponding statement is also true in for both 3-APs and 4-APs.[33] However, the claim has been shown to be false for 5-APs.[34]
Remove ads
References
External links
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads