Roth's theorem on arithmetic progressions

In 1953, Roth used Fourier analysis to prove an upper bound of ${\displaystyle r_{3}([N])=O\left({\frac {N}{\log \log N}}\right)}$. Below is a sketch of this proof.

Define the Fourier transform of a function ${\displaystyle f:\mathbb {Z} \rightarrow \mathbb {C} }$ to be the function ${\displaystyle {\widehat {f}}}$ satisfying

${\displaystyle {\widehat {f}}(\theta )=\sum _{x\in \mathbb {Z} }f(x)e(-x\theta )}$,

where ${\displaystyle e(t)=e^{2\pi it}}$.

Let ${\displaystyle A}$ be a 3-AP-free subset of ${\displaystyle \{1,\dots ,N\}}$. The proof proceeds in 3 steps.

1. Show that a ${\displaystyle A}$ admits a large Fourier coefficient.
2. Deduce that there exists a sub-progression of ${\displaystyle \{1,\dots ,N\}}$ such that ${\displaystyle A}$ has a density increment when restricted to this subprogression.
3. Iterate Step 2 to obtain an upper bound on ${\displaystyle |A|}$.

For functions, ${\displaystyle f,g,h:\mathbb {Z} \rightarrow \mathbb {C} ,}$ define

${\displaystyle \Lambda (f,g,h)=\sum _{x,y\in \mathbb {Z} }f(x)g(x+y)h(x+2y)}$

Counting Lemma Let ${\displaystyle f,g:\mathbb {Z} \rightarrow \mathbb {C} }$ satisfy ${\displaystyle \sum _{n\in \mathbb {Z} }|f(n)|^{2},\sum _{n\in \mathbb {Z} }|g(n)|^{2}\leq M}$. Define ${\displaystyle \Lambda _{3}(f)=\Lambda (f,f,f)}$. Then ${\displaystyle |\Lambda _{3}(f)-\Lambda _{3}(g)|\leq 3M\|{\widehat {f-g}}\|_{\infty }}$.

The counting lemma tells us that if the Fourier Transforms of ${\displaystyle f}$ and ${\displaystyle g}$ are "close", then the number of 3-term arithmetic progressions between the two should also be "close." Let ${\displaystyle \alpha =|A|/N}$ be the density of ${\displaystyle A}$. Define the functions ${\displaystyle f=\mathbf {1} _{A}}$ (i.e the indicator function of ${\displaystyle A}$), and ${\displaystyle g=\alpha \cdot \mathbf {1} _{[N]}}$. Step 1 can then be deduced by applying the Counting Lemma to ${\displaystyle f}$ and ${\displaystyle g}$, which tells us that there exists some ${\displaystyle \theta }$ such that

${\displaystyle \left|\sum _{n=1}^{N}(1_{A}-\alpha )(n)e(\theta n)\right|\geq {\frac {\alpha ^{2}}{10}}N}$.

Given the ${\displaystyle \theta }$ from step 1, we first show that it's possible to split up ${\displaystyle [N]}$ into relatively large subprogressions such that the character ${\displaystyle x\mapsto e(x\theta )}$ is roughly constant on each subprogression.

Lemma 1: Let ${\displaystyle 0<\eta <1,\theta \in \mathbb {R} }$. Assume that ${\displaystyle N>C\eta ^{-6}}$ for a universal constant ${\displaystyle C}$. Then it is possible to partition ${\displaystyle [N]}$ into arithmetic progressions ${\displaystyle P_{i}}$ with length ${\displaystyle N^{1/3}\leq |P_{i}|\leq 2N^{1/3}}$ such that ${\displaystyle \sup _{x,y\in P_{i}}|e(x\theta )-e(y\theta )|<\eta }$ for all ${\displaystyle i}$.

Next, we apply Lemma 1 to obtain a partition into subprogressions. We then use the fact that ${\displaystyle \theta }$ produced a large coefficient in step 1 to show that one of these subprogressions must have a density increment:

Lemma 2: Let ${\displaystyle A}$ be a 3-AP-free subset of ${\displaystyle [N]}$, with ${\displaystyle |A|=\alpha N}$ and ${\displaystyle N>C\alpha ^{-12}}$. Then, there exists a sub progression ${\displaystyle P\subset [N]}$ such that ${\displaystyle |P|\geq N^{1/3}}$ and ${\displaystyle |A\cap P|\geq (\alpha +\alpha ^{2}/40)|P|}$.

We now iterate step 2. Let ${\displaystyle a_{t}}$ be the density of ${\displaystyle A}$ after the ${\displaystyle t}$th iteration. We have that ${\displaystyle \alpha _{0}=\alpha ,}$ and ${\displaystyle \alpha _{t+1}\geq \alpha +\alpha ^{2}/40.}$ First, see that ${\displaystyle \alpha }$ doubles (i.e. reach ${\displaystyle T}$ such that ${\displaystyle \alpha _{T}\geq 2\alpha _{0}}$) after at most ${\displaystyle 40/\alpha +1}$ steps. We double ${\displaystyle \alpha }$ again (i.e reach ${\displaystyle \alpha _{T}\geq 4\alpha _{0}}$) after at most ${\displaystyle 20/\alpha +1}$ steps. Since ${\displaystyle \alpha \leq 1}$, this process must terminate after at most ${\displaystyle O(1/\alpha )}$ steps.

Let ${\displaystyle N_{t}}$ be the size of our current progression after ${\displaystyle t}$ iterations. By Lemma 2, we can always continue the process whenever ${\displaystyle N_{t}\geq C\alpha _{t}^{-12},}$ and thus when the process terminates we have that ${\displaystyle N_{t}\leq C\alpha _{t}^{-12}\leq C\alpha ^{-12}.}$ Also, note that when we pass to a subprogression, the size of our set decreases by a cube root. Therefore

${\displaystyle N\leq N_{t}^{3^{t}}\leq (C\alpha ^{-12})^{3^{O(1/\alpha )}}=e^{e^{O(1/\alpha )}}.}$

Therefore ${\displaystyle \alpha =O(1/\log \log N),}$ so ${\displaystyle |A|=O\left({\frac {N}{\log \log N}}\right),}$ as desired. ${\displaystyle \blacksquare }$

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]

Below is an outline of a proof using the Szemerédi regularity lemma.

Let ${\displaystyle G}$ be a graph and ${\displaystyle X,Y\subseteq V(G)}$. We call ${\displaystyle (X,Y)}$ an ${\displaystyle \epsilon }$-regular pair if for all ${\displaystyle A\subset X,B\subset Y}$ with ${\displaystyle |A|\geq \epsilon |X|,|B|\geq \epsilon |Y|}$, one has ${\displaystyle |d(A,B)-d(X,Y)|\leq \epsilon }$.

A partition ${\displaystyle {\mathcal {P}}=\{V_{1},\ldots ,V_{k}\}}$ of ${\displaystyle V(G)}$ is an ${\displaystyle \epsilon }$-regular partition if

${\displaystyle \sum _{(i,j)\in [k]^{2},(V_{i},V_{j}){\text{ not }}\epsilon {\text{-regular}}}|V_{i}||V_{j}|\leq \epsilon |V(G)|^{2}}$.

Then the Szemerédi regularity lemma says that for every ${\displaystyle \epsilon >0}$, there exists a constant ${\displaystyle M}$ such that every graph has an ${\displaystyle \epsilon }$-regular partition into at most ${\displaystyle M}$ parts.

We can also prove that triangles between ${\displaystyle \epsilon }$-regular sets of vertices must come along with many other triangles. This is known as the triangle counting lemma.

Triangle Counting Lemma: Let ${\displaystyle G}$ be a graph and ${\displaystyle X,Y,Z}$ be subsets of the vertices of ${\displaystyle G}$ such that ${\displaystyle (X,Y),(Y,Z),(Z,X)}$ are all ${\displaystyle \epsilon }$-regular pairs for some ${\displaystyle \epsilon >0}$. Let ${\displaystyle d_{XY},d_{XZ},d_{YZ}}$ denote the edge densities ${\displaystyle d(X,Y),d(X,Z),d(Y,Z)}$ respectively. If ${\displaystyle d_{XY},d_{XZ},d_{YZ}\geq 2\epsilon }$, then the number of triples ${\displaystyle (x,y,z)\in X\times Y\times Z}$ such that ${\displaystyle x,y,z}$ form a triangle in ${\displaystyle G}$ is at least

${\displaystyle (1-2\epsilon )(d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )\cdot |X||Y||Z|}$.

Using the triangle counting lemma and the Szemerédi regularity lemma, we can prove the triangle removal lemma, a special case of the graph removal lemma.[6]

Triangle Removal Lemma: For all ${\displaystyle \epsilon >0}$, there exists ${\displaystyle \delta >0}$ such that any graph on ${\displaystyle n}$ vertices with less than or equal to ${\displaystyle \delta n^{3}}$ triangles can be made triangle-free by removing at most ${\displaystyle \epsilon n^{2}}$ edges.

This has an interesting corollary pertaining to graphs ${\displaystyle G}$ on ${\displaystyle N}$ vertices where every edge of ${\displaystyle G}$ lies in a unique triangle. In specific, all of these graphs must have ${\displaystyle o(N^{2})}$ edges.

Take a set ${\displaystyle A}$ with no 3-term arithmetic progressions. Now, construct a tripartite graph ${\displaystyle G}$ whose parts ${\displaystyle X,Y,Z}$ are all copies of ${\displaystyle \mathbb {Z} /(2N+1)\mathbb {Z} }$. Connect a vertex ${\displaystyle x\in X}$ to a vertex ${\displaystyle y\in Y}$ if ${\displaystyle y-x\in A}$. Similarly, connect ${\displaystyle z\in Z}$ with ${\displaystyle y\in Y}$ if ${\displaystyle z-y\in A}$. Finally, connect ${\displaystyle x\in X}$ with ${\displaystyle z\in Z}$ if ${\displaystyle (z-x)/2\in A}$.

This construction is set up so that if ${\displaystyle x,y,z}$ form a triangle, then we get elements ${\displaystyle y-x,{\frac {z-x}{2}},z-y}$ that all belong to ${\displaystyle A}$. These numbers form an arithmetic progression in the listed order. The assumption on ${\displaystyle A}$ then tells us this progression must be trivial: the elements listed above are all equal. But this condition is equivalent to the assertion that ${\displaystyle x,y,z}$ is an arithmetic progression in ${\displaystyle \mathbb {Z} /(2N+1)\mathbb {Z} }$. Consequently, every edge of ${\displaystyle G}$ lies in exactly one triangle. The desired conclusion follows. ${\displaystyle \blacksquare }$

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

${\displaystyle r_{3}([N])\leq c\cdot {\frac {N}{\log \log N}}}$

for some constant ${\displaystyle c}$. 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

${\displaystyle r_{3}([N])\leq {\frac {N}{(\log N)^{1+c}}}.}$

In February 2023 a preprint by Kelley and Meka[18][19] gave a new bound of

${\displaystyle r_{3}([N])\leq 2^{-O((\log N)^{c})}\cdot N}$.

and four days later Bloom and Sisask simplified the result and with a little improvement to ${\displaystyle r_{3}([N])\leq \exp(-c(\log N)^{1/11})N}$.[20]

There has also been work done on the other end, constructing the largest set with no three-term arithmetic progressions. The best construction has barely been improved since 1946 when Behrend[21] improved on the initial construction by Salem and Spencer and proved

${\displaystyle r_{3}([N])\geq N\exp(-c{\sqrt {\log N}})}$.

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 three-term progressions.[11] If correct, the Kelley-Meka bound will prove this conjecture.

As a variation, we can consider the analogous problem over finite fields. Consider the finite field ${\displaystyle \mathbb {F} _{3}^{n}}$, and let ${\displaystyle r_{3}(\mathbb {F} _{3}^{n})}$ be the size of the largest subset of ${\displaystyle \mathbb {F} _{3}^{n}}$ which contains no 3-term arithmetic progression. This problem is actually equivalent to the cap set problem, which asks for the largest subset of ${\displaystyle \mathbb {F} _{3}^{n}}$ 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[22] were the first to show that ${\displaystyle r_{3}(\mathbb {F} _{3}^{n})=o(3^{n}).}$ In 1995, Roy Mesuhlam[23] used a similar technique to the Fourier-analytic proof of Roth's theorem to show that ${\displaystyle r_{3}(\mathbb {F} _{3}^{n})=O\left({\frac {3^{n}}{n}}\right).}$ This bound was improved to ${\displaystyle O(3^{n}/n^{1+\epsilon })}$ in 2012 by Bateman and Katz.[24]

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 ${\displaystyle r_{3}(\mathbb {F} _{3}^{n})=O(2.756^{n})}$.[25][26][27]

The best known lower bound is approximately ${\displaystyle 2.218^{n}}$, given in 2022 by Tyrrell.[28]

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 ${\displaystyle \epsilon >0}$, there exists some ${\displaystyle n_{0}=n_{0}(\epsilon )}$ such that for every ${\displaystyle n>n_{0}}$ and ${\displaystyle A\subset \mathbb {F} _{3}^{n}}$ with ${\displaystyle |A|=\alpha 3^{n},}$ there exists some ${\displaystyle y\neq 0}$ such that ${\displaystyle |\{x:x,x+y,x+2y\in A\}|\geq (\alpha ^{3}-\epsilon )3^{n}.}$

If ${\displaystyle A}$ is chosen randomly from ${\displaystyle \mathbb {F} _{3}^{n},}$ then we would expect there to be ${\displaystyle \alpha ^{3}3^{n}}$ progressions for each value of ${\displaystyle y}$. The popular differences theorem thus states that for each ${\displaystyle |A|}$ with positive density, there is some ${\displaystyle y}$ such that the number of 3-APs with common difference ${\displaystyle y}$ is close to what we would expect.

This theorem was first proven by Green in 2005,[29] who gave a bound of ${\displaystyle n_{0}={\text{tow}}((1/\epsilon )^{O(1)}),}$ where ${\displaystyle {\text{tow}}}$ is the tower function. In 2019, Fox and Pham recently improved the bound to ${\displaystyle n_{0}={\text{tow}}(O(\log {\frac {1}{\epsilon }})).}$[30]

A corresponding statement is also true in ${\displaystyle \mathbb {Z} }$ for both 3-APs and 4-APs.[31] However, the claim has been shown to be false for 5-APs.[32]