# 10 Approximate homomorphism version of PFR

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\).

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

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

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

From double counting we have

The claim now follows from the Cauchy–Schwarz inequality

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)

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

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\).

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

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

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

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

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.