Theorem 1 (van der Waerden). Let $k$ and $\ell$ be positive integers. Then there exists a number $W(k,\ell)$ such that whenever the numbers in $\{1,2,...,N\}$ with $N\geq W(k,\ell)$ are colored using $\ell$ colors, there is a monochromatic arithmetic progression of length $k$ .
Theorem 2 (Szemerédi). Let $\delta>0$, and let $k$ be a positive integer. Then, if $A$ is any subset of $\{1,2,...,N\}$ with $N\geq N(k,\delta)$ and having density at least $\delta$ (that is, $|A|\geq \delta N$), the set $A$ contains an arithmetic progression of length $k$.
The first result was proved by van der Waerden in 1927 (back then, the result was an open problem that many famous mathematicians attempted to resolve, but it was the young van der Waerden who solved it). The latter result is a very deep and important result of Szemerédi from 1975 (the proof was so complicated that Szemerédi refused to write it down himself). Szemerédi's proof was based on his graph regularity lemma, and virtually every proof of the theorem has started a fruitful new research direction. For instance, Furstenberg proved the theorem using ergodic theory in 1977, and Gowers using Fourier analytic methods and his uniformity norms in 2001, and the latter proof also improved bounds on $W(k,\ell)$ enormously.
It is easy to see that van der Waerden's theorem is a special case of Szemerédi's; indeed, if $\{1,2,...,N\}$ is colored with $\ell$ colors, there is at least one monochromatic subset of density at least $\frac{1}{\ell}$. In addition, both theorems allow immediately an infinite version. For Szemerédi's theorem, the infinite version is that any subset of the natural numbers with a positive lower density contains arbitrarily long arithmetic progressions. In fact, there is a nice compactness argument that can be used to deduce the finite versions of the theorems from their infinite versions, but that is a different story.
We will not try to prove Szemerédi's theorem in this post, but we will prove its special case $k=3$ due to Roth from 1953. This case is an elegant and relatively short application of Fourier analysis into combinatorics. For convenience, we also formulate this claim.
Structure increasing principle
Theorem 3 (Roth's theorem). Let $\delta>0$. Then any subset of $\{1,2,...,N\}$ with $N\geq N(\delta)$ and density at least $\delta$ contains a three term arithmetic progression.
The proof follows a general principle, which one might call structure increasing principle. I follow the presentation in Tao's book Higher order Fourier Analysis. To prove Roth's theorem, we are going to prove the following.
Lemma 4 (structure increasing principle). Let $\delta>0$ and $A\subset\{1,2,...,N\}$ with $N$ large enough. Then one of the following holds.
(i) $A$ contains a three term arithmetic progression.
(ii) There exists an arithmetic progression $J$ of length at least $ c_0\delta^2\sqrt{N}$ such that $\frac{|A\cap J|}{|J|}\geq \delta+\frac{\delta^2}{32}$.
The idea of this principle is the following: If the set $A$ is ''random'', there should be no problem in finding (many) arithmetic progressions of length three. On the other hand, if $A$ is not random enough, then (ii) asserts that it contains a highly structured part, namely a significant proportion of a long arithmetic progression. We have thus found a subset $A\cap J$ with more structure, and the density of $A\cap J$ in $J$ is larger than the original density. In this way, we can increase the density until it becomes so large the the theorem is trivial, so we get the result.
To add more detail to deducing Roth's theorem from the lemma, let $\delta_0$ be the infimum of the densities for which Roth's theorem holds. For $\delta>\frac{2}{3}$, the set $A$ even contains three consecutive elements by the pigeonhole principle, so $\delta_0\leq \frac{2}{3}$. By the structure increasing principle, either (i) holds and we are done, or we find an arithmetic progression $J=\{x_1,...,x_{|J|}\}$ (with $x_1<...<x_{|J|}$) having the property (ii). The subset $A\cap J$ of $J$ is cleraly contains a three term arithmetic progression if and only if it contains $x_i,x_j,x_k$ such that $j=\frac{i+k}{2}$. We know that for $N$ large enough (that is, $|J|$ large enough), any subset of the index set $\{1,2,...,|J|\}$ with density $\geq \delta_0+\frac{\delta_0^2}{32}$ contains an arithmetic progression of length $3$ (since $\delta_0$ was the infimum). Hence $A\cap J$ has three elements that form an arithmetic progression, and the proof is complete. ■
It is good to note that proofs of many other theorems from Ramsey theory also involve some structure increasing principle. For example, a standard proof of van der Waerden's proof proceeds by using induction on $r$ (as well as $k$ and $\ell$) to show that if a large set colored with $\ell$ colors fails to have an arithmetic progression of length $k$, then it contains $r$ monochromatic arithmetic progressions of length $k-1$, each having a different color, so when we reach $r=k+1$, the statement is proved.
In the rest of this post, we use discrete Fourier analysis to prove the crucial lemma for Roth's theorem, and then discuss some strengthenings of the proof.
Proof of Roth's theorem
To count the number of three term arithmetic progressions in $A$, we can use the sum expression
\[\begin{eqnarray}\sum_{k+n=2m}1_A(k)1_A(m)1_A(n),\end{eqnarray}\]
where $1_A(n)$ is the indicator of $A$, that is it yields $1$ if $n\in A$ and $0$ otherwise.
However, this expression on its own is not of much help, so we consider the more general expression
\[\begin{eqnarray}\sum_{k+n=2m}f_1(k)f_2(m)f_3(n).\end{eqnarray}\]
So far in the earlier posts, we have had periodic functions for which we have formed Fourier series. Now we embed $A$ into $\mathbb{Z}_N=\mathbb{Z}/N\mathbb{Z}$ in the trivial way, and for functions $f:\mathbb{Z}_N\to \mathbb{C}$, we define the discrete Fourier transform
\[\begin{eqnarray}\hat{f}(r)=\sum_{k=0}^{N-1}f(k)e^{-2\pi i \frac{rk}{N}}.\end{eqnarray}\]
Similarly to the case of Fourier series, we have Plancherel's formula
\[\begin{eqnarray}\sum_{r=0}^{N-1}|\hat{f}(r)|^2=N\sum_{k=0}^{N-1}|f(k)|^2,\end{eqnarray}\]
but the proof is now easier as there are no infinite sums or integrals. From the orthogonality of the functions $r\mapsto e^{-2\pi i \frac{kr}{N}}$, $k=0,1,...,N-1$, one immediately obtains the inversion formula
\[\begin{eqnarray}f(k)=\frac{1}{N}\sum_{r=0}^{N-1}\hat{f}(r)e^{2\pi i \frac{kr}{N}}.\end{eqnarray}\]
Now, if $f_1,f_2,f_3:\mathbb{Z}_N\to \mathbb{C}$, the inversion formula gives
\[\begin{eqnarray}\sum_{k+n=2m\atop k,m,n \in \mathbb{Z}_N}\hat{f}_1(k)\hat{f}_2(m)\hat{f}_3(n)&=&\frac{1}{N^3}\sum_{k+n=2m \atop k,m,n \in \mathbb{Z}_N}\sum_{a,b,c\in \mathbb{Z}_N}\hat{f}_1(a)\hat{f}_2(b)\hat{f}_3(c)e^{2\pi i\frac{ak+bm+cn}{N}}\\&=&\frac{1}{N^3}\sum_{a,b,c\in \mathbb{Z}_N}\hat{f}_1(a)\hat{f}_2(b)\hat{f}_3(c)\sum_{k+n=2m \atop k,m,n \in \mathbb{Z}_N}e^{2\pi i\frac{ak+bm+cn}{N}}\\&=&\frac{1}{N^3}\sum_{a,b,c\in \mathbb{Z}_N}\hat{f}_1(a)\hat{f}_2(b)\hat{f}_3(c)\sum_{k,n \in \mathbb{Z}_N}e^{2\pi i \frac{k(a+\frac{b}{2})}{N}}e^{2\pi i \frac{n(\frac{b}{2}+c)}{N}}.\end{eqnarray}\]
Without loss of generality, $N$ can be taken to be odd. By orthogonality, the sum of exponentials in the last expression is $0$ unless $a\equiv -\frac{b}{2}\equiv c \pmod N$, in which case the sum equals $N^2$. We arrive at
\[\begin{eqnarray}\sum_{k+n=2m\atop k,m,n \in \mathbb{Z}_N}f_1(k)f_2(m)f_3(n)=\frac{1}{N}\sum_{a\in \mathbb{Z}_N}\hat{f}_1(a)\hat{f}_2(-2a)\hat{f}_3(a).\end{eqnarray}\]
Now the Cauchy-Schwarz inequality gives
\[\begin{eqnarray}\left|\sum_{k+n=2m\atop k,m,n \in \mathbb{Z}_N}f_1(k)f_2(m)f_3(n)\right|\leq \frac{1}{N}\max_{a\in \mathbb{Z}_N} |\hat{f}_i(a)|\left(\sum_{b\in \mathbb{Z_N}} |\hat{f}_{j}(b)|^2 \sum_{c\in \mathbb{Z}_N} |\hat{f}_k(c)|^2\right)^{\frac{1}{2}}\quad \quad (1).\end{eqnarray}\]
for any permutation $(i,j,k)$ of $\{1,2,3\}$ (since $x\mapsto 2x$ is a bijection in $\mathbb{Z}_N$ for odd $N$). Plancherel's formula says that the right-hand side is
\[\begin{eqnarray}\max_{a\in Z_N} |\hat{f}_i(a)|\left(\sum_{b\in \mathbb{Z_N}} |f_{j}(b)|^2 \sum_{c\in \mathbb{Z}_N} |f_k(c)|^2\right)^{\frac{1}{2}}\end{eqnarray}\]
Let $|A|=\delta N$. The functions we choose will be of the form $f_i(n)=\delta 1_{[1,N]}(n)$ and $f_i(n)=1_A(n)-\delta 1_{[1,N]}(n)$ (we can of course extend these functions to $\mathbb{Z}_N$), and we will later exploit the fact that $1_A-\delta 1_{[1,N]}$ has average $0$ and that the function $\delta 1_{[1,N]}(n)$ is easy to deal with.
Assume that Roth's theorem fails for $A$. Then
\[\begin{eqnarray}\sum_{k+n=2m\atop k,m,n \in \mathbb{Z}_N}1_A(k)1_A(m)1_A(n)=0\quad \quad (2).\end{eqnarray}\]
On the other hand, by writing $1_A=(1_A-\delta 1_{[1,N]})+\delta 1_{[1,N]}$, this sum decomposes into eight parts, such as
\[\begin{eqnarray}\sum_{k+n=2m\atop k,m,n\in \mathbb{Z}_N}(1_A(k)-\delta 1_{[1,N]}(k))\cdot \delta 1_{[1,N]}(m)(1_A(n)-\delta 1_{[1,N]}(n)).\end{eqnarray}\]
The part
\[\begin{eqnarray}\delta^3 \sum_{k+n=2m\atop k,m,n \in \mathbb{Z}_N}1_{[1,N]}(k)1_{[1,N]}(m)1_{[1,N]}(n)\end{eqnarray}\]
represents how many three term arithmetic progressions we expect to find in a random subset of $\mathbb{Z}_N$, and it is $\delta^3\left\lfloor\frac{N}{2} \right\rfloor^2+\delta^3\left\lceil \frac{N}{2} \right\rceil^2\geq \frac{\delta^3N^2}{2}$.
By $(2)$, also one of the seven other parts to which the sum $(2)$ decomposes has size at least $\frac{\delta^3 N^2}{14}$. Since
\[\begin{eqnarray}\left(\sum_{k=0}^{N-1}|1_A(k)-\delta 1_{[1,N]}(k)|^2\right)^{\frac{1}{2}}&\leq& \sqrt{N},\\\left(\sum_{k=0}^{N-1}|\delta 1_{[1,N]}(k)|^2\right)^{\frac{1}{2}}&=&\delta \sqrt{N},\end{eqnarray}\]
the inequality $(1)$ for the functions $\delta1_{[1,N]}-1_A,\delta1_{[1,N]}, \delta1_{[1,N]}-1_A$ gives
\[\begin{eqnarray}\max_{a\in \mathbb{Z}_N}|\hat{1}_A(a)-\delta \hat{1}_{[1,N](a)}|\geq \frac{\delta^2 N^2}{14}.\end{eqnarray}\]
Let $r$ be the element that attains the maximum above. Then
\[\begin{eqnarray}\left|\sum_{k=0}^{N-1}(1_A(k)-\delta 1_{[1,N](k)})e^{2\pi i \frac{rk}{N}}\right|\geq \frac{\delta^2 N^2}{14}\quad \quad (3).\end{eqnarray}\]
The next step is to divide $[1,N]$ into long disjoint arithmetic progressions $(J_m)_{m=1}^{M}$ that almost cover it and in which the phase $e^{2\pi i \frac{rk}{N}}$ varies only little. This is achieved using the following lemma.
Lemma 5. Let $\varepsilon>0$ be fixed, $N$ a large positive integer and $r$ an integer. Then we can choose finite arithmetic progressions $J_m,m=1,...,M$ such that
(i) We have a partition
\[\begin{eqnarray}[1,N]\cap \mathbb{Z}=E\cup\bigcup_{m=1}^M J_m,\end{eqnarray}\]
where $|E|<\varepsilon N$
(ii) $|J_m|\geq\frac{1}{7}\varepsilon \sqrt{N}$
(iii) $|e^{2\pi i \frac{ak}{N}}-e^{2\pi i k \frac{a\ell}{N}}|\leq \varepsilon$ for $k,\ell \in J_m$.
Proof. By the pigeonhole principle, we can find a number $0<r'\leq \sqrt{N}$ for which $rr'\pmod N\leq \sqrt{N}$ (where $x\pmod N$ is an integer from $[0,N-1]$). Then, if $k=r's+d$ and $\ell=r't+d$, $s,t,d\in \mathbb{Z}$, we have
\[\begin{eqnarray}|e^{2\pi i \frac{rk}{N}}-e^{2\pi i k \frac{r\ell}{N}}|\leq \left\|2\pi \frac{r(k-\ell)}{N}\right\|\leq \left|2\pi \frac{s-t}{\sqrt{N}}\right|,\end{eqnarray}\]
where $\|\cdot\|$ denotes the distance to the nearest integer. Therefore, if we take the finite arithmetic progressions $r's+d,d=0,...,a'-1$ (where $s=0,...,\frac{N}{r'}$ so that the lengths are $\geq \sqrt{N}$) and chop them into pieces of length $\lfloor \frac{1}{2\pi}\varepsilon \sqrt{N}\rfloor$ (there will of course be some excess terms), the number of excess elements is in total bounded by $\varepsilon \sqrt{N}r'\leq \varepsilon N$. Moreover, if $s$ and $t$ are from the same piece, it holds that
\[\begin{eqnarray}\left|2\pi \frac{s-t}{\sqrt{N}}\right|\leq \varepsilon.\end{eqnarray}\]
Finally, since the length of a piece is of $r's+d$ was $\lfloor \frac{1}{2\pi}\varepsilon \sqrt{N}\rfloor$, we have constructed the progressions $J_m.$ ■
Now we return to the proof of Roth's theorem. The inequality $(3)$ implies
\[\begin{eqnarray}\sum_{m=1}^M\left|\sum_{k\in J_m}(1_A(k)-\delta 1_{[1,N](k)})e^{2\pi i \frac{rk}{N}}\right|\geq \frac{\delta^2 N^2}{14}+O(\varepsilon N),\end{eqnarray}\]
where the constant in the big $O$ can be taken as $1$. Choose $\varepsilon=\frac{1}{1000}\delta^2$. Then by the property (iii) in the lemma, we can get rid of the phase factor with very minor losses. In other words,
\[\begin{eqnarray}\sum_{m=1}^M\left|\sum_{k\in J_m}(1_A(k)-\delta 1_{[1,N](k)})\right|\geq \frac{\delta^2 N^2}{15}+O(N).\end{eqnarray}\]
The inner sum is equal to $|A\cap J_m|-\delta |J_m|$. We apply one more trick. We add to both sides the sum
\[\begin{eqnarray}\sum_{m=1}^{M}(|A\cap J_m|-\delta |J_m|),\end{eqnarray}\]
and use $x+|x|=2\max\{0,x\}$. Then we get
\[\begin{eqnarray}\sum_{m=1}^M\left(2\max\left\{0,(|A\cap J_m|-\delta |J_m|)\right\}-\frac{\delta^2}{16}|J_m|\right)\geq \frac{\delta^2}{1000}N^2+O(N)\quad \quad (4)\end{eqnarray}\]
By the pigeonhole principle, for $N$ large enough, the sum has some positive term, so for some $m$ we have
\[\begin{eqnarray}2(|A\cap J_m|-\delta |J_m|)\geq \frac{\delta^2}{16}|J_m|,\end{eqnarray}\]
and this is what the structure increasing lemma claims. ■
Strengthening of Roth's theorem
The proof actually tells us a more than what we have stated. Let $r_3(N)$ be the largest size of a subset of $\{1,2,..,N\}$ such that it is free of three term arithmetic progressions. The theorem states $r_3(N)=o(N)$, but what the proof gives, and what Roth also obtained, is the following.
Theorem 6. One has $r_3(N)\ll \frac{N}{\log \log N}$.
Proof. Let $A$ be a subset of $\{1,2,...,N\}$ with densty $\delta.$ From the proof above, we see that we can find a progression $J$ such that $|A\cap J|\geq ( \delta+\frac{\delta^2}{32})|J|$ unless $N\leq c\delta^{-2}$ for an absolute constant $c$ (this is due to $(4)$).
Therefore, we actually have the following result: For any $k$, if $f_k$ denotes the $k$th iterate of $x\mapsto x+\frac{x^2}{32}$ and $g_k$ denotes the $k$th iterate of $x\mapsto c_0\sqrt{x}$, then either
(a) $g_k(N)\leq c\delta^{-2} $ or
(b) There is an arithmetic progression $J_k'$ of length $|J_k'|\geq g_{k+1}(N)$ such that $\frac{|A\cap J_k'|}{|J_k'|}\geq f_k(\delta)$. (the bound $c\delta^{-2}$ does not grow in iteration, since increasing $\delta$ means decreasing $\delta^{-1}$).
The case $k=0$ is the structure increasing lemma, and the above is just an iteration of that lemma. Suppose that our set has no three term arithmetic progression. If the case (a) never occurs until $f_k(\delta)>1$, while still having $g_k(N)\geq 1$, we have a contradiction, since no subset can have density greater than $1$ in some arithmetic progression.
We have $f_k(\delta)\geq \delta+\frac{k}{32}\delta^2$, so after $\frac{32}{\delta}$ iterations the density is at least $2\delta$. Similarly, in $\frac{32}{\delta}+\frac{16}{\delta}$ steps the density exceeds $4\delta$. Continuing in this way, in less that $\frac{64}{\delta}$ steps the density has exceeded $1$ if (a) has not occurred so far.
We arrive at $k=\frac{64}{\delta}$ (or actually the nearest integer to $\frac{64}{\delta}$), in such a way that (a) has never happened and $g_k(N)\geq 1$, if we show that $g_k(N)\geq \delta^{-2}>\max\{1,c\delta^{-2}\}$ (we had $c<1$). Then we have a contradiction because the density of a subset is then greater than $1$.
The iterated function $g_k$ satisfies $g_k(N)\geq c_0^2 N^{\frac{1}{2^k}}$. Therefore, we need to show that this is at least $\delta^{-1}$, and hence $\frac{1}{2^k}\log N\geq C\log \delta^{-1}+c_1$ . This means $\log N\geq (C\log \delta^{-1}+c_1)2^{\frac {64}{\delta}}$.This leads to $\log N\gg 2^{\frac{c'}{\delta}}$ as $\delta \to \infty$, so $N\gg\exp(\exp(\frac{c'}{\delta}))$. This was enough to give a contradiction, and hence the existence of an arithmetic progression, so $r_3(N)\leq\delta N\ll \frac{N}{\log \log N}.$■
Quite surprisingly, the bound $\frac{N}{\log \log N}$ is not very weak; it was proved by Behrend in 1946 that $r_3(N)\gg N\exp(-c\sqrt{\log N})$ for some constant $c$, and the proof uses (among other things) the simple fact that a line intersects a sphere in at most two points.
