# 7 Proof of PFR

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\).

Cover \(A\) greedily by disjoint translates of \(B\).

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

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

By Theorem 6.24, we may thus find a subspace \(H\) of \(\mathbb {F}_2^n\) such that

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

proving 1. From Definition 3.8, 2 is equivalent to

By Lemma 2.8 we conclude the existence of a point \(x_0 \in \mathbb {F}_p^n\) such that

or equivalently

Applying Lemma 7.1, we may thus cover \(A\) by at most

translates of

This proves the claim.

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|\).

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

translates of \(H'\), and the claim again follows from 1.

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|\).

Apply Theorem 7.3 to the group generated by \(A\), which is isomorphic to \(\mathbb {F}_2^n\) for some \(n\).