Roth’s theorem and the density increment method

Roth proved in 1953 that every subset of the integers with positive density contains a three-term arithmetic progression. More precisely, if A\subseteq{1,2,\ldots,N} contains no three distinct numbers of the form \displaystyle a, a+d, a+2d, then \displaystyle |A|=o(N) . In other words, a set that avoids three-term progressions must occupy a smaller and smaller proportion of the integers as the interval becomes larger.

Roth’s proof introduced a useful way of thinking about such problems. Suppose a set has relatively large density but contains no arithmetic progressions. A random set of the same density would contain many progressions, so something must be unusual about our set. Roth used Fourier analysis to detect this unusual behaviour and then found a smaller arithmetic region on which the set has even greater density. Repeating this process eventually gives a contradiction, because the density of a set cannot exceed one. We will study this argument in a simpler setting, replacing the integers by the finite vector space \displaystyle G=\mathbb F_3^n. Here every element is a vector of n coordinates, each belonging to {0,1,2} , and all arithmetic is modulo three. The group has N=3^n elements. A three-term arithmetic progression is \displaystyle x, x+h, x+2h. When h\neq0 , these are three distinct points. In fact, they are precisely the three points on an affine line in \mathbb F_3^n .

We want to know how large a subset A\subseteq G can be if it contains no such progression. We will prove

\displaystyle |A|\le\frac{7\cdot3^n}{n}.

The constant 7 is not important. What matters is that the density is O(1/n) . The argument is a finite-field version of Roth’s density increment method, and the geometry is much simpler than in the integers: instead of looking for long arithmetic progressions on which the density increases, we only need to find a denser affine hyperplane.

Counting arithmetic progressions

Let f=1_A be the indicator function of A , and write

\displaystyle \alpha=\mathbb E_xf(x)=\frac{|A|}{N}

for its density. Consider the average

\displaystyle T(f)=\mathbb E_{x,h}f(x)f(x+h)f(x+2h).

This counts three-term arithmetic progressions, divided by N^2 . If we took a random set of density \alpha , we would expect this average to be roughly \alpha^3 , since each of the three points would have probability about \alpha of belonging to the set. But our set contains no nontrivial progressions. The only terms that survive are those with h=0 . For these terms, \displaystyle f(x)f(x)f(x)=f(x). Therefore

\displaystyle T(f)=\frac{\alpha}{N}.

So the number of progressions is much smaller than we would expect from a random set, unless \alpha is already very small. How can we use this? The idea is to express the progression count in terms of Fourier coefficients. If the count is unusually small, we will see that some Fourier coefficient must be unusually large.

Large Fourier coefficient

Let \omega=e^{2\pi i/3} . For \xi\in G , define

\displaystyle \widehat f(\xi)=\mathbb E_xf(x)\omega^{-\xi\cdot x}.

Fourier inversion gives

\displaystyle f(x)=\sum_{\xi\in G}\widehat f(\xi)\omega^{\xi\cdot x}.

Substitute this into the progression count. We get a sum of terms involving

\displaystyle \mathbb E_{x,h}\omega^{\xi_1\cdot x+\xi_2\cdot(x+h)+\xi_3\cdot(x+2h)}.

By character orthogonality, this average is zero unless

\displaystyle \xi_1+\xi_2+\xi_3=0,\qquad \xi_2+2\xi_3=0.

Since we are working in characteristic three, these equations give

\displaystyle \xi_1=\xi_2=\xi_3.

Hence the progression count has the particularly simple expression

\displaystyle T(f)=\sum_{\xi\in G}\widehat f(\xi)^3.

The Fourier coefficient at zero is just the density: \displaystyle \widehat f(0)=\alpha.

Thus

\displaystyle T(f)=\ \alpha^3+\sum_{\xi\neq0}\widehat f(\xi)^3.

The first term is exactly what we expected for a random set. The remaining Fourier coefficients must account for the difference.

Using the triangle inequality, followed by Parseval’s identity,

\displaystyle \begin{aligned} \alpha^3-\frac{\alpha}{N} &\le\sum_{\xi\neq0}|\widehat f(\xi)|^3\\ &\le \left(\max_{\xi\neq0}|\widehat f(\xi)|\right) \sum_\xi|\widehat f(\xi)|^2\\ &= \alpha\max_{\xi\neq0}|\widehat f(\xi)|. \end{aligned}

We used \sum_\xi|\widehat f(\xi)|^2=\mathbb E_x f(x)^2=\alpha . Dividing by \alpha , we obtain

\displaystyle \max_{\xi\neq0}|\widehat f(\xi)| \ge\alpha^2-\frac1N.

In particular, provided \displaystyle \alpha^2\ge\frac2N, there is some nonzero frequency \xi with

\displaystyle |\widehat f(\xi)|\ge\frac{\alpha^2}{2}.

This is our first useful conclusion. If the set is not already very sparse, the absence of progressions forces a large nontrivial Fourier coefficient. What does that coefficient tell us about the set?

Density Increment

Fix the frequency \xi\neq0 . Consider the three parallel hyperplanes

\displaystyle H_j={x\in G:\xi\cdot x=j},\qquad j=0,1,2.

Each contains exactly N/3 points. Let \alpha_j be the density of A in H_j . Since these three hyperplanes partition the whole space,

\displaystyle \alpha=\frac{\alpha_0+\alpha_1+\alpha_2}{3}.

Now write the Fourier coefficient in terms of these densities:

\displaystyle f(\xi) = \frac13\left(\alpha_0+\omega^{-1}\alpha_1+\omega^{-2}\alpha_2\right).

If the set had exactly the same density on all three hyperplanes, this expression would vanish, because 1+\omega+\omega^2=0 . So a large Fourier coefficient tells us that the densities \alpha_0,\alpha_1,\alpha_2 are not all close to their average. We should therefore be able to find one hyperplane where the density is noticeably larger than \alpha .

Let \displaystyle \Delta=\max_j(\alpha_j-\alpha). Since the three deviations from the average sum to zero, each deviation has absolute value at most 2\Delta . It follows that

\displaystyle |\widehat f(\xi)|\le2\Delta.

Combining this with our lower bound \displaystyle |\widehat f(\xi)|\ge\frac{\alpha^2}{2}. gives

\displaystyle \Delta\ge\frac{\alpha^2}{4}.

Thus, on at least one of the hyperplanes,

\displaystyle \alpha_j\ge\alpha+\frac{\alpha^2}{4}.

This is the main step of the proof. We have found a hyperplane of dimension n-1 where the set has greater density than it did in the original space. The intersection of A with this hyperplane is still progression-free. We can identify the hyperplane with \mathbb F_3^{n-1} and apply the same argument again. So, as long as the density is not already tiny relative to the size of the space, we can go down one dimension and increase the density by at least \alpha^2/4 .

Repeating the argument

Suppose we continue restricting to denser hyperplanes, obtaining densities

\displaystyle \alpha_0,\alpha_1,\ldots,\alpha_t.

At every successful step,

\displaystyle \alpha_{j+1}\ge\alpha_j+\frac{\alpha_j^2}{4}.

How many times can this happen? The increment gets larger as the density increases, so it is convenient to look at the reciprocal density. We have

\displaystyle \begin{aligned} \frac1{\alpha_j}-\frac1{\alpha_{j+1}} &\ge \frac1{\alpha_j} -\frac1{\alpha_j+\alpha_j^2/4}\\ &=\frac1{4+\alpha_j} \ge\frac15, \end{aligned}

since \alpha_j\le1 . Thus every step decreases the reciprocal density by at least 1/5 . As reciprocal densities remain positive, there can be at most 5/\alpha_0 successful steps.

Suppose the process stops when the remaining space has dimension d and the set has density \beta . It can stop only when our Fourier argument no longer guarantees an increment, namely when

\displaystyle \beta^2<\frac2{3^d}.

But the densities have been increasing, so \beta\ge\alpha_0 . Therefore

\displaystyle d<\log_3\left(\frac2{\alpha_0^2}\right).

We started in dimension n . Each successful step removes one dimension, so

\displaystyle n \le\frac5{\alpha_0}+\log_3\left(\frac2{\alpha_0^2}\right).

Using the elementary estimate \log_3(2/\alpha_0^2)\le2/\alpha_0 for 0<\alpha_0\le1 , we get

\displaystyle n\le\frac7{\alpha_0}.

Hence

\displaystyle \alpha_0\le\frac7n,

or equivalently,

\displaystyle |A|\le\frac{7\cdot3^n}{n}.

This proves the theorem.

The proof is worth remembering because of the way the different steps fit together. We were looking for arithmetic progressions, but Fourier analysis did not directly produce one. Instead, it told us that if there were no progressions, the set could not be evenly distributed across certain hyperplanes. We then used this uneven distribution to pass to a smaller space with greater density. There are really two possibilities at each stage. Either the set is already sparse enough that the desired bound is approaching, or we can find a smaller region where it is denser. The second possibility cannot keep happening, because density cannot exceed one. This is the main idea behind Roth’s method. A lack of arithmetic progressions gives a large Fourier coefficient, and a large Fourier coefficient gives a density increment. Repeating the increment eventually becomes impossible. The finite-field setting makes the proof especially clean. A nonzero Fourier frequency divides the space into three parallel hyperplanes, and we can restrict to one of them without changing the kind of problem we are studying. For subsets of the integers, the corresponding argument is more involved: one has to find suitable long arithmetic progressions on which the density increases, and carefully keep track of their lengths.

The bound here is not the strongest one available. Meshulam proved in 1995 that a progression-free subset of \mathbb F_3^n has size at most 2\cdot3^n/n . But the simpler proof is useful because it shows the method with almost no extra machinery. The main point is that Fourier analysis gives us a way to turn a missing pattern into useful information about where the set is concentrated. Once we have found that concentration, we can repeat the problem on a smaller space. This combination of Fourier analysis and density increments is one of the basic ideas behind Roth’s theorem and much of additive combinatorics.

Leave a Reply