AFTD Auto-Formalizing Theoretical Domains

op_1567_hellinger_factor_one_fails

theoremverified

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

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.

  1. 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.

    line 4

      intro h
  2. The 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.

    lines 5–12

    uses Fin.sum_univ_two

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

    lines 13–15

    uses hellinger_mutual_information, Fintype.sum_prod_type, Fin.sum_univ_two, Matrix.cons_val_zero, Matrix.cons_val_one

      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
  4. 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.

    lines 16–25

      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
  5. 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.

    line 26

      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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it