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 {\bf 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 \({\bf F}_2^n\) with

\begin{equation} \label{ah} |H|/|A| \in [K^{-11}, K^{11}]. \end{equation}

Proof ▶

Let \(U_A\) be the uniform distribution on \(A\) (which exists by Lemma 2.5), thus \(\mathbb {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\), \(\mathbb {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 \(\mathbb {F}_2^n\) such that

\begin{equation} \label{uauh} d[U_A;U_H] \leq \tfrac {1}{2} C' \log K\end{equation}

with \(C' = 11\). By Lemma 3.13 we conclude that

\begin{equation*} |\log |H| - \log |A|| \leq C’ \log K, \end{equation*}

proving 1. From Definition 3.8, 2 is equivalent to

\[ \mathbb {H}[U_A - U_H] \leq \log ( |A|^{1/2} |H|^{1/2}) + \tfrac {1}{2} C' \log K. \]

By Lemma 2.8 we conclude the existence of a point \(x_0 \in \mathbb {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

\[ \bigl(A \cap (H + x_0)\bigr) - \bigl(A \cap (H + x_0)\bigr) \subseteq H. \]

This proves the claim.

Theorem 7.3 PFR

✓

If \(A \subset {\bf F}_2^n\) is non-empty and \(|A+A| \leq K|A|\), then \(A\) can be covered by most \(2K^{12}\) translates of a subspace \(H\) of \({\bf 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| {\gt} |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

\[ 2K^{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 \(2K^{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 \(\mathbb {F}_2^n\) for some \(n\).