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 ^{144} * K ^{122})\) 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 Corollary 13.40, we may find a subspace \(H \subset G \times G'\) such that \(|H| / |A'| \in [L^{-8}, L^{8}]\) and a subset \(c\) of cardinality at most \(L^5 |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^{10} \geq |G| / (C_1C_3 K^{2(C_2+C_4)})^{10} (C_1 K^{2C_2})\) elements of \(A'\) (and hence of \(A\)), and the claim follows.
With a bit more effort, we can remove the constant term \(c\), at the cost of reducing the set of agreement slightly. We need some preliminary lemmas.
Let \(G\) be a finite abelian \(2\)-group. Then the finite abelian \(2\)-group \(\mathrm{Hom}(G,\mathbb {Z}/2\mathbb {Z})\) of homomorphisms from \(G\) to \(\mathbb {Z}/2\mathbb {Z}\) has the same order as \(G\).
By the classification of finite abelian groups, \(G\) is isomorphic to \((\mathbb {Z}/2\mathbb {Z})^n\). Then \(\mathrm{Hom}(G,\mathbb {Z}/2\mathbb {Z})\) is isomorphic to \((\mathbb {Z}/2\mathbb {Z})^n\) as well, and hence has the same order.
Let \(G\) be a finite abelian \(2\)-group, and let \(x \in G\) be non-zero. Then there are \(|G|/2\) homomorphisms \(\phi : G \to \mathbb {Z}/2\mathbb {Z}\) such that \(\phi (x) = 1\).
The map \(\phi \mapsto \phi (x)\) is a homomorphism from \(\mathrm{Hom}(G,\mathbb {Z}/2\mathbb {Z})\) to \(\mathbb {Z}/2\mathbb {Z}\), and by Lemma 10.5 the kernel has order equal to the order of \(G / \{ 0,x\} \), which is \(|G|/2\). Then the preimage of \(1\) must also be of order \(|G|/2\).
Let \(G\) be a finite abelian \(2\)-group, and let \(A\) be a subset of \(G\). Then there exists a homomorphism \(\phi : G \to \mathbb {Z}/2\mathbb {Z}\) such that \(|A \cap \phi ^{-1}(1)| \geq (|A|-1)/2\).
We have
thanks to Lemma 10.6. The claim now follows from Lemma 10.5 and the pigeonhole principle.
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'\) such that \(f(x) = \phi ''(x)\) for at least \((|G| / (2 ^{172} * K ^{146}) - 1)/2\) values of \(x \in G\).
By Theorem 10.4, there exists a homomorphism \(\phi : G \to G'\) and a constant \(c \in G'\) such that the set \(A := \{ x \in G: f(x) = \phi (x) \} \) has cardinality at least \(|G| / (2 ^{172} * K ^{146})\). By Lemma 10.7, there exists a homomorphism \(\phi ': G \to \mathbb {Z}/2\mathbb {Z}\) such that
Then the claim follows by taking \(\phi '' = \phi + \phi ' \bullet c\) (where we view \(G'\) as a \(\mathbb {Z}/2\mathbb {Z}\)-module).