AFTD Auto-Formalizing Theoretical Domains

mutual_hellinger_information_not_subadditive

theoremverifiedoriginal

Subadditivity fails in the Hellinger case β = 1/2: there are binary random variables X, Y, Z with Y ← X → Z and Ĩ_{f_{1/2}}(X; YZ) > Ĩ_{f_{1/2}}(X; Y) + Ĩ_{f_{1/2}}(X; Z). Instance: P(X = 0) = 1/300; P(Y = 0 | X = 0) = 1/3, P(Y = 0 | X = 1) = 1/300; Z is Y's channel mirrored, P(Z = z | x) = P(Y = 1 − z | x).

Statement

theorem mutual_hellinger_information_not_subadditive :
    ∃ (pX : Fin 2 → ℝ) (PY PZ : Fin 2 → Fin 2 → ℝ),
      (∀ x, 0 ≤ pX x) ∧ ∑ x, pX x = 1 ∧ (∀ x y, 0 ≤ PY x y) ∧ (∀ x, ∑ y, PY x y = 1) ∧
      (∀ x z, 0 ≤ PZ x z) ∧ (∀ x, ∑ z, PZ x z = 1) ∧
      mutual_f_information (power_divergence_generator (1 / 2)) (fun x y => pX x * PY x y) +
          mutual_f_information (power_divergence_generator (1 / 2)) (fun x z => pX x * PZ x z) <
        mutual_f_information (power_divergence_generator (1 / 2))
          (fun x (yz : Fin 2 × Fin 2) => pX x * PY x yz.1 * PZ x yz.2)
Related work
List entry OP-332, a question proposed here from arXiv:2610.21231 (On the subadditivity of mutual f-information), Theorem 1 (a sufficient condition for subadditivity, toward the open question of Polyanskiy and Wu on further subadditive examples); the paper does not discuss the Hellinger case. Answered in the negative at β = 1/2.
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • mutual_f_informationFor a joint probability mass function p_{XY} on finite sets, the mutual f-information is Ĩ_f(X; Y) = D_f(p_{XY} ‖ p_X p_Y) = Σ_{x,y}…
  • power_divergence_generatorThe power-divergence generator f_β(x) = (x^β − βx + β − 1)/(β(β − 1)), for β ∉ {0, 1} and x ≥ 0 (β = 1/2 gives 2(√x − 1)², the squared…
  • power_divergence_half_root_boundsFor x ≥ 0 and b ≥ 0, if a^2 ≤ x ≤ b^2 then a ≤ x^(1/2) ≤ b.
Used by 1

The proof, explained

Subadditivity of mutual f-information is shown to fail for the Hellinger case β = 1/2 via an explicit binary counterexample: X has prior distribution (1/300, 299/300), Y is obtained through a channel with conditional distributions (1/3, 2/3) and (1/300, 299/300), and Z is Y's channel mirrored. After verifying that these define valid probability distributions, the subadditivity defect reduces to an algebraic inequality involving ten square roots of rational numbers. The proof establishes sharp two-sided rational bounds on each square root and completes the verification by real linear arithmetic.

  1. We instantiate the random variables with explicit probability distributions.

    We choose the prior distribution pX = (1/300, 299/300) and transition channels PY = [[1/3, 2/3], [1/300, 299/300]] and PZ = [[2/3, 1/3], [299/300, 1/300]], leaving seven subgoals: checking nonnegativity and normalization for each distribution, and verifying the strict failure of subadditivity.

    lines 9–10

      refine ⟨![1/300, 299/300], ![![1/3, 2/3], ![1/300, 299/300]],
        ![![2/3, 1/3], ![299/300, 1/300]], ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
  2. The chosen distributions and channels are nonnegative and normalize to 1.

    For each distribution (pX, PY, PZ), nonnegativity is checked by enumerating the elements of Fin 2 and evaluating the entries with norm_num. Normalization is verified by expanding the sums over Fin 2 using Fin.sum_univ_two and computing the rational sums.

    lines 11–16

    uses Fin.sum_univ_two

      · intro x; fin_cases x <;> norm_num
      · norm_num [Fin.sum_univ_two]
      · intro x y; fin_cases x <;> fin_cases y <;> norm_num
      · intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num
      · intro x y; fin_cases x <;> fin_cases y <;> norm_num
      · intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num
  3. Sharp rational lower and upper bounds are obtained for ten square roots.

    For the power divergence parameter β = 1/2, evaluating mutual f-information involves square roots x^(1/2). Ten distinct square roots of rational numbers arise. For each root, power_divergence_half_root_bounds establishes rational lower and upper bounds a ≤ x^(1/2) ≤ b by verifying a² ≤ x and x ≤ b² with norm_num.

    lines 17–26

    uses power_divergence_half_root_bounds

      · obtain ⟨l0, u0⟩ := power_divergence_half_root_bounds (100 / 3433) (170672322461 / 1000000000000) (85336161231 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨l1, u1⟩ := power_divergence_half_root_bounds (4000000 / 8923633) (669513202051 / 1000000000000) (167378300513 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨l2, u2⟩ := power_divergence_half_root_bounds (20000 / 29867) (818312521921 / 1000000000000) (409156260961 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨l3, u3⟩ := power_divergence_half_root_bounds (100 / 133) (216777492381 / 250000000000) (34684398781 / 40000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨l4, u4⟩ := power_divergence_half_root_bounds (29900 / 36467) (90549399731 / 100000000000) (905493997311 / 1000000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨l5, u5⟩ := power_divergence_half_root_bounds (29900 / 29867) (40022091867 / 40000000000) (250138074169 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨l6, u6⟩ := power_divergence_half_root_bounds (8940100 / 8923633) (1000922237067 / 1000000000000) (250230559267 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨l7, u7⟩ := power_divergence_half_root_bounds (2000000 / 36467) (7405680632443 / 1000000000000) (1851420158111 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨l8, u8⟩ := power_divergence_half_root_bounds (10000 / 133) (8671099695241 / 1000000000000) (4335549847621 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨l9, u9⟩ := power_divergence_half_root_bounds (1000000 / 3433) (17067232246187 / 1000000000000) (4266808061547 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)
  4. The mutual information inequality expands to a linear inequality in the bounded square roots.

    We unfold the definitions of mutual f-information and the power divergence generator for β = 1/2, expand the product and finite sums with Fintype.sum_prod_type and Fin.sum_univ_two, evaluate matrix indexing via Matrix.cons_val_zero and Matrix.cons_val_one, and normalize all rational coefficients in the bounds and goal using norm_num.

    lines 27–29

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

        simp only [mutual_f_information, power_divergence_generator, Fintype.sum_prod_type,
          Fin.sum_univ_two, Fin.isValue, Matrix.cons_val_zero, Matrix.cons_val_one]
        norm_num at l0 u0 l1 u1 l2 u2 l3 u3 l4 u4 l5 u5 l6 u6 l7 u7 l8 u8 l9 u9 ⊢
  5. Subadditivity fails: the mutual information with the pair strictly exceeds the sum of the individual mutual informations.

    Linear arithmetic (linarith) combines the rational lower and upper bounds on the ten square roots with the normalized linear expression to conclude that I_{f_{1/2}}(X; Y) + I_{f_{1/2}}(X; Z) < I_{f_{1/2}}(X; YZ).

    line 30

        linarith
Fin.sum_univ_two
The sum of a function over a two-element type Fin 2 equals f 0 + f 1.
Fintype.sum_prod_type
The sum over a product type α₁ × α₂ is equal to the double sum over α₁ and α₂.
Matrix.cons_val_zero
The 0-th element of a vector constructed with Matrix.vecCons is the prepended head element.
Matrix.cons_val_one
The 1-st element of a vector constructed with Matrix.vecCons is the head of the remaining tail vector.
power_divergence_half_root_bounds
If 0 ≤ x, 0 ≤ b, a² ≤ x, and x ≤ b², then a ≤ x^(1/2) ≤ b.

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

theorem mutual_hellinger_information_not_subadditive :    ∃ (pX : Fin 2 → ℝ) (PY PZ : Fin 2 → Fin 2 → ℝ),      (∀ x, 0 ≤ pX x) ∧ ∑ x, pX x = 1 ∧ (∀ x y, 0 ≤ PY x y) ∧ (∀ x, ∑ y, PY x y = 1) ∧      (∀ x z, 0 ≤ PZ x z) ∧ (∀ x, ∑ z, PZ x z = 1) ∧      mutual_f_information (power_divergence_generator (1 / 2)) (fun x y => pX x * PY x y) +          mutual_f_information (power_divergence_generator (1 / 2)) (fun x z => pX x * PZ x z) <        mutual_f_information (power_divergence_generator (1 / 2))          (fun x (yz : Fin 2 × Fin 2) => pX x * PY x yz.1 * PZ x yz.2) := by  refine ⟨![1/300, 299/300], ![![1/3, 2/3], ![1/300, 299/300]],    ![![2/3, 1/3], ![299/300, 1/300]], ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩  · intro x; fin_cases x <;> norm_num  · norm_num [Fin.sum_univ_two]  · intro x y; fin_cases x <;> fin_cases y <;> norm_num  · intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num  · intro x y; fin_cases x <;> fin_cases y <;> norm_num  · intro x; fin_cases x <;> simp [Fin.sum_univ_two] <;> norm_num  · obtain ⟨l0, u0⟩ := power_divergence_half_root_bounds (100 / 3433) (170672322461 / 1000000000000) (85336161231 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨l1, u1⟩ := power_divergence_half_root_bounds (4000000 / 8923633) (669513202051 / 1000000000000) (167378300513 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨l2, u2⟩ := power_divergence_half_root_bounds (20000 / 29867) (818312521921 / 1000000000000) (409156260961 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨l3, u3⟩ := power_divergence_half_root_bounds (100 / 133) (216777492381 / 250000000000) (34684398781 / 40000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨l4, u4⟩ := power_divergence_half_root_bounds (29900 / 36467) (90549399731 / 100000000000) (905493997311 / 1000000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨l5, u5⟩ := power_divergence_half_root_bounds (29900 / 29867) (40022091867 / 40000000000) (250138074169 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨l6, u6⟩ := power_divergence_half_root_bounds (8940100 / 8923633) (1000922237067 / 1000000000000) (250230559267 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨l7, u7⟩ := power_divergence_half_root_bounds (2000000 / 36467) (7405680632443 / 1000000000000) (1851420158111 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨l8, u8⟩ := power_divergence_half_root_bounds (10000 / 133) (8671099695241 / 1000000000000) (4335549847621 / 500000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨l9, u9⟩ := power_divergence_half_root_bounds (1000000 / 3433) (17067232246187 / 1000000000000) (4266808061547 / 250000000000) (by norm_num) (by norm_num) (by norm_num) (by norm_num)    simp only [mutual_f_information, power_divergence_generator, Fintype.sum_prod_type,      Fin.sum_univ_two, Fin.isValue, Matrix.cons_val_zero, Matrix.cons_val_one]    norm_num at l0 u0 l1 u1 l2 u2 l3 u3 l4 u4 l5 u5 l6 u6 l7 u7 l8 u8 l9 u9 ⊢    linarith
See it in the graphDiscuss this resultChallenge it