7 Proof of PFR

Lemma 7.1 Ruzsa covering lemma

✓

If $A, B$ are finite non-empty subsets of a group $G$ , then $A$ can be covered by at most $| A + B | / | B |$ translates of $B - B$ .

Proof ▶

Cover $A$ greedily by disjoint translates of $B$ .

Lemma 7.2

✓

If $A \subset F_{2}^{n}$ is non-empty and $| A + A | \leq K | A |$ , then $A$ can be covered by at most $K^{13 / 2} | A |^{1 / 2} / | H |^{1 / 2}$ translates of a subspace $H$ of $F_{2}^{n}$ with

| H | / | A | \in [K^{- 11}, K^{11}] .

Proof ▶

Let $U_{A}$ be the uniform distribution on $A$ (which exists by Lemma 2.5), thus $H [U_{A}] = \log | A |$ by Lemma 2.7. By Lemma 2.3 and the fact that $U_{A} + U_{A}$ is supported on $A + A$ , $H [U_{A} + U_{A}] \leq \log | A + A |$ . By Definition 3.8, the doubling condition $| A + A | \leq K | A |$ therefore gives

d [U_{A}; U_{A}] \leq \log K .

By Theorem 6.24, we may thus find a subspace $H$ of $F_{2}^{n}$ such that

d [U_{A}; U_{H}] \leq \frac{1}{2} C^{'} \log K

with $C^{'} = 11$ . By Lemma 3.13 we conclude that

| \log | H | - \log | A | | \leq C^{'} \log K,

proving 1. From Definition 3.8, 2 is equivalent to

H [U_{A} - U_{H}] \leq \log (| A |^{1 / 2} | H |^{1 / 2}) + \frac{1}{2} C^{'} \log K .

By Lemma 2.8 we conclude the existence of a point $x_{0} \in F_{p}^{n}$ such that

p_{U_{A} - U_{H}} (x_{0}) \geq | A |^{- 1 / 2} | H |^{- 1 / 2} K^{- C^{'} / 2},

or equivalently

| A \cap (H + x_{0}) | \geq K^{- C^{'} / 2} | A |^{1 / 2} | H |^{1 / 2} .

Applying Lemma 7.1, we may thus cover $A$ by at most

\frac{| A + (A \cap (H + x_{0})) |}{| A \cap (H + x_{0}) |} \leq \frac{K | A |}{K^{- C^{'} / 2} | A |^{1 / 2} | H |^{1 / 2}} = K^{C^{'} / 2 + 1} \frac{| A |^{1 / 2}}{| H |^{1 / 2}}

translates of

(A \cap (H + x_{0})) - (A \cap (H + x_{0})) \subseteq H .

This proves the claim.

Theorem 7.3 PFR

✓

If $A \subset F_{2}^{n}$ is non-empty and $| A + A | \leq K | A |$ , then $A$ can be covered by most $2 K^{12}$ translates of a subspace $H$ of $F_{2}^{n}$ with $| H | \leq | A |$ .

Proof ▶

Let $H$ be given by Lemma 7.2. If $| H | \leq | A |$ then we are already done thanks to 1. If $| H | > | A |$ then we can cover $H$ by at most $2 | H | / | A |$ translates of a subspace $H^{'}$ of $H$ with $| H^{'} | \leq | A |$ . We can thus cover $A$ by at most

2 K^{13 / 2} \frac{| H |^{1 / 2}}{| A |^{1 / 2}}

translates of $H^{'}$ , and the claim again follows from 1.

Corollary 7.4 PFR in infinite groups

✓

If $G$ is an abelian $2$ -torsion group, $A \subset G$ is non-empty finite, and $| A + A | \leq K | A |$ , then $A$ can be covered by most $2 K^{12}$ translates of a finite group $H$ of $G$ with $| H | \leq | A |$ .

Proof ▶

Apply Theorem 7.3 to the group generated by $A$ , which is isomorphic to $F_{2}^{n}$ for some $n$ . □