Roth’s theorem using energy increment

Roth’s theorem says that a subset of the integers with positive density must contain a three-term arithmetic progression. More precisely, if $A\subseteq\{1,\ldots,N\}$ contains no three distinct numbers of the form $x,x+d,x+2d$ , then $|A|=o(N)$ . In the previous post, we considered the same problem in the finite vector space $G=\mathbb F_3^n$ . We used Fourier analysis to show that if a set contains no nontrivial three-term progressions, then we can find a hyperplane on which its density is larger. Restricting to that hyperplane gives a smaller vector space with a denser progression-free set. We can repeat this process, but not indefinitely, since the density cannot exceed one. This density increment argument proves required Roth’s theorem and bounds the density of sets without three term arithmetic progressions.

There is another way to use Fourier analysis. Instead of selecting one hyperplane and discarding the rest of the space, we keep the whole space and divide it into smaller pieces. We then study how the set is distributed across these pieces. If its distribution is uneven, we refine the partition to reveal more of that variation. The quantity we track is the average square of the densities on the different pieces. This quantity increases whenever we make a useful refinement, but it is always bounded above by one.

This is the energy increment method. We will use it to prove that, for every fixed $\alpha>0$ , every sufficiently large vector space $\mathbb F_3^n$ has the property that any subset of density at least $\alpha$ contains a nontrivial three-term arithmetic progression. The proof gives a much weaker quantitative bound than the earlier density-increment argument. But it illustrates a useful idea: rather than looking for one region of greater density, we make a partition increasingly regular until we can count arithmetic progressions on most of its parts.

Energy

Let $A\subseteq G=\mathbb F_3^n$ , and write $\alpha=|A|/3^n$ for its density. Suppose we divide $G$ into three parallel affine hyperplanes $C_0,C_1,C_2$ , and let $\alpha_0,\alpha_1,\alpha_2$ denote the density of $A$ on each. Since the hyperplanes have equal sizes and together cover the entire space, their average density is the original density, so $(\alpha_0+\alpha_1+\alpha_2)/3=\alpha$ . Now consider the average of the squares of these densities:

$\displaystyle \mathcal E=\frac{\alpha_0^2+\alpha_1^2+\alpha_2^2}{3}.$

Why take the squares? The point is that the average density does not tell us how evenly the set is distributed. For example, suppose the original density is $1/3$ . If each hyperplane also has density $1/3$ , then $\mathcal E=1/9$ . But if the entire set lies in one hyperplane, the three densities are $1,0,0$ , and $\mathcal E=1/3$ . The average density is unchanged, but the average square has increased. In general, expanding the squares gives

$\displaystyle \mathcal E-\alpha^2=\frac13\sum_{j=0}^{2}(\alpha_j-\alpha)^2.$

Thus $\mathcal E\ge\alpha^2$ , with equality precisely when all three densities are equal. The difference $\mathcal E-\alpha^2$ measures how much the densities vary between the hyperplanes. We can define the same quantity for any partition into cosets of a subspace. Let $H\le G$ be a vector subspace. Its cosets $C=x+H$ partition $G$ into equally sized pieces. Write $\alpha_C=|A\cap C|/|H|$ for the density on a coset, and define

$\displaystyle \mathcal E(H)=\underset{C\in G/H} {\mathbb E} \alpha_C^2.$

The average of the $\alpha_C$ is $\alpha$ , and every density lies between zero and one. Consequently, $\alpha^2\le\mathcal E(H)\le\alpha\le1$ . In particular, energy cannot increase beyond one.

The main property we need is that refining a partition cannot decrease its energy. Suppose we divide one coset $C$ into $m$ equally sized smaller cosets with densities $\beta_1,\ldots,\beta_m$ . Their average is the old density $\alpha_C$ . The change in the local average square is

$\displaystyle \frac1m\sum_{j=1}^{m}\beta_j^2-\alpha_C^2=\frac1m\sum_{j=1}^{m}(\beta_j-\alpha_C)^2\ge0.$

The energy therefore increases whenever the smaller pieces have different densities. This gives us a way to keep track of refinements. If the set is distributed irregularly inside a coset, we would like to divide that coset in a way that reveals the irregularity. The energy will then increase by an amount we can estimate.

Regular and Irregular Cosets

Suppose $C=x_0+H$ is one coset of our current subspace $H$ . We identify $C$ with $H$ by writing its elements as $x_0+y$ , where $y\in H$ . Define $f_C(y)=1_A(x_0+y)$ . Its average over $H$ is $\alpha_C$ . We want to count three-term progressions lying entirely inside $C$ . Since their common difference must belong to $H$ , the relevant average is

$\displaystyle T_C=\underset{y,h\in H} {\mathbb E} f_C(y)f_C(y+h)f_C(y+2h).$

As in the earlier proof of Roth’s theorem, Fourier analysis gives $T_C=\sum_{\xi\in\widehat H}\widehat f_C(\xi)^3$ , where $\widehat H$ denotes the characters of $H$ . These are the functions $y\mapsto\omega^{\ell(y)}$ , where $\omega=e^{2\pi i/3}$ and $\ell:H\to\mathbb F_3$ is a linear functional. The coefficient at zero is $\widehat f_C(0)=\alpha_C$ . Hence

$\displaystyle T_C=\alpha_C^3+\sum_{\xi\neq0}\widehat f_C(\xi)^3.$

The first term is the progression count we would expect from a random set of density $\alpha_C$ . The other terms measure the difference between the actual count and this prediction.

Suppose that every nonzero Fourier coefficient satisfies $|\widehat f_C(\xi)|\le\eta$ , where $\eta>0$ is a small parameter that we will choose later. By the triangle inequality and Parseval,

$\displaystyle \left|T_C-\alpha_C^3\right|\le\sum_{\xi\neq0}|\widehat f_C(\xi)|^3\le\eta\sum_\xi|\widehat f_C(\xi)|^2=\eta\alpha_C.$

Therefore

$\displaystyle T_C\ge\alpha_C^3-\eta\alpha_C.$

This is the estimate we need. If all nonzero Fourier coefficients are small, we can count progressions inside the coset almost as though the set were random. We will call such a coset regular. A coset is irregular if at least one nonzero Fourier coefficient has magnitude greater than $\eta$ . Our aim is not to make every coset regular. It will be enough if only a small proportion are irregular, since we can ignore those exceptional cosets when counting progressions. The next question is how to reduce their number. A large Fourier coefficient will tell us how to refine the partition so that the energy increases.

Energy Increment

Suppose $C=x_0+H$ is irregular. Then there is a nonzero linear functional $\ell:H\to\mathbb F_3$ such that $|\widehat f_C(\ell)|>\eta$ . Use this functional to divide $C$ into three smaller affine hyperplanes, according to whether $\ell(y)=0,1$ , or $2$ . Let their densities be $\beta_0,\beta_1,\beta_2$ . Their average is $\alpha_C$ . The Fourier coefficient can be written as

$\displaystyle \widehat f_C(\ell)=\frac13\left(\beta_0+\omega^{-1}\beta_1+\omega^{-2}\beta_2\right).$

Parseval’s identity on the three-element group gives

$\displaystyle \frac13\sum_{j=0}^{2}(\beta_j-\alpha_C)^2=2|\widehat f_C(\ell)|^2>2\eta^2.$

The left side is exactly the increase in the average square density caused by this three-way split. Thus the large Fourier coefficient tells us how to refine the coset, and it guarantees an energy increase of at least $2\eta^2$ .

Now suppose at least a proportion $\delta$ of the cosets of our current subspace $H$ are irregular. For each irregular coset, choose one linear functional witnessing its irregularity. We would like to refine all these cosets simultaneously. There is a small point here. We want the new partition to consist of cosets of a single subspace, rather than choosing unrelated partitions of different cosets. To arrange this, let $H'$ be the intersection of the kernels of all the chosen linear functionals on $H$ . Every old coset of $H$ is then divided into cosets of $H'$ .

Inside each irregular coset, this new partition is at least as fine as the three-way split given by its chosen Fourier coefficient. Further refinement cannot decrease energy, so every irregular coset still contributes an increase of at least $2\eta^2$ to its local average square. Since at least a proportion $\delta$ of the cosets are irregular, the total energy increases by at least

$\displaystyle \mathcal E(H')-\mathcal E(H)\ge2\delta\eta^2.$

This is the energy increment. We have found a refinement that makes a definite amount of progress whenever too many cosets are irregular. But energy is always at most one. Therefore we cannot keep increasing it by $2\delta\eta^2$ indefinitely. After at most $1/(2\delta\eta^2)$ successful refinements, we must reach a subspace $H$ for which fewer than a proportion $\delta$ of the cosets are irregular.

We should also check how much the dimension decreases. Suppose the current subspace has codimension $k$ in $G$ . Then it has $3^k$ cosets. We choose at most one linear equation for each irregular coset, so we impose at most $3^k$ new equations. The codimension of the new subspace is therefore at most $k+3^k$ . This can grow very quickly. Nevertheless, the number of refinement steps is bounded in terms of $\delta$ and $\eta$ alone. We start with $H=G$ , which has codimension zero, and at each step the codimension is bounded by a function of its previous value. Consequently, the final codimension is bounded by some constant depending only on $\delta,\eta$ , not on the original dimension $n$ .

We have now proved the regularity statement needed for Roth’s theorem: for any fixed $\delta,\eta>0$ , we can partition the space into cosets of a subspace of bounded codimension so that all but a proportion $\delta$ of those cosets are regular.

Counting Progressions in the Regular Partition

We can now finish the proof. Let $\alpha>0$ be the original density, and choose $\eta=\alpha^2/4$ and $\delta=\alpha^3/4$ . By the energy-increment argument, there is a subspace $H$ whose codimension is bounded in terms of $\alpha$ alone, such that fewer than a proportion $\delta$ of its cosets are irregular.

On every regular coset $C$ , we have the progression estimate $T_C\ge\alpha_C^3-\eta\alpha_C$ . On an irregular coset, we simply use $T_C\ge0$ , since the progression count is always nonnegative. Average over all cosets. Discarding the irregular cosets loses at most $\delta$ from the average of $\alpha_C^3$ , because each $\alpha_C^3$ is at most one. The error term from the regular cosets is at most $\eta \mathop{\mathbb E}\limits_C \alpha_C=\eta\alpha$ .

Finally, the average of the densities is $\alpha$ , so convexity gives $\mathbb E_C\alpha_C^3\ge\alpha^3$ . Putting everything together,

$\displaystyle \underset{C}{\mathbb E} ~ T_C\ge\alpha^3-\delta-\eta\alpha=\frac{\alpha^3}{2}.$

This says that if we first choose a random coset of $H$ , and then choose a random three-term progression inside that coset, the probability that all three points belong to $A$ is at least $\alpha^3/2$ . In particular, we have found many progressions, provided the subspace $H$ is large enough that they cannot all be trivial.

Now suppose, for a contradiction, that $A$ contains no nontrivial three-term arithmetic progression. Inside any coset $C=x_0+H$ , the only contributing progressions have common difference $h=0$ . Their contribution is therefore exactly $T_C=\alpha_C/|H|$ .

Averaging over cosets gives $\underset{C}{\mathbb E} ~T_C=\alpha/|H|$ . Comparing this with our lower bound,

$\displaystyle \frac{\alpha}{|H|}\ge\frac{\alpha^3}{2},\qquad\text{so}\qquad |H|\le\frac2{\alpha^2}.$

But this is impossible when $n$ is sufficiently large. Our construction gives a subspace $H$ whose codimension is bounded by some constant $K(\alpha)$ depending only on the original density. Hence $\dim H\ge n-K(\alpha)$ , and so $|H|\ge3^{n-K(\alpha)}$ . For sufficiently large $n$ , this is greater than $2/\alpha^2$ , contradicting the preceding inequality. Therefore every subset of fixed positive density in a sufficiently large vector space $\mathbb F_3^n$ contains a nontrivial three-term arithmetic progression.

This proves the finite-field version of Roth’s theorem. It is useful to compare this with the earlier density-increment proof. There, a large Fourier coefficient gave us one hyperplane on which the density was larger. We restricted to that hyperplane and repeated the argument in a smaller space. The density kept increasing until the process could no longer continue.

Here we never select one hyperplane and discard everything else. We keep the whole space and refine its partition. If many cosets have large Fourier coefficients, we split them in directions that reveal their uneven distribution. The average square density increases, and because it is bounded, this process must eventually stop. At the final stage, almost every coset has small nonzero Fourier coefficients. On those cosets, the three-term progression count is close to what we would expect from a random set with the same density. Averaging over the cosets then gives many progressions in the original set. The only way a progression-free set could survive would be if the final subspace were very small. But the energy argument guarantees that its codimension is bounded independently of $n$ , so this cannot happen when the original dimension is large. The price is a much weaker quantitative estimate. The codimension may grow very rapidly during refinement, because at each stage we may have to impose one linear condition for every irregular coset.

Unlike the earlier density-increment argument, this proof does not give the bound $O(1/n)$ . The point of the method is different. It shows how to make a partition regular by repeatedly exposing the variation hidden inside its parts. The Fourier coefficients tell us where the irregularity lies, and the mean square of the densities measures how much we gain by refining. Since this energy is bounded, there can only be finitely many substantial refinements. For Roth’s theorem, this is enough: either a partition has enough regularity to count progressions, or we can refine it and obtain a definite increase in energy.

Share this:

Related

Leave a Reply Cancel reply