4 The 100% version of PFR

Definition 4.1 Symmetry group

✓

If $X$ is a $G$ -valued random variable, then the symmetry group $Sym [X]$ is the set of all $h \in G$ such that $X + h$ has the same distribution as $X$ .

Lemma 4.2 Symmetry group is a group

✓

If $X$ is a $G$ -valued random variable, then $Sym [X]$ is a subgroup of $G$ .

Proof ▶

Lemma 4.3 Zero Ruzsa distance implies large symmetry group

✓

If $X$ is a $G$ -valued random variable such that $d [X; X] = 0$ , and $x, y \in G$ are such that $P [X = x], P [X = y] > 0$ , then $x - y \in Sym [X]$ .

Proof ▶

Let $X_{1}, X_{2}$ be independent copies of $X$ (from Lemma 3.7). Let $A$ denote the range of $X$ . From Lemma 3.11 and Lemma 3.10 we have

H [X_{1} - X_{2}] = H [X_{1}] .

Observe from Lemma 2.12 that

H [X_{1} - X_{2} | X_{2}] = H [X_{1} | X_{2}] = H [X_{1}]

and hence by Lemma 2.16

I [X_{1} - X_{2} : X_{1}] = 0.

By Lemma 2.23, $X_{1} - X_{2}$ and $X_{1}$ are therefore independent, thus the law of $(X_{1} - X_{2} | X_{1} = x)$ does not depend on $x \in A$ . The claim follows.

Lemma 4.4 Translate is uniform on symmetry group

✓

If $X$ is a $G$ -valued random variable with $d [X; X] = 0$ , and $x_{0}$ is a point with $P [X = x_{0}] > 0$ , then $X - x_{0}$ is uniformly distributed on $Sym [X]$ .

Proof ▶

The law of $X - x_{0}$ is invariant under $Sym [X]$ , non-zero at the origin, and supported on $Sym [X]$ , giving the claim.

Lemma 4.5 Symmetric 100% inverse theorem

✓

Suppose that $X$ is a $G$ -valued random variable such that $d [X; X] = 0$ . Then there exists a subgroup $H \leq G$ such that $d [X; U_{H}] = 0$ .

Proof ▶

Take $H$ to be the symmetry group of $X$ , which is a group by Lemma 4.2. From Lemma 4.4, $X - x_{0}$ is uniform on $H$ , and $d [X; X - x_{0}] = d [X; X] \leq 0$ , and the claim follows.

Corollary 4.6 General 100% inverse theorem

✓

Suppose that $X_{1}, X_{2}$ are $G$ -valued random variables such that $d [X_{1}; X_{2}] = 0$ . Then there exists a subgroup $H \leq G$ such that $d [X_{1}; U_{H}] = d [X_{2}; U_{H}] = 0$ .

Proof ▶

Using Lemma 3.18 and Lemma 3.15 we have $d [X_{1}; X_{1}] = 0$ , hence by Lemma 4.5 $d [X_{1}; U_{H}] = 0$ for some subgroup $H$ . By Lemma 3.18 and Lemma 3.15 again we also have $d [X_{2}; U_{H}]$ as required. □