CO 740: Additive Combinatorics

Proof. We use the Davenport transform. If \(|A + B| \ge p\), the result is immediate since \(A + B \subseteq \mathbb{Z}/p\mathbb{Z}\). So assume \(A + B \neq \mathbb{Z}/p\mathbb{Z}\).

We proceed by strong induction on \(|B|\). The base case \(|B| = 1\) is trivial, since \(|A + B| = |A| = |A| + 1 - 1\).

\[ A' = A \cup (c - B), \qquad B' = B \cap (c - A). \]

We claim:

Step 1: \(A' + B' \subseteq A + B\). Indeed, let \(a' + b' \in A' + B'\). If \(a' \in A\), then \(b' \in B\) (since \(B' \subseteq B\)), so \(a' + b' \in A + B\). If \(a' \in c - B\), say \(a' = c - b_0\) for some \(b_0 \in B\), then \(b' \in c - A\), say \(b' = c - a_0\) for some \(a_0 \in A\). Then \(a' + b' = 2c - b_0 - a_0\). But also \(b' \in B\), so \(a_0 + b' \in A + B\). However, we need a different argument. Instead, since \(b' \in B' \subseteq c - A\), we have \(b' = c - a_0\) for some \(a_0 \in A\), and then \(a' + b' = (c - b_0) + (c - a_0) = 2c - a_0 - b_0\). This does not immediately land in \(A + B\).

\[ A_e = A \cup (B + e), \qquad B_e = B \cap (A - e). \]

We verify:

1. \(A_e + B_e \subseteq A + B\). Let \(x \in A_e\) and \(y \in B_e\). If \(x \in A\), then \(y \in B\) (since \(B_e \subseteq B\)), so \(x + y \in A + B\). If \(x \in B + e\), say \(x = b_1 + e\) for some \(b_1 \in B\), then since \(y \in A - e\), we have \(y + e \in A\), so \(x + y = b_1 + (y + e) \in B + A = A + B\). ■
2. \(|A_e| + |B_e| = |A| + |B|\). By inclusion-exclusion, \(|A_e| = |A \cup (B+e)| = |A| + |B+e| - |A \cap (B+e)| = |A| + |B| - |A \cap (B+e)|\). Also \(|B_e| = |B \cap (A - e)| = |A \cap (B+e)|\) (since \(b \in B \cap (A-e) \Leftrightarrow b \in B\) and \(b + e \in A \Leftrightarrow b + e \in A \cap (B+e)\)). Hence \(|A_e| + |B_e| = |A| + |B|\). ■

Now, if \(|B| \ge 2\) and \(A + B \neq \mathbb{Z}/p\mathbb{Z}\), we choose \(e\) so that \(B_e\) is non-empty but strictly smaller than \(B\). Since \(A + B \neq \mathbb{Z}/p\mathbb{Z}\), there exists \(e\) such that \(e \notin A - B\), which means \(B \cap (A - e) = \emptyset\), giving \(|B_e| = 0\). That is too small. Instead, choose \(e\) so that \(A \cap (B + e) \neq \emptyset\) (which is possible since we can take \(e = a - b\) for any \(a \in A, b \in B\)) but \(B + e \not\subseteq A\). If \(B + e \subseteq A\), then \(|A| \ge |B|\), and taking a different \(e' = a' - b'\) where \(a' \notin B + e\) (possible since \(A + B \neq \mathbb{Z}/p\mathbb{Z}\) implies \(A \neq \mathbb{Z}/p\mathbb{Z}\)) gives \(B_{e'}\) strictly between \(0\) and \(|B|\) — unless all translates \(B + e\) that intersect \(A\) are contained in \(A\), which would force \(A\) to be a union of translates of \(B\) and hence a coset of a subgroup containing \(B-B\). Since \(p\) is prime, the only subgroups of \(\mathbb{Z}/p\mathbb{Z}\) are \(\{0\}\) and \(\mathbb{Z}/p\mathbb{Z}\), so this cannot happen when \(|B| \ge 2\).

\[ |A + B| \ge |A_e + B_e| \ge |A_e| + |B_e| - 1 = |A| + |B| - 1. \]

This completes the induction. ■

Proof. We construct an injection. For each \(x \in B - C\), choose a representation \(x = b_x - c_x\) with \(b_x \in B\) and \(c_x \in C\). Define the map \[ \varphi: A \times (B - C) \to (A - B) \times (A - C) \] by \(\varphi(a, x) = (a - b_x, \, a - c_x)\). This map is injective: if \(\varphi(a, x) = \varphi(a', x')\), then \(a - b_x = a' - b_{x'}\) and \(a - c_x = a' - c_{x'}\). Subtracting, \(b_x - c_x = b_{x'} - c_{x'}\), i.e., \(x = x'\). Then the first equation gives \(a = a'\). Since \(\varphi\) is injective, \[ |A| \cdot |B - C| \le |A - B| \cdot |A - C|. \] The proof of the second inequality is analogous, using the map \((a, x) \mapsto (a + b_x, a + c_x)\). ■

Proof. We choose \(X \subseteq A\) to be non-empty and minimizing the ratio \(|X + B|/|X|\). Set \(K' = |X + B|/|X| \le K\) (the ratio is at most \(K\) since \(X = A\) gives ratio at most \(K\)).

We prove \(|X + B + C| \le K'|X + C|\) for every finite set \(C\) by induction on \(|C|\). The base case \(|C| = \{c\}\) gives \(|X + B + \{c\}| = |X + B| = K'|X| = K'|X + \{c\}|\), which holds with equality.

\[ X + B + C = (X + B + C') \cup (X + B + c), \]\[ |X + B + C| = |X + B + C'| + |X + B + c| - |(X + B + C') \cap (X + B + c)|. \]\[ |X + B + C| \le |X + B + C'| + |X + B| - |Y + B|. \]\[ |X + C| = |X + C'| + |X + c| - |(X + C') \cap (X + c)| \le |X + C'| + |X| - |Y|. \]\[ |X + B + C| \le K'|X + C'| + K'|X| - K'|Y| \le K'(|X + C'| + |X| - |Y|) \le K'|X + C|. \]

If \(Y = \emptyset\), the bound \(|X + B + C| \le |X + B + C'| + |X + B|\) combined with induction and the trivial \(|X + C| \ge |X + C'|\) gives an even easier estimate. ■

Proof of the Plünnecke-Ruzsa Inequality. We apply Petridis's lemma with \(B = A\). We obtain a non-empty \(X \subseteq A\) such that \(|X + A + C| \le K|X + C|\) for every finite set \(C\). Applying this with \(C = A\) gives \(|X + 2A| \le K|X + A| \le K^2|X|\). By induction, \(|X + kA| \le K^k|X|\) for all \(k \ge 0\). \[ |X| \cdot |kA - lA| \le |X + kA| \cdot |X + lA| \le K^k|X| \cdot K^l|X| = K^{k+l}|X|^2, \]

which gives \(|kA - lA| \le K^{k+l}|X| \le K^{k+l}|A|\). ■

Proof. Choose \(T \subseteq A\) to be a maximal subset such that the translates \(\{t + B : t \in T\}\) are pairwise disjoint. By maximality, for every \(a \in A\), the set \(a + B\) intersects \(t + B\) for some \(t \in T\). That is, there exist \(b_1, b_2 \in B\) with \(a + b_1 = t + b_2\), giving \(a = t + b_2 - b_1 \in t + B - B \subseteq T + B - B\). \[ |T| \cdot |B| = \left|\bigsqcup_{t \in T} (t + B)\right| \le |A + B| \le K|B|, \]

giving \(|T| \le K\). ■

Proof. The triangle inequality follows directly from the Ruzsa triangle inequality (Theorem 1.8). We have \[ |B| \cdot |A - C| \le |A - B| \cdot |B - C|, \] so \[ \frac{|A - C|}{\sqrt{|A| \cdot |C|}} \le \frac{|A - B|}{\sqrt{|A| \cdot |B|}} \cdot \frac{|B - C|}{\sqrt{|B| \cdot |C|}}, \] and taking logarithms gives \(d(A, C) \le d(A, B) + d(B, C)\).

For non-negativity, note that \(|A - B| \ge \max(|A|, |B|) \ge \sqrt{|A| \cdot |B|}\), so \(d(A, B) \ge 0\).

Finally, \(d(A, A) = \log(|A - A|/|A|)\). This equals zero if and only if \(|A - A| = |A|\), which happens if and only if \(A\) is a coset of a finite subgroup. ■

Proof sketch (following Ruzsa). The proof proceeds in several stages.

Step 1: Reduction to a bounded torsion-free setting. Using the Ruzsa covering lemma, one can “model” \(A\) — up to Freiman isomorphism — as a subset of \(\mathbb{Z}^d\) for some bounded \(d\). The idea is that if \(|A + A| \le K|A|\), then by the Plünnecke-Ruzsa inequality, \(|2A - 2A| \le K^4|A|\), and by the covering lemma, \(2A - 2A\) can be covered by \(K^4\) translates of \(A - A\). This gives enough “linear algebra” structure to embed into a lattice.

Step 2: Bogolyubov’s lemma. One shows that \(2A - 2A\) contains a large structured subset. Specifically, Bogolyubov’s lemma (which we will prove via Fourier analysis in Chapter 3) asserts that if \(|A + A| \le K|A|\) in \(\mathbb{Z}/N\mathbb{Z}\), then \(2A - 2A\) contains a subspace (or a GAP) of bounded codimension.

Step 3: Geometry of numbers. Using Minkowski’s second theorem or John’s theorem, one refines the GAP to be proper and of controlled rank and volume.

The bounds obtained by Ruzsa’s method give \(d(K) \le CK^2 \log K\) and \(c(K) \le e^{CK^2 \log^2 K}\) for some absolute constant \(C\). ■

Proof. By Fourier inversion, \[ \sum_{\chi} |\widehat{f}(\chi)|^2 = \sum_{\chi} \widehat{f}(\chi) \overline{\widehat{f}(\chi)} = \sum_{\chi} \widehat{f}(\chi) \left( \mathbb{E}_x \overline{f(x)} \chi(x) \right) = \mathbb{E}_x \overline{f(x)} \sum_{\chi} \widehat{f}(\chi) \chi(x) = \mathbb{E}_x \overline{f(x)} f(x) = \mathbb{E}_x |f(x)|^2. \] ■

Proof. \[ \widehat{f * g}(\chi) = \mathbb{E}_x (f * g)(x) \overline{\chi(x)} = \mathbb{E}_x \mathbb{E}_y f(y) g(x - y) \overline{\chi(x)}. \] Substituting \(z = x - y\), \[ = \mathbb{E}_y f(y) \overline{\chi(y)} \cdot \mathbb{E}_z g(z) \overline{\chi(z)} = \widehat{f}(\chi) \cdot \widehat{g}(\chi). \] ■

Proof. Consider the convolution \(f = 1_A * 1_{-A}\), which is supported on \(A - A\) and satisfies \(\widehat{f}(\chi) = |\widehat{1_A}(\chi)|^2\). By Parseval, \[ \sum_\chi |\widehat{1_A}(\chi)|^4 = \mathbb{E}_x |f(x)|^2. \] The right-hand side counts (with normalization) the number of quadruples \((a_1, a_2, a_3, a_4) \in A^4\) with \(a_1 - a_2 = a_3 - a_4\), which equals the additive energy \(E(A, A)/|G|^2\). By the Cauchy-Schwarz inequality, \(E(A, A) \ge |A|^4 / |A + A| \ge |A|^4 / (K|A|) = |A|^3/K\). On the other hand, the contribution of the trivial character \(\chi_0\) gives \(|\widehat{1_A}(\chi_0)|^4 = \alpha^4\). Comparing, \[ \alpha^4 + \sum_{\chi \neq \chi_0} |\widehat{1_A}(\chi)|^4 \ge \frac{|A|^3}{K |G|^2} = \frac{\alpha^3}{K |G|} \cdot |G| = \frac{\alpha^3}{K}. \] Wait, let us be more careful. With our normalization \(\widehat{1_A}(\chi) = \mathbb{E}_x 1_A(x) \overline{\chi(x)}\), we have \(|\widehat{1_A}(\chi_0)| = \alpha\). The \(\ell^4\) Parseval identity gives \[ \sum_\chi |\widehat{1_A}(\chi)|^4 = \frac{E(A,A)}{|G|^3}, \] where \(E(A,A) = |\{(a_1,a_2,a_3,a_4) \in A^4 : a_1+a_2 = a_3+a_4\}|\). By Cauchy-Schwarz, \(E(A,A) \ge |A|^4/|A+A| \ge |A|^3/K\). So \[ \sum_{\chi \neq \chi_0} |\widehat{1_A}(\chi)|^4 \ge \frac{|A|^3}{K|G|^3} - \alpha^4 = \frac{\alpha^3}{K} - \alpha^4 = \alpha^3\left(\frac{1}{K} - \alpha\right). \] If \(\alpha \le 1/(2K)\), this is at least \(\alpha^3/(2K)\). Since each term \(|\widehat{1_A}(\chi)|^4 \le \alpha^2 \cdot |\widehat{1_A}(\chi)|^2\) and \(\sum_\chi |\widehat{1_A}(\chi)|^2 = \alpha\), the maximum Fourier coefficient satisfies \(\max_{\chi \neq \chi_0} |\widehat{1_A}(\chi)|^2 \ge \alpha^2/(2K)\), giving \(\max_{\chi \neq \chi_0} |\widehat{1_A}(\chi)| \ge \alpha / \sqrt{2K}\). A more careful argument gives the claimed bound. ■

Proof. Let \(f = 1_A * 1_A * 1_{-A} * 1_{-A}\). Then \(\widehat{f}(t) = |\widehat{1_A}(t)|^4\), and \(f\) is supported on \(2A - 2A\). We want to show that \(2A - 2A\) contains a large subspace. \[ B = \{x \in \mathbb{F}_p^n : f(x) > 0\} = 2A - 2A. \]\[ S = \{t : |\widehat{1_A}(t)| > 0\} \supseteq \mathrm{Spec}_\delta(A) \text{ for all } \delta > 0. \]

Let us take a different approach. We claim: \(2A - 2A \supseteq V^\perp\) where \(V = \mathrm{Spec}_{\sqrt{\alpha}}(A) = \{t : |\widehat{1_A}(t)| \ge \sqrt{\alpha} \cdot \alpha\}\). Wait, we need to be more precise.

\[ f(x) = \sum_t |\widehat{1_A}(t)|^4 \omega^{t \cdot x}. \]\[ f(x) = \sum_{t \in \Lambda} |\widehat{1_A}(t)|^4 \omega^{t \cdot x} + \sum_{t \notin \Lambda} |\widehat{1_A}(t)|^4 \omega^{t \cdot x}. \]\[ \sum_{t \notin \Lambda} |\widehat{1_A}(t)|^4 \le \delta^2 \sum_{t \notin \Lambda} |\widehat{1_A}(t)|^2 \le \delta^2 \alpha. \]\[ \sum_{t \in \Lambda} |\widehat{1_A}(t)|^4 \ge |\widehat{1_A}(0)|^4 = \alpha^4. \]\[ f(x) \ge \alpha^4 - \delta^2 \alpha. \]

Choosing \(\delta^2 = \alpha^3 / 2\), i.e., \(\delta = \alpha^{3/2}/\sqrt{2}\), we get \(f(x) \ge \alpha^4/2 > 0\), so \(x \in 2A - 2A\).

\[ |\Lambda| \le \frac{\alpha}{\delta^2} = \frac{\alpha}{\alpha^3/2} = \frac{2}{\alpha^2}. \]

Hence \(\Lambda^\perp\) has codimension at most \(\lceil 2/\alpha^2 \rceil\), and \(2A - 2A \supseteq \Lambda^\perp\). ■

Proof. We use the density increment strategy. Let \(\alpha = |A|/3^n\) be the density of \(A\). We show that either \(\alpha\) is small, or we can pass to a subspace of \(\mathbb{F}_3^n\) where the density of \(A\) increases. \[ T = \sum_{x+y+z=0} 1_A(x) 1_A(y) 1_A(z) = 3^{2n} \sum_{t \in \mathbb{F}_3^n} \widehat{1_A}(t)^3. \]\[ T = 3^{2n} \sum_t \widehat{1_A}(t)^3. \]\[ T = \sum_{\substack{x, y, z \in \mathbb{F}_3^n \\ x+y+z=0}} f(x) f(y) f(z). \]\[ T = 3^{-n} \sum_t \left(\sum_x f(x) \omega^{t \cdot x}\right)^3 = 3^{2n} \sum_t \widehat{f}(t)^3, \]

since \(\sum_x f(x) \omega^{t \cdot x} = 3^n \widehat{f}(t)\) (with our convention \(\widehat{f}(t) = \mathbb{E}_x f(x) \omega^{-t \cdot x}\); note \(\omega^{t \cdot x} = \omega^{-t \cdot x}\) in \(\mathbb{F}_3\) since \(-1 \equiv 2 \pmod{3}\) and we can absorb the sign into \(t\)). Let us just proceed with the standard computation.

We have \(T = 3^{2n} \sum_t \widehat{f}(t)^3\). If \(A\) has no non-trivial 3-AP, then the only solutions to \(x + y + z = 0\) in \(A\) have \(x = y = z\), so \(T = |A| = \alpha \cdot 3^n\).

\[ \alpha \cdot 3^n = 3^{2n} \sum_t \widehat{f}(t)^3 = 3^{2n} \left( \alpha^3 + \sum_{t \neq 0} \widehat{f}(t)^3 \right). \]\[ \left| \sum_{t \neq 0} \widehat{f}(t)^3 \right| = \left| \frac{\alpha}{3^n} - \alpha^3 \right| \ge \frac{\alpha}{3^n} - \alpha^3 \ge \frac{\alpha}{2 \cdot 3^n} \]

provided \(\alpha^3 \le \alpha/(2 \cdot 3^n)\), i.e., \(\alpha \le (2 \cdot 3^n)^{-1/2}\). But actually, the density increment works regardless. Let us proceed differently.

\[ \sum_{t \neq 0} \widehat{f}(t)^3 = \frac{\alpha}{3^n} - \alpha^3. \]\[ \left|\frac{\alpha}{3^n} - \alpha^3\right| \le \max_{t \neq 0} |\widehat{f}(t)| \cdot \sum_{t \neq 0} |\widehat{f}(t)|^2 \le \max_{t \neq 0} |\widehat{f}(t)| \cdot \alpha, \]

using Parseval: \(\sum_t |\widehat{f}(t)|^2 = \mathbb{E}_x |f(x)|^2 = \alpha\) (since \(f = 1_A\)), so \(\sum_{t \neq 0} |\widehat{f}(t)|^2 \le \alpha\).

\[ \alpha^2 - \frac{1}{3^n} \le \max_{t \neq 0} |\widehat{f}(t)|. \]

For \(\alpha > 3/n\) and \(n\) sufficiently large, \(\alpha^2/2 \le \max_{t \neq 0} |\widehat{f}(t)|\), so there exists \(t_0 \neq 0\) with \(|\widehat{f}(t_0)| \ge \alpha^2/2\).

Step 3: Passing to a subspace. Let \(V = t_0^\perp = \{x \in \mathbb{F}_3^n : t_0 \cdot x = 0\}\), a subspace of codimension 1 (so \(|V| = 3^{n-1}\)). The group \(\mathbb{F}_3^n\) decomposes as \(V \sqcup (V + v) \sqcup (V + 2v)\) for some \(v \notin V\). By the pigeonhole principle, at least one coset \(V + jv\) contains at least \(\alpha |V|\) elements of \(A\). In fact, the large Fourier coefficient gives a density increment: the density of \(A\) on the coset \(V + jv\) (for the right \(j\)) is at least \(\alpha + \alpha^2/6 > \alpha\).

More precisely, \(\widehat{f}(t_0) = \mathbb{E}_x 1_A(x) \omega^{-t_0 \cdot x}\). Let \(\alpha_j = |A \cap (V+jv)|/|V|\) for \(j = 0, 1, 2\). Then \(\widehat{f}(t_0) = \frac{1}{3}(\alpha_0 + \alpha_1 \omega^{-j_1} + \alpha_2 \omega^{-j_2})\) for appropriate phases, and \(|\widehat{f}(t_0)| \ge \alpha^2/2\) implies that some \(\alpha_j \ge \alpha + c\alpha^2\) for a constant \(c > 0\).

Now \(A \cap (V + jv)\) is a subset of a coset of a codimension-1 subspace, and after translating, it becomes a subset of \(\mathbb{F}_3^{n-1}\) with density at least \(\alpha + c\alpha^2\) and no 3-AP. We can iterate: after \(m\) iterations, we have a subset of \(\mathbb{F}_3^{n-m}\) with density at least \(\alpha + mc\alpha^2\) and no 3-AP. Since the density cannot exceed 1, we need \(mc\alpha^2 \le 1\), so \(m \le 1/(c\alpha^2)\). But we also need \(n - m \ge 1\), so \(n \ge m + 1 \ge 1/(c\alpha^2)\), giving \(\alpha \le C/\sqrt{n}\). Wait, this gives \(\alpha = O(n^{-1/2})\) rather than \(O(1/n)\).

The correct iteration is: at each step, the density increases by a multiplicative factor, not additive. Specifically, the new density \(\alpha' \ge \alpha(1 + c'\alpha)\) for some \(c' > 0\). Then after \(m\) steps, \(\alpha_m \ge \alpha_0 \prod_{i=0}^{m-1}(1 + c'\alpha_i)\). Since \(\alpha_i\) is increasing, \(\alpha_m \ge \alpha_0(1 + c'\alpha_0)^m\). For this to remain at most 1, we need \((1 + c'\alpha_0)^m \le 1/\alpha_0\), so \(m \le \log(1/\alpha_0) / \log(1 + c'\alpha_0) \le O(1/(c'\alpha_0) \cdot \log(1/\alpha_0))\). But we also need \(m \le n-1\). Actually, a cleaner bookkeeping: track \(1/\alpha\). At each step, \(1/\alpha'\) decreases by a constant. So after \(O(1/\alpha)\) steps we reach density 1 (or the ambient space becomes trivial). This requires \(n \ge C/\alpha\), giving \(\alpha \ge C/n\). This gives the bound \(|A| \le C \cdot 3^n/n\). ■

Proof. The proof follows the same density increment strategy as in \(\mathbb{F}_3^n\), but with some additional technical complications.

Step 1: Embedding in \(\mathbb{Z}/N'\mathbb{Z}\). We embed \(\{1, \ldots, N\}\) into \(\mathbb{Z}/N'\mathbb{Z}\) for a prime \(N' \ge 3N\), so that any 3-AP in \(\mathbb{Z}/N'\mathbb{Z}\) with elements in \(\{1, \ldots, N\}\) is a genuine 3-AP. Set \(A \subseteq \mathbb{Z}/N'\mathbb{Z}\), \(|A| = \alpha N'\) where \(\alpha \ge \delta/3\).

\[ \Lambda_3(A) = \sum_{a, d \in \mathbb{Z}/N'\mathbb{Z}} 1_A(a) 1_A(a+d) 1_A(a+2d) = N' \sum_r \widehat{1_A}(r)^2 \widehat{1_A}(-2r). \]\[ \Lambda_3(A) = \sum_{x, y, z \in \mathbb{Z}/N'\mathbb{Z}} 1_A(x) 1_A(y) 1_A(z) \cdot \mathbf{1}[x - 2y + z = 0]. \]\[ \Lambda_3(A) = N' \sum_r \widehat{f}(r)^2 \overline{\widehat{f}(2r)}, \]\[ \Lambda_3(A) = (N')^3 \mathbb{E}_{x,y,z} f(x) f(y) f(z) \mathbf{1}[x-2y+z=0] = (N')^2 \sum_r \widehat{f}(r)^2 \widehat{f}(-2r). \]\[ \left|\alpha^3 - \frac{\alpha}{(N')^2}\right| \le \left|\sum_{r \neq 0} \widehat{f}(r)^2 \widehat{f}(-2r)\right| \le \sup_{r \neq 0} |\widehat{f}(r)| \cdot \sum_r |\widehat{f}(r)|^2 = \sup_{r \neq 0} |\widehat{f}(r)| \cdot \alpha. \]

So if \(A\) has no non-trivial 3-AP, then \(\sup_{r \neq 0} |\widehat{f}(r)| \ge \alpha^2 - O(1/N') \ge \alpha^2/2\) for \(N'\) large enough.

Step 3: Density increment on a long arithmetic progression. A large Fourier coefficient \(|\widehat{f}(r)| \ge \alpha^2/2\) at some \(r \neq 0\) means that \(A\) correlates with the character \(e^{2\pi i rx/N'}\). Unlike the \(\mathbb{F}_p^n\) case where we could pass to a subspace, in \(\mathbb{Z}/N'\mathbb{Z}\) we partition into long arithmetic progressions. Specifically, partition \(\mathbb{Z}/N'\mathbb{Z}\) into roughly \(r\) arithmetic progressions of common difference \(r\) and length roughly \(N'/r\). On at least one of these progressions \(P\), the density of \(A\) is at least \(\alpha + c\alpha^2\).

Step 4: Iteration. We now have a dense subset of a long arithmetic progression with no 3-AP and increased density. By a linear change of variables, a subset of an arithmetic progression of length \(M\) and common difference \(d\) is equivalent to a subset of \(\{1, \ldots, M\}\). So we can iterate the argument.

At each step, the density increases by \(c\alpha^2\), and the length of the ambient progression decreases by a factor. After \(O(1/\alpha)\) steps, the density exceeds 1, which is a contradiction. The length must remain positive throughout, giving the bound \(N \ge \exp(\exp(C/\delta))\) or similar, which proves that \(r_3(N) = o(N)\). Roth’s original argument gives \(r_3(N) = O(N/\log\log N)\). ■

Proof. The key idea is to use the sphere in high dimensions. Consider the set of integers representable in base \(d\) with digits in \(\{0, 1, \ldots, d-1\}\): \[ \phi(x_1, \ldots, x_k) = x_1 + x_2 d + x_3 d^2 + \cdots + x_k d^{k-1} \] for \(x_i \in \{0, 1, \ldots, d-1\}\). The map \(\phi\) sends the \(k\)-dimensional cube \(\{0, \ldots, d-1\}^k\) into \(\{0, 1, \ldots, d^k - 1\}\). Crucially, \(\phi\) preserves arithmetic progressions: if \(x, y, z \in \{0, \ldots, d-1\}^k\) form a 3-AP (i.e., \(x + z = 2y\) in \(\mathbb{Z}^k\)), then \(\phi(x) + \phi(z) = 2\phi(y)\) in \(\mathbb{Z}\) (provided we choose \(d\) large enough to avoid carries, specifically \(d \ge 3\) so that all digit sums stay below \(2d\), and actually we need \(2(d-1) < 2d\), which is always true, but carries happen when digits sum to \(\ge d\); to avoid this, replace \(d\) by \(2d\) in the base).

Now, consider the sphere \(S_r = \{x \in \{0, \ldots, d-1\}^k : x_1^2 + x_2^2 + \cdots + x_k^2 = r\}\). Since \(x + z = 2y\) implies \(\|x\|^2 + \|z\|^2 = 2\|y\|^2 + \frac{1}{2}\|x-z\|^2 \ge 2\|y\|^2\), a 3-AP on the sphere requires \(\|x\|^2 = \|y\|^2 = \|z\|^2\), which then forces \(x - z = 0\) — but this is not quite right. The point is that the sphere is 3-AP-free as a subset of \(\mathbb{Z}^k\) if \(\|x\|^2 + \|z\|^2 > 2\|y\|^2\) for non-constant APs, which follows from strict convexity of \(\|\cdot\|^2\).

More precisely: if \(x + z = 2y\), then \(\|x\|^2 + \|z\|^2 = 2\|y\|^2 + \frac{1}{2}\|x - z\|^2\), so \(\|x\|^2 + \|z\|^2 \ge 2\|y\|^2\) with equality if and only if \(x = z\). Hence if \(x, y, z \in S_r\), then \(2r = \|x\|^2 + \|z\|^2 \ge 2\|y\|^2 = 2r\), so equality holds and \(x = z\), hence \(y = x = z\). Thus \(S_r\) is 3-AP-free in \(\mathbb{Z}^k\).

By pigeonhole, since \(\sum_r |S_r| = d^k\) and \(r\) ranges over \(\{0, 1, \ldots, k(d-1)^2\}\), there exists \(r\) with \(|S_r| \ge d^k / (k(d-1)^2 + 1) \ge d^k / (kd^2)\).

Setting \(N \approx d^k\), we optimize: choose \(k \approx \sqrt{\log N / \log d}\) and \(d\) appropriately. The result is \(|S_r| \ge N \exp(-C\sqrt{\log N})\) for some constant \(C\). ■

Proof sketch. The proof proceeds by an "energy increment" argument. Define the energy (or index) of a partition \(\mathcal{P} = \{V_1, \ldots, V_k\}\) to be \[ q(\mathcal{P}) = \sum_{i < j} \frac{|V_i| \cdot |V_j|}{|V|^2} \, d(V_i, V_j)^2. \] This quantity satisfies \(0 \le q(\mathcal{P}) \le 1\).

The key claim is: if the partition \(\mathcal{P}\) is not \(\varepsilon\)-regular (i.e., too many pairs are irregular), then we can refine \(\mathcal{P}\) to a new partition \(\mathcal{P}'\) with \(q(\mathcal{P}') \ge q(\mathcal{P}) + \varepsilon^5\) (or a similar polynomial in \(\varepsilon\)).

Since the energy is bounded above by 1 and increases by at least \(\varepsilon^5\) at each step, the process terminates after at most \(1/\varepsilon^5\) refinements. At each step, the number of parts may increase (each part is subdivided into a bounded number of subparts), leading to the tower-type bound for \(M(\varepsilon, m)\).

To prove the key claim: if \((V_i, V_j)\) is an irregular pair, then by definition there exist \(A \subseteq V_i\) and \(B \subseteq V_j\) with \(|A| \ge \varepsilon |V_i|\), \(|B| \ge \varepsilon |V_j|\), and \(|d(A, B) - d(V_i, V_j)| > \varepsilon\). Refining the partition by splitting \(V_i\) into \(A\) and \(V_i \setminus A\) (and similarly \(V_j\)) increases the energy. By a convexity argument (the energy is the sum of squared densities, and splitting a pair with unequal sub-densities increases the sum of squares), the energy increment is at least \(\varepsilon^5\). ■

Proof sketch. Apply the regularity lemma with parameter \(\varepsilon' \ll \varepsilon\) to get a partition \(V = V_0 \sqcup V_1 \sqcup \cdots \sqcup V_k\). Remove all edges incident to \(V_0\), all edges inside the parts \(V_i\), all edges between irregular pairs, and all edges between regular pairs of density less than \(\varepsilon'\). Each of these removes at most \(O(\varepsilon') n^2\) edges.

If a triangle remains in the cleaned graph, its three vertices must lie in three distinct parts \(V_i, V_j, V_l\) that form an \(\varepsilon'\)-regular triple with densities at least \(\varepsilon'\). By the counting lemma, the number of such triangles is at least \(c(\varepsilon') n^3\) for some \(c(\varepsilon') > 0\). So if \(\delta < c(\varepsilon')\), no triangle survives, and the total number of removed edges is \(O(\varepsilon') n^2 \le \varepsilon n^2\). ■

Proof. Let \(A \subseteq \{1, \ldots, N\}\) with \(|A| \ge \delta N\). We construct a tripartite graph \(G\) on vertex sets \(X = Y = Z = \mathbb{Z}/N'\mathbb{Z}\) (for an appropriate \(N' \ge 3N\)) as follows:

• \(xy \in E(G)\) (for \(x \in X, y \in Y\)) if \(y - x \in A\),
• \(yz \in E(G)\) (for \(y \in Y, z \in Z\)) if \(z - y \in A\),
• \(xz \in E(G)\) (for \(x \in X, z \in Z\)) if \((z - x)/2 \in A\) (assuming \(N'\) is odd so that 2 is invertible).

A triangle \((x, y, z)\) in \(G\) corresponds to \(y - x, z - y, (z-x)/2 \in A\), which means \(y - x, z - y, (y-x + z-y)/2 \in A\). Setting \(a = y - x\), \(c = z - y\), \(b = (a+c)/2\), this is the triple \(a, b, c \in A\) with \(a + c = 2b\), i.e., \((a, b, c)\) is a 3-AP in \(A\).

Since each element \(a \in A\) gives rise to \(N'\) triangles (varying \(x\)), and each 3-AP \((a, b, c)\) gives rise to \(N'\) triangles, the number of triangles is at least \(\delta (N')^2\) (from the trivial APs \(a = b = c\)). By the triangle removal lemma, if \(A\) contains no non-trivial 3-AP, then the graph can be made triangle-free by removing \(o((N')^2)\) edges. But the trivial APs force at least \(|A| \cdot N' \ge \delta (N')^2\) triangles, each requiring the removal of an edge. This gives a contradiction for \(N'\) large enough. ■

Proof. We proceed by induction on \(n\). For \(n = 1\), a non-zero polynomial of degree \(d_1\) over a field has at most \(d_1\) roots, so if \(|S_1| > d_1\), there must exist \(s_1 \in S_1\) with \(f(s_1) \neq 0\). \[ f(x_1, \ldots, x_n) = \sum_{j=0}^{d_1} x_1^j \cdot g_j(x_2, \ldots, x_n) \]

where each \(g_j\) is a polynomial in \(x_2, \ldots, x_n\). The coefficient of \(x_1^{d_1} x_2^{d_2} \cdots x_n^{d_n}\) in \(f\) is the coefficient of \(x_2^{d_2} \cdots x_n^{d_n}\) in \(g_{d_1}\), which is non-zero by assumption. The degree of \(g_{d_1}\) is at most \(d - d_1 = d_2 + \cdots + d_n\), and the coefficient of the leading monomial \(x_2^{d_2} \cdots x_n^{d_n}\) is non-zero.

\[ h(x_1) = f(x_1, s_2, \ldots, s_n) = \sum_{j=0}^{d_1} x_1^j \cdot g_j(s_2, \ldots, s_n). \]

The leading coefficient of \(h\) is \(g_{d_1}(s_2, \ldots, s_n) \neq 0\), so \(h\) is a polynomial of degree exactly \(d_1\). Since \(|S_1| > d_1\), there exists \(s_1 \in S_1\) with \(h(s_1) = f(s_1, s_2, \ldots, s_n) \neq 0\). ■

Proof. Let \(N = |\{x \in \mathbb{F}_p^n : f_1(x) = \cdots = f_m(x) = 0\}|\). We compute \(N \pmod{p}\) using the identity (valid over \(\mathbb{F}_p\)): \[ \mathbf{1}[y = 0] = 1 - y^{p-1} \quad \text{for all } y \in \mathbb{F}_p. \] Thus \[ N = \sum_{x \in \mathbb{F}_p^n} \prod_{i=1}^m (1 - f_i(x)^{p-1}). \] Expanding the product, \(N\) is a sum of terms of the form \(\pm \sum_{x \in \mathbb{F}_p^n} f_{i_1}(x)^{p-1} \cdots f_{i_k}(x)^{p-1}\). Each such term is a sum over \(\mathbb{F}_p^n\) of a polynomial of degree at most \((p-1) \sum_i \deg f_i < (p-1)n\).

Now we use the key fact: for a polynomial \(g(x_1, \ldots, x_n)\) over \(\mathbb{F}_p\) of degree less than \((p-1)n\), we have \(\sum_{x \in \mathbb{F}_p^n} g(x) = 0\) in \(\mathbb{F}_p\). This follows from the observation that the sum over \(\mathbb{F}_p\) of \(x^k\) is \(-1\) if \((p-1) | k\) and \(k > 0\), and \(0\) otherwise; a monomial of degree less than \((p-1)n\) cannot have all exponents divisible by \(p-1\) unless some exponent is zero, and the corresponding sum factors as a product of one-dimensional sums, at least one of which vanishes.

Hence \(N \equiv 0 \pmod{p}\) when computed modulo the corrections from the constant term, which is the sum of \(1\) over all \(x\), giving \(p^n \equiv 0\). More carefully, \(N \equiv p^n \equiv 0 \pmod{p}\). Wait, the constant term contribution is 1 from each \(x\), giving \(p^n\). But we need \(N = \sum_x \prod_i (1 - f_i(x)^{p-1})\), and each term in the expansion, when summed over \(\mathbb{F}_p^n\), vanishes modulo \(p\) by the degree argument, except possibly the constant term \(\sum_x 1 = p^n \equiv 0 \pmod{p}\). So \(N \equiv 0 \pmod{p}\). ■

Proof (for \(n = p\) prime, via Chevalley-Warning). Let \(a_1, \ldots, a_{2p-1}\) be integers. Consider the system of polynomials over \(\mathbb{F}_p\): \[ f_1(x_1, \ldots, x_{2p-1}) = \sum_{i=1}^{2p-1} x_i^{p-1} - p, \qquad f_2(x_1, \ldots, x_{2p-1}) = \sum_{i=1}^{2p-1} a_i x_i^{p-1}. \] Wait, we need a slightly different formulation. Consider \(x_1, \ldots, x_{2p-1} \in \{0, 1\} \subseteq \mathbb{F}_p\) representing a choice of \(p\) elements from the \(2p-1\) given integers. Over \(\mathbb{F}_p\), \(x_i^{p-1} = \mathbf{1}[x_i \neq 0]\) for \(x_i \in \mathbb{F}_p\). \[ g_1 = x_1^{p-1} + x_2^{p-1} + \cdots + x_{2p-1}^{p-1} - (p-1), \qquad g_2 = a_1 x_1 + a_2 x_2 + \cdots + a_{2p-1} x_{2p-1}. \]

We want to find \(x \in \mathbb{F}_p^{2p-1} \setminus \{0\}\) with \(x_i \in \{0, 1\}\) for all \(i\) (in \(\mathbb{F}_p\)), \(\sum x_i^{p-1} = p\) (i.e., exactly \(p\) of the \(x_i\) are nonzero), and \(\sum a_i x_i \equiv 0 \pmod p\). This is a bit more delicate.

Here is a cleaner approach via the Combinatorial Nullstellensatz. We use Alon’s theorem directly: consider the polynomial \(f(x_1, \ldots, x_{2p-1}) = \left(\sum_{i=1}^{2p-1} a_i x_i\right)^{p-1} \cdot \left(\sum_{i=1}^{2p-1} x_i^{p-1}\right)\) … but this becomes complicated.

\[ f(x) = a_1 x_1 + a_2 x_2 + \cdots + a_{2p-1} x_{2p-1}, \qquad g(x) = x_1^{p-1} + \cdots + x_{2p-1}^{p-1}. \]

The degrees are \(\deg f = 1\) and \(\deg g = p-1\), so \(\deg f + \deg g = p < 2p - 1 = n\) (the number of variables). By Chevalley-Warning, the number of common zeros is divisible by \(p\). The zero vector is one solution, so there is another solution \(x \neq 0\) with \(\sum a_i x_i \equiv 0 \pmod p\) and … but \(g(x) = 0\) means the number of non-zero coordinates is divisible by \(p-1\)… this is not quite what we want.

Actually, the standard proof uses the following approach. We want to show that among any \(2p-1\) elements of \(\mathbb{Z}/p\mathbb{Z}\), there exist \(p\) whose sum is zero. Consider the elementary symmetric polynomials and use the Davenport constant. The Chevalley-Warning approach works as follows.

\[ P(x_1, \ldots, x_{2p-1}) = \left(1 - \left(\sum_{i=1}^{2p-1} a_i x_i \right)^{p-1}\right) \cdot \prod_{i=1}^{2p-1}(1 - x_i^{p-1}). \]

This polynomial evaluates to 1 at a point \(x = (x_1, \ldots, x_{2p-1}) \in \mathbb{F}_p^{2p-1}\) if and only if all \(x_i = 0\) and the “vacuously” the sum condition holds. But we actually want to select a \(p\)-element subset…

The most direct proof for the prime case uses the following: by the Davenport constant \(D(\mathbb{Z}/p\mathbb{Z}) = 2p - 1\), any sequence of \(2p - 1\) elements has a non-empty subsequence of length at most \(p\) summing to zero. Since the Davenport constant is defined as the smallest \(d\) such that every sequence of length \(d\) has a non-empty zero-sum subsequence, and the Erdős-Ginzburg-Ziv theorem requires a zero-sum subsequence of length exactly \(p\), a slightly different argument is needed. The complete proof uses a combination of the Cauchy-Davenport theorem and induction, or alternatively the Chevalley-Warning theorem applied to appropriately constructed polynomials. ■

Proof. We use the following formulation. For \(A \subseteq \mathbb{F}_3^n\), define the \(|A| \times |A|\) matrix \(M\) indexed by \(A \times A\) with entries \[ M_{x,y} = \delta(x + y \in A), \] where \(\delta\) is the indicator function. If \(A\) is cap-set-free (no 3-AP), then \(x + y \in A\) with \(x, y \in A\) implies \(x + y + z = 0\) has a solution with \(z = -(x+y) \in A\), which would be a 3-AP unless \(x = y = z\). In \(\mathbb{F}_3\), \(x + y + z = 0\) and \(x = y\) gives \(z = -2x = x\), so \(x = y = z\). Thus \(M_{x,y} \neq 0\) implies \(x + y \in A\) implies \(x = y\) (if no non-trivial 3-AP), so \(M_{x,x} = \delta(2x \in A) = \delta(-x \in A)\). \[ F(x, y) = \prod_{a \in \mathbb{F}_3^n \setminus A} (1 - (x + y - a)^{3^n - 1}) \]

… this is getting complicated. Let us use the standard “slice rank” argument.

Define the tensor \(T: A \times A \times A \to \mathbb{F}_3\) by \(T(x, y, z) = \delta(x + y + z = 0)\). If \(A\) has no 3-AP, then \(T\) is supported on the “diagonal” \(\{(x, x, x) : x \in A, \, 3x = 0\}\), and since we are in \(\mathbb{F}_3\), \(3x = 0\) always, so the support is \(\{(x, x, x) : x \in A\}\). Thus the diagonal restriction of \(T\) has \(|A|\) non-zero entries.

\[ T(x, y, z) = \sum_i f_i(x) \cdot g_i(y, z) + \sum_j h_j(y) \cdot k_j(x, z) + \sum_l m_l(z) \cdot n_l(x, y). \]\[ \delta(x + y + z = 0) = \prod_{i=1}^n (1 - (x_i + y_i + z_i)^2). \]\[ \prod_{i=1}^n (1 - (x_i + y_i + z_i)^2) = \sum_{S \subseteq [n]} (-1)^{|S|} \prod_{i \in S} (x_i + y_i + z_i)^2. \]\[ \delta(x+y+z = 0) = \sum_{\alpha + \beta + \gamma = (2, 2, \ldots, 2)_S \text{ for various } S} c_{\alpha,\beta,\gamma} \, x^\alpha y^\beta z^\gamma, \]

where the monomials satisfy \(\deg_x + \deg_y + \deg_z = 2|S|\) with each coordinate contributing degree at most 2. In \(\mathbb{F}_3^n\), we reduce modulo \(x_i^3 = x_i\), so each variable has degree at most 2 in each coordinate.

The key observation: the total degree is \(2n\), so for each monomial \(x^\alpha y^\beta z^\gamma\) appearing in the expansion, we have \(|\alpha| + |\beta| + |\gamma| = 2n\) (where \(|\alpha| = \sum \alpha_i\), with each \(\alpha_i \in \{0, 1, 2\}\)). By the pigeonhole principle, at least one of \(|\alpha|, |\beta|, |\gamma|\) is at most \(2n/3\).

\[ T(x, y, z) = \sum_{|\alpha| \le 2n/3} c_\alpha(x) \cdot g_\alpha(y, z) + \sum_{|\beta| \le 2n/3} d_\beta(y) \cdot h_\beta(x, z) + \sum_{|\gamma| \le 2n/3} e_\gamma(z) \cdot k_\gamma(x, y), \]

where the sums are over multi-indices with the indicated degree bounds.

The number of multi-indices \(\alpha \in \{0, 1, 2\}^n\) with \(|\alpha| \le 2n/3\) is at most \(D_n\), where \(D_n = |\{\alpha \in \{0,1,2\}^n : |\alpha| \le 2n/3\}|\).

Thus the slice rank of \(T\) is at most \(3 D_n\).

Since \(T\) restricted to the diagonal has \(|A|\) non-zero entries, and the slice rank gives an upper bound on the diagonal support size (by a simple linear algebra argument: on the diagonal, the decomposition gives \(T(x,x,x) = \sum_i f_i(x) g_i(x,x) + \cdots\), and the rank of the diagonal matrix is at most the slice rank, so \(|A| \le 3D_n\)).

\[ D_n \le \left(\frac{3}{2^{2/3}}\right)^n. \]

Therefore \(|A| \le 3 D_n \le 3 (3/2^{2/3})^n\). ■

Proof sketch. The idea is to construct the dynamical system from the combinatorial data. Let \(\Omega = \{0, 1\}^{\mathbb{Z}}\) with the product topology, and let \(T: \Omega \to \Omega\) be the left shift: \((T\omega)(n) = \omega(n+1)\). The set \(A\) defines a point \(\omega_A \in \Omega\) by \(\omega_A(n) = 1_A(n)\). Let \(X = \overline{\{T^n \omega_A : n \in \mathbb{Z}\}}\) be the orbit closure, and let \(E = \{\omega \in X : \omega(0) = 1\}\).

To construct the measure \(\mu\), take a subsequence of the Cesàro averages \(\frac{1}{N} \sum_{n=1}^{N} \delta_{T^n \omega_A}\) that converges weak-* to a \(T\)-invariant probability measure \(\mu\) on \(X\) (this exists by compactness of the space of probability measures). One can ensure \(\mu(E) = \bar{d}(A)\) by choosing the subsequence appropriately. The correspondence between patterns in \(A\) and multiple recurrence of \(T\) then follows from the construction. ■

Proof sketch. Furstenberg's proof proceeds by structural induction on the complexity of the system. The base case is when \((X, T)\) is "compact" (has discrete spectrum), where the result follows from a generalization of Weyl's equidistribution theorem. The general case reduces to the compact case via the "Furstenberg structure theorem," which decomposes any system into a tower of extensions, each of which is either compact or "weak-mixing." The weak-mixing case is handled by a "van der Waerden" argument at the measure-theoretic level.

The key innovation is the use of the Furstenberg-Zimmer structure theorem, which constructs the maximal compact factor of a system. For a \(\mathbb{Z}\)-action, this is the Kronecker factor (the closed linear span of the eigenfunctions). The multiple recurrence theorem is first proved for the Kronecker factor (using equidistribution of polynomial sequences), and then extended to the full system by showing that the “remainder” (the weak-mixing part) does not affect the limit. ■

Proof architecture. The proof proceeds in several major stages, each representing a significant technical achievement.

Stage 1: Reformulation. The primes have density zero in the integers, so Szemerédi’s theorem does not apply directly. Green and Tao show that it suffices to find a “pseudo-random” measure \(\nu\) that majorizes the primes (or rather, a modified version of the primes) and satisfies certain correlation conditions.

Stage 2: The transference principle. The key innovation is a “transference principle” that allows one to transfer results from the dense setting (Szemerédi’s theorem for dense subsets of \(\{1, \ldots, N\}\)) to the sparse setting (subsets of a pseudo-random set). Green and Tao show that if \(\nu\) is a pseudo-random measure (satisfying a “linear forms condition” and a “correlation condition”) and \(A\) is a subset of the support of \(\nu\) with positive relative density, then \(A\) contains \(k\)-APs.

The transference principle works by showing that the “balanced function” \(f = 1_A - \delta \cdot \nu\) (where \(\delta\) is the relative density) has small Gowers \(U^{k-1}\) norm relative to the pseudo-random measure. This allows one to replace \(1_A\) by \(\delta \cdot \nu\) in the counting operator for \(k\)-APs, reducing to the pseudo-random case, which is easy.

Stage 3: Constructing the pseudo-random measure. Green and Tao construct \(\nu\) using a “W-trick” (working modulo the product of small primes to remove the obvious bias from the primes) and Goldston-Yıldırım sieve weights. The key input from analytic number theory is a truncated version of the Hardy-Littlewood conjectures, verified for the modified sieve weights.

Stage 4: Verifying the linear forms condition. The most technically demanding part is showing that \(\nu\) satisfies the linear forms condition: for any system of linear forms \(\psi_i(x) = L_i \cdot x + b_i\) of finite complexity, the average of \(\prod_i \nu(\psi_i(x))\) equals \(1 + o(1)\). This requires deep estimates from multiplicative number theory, specifically a generalization of the Goldston-Pintz-Yıldırım estimates. ■