Let \(Y_1,Y_2\) be independent copies of \(Y\) (also independent of \(X\)). Since \(G\) is torsion-free we know \(X,Y_1-Y_2,X-2Y_1\) uniquely determine \(X,Y_1,Y_2\) and so

Similarly

Furthermore

By submodularity (Corollary 2.21)

Combining these inequalities

Similarly we have

and

and by submodularity (Corollary 2.21) again

Combining these inequalities (and recalling the definition of Ruzsa distance) gives

It follows that

and so (using \(\mathbb {H}(2Y)=\mathbb {H}(Y)\))

Finally note that by the triangle inequality (Lemma 3.18) we have

The result follows from \((\mathbb {H}(Y)-\mathbb {H}(X))/2\leq d[X;Y]\) (Lemma 3.13).

By Corollary 5.2 and Lemma 11.1 we have

and \(\phi (2Y)=2\phi (Y)\equiv 0\) so the left-hand side is equal to \(d[\phi (X);0]=\mathbb {H}(\phi (X))/2\) (using Lemma 3.9).

By Theorem 8.9 there exists a subgroup \(H\) such that \(d[X;U_H] + d[Y;U_H] \leq 10 d[X;Y]\). Using Lemma 3.16 we deduce that \(\mathbb {H}(\psi (X)) + \mathbb {H}(\psi (X)) \leq 20 d[X;Y]\). The second claim follows adding these inequalities and using the assumption on \(\mathbb {H}(X)+\mathbb {H}(Y)\).

Furthermore we have by Lemma 3.13

and similarly for \(Y\) and thus

Finally note that if \(H\) were trivial then \(\psi (X)=X\) and \(\psi (Y)=Y\) and hence \(\mathbb {H}(X)+\mathbb {H}(Y)=0\), which contradicts Lemma 3.15.

Let \(H\leq \mathbb {F}_2^d\) be a maximal subgroup such that

and such that there exists \(c \ge 0\) with

and

Note that this exists since \(H=\{ 0\} \) is an example of such a subgroup or we are done with this choice of \(H\).

We know that \(G/H\) is a \(2\)-elementary group and so by Lemma 11.3 there exists some non-trivial subgroup \(H'\leq G/H\) such that

and

where \(\psi ':G/H\to (G/H)/H'\). By group isomorphism theorems we know that there exists some \(H''\) with \(H\leq H''\leq G\) such that \(H'\cong H''/H\) and \(\psi ' \circ \psi (X)=\psi ''(X)\) where \(\psi '':G\to G/H''\) is the projection homomorphism.

Since \(H'\) is non-trivial we know that \(H\) is a proper subgroup of \(H''\). On the other hand we know that

and

Therefore (using the maximality of \(H\)) it must be the first condition that fails, whence

Specialize Lemma 11.4 to \(\alpha =3/5\). In the second inequality, it gives a bound \(100/3 {\lt} 34\).

The random variables \((U_A\mid \phi (U_A)=x)\) and \((U_B\mid \phi (U_B)=y)\) are equal in distribution to \(U_{A_x}\) and \(U_{B_y}\) respectively (both are uniformly distributed over their respective fibres). It follows from Proposition 5.1 that

Therefore with \(M:=\mathbb {H}(\phi (U_A))+\mathbb {H}(\phi (U_B))\) we have

Since

we have

It follows that there exists some \(x,y\in H\) such that \(\lvert A_x\rvert ,\lvert B_y\rvert \neq 0\) and

Without loss of generality we can assume that \(A\) and \(B\) are not both inside (possibly distinct) cosets of the same subgroup of \(\mathbb {Z}^d\), or we just replace \(\mathbb {Z}^d\) with that subgroup. We prove the result by induction on \(\lvert A\rvert +\lvert B\rvert \).

Let \(\phi :\mathbb {Z}^d\to \mathbb {F}_2^d\) be the natural mod-2 homomorphism. By Lemma 11.2

We now apply Lemma 11.5, obtaining some subgroup \(H\leq \mathbb {F}_2^d\) such that

and

where \(\tilde{\phi }:\mathbb {Z}^d\to \mathbb {F}_2^d/H\) is \(\phi \) composed with the projection onto \(\mathbb {F}_2^d/H\).

By Lemma 11.6 there exist \(x,y\in \mathbb {F}_2^d/H\) such that, with \(A_x=A\cap \tilde{\phi }^{-1}(x)\) and similarly for \(B_y\),

Suppose first that \(\lvert A_x\rvert +\lvert B_y\rvert =\lvert A\rvert +\lvert B\rvert \). This means that \(\tilde{\phi }(A)=\{ x\} \) and \(\tilde{\phi }(B)=\{ y\} \), and hence both \(A\) and \(B\) are in cosets of \(\ker \tilde{\phi }\). Since by assumption \(A,B\) are not in cosets of a proper subgroup of \(\mathbb {Z}^d\) this means \(\ker \tilde{\phi }=\mathbb {Z}^d\), and so (examining the definition of \(\tilde{\phi }\)) we must have \(H=\mathbb {F}_2^d\). Then our bound on \(\log \lvert H\rvert \) forces \(d\leq \frac{40}{\log 2}d[U_A;U_B]\) and we are done with \(A'=A\) and \(B'=B\).

Otherwise,

By induction we can find some \(A'\subseteq A_x\) and \(B'\subseteq B_y\) such that \(\dim A',\dim B'\leq \frac{40}{\log 2} d[U_{A_x};U_{B_y}]\leq \frac{40}{\log 2}d[U_A;U_B]\) and

Adding these inequalities implies

as required.

Immediate from Theorem 11.8 and rearranging.

As in the beginning of Theorem 7.3 the doubling condition forces \(d[U_A;U_A]\leq \log K\), and then we apply Theorem 11.9.