op_1567_hellinger_factor_one_fails
Multiplicative subadditivity with factor C = 1 fails for Hellinger mutual information: not hellinger_information_multiplicative_subadditive 1.
Statement
theorem op_1567_hellinger_factor_one_fails :
¬ hellinger_information_multiplicative_subadditive 1- Source
- scout/2610-21231-on-the-subadditivity-of-mutual-f-information.md:123
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- hellinger_information_multiplicative_subadditiveA real number C satisfies multiplicative subadditivity for Hellinger mutual information if for all finite types X, Y, Z, every prior pX on…
- hellinger_mutual_informationFor finite types U and V, the Hellinger mutual information of a joint distribution p on U × V is defined as ∑ u, ∑ v, (Real.sqrt (p u v) -…
Read back from the Lean
The negation of hellinger_information_multiplicative_subadditive 1. That is, it is false that for all finite types $X, Y, Z$, all probability distributions $p_X : X \to \mathbb{R}$ (satisfying $\forall x, 0 \le p_X(x)$ and $\sum_{x} p_X(x) = 1$), and all conditional probability distributions (transition kernels) $P_Y : X \to Y \to \mathbb{R}$ and $P_Z : X \to Z \to \mathbb{R}$ (satisfying nonnegativity and summing to 1 over their respective codomains for each $x \in X$), the Hellinger mutual information between $X$ and the pair $(Y, Z)$ under the conditionally independent joint distribution $p(x, (y, z)) = p_X(x) P_Y(x, y) P_Z(x, z)$ is bounded by 1 times the sum of the Hellinger mutual information between $X$ and $Y$ and that between $X$ and $Z$. In other words, subadditivity of Hellinger mutual information fails with constant $C = 1$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof is by contradiction, disproving factor-1 multiplicative subadditivity by constructing an explicit two-state counterexample. The universal subadditivity hypothesis is instantiated with binary random variables X, Y, Z having prior distribution (1/300, 299/300) and asymmetric binary channels for Y and Z conditioned on X. Expanding the definition of Hellinger mutual information yields a concrete numerical inequality involving square roots, which is shown to be false by numerical verification.
Assume for contradiction that multiplicative subadditivity holds with factor C = 1.
We argue by contradiction, introducing the hypothesis h that Hellinger mutual information is multiplicatively subadditive with constant C = 1 for all finite alphabets and all valid probability distributions.
intro hThe subadditivity inequality is instantiated on a concrete two-state counterexample.
We specialize the subadditivity hypothesis to binary alphabets X = Y = Z = {0, 1}, prior distribution p_X = (1/300, 299/300), and conditional probability matrices P_Y = [[1/3, 2/3], [1/300, 299/300]] and P_Z = [[2/3, 1/3], [299/300, 1/300]]. The required conditions that all entries are non-negative and row sums equal 1 are checked by exhausting the two elements of Fin 2.
uses
Fin.sum_univ_twohave h1 := h (Fin 2) (Fin 2) (Fin 2) ![1/300, 299/300] ![![1/3, 2/3], ![1/300, 299/300]] ![![2/3, 1/3], ![299/300, 1/300]] (by intro x; fin_cases x <;> norm_num) (by norm_num [Fin.sum_univ_two]) (by intro x y; fin_cases x <;> fin_cases y <;> norm_num) (by intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num) (by intro x y; fin_cases x <;> fin_cases y <;> norm_num) (by intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num)
The inequality reduces to an explicit numerical inequality between expressions with square roots of rationals.
We unfold the definition of Hellinger mutual information, split the product sum into nested sums, expand the two-element sums, evaluate vector lookups, and perform rational arithmetic, leaving an explicit inequality between sums of squared differences of square roots.
uses
hellinger_mutual_information,Fintype.sum_prod_type,Fin.sum_univ_two,Matrix.cons_val_zero,Matrix.cons_val_onesimp only [hellinger_mutual_information, Fintype.sum_prod_type, Fin.sum_univ_two, Fin.isValue, Matrix.cons_val_zero, Matrix.cons_val_one] at h1 norm_num at h1
Inside five squared terms of the inequality, the order of subtraction is reversed.
Using the algebraic identity (a - b)^2 = (b - a)^2, five of the squared differences are rewritten so that the larger numerical term is subtracted from, putting each difference in positive form.
rw [show ((Real.sqrt 675)⁻¹ - Real.sqrt 8923633 / Real.sqrt 2700000000) ^ 2 = (Real.sqrt 8923633 / Real.sqrt 2700000000 - (Real.sqrt 675)⁻¹) ^ 2 from by ring, show (299 / Real.sqrt 27000000 - Real.sqrt 10903633 / Real.sqrt 2700000000) ^ 2 = (Real.sqrt 10903633 / Real.sqrt 2700000000 - 299 / Real.sqrt 27000000) ^ 2 from by ring, show (Real.sqrt 299 / Real.sqrt 27000000 - Real.sqrt 1026467 / Real.sqrt 2700000000) ^ 2 = (Real.sqrt 1026467 / Real.sqrt 2700000000 - Real.sqrt 299 / Real.sqrt 27000000) ^ 2 from by ring, show ((Real.sqrt 450)⁻¹ - Real.sqrt 29867 / 3000) ^ 2 = (Real.sqrt 29867 / 3000 - (Real.sqrt 450)⁻¹) ^ 2 from by ring, show (Real.sqrt 299 / 300 - Real.sqrt 39767 / 3000) ^ 2 = (Real.sqrt 39767 / 3000 - Real.sqrt 299 / 300) ^ 2 from by ring] at h1
A contradiction is derived from the numerical inequality. automation
Numerical evaluation verifies that the left-hand side strictly exceeds the right-hand side, refuting the inequality and deriving False.
num_ineq
Fin.sum_univ_two- The sum of a function over the two-element type Fin 2 equals f 0 + f 1.
Fintype.sum_prod_type- A sum over a Cartesian product of two finite types equals the iterated sum over each component.
hellinger_mutual_information- The definition of Hellinger mutual information for a joint distribution p(u, v), given by ∑ u v, (√(p u v) - √((∑ v', p u v') * (∑ u', p u' v)))^2.
Matrix.cons_val_one- The second element (index 1) of a vector formed by prepending an element x to a tail vector u is the head of u.
Matrix.cons_val_zero- The first element (index 0) of a vector formed by prepending an element x to a tail vector u is x.
- The final step relies on the automated tactic num_ineq, which proves false numerical inequalities by computing rigorous interval bounds on the real square root expressions.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Ordinary factor-one subadditivity fails for Hellinger mutual information. -/theorem op_1567_hellinger_factor_one_fails : ¬ hellinger_information_multiplicative_subadditive 1 := by intro h have h1 := h (Fin 2) (Fin 2) (Fin 2) ![1/300, 299/300] ![![1/3, 2/3], ![1/300, 299/300]] ![![2/3, 1/3], ![299/300, 1/300]] (by intro x; fin_cases x <;> norm_num) (by norm_num [Fin.sum_univ_two]) (by intro x y; fin_cases x <;> fin_cases y <;> norm_num) (by intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num) (by intro x y; fin_cases x <;> fin_cases y <;> norm_num) (by intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num) simp only [hellinger_mutual_information, Fintype.sum_prod_type, Fin.sum_univ_two, Fin.isValue, Matrix.cons_val_zero, Matrix.cons_val_one] at h1 norm_num at h1 rw [show ((Real.sqrt 675)⁻¹ - Real.sqrt 8923633 / Real.sqrt 2700000000) ^ 2 = (Real.sqrt 8923633 / Real.sqrt 2700000000 - (Real.sqrt 675)⁻¹) ^ 2 from by ring, show (299 / Real.sqrt 27000000 - Real.sqrt 10903633 / Real.sqrt 2700000000) ^ 2 = (Real.sqrt 10903633 / Real.sqrt 2700000000 - 299 / Real.sqrt 27000000) ^ 2 from by ring, show (Real.sqrt 299 / Real.sqrt 27000000 - Real.sqrt 1026467 / Real.sqrt 2700000000) ^ 2 = (Real.sqrt 1026467 / Real.sqrt 2700000000 - Real.sqrt 299 / Real.sqrt 27000000) ^ 2 from by ring, show ((Real.sqrt 450)⁻¹ - Real.sqrt 29867 / 3000) ^ 2 = (Real.sqrt 29867 / 3000 - (Real.sqrt 450)⁻¹) ^ 2 from by ring, show (Real.sqrt 299 / 300 - Real.sqrt 39767 / 3000) ^ 2 = (Real.sqrt 39767 / 3000 - Real.sqrt 299 / 300) ^ 2 from by ring] at h1 num_ineq