We have

thanks to Lemma 2.2 and Lemma 2.13, giving the claim.

By Lemma 2.16 it suffices to show that \(\mathbb {H}[Y|X] \leq \mathbb {H}[Y|f(X)]\). But this follows from Corollary 2.20 (and Lemma 2.2).

From Lemma 12.2, Lemma 2.9 we have \(\mathbb {I}[f(X) : Y] \leq \mathbb {I}[X:Y]\) and \(\mathbb {I}[f(X): g(Y)] \leq \mathbb {I}[f(X):Y]\), giving the claim.

Apply Lemma 12.3 to \(X,Y\) conditioned to the event \(Z=z\), multiply by \({\bf P}[Z=z]\), and sum using Definition 2.25.

Without loss of generality (using Lemma 3.10 and Lemma 3.7) we may take \(X,Y\) to be independent. By \((X_1,Y_1)\), \((X_2,Y_2)\) be copies of \((X,Y)\) that are conditionally independent over \(X_1-Y_1=X_2-Y_2\) (this exists thanks to Lemma 3.22). By Lemma 3.7, we can also find another copy \((X_3,Y_3)\) of \((X,Y)\) that is independent of \(X_1,Y_1,X_2,Y_2\). From Corollary 2.21, one has

From Lemma 3.11, Lemma 3.1, Lemma 3.10 we have

Since \(X_3+Y_3\) is a function of \(X_3,Y_3\), we see from Lemma 2.2 and Corollary 2.24 that

Because \(X_1-Y_1=X_2-Y_2\), we have

and thus by Lemma 2.2

and hence by Corollary 2.18

Since \(X_3,Y_2\) are independent, we see from Lemma 3.11, Lemma 3.10 that

Similarly

We conclude that

Finally, from Lemma 12.1 we have

From Corollary 2.24 followed by Corollary 2.30, we have

and thus by Lemma 3.11, Lemma 3.10, Lemma 2.2, Corollary 2.24

Applying all of these estimates, the claim now follows from linear arithmetic.

This is trivial for \(n=0,1\), while the \(n=2\) case is Lemma 3.21. Now suppose inductively that \(n {\gt} 2\), and the claim was already proven for \(n-1\). By a further application of Lemma 3.21 one has

By induction hypothesis one has

Summing the two inequalities, we obtain the claim.

Applying Lemma 12.6 with all the \(Y_i\) replaced by \(-Y_i\), and using Lemma 3.1 and Lemma 3.11, we obtain after some rearranging

From Corollary 3.5 we have

for all \(i\); subtracting \(\mathbb {H}[X]\) and averaging, we conclude that

and thus

From Lemma 3.13 we have

Since \(0 \leq \frac{n-1}{2n} \leq \frac{1}{2}\), the claim follows.

From Lemma 3.21 one has

The claim then follows from Lemma 3.11 and some elementary algebra.

Write \(W := \sum _{i=1}^m X_i\). From Corollary 3.5 we have

while from Lemma 12.6 one has

From Lemma 3.21 one has

The claim now follows from Lemma 3.1 and some elementary algebra.

From Lemma 3.17 we have

which gives the first inequality. Similarly from Lemma 3.17 we have

which (when combined with Lemma 3.1) gives the second inequality.

From Lemma 3.21 one has

which by Lemma 3.11 gives

and hence by Lemma 12.5

From Lemma 12.10 we then have

and the claim now follows by an induction on \(|a|\).

Clear from Lemma 3.6.

Clear from definition.

From Corollary 3.5 one has

for each \(1 \leq i \leq m\). Averaging over \(i\), we obtain the claim.

Trivial.

By Lemma 3.10, Lemma 12.13 we may take the \(X_i\) to be jointly independent. From Corollary 3.5, we see that for any distinct \(1 \leq j,k \leq m\), we have

and hence by Lemma 3.11

Summing this over all pairs \((j,k)\), \(j \neq k\) and using Lemma 12.14, we obtain the claim.

From Lemma 3.18 we have \(\operatorname{dist}{X_j}{X_j} \leq 2 \operatorname{dist}{X_j}{-X_k}\), and applying this to every summand in Lemma 12.17, we obtain the claim.

By Lemma 3.10, Lemma 12.13 we may take the \(X_i\) to be jointly independent. Let \(X_0\) be a further independent copy of the \(X_i\). From Lemma 12.6, we have

and hence by Lemma 3.1 and Lemma 3.11

On the other hand, by Corollary 3.5 we have

and the claim follows.

Take \((X'_i)_{1 \leq i \leq m}\) to be further independent copies of \((X_i)_{1 \leq i \leq m}\) (which exist by Lemma 3.7), and write \(W' := \sum _{i=1}^m X'_i\). Fix any distinct \(a,b \in I\).

From Lemma 3.21 one has

and also

Combining this with 1 and then applying Corollary 3.5 we have

Averaging this over all choices of \((a,b)\) gives \(\mathbb {H}[W] + 2 D[X_{[m]}]\), and the claim follows from Lemma 3.11.

From Lemma 12.17 and Lemma 3.15 we have \(d[X_j; X_{-k}]=0\) for all \(1 \leq j,k \leq m\). The claim now follows from Corollary 4.6.

This is similar to the proof of Proposition 6.5.

By Definition 12.24 we have

and hence by Definition 12.23 and Lemma 12.15

The claim now follows from Lemma 12.19.

By Definition 12.24 we have

and hence by Definition 12.23

On the other hand, by Lemma 3.18 we have

The claim follows.

This is routine from Definition 2.11 and Definitions 12.12 and 12.28.

Clear from Lemma 12.15 and Definition 12.28, except that some care may need to be taken to deal with the \(y_i\) where \(p_{Y_i}\) vanish.

Immediate from Lemma 12.27, Lemma 12.29, and Definition 3.19.

This follows from Lemma 12.31 and Lemma 12.16.

For notational brevity during this proof, write \(S := \sum _{i=1}^m X_i\).

From Lemma 2.26 and Lemma 2.2, noting that \(\pi (S)\) is determined both by \(S\) and by \(\pi (X_{[m]})\), we have

and by Lemma 2.13 the right-hand side is equal to

Therefore,

From a further application of Lemma 2.13 and Lemma 2.2 we have

for all \(1 \leq i \leq m\). Averaging 7 in \(i\) and subtracting this from 6, we obtain the claim from Definition 12.12.

For each \(y_i\) in the support of \(p_{Y_i}\), apply Lemma 12.33 with \(X_i\) replaced by the conditioned random variable \((X_i|Y_i=y_i)\), and the claim 8 follows by averaging 5 in the \(y_i\) using the weights \(p_{Y_i}\).

From Lemma 12.34 (taking \(Y_{[m]} = \pi _{d-1}(X_{[m]})\) and \(\pi = \pi _d\) there, and noting that \(\pi _d(X_{[m]})\) determines \(Y_{[m]}\)) we have

for \(d=1,\dots ,m\). The claim follows by telescoping series, noting that \(D[X_{[m]} | \pi _0(X_{[m]})] = D[X_{[m]}]\) and that \(\pi _m(X_{[m]})=X_{[m]}\) (and also \(\pi _m( \sum _i X_i ) = \sum _i X_i\)).

In Lemma 12.35 we take \(G_d := G^d\) with the maps \(\pi _d \colon G^m \to G^d\) for \(d=1,\dots ,m\) defined by

with \(\pi _0=0\). Since \(\pi _{d-1}(x)\) can be obtained from \(\pi _{d}(x)\) by applying a homomorphism, we obtain a sequence of the form 9.

Now we apply Lemma 12.35 with \(I = \{ 1,\dots , m\} \) and \(X_i := (X_{i,j})_{j = 1}^m\). Using joint independence and Corollary 2.24, we find that

On the other hand, for \(1 \leq j \leq m-1\), we see that once \(\pi _{j}(X_i)\) is fixed, \(\pi _{j+1}(X_i)\) is determined by \(X_{i, j}\) and vice versa, so

Since the \(X_{i,j}\) are jointly independent, we may further simplify:

Putting all this into the conclusion of Lemma 12.35, we obtain

and the claim follows by rearranging.

For each \(j \in \{ 1,\dots ,m\} \) we call the tuple \((X_{i,j})_{i = 1}^m\) a column and for each \(i \in \{ 1,\dots , m\} \) we call the tuple \((X_{i,j})_{j = 1}^m\) a row. Hence, by hypothesis, each column is a permutation of \(X_{[m]} = (X_i)_{i=1}^m\).

From Corollary 12.36 we have

where

and

We first consider the \(A_j\), for fixed \(j \in \{ 1,\dots , m-1\} \). By Lemma 12.16 and and our hypothesis on columns, we have

Let \(\sigma = \sigma _j \colon I \to I\) be a permutation such that \(X_{i,j} = X_{\sigma (i)}\), and write \(X'_i := X_{i,j}\) and \(Y_i := X_{i,j} + \cdots + X_{i,m}\). Corollary 12.32, we have

We similarly consider \(B\). By Lemma 12.16 applied to the \(m\)-th column,

For \(1 \leq i \leq m\), denote the sum of row \(i\) by

if we apply Corollary 12.32 again, now with \(X_{\sigma (i)} = X_{i,m}\), \(X'_i := V_i\), and with the variable \(Y_i\) being trivial, we obtain

It remains to bound the distances appearing in 16 and 17 further using Ruzsa calculus. For \(1 \leq j \leq m-1\) and \(1 \leq i \leq m\), by Lemma 3.25 we have

For each \(i\), summing over \(j = 1,\dots , m-1\) gives

On the other hand, by Lemma 12.8 (since \(X_{i,m}\) appears in the sum \(V_i\)) we have

Combining 15, 16 and 17 with 18 and 19 (the latter two summed over \(i\)), we get

By Lemma 12.9 (with \(f\) taking each \(j\) to the index \(j'\) such that \(X_{i,j}\) is a copy of \(X_{j'}\)) we obtain the bound

Finally, summing over \(i\) and using \(D[X_{[m]}] = k\) gives

where in the second step we used the permutation hypothesis. Combining this with 20 gives the

The claim 14 is now immediate from Lemma 12.18.

Clear from definition.

We analyze these variables by Proposition 12.37 in several different ways. In the first application, take \(X_{i,j}=Y_{i,j}\). Note that each column \((X_{i,j})_{i=1}^m\) is indeed a permutation of \(X_1,\dots ,X_m\); in fact, the trivial permutation. Note also that for each \(i \in \mathbb {Z}/m\mathbb {Z}\), the row sum is

and for each \(j \in \mathbb {Z}/m\mathbb {Z}\), the column sum is

Finally note that \(\sum _{i,j=1}^m X_{i,j} = W\). From Proposition 12.37 we then have

with \(t\) as in 23. Since \(Z_1\) is a function of \((P_i)_{i \in \mathbb {Z}/m\mathbb {Z}}\) by 21, and similarly \(Z_2\) is a function of \((Q_j)_{j \in \mathbb {Z}/m\mathbb {Z}}\), it follows immediately from Lemma 12.4 that

In the second application of Proposition 12.37, we instead consider \(X'_{i,j} = Y_{i-j,j}\). Again, for each fixed \(j\), the tuple \((X'_{i,j})_{i=1}^m\) is a permutation of \(X_1,\dots ,X_m\). This time the row sums for \(i \in \{ 1,\dots , m\} \) are

Similarly, the column sums for \(j \in \{ 1,\dots , m\} \) are

As before, \(\sum _{i,j=1}^m X'_{i,j} = W\). Hence, using 21 and Lemma 12.4 again, Proposition 12.37 tells us

In the third application ¹ of Proposition 12.37, take \(X''_{i,j} = Y_{i,j-i}\). The column and row sums are respectively

and

Hence, Proposition 12.37 and Lemma 12.4 give

which completes the proof.

Without loss of generality, we may take \(X_1,\dots ,X_m\) to be independent. Write \(S = \sum _{i=1}^m X_i\). Note that for each \(j \in \mathbb {Z}/m\mathbb {Z}\), the sum \(Q_j\) from 21 above has the same distribution as \(S\). By Lemma 12.6 we have

By Lemma 12.20, we have

and hence

From Definition 12.12 we have

and the claim follows.

We observe

Applying Lemma 12.6 one has

Using Lemma 12.11 and 24 we get

Applying 25 gives the claim.

From Lemma 2.16 we have \(\mathbb {I}[W : Z_2] = \mathbb {H}[W] - \mathbb {H}[W | Z_2]\), and since \(Z_2 = \sum _{j=1}^{m-1} j Q_j\) and \(W = \sum _{j=1}^m Q_j\),

Hence, by Lemma 12.41,

as claimed.

For each \(i \in \{ 1,\dots , m\} \), using Lemma 12.8 (noting the sum \(Z_2\) contains \(X_i\) as a summand) we have

and using Lemma 3.24 we have

Combining with 26 and Lemma 12.43 gives

Summing over \(i\) and applying Lemma 12.42 gives

Finally, applying Lemma 12.18 (and dropping some lower order terms) gives the claim.

We apply Lemma 3.23 with \(X=T_1\) and \(Y=T_2\). Since \(T_1+T_2=-T_3\), we find that

where the last line follows from Lemma 2.2 by observing

since any two of \(T_1,T_2,T_3\) determine the third.

By 28 and the triangle inequality,

and by Lemma 3.25, for each \(Y_i\),

Hence,

and the result follows by setting \(U=(T_2 \, |\, T_3 \mathop{=} z)\) for some \(z\) such that the quantity in parentheses on the left-hand side is at most the weighted average value.

For each value \(W=w\), apply Lemma 12.45 (and Lemma 12.39) to

with \(Y_i=X_i\) and \(\alpha =\eta /m\). Write

for this choice, and note that

by Proposition 12.40. Write \(U_w\) for the random variable guaranteed to exist by Lemma 12.45, so that 27 gives

Let \((U_w)_I\) denote the tuple consisting of the same variable \(U_w\) repeated \(m\) times. By Lemma 12.19

On the other hand, from Lemma 12.27 one has

Combining 30, 31 and 32 and averaging over \(w\) (with weight \(p_W(w)\)), and recalling the value \(\alpha =\eta /m\), gives

since the terms \(d[X_i; U_w]\) cancel by our choice of \(\alpha \). Substituting in Lemma 12.44 and 29, and using the fact that \(2 + \frac{\eta }{2} {\lt} 3\), we have

From Definition 12.22 we have we have

and hence \(k \leq 0\). The claim now follows from Lemma 12.15.

Set \(X^0 := X\). By Proposition 12.25, there exists a \(\tau \)-minimizer \(X_{[m]} = (X_i)_{1 \leq i \leq m}\). By Proposition 12.46, we have \(D[X_{[m]}]=0\). By Proposition 12.26 and the pigeonhole principle, there exists \(1 \leq i \leq m\) such that \(d[X_i; X] \leq \frac{2}{\eta } d[X;X]\). By Proposition 12.21, we have \(d[X_i;U_H]=0\) for some subgroup \(H \leq G\), hence by Lemma 3.18 we have \(d[U_H; X] \leq \frac{2}{\eta } d[X;X]\). The claim then follows from Definition 12.22.

Repeat the proof of Lemma 7.2, but with Theorem 12.47 in place of Theorem 6.24.

Repeat the proof of Theorem 7.3, but with Lemma 12.48 in place of Lemma 7.2.