Dependencies

If \(X,Y\) are random variables, then \(\mathbb {H}[X,Y] = \mathbb {H}[X] + \mathbb {H}[Y]\) if and only if \(X,Y\) are independent.

With three random variables \(X,Y,Z\), one has

With notation as above, we have

Let \(G=\mathbb {F}_2^n\) and \(\alpha \in (0,1)\) and let \(X,Y\) be \(G\)-valued random variables such that

There is a non-trivial subgroup \(H\leq G\) such that

and

where \(\psi :G\to G/H\) is the natural projection homomorphism.

Let \(G,G'\) be finite abelian \(2\)-groups. Let \(f: G \to G'\) be a function, and suppose that there are at least \(|G|^2 / K\) pairs \((x,y) \in G^2\) such that

Then there exists a homomorphism \(\phi : G \to G'\) and a constant \(c \in G'\) such that \(f(x) = \phi (x)+c\) for at least \(|G| / (2 ^{144} * K ^{122})\) values of \(x \in G\).

One has

If \(X\) is an \(S\)-valued random variable, then there exists \(s \in S\) such that \(\mathbb {P}[X=s] \geq \exp (-\mathbb {H}[X])\).

Let \(G\) be an abelian group, and let \(A\) be a finite non-empty set with \(E(A) \geq |A|^3 / K\) for some \(K \geq 1\). Then there is a subset \(A'\) of \(A\) with \(|A'| \geq |A| / (C_1 K^{C_2})\) and \(|A'-A'| \leq C_3 K^{C_4} |A|\), where (provisionally)

If \(X: \Omega \to S\) and \(Y: \Omega \to T\) are random variables, then

If \(X,Y,Z\) are random variables, with \(X,Z\) defined on the same sample space, we define

Let \((X_i)_{1 \leq i \leq m}\) and \((Y_j)_{1 \leq j \leq l}\) be tuples of jointly independent random variables (so the \(X\)’s and \(Y\)’s are also independent of each other), and let \(f: \{ 1,\dots ,l\} \to \{ 1,\dots ,m\} \) be a function, then

\(h\) is strictly concave on \([0,\infty )\).

The expression \(d[X | Z;Y | W]\) is unchanged if \((X,Z)\) or \((Y,W)\) is replaced by a copy. Furthermore, if \((X,Z)\) and \((Y,W)\) are independent, then

and similarly

If \((X, Z)\) and \((Y, W)\) are random variables (where \(X\) and \(Y\) are \(G\)-valued) we define

similarly

Suppose that \((X, Z)\) and \((Y, W)\) are random variables, where \(X, Y\) take values in an abelian group. Then

In particular,

For any \(G\)-valued random variables \(X'_1,X'_2\) and random variables \(Z,W\), one has

For \(X,Y\) random variables, there exist random variables \(X_1,X_2,Y'\) on a common probability space with \((X_1, Y'), (X_2, Y')\) both having the distribution of \((X,Y)\), and \(X_1, X_2\) conditionally independent over \(Y'\) in the sense of Definition 2.28.

If the \((X_i,Y_i)\) are independent,

If \(X_{[m]} = (X_i)_{1 \leq i \leq m}\) and \(Y_{[m]} = (Y_i)_{1 \leq i \leq m}\) are tuples of random variables, with the \(X_i\) being \(G\)-valued (but the \(Y_i\) need not be), then we define

where each \(y_i\) ranges over the support of \(p_{Y_i}\) for \(1 \leq i \leq m\).

If \((X_i)_{1 \leq i \leq m}\) is a \(\tau \)-minimizer, and \(k := D[(X_i)_{1 \leq i \leq m}]\), then for any other tuples \((X'_i)_{1 \leq i \leq m}\) and \((Y_i)_{1 \leq i \leq m}\) with the \(X'_i\) \(G\)-valued, one has

With the notation of the previous lemma, we have

for any permutation \(\sigma : \{ 1,\dots ,m\} \rightarrow \{ 1,\dots ,m\} \).

If \(X_{[m]} = (X_i)_{1 \leq i \leq m}\) and \(Y_{[m]} = (Y_i)_{1 \leq i \leq m}\) are tuples of random variables, then \(D[ X_{[m]} | Y_{[m]} ] \geq 0\).

With notation as above, we have \(\mathbb {H}[X|Y] \leq \mathbb {H}[X]\).

If \(X, Y\) are conditionally independent over \(Z\), then

If \(X: \Omega \to S\) is an \(S\)-valued random variable and \(E\) is an event in \(\Omega \), then the conditioned event \((X|E)\) is defined to be the same random variable as \(X\), but now the ambient probability measure has been conditioned to \(E\).

If \(X: \Omega \to S\), \(Y: \Omega \to T\), \(Z: \Omega \to U\) are random variables, then

If \(X: \Omega \to S\) and \(Y: \Omega \to T\) are random variables, the conditional entropy \(\mathbb {H}[X|Y]\) is defined as

\(D_{KL}((X|W)\Vert Y) \geq 0\).

Two random variables \(X: \Omega \to S\) and \(Y: \Omega \to T\) are conditionally independent relative to another random variable \(Z: \Omega \to U\) if \(P[X = s \wedge Y = t| Z=u] = P[X=s|Z=u] P[Y=t|Z=u]\) for all \(s \in S, t \in T, u \in U\). (We won’t need conditional independence for more variables than this.)

We have

and

If \(X,Y,Z\) are random variables, with \(Z\) \(U\)-valued, then

If \(X,Y,Z\) are random variables, then \(\mathbb {I}[X:Y|Z] \ge 0\).

If \(X,Y,Z\) are random variables, then \(\mathbb {I}[X:Y|Z] = 0\) iff \(X,Y\) are conditionally independent over \(Z\).

One has

One has

One has

One has

If equality holds in the above lemma, then \(p_s = \sum _{s \in S} w_s h(p_s)\) whenever \(w_s \neq 0\).

If equality holds in Lemma 1.4, then \(a_s=r\cdot b_s\) for every \(s\in S\), for some constant \(r\in \mathbb {R}\).

If \(X'\) is a copy of \(X\) then \(\mathbb {H}[X'] = \mathbb {H}[X]\).

Let \(Y_1,Y_2,Y_3\) and \(Y_4\) be independent \(G\)-valued random variables. Then

Let \(G\) be an abelian group and let \(m \geq 2\). Suppose that \(X_{i,j}\), \(1 \leq i, j \leq m\), are independent \(G\)-valued random variables. Then

where all the multidistances here involve the indexing set \(\{ 1,\dots , m\} \).

If \(G\) is a group, \(A,B\) are finite subsets of \(G\), then

Let \(X,Y,Z\). For any functions \(f, g\) on the ranges of \(X, Y\) respectively, we have \(\mathbb {I}[f(X) : g(Y )|Z] \leq \mathbb {I}[X :Y |Z]\).

Let \(X\) be a random variable. Then for any function \(f\) on the range of \(X\), one has \(\mathbb {H}[f(X)] \leq \mathbb {H}[X]\).

Let \(X,Y\) be random variables. For any functions \(f, g\) on the ranges of \(X, Y\) respectively, we have \(\mathbb {I}[f(X) : g(Y )] \leq \mathbb {I}[X : Y]\).

Let \(X,Y\) be random variables. For any function \(f, g\) on the range of \(X\), we have \(\mathbb {I}[f(X) : Y] \leq \mathbb {I}[X:Y]\).

Let \(X_1, X_2\) be tau-minimizers. Then \(d[X_1;X_2] = 0\).

Suppose \(0 {\lt} \eta {\lt} 1/8\). Let \(X_1, X_2\) be tau-minimizers. Then \(d[X_1;X_2] = 0\).

For \(\eta = 1/8\), there exist tau-minimizers \(X_1, X_2\) satisfying \(d[X_1;X_2] = 0\).

If \(A\subseteq \mathbb {Z}^{d}\) then by \(\dim (A)\) we mean the dimension of the span of \(A-A\) over the reals – equivalently, the smallest \(d'\) such that \(A\) lies in a coset of a subgroup isomorphic to \(\mathbb {Z}^{d'}\).

We have

If \(G\) is an additive group and \(X\) is a \(G\)-valued random variable and \(H\leq G\) is a finite subgroup then, with \(\pi :G\to G/H\) the natural homomorphism we have (where \(U_H\) is uniform on \(H\))

We have

If \(X\) is a \(G\)-valued random variable and \(0\) is the random variable taking the value \(0\) everywhere then

For any \(G\)-valued random variables \(X'_1,X'_2\), one has

If \(G\) is a group, and \(A\) is a finite subset of \(G\), the additive energy \(E(A)\) of \(A\) is the number of quadruples \((a_1,a_2,a_3,a_4) \in A^4\) such that \(a_1+a_2 = a_3+a_4\).

We have \(\mathbb {H}[W] \leq (2m-1)k + \frac1m \sum _{i=1}^m \mathbb {H}[X_i]\).

We have \(\mathbb {H}[Z_2] \leq (8m^2-16m+1) k + \frac{1}{m} \sum _{i=1}^m \mathbb {H}[X_i]\).

Let \(A,B\) be \(G\)-valued random variables on \(\Omega \), and set \(Z := A+B\). Then

If \(X: \Omega \to S\), \(Y: \Omega \to T\), and \(Z: \Omega \to U\) are random variables, then \(\mathbb {H}[X, Y] = \mathbb {H}[Y, X]\) and \(\mathbb {H}[X, (Y,Z)] = \mathbb {H}[(X,Y), Z]\).

If \(X\) is an \(S\)-valued random variable, the entropy \(\mathbb {H}[X]\) of \(X\) is defined

with the convention that \(0 \log \frac{1}{0} = 0\).

Let \(G = \mathbb {F}_2^n\), and suppose that \(X^0_1, X^0_2\) are \(G\)-valued random variables. Then there is some subgroup \(H \leq G\) such that

where \(U_H\) is uniformly distributed on \(H\). Furthermore, both \(d[X^0_1;U_H]\) and \(d[X^0_2;U_H]\) are at most \(6 d[X^0_1;X^0_2]\).

Let \(G = \mathbb {F}_2^n\), and suppose that \(X^0_1, X^0_2\) are \(G\)-valued random variables. Then there is some subgroup \(H \leq G\) such that

where \(U_H\) is uniformly distributed on \(H\). Furthermore, both \(d[X^0_1;U_H]\) and \(d[X^0_2;U_H]\) are at most \(6 d[X^0_1;X^0_2]\).

\(\eta := 1/9\).

We set \(\eta := \frac{1}{32m^3}\).

\(\eta \) is a real parameter with \(\eta {\gt} 0\).

Let \(\pi : H \to H'\) be a homomorphism additive groups, and let \(Z_1,Z_2\) be \(H\)-valued random variables. Then we have

Moreover, if \(Z_1,Z_2\) are taken to be independent, then the difference between the two sides is

If \(\pi :G\to H\) is a homomorphism of additive groups and \(X,Y\) are \(G\)-valued random variables then

We have

We have

We have \(I_1 \leq 2 \eta k\).

We have

We have

Let \(X, Y, Z\) be random variables taking values in some abelian group of characteristic \(2\), and with \(Y, Z\) independent. Then we have

and

With the same notation, we have

Let \(X_1, X_2, X_3, X_4\) be independent \(G\)-valued random variables, and let \(Y\) be another \(G\)-valued random variable. Set \(S := X_1+X_2+X_3+X_4\). Then

\(D_{KL}(X\Vert Y) \geq 0\).

If \(D_{KL}(X\Vert Y) = 0\), then \(Y\) is a copy of \(X\).

Let \(H\) be a subgroup of \(G \times G'\). Then there exists a subgroup \(H_0\) of \(G\), a subgroup \(H_1\) of \(G'\), and a homomorphism \(\phi : G \to G'\) such that

In particular, \(|H| = |H_0| |H_1|\).

Let \(H_0\) be a subgroup of \(G\). Then every homomorphism \(\phi : H_0 \to G'\) can be extended to a homomorphism \(\tilde\phi : G \to G'\).

Let \(f: G \to G'\) be a function, and let \(S\) denote the set

Then there exists a homomorphism \(\phi : G \to G'\) such that

\(d[X_1;X_1]+d[X_2;X_2]= 2d[X_1;X_2]+(I_2-I_1)\).

Two random variables \(X: \Omega \to S\) and \(Y: \Omega \to T\) are independent if the law of \((X,Y)\) is the product of the law of \(X\) and the law of \(Y\). Similarly for more than two variables.

Let \(X_i : \Omega _i \to S_i\) be random variables for \(i=1,\dots ,k\). Then if one gives \(\prod _{i=1}^k S_i\) the product measure of the laws of \(X_i\), the coordinate functions \((x_j)_{j=1}^k \mapsto x_i\) are jointly independent random variables which are copies of the \(X_1,\dots ,X_k\).

If \(X: \Omega \to S\), \(Y: \Omega \to T\) are random variables, then

If \(S\) is a finite set, and \(\sum _{s \in S} w_s = 1\) for some non-negative \(w_s\), and \(p_s \in [0,1]\) for all \(s \in S\), then

If \(X\) is an \(S\)-valued random variable, then \(\mathbb {H}[X] \leq \log |S|\).

We have \(k = 0\).

Suppose that \(X_{i,j}\), \(1 \leq i,j \leq m\), are jointly independent \(G\)-valued random variables, such that for each \(j = 1,\dots ,m\), the random variables \((X_{i,j})_{i = 1}^m\) coincide in distribution with some permutation of \(X_{[m]}\). Write

Then

We have \(U+V+W=0\).

If \(X, Y\) are independent \(G\)-valued random variables, and \(Z\) is another random variable defined on the same sample space as \(X\), then

If \(X,Y\) are two \(G\)-valued random variables, the Kullback–Leibler divergence is defined as

If \(S\) is a finite set, \(\sum _{s \in S} w_s = 1\) for some non-negative \(w_s\), and \({\bf P}(X=x) = \sum _{s\in S} w_s {\bf P}(X_s=x)\), \({\bf P}(Y=x) = \sum _{s\in S} w_s {\bf P}(Y_s=x)\) for all \(x\), then

If \(X'\) is a copy of \(X\), and \(Y'\) is a copy of \(Y\), then \(D_{KL}(X'\Vert Y') = D_{KL}(X\Vert Y)\).

If \(f:G \to H\) is an injection, then \(D_{KL}(f(X)\Vert f(Y)) = D_{KL}(X\Vert Y)\).

If \(X, Y, Z\) are independent \(G\)-valued random variables, then

If \(n \geq 0\) and \(X, Y_1, \dots , Y_n\) are jointly independent \(G\)-valued random variables, then

If \(n \geq 1\) and \(X, Y_1, \dots , Y_n\) are jointly independent \(G\)-valued random variables, then

If \(n \geq 1\) and \(X, Y_1, \dots , Y_n\) are jointly independent \(G\)-valued random variables, then

Suppose that \(X, Y, Z\) are independent \(G\)-valued random variables. Then

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

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

Let \(G\) be an abelian group, let \((T_1,T_2,T_3)\) be a \(G^3\)-valued random variable such that \(T_1+T_2+T_3=0\) holds identically, and write

Let \(Y_1,\dots ,Y_n\) be some further \(G\)-valued random variables and let \(\alpha {\gt}0\) be a constant. Then there exists a random variable \(U\) such that

If \(S\) is a finite set, and \(a_s,b_s\) are non-negative for \(s\in S\), then

with the convention \(0\log \frac{0}{b}=0\) for any \(b\ge 0\) and \(0\log \frac{a}{0}=\infty \) for any \(a{\gt}0\).

Suppose that \(G\) is a finite abelian group of torsion \(m\). Suppose that \(X\) is a \(G\)-valued random variable. Then there exists a subgroup \(H \leq G\) such that

By a slight abuse of notation, we identify \(\mathbb {Z}/m\mathbb {Z}\) and \(\{ 1,\dots ,m\} \) in the obvious way, and let \(Y_{i,j}\) be an independent copy of \(X_i\) for \(i,j \in \mathbb {Z}/m\mathbb {Z}\). Then also define:

and

The addition \((-i-j)\) takes place over \(\mathbb {Z}/m\mathbb {Z}\). Note that, because we are assuming \(G\) is \(m\)-torsion, it is well-defined to multiply elements of \(G\) by elements of \(\mathbb {Z}/m\mathbb {Z}\). We will also define for \(i,j,r \in \mathbb {Z}/m\mathbb {Z}\) the variables

If \(D[X_{[m]}]=0\), then for each \(1 \leq i \leq m\) there is a finite subgroup \(H_i \leq G\) such that \(d[X_i; U_{H_i}] = 0\).

Let \(\pi \colon G \to H\) be a homomorphism of abelian groups and let \(X_{[m]}\) be a tuple of jointly independent \(G\)-valued random variables. Then \(D[X_{[m]}]\) is equal to

where \(\pi (X_{[m]}) := (\pi (X_i))_{1 \leq i \leq m}\).

Let \(\pi \colon G \to H\) be a homomorphism of abelian groups. Let \(I\) be a finite index set and let \(X_{[m]}\) be a tuple of \(G\)-valued random variables. Let \(Y_{[m]}\) be another tuple of random variables (not necessarily \(G\)-valued). Suppose that the pairs \((X_i, Y_i)\) are jointly independent of one another (but \(X_i\) need not be independent of \(Y_i\)). Then

Let \(m\) be a positive integer. Suppose one has a sequence

of homomorphisms between abelian groups \(G_0,\dots ,G_m\), and for each \(d=0,\dots ,m\), let \(\pi _d : G_m \to G_d\) be the homomorphism from \(G_m\) to \(G_d\) arising from this sequence by composition (so for instance \(\pi _m\) is the identity homomorphism and \(\pi _0\) is the zero homomorphism). Let \(X_{[m]} = (X_i)_{1 \leq i \leq m}\) be a jointly independent tuple of \(G_m\)-valued random variables. Then

In particular, by Lemma 2.27,

If \(X_{[m]} = (X_i)_{1 \leq i \leq m}\) and \(Y_{[m]} = (Y_i)_{1 \leq i \leq m}\) are such that \(X_i\) and \(Y_i\) have the same distribution for each \(i\), then \(D[X_{[m]}] = D[Y_{[m]}]\).

Let \(m\) be a positive integer, and let \(X_{[m]} = (X_i)_{1 \leq i \leq m}\) be an \(m\)-tuple of \(G\)-valued random variables \(X_i\). Then we define

where the \(\tilde X_i\) are independent copies of the \(X_i\).

If \(X_{[m]} = (X_i)_{1 \leq i \leq m}\) are jointly independent, then \(D[X_{[m]}] = \mathbb {H}[\sum _{i=1}^m X_i] - \frac{1}{m} \sum _{i=1}^m \mathbb {H}[X_i]\).

If \((X_i)_{1 \leq i \leq m}\) is a \(\tau \)-minimizer, and \(k := D[(X_i)_{1 \leq i \leq m}]\), then for any other tuple \((X'_i)_{1 \leq i \leq m}\), one has

For any such tuple, we have \(D[X_{[m]}] \geq 0\).

If \(\phi : \{ 1,\dots ,m\} \to \{ 1,\dots ,m\} \) is a bijection, then \(D[X_{[m]}] = D[(X_{\phi (j)})_{1 \leq j \leq m}]\).

Let \(m \ge 2\), and let \(X_{[m]}\) be a tuple of \(G\)-valued random variables. Then

Let \(m \ge 2\), and let \(X_{[m]}\) be a tuple of \(G\)-valued random variables. Then

Let \(m \ge 2\), and let \(X_{[m]}\) be a tuple of \(G\)-valued random variables. If the \(X_i\) all have the same distribution, then \(D[X_{[m]}] \leq m d[X_i;X_i]\) for any \(1 \leq i \leq m\).

Let \(m \ge 2\), and let \(X_{[m]}\) be a tuple of independent \(G\)-valued random variables. Let \(W := \sum _{i=1}^m X_i\). Then

We have \(\mathbb {I}[X:Y] \geq 0\).

We have \(\mathbb {I}[W : Z_2] \leq 2 (m-1) k\).

If \(X\) is \(G\)-valued, then \(\mathbb {H}[-X]=\mathbb {H}[X]\).

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

If \(A \subset {\bf F}_2^n\) is finite non-empty with \(|A+A| \leq K|A|\), then there exists a subgroup \(H\) of \({\bf F}_2^n\) with \(|H| \leq |A|\) such that \(A\) can be covered by at most \(2K^9\) translates of \(H\).

If \(|A+A| \leq K|A|\), then there exists a subgroup \(H\) and \(t\in G\) such that \(|A \cap (H+t)| \geq K^{-4} \sqrt{|A||H|}\), and \(|H|/|A|\in [K^{-8},K^8]\).

If \(|A+A| \leq K|A|\), then there exist a subgroup \(H\) and a subset \(c\) of \(G\) with \(A \subseteq c + H\), such that \(|c| \leq K^{5} |A|^{1/2}/|H|^{1/2}\) and \(|H|/|A|\in [K^{-8},K^8]\).

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

If \(A \subset {\bf F}_2^n\) is non-empty and \(|A+A| \leq K|A|\), then \(A\) can be covered by most \(2K^{11}\) translates of a subspace \(H\) of \({\bf F}_2^n\) with \(|H| \leq |A|\).

If \(G=\mathbb {F}_2^d\) and \(\alpha \in (0,1)\) and \(X,Y\) are \(G\)-valued random variables then there is a subgroup \(H\leq \mathbb {F}_2^d\) such that

and if \(\psi :G \to G/H\) is the natural projection then

If \(G=\mathbb {F}_2^d\) and \(\alpha \in (0,1)\) and \(X,Y\) are \(G\)-valued random variables then there is a subgroup \(H\leq \mathbb {F}_2^d\) such that

and if \(\psi :G \to G/H\) is the natural projection then

For any random variables \(Y_1,Y_2\), there exist a subgroup \(H\) such that

Suppose that \(G\) is a finite abelian group of torsion \(m\). If \(A \subset G\) is non-empty and \(|A+A| \leq K|A|\), then \(A\) can be covered by most \(mK^{96m^3+2}\) translates of a subspace \(H\) of \(G\) with \(|H| \leq |A|\).

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

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^6 |A|^{1/2}/|H|^{1/2}\) translates of a subspace \(H\) of \({\bf F}_2^n\) with

Suppose that \(G\) is a finite abelian group of torsion \(m\). If \(A \subset G\) is non-empty and \(|A+A| \leq K|A|\), then \(A\) can be covered by at most \(K ^{(64m^3+2)/2}|A|^{1/2}/|H|^{1/2}\) translates of a subspace \(H\) of \(G\) with

\(I_1\le 2\eta d[X_1;X_2]\)

Given \(G\)-valued random variables \(X,Y\), define

and define a \(\phi \)-minimizer to be a pair of random variables \(X,Y\) which minimizes \(\phi [X;Y]\).

There exists a \(\phi \)-minimizer.

If \(X_1,X_2\) is a \(\phi \)-minimizer, then \(d[X_1;X_2] = 0\).

\(I_2\le 2\eta d[X_1;X_2] + \frac{\eta }{1-\eta }(2\eta d[X_1;X_2]-I_1)\).

We have

where

• If \(X: \Omega \to S\) and \(Y: \Omega \to T\) are random variables, and \(Y = f(X)\) for some injection \(f: S \to T\), then \(\mathbb {H}[X] = \mathbb {H}[Y]\).

• If \(X: \Omega \to S\) and \(Y: \Omega \to T\) are random variables, and \(Y = f(X)\) and \(X = g(Y)\) for some functions \(f: S \to T\), \(g: T \to S\), then \(\mathbb {H}[X] = \mathbb {H}[Y]\).

If \(X: \Omega \to S\), \(Y: \Omega \to T\), and \(Z: \Omega \to U\) are random variables, and \(Y = f(X,Z)\) almost surely for some map \(f: S \times U \to T\) that is injective for each fixed \(U\), then \(\mathbb {H}[X|Z] = \mathbb {H}[Y|Z]\).

Similarly, if \(g: T \to U\) is injective, then \(\mathbb {H}[X|g(Y)] = \mathbb {H}[X|Y]\).

If \(G\)-valued random variables \(T_1,T_2,T_3\) satisfy \(T_1+T_2+T_3=0\), then

If \(G\)-valued random variables \(T_1,T_2,T_3\) satisfy \(T_1+T_2+T_3=0\), then

If \(X,Z\) are defined on the same space, one has

and

We define \(\rho (X|Y) := \sum _y {\bf P}(Y=y) \rho (X|Y=y)\).

For any \(s\in G\), \(\rho (X+s|Y)=\rho (X|Y)\).

If \(f\) is injective, then \(\rho (X|f(Y))=\rho (X|Y)\).

If \(X,Y\) are independent, then

\(\rho (X)\) depends continuously on the distribution of \(X\).

We define \(\rho (X) := (\rho ^+(X) + \rho ^-(X))/2\).

For independent random variables \(Y_1,Y_2,Y_3,Y_4\) over \(G\), define \(S:=Y_1+Y_2+Y_3+Y_4\), \(T_1:=Y_1+Y_2\), \(T_2:=Y_1+Y_3\). Then

For independent random variables \(Y_1,Y_2,Y_3,Y_4\) over \(G\), define \(T_1:=Y_1+Y_2,T_2:=Y_1+Y_3,T_3:=Y_2+Y_3\) and \(S:=Y_1+Y_2+Y_3+Y_4\). Then

For any \(s \in G\), \(\rho (X+s) = \rho (X)\).

If \(H\) is a finite subgroup of \(G\), and \(\rho (U_H) \leq r\), then there exists \(t\) such that \(|A \cap (H+t)| \geq e^{-r} \sqrt{|A||H|}\), and \(|H|/|A|\in [e^{-2r},e^{2r}]\).

If \(X,Y\) are independent, one has

and

If \(X,Y\) are independent, then

We have \(\rho (U_A) = 0\).

For any \(G\)-valued random variable \(X\), we define \(\rho ^-(X)\) to be the infimum of \(D_{KL}(X \Vert U_A + T)\), where \(U_A\) is uniform on \(A\) and \(T\) ranges over \(G\)-valued random variables independent of \(U_A\).

If \(H\) is a finite subgroup of \(G\), then \(\rho ^-(U_H) = \log |A| - \log \max _t |A \cap (H+t)|\).

We have \(\rho ^-(X) \geq 0\).

For any \(G\)-valued random variable \(X\), we define \(\rho ^+(X) := \rho ^-(X) + \mathbb {H}(X) - \mathbb {H}(U_A)\).

If \(H\) is a finite subgroup of \(G\), then \(\rho ^+(U_H) = \log |H| - \log \max _t |A \cap (H+t)|\).

If \(X',Y'\) are copies of \(X,Y\) respectively then \(d[X';Y']=d[X ;Y]\).

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

Let \(X,Y\) be \(G\)-valued random variables (not necessarily on the same sample space). The Ruzsa distance \(d[X ;Y]\) between \(X\) and \(Y\) is defined to be

where \(X',Y'\) are (the canonical) independent copies of \(X,Y\) from Lemma 3.7.

If \(X,Y\) are independent \(G\)-random variables then

If \(X,Y\) are \(G\)-valued random variables, then

If \(X,Y\) are independent \(G\)-valued random variables, then

If \(X,Y\) are \(G\)-valued random variables, then

If \(X,Y\) are \(G\)-valued random variables, then

If \(X,Y,Z\) are \(G\)-valued random variables, then

If \(X,Y,Z\) are \(G\)-valued random variables on \(\Omega \) with \((X,Y)\) independent of \(Z\), then

We have

We have

Let \(X, Y, Z, Z'\) be random variables taking values in some abelian group, and with \(Y, Z, Z'\) independent. Then we have

If \(X,Y\) are \(G\)-valued, then \(\mathbb {H}[X \pm Y | Y]=\mathbb {H}[X|Y]\) and \(\mathbb {H}[X \pm Y, Y] = \mathbb {H}[X, Y]\).

If \(X,Y\) are \(G\)-valued, then

Let \(\phi :G\to H\) be a homomorphism and \(A,B\subseteq G\) be finite subsets. If \(x,y\in H\) then let \(A_x=A\cap \phi ^{-1}(x)\) and \(B_y=B\cap \phi ^{-1}(y)\). There exist \(x,y\in H\) such that \(A_x,B_y\) are both non-empty and

With notation as above, we have \(\mathbb {H}[X,Y] \leq \mathbb {H}[X] + \mathbb {H}[Y]\).

With three random variables \(X,Y,Z\), one has \(\mathbb {H}[X|Y,Z] \leq \mathbb {H}[X|Z]\).

Let \(X,Y,X'\) be independent \(G\)-valued random variables, with \(X'\) a copy of \(X\), and let \(a\) be an integer. Then

and

Let \(X,Y\) be independent \(G\)-valued random variables, and let \(a\) be an integer. Then

If \(X,Y\) are independent \(G\)-valued random variables, then

If \(X,Y\) are \(G\)-valued random variables on \(\Omega \), we have

If \(X,Y\) are \(G\)-valued random variables on \(\Omega \) and \(Z\) is another random variable on \(\Omega \) then

If \(X\) is a \(G\)-valued random variable, then \(\mathrm{Sym}[X]\) is a subgroup of \(G\).

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

If \(X\) is a \(G\)-valued random variable with \(d[X ;X]=0\), and \(x_0\) is a point with \(P[X=x_0] {\gt} 0\), then \(X-x_0\) is uniformly distributed on \(\mathrm{Sym}[X]\).

We have

If \(X'_1, X'_2\) are copies of \(X_1,X_2\), then \(\tau [X'_1;X'_2] = \tau [X_1;X_2]\).

If \(X_1,X_2\) are two \(G\)-valued random variables, then

If \((X_i)_{1 \leq i \leq m}\) is a tuple, we define its \(\tau \)-functional

A pair \(X_1, X_2\) of \(\tau \)-minimizers exist.

A pair of \(G\)-valued random variables \(X_1, X_2\) are said to be a \(\tau \)-minimizer if one has

for all \(G\)-valued random variables \(X'_1, X'_2\).

If \(G\) is finite, then a \(\tau \)-minimizer exists.

A \(\tau \)-minimizer is a tuple \((X_i)_{1 \leq i \leq m}\) that minimizes the \(\tau \)-functional among all tuples of \(G\)-valued random variables.

If \((X_i)_{1 \leq i \leq m}\) is a \(\tau \)-minimizer, then \(\sum _{i=1}^m d[X_i; X^0] \leq \frac{2m}{\eta } d[X^0; X^0]\).

If \(G\) is a torsion-free group and \(X,Y\) are \(G\)-valued random variables and \(\phi :G\to \mathbb {F}_2^d\) is a homomorphism then

If \(G\) is torsion-free and \(X,Y\) are \(G\)-valued random variables then \(d[X;2Y]\leq 5d[X;Y]\).

We have

Given a finite non-empty subset \(H\) of a set \(S\), there exists a random variable \(X\) (on some probability space) that is uniformly distributed on \(H\).

If \(H\) is a subset of \(S\), an \(S\)-random variable \(X\) is said to be uniformly distributed on \(H\) if \(\mathbb {P}[X = s] = 1/|H|\) for \(s \in X\) and \(\mathbb {P}[X=s] = 0\) otherwise.

If \(X\) is \(S\)-valued random variable, then \(\mathbb {H}[X] = \log |S|\) if and only if \(X\) is uniformly distributed on \(S\).

If \(X\) is uniformly distributed on \(H\), then, then \(\mathbb {H}[X] = \log |H|\).

We have

If \(X,Y\) are random variables, then \(\mathbb {I}[X:Y] = 0\) if and only if \(X,Y\) are independent.

If \(A,B\subseteq \mathbb {Z}^d\) are finite non-empty sets then there exist non-empty \(A'\subseteq A\) and \(B'\subseteq B\) such that

such that \(\max (\dim A',\dim B')\leq \frac{40}{\log 2} d[U_A;U_B]\).

Let \(A\subseteq \mathbb {Z}^d\) and \(\lvert A-A\rvert \leq K\lvert A\rvert \). There exists \(A'\subseteq A\) such that \(\lvert A'\rvert \geq K^{-17}\lvert A\rvert \) and \(\dim A' \leq \frac{40}{\log 2}\log K\).

If \(A\subseteq \mathbb {Z}^d\) is a finite non-empty set with \(d[U_A;U_A]\leq \log K\) then there exists a non-empty \(A'\subseteq A\) such that

and \(\dim A'\leq \frac{40}{\log 2} \log K\).

We have \(\sum _{i=1}^m d[X_i;Z_2|W] \leq 8(m^3-m^2) k\).

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]{\gt}0\), then \(x-y \in \mathrm{Sym}[X]\).

We have