9 Homomorphism version of PFR
In this section, \(G, G'\) are finite abelian \(2\)-groups.
Let \(H_0\) be a subgroup of \(G\). Then every homomorphism \(\phi : H_0 \to G'\) can be extended to a homomorphism \(\tilde\phi : G \to G'\).
By induction it suffices to treat the case where \(H_0\) has index \(2\) in \(G\), but then the extension can be constructed by hand.
Let \(H\) be a subgroup of \(G \times G'\). Then there exists a subgroup \(H_0\) of \(G\), a subgroup \(H_1\) of \(G'\), and a homomorphism \(\phi : G \to G'\) such that
In particular, \(|H| = |H_0| |H_1|\).
We can take \(H_0\) to be the projection of \(H\) to \(G\), and \(H_1\) to be the slice \(H_1 := \{ y: (0,y) \in H \} \). One can construct \(\phi \) on \(H_0\) one generator at a time by the greedy algorithm, and then extend to \(G\) by Lemma 9.1. The cardinality bound is clear from direct counting.
Let \(f: G \to G'\) be a function, and let \(S\) denote the set
Then there exists a homomorphism \(\phi : G \to G'\) such that
Consider the graph \(A \subset G \times G'\) defined by
Clearly, \(|A| = |G|\). By hypothesis, we have
and hence \(|A+A| \leq |S| |A|\). Applying Corollary 13.40, we may find a subspace \(H \subset G \times G'\) such that \(|H|/ |A| \in [|S|^{-8}, |S|^{8}]\) and \(A\) is covered by \(c + H\) with \(|c| \le |S|^5|A|^{1/2} / |H|^{1/2}\). If we let \(H_0, H_1\) be as in Lemma 9.2, this implies on taking projections that \(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)+d): x \in G \} \) for some \(d \in G'\). Since
the result follows.