Chapter 34: Arithmetic Combinatorics and Higher-Order Fourier Analysis

Why does positive density force long arithmetic progressions?

An arithmetic progression is a sequence $x,x+d,\ldots,x+(k-1)d$ with a constant difference. In the integers we require $d\gt0$; in a vector space we require $d\ne0$ and choose a length for which the terms are distinct. A dense set has many points, but those points might deliberately avoid patterns. Arithmetic combinatorics asks how far such avoidance can persist.

Write $[N]=\{1,\ldots,N\}$ and define the density of $A\subseteq[N]$ by $\alpha=|A|/N$. Szemerédi's theorem says that, for each fixed $k$ and $\delta\gt0$, every sufficiently large $[N]$ and every $A$ with $\alpha\ge\delta$ contain a nontrivial $k$-term progression. The order of quantifiers matters: the required size depends on both the length and the density. A small dense set can have no three-term progression.

The foundation of this chapter is a finite model that makes the proof mechanism visible. Let $V=\mathbb F_3^n$, let $N=|V|=3^n$, and let $\mathbb E_x$ mean the average over all $x\in V$. Addition is coordinatewise modulo $3$. For a function $f:V\to\mathbb C$, define the normalized Fourier transform

$$ \widehat f(\xi)=\mathbb E_x f(x)e_3(-\xi\cdot x),\qquad e_3(t)=\exp(2\pi it/3). $$

This chapter uses averages rather than the unnormalized Fourier sums of the additive-combinatorics prerequisite. Thus every coefficient here is the corresponding unnormalized coefficient divided by $N$. Orthogonality of characters gives inversion and Parseval:

$$ f(x)=\sum_{\xi\in V}\widehat f(\xi)e_3(\xi\cdot x),\qquad \sum_{\xi\in V}|\widehat f(\xi)|^2=\mathbb E_x|f(x)|^2. $$

Define $1_A$ to be the indicator of $A$, and put

$$ \Lambda_3(f)=\mathbb E_{x,d}f(x)f(x+d)f(x+2d). $$

Then $N^2\Lambda_3(1_A)$ counts ordered progression parameters, including $d=0$. If $A$ has no nontrivial progression, this count is exactly $|A|$, so $\Lambda_3(1_A)=\alpha/N$. A random-looking set of density $\alpha$ should instead have a count near $\alpha^3N^2$. A deficit creates a detectable Fourier bias. Restricting to a fiber of its character increases density, while reducing dimension. Repeating this step proves that fixed positive density cannot remain progression-free in arbitrarily large dimension.

Here are the ingredients needed for the concluding investigation, independently of the optional extensions. Set $\beta=\max_{\xi\ne0}|\widehat{1_A}(\xi)|$. Fourier inversion and character orthogonality give

$$ \Lambda_3(1_A)=\sum_\xi\widehat{1_A}(\xi)^3,\qquad |\Lambda_3(1_A)-\alpha^3|\le\beta\alpha(1-\alpha). $$

The cube formula uses characteristic $3$ and must not be substituted unchanged into an integer calculation. For a nonzero frequency $\xi$, let $\alpha_t$ be the density on $\{x:\xi\cdot x=t\}$, for $t\in\mathbb F_3$. These three equally sized fibers satisfy $\mathbb E_t\alpha_t=\alpha$. Their deviations $\delta_t=\alpha_t-\alpha$ have mean zero, and

$$ |\widehat{1_A}(\xi)|\le\mathbb E_t|\delta_t|\le2\max_t\delta_t. $$

Consequently some affine hyperplane has density at least $\alpha+|\widehat{1_A}(\xi)|/2$. The investigation proves these facts step by step. No analysis of nilmanifolds, cap-set tensors, or primes is needed to complete it. Background in Fourier analysis or real and complex analysis can deepen the extensions; the character identities above supply the finite foundation.

34.1 Arithmetic progressions in dense sets

Optional extension; not required to complete the chapter foundation.

For a fixed integer $k\ge3$, a nontrivial progression in $[N]$ has parameters $x,d\in\mathbb Z$ with $d\ge1$ and $1\le x\le x+(k-1)d\le N$. Let $r_k(N)$ be the maximum size of a subset of $[N]$ containing no such progression. The density theorem can be expressed as $r_k(N)/N\to0$ for each fixed $k$. This is an asymptotic statement, rather than a claim that density alone determines the answer at every finite size.

For an infinite set $B\subseteq\mathbb N$, its upper density is $\limsup_{N\to\infty}|B\cap[N]|/N$. Positive upper density supplies arbitrarily large initial intervals with a fixed positive density; the finite theorem then supplies progressions of each prescribed length. An upper density condition permits substantial gaps between these intervals.

Solved example. Let $A=\{1,2,4,5,7,8\}\subseteq[8]$. Its density is $3/4$, and $2,5,8$ is a progression with $x=2,d=3$. Equivalently, $2+8=2\cdot5$. The set is concentrated in two residue classes modulo $3$, but that concentration creates rather than prevents this progression. To count all three-term progressions with positive difference, test each middle point $b\in A$ and each $d$ with $b-d,b+d\in[8]$. The resulting triples are $1,4,7$ and $2,5,8$; there are exactly two. Counting reversed sequences as well would double this count.

In $\mathbb F_p^n$, where $p$ is an odd prime, the relation $a+c=2b$ describes three-term progressions. Unlike $[N]$, the group has no boundary, so all pairs $(x,d)$ are admissible. For longer progressions require $k\le p$ if distinctness is to follow from $d\ne0$. Otherwise the sequence wraps around and repeats.

Exercise. Find the density and all positive-difference three-term progressions in $B=\{1,3,5,7\}\subseteq[8]$. Hint: use each possible middle point. Solution: the density is $1/2$. Middle point $3$ gives $1,3,5$; middle point $5$ gives $3,5,7$. No other middle point has a member of $B$ on both sides at an equal distance. Thus there are two progressions.

34.2 Roth's theorem

Optional extension; not required to complete the chapter foundation.

Roth's theorem. For every $\delta\gt0$ there is an integer $N_3(\delta)$ such that, whenever $N\ge N_3(\delta)$ and $A\subseteq[N]$ has $|A|\ge\delta N$, there exist $x,d$ with $d\gt0$ and $x,x+d,x+2d\in A$. Equivalently, $r_3(N)=o(N)$. This chapter uses the qualitative theorem and does not assert a best quantitative bound.

The mechanism is a density increment. Compare the progression count with the main term predicted by density. If a sufficiently large set has no progression, a large Fourier coefficient witnesses a departure from uniformity. In an integer interval, one localizes this bias on a suitable subprogression and obtains a denser set in a shorter interval. Iteration must control both the density gained and the length lost.

Proof sketch; omitted prerequisites. The integer proof requires Fourier estimates with boundary control and a localization lemma converting a character bias into an increment on a long subprogression. These steps are not proved here. The finite-field version below has exact fibers and no boundary; its increment lemma is proved fully in Section 34.5 and the investigation. Replacing integer intervals by vector spaces changes the geometry of the restriction, so that model is an analogue rather than a complete proof of the integer theorem.

Exercise. If $A\subseteq\mathbb F_3^n$ is progression-free and has density $\alpha$, express its number of ordered progression parameters and its normalized count. Hint: identify the parameters with $d=0$. Solution: there are exactly $|A|=\alpha N$ parameters, one for each $x\in A$. Dividing by $N^2$ gives $\Lambda_3(1_A)=\alpha/N$. A positive count alone therefore does not prove a nontrivial progression exists.

34.3 Szemerédi's theorem

Optional extension; not required to complete the chapter foundation.

Szemerédi's theorem. For every integer $k\ge3$ and every real $\delta\gt0$, there is $N_k(\delta)$ such that every $A\subseteq[N]$ with $N\ge N_k(\delta)$ and $|A|\ge\delta N$ contains a nontrivial $k$-term arithmetic progression. Neither $k$ nor $\delta$ is allowed to vary with $N$ in this formulation.

Roth's theorem is the case $k=3$. For larger $k$, ordinary Fourier coefficients do not detect every obstruction to a random-like count. Quadratic phases, for example, can have small linear Fourier coefficients while possessing exact identities on four-term progressions. Higher uniformity norms measure these additional dependencies.

Proof sketch; omitted prerequisites. One route develops a uniformity-versus-structure decomposition: a uniform error contributes little to progression counts, while the structured part can support a density increment. Another route encodes progressions in hypergraphs and applies a removal theorem. The inverse, regularity, and counting lemmas in these routes are substantial theorems; the description is an explanation of the mechanism, not a proof of Szemerédi's theorem.

Solved example and diagram. In $[20]$, let $A$ contain exactly the numbers not divisible by $3$. There are fourteen members, so $\alpha=7/10$. The highlighted witness is $2,5,8,11,14,17,20$, a seven-term progression with difference $3$. In the diagram, filled dots are members, open dots are excluded, and the upper row lists the witness in order. Every connector joins its labeled term to the corresponding integer below. The diagram verifies one finite configuration; the theorem guarantees configurations in all sufficiently large sets of the prescribed density.

Exercise. Can the example contain an eight-term progression of difference $3$? Could the displayed seven terms be extended backward while staying in $[20]$? Hint: compare the span with the interval length. Solution: eight terms have span $7\cdot3=21$, exceeding the available span $19$. The term preceding $2$ would be $-1$, outside the interval. Thus neither extension is possible within this interval, without contradicting the asymptotic theorem.

34.4 Gowers uniformity norms

Optional extension; not required to complete the chapter foundation.

Let $G$ be a finite abelian group, let $\mathcal C$ denote complex conjugation, and let $\omega\cdot h=\sum_i\omega_i h_i$ for $\omega\in\{0,1\}^s$. Define

$$ \|f\|_{U^s(G)}^{2^s}=\mathbb E_{x,h_1,\ldots,h_s} \prod_{\omega\in\{0,1\}^s}\mathcal C^{|\omega|}f(x+\omega\cdot h). $$

This average compares a function on all vertices of an additive cube. Alternating conjugations cancel low-degree phases. For $s\ge2$ it is a norm; the expression at $s=1$ is the seminorm $|\mathbb E f|$. The defining average is nonnegative, as follows inductively from Cauchy–Schwarz, and its nonnegative root is intended.

With the normalized Fourier transform,

$$ \|f\|_{U^2}^4=\sum_\xi|\widehat f(\xi)|^4. $$

To derive this, expand the four factors at $x,x+h_1,x+h_2,x+h_1+h_2$. Averaging over the three variables forces their frequencies to coincide in the alternating pattern, leaving one fourth power per frequency. In particular, $\|1_A\|_{U^2}^4$ equals additive energy divided by $|G|^3$.

Solved example. On $\mathbb F_p$, with $p$ odd, take $q(x)=e_p(x^2)$. The alternating second difference of $x^2$ is $2h_1h_2$, so

$$ \|q\|_{U^2}^4=\mathbb E_{h_1,h_2}e_p(2h_1h_2)=1/p. $$

For $h_1=0$, the inner average is $1$; otherwise it is $0$ by orthogonality. The third alternating difference vanishes, giving $\|q\|_{U^3}=1$. On $\mathbb F_5$ these norms are $5^{-1/4}$ and $1$. On $\mathbb F_p^n$, the phase $e_p(\sum_i x_i^2)$ has $U^2=p^{-n/4}$ and $U^3=1$. Thus higher-order structure can persist as linear Fourier information becomes small.

For $k\ge3$ and prime $p\ge k$, define $\Lambda_k(f_0,\ldots,f_{k-1})=\mathbb E_{x,d}\prod_{j=0}^{k-1}f_j(x+jd)$ on $\mathbb F_p^n$. If each $|f_j|\le1$, repeated Cauchy–Schwarz gives the generalized von Neumann estimate

$$ |\Lambda_k(f_0,\ldots,f_{k-1})|\le\min_j\|f_j\|_{U^{k-1}}. $$

Each elimination of a bounded factor duplicates the remaining variables and introduces a difference. After $k-1$ eliminations the surviving average is an additive cube. The characteristic restriction ensures the needed distinct coefficients remain invertible. This is a proof mechanism sketch; the full repeated-variable bookkeeping is omitted.

Exercise. Compute $U^2$ and $U^3$ for $q(x,y)=e_5(x^2+y^2)$. Hint: the coordinate averages factor. Solution: $U^2{}^4=1/25$, hence $U^2=5^{-1/2}$; the third derivative vanishes in both coordinates, so $U^3=1$. Small $U^2$ does not imply small $U^3$.

34.5 Fourier-analytic density increment arguments

Optional extension; not required to complete the chapter foundation.

Work in $V=\mathbb F_p^n$ for an odd prime $p$, and put $a=1_A$, $\alpha=\mathbb E a$, and $f=a-\alpha$. Fourier inversion in the three progression factors imposes the equations $\xi_0+\xi_1+\xi_2=0$ and $\xi_1+2\xi_2=0$. Therefore

$$ \Lambda_3(a)=\sum_\xi\widehat a(\xi)^2\widehat a(-2\xi). $$

The zero-frequency term is $\alpha^3$. Set $\beta=\max_{\xi\ne0}|\widehat a(\xi)|$. Since multiplication by $-2$ preserves nonzero frequencies, Parseval yields

$$ |\Lambda_3(a)-\alpha^3|\le \beta\sum_{\xi\ne0}|\widehat a(\xi)|^2 =\beta(\alpha-\alpha^2). $$

If $A$ is progression-free, $0\lt\alpha\lt1$, and $N=|V|$, then $\Lambda_3(a)=\alpha/N$. When $\alpha^2\gt1/N$, rearrangement gives

$$ \beta\ge\frac{\alpha^2-1/N}{1-\alpha}. $$

The size assumption is essential: the right side could otherwise be nonpositive. In particular, $N\ge2/\alpha^2$ implies $\beta\ge\alpha^2/2$.

Here is the complete restriction lemma. Choose a nonzero frequency attaining $\beta$. Its linear map $x\mapsto\xi\cdot x$ is onto $\mathbb F_p$, so every fiber has size $N/p$. Write its fiber densities as $\alpha_t$ and their deviations as $\delta_t=\alpha_t-\alpha$. Orthogonality gives

$$ \widehat a(\xi)=\mathbb E_t\delta_t e_p(-t),\qquad \mathbb E_t\delta_t=0. $$

The total positive deviation equals the absolute total negative deviation. Consequently

$$ \beta\le\mathbb E_t|\delta_t| =2\mathbb E_t\max(\delta_t,0)\le2\max_t\delta_t. $$

Some affine hyperplane therefore has density at least $\alpha+\beta/2$. Identifying it affinely with $\mathbb F_p^{n-1}$ preserves progression-freeness: an affine map preserves $x,x+d,x+2d$ and nonzero differences.

Solved example. For $A=\{0,1\}^2$ in $\mathbb F_3^2$, set $\omega=e^{2\pi i/3}$. Factorization across coordinates gives

$$ \widehat a(\xi_1,\xi_2)=\frac{(1+\omega^{-\xi_1})(1+\omega^{-\xi_2})}{9}. $$

The coefficient at $(0,0)$ is $4/9$. Four frequencies with exactly one nonzero coordinate have magnitude $2/9$; the other four have magnitude $1/9$. Thus $\beta=2/9$, and $\widehat a(1,0)=(1-i\sqrt3)/9$. The progression-free count is $4/81$, while $\alpha^3=64/729$, so the deficit is $28/729$. The general bound gives $\beta\ge7/45$, consistent with the exact $2/9$.

For the frequency $(1,0)$, the three densities are $2/3,2/3,0$. The lemma guarantees at least $\alpha+\beta/2=5/9$; the actual maximum is $2/3$. These are a guaranteed increment and an observed increment, respectively.

Exercise. Explain why repeated restriction proves a qualitative density theorem for $\mathbb F_3^n$. Hint: retain the original density as a lower bound. Solution: if the initial density is $\alpha_0\gt0$, every admissible step increases density by at least $\alpha_0^2/4$ and reduces dimension by one. More than $4/\alpha_0^2$ steps would make density exceed $1$. Choose initial dimension so large that the remaining space still has at least $2/\alpha_0^2$ points through all these steps. Then progression-freeness is impossible. For $\alpha_0=1$ the conclusion is immediate in positive dimension. This proves existence of a sufficient dimension, without an optimal bound.

34.6 Higher-order Fourier analysis and nilsequences

Optional extension; not required to complete the chapter foundation.

Linear Fourier analysis detects correlation with characters $e(\theta n)$, where $e(t)=e^{2\pi it}$. Higher-order analysis asks what a large $U^{s+1}$ norm detects. The quadratic example shows that ordinary characters cannot be the whole answer.

A nilpotent group has a terminating sequence of commutator subgroups; its step is the number of stages needed. A nilmanifold is a quotient $G/\Gamma$ of a nilpotent Lie group by a discrete cocompact subgroup. A basic nilsequence has the form $F(g^n x)$, where $x\in G/\Gamma$ and $F$ is a continuous function. Quantitative results normally impose Lipschitz and complexity bounds. Polynomial nilsequences replace $g^n$ by a polynomial group sequence, defined through iterated group differences and a filtration. The filtration records which degree of motion is permitted in each subgroup.

Solved example. The circle $\mathbb R/\mathbb Z$ is a one-step nilmanifold. Take $x=0$, translation by $\theta$, and $F(t)=e(t)$. Then $F(n\theta)=e(\theta n)$. If $f(n)=e(\theta n)$, its correlation with this sequence is

$$ \left|\frac1N\sum_{n=1}^N f(n)\overline{F(n\theta)}\right|=1. $$

Every summand equals $1$. This recovers a Fourier character as the first level of the theory. A quadratic phase $e(\theta n^2)$ is obtained from a polynomial orbit $n\mapsto\theta n^2$ on a torus equipped with a degree-two filtration. It is not obtained by simply replacing an ordinary linear torus rotation with the same linear orbit and the same character.

Established inverse theorem. For fixed $s\ge1$ and $\delta\gt0$, a bounded function on $[N]$ with interval norm $U^{s+1}[N]\ge\delta$ correlates with an $s$-step nilsequence whose complexity and correlation bound depend only on $s,\delta$. Here interval norms use zero extension to a sufficiently large cyclic group, normalized by the corresponding norm of $1_{[N]}$; this prevents the choice of ambient group from changing the scale. The full formulation and proof are in Green, Tao, and Ziegler, An inverse theorem for the Gowers norm (2012). The historical inverse conjecture addressed by this theorem is proved; it is not an open assumption in this chapter.

On finite vector spaces the structural objects can instead be polynomial phases. A map $P:V\to\mathbb R/\mathbb Z$ is a nonclassical polynomial of degree at most $s$ when all $(s+1)$-fold additive derivatives vanish. The inverse theorem gives correlation with $e(P)$ when $U^{s+1}$ is large. In low characteristic the range need not lie in the ordinary $p$-torsion subgroup; restricting to classical field-valued polynomials can miss the structure. See Tao and Ziegler's finite-field inverse theorem. This result is also established, despite the word “conjecture” in its title.

Proof sketch; omitted prerequisites. Repeated differences first locate lower-degree structure, then compatibility arguments integrate it into a higher-degree object. On intervals this involves nilpotent geometry and quantitative equidistribution; in low-characteristic fields it involves the structure of nonclassical polynomials. Those integration and equidistribution theorems are omitted. No bound in this paragraph is claimed to be the best currently available.

Exercise. For $P(x)=x^2/p$ interpreted modulo $1$ on $\mathbb F_p$, $p$ odd, compute its second and third additive derivatives. Hint: expand $P(x+h)-P(x)$. Solution: the second derivative is $2h_1h_2/p$ modulo $1$, independent of $x$; the third is zero. Hence $P$ has degree at most two and its phase has $U^3=1$. Choosing $h_1=h_2=1$ shows its degree is not at most one.

34.7 Arithmetic regularity lemmas

Optional extension; not required to complete the chapter foundation.

Regularity replaces a complicated function with a structured approximation and a uniform residual. One elementary version controls individual Fourier coefficients. It is weaker than the higher-order regularity needed for long progressions, but its proof explains the energy-increment method.

Let $f:\mathbb F_p^n\to[0,1]$ and $\varepsilon\gt0$. There is a subspace $H$ with codimension at most $\lceil\varepsilon^{-2}\rceil$ such that, if $g=\mathbb E(f\mid\text{cosets of }H)$ and $r=f-g$, then

$$ \max_\xi|\widehat r(\xi)|\le\varepsilon. $$

The conditional expectation $g$ is the average of $f$ on the coset containing the input. Its energy is $\mathbb E g^2$. Begin with $H=V$, so $g$ is constant. If a residual coefficient exceeds $\varepsilon$, refine $H$ to $H\cap\ker\xi$. The selected frequency is outside the span of previously selected frequencies, because the old conditional expectation already preserves every coefficient in that span. Thus the refinement increases codimension by one.

Let $g'$ be the new conditional expectation. Orthogonal projection gives $\mathbb E(g')^2-\mathbb E g^2=\mathbb E|g'-g|^2$. The newly exposed Fourier coefficient is $\widehat r(\xi)$, so Parseval shows this increase exceeds $\varepsilon^2$. Energy is at most $\mathbb E f^2\le1$. Only finitely many such steps are possible, yielding the claimed bound. If the span already fills the dual space, the residual is zero.

Solved example. For $f=1_{\{0,1\}^2}$ on $\mathbb F_3^2$, the initial energy is $(4/9)^2=16/81$. Refining by the first coordinate gives $g$ with row values $2/3,2/3,0$, and

$$ \mathbb E g^2=8/27,\qquad 8/27-16/81=8/81. $$

Both newly exposed nonzero frequencies on this axis have magnitude $2/9$, and their squared magnitudes sum to $8/81$. Refining by the second coordinate produces singleton fibers, so $g=f$ and the energy becomes $4/9$. The second increase is $4/27$; the residual now vanishes.

Higher-order regularity replaces a linear factor by polynomial or nilsequence structure and typically writes $f=f_{\mathrm{str}}+f_{\mathrm{sml}}+f_{\mathrm{unf}}$, with small $L^2$ error and small higher uniformity norm. Its complexity and approximation parameters require a more elaborate theorem. The elementary coefficient bound above does not establish that stronger decomposition. For example, a quadratic phase on a large vector space has small coefficients but maximal $U^3$.

Exercise. Why does refining a factor never decrease energy? Hint: condition the refined approximation on the old factor. Solution: $\mathbb E(g'\mid\text{old factor})=g$, so $g'-g$ is orthogonal to $g$. Expanding the square gives $\mathbb E(g')^2=\mathbb E g^2+\mathbb E(g'-g)^2\ge\mathbb E g^2$. This monotone bounded quantity pays for each detected obstruction.

34.8 Polynomial configurations

Optional extension; not required to complete the chapter foundation.

A polynomial configuration is $x+P_0(d),\ldots,x+P_m(d)$ for fixed integer polynomials $P_i$. The condition $P_i(0)=0$ makes their shifts simultaneously vanish at the origin and removes certain residue-class obstructions. Taking $P_i(d)=id$ recovers an arithmetic progression.

The polynomial Szemerédi theorem states that, for fixed integer polynomials with zero constant terms and fixed $\delta\gt0$, every sufficiently large interval subset of density at least $\delta$ contains such a configuration with a positive integer parameter $d$. The terms must lie in the interval. If distinctness is required, use distinct polynomials and avoid their finitely many positive collision parameters; the strengthened recurrence statement supplies this. A zero polynomial is allowed and supplies the base point $x$.

For the original theorem and its broader recurrence setting, see Bergelson and Leibman's Polynomial extensions of van der Waerden's and Szemerédi's theorems, JAMS 9 (1996), 725–753. Their later primary treatment with Lesigne, Intersective polynomials and polynomial Szemerédi theorem, explains the more general residue condition. The zero-constant-term case here is an established theorem.

Solved example. Let $A=\{1,3,5,7,9,11,13,15,17\}\subseteq[17]$, of density $9/17$. For $P_0=0$, $P_1(d)=d^2$, and $P_2(d)=2d^2$, take $x=1,d=2$. The configuration is $1,5,9$, all in $A$. Its common difference is a square. The separate configuration from $0,d,d^2$ with the same parameters is $1,3,5$. At $d=1$ its last two terms would coincide, so the explicit choice of $d=2$ matters.

Proof sketch; omitted prerequisites. Polynomial exhaustion techniques repeatedly difference families of polynomials, reducing a suitable ordering of their complexity. The simplest calculation is $(d+h)^2-d^2=2hd+h^2$: a quadratic dependence becomes linear in $d$. The full argument also controls multiple recurrence and the reorganized polynomial family, not just the highest degree of a single polynomial. Ergodic correspondence and polynomial multiple recurrence are omitted prerequisites.

Exercise. Why is a nonzero constant shift not covered merely by positive density? Hint: consider parity. Solution: the even integers have density $1/2$ but never contain both $x$ and $x+1$. Thus the family of shifts $0,1$ has a local obstruction. Zero constant terms ensure that taking $d$ divisible by any chosen modulus makes every $P_i(d)$ divisible by that modulus, eliminating this particular obstruction.

34.9 Finite-field models and the cap-set problem

Optional extension; not required to complete the chapter foundation.

The later Section 43.9 is recommended background for a fuller polynomial-method treatment, rather than an entry requirement. This section supplies the bridge: Fourier arguments find biased fibers; polynomial methods encode forbidden triples in a low-degree tensor. For the full primary treatment, see Ellenberg and Gijswijt, On large subsets with no three-term arithmetic progression (2017).

A cap set is $A\subseteq\mathbb F_3^n$ with no nontrivial three-term progression. Because $2=-1$ in this field, a triple satisfies the progression equation exactly when $a+b+c=0$. If two entries coincide, the third also coincides. Hence a cap set admits only the diagonal solutions $a=b=c$.

Solved example. The product set $\{0,1\}^n$ is a cap set of size $2^n$. In any coordinate, three entries from $\{0,1\}$ sum to zero modulo $3$ only if their number of ones is zero or three. The three entries are therefore equal in every coordinate, proving all solutions are diagonal. Its density is $(2/3)^n$, which tends to zero. It supplies a construction, not a contradiction to the fixed-density theorem. In dimension two its size is four; exhaustive enumeration of all $512$ subsets of the nine-point plane confirms that four is the maximum in that dimension.

A classical polynomial-method bound is

$$ |A|\le3m(n,\lfloor2n/3\rfloor),\qquad m(n,D)=|\{(a_1,\ldots,a_n)\in\{0,1,2\}^n:\sum_i a_i\le D\}|. $$

For $0\lt t\lt1$, generating functions imply $m(n,D)\le t^{-D}(1+t+t^2)^n$, and therefore

$$ |A|\le3c_3^n,\qquad c_3=\min_{0\lt t\lt1}(1+t+t^2)t^{-2/3}\lt2.756. $$

The minimizer is $(\sqrt{33}-1)/8$, obtained from $4t^2+t-2=0$. This historical bound establishes exponential decay relative to $3^n$; it is not presented as a current optimal estimate.

Proof sketch; omitted prerequisites. On $A^3$, consider the tensor $T(x,y,z)=\prod_i(1-(x_i+y_i+z_i)^2)$ over $\mathbb F_3$. It equals one when $x+y+z=0$ and zero otherwise. For a cap set it is a diagonal tensor. Its total degree is $2n$, so each monomial has degree at most $2n/3$ in at least one of the three variable blocks. Grouping by a low-degree block bounds slice rank by $3m$. Slice rank is the minimum number of terms of forms $u(x)v(y,z)$, or either of the other block choices, needed to represent the tensor. The diagonal-tensor slice-rank lemma gives rank $|A|$ and completes the bound; that lemma is the omitted prerequisite. The example's cap property was proved separately and does not depend on this sketch.

Exercise. Evaluate the bound $3m$ at $n=2$. Hint: only total degree at most one is allowed. Solution: the permitted exponent vectors are $(0,0),(1,0),(0,1)$, so $m=3$ and the bound is $9$. It is valid but weaker than the exact maximum four. An asymptotically useful theorem need not be sharp in the smallest dimensions.

34.10 Arithmetic combinatorics in prime and pseudorandom sets

Optional extension; not required to complete the chapter foundation.

The primes have zero natural density, so their long progressions do not follow by applying Szemerédi's theorem directly to the prime indicator. The established Green–Tao theorem states that primes contain nontrivial arithmetic progressions of every finite length. Its proof combines the dense theorem with transference and a suitable sieve majorant. This chapter makes no claim about a best bound for the first such progression.

The local divisibility biases must first be addressed. Let $W$ be the product of primes at most a parameter $w$, and choose $b$ coprime to $W$. Restricting to numbers $Wm+b$ is the $W$-trick. It removes divisibility by the primes used in $W$. A common weight is

$$ \Lambda_{W,b}(m)=\frac{\varphi(W)}W\Lambda(Wm+b), $$

where $\varphi$ is Euler's totient and $\Lambda(q)=\log\ell$ if $q$ is a positive power of a prime $\ell$, and zero otherwise. Prime powers are included in this von Mangoldt definition. Controlling its averages with a growing $W$ requires number-theoretic estimates; these are not consequences of the finite Fourier lemmas.

For transference, work on a sequence of cyclic groups and take a nonnegative majorant $\nu$ with $\mathbb E\nu=1+o(1)$. A nonnegative function $f\le\nu$ of mean at least $\delta$ represents positive relative density. The majorant must also satisfy a suitable linear-forms condition: averages of specified products $\prod_j\nu(L_j(\mathbf x))$ approach one for the systems of forms needed in the counting argument, including the prescribed subcollections. The notation $o(1)$ refers to the ambient size tending to infinity with the other theorem parameters appropriately controlled.

Mean one alone is insufficient. Even requiring the single product associated with a progression is not a substitute for all the theorem's hypotheses. A relative counting theorem transfers the dense progression conclusion to $f$ under those stronger conditions. The full linear-forms condition and established transference result are given by Conlon, Fox, and Zhao, A relative Szemerédi theorem. This is an established theorem, not a conjectural random model for primes.

Solved example. The primes $5,11,17,23,29$ form a five-term progression of difference $6$. Each is prime by trial division by primes at most its square root, and every term is $5$ modulo $6$. With $W=6,b=5$, their transformed coordinates are $m=0,1,2,3,4$. The initial transformed coordinate zero is legitimate for this finite illustration; asymptotic intervals can be chosen with positive coordinates. The calculation illustrates local normalization, not the sieve estimates required to prove arbitrarily long prime progressions.

For an exact warning about pseudorandomness, take $V=\mathbb F_3^2$, $H=\{(0,y):y\in\mathbb F_3\}$, and $\nu=3\,1_H$. Its mean is one. For a progression to have all its terms in $H$, both $x$ and $d$ must lie in $H$. There are nine such parameters, each with product $27$, so

$$ \Lambda_3(\nu)=\frac{9\cdot27}{81}=3. $$

This differs from the value one predicted by a suitable pseudorandom majorant. Normalization alone does not erase concentration on a subspace.

Proof sketch; omitted prerequisites. Construct a sieve majorant, prove the needed linear-forms estimates, approximate the relatively dense function by a bounded dense model, and transfer progression counts using relative counting lemmas. The sieve estimates, dense-model theorem, and relative counting lemma are omitted. The finite-field increment provides intuition for identifying obstructions, but does not itself prove these analytic ingredients.

Exercise. Why does restricting primes greater than $3$ to residues modulo $6$ leave only $1$ and $5$? Does that prove those residue classes contain only primes? Hint: consider divisibility by $2$ and $3$, then test $25$. Solution: every other residue is divisible by $2$ or $3$. The remaining classes still contain composites, including $25\equiv1\pmod6$ and $35\equiv5\pmod6$. The $W$-trick removes selected local obstructions; it does not certify primality.

Analyze a density-increment argument in a finite-field model

The investigation is self-contained using the introduction's finite Fourier definitions. It connects the dense-set proof mechanism to the need for pseudorandom ambient weights in sparse arithmetic problems. Complete the calculations before drawing a conclusion about iteration: a density increment costs ambient dimension.

Worked solution: warm-up. The points are $(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)$. A nonzero line direction changes at least one coordinate, which then runs through all three field values. It cannot remain in $\{0,1\}^2$. Thus there are zero nontrivial parameters and four degenerate parameters. The density is $4/9$, the normalized count is $4/81=36/729$, and its difference from $\alpha^3$ is $-28/729$.

Worked solution: Fourier coefficients. Put $u=1+\omega^2=(1-i\sqrt3)/2$ and $v=1+\omega=(1+i\sqrt3)/2$. Their magnitudes are one, with $uv=1$. The complete table is

Parseval gives $16/81+4(4/81)+4(1/81)=4/9$. Since $u^3=v^3=-1$, the four axis-frequency cubes sum to $-32/729$. The four remaining nonprincipal cubes sum to $4/729$. Adding $64/729$ from the principal coefficient yields $36/729=4/81$. This verifies the progression identity exactly.

Worked solution: all fibers. For frequency $\xi$, the entries below give densities in fibers with values $t=0,1,2$. Opposite frequencies have the same fibers with labels $1,2$ interchanged.

Every row averages to $4/9$. The highest fiber density is $2/3$, while the Fourier lemma guarantees $5/9$ using a maximizing coefficient. To reproduce the finite cap search, encode subsets by nine-bit masks; for each mask test every $x$ and every nonzero $d$ and reject it if all three points belong to the mask. The maximum surviving population is four. Character orthogonality and the coordinate argument already prove the stated identities without relying on decimal computations.

Worked solution: general proof and stopping rule. For progression-free $B$, the count is $\alpha/N$. The nonprincipal Fourier sum has absolute value at most $\beta\alpha(1-\alpha)$, so, when $\alpha^2\gt1/N$, $\beta\ge(\alpha^2-1/N)/(1-\alpha)$. If $N\ge2/\alpha^2$, this implies $\beta\ge\alpha^2/2$. The mean-zero fiber deviations give $\max_t\delta_t\ge\beta/2$. Restriction therefore raises density by at least $\alpha^2/4$ and loses one dimension.

Starting at density $\alpha_0\in(0,1)$, put $L=\lfloor4/\alpha_0^2\rfloor+1$. Choose initial dimension $n$ with $n\ge L$ and $3^{n-L}\ge2/\alpha_0^2$. If the set remained progression-free, every one of the next $L$ steps would satisfy the size condition, since density only increases. The density after those steps would be at least $\alpha_0+L\alpha_0^2/4\gt1$, impossible. Hence some nontrivial progression must have existed. This is a complete qualitative finite-field proof, with a deliberately coarse dimension budget.

For the actual nine-point example, after restricting to a best fiber the size is $3$ and density is $2/3$. The condition $N\ge2/\alpha^2$ would require $3\ge9/2$, which fails. In fact its two-point subset of a three-point line is still progression-free. The proof has reached its legitimate stopping point; a small-space example cannot be converted into a contradiction by ignoring size loss.

Worked solution: interpretation and extension. Dense-set theorems start with a bounded indicator in a uniform ambient space. Prime problems use a sparse set normalized by a weight. The weight $3\,1_H$ has mean one but progression average three, so its concentration is an obstruction that normalization does not remove. Transfer to primes requires verified pseudorandomness conditions on an appropriate majorant, beyond the finite density increment.

For the optional product set in dimension three, density is $8/27$. Factorization gives a coefficient of magnitude $2^{3-r}/27$ when exactly $r$ coordinates of the frequency are nonzero. The largest nonprincipal magnitude is $4/27$, attained at $r=1$. Restricting a coordinate to $0$ or $1$ gives density $4/9$, whereas the lemma guarantees $8/27+2/27=10/27$. Its cap property follows from the same coordinate proof as before.

A cross-disciplinary application is detecting algebraic patterns in categorical data. Encode three possible attribute values by $\mathbb F_3$ and a record with $n$ attributes by a vector. Three distinct records satisfy $a+b+c=0$ exactly when, in every attribute, the values are either all equal or all different—the rule underlying SET configurations. The finite investigation provides exact pattern detection, while cap bounds limit how many records can avoid all such triples. A sampled search provides evidence about the data inspected; an exhaustive search proves the finite claim, and the dimension-independent theorem requires the mathematical argument above.