9 Homomorphism version of PFR

In this section, $G, G^{'}$ are finite abelian $2$ -groups.

Lemma 9.1 Hahn-Banach type theorem

✓

Let $H_{0}$ be a subgroup of $G$ . Then every homomorphism $ϕ : H_{0} \to G^{'}$ can be extended to a homomorphism $\tilde{ϕ} : G \to G^{'}$ .

Proof ▶

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.

Lemma 9.2 Goursat type theorem

✓

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 $ϕ : G \to G^{'}$ such that

H := {(x, ϕ (x) + y) : x \in H_{0}, y \in H_{1}} .

In particular, $| H | = | H_{0} | | H_{1} |$ .

Proof ▶

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 $ϕ$ 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.

Theorem 9.3 Homomorphism form of PFR

✓

Let $f : G \to G^{'}$ be a function, and let $S$ denote the set

S := {f (x + y) - f (x) - f (y) : x, y \in G} .

Then there exists a homomorphism $ϕ : G \to G^{'}$ such that

| {f (x) - ϕ (x) : x \in G} | \leq | S |^{10} .

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 \subset {(x, f (x) + s) : x \in G, s \in S}

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 | \leq | 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

| c | | H_{0} | \geq | G |;

since $| H_{0} | | H_{1} | = | H |$ , we conclude that

| H_{1} | \leq | c | | H | / | G | = | 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, ϕ (x)) : x \in G}$ . As $ϕ$ is a homomorphism, each such translate can be written in the form ${(x, ϕ (x) + d) : x \in G}$ for some $d \in G^{'}$ . Since

| c | | H_{1} | \leq | c |^{2} \frac{| H |}{| A |} \leq {(| S |^{5} \frac{| A |^{1 / 2}}{| H |^{1 / 2}})}^{2} \frac{| H |}{| A |} = | S |^{10},

the result follows. □