PFR

Other version of gen_ineq_00, in which we switch to the complement in the second term.

Other version of gen_ineq_00, in which we switch to the complement in the first term.

For any $T_1, T_2, T_3$ adding up to $0$, then $k$ is at most $\delta + \eta (d[X^0_1;T_1|T_3]-d[X^0_1;X_1]) + \eta (d[X^0_2;T_2|T_3]-d[X^0_2;X_2])$ where $\delta = I[T₁ : T₂ ; μ] + I[T₂ : T₃ ; μ] + I[T₃ : T₁ ; μ]$.

In fact $k$ is at most

$k$ is at most

For p.η ≤ 1/8, there exist τ-minimizers X₁, X₂ at zero Rusza distance. For p.η < 1/8, all minimizers are fine, by tau_strictly_decreases'. For p.η = 1/8, we use a limit of minimizers for η < 1/8, which exists by compactness.

entropic_PFR_conjecture_improv: For two $G$-valued random variables $X^0_1, X^0_2$, there is some subgroup $H \leq G$ such that $d[X^0_1;U_H] + d[X^0_2;U_H] \le 10 d[X^0_1;X^0_2]$.

entropic_PFR_conjecture_improv': For two $G$-valued random variables $X^0_1, X^0_2$, there is some subgroup $H \leq G$ such that $d[X^0_1;U_H] + d[X^0_2;U_H] \le 10 d[X^0_1;X^0_2]$., and d[X^0_1; U_H] and d[X^0_2; U_H] are at most 5/2 * d[X^0_1;X^0_2]

The polynomial Freiman-Ruzsa (PFR) conjecture: if $A$ is a subset of an elementary abelian 2-group of doubling constant at most $K$, then $A$ can be covered by at most 2K^{11} cosets of a subgroup of cardinality at most $|A|$.

Corollary of PFR_conjecture_improv in which the ambient group is not required to be finite (but) then $H$ and $c$ are finite.

KL(X ‖ Y) ≥ 0.

KL(X ‖ Y) = 0 if and only if Y is a copy of X.

If $S$ is a finite set, $w_s$ is non-negative, 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 $D_{KL}(X\Vert Y) \le \sum_{s\in S} w_s D_{KL}(X_s\Vert Y_s).$

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