Title: Daniel's Flashcards / Year 4 / Term 2 / Entropy Methods in Combinatorics

html: Definition (Entropy). The entropy of a discrete random variable X is a quantity H [ X ] that takes real values and has the following properties:
- (i) Normalisation: If X is uniform on { 0 , 1 } then H [ X ] = 1.
- (ii) Invariance: If X takes values in A, Y takes values in B, f is a bijection from A to B, and for every a ∈ A we have ℙ [ X = a ] = ℙ [ Y = f ( a ) ], then H [ Y ] = H [ X ].
- (iii) Extendability: If X takes values in a set A, and B is disjoint from A, Y takes values in A ∪ B, and for all a ∈ A we have ℙ [ Y = a ] = ℙ [ X = a ], then H [ Y ] = H [ X ].
- (iv) Maximality: If X takes values in a finite set A and Y is uniformly distributed in A, then H [ X ] ≤ H [ Y ].
- (v) Continuity: H depends continuously on X with respect to total variation distance (defined by the distance between X and Y is sup ⁡ E | ℙ [ X ∈ E ] − ℙ [ Y ∈ E ] |).
For the last axiom we need a definition:
Let X and Y be random variables. The conditional entropy H [ X | Y ] of X given Y is
∑ y ℙ [ Y = y ] H [ X | Y = y ] .
- (vi) Additivity: H [ X , Y ] = H [ Y ] + H [ X | Y ].
nothing: True

html: Lemma 1.1. Assuming that:
- X and Y are independent random variables
Then
H [ X , Y ] = H [ X ] + H [ Y ] .
proof: Proof. H [ X | Y ] = ∑ ⁡ y ℙ [ Y = y ] H [ X | Y = y ].
Since X and Y are independent, the distribution of X is unaffected by knowing Y (so by invariance, H [ X | Y = y ] = H [ X ]), so
H [ X | Y = y ] = H [ X ]
for all y, which gives the result. □
cloze1: True

html: Lemma 1.3 (Chain rule). Assuming that:
- X 1 , … , X n are random variables
Then
H [ X 1 , … , X n ] = H [ X 1 ] + H [ X 2 | X 1 ] + H [ X 3 | X 1 , X 2 ] + ⋯ + H [ X n | X 1 , … , X n − 1 ] .
proof: Proof. The case n = 2 is additivity. In general,
H [ X 1 , … , X n ] = H [ X 1 , … , X n − 1 ] + H [ X n | X 1 , … , X n − 1 ]
so we are done by induction. □
nothing: True

html: Lemma 1.4. Assuming that:
- Y = f ( X )
Then
H [ X , Y ] = H [ X ] .
Also,
H [ Z | X , Y ] = H [ Z | X ] .
proof: Proof. The map g : x ↦ ( x , f ( x ) ) is a bijection, and ( X , Y ) = g ( X ). So the first statement follows by invariance. For the second statement:
H [ Z | X , Y ] = H [ Z , X , Y ] − H [ X , Y ] (by additivity ) = H [ Z , X ] − H [ X ] (by first part) = H [ Z | X ] (by additivity ) □
cloze1: True

html: Lemma 1.5. Assuming that:
- X takes only one value
Then H [ X ] = 0.
proof: Proof. X and X are independent. Therefore, by Lemma 1.1, H [ X , X ] = 2 H [ X ]. But by invariance, H [ X , X ] = H [ X ]. So H [ X ] = 0. □
cloze1: True

html: Proposition 1.6. Assuming that:
- X is uniformly distributed on a set of size 2 n
Then H [ X ] = n.
proof: Proof. Let X 1 , … , X n be independent random variables uniformly distributed on { 0 , 1 }. By Corollary 1.2 and normalisation, H [ X 1 , … , X n ] = n. But ( X 1 , … , X n ) is uniformly distributed on { 0 , 1 } n, so by invariance, the result follows. □
cloze1: True

html: Proposition 1.7. Assuming that:
- X is uniformly distributed on a set A of size n
Then H [ X ] = log ⁡ n.
proof: Proof. Let r be a positive integer and let X 1 , … , X r be independent copies of X.
Then ( X 1 , … , X r ) is uniform on A r and
H [ X 1 , … , X r ] = r H [ X ] .
Now pick k such that 2 k ≤ n r ≤ 2 k + 1. Then by invariance, maximality, and Proposition 1.6, we have that
k ≤ r H [ X ] ≤ k + 1 .
So
k r ≤ log ⁡ n ≤ k + 1 r ⟹ k r ≤ H [ X ] ≤ k + 1 r ∀ ⁡ k , r
Therefore, H [ X ] = log ⁡ n as claimed. □
cloze1: True

html: Theorem 1.8 (Khinchin). Assuming that:
- H satisfies the Khinchin axioms
- X takes values in a finite set A
Then
H [ X ] = ∑ a ∈ A p a log ⁡ ( 1 p a ) .
proof: Proof. First we do the case where all p a are rational (and then can finish easily by the continuity axiom).
Pick n ∈ ℕ such that for all a, there is some m a ∈ ℕ ∪ { 0 } such that p a = m a n.
Let Z be uniform on [ n ]. Let ( E a : a ∈ A ) be a partition of [ n ] into sets with | E a | = m a. By invariance we may assume that X = a ⟺ Z ∈ E a. Then
log ⁡ n = H [ Z ] = H [ Z , X ] = H [ X ] + H [ Z | X ] = H [ X ] + ∑ a ∈ A p a H [ Z | X = a ] = H [ X ] + ∑ a ∈ A p a log ⁡ ( m a ) = H [ X ] + ∑ a ∈ A p a ( log ⁡ p a + log ⁡ n )
Hence
H [ X ] = − ∑ a ∈ A p a log ⁡ p a = ∑ a ∈ A p a log ⁡ ( 1 p a ) .
By continuity, since this holds if all p a are rational, we conclude that the formula holds in general. □
nothing: True

html: Corollary 1.9. Assuming that:
- X and Y random variables
Then H [ X ] ≥ 0 and H [ X | Y ] ≥ 0.
proof: Proof. Immediate consequence of Theorem 1.8. □
cloze1: True

html: Corollary 1.10. Assuming that:
- Y = f ( X )
Then H [ Y ] ≤ H [ X ].
proof: Proof. H [ X ] = H [ X , Y ] = H [ Y ] + H [ X | Y ]. But H [ X | Y ] ≥ 0. □
cloze1: True

html: Proposition 1.11 (Subadditivity). Assuming that:
- X and Y be random variables
Then H [ X , Y ] ≤ H [ X ] + H [ Y ].
proof: Proof. Note that for any two random variables X , Y we have
H [ X , Y ] ≤ H [ X ] + H [ Y ] ⟺ H [ X | Y ] ≤ H [ X ] ⟺ H [ Y | X ] ≤ H [ Y ]
Next, observe that H [ X | Y ] ≤ H [ X ] if X is uniform on a finite set. That is because
H [ X | Y ] = ∑ y ℙ [ Y = y ] H [ X | Y = y ] ≤ ∑ y ℙ [ Y = y ] H [ X ] (by maximality ) = H [ X ]
By the equivalence noted above, we also have that H [ X | Y ] ≤ H [ X ] if Y is uniform.
Now let p a b = ℙ [ ( X , Y ) = ( a , b ) ] and assume that all p a b are rational. Pick n such that we can write p a b = m a b n with each m a b an integer. Partition [ n ] into sets E a b of size m a b. Let Z be uniform on [ n ]. Without loss of generality (by invariance) ( X , Y ) = ( a , b ) ⟺ Z ∈ E a b.
Let E b = ∪ a E a b for each b. So Y = b ⟺ Z ∈ E b. Now define a random variable W as follows: If Y = b, then W ∈ E b, but then W is uniformly distributed in E b and independent of X (or Z if you prefer).
So W and X are conditionally independent given Y, and W is uniform on [ n ].
Then
H [ X | Y ] = H [ X | Y , W ] (by conditional independence) = H [ X | W ] (as W determines Y ) ≤ H [ X ] (as W is uniform)
By continuity, we get the result for general probabilities. □
nothing: True

html: Corollary 1.12. Assuming that:
- X a random variable
Then H [ X ] ≥ 0.
proof: Proof (Without using formula). By Subadditivity, H [ X | X ] ≤ H [ X ]. But H [ X | X ] = 0. □
cloze1: True

html: Corollary 1.13. Assuming that:
- X 1 , … , X n are random variables
Then
H [ X 1 , … , X n ] ≤ H [ X 1 ] + ⋯ + H [ X n ] .
proof: Proof. Induction using Subadditivity. □
cloze1: True

html: Proposition 1.14 (Submodularity). Assuming that:
- X , Y , Z are random variables
Then
H [ X | Y , Z ] ≤ H [ X | Z ] .
proof: Proof. Calculate:
H [ X | Y , Z ] = ∑ z ℙ [ Z = z ] H [ X | Y , Z = z ] ≤ ∑ z ℙ [ Z = z ] H [ X | Z = z ] = H [ X | Z ] □
nothing: True

html: Lemma 1.15. Assuming that:
- X , Y , Z random variables
- Z = f ( Y )
Then
H [ X | Y ] ≤ H [ X | Z ] .
proof: Proof.
H [ X | Y ] = H [ X , Y ] − H [ Y ] = H [ X , Y , Z ] − H [ Y , Z ] ≤ H [ X , Z ] − H [ Z ] ( Submodularity ) = H [ X | Z ] □
cloze1: True

html: Lemma 1.16. Assuming that:
- X , Y , Z random variables
- Z = f ( X ) = g ( Y )
Then
H [ X , Y ] + H [ Z ] ≤ H [ X ] + H [ Y ] .
proof: Proof. Submodularity says:
H [ X , Y , Z ] = H [ Z ] ≤ H [ X , Z ] + H [ Y , Z ]
which implies the result since Z depends on X and Y. □
cloze1: True

html: Lemma 1.17. Assuming that:
- X takes values in a finite set A
- Y is uniform on A
- H [ X ] = H [ Y ]
Then X is uniform.
proof: Proof. Let p a = ℙ [ X = a ]. Then
H [ X ] = ∑ a ∈ A p a log ⁡ ( 1 p a ) = | A | ∑ a ∈ A p a log ⁡ ( 1 p a )
The function x ↦ x log ⁡ 1 x is concave on [ 0 , 1 ]. So, by Jensen’s inequality this is at most
| A | ( 𝔼 a p a ) log ⁡ ( 1 𝔼 a p a ) = log ⁡ ( | A | ) = H [ Y ] .
Equality holds if and only if a ↦ p a is constant – i.e. X is uniform. □
cloze1: True

html: Corollary 1.18. Assuming that:
- X , Y random variables
- H [ X , Y ] = H [ X ] + H [ Y ]
Then X and Y are independent.
proof: Proof. We go through the proof of Subadditivity and check when equality holds.
Suppose that X is uniform on A. Then
H [ X | Y ] = ∑ y ℙ [ Y = y ] H [ X | Y = y ] ≤ H [ X ]
with equality if and only if H [ X | Y = y ] is uniform on A for all y (by Lemma 1.17), which implies that X and Y are independent.
At the last stage of the proof we used
H [ X | Y ] = H [ X | Y , W ] = H [ X | W ] ≤ H [ X ]
where W was uniform. So equality holds only if X and W are independent, which implies (since Y depends on W) that X and Y are indpendent. □
cloze1: True

html: Definition (Mutual information). Let X and Y be random variables. The mutual information I [ X : Y ] is
H [ X ] + H [ Y ] − H [ X , Y ] = H [ X ] − H [ X | Y ] = H [ Y ] − H [ Y | X ]
nothing: True

html: Definition (Conditional mutual information). Let X, Y and Z be random variables. The conditional mutual information of X and Y given Z, denoted by I [ X : Y | Z ] is
∑ z ℙ [ Z = z ] I [ X | Z = z : Y | Z = z ] = ∑ z ℙ [ Z = z ] ( H [ X | Z = z ] + H [ Y | Z = z ] − H [ X , Y | Z = z ] ) = H [ X | Z ] + H [ Y | Z ] − H [ X , Y | Z ] = H [ X , Z ] + H [ Y , Z ] − H [ X , Y , Z ] − H [ Z ]
nothing: True

html: Theorem 2.1. Sidorenko’s conjecture is true if H is a path of length 3.
proof: Proof. We want to show that if G is a bipartite graph of density α with vertex sets X , Y of size m and n and we choose x 1 , x 2 ∈ X, y 1 , y 2 ∈ Y independently at random, then
ℙ [ x 1 y 1 , x 2 y 2 , x 3 y 3 ∈ E ( G ) ] ≥ α 3 .
It would be enough to let P be a P3 chosen uniformly at random and show that H [ P ] ≥ log ⁡ ( α 3 m 2 n 2 ).
Instead we shall define a different random variable taking values in the set of all P3s (and then apply maximality).
To do this, let ( X 1 , Y 1 ) be a random edge of G (with X 1 , ∈ X, Y 1 ∈ Y). Now let X 2 be a random neighbour of Y 1 and let Y 2 be a random neighbour of X 2.
It will be enough to prove that
H [ X 1 , Y 1 , X 2 , Y 2 ] ≥ log ⁡ ( α 3 m 2 n 2 ) .
We can choose X 1 Y 1 in three equivalent ways:
- (1) Pick an edge uniformly from all edges.
- (2) Pick a vertex x with probability proportional to its degree d ( x ), and then pick a random neighbour y of x.
- (3) Same with x and y exchanged.
It follows that Y 1 = y with probability d ( y ) | E ( G ) |, so X 2 Y 1 is uniform in E ( G ), so X 2 = x ′ with probability d ( x ′ ) | E ( G ) |, so X 2 Y 2 is uniform in E ( G ).
Therefore,
H [ X 1 , Y 1 , X 2 , Y 2 ] = H [ X 1 ] + H [ Y 1 | X 1 ] + H [ X 2 | X 1 , Y 1 ] + H [ Y 2 | X 1 , Y 1 , X 2 ] = H [ X 1 ] + H [ Y 1 | X 1 ] + H [ X 2 | Y 1 ] + H [ Y 2 | X 2 ] = H [ X 1 ] + H [ X 1 , Y 1 ] − H [ X 1 ] + H [ X 2 , Y 1 ] − H [ Y 1 ] + H [ Y 2 , X 2 ] − H [ X 2 ] = 3 H [ U E ( G ) ] − H [ Y 1 ] − H [ X 2 ] ≥ 3 H [ U E ( G ) ] − H [ U Y ] − H [ U X ] = 3 log ⁡ ( α m n ) − log ⁡ m − log ⁡ n = log ⁡ ( α 3 m 2 n 2 )
So we are done my maximality.
Alternative finish (to avoid using log ⁡!):
Let X ′ , Y ′ be uniform in X , Y and independent of each other and X 1 , Y 1 , X 2 , Y 2. Then:
H [ X 1 , Y 2 , X 2 , Y 2 , X ′ , Y ′ ] = H [ X 1 , Y 1 , X 2 , Y 2 ] + H [ U X ] + H [ U Y ] ≥ 3 H [ U E ( G ) ]
So by maximality,
# P 3 s × | X | × | Y | ≥ | E ( G ) | 3 . □

html: Definition (Permanent of a matrix). Let A be an n × n matrix over ℝ. The permanent of A, denoted per ⁡ ( A ), is
∑ σ ∈ S n ∏ i = 1 n A i σ ( i ) ,
i.e. “the determinant without the signs”.
nothing: True

html: Theorem 3.1 (Bregman). Assuming that:
- G a bipartite graph with vertex sets X , Y of size n
Then the number of perfect matchings in G is at most
∏ x ∈ X ( d ( x ) ! ) 1 d ( x ) .
proof: Proof (Radhakrishnan). Each matching corresponds to a bijection σ : X → Y such that x σ ( x ) ∈ E ( G ) for every x. Let σ be chosen uniformly from all such bijections.
H [ σ ] = H [ σ ( x 1 ) ] + H [ σ ( x 2 ) | σ ( x 1 ) ] + ⋯ + H [ σ ( x n ) | σ ( x 1 ) , … , σ ( x n − 1 ) ] ,
where x 1 , … , x n is some enumeration of X.
Then
H [ σ ( x 1 ) ] ≤ log ⁡ d ( x 1 ) H [ σ ( x 2 ) | σ ( x 1 ) ] ≤ 𝔼 σ log ⁡ d x 1 σ ( x 2 )
where
d x i σ ( x 2 ) = | N ( x 2 ) ∖ { σ ( x 1 ) } | .
In general,
H [ σ ( x i ) ] σ ( x 1 ) , … , σ ( x i − 1 ) ≤ 𝔼 σ log ⁡ d x 1 , … , x i − 1 σ ( x i ) ,
where
d x 1 , … , x i − 1 σ ( x i ) = | N ( x i ) ∖ { σ ( x 1 ) , … , σ ( x i − 1 ) } | .
Key idea: we now regard x 1 , … , x n as a random enumeration of X and take the average.
For each x ∈ X, define the contribution of x to be
log ⁡ ( d x 1 , … , x i − 1 σ ( x i ) )
where x i = x (note that this “contribution” is a random variable rather than a constant).
We shall now fix σ. Let the neighbours of x be y 1 , … , y k.
Then one of the y j will be σ ( x ), say y h. Note that d x 1 , … , x i − 1 σ ( x i ) (given that x i = x) is
d ( x ) − | { j : σ − 1 ( y j ) comes earlier than x = σ − 1 ( y h ) } | .
All positions of σ − 1 ( y h ) are equally likely, so the average contribution of x is
1 d ( x ) ( log ⁡ d ( x ) + log ⁡ ( d ( x ) − 1 ) + ⋯ + log ⁡ 1 ) = 1 d ( x ) log ⁡ ( d ( x ) ! ) .
By linearity of expectation,
H [ σ ] ≤ ∑ x ∈ X 1 d ( x ) log ⁡ ( d ( x ) ! ) ,
so the number of matchings is at most
∏ x ∈ X ( d ( x ) ! ) 1 d ( x ) . □
nothing: True

html: Definition (1-factor). Let G be a graph with 2 n vertices. A 1-factor in G is a collection of n disjoint edges.
nothing: True

html: Theorem 3.2 (Kahn-Lovasz). Assuming that:
- G a graph with 2 n vertices
Then the number of 1-factors in G is at most
∏ x ∈ V ( G ) ( d ( x ) ! ) 1 2 d ( x ) .
proof: Proof (Alon, Friedman). Let M be the set of 1-factors of G, and let ( M 1 , M 2 ) be a uniform random element of M 2. For each M 1 , M 2, the union M 1 ∪ M 2 is a collection of disjoint edges and even cycles that covers all the vertices of G.
Call such a union a cover of G by edges and even cycles.
If we are given such a cover, then the number of pairs ( M 1 , M 2 ) that could give rise to it is 2 k, where k is the number of even cycles.
Now let’s build a bipartite graph G 2 out of G. G 2 has two vertex sets (call them V 1 , V 2), both copies of V ( G ). Join x ∈ V 1 to y ∈ V 2 if and only if x y ∈ E ( G ).
For example:
By Bregman, the number of perfect matchings in G 2 is ≤ ∏ ⁡ x ∈ V ( G ) ( d ( x ) ! ) 1 d ( x ). Each matching gives a permutation σ of V ( G ), such that x σ ( x ) ∈ E ( G ) for every x ∈ V ( G ).
Each such σ has a cycle decomposition, and each cycle gives a cycle in G. So σ gives a cover of V ( G ) by isolated vertices, edges and cycles.
Given such a cover with k cycles, each edge can be directed in two ways, so the number of σ that give rise to is is 2 k, where k is the number of cycles.
So there is an injection from M 2 to the set of matchings of G 2, since every cover by edges and even cycles is a cover by vertices, edges and cycles.
So
| M | 2 ≤ ∏ x ∈ V ( G ) ( d ( x ) ! ) 1 d ( x ) . □
nothing: True

html: Lemma 4.1 (Shearer). Assuming that:
- X = ( X 1 , … , X n ) a random variable
- A a family of subsets of [ n ] such that every i ∈ [ n ] belongs to at least r of the sets A ∈ A
Then
H [ X 1 , … , X n ] ≤ 1 r ∑ A ∈ A H [ X A ] .
proof: Proof. For each a ∈ [ n ], write X < a for ( X 1 , … , X a − 1 ).
For each A ∈ A, A = { a 1 , … , a k } with a 1 < ⋯ < a k, we have
H [ X A ] = H [ X a 1 ] + H [ X a 2 | X a 1 ] + ⋯ + H [ X a k | X a 1 , … , X a k ] ≥ H [ X a 1 | X < a 1 ] + H [ X a 2 | X < a 2 ] + ⋯ + H [ X a k | X < a k ] (Lemma 1.15 ) = ∑ a ∈ A H [ X a | X < a ]
Therefore,
∑ A ∈ A H [ X A ] ≥ ∑ A ∈ A ∑ a ∈ A H [ X a | X < a ] ≥ r ∑ a = 1 n H [ X a | X < a ] = r H [ X ] □
nothing: True

html: Lemma 4.2 (Shearer, expectation version). Assuming that:
- X = ( X 1 , … , X n ) a random variable
- A ⊂ [ n ] a randomly chosen subset of [ n ], according to some probability distribution (don’t need any independence conditions!)
- for each i ∈ [ n ], ℙ [ i ∈ A ] ≥ μ
Then
H [ X ] ≤ μ − 1 𝔼 A H [ X A ] .
proof: Proof. As before,
H [ X A ] ≥ ∑ a ∈ A H [ X a | X < a ] .
So
𝔼 A H [ X A ] ≥ 𝔼 A ∑ a ∈ A H [ X a | X < a ] ≥ μ ∑ a = 1 n H [ X a | X < a ] = μ H [ X ] □
nothing: True

html: Definition (P A). Let E ⊂ ℤ n and let A ⊂ [ n ]. Then we write P A E for the set of all u ∈ ℤ A such that there exists v ∈ ℤ [ n ] ∖ A such that [ u , v ] ∈ E, where [ u , v ] is u suitably intertwined with v (i.e. u ∪ v as functions).
nothing: True

html: Corollary 4.3. Assuming that:
- E ⊂ ℤ n
- A a family of subsets of [ n ] such that every i ∈ [ n ] is contained at least r sets A ∈ A
Then
| E | ≤ ∏ A ∈ A | P A E | 1 r .
proof: Proof. Let X be a uniform random element of E. Then by Shearer,
H [ X ] ≤ 1 r ∑ A ∈ A H [ X A ] .
But X A tkaes values in P A E, so
H [ X A ] ≤ log ⁡ | P A X ,
so
log ⁡ | E | ≤ 1 r ∑ A log ⁡ | P A E | . □
cloze1: True

html: Theorem 4.4. Assuming that:
- G a graph with m edges
Then G has at most ( 2 m ) 3 2 6 triangles.
proof: Proof. Let ( X 1 , X 2 , X 3 ) be a random ordered triangle (without loss of generality G has a triangle so that this is possible).
Let t be the number of triangles in G. By Shearer,
log ⁡ ( 6 t ) = H [ X 1 , X 2 , X 3 ] ≤ 1 2 ( H [ X 1 , X 2 ] + H [ X 1 , X 3 ] + H [ X 2 , X 3 ] ) .
Each edge H [ X i , X j ] is supported in the set of edges G, given a direction, i.e.
1 2 ( H [ X 1 , X 2 ] + H [ X 1 , X 3 ] + H [ X 2 , X 3 ] ) ≤ 3 2 ⋅ log ⁡ ( 2 m ) . □
cloze1: True

html: Theorem 4.5. Assuming that:
- | V | = n
- G a Δ-intersecting family with vertex set V
Then G has size at most 2 n 2 − 2.
proof: Proof. Let X be chosen uniformly at random from G. We write V ( 2 ) for the set of (unordered) pairs of elements of V. Think of any G ∈ G as a function from V ( 2 ) to { 0 , 1 }. So X = ( X e : e ∈ V ( 2 ) ).
For each R ⊂ V, let G R be the graph K R ∪ K V ∖ R
For each R, we shall look at the projection X G R, which we can think of as taking values in the set { G ∩ G R : G ∈ G } = : G R.
Note that if G 1 , G 2 ∈ G, R ⊂ [ n ], then G 1 ∩ G 2 ∩ G R ≠ ∅, since G 1 ∩ G 2 contains a triangle, which must intersect G R by Pigeonhole Principle.
Thus, G R is an intersecting family, so it has size at most 2 | E ( G R ) | − 1. By Shearer, expectation version,
H [ X ] ≤ 2 𝔼 R H [ X G R ] ( since each e belongs to G R with probability 1 ∕ 2 ) ≤ 2 𝔼 R ( | E ( G R ) | − 1 ) = 2 ( 1 2 m 2 − 1 ) = n 2 − 2 □
cloze1: True

html: Definition (Edge-boundary). Let G be a graph and let A ⊂ V ( G ). The edge-boundary ∂ A of A is the set of edges x y such that y ∉ A.
If G = ℤ n or { 0 , 1 } n and i ∈ [ n ], then the i-th boundary ∂ i A is the set of edges x y ∈ ∂ A such that x − y = ± e i, i.e. ∂ i A consists of deges pointing in direction i.
nothing: True

html: Theorem 4.6 (Edge-isoperimetric inequality in Z n). Assuming that:
- A ⊂ ℤ n a finite set
Then | ∂ A | ≥ 2 n | A | n − 1 n.
proof: Proof. By the discrete Loomis-Whitney inequality,
| A | ≤ ∏ i = 1 n | P [ n ] ∖ { i } A | 1 n − 1 = ( ∏ i = 1 n | P [ n ] ∖ { i } A | 1 n ) n n − 1 ≤ ( 1 n ∑ i = 1 n | P [ n ] ∖ { i } A | ) n n − 1
But | ∂ i A | ≥ 2 | P [ n ] ∖ { i } A | since each fibre contributes at least 2.
So
| A | ≤ ( 1 2 n ∑ i = 1 n | ∂ i A | ) n n − 1 = ( 1 2 n | ∂ A | ) n n − 1 □
nothing: True

html: Theorem 4.7 (Edge-isoperimetric inequality in the cube). Assuming that:
- A ⊂ { 0 , 1 } n (where we take the usual graph)
Then | ∂ A | ≥ | A | ( n − log ⁡ | A | ).
proof: Proof. Let X be a uniform random element of A and write X = ( X 1 , … , X n ). Write X ∖ i for ( X 1 , … , X i − 1 , X i + 1 , … , X n ). By Shearer,
H [ X ] ≤ 1 n − 1 ∑ i = 1 r H [ X ∖ i ] = 1 n − 1 ∑ i = 1 n H [ X ] − H [ X i | X ∖ i ]
Hence
∑ i = 1 n H [ X i | X ∖ i ] ≤ H [ X ] .
Note
H [ X i | X ∖ i = u ] = { 1 | P [ n ] ∖ { i } − 1 ( u ) | = 2 0 | P [ n ] ∖ { i } − 1 ( u ) | = 1
The number of points of the second kind is | ∂ i A |, so H [ X i | X ∖ i ] = 1 − | ∂ i A | | A |. So
H [ X ] ≥ ∑ i = 1 n ( 1 − | ∂ i A | | A | ) = n − | ∂ A | | A |
Also, H [ X ] = log ⁡ | A |. So we are done. □
nothing: True

html: Definition (Lower shadow). Let A be a family of sets of size d. The lower shadow ∂ A is { B : | B | = d − 1 , ∃ ⁡ A ∈ A , B ⊂ A }.
nothing: True

html: Theorem 4.8 (Kruskal-Katona). Assuming that:
- | A | = t d = t ( t − 1 ) ⋯ ( t − d − 1 ) d ! for some real number t
Then | ∂ A | ≥ t d − 1.
proof: Proof. Let X = ( X 1 , … , X d ) be a random ordering of the elements of a uniformly random A ∈ A. Then
H [ X ] = log ⁡ ( d ! t d ) .
Note that ( X 1 , … , X d − 1 ) is an ordering of the elements of some B ∈ ∂ A, so
H [ X 1 , … , X d − 1 ] ≤ log ⁡ ( ( d − 1 ) ! | ∂ A | ) .
So it’s enough to show
H [ X 1 , … , X d − 1 ] ≥ log ⁡ ( ( d − 1 ) ! t d − 1 ) .
Also,
H [ X ] = H [ X 1 , … , X d − 1 ] + H [ X d | X 1 , … , X d − 1 ]
and
H [ X ] = H [ X 1 ] + H [ X 2 | X 1 ] + ⋯ + H [ X d | X 1 , … , X d − 1 ] .
We would like an upper bound for H [ X d ] X < d. Our strategy will be to obtain a lower bound for H [ X k | X < k ] in terms of H [ X k + 1 | X < k + 1 ]. We shall prove that
2 H [ X k | X < k ] ≥ 2 H [ X k + 1 | X < k + 1 ] + 1 ∀ ⁡ k .
Let T be chosen independently of X 1 , … , X k − 1 with
T = { 0 probability p 1 probability 1 − p
(p will be chosen and optimised later).
Given X 1 , … , X k − 1, let
X ∗ = { X k + 1 T = 0 X k T = 1
Note that X k and X k + 1 have the same distribution (given X 1 , … , X k − 1), so X ∗ does as well. Then
H [ X k | X < k ] = H [ X ∗ | X < k ] ≥ H [ X ∗ | X ≤ k ] ( Submodularity ) = H [ X ∗ , T | X ≤ k ] ( X ≤ k and X ∗ determine T ) = H [ T | X ≤ k ] + H [ X ∗ | T , X ≤ k ] ( additivity ) = H [ T ] + p H [ X k + 1 | X 1 , … , X k ] + ( 1 − p ) H [ X k | X 1 , … , X k ] = h ( p ) + p s
where h ( p ) = p log ⁡ 1 p + ( 1 − p ) log ⁡ 1 1 − p and s = H [ X k + 1 | X 1 , … , X k ].
It turns out that this is maximised when p = 2 s 2 s + 1. Then we get
2 s 2 s + 1 ( log ⁡ ( 2 s + 1 ) − log ⁡ 2 s ) + log ⁡ ( 2 s + 1 ) 2 s + 1 + s 2 s 2 s + 1 = log ⁡ ( 2 s + 1 ) .
This proves the claim.
Let r = 2 H [ X d | X 1 , … , X d − 1 ]. Then
H [ X ] = H [ X 1 ] + ⋯ + H [ X d | X 1 , … , X d − 1 ] ≥ log ⁡ r + log ⁡ ( r + 1 ) + ⋯ + log ⁡ ( r + d − 1 ) = log ⁡ ( ( r + d − 1 ) ! ( r − 1 ) ! ) = log ⁡ ( d ! r + d − 1 d )
Since H [ X ] = log ⁡ ( d ! t d ), it follows that
r + d − 1 ≤ t , r ≤ t + 1 − d .
It follows that
H [ X 1 , … , X d − 1 ] = log ⁡ ( d ! t d ) − log ⁡ r ≥ log ⁡ ( d ! t ! d ! ( t − d ) ! ( t + 1 − d ) ) = log ⁡ ( ( d − 1 ) ! t d − 1 ) □
nothing: True

html: Definition (Union-closed). Let A be a (finite) family of sets. Say that A is union closed if for any A , B ∈ A, we have A ∪ B ∈ A.
nothing: True

html: Conjecture. If A is a non-empty union-closed family, then there exists x that belongs to at least 1 2 | A | sets in A.
proof: Proof. Think of A , B as characteristic functions. Write A < k for ( A 1 , … , A k − 1 ) etc. By the Chain rule it is enough to prove for every k that
H [ ( A ∪ B ) k | ( A ∪ B ) < k ] > c ( 1 − p ) ( H [ A k | A < k ] + H [ B k | B < k ] ) .
By Submodularity,
H [ ( A ∪ B ) k | ( A ∪ B ) < k ] ≥ H [ ( A ∪ B ) k | A < k , B < k ] .
For each u , v ∈ { 0 , 1 } k − 1 write p ( u ) = ℙ ( A k = 0 | A < k = u ), q ( v ) = ℙ ( B k = 0 | B < k = v ).
Then
H [ ( A ∪ B ) k | A < k = u , B < k = v ] = h ( p ( u ) q ( v ) )
which by hypothesis is at least
c ( p ( u ) h ( q ( v ) ) + q ( v ) h ( p ( u ) ) ) .
So
H [ ( A ∪ B ) k | ( A ∪ B ) < k ] ≥ c ∑ u , v ℙ ( A < k = u ) ℙ ( B < k = v ) ( p ( u ) h ( q ( v ) ) + q ( v ) h ( p ( u ) ) ) .
But
∑ u ℙ ( A < k = u ) ℙ ( A k = 0 | A < k = u ) = ℙ ( A k = 0 )
and
∑ v ℙ ( B < k = v ) h ( q ( v ) ) = ∑ v ℙ ( B < k = v ) H [ B k | B < k = v ] = H [ B k | B < k ] .
Similarly for the other term, so the RHS equals
c ( ℙ ( A k = 0 ) H [ B k | B < k ] + ℙ ( B k = 0 ) H [ A k | A < k ] ) ,
which by hypothesis is greater than
c ( 1 − p ) ( H [ A k | A < k ] + H [ B k | B < k ] )
as required. □

html: Theorem (Justin Gilmer). There exists c > 0 such that if A is a union-closed family, then there exists x that belongs to at least c | A | of the sets in A.
proof: Proof. Think of A , B as characteristic functions. Write A < k for ( A 1 , … , A k − 1 ) etc. By the Chain rule it is enough to prove for every k that
H [ ( A ∪ B ) k | ( A ∪ B ) < k ] > c ( 1 − p ) ( H [ A k | A < k ] + H [ B k | B < k ] ) .
By Submodularity,
H [ ( A ∪ B ) k | ( A ∪ B ) < k ] ≥ H [ ( A ∪ B ) k | A < k , B < k ] .
For each u , v ∈ { 0 , 1 } k − 1 write p ( u ) = ℙ ( A k = 0 | A < k = u ), q ( v ) = ℙ ( B k = 0 | B < k = v ).
Then
H [ ( A ∪ B ) k | A < k = u , B < k = v ] = h ( p ( u ) q ( v ) )
which by hypothesis is at least
c ( p ( u ) h ( q ( v ) ) + q ( v ) h ( p ( u ) ) ) .
So
H [ ( A ∪ B ) k | ( A ∪ B ) < k ] ≥ c ∑ u , v ℙ ( A < k = u ) ℙ ( B < k = v ) ( p ( u ) h ( q ( v ) ) + q ( v ) h ( p ( u ) ) ) .
But
∑ u ℙ ( A < k = u ) ℙ ( A k = 0 | A < k = u ) = ℙ ( A k = 0 )
and
∑ v ℙ ( B < k = v ) h ( q ( v ) ) = ∑ v ℙ ( B < k = v ) H [ B k | B < k = v ] = H [ B k | B < k ] .
Similarly for the other term, so the RHS equals
c ( ℙ ( A k = 0 ) H [ B k | B < k ] + ℙ ( B k = 0 ) H [ A k | A < k ] ) ,
which by hypothesis is greater than
c ( 1 − p ) ( H [ A k | A < k ] + H [ B k | B < k ] )
as required. □
nothing: True

html: Lemma 5.1. Assuming that:
- c > 0 is such that
h ( x y ) ≥ c ( x h ( y ) + y h ( x ) )
for every x , y ∈ [ 0 , 1 ]
- A is a family of sets such that every element (of ⋃ ⁡ A) belongs to fewer than p | A | members of A
Then H [ A ∪ B ] > c ( 1 − p ) ( H [ A ] + H [ B ] ).
proof: Proof. Think of A , B as characteristic functions. Write A < k for ( A 1 , … , A k − 1 ) etc. By the Chain rule it is enough to prove for every k that
H [ ( A ∪ B ) k | ( A ∪ B ) < k ] > c ( 1 − p ) ( H [ A k | A < k ] + H [ B k | B < k ] ) .
By Submodularity,
H [ ( A ∪ B ) k | ( A ∪ B ) < k ] ≥ H [ ( A ∪ B ) k | A < k , B < k ] .
For each u , v ∈ { 0 , 1 } k − 1 write p ( u ) = ℙ ( A k = 0 | A < k = u ), q ( v ) = ℙ ( B k = 0 | B < k = v ).
Then
H [ ( A ∪ B ) k | A < k = u , B < k = v ] = h ( p ( u ) q ( v ) )
which by hypothesis is at least
c ( p ( u ) h ( q ( v ) ) + q ( v ) h ( p ( u ) ) ) .
So
H [ ( A ∪ B ) k | ( A ∪ B ) < k ] ≥ c ∑ u , v ℙ ( A < k = u ) ℙ ( B < k = v ) ( p ( u ) h ( q ( v ) ) + q ( v ) h ( p ( u ) ) ) .
But
∑ u ℙ ( A < k = u ) ℙ ( A k = 0 | A < k = u ) = ℙ ( A k = 0 )
and
∑ v ℙ ( B < k = v ) h ( q ( v ) ) = ∑ v ℙ ( B < k = v ) H [ B k | B < k = v ] = H [ B k | B < k ] .
Similarly for the other term, so the RHS equals
c ( ℙ ( A k = 0 ) H [ B k | B < k ] + ℙ ( B k = 0 ) H [ A k | A < k ] ) ,
which by hypothesis is greater than
c ( 1 − p ) ( H [ A k | A < k ] + H [ B k | B < k ] )
as required. □
cloze1: True

html: Lemma 5.2 (Boppana). For every x ∈ [ 0 , 1 ],
h ( x 2 ) ≥ ϕ x h ( x ) .
proof: Proof. Write ψ for ϕ − 1 = 5 − 1 2. Then ψ 2 = 1 − ψ, so h ( ψ 2 ) = h ( 1 − ψ ) = h ( ψ ) and ϕ ψ = 1, so h ( ψ 2 ) = ϕ ψ h ( ψ ). Equality also when x = 0 , 1.
Toolkit:
ln ⁡ 2 h ( x ) = − x ln ⁡ x − ( 1 − x ) ln ⁡ ( 1 − x ) ln ⁡ 2 h ′ ( x ) = − ln ⁡ x − 1 + ln ⁡ ( 1 − x ) + 1 = ln ⁡ ( 1 − x ) − ln ⁡ x ln ⁡ 2 h ″ ( x ) = − 1 x − 1 1 − x ln ⁡ 2 h ‴ ( x ) = 1 x 2 − 1 ( 1 − x ) 2
Let f ( x ) = h ( x 2 ) − ϕ x h ( x ). Then
f ′ ( x ) = 2 x h ′ ( x 2 ) − ϕ h ( x ) − ϕ x h ′ ( x ) f ″ ( x ) = 2 h ′ ( x 2 ) + 4 x 2 h ″ ( x 2 ) − 2 ϕ h ′ ( x ) − ϕ x h ″ ( x ) f ‴ ( x ) = 4 x h ″ ( x 2 ) + 8 x h ″ ( x 2 ) + 8 x 3 h ‴ ( x 2 ) − 3 ϕ h ″ ( x ) − ϕ x h ‴ ( x ) = 1 2 x h ″ ( x 2 ) + 8 x 3 h ‴ ( x 2 ) − 3 ϕ h ″ ( x ) − ϕ x h ‴ ( x )
So
ln ⁡ 2 f ‴ ( x ) = − 1 2 x x 2 ( 1 − x 2 ) + 8 x 3 ( 1 − 2 x 2 ) x 4 ( 1 − x 2 ) 2 + 3 ϕ x ( 1 − x ) − ϕ x ( 1 − 2 x ) x 2 ( 1 − x ) 2 = − 1 2 x ( 1 − x 2 ) + 8 ( 1 − 2 x 2 ) x ( 1 − x 2 ) 2 + 3 ϕ x ( 1 − x ) − ϕ ( 1 − 2 x ) x ( 1 − x ) 2 = − 1 2 ( 1 − x 2 ) + 8 ( 1 − 2 x 2 ) + 3 ϕ ( 1 − x ) ( 1 + x ) 2 − ϕ ( 1 − 2 x ) ( 1 + x ) 2 x ( 1 − x ) 2 ( 1 + x ) 2
This is zero if and only if
− 1 2 + 1 2 x 2 + 8 − 1 6 x 2 + 3 ϕ ( 1 + x − x 2 − x 3 ) − ϕ ( 1 − 3 x 2 − 2 x 3 ) = 0
which simplifies to
− ϕ x 3 − 4 x 2 + 3 ϕ x − 4 + 2 ϕ = 0 .
Since this is a cubic with negative leading coefficient and constant term, it has a negative root, so it has at most two roots in ( 0 , 1 ). It follows (using Rolle’s theorem) that f has at most five roots in [ 0 , 1 ], up to multiplicity.
But
f ′ ( x ) = 2 x ( log ⁡ ( 1 − x 2 ) − log ⁡ x 2 ) + ϕ ( x log ⁡ x + ( 1 − x ) log ⁡ ( 1 − x ) ) − ϕ x ( log ⁡ ( 1 − x ) − log ⁡ x ) .
So f ′ ( 0 ) = 0, so f has a double root at 0.
We can also calculate (using ψ 2 + ψ = 1):
f ′ ( ψ ) = 2 ψ ( log ⁡ ψ − 2 log ⁡ ψ ) + ϕ ( ψ log ⁡ ψ + 2 ( 1 − ψ ) log ⁡ ψ ) − ( 2 log ⁡ ψ − log ⁡ ψ ) = − 2 ψ log ⁡ ψ + log ⁡ ψ + 2 ϕ log ⁡ ψ − 2 log ⁡ ψ − log ⁡ ψ = 2 log ⁡ ψ ( − ψ + ϕ − 1 ) = 2 ϕ log ⁡ ψ ( − ψ 2 + 1 − ψ ) = 0
So there’s a double root at ψ.
Also, note f ( 1 ) = 0.
So f is either non-negative on all of [ 0 , 1 ] or non-positive on all of [ 0 , 1 ].
If x is small,
f ( x ) = x 2 log ⁡ 1 x 2 + ( 1 − x 2 ) log ⁡ 1 1 − x 2 − ϕ x ( x log ⁡ 1 x + ( 1 − x ) log ⁡ 1 1 − x ) = 2 x 2 log ⁡ 1 x − ϕ x 2 log ⁡ 1 x + O ( x 2 )
so there exists x such that f ( x ) > 0. □
nothing: True

html: Lemma 5.3. The function f ( x , y ) = h ( x y ) x h ( y ) + y h ( x ) is minimised on ( 0 , 1 ) 2 at a point where x = y.
proof: Proof. We can extend f continuously to the boundary by setting f ( x , y ) = 1 whenever x or y is 0 or 1. To see this, note first that it’s valid if neither x nor y is 0.
If either x or y is small, then
h ( x y ) = − x y ( log ⁡ x + log ⁡ y ) + O ( x y ) x h ( y ) + y h ( x ) = − x ( y log ⁡ y + O ( y ) ) − y ( x log ⁡ x + O ( x ) ) = h ( x ) + O ( x y )
So it tends to 1 again.
One can check that f ( 1 2 , 1 2 ) < 1, so f is minimised somewhere in ( 0 , 1 ) 2.
Let ( x ∗ , y ∗ ) be a minimum with f ( x ∗ , y ∗ ) = α.
Let g ( x ) = h ( x ) x and note that
f ( x , y ) = g ( x y ) g ( x ) + g ( y ) .
Also,
g ( x y ) − α ( g ( x ) + g ( y ) ) ≥ 0
with equality at ( x ∗ , y ∗ ). So the partial derivatives of LHS are both 0 at ( x ∗ , y ∗ ).
y ∗ g ′ ( x ∗ y ∗ ) − α g ′ ( x ∗ ) = 0 x ∗ g ′ ( x ∗ y ∗ ) − α g ′ ( y ∗ ) = 0
So x ∗ g ′ ( x ∗ ) = y ∗ g ′ ( y ∗ ). So it’s enough to prove that x g ′ ( x ) is an injection. g ′ ( x ) = h ′ ( x ) x − h ( x ) x 2, so
x g ′ ( x ) = h ′ ( x ) − h ( x ) x = log ⁡ ( 1 − x ) − log ⁡ x + x log ⁡ x + ( 1 − x ) log ⁡ ( 1 − x ) x = log ⁡ ( 1 − x ) x
Differentiating gives
− 1 x ( 1 − x ) − log ⁡ ( x − 1 ) x 2 = − x − ( 1 − x ) log ⁡ ( 1 − x ) x 2 ( 1 − x ) .
The numerator differentiates to − 1 + 1 + log ⁡ ( 1 − x ), which is negative everywhere. Also, it equals 0 at 0. So it has a constant sign. □

html: Definition (Sum set / difference set / etc). Let G be an abelian group and let A , B ⊂ G.
The sumset A + B is the set { x + y : x ∈ A , y ∈ B }.
The difference set A − B is the set { x − y : x ∈ A , y ∈ B }.
We write 2 A for A + A, 3 A for A + A + A, etc.
nothing: True

html: Definition (Ruzsa distance). The Ruzsa distance d ( A , B ) is
| A − B | | A | 1 2 | B | 1 2 .
nothing: True

html: Lemma 6.1 (Ruzsa triangle inequality). d ( A , C ) ≤ d ( A , B ) + d ( B , C ).
proof: Proof. This is equivalent to the statement
| A − C | | B | ≤ | A − B | | B − C | .
For each x ∈ A − C, pick a ( x ) ∈ A, c ( x ) ∈ C such that a ( x ) − c ( x ) = x. Define a map
ϕ : ( A − C ) × B → ( A − B , B − C ) ( x , b ) ↦ ( a ( x ) − b , b − c ( x ) )
Adding the coordinates of ϕ ( x , b ) gives x, so we can calculate a ( x ) (and c ( x )) from ϕ ( x , b ), and hence can calculate b. So ϕ is an injection. □
nothing: True

html: Lemma 6.2 (Ruzsa covering lemma). Assuming that:
- G an abelian group
- A , B finite subsets of G
Then A can be covered by at most | A + B | | B | translates of B − B.
proof: Proof. Let { x 1 , … , x k } be a maximal subset of A such that the sets x i + B are disjoint.
Then if a ∈ A, there exists i such that ( a + B ) ∩ ( x i + B ) ≠ ∅. Then a ∈ x i + B − B.
So A can be covered by k translates of B − B. But
| B | k = | { x 1 , … ⁡ , x k } + B ⏟ ⊂ A + B | ≤ | A + B | . □
nothing: True

html: Definition (Entropic Ruzsa distance). Let G be an abelian group and let X, Y be G-valued random variables. The entropic Ruzsa distance d [ X ; Y ] is
H [ X ′ − Y ′ ] − 1 2 H [ X ] − 1 2 H [ Y ]
where X ′, Y ′ are independent copies of X and Y.
nothing: True

html: Lemma 6.3. Assuming that:
- A, B are finite subsets of G
- X, Y are uniformly distributed on A, B respectively
Then
d [ X ; Y ] ≤ log ⁡ d ( A , B ) .
proof: Proof. Without loss of generality X, Y are indepent. Then
d [ X ; Y ] = H [ X − Y ] − 1 2 H [ X ] − 1 2 H [ Y ] ≤ log ⁡ | A − B | − 1 2 log ⁡ A − 1 2 log ⁡ B = log ⁡ d ( A , B ) □
cloze1: True

html: Lemma 6.4. Assuming that:
- X, Y are G-valued random variables
Then
H [ X + Y ] ≥ max ⁡ { H [ X ] , H [ Y ] } − I [ X : Y ] .
proof: Proof.
H [ X + Y ] ≥ H [ X + Y | Y ] (by Subadditivity ) = H [ X + Y , Y ] − H [ Y ] = H [ X , Y ] − H [ Y ] = H [ X ] + H [ Y ] − H [ Y ] − I [ X : Y ] = H [ X ] − I [ X : Y ]
By symmetry we also have
H [ X + Y ] ≥ H [ Y ] − I [ X : Y ] . □
cloze1: True

html: Corollary 6.5. Assuming that:
- X, Y are G-valued random variables
Then
d [ X ; Y ] ≥ 0 .
proof: Proof. Without loss of generality X, Y are independent. Then I [ X : Y ] = 0, so
H [ X − Y ] ≥ max ⁡ { H [ X ] , H [ Y ] } ≥ 1 2 ( H [ X ] + H [ Y ] ) □
cloze1: True

html: Lemma 6.6. Assuming that:
- X, Y are G-valued random variables
Then d [ X ; Y ] = 0 if and only if there is some (finite) subgroup H of G such that X and Y are uniform on cosets of H.
proof: Proof.
- ⇐ If X, Y are uniform on x + H, y + H, then X ′ − Y ′ is uniform on x − y + H, so
H [ X ′ − Y ′ ] = H [ X ] = H [ Y ] .
So d [ X ; Y ] = 0.
- ⇒ Suppose that X, Y are independent and H [ X − Y ] = 1 2 ( H [ X ] + H [ Y ] ).
From the first line of the proof of Lemma 6.4, it follows that H [ X − Y | Y ] = H [ X − Y ]. Therefore, X − Y and Y are independent. So for every z ∈ A − B and every y 1 , y 2 ∈ B,
ℙ ( X − Y = z | Y = y 1 ) = ℙ ( X − Y = z | Y = y 2 )
where A = { x : p x ≠ 0 }, B = { y : q y ≠ 0 }, i.e. for all y 1 , y 2 ∈ B,
ℙ ( X = y 1 + z ) = ℙ ( X = y 2 + z ) .
So p x is constant on z + B.
In particular, A ⊃ z + B.
By symmetry, B ⊃ A − z.
So A = B + z for any z ∈ A − B. So for every x ∈ A, y ∈ B, A = B + x − y, so A − x = B − y. So A − x is the same for every x ∈ A. Therefore, A − x = A − A for every x ∈ A.
It follows that
A − A + A − A = ( A − x ) − ( A − x ) = A − A .
So A − A is a subgroup. Also, A = A − A + c, so A is a coset of A − A. B = A + z, so B is also a coset of A − A. □
cloze1: True

html: Lemma 6.7 (The entropic Ruzsa triangle inequality). Assuming that:
- X, Y, Z are G-valued random variables
Then
d [ X ; Z ] ≤ d [ X ; Y ] + d [ Y ; Z ] .
proof: Proof. We must show that (assuming without loss of generality that X, Y and Z are independent) that
H [ X − Z ] − 1 2 H [ X ] − 1 2 H [ Z ] ≤ H [ X − Y ] − 1 2 H [ X ] − 1 2 H [ Y ] + H [ Y − Z ] − 1 2 H [ Y ] − 1 2 H [ Z ] ,
i.e. that
H [ X − Z ] + H [ Y ] ≤ H [ X − Y ] + H [ Y − Z ] . (∗)
Since X − Z is a function of ( X − Y , Y − Z ) and is also a function of ( X , Z ), we get using Lemma 1.16 that
H [ X − Y , Y − Z , X , Z ] + H [ X − Z ] ≤ H [ X − Y , Y − Z ] + H [ X , Z ] .
This is the same as
H [ X , Y , Z ] + H [ X − Z ] ≤ H [ X , Z ] + H [ X − Y , Y − Z ] .
By independence, cancelling common terms and Subadditivity, we get (∗). □
nothing: True

html: Lemma 6.8 (Submodularity for sums). Assuming that:
- X, Y, Z are independent G-valued random variables
Then
H [ X + Y + Z ] + H [ Z ] ≤ H [ X + Z ] + H [ Y + Z ] .
proof: Proof. X + Y + Z is a function of ( X + Z , Y ) and also a function of ( X , Y + Z ). Therefore (using Lemma 1.16),
H [ X + Z , Y X , Y + Z ] + H [ X + Y + Z ] ≤ H [ X + Z , Y ] + H [ X , Y + Z ] .
Hence
H [ X , Y , Z ] + H [ X + Y + Z ] ≤ H [ X + Z ] + H [ Y ] + H [ X ] + H [ Y + Z ] .
By independence and cancellation, we get the desired inequality. □
nothing: True

html: Lemma 6.9. Assuming that:
- G an abelian group
- X a G-valued random variable
Then
d [ X ; − X ] ≤ 2 d [ X ; X ] .
proof: Proof. Let X 1, X 2, X 3 be independent copies of X. Then
d [ X ; − X ] = H [ X 1 + X 2 ] − 1 2 H [ X 1 ] − 1 2 H [ X 2 ] ≤ H [ X 1 + X 2 − X 3 ] − H [ X ] ≤ H [ X 1 − X 3 ] + H [ X 2 − X 3 ] − H [ X 3 ] − H [ X ] = 2 d [ X ; X ]
(as X 1 , X 2 , X 3 are all copies of X). □
cloze1: True

html: Corollary 6.10. Assuming that:
- X and Y are G-valued random variables
Then
d [ X ; − Y ] ≤ 5 d [ X ; Y ] .
proof: Proof.
d [ X ; − Y ] ≤ d [ X ; Y ] + d [ Y ; − Y ] ≤ d [ X ; Y ] + 2 d [ Y ; Y ] ≤ d [ X ; Y ] + 2 ( d [ Y ; X ] + d [ X ; Y ] ) = 5 d [ X ; Y ] □
cloze1: True

html: Definition (Conditional distance). Let X , Y , U , V be G-valued random variables (in fact, U and V don’t have to be G-valued for the definition to make sense). Then the conditional distance is
d [ X | U ; Y | V ] = ∑ u , v ℙ [ U = u ] ℙ [ V = v ] d [ X | U = u ; Y | V = v ] .
nothing: True

html: Definition (Simultaneous conditional distance). Let X , Y , U be G-valued random variables. The simultaneous conditional distance of X to Y given U is
d [ X ; Y ∥ U ] = ∑ u ℙ [ U = u ] d [ X | U = u ; Y | U = u ] .
We say that X ′, Y ′ are conditionally independent trials of X, Y given U if:
- X ′ is distributed like X.
- Y ′ is distributed like Y.
- For each u ∈ U, X ′ | U = u is distributed like X | U = u,
- For each u ∈ U, Y ′ | U = u is distributed like Y | U = u.
- X ′ | U = u and Y ′ | U = u are independent.
Then
d [ X ; Y ∥ U ] = H [ X ′ − Y ′ | U ] − 1 2 H [ X ′ | U ] − 1 2 H [ Y ′ | U ]
(as can be seen directly from the formula).
nothing: True

html: Lemma 6.11 (The entropic BSG theorem). Assuming that:
- A and B are G-valued random variables
Then
d [ A ; B ∥ A + B ] ≤ 3 I [ A : B ] + 2 H [ A + B ] − H [ A ] − H [ B ] .
proof: Proof.
d [ A ; B ∥ A + B ] = H [ A ′ − B ′ | A + B ] − 1 2 H [ A ′ | A + B ] − 1 2 H [ B ′ | A + B ]
where A ′, B ′ are conditionally independent trials of A, B given A + B. Now calculate
H [ A ′ | A + B ] = H [ A | A + B ] = H [ A , A + B ] − H [ A + B ] = H [ A , B ] − H [ A + B ] = H [ A ] + H [ B ] − I [ A : B ] − H [ A + B ]
Similarly, H [ B ′ | A + B ] is the same, so 1 2 H [ A ′ | A + B ] + 1 2 H [ B ′ | A + B ] is also the same.
H [ A ′ − B ′ | A + B ] ≤ H [ A ′ − B ′ ] .
Let ( A 1 , B 1 ) and ( A 2 , B 2 ) be conditionally independent trials of ( A , B ) given A + B. Then H [ A ′ − B ′ ] = H [ A 1 − B 2 ]. By Submodularity,
H [ A 1 − B 2 ] ≤ H [ A 1 − B 2 , A ] + H [ A 1 − B 2 , B 1 ] − H [ A 1 − B 2 , A 1 , B 1 ] H [ A 1 − B 2 , A 1 ] = H [ A 1 , B 2 ] ≤ H [ A 1 ] + H [ B 2 ] = H [ A ] + H [ B ] H [ A 1 − B 2 , B 1 ] = H [ A 2 − B 1 , B 1 ] (since A 1 + B 1 = A 2 + B 2 ) = H [ A 2 , B 1 ] ≤ H [ A ] + H [ B ]
Finally,
H [ A 1 − B 2 , A 1 , B 1 ] = H [ A 1 , B 1 , A 2 , B 2 ] = H [ A 1 , B 1 , A 2 , B 2 | A + B ] + H [ A + B ] = 2 H [ A , B ] A + B + H [ A + B ] (by conditional independence of ( A 1 , B 1 ) and ( A 2 , B 2 ) ) = 2 H [ A , B ] − H [ A + B ] = 2 H [ A ] + 2 H [ B ] − 2 I [ A : B ] − H [ A + B ]
Adding or subtracting as appropriate all these terms gives the required inequality. □
nothing: True

html: Theorem 7.1 (Green, Manners, Tao, Gowers). There is a polynomial p with the following property:
If n ∈ ℕ and A ⊂ 𝔽 2 n is such that | A + A | ≤ C | A |, then there is a subspace H ⊂ 𝔽 2 n of size at most | A | such that A is contained in the union of at most p ( C ) translates of H. (Equivalently, there exists K ⊂ 𝔽 2 n, | K | ≤ p ( C ) such that A ⊂ K + H).
proof: Proof. If not, then
H [ X ] = ∑ x p x log ⁡ ( 1 p x ) > H [ X ] ∑ x p x = H [ X ] ,
contradiction. □
nothing: True

html: Theorem 7.2 (Entropic Polynomial Freiman–Ruzsa). There exists an absolute constant α satisfying the following: Let G = 𝔽 2 n and let X , Y be G-valued random variables. Then there exists a subsgroup H of G such that
d [ X ; U H ] + d [ U H ; Y ] ≤ α d [ X ; Y ]
where U H is the uniform distribution on H.
proof: Proof. If not, then
H [ X ] = ∑ x p x log ⁡ ( 1 p x ) > H [ X ] ∑ x p x = H [ X ] ,
contradiction. □
nothing: True

html: Lemma 7.3. Assuming that:
- X a discrete random variable (and write p x for ℙ ( X = x ))
Then there exists x such that p x ≥ 2 − H [ X ].
proof: Proof. If not, then
H [ X ] = ∑ x p x log ⁡ ( 1 p x ) > H [ X ] ∑ x p x = H [ X ] ,
contradiction. □
cloze1: True

html: Proposition 7.4. Theorem 7.2 implies Theorem 7.1.
proof: Proof. Let A ⊂ 𝔽 2 n, | A + A | ≤ C | A |. Let X and Y be independent copies of U A. Then by Theorem 7.2, there exists H (a subgroup) such that
d [ X ; U H ] + d [ U H ; X ] ≤ α d [ X ; Y ]
so
d [ X ; U H ] ≤ α 2 d [ X ; Y ] .
But
d [ X ; Y ] = H [ U A − U A ′ ] − H [ U A ] = H [ U A + U A ′ ] − H [ U A ] (characteristic 2) ≤ log ⁡ ( C | A | ) − log ⁡ | A | = log ⁡ C
So d [ X ; U H ] ≤ α log ⁡ C 2. Therefore
H [ X + U H ] ≤ 1 2 H [ X ] + 1 2 H [ U H ] + α log ⁡ C 2 = 1 2 log ⁡ | A | + 1 2 log ⁡ | H | + α log ⁡ C 2
Therefore, by Lemma 7.3, there exists z such that
ℙ ( X + U H = z ) ≥ | A | − 1 2 | H | − 1 2 C − α 2 .
But
ℙ ( X + U H = z ) = | A ∩ ( z − H ) | | A | | H | = | A ∩ ( z + H ) | | A | | H |
(using characteristic 2). So there exists z ∈ G such that
| A ∩ ( z + H ) | ≥ C − α 2 | A | 1 2 | H | 1 2 .
Let B = A ∩ ( z + H ). By the Ruzsa covering lemma, we can cover A by at most | A + B | | B | translates of B + B. But B ⊂ z + H so B + B ⊂ H + H = H, so A can be covered by at most | A + B | | B | translates of H.
But using B ⊂ A,
| A + B | ≤ | A + A | ≤ C | A | .
So
| A + B | | B | ≤ C | A | C − α 2 | A | 1 2 | H | 1 2 = C α 2 + 1 | A | 1 2 | H | 1 2 .
Since B is contained in z + H,
| H | ≥ C − α 2 | A | 1 2 | H | 1 2
so | H | ≥ C − α | A |, so
C α 2 + 1 | A | 1 2 | H | 1 2 ≤ C α + 1 .
If | H | ≤ | A | then we are done. Otherwise, since B ⊂ A,
| A | ≥ C − α 2 | A | 1 2 | H | 1 2
so | H | ≤ C α | A |.
Pick a subgroup H ′ of H of size between | A | 2 and | A |. Then H is a union of at most 2 C α translates of H ′, so A is a union of at most 2 C 2 α + 1 translates of H ′. □

html: Theorem 7.5 (EPFR′). There is a constant η > 0 such that if X and Y are any two 𝔽 2 n-valued random variables with d [ X ; Y ] > 0, then there exists 𝔽 2 n-valued random variables U and V such that
d [ U ; V ] + η ( d [ U ; X ] + d [ V ; Y ] ) < d [ X ; Y ] .
proof: Proof. By compactness we can find U, V such that
τ X , Y [ U ; V ] = d [ U ; V ] + η ( d [ U ; X ] + d [ V ; Y ] )
is minimised. If d [ U ; V ] ≠ 0 then by EPFR′(η) there exist Z, W such that τ U , V [ Z ; W ] < d [ U ; V ].
But then
τ X , Y [ Z ; W ] = d [ Z ; W ] + η ( d [ Z ; X ] + d [ W ; Y ] ) ≤ d [ Z ; W ] + η ( d [ Z ; U ] + d [ W ; V ] ) + η ( d [ U ; X ] + d [ V ; Y ] ) (by The entropic Ruzsa triangle inequality ) < d [ U ; V ] + η ( d [ U ; X ] + d [ V ; Y ] ) = τ X , Y [ U ; V ]
Contradiction.
It follows that d [ U ; V ] = 0. So there exists H such that U and V are uniform on cosets of H, so
η ( d [ U H ; X ] + d [ U H ; Y ] ) < d [ X ; Y ] ,
which gives us EPFR(η − 1). □
nothing: True

html: Proposition 7.6. EPFR′(η) ⟹ EPFR(η − 1).
proof: Proof. By compactness we can find U, V such that
τ X , Y [ U ; V ] = d [ U ; V ] + η ( d [ U ; X ] + d [ V ; Y ] )
is minimised. If d [ U ; V ] ≠ 0 then by EPFR′(η) there exist Z, W such that τ U , V [ Z ; W ] < d [ U ; V ].
But then
τ X , Y [ Z ; W ] = d [ Z ; W ] + η ( d [ Z ; X ] + d [ W ; Y ] ) ≤ d [ Z ; W ] + η ( d [ Z ; U ] + d [ W ; V ] ) + η ( d [ U ; X ] + d [ V ; Y ] ) (by The entropic Ruzsa triangle inequality ) < d [ U ; V ] + η ( d [ U ; X ] + d [ V ; Y ] ) = τ X , Y [ U ; V ]
Contradiction.
It follows that d [ U ; V ] = 0. So there exists H such that U and V are uniform on cosets of H, so
η ( d [ U H ; X ] + d [ U H ; Y ] ) < d [ X ; Y ] ,
which gives us EPFR(η − 1). □

html: Definition. Write τ X , Y [ U | Z ; V | W ] for
∑ Z , W ℙ [ Z = z ] ℙ [ W = w ] τ X , Y [ U | Z = z ; V | W = w ]
cloze1: True

html: Definition. Write τ X , Y [ U ; V ∥ Z ] for
∑ z ℙ [ Z = z ] τ X , Y [ U | z = z ; V | Z = z ]
cloze1: True

html: Lemma 7.7 (Fibring lemma). Assuming that:
- G and H are abelian groups
- ϕ : G → H a homomorphism
- let X, Y be G-valued random variables.
Then
d [ X ; Y ] = d [ ϕ ( X ) ; ϕ ( Y ) ] + d [ X | ϕ ( X ) ; Y | ϕ ( Y ) ] + I [ X − Y : ϕ ( X ) , ϕ ( Y ) | ϕ ( X ) − ϕ ( Y ) ] .
proof: Proof.
d [ X ; Y ] = H [ X − Y ] − 1 2 H [ X ] − 1 2 H [ Y ] = H [ ϕ ( X ) − ϕ ( Y ) ] + H [ X − Y | ϕ ( X ) − ϕ ( Y ) ] − 1 2 H [ ϕ ( X ) ] − 1 2 H [ X | ϕ ( X ) ] − 1 2 H [ ϕ ( Y ) ] − 1 2 H [ Y | ϕ ( Y ) ] = d [ ϕ ( X ) ; ϕ ( Y ) ] + d [ X | ϕ ( X ) ; Y | ϕ ( Y ) ] + H [ X − Y | ϕ ( X ) − ϕ ( Y ) ] − H [ X − Y | ϕ ( X ) , ϕ ( Y ) ]
But the last line of this expression equals
H [ X − Y | ϕ ( X ) − ϕ ( Y ) ] − H [ X − Y | ϕ ( X ) , ϕ ( Y ) , ϕ ( X ) − ϕ ( Y ) ] = I [ X − Y : ϕ ( X ) , ϕ ( Y ) | ϕ ( X ) − ϕ ( Y ) ] . □
nothing: True

html: Corollary 7.8. Assuming that:
- G = 𝔽 2 n and X 1 , X 2 , X 3 , X 4 are independent G-valued random variables
Then d [ ( X 1 , X 2 ) ; ( X 3 , X 4 ) ] = d [ X 1 ; X 3 ] + d [ X 2 ; X 4 ] = d [ X 1 + X 2 ; X 3 + X 4 ] + d [ X 1 | X 1 + X 2 ; X 3 | X 3 + X 4 ] + I [ X 1 + X 3 , X 2 + X 4 : X 1 + X 2 , X 3 + X 4 | X 1 + X 2 + X 3 + X 4 ] ⏟ ( ∗ )
proof: Proof. Apply Lemma 7.7 with X = ( X 1 , X 2 ), Y = ( X 3 , X 4 ) and ϕ ( x , y ) = x + y. □
cloze1: True

html: Lemma 7.9.
2 d [ X 1 ; X 2 ] + 2 d [ X 3 ; X 4 ] + d [ X 1 ; X 4 ] + d [ X 2 ; X 3 ] ≥ 2 d [ X 1 + X 2 ; X 3 + X 4 ] + d [ X 1 + X 4 ; X 2 + X 3 ] + 2 d [ X 1 | X 1 + X 2 ; X 3 | X 3 + X 4 ] + d [ X 1 | X 1 + X 4 ; X 2 | X 2 + X 3 ] + 1 3 ( d [ X 1 + X 2 ; X 1 + X 3 ∥ X 2 + X 3 , W ] + d [ X 1 + X 2 ; X 1 + X 4 ∥ X 2 + X 4 , W ] + d [ X 1 + X 4 ; X 1 + X 3 ∥ X 3 + X 4 , W ] )
proof: Proof. Above. □
cloze1: True

html: Lemma 7.10. Assuming that:
- X 1 , X 2 , Y 1 , Y 2 satisfy: X 1 and X 2 are copies of X, Y 1 and Y 2 are copies of Y, and all of them are independent
Then 6 d [ X ; Y ] ≥ 2 d [ X 1 + X 2 ; Y 1 + Y 2 ] + d [ X 1 + Y 2 ; X 2 + Y 1 ] + 2 d [ X 1 | X 1 + X 2 ; Y 1 | Y 1 + Y 2 ] + d [ X 1 | X 1 + Y 1 ; X 2 | X 2 + Y 2 ] + 2 3 d [ X 1 + X 2 ; X 1 + Y 1 ∥ X 2 + Y 1 , X 1 + Y 2 ] + 1 3 d [ X 1 + Y 1 ; X 1 + Y 2 ∥ X 1 + X 2 , Y 1 + Y 2 ]
OR? TODO: figure out which is correct
6 d [ X ; Y ] ≥ 2 d [ X 1 + X 2 ; Y 1 + Y 2 ] + d [ X 1 + Y 1 ; X 2 + Y 2 ] + 2 d [ X 1 | X 1 + X 2 ; Y 1 | Y 1 + Y 2 ] + d [ X 1 | X 1 + Y 1 ; X 2 | X 2 + Y 2 ] + 2 3 d [ X 1 + X 2 | X 1 + Y 1 ; X 2 + Y 1 | X 1 + Y 2 ] + 1 3 d [ X 1 + Y 1 | X 1 + Y 2 ; X − 1 + X 1 | Y 1 + Y 2 ]
proof: Proof. Use above. □
cloze1: True

html: Definition (C-relevant). Say that ( U , V ) is C-relevant to ( X , Y ) if
d [ U ; X ] + d [ V ; Y ] ≤ C d [ X ; Y ] .
nothing: True

html: Lemma 7.11. ( Y , X ) is 2-relevant to ( X , Y ).
proof: Proof. d [ Y ; X ] + d [ X ; Y ] = 2 d [ X ; Y ]. □
cloze1: True

html: Lemma 7.12. Assuming that:
- U , V , X be independent 𝔽 2 n-valued random variables
Then
d [ U + V ; X ] ≤ 1 2 ( d [ U ; X ] + d [ V ; X ] + d [ U ; V ] ) .
proof: Proof.
d [ U + V ; X ] = H [ U + V + X ] − 1 2 H [ U + V ] − 1 2 H [ X ] = H [ U + V + X ] − H [ U + V ] + 1 2 H [ U + V ] − 1 2 H [ X ] ≤ 1 2 H [ U + X ] − 1 2 H [ U ] + 1 2 H [ V + X ] − 1 2 H [ V ] + 1 2 H [ U + V ] − 1 2 H [ X ] = 1 2 ( d [ U ; X ] + d [ V ; X ] + d [ U ; V ] ) □
cloze1: True

html: Corollary 7.13. Assuming that:
- ( U , V ) is C-relevant to ( X , Y )
- U 1 , U 2 , V 1 , V 2 are independent copies of U , V
Then ( U 1 + U 2 , V 1 + V 2 ) is 2 C-relevant to ( X , Y ).
proof: Proof.
d [ U 1 + U 2 ; X ] + d [ V 1 + V 2 ; Y ] ≤ 1 2 ( 2 d [ U ; V ] + d [ U ; U ] + 2 d [ V ; Y ] + d [ V ; V ] ) (by Lemma 7.12 ) ≤ 2 ( d [ U ; X ] + d [ V ; Y ] ) (by The entropic Ruzsa triangle inequality ) ≤ 2 C d [ X ; Y ] □
cloze1: True

html: Corollary 7.14. ( X 1 + X 2 , Y 1 + Y 2 ) is 4-relevant to ( Y , X ).
proof: Proof. ( X , Y ) is 2-relevant to ( Y , X ), so by Corollary 7.13 we’re done. □
cloze1: True

html: Corollary. Assuming that:
- ( U , V ) is C-relevant to ( X , Y )
Then ( U + V , U + V ) is ( 3 C + 2 )-relevant to ( X , Y ).
proof: Proof. By Lemma 7.12,
d [ U + V ; X ] + d [ U + V ; Y ] ≤ 1 2 ( d [ U ; X ] + d [ V ; X ] + d [ U ; Y ] + d [ V ; Y ] + 2 d [ U ; V ] ) ≤ 1 2 ( 2 d [ U ; X ] + 4 d [ U ; V ] + 2 d [ V ; Y ] ) ≤ 1 2 ( 6 d [ U ; X ] + 6 d [ V ; Y ] + 4 d [ X ; Y ] ) □
cloze1: True

html: Corollary 7.15. Assuming that:
- ( U , V ) is C-relevant to ( X , Y )
Then ( U + V , U + V ) is 2 ( C + 1 )-relevant to ( X , Y ).
proof: Proof.
d [ U + V ; X ] ≤ 1 2 ( d [ U ; X ] + d [ V ; X ] + d [ U ; V ] ) ≤ 1 2 ( d [ U ; X ] + d [ V ; Y ] + d [ X ; Y ] + d [ U ; X ] + d [ X ; Y ] + d [ V ; Y ] ) = d [ U ; X ] + d [ V ; Y ] + d [ X ; Y ]
Similarly for d [ U + V ; Y ]. □
cloze1: True

html: Lemma 7.16. Assuming that:
- U , V , X are independent 𝔽 2 n-valued random variables
Then
d [ U | U + V ; X ] ≤ 1 2 ( d [ U ; X ] + d [ V ; X ] + d [ U ; V ] ) .
proof: Proof.
d [ U | U + V ; X ] ≤ H [ U + X | U + V ] − 1 2 H [ U | U + V ] − 1 2 H [ X ] ≤ H [ U + X ] − 1 2 H [ U ] − 1 2 H [ V ] + 1 2 H [ U + V ] − 1 2 H [ X ]
But d [ U | U + V ; X ] = d [ V | U + V ; X ], so it’s also
≤ H [ V + X ] − 1 2 H [ U ] − 1 2 H [ V ] + 1 2 H [ U + V ] − 1 2 H [ X ] .
Averaging the two inequalities gives the result (as earlier). □
cloze1: True

html: Corollary 7.17. Assuming that:
- U , V are independent random variables
- ( U , V ) is C-relevant to ( X , Y )
Then
- (i) ( U 1 | U 1 + U 2 , V 1 | V 1 + V 2 ) is 2 C-relevant to ( X , Y ).
- (ii) ( U 1 | U 1 + V 1 , U 2 | U 2 + V 2 ) is 2 ( C + 1 )-relevant to ( X , Y ).
proof: Proof. Use Lemma 7.16. Then as soon as it is used, we are in exactly the situation we were in when bounding the relevance of ( U 1 + U 2 , V 1 + V 2 ) and ( U 1 + V 1 , U 2 + V 2 ). □
cloze1: True