- Boxes
- definitions
- Ellipses
- theorems and lemmas
- Blue border
- the statement of this result is ready to be formalized; all prerequisites are done
- Orange border
- the statement of this result is not ready to be formalized; the blueprint needs more work
- Blue background
- the proof of this result is ready to be formalized; all prerequisites are done
- Green border
- the statement of this result is formalized
- Green background
- the proof of this result is formalized
- Dark green background
- the proof of this result and all its ancestors are formalized
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 ^{172} * K ^{146})\) values of \(x \in G\).
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
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 \(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 \(X: \Omega \to S\), \(Y: \Omega \to T\), \(Z: \Omega \to U\) are random variables, then
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
We have
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]\).
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]\).
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
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
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
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 \(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 \(X\) is an \(S\)-valued random variable, then \(\mathbb {H}[X] \leq \log |S|\).
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
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]\).
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\)-valued random variables, then
If \(X,Y,Z\) are \(G\)-valued random variables on \(\Omega \) with \((X,Y)\) independent of \(Z\), then
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]\).
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 three random variables \(X,Y,Z\), one has \(\mathbb {H}[X|Y,Z] \leq \mathbb {H}[X|Z]\).
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
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\).
We have
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]\).