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 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 ▶

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 $ϕ : G \to G^{'}$ and a constant $c \in G^{'}$ such that $f (x) = ϕ (x) + c$ for at least $| G | / (2^{144} * K^{122})$ 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^{2 C_{2}}$ and $| A^{'} + A^{'} | \leq C_{1} C_{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_{1} C_{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, ϕ (x)) : x \in G}$ . As $ϕ$ is a homomorphism, each such translate can be written in the form ${(x, ϕ (x) + c) : x \in G}$ for some $c \in G^{'}$ . The number of translates is bounded by

| c |^{2} \frac{| H |}{| A^{'} |} \leq {(L^{5} \frac{| A^{'} |^{1 / 2}}{| H |^{1 / 2}})}^{2} \frac{| H |}{| A^{'} |} = L^{10} .

By the pigeonhole principle, one of these translates must then contain at least $| A^{'} | / L^{10} \geq | G | / (C_{1} C_{3} K^{2 (C_{2} + C_{4})})^{10} (C_{1} K^{2 C_{2}})$ elements of $A^{'}$ (and hence of $A$ ), and the claim follows. □