10 Approximate homomorphism version of PFR

Definition 10.1 Additive energy

✓

If \(G\) is a group, and \(A\) is a finite subset of \(G\), the additive energy \(E(A)\) of \(A\) is the number of quadruples \((a_1,a_2,a_3,a_4) \in A^4\) such that \(a_1+a_2 = a_3+a_4\).

Lemma 10.2 Cauchy–Schwarz bound

✓

If \(G\) is a group, \(A,B\) are finite subsets of \(G\), then

\[ E(A) \geq \frac{|\{ (a,a') \in A \times A: a+a' \in B \} |^2}{|B|}. \]

Proof ▶

If \(B\) is empty then the claim is trivial (with the Lean convention \(0/0\)), so without loss of generality \(B\) is non-empty. We can rewrite

\[ |\{ (a,a') \in A \times A: a+a' \in B \} | = \sum _{b \in B} r(b) \]

where \(r: G \to \mathbb {N}\) is the counting function

\[ r(b) := |\{ (a,a') \in A \times A: a+a' = b \} |. \]

From double counting we have

\[ \sum _{b \in G} r(b)^2 = E(A). \]

The claim now follows from the Cauchy–Schwarz inequality

\[ (\sum _{b \in B} r(b))^2 \leq |B| \sum _{b \in B} r(b)^2. \]

Lemma 10.3 Balog–Szemerédi–Gowers lemma

✓

Let \(G\) be an abelian group, and let \(A\) be a finite non-empty set with \(E(A) \geq |A|^3 / K\) for some \(K \geq 1\). Then there is a subset \(A'\) of \(A\) with \(|A'| \geq |A| / (C_1 K^{C_2})\) and \(|A'-A'| \leq C_3 K^{C_4} |A|\), where (provisionally)

\[ C_1 = 2^4, C_2 = 1, C_3 = 2^{10}, C_4 = 5. \]

Proof ▶

See https://terrytao.files.wordpress.com/2024/01/simplebsg.pdf

Theorem 10.4 Approximate homomorphism form of PFR

✓

Let \(G,G'\) be finite abelian \(2\)-groups. Let \(f: G \to G'\) be a function, and suppose that there are at least \(|G|^2 / K\) pairs \((x,y) \in G^2\) such that

\[ f(x+y) = f(x) + f(y). \]

Then there exists a homomorphism \(\phi : G \to G'\) and a constant \(c \in G'\) such that \(f(x) = \phi (x)+c\) for at least \(|G| / (2 ^{172} * K ^{146})\) values of \(x \in G\).

Proof ▶

Consider the graph \(A \subset G \times G'\) defined by

\[ A := \{ (x,f(x)): x \in G \} . \]

Clearly, \(|A| = |G|\). By hypothesis, we have \(a+a' \in A\) for at least \(|A|^2/K\) pairs \((a,a') \in A^2\). By Lemma 10.2, this implies that \(E(A) \geq |A|^3/K^2\). Applying Lemma 10.3, we conclude that there exists a subset \(A' \subset A\) with \(|A'| \geq |A|/C_1 K^{2C_2}\) and \(|A'+A'| \leq C_1C_3 K^{2(C_2+C_4)} |A'|\). Applying Lemma 8.10, we may find a subspace \(H \subset G \times G'\) such that \(|H| / |A'| \in [L^{-10}, L^{10}\) and a subset \(c\) of cardinality at most \(L^6 |A'|^{1/2} / |H|^{1/2}\) such that \(A' \subseteq c + H\), where \(L = C_1C_3 K^{2(C_2+C_4)}\). If we let \(H_0,H_1\) be as in Lemma 9.2, this implies on taking projections the projection of \(A'\) to \(G\) is covered by at most \(|c|\) translates of \(H_0\). This implies that

\[ |c| |H_0| \geq |A'|; \]

since \(|H_0| |H_1| = |H|\), we conclude that

\[ |H_1| \leq |c| |H|/|A'|. \]

By hypothesis, \(A'\) is covered by at most \(|c|\) translates of \(H\), and hence by at most \(|c| |H_1|\) translates of \(\{ (x,\phi (x)): x \in G \} \). As \(\phi \) is a homomorphism, each such translate can be written in the form \(\{ (x,\phi (x)+c): x \in G \} \) for some \(c \in G'\). The number of translates is bounded by

\[ |c|^2 \frac{|H|}{|A'|} \leq \left(L^6 \frac{|A'|^{1/2}}{|H|^{1/2}}\right)^2 \frac{|H|}{|A'|} = L^{12}. \]

By the pigeonhole principle, one of these translates must then contain at least \(|A'|/L^{12} \geq |G| / (C_1C_3 K^{2(C_2+C_4)})^{12} (C_1 K^{2C_2})\) elements of \(A'\) (and hence of \(A\)), and the claim follows.