AFTD Auto-Formalizing Theoretical Domains

mutual_power_divergence_information_not_subadditive_quarter

theoremverifiedoriginal

Subadditivity fails for the power divergence with β = 1/4: there are random variables X, Y, Z on three-element alphabets with Y ← X → Z (p_{XYZ} = p_X p_{Y|X} p_{Z|X}) and Ĩ_{f_{1/4}}(X; YZ) > Ĩ_{f_{1/4}}(X; Y) + Ĩ_{f_{1/4}}(X; Z). Instance: X uniform on Z/3, P(Y = x + 1 | x) = 4/5 and P(Z = −x | x) = 4/5, the other values 1/10.

Statement

theorem mutual_power_divergence_information_not_subadditive_quarter :
    ∃ (pX : Fin 3 → ℝ) (PY PZ : Fin 3 → Fin 3 → ℝ),
      (∀ 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 / 4)) (fun x y => pX x * PY x y) +
          mutual_f_information (power_divergence_generator (1 / 4)) (fun x z => pX x * PZ x z) <
        mutual_f_information (power_divergence_generator (1 / 4))
          (fun x (yz : Fin 3 × Fin 3) => 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; the paper does not discuss the power divergences with β ∈ (0, 1). Answered in the negative at β = 1/4.
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_quarter_root_boundsFor x ≥ 0 and b ≥ 0, if a^4 ≤ x ≤ b^4 then a ≤ x^(1/4) ≤ b.

The proof, explained

Subadditivity of the power divergence mutual information fails for β = 1/4 on a three-element alphabet. The counterexample sets X uniform on Z/3 and defines conditionally independent Y and Z given X with P(Y = x + 1 | x) = 4/5 and P(Z = −x | x) = 4/5 (with remaining entries 1/10). Expanding the mutual information expressions reduces the problem to an inequality between linear combinations of fourth roots of density ratios (such as (12/5)^(1/4) and (32/11)^(1/4)). Rigorous two-sided bounds on these fourth roots, verified via exact fourth powers of rationals, allow linear arithmetic (linarith) to establish the strict inequality I(X; Y) + I(X; Z) < I(X; YZ).

  1. Specify the counterexample distributions: X is uniform on Fin 3, and Y and Z are given by explicit 3 × 3 transition matrices.

    We supply explicit witnesses using refine: pX(x) = 1/3 for each x ∈ Fin 3, the transition matrix PY with rows [1/10, 4/5, 1/10], [1/10, 1/10, 4/5], and [4/5, 1/10, 1/10] (representing P(Y = x + 1 | x) = 4/5), and PZ with rows [4/5, 1/10, 1/10], [1/10, 1/10, 4/5], and [1/10, 4/5, 1/10] (representing P(Z = -x | x) = 4/5). This leaves seven subgoals: six verifying the probability axioms and one establishing the failure of subadditivity.

    lines 9–10

      refine ⟨fun _ => 1 / 3, ![![1/10, 4/5, 1/10], ![1/10, 1/10, 4/5], ![4/5, 1/10, 1/10]],
        ![![4/5, 1/10, 1/10], ![1/10, 1/10, 4/5], ![1/10, 4/5, 1/10]], ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
  2. pX is a valid probability distribution on Fin 3.

    Nonnegativity 0 ≤ 1/3 holds by arithmetic. Expanding the sum over Fin 3 using Fin.sum_univ_three reduces the normalization condition to 1/3 + 1/3 + 1/3 = 1, verified by norm_num.

    lines 11–12

    uses Fin.sum_univ_three

      · intro x; norm_num
      · norm_num [Fin.sum_univ_three]
  3. PY is a valid Markov transition kernel.

    Exhaustive case analysis on x, y ∈ Fin 3 via fin_cases checks that all nine matrix entries are nonnegative (each is 1/10 or 4/5). Expanding each row sum using Fin.sum_univ_three confirms that every row sums to 1/10 + 4/5 + 1/10 = 1.

    lines 13–14

    uses Fin.sum_univ_three

      · intro x y; fin_cases x <;> fin_cases y <;> norm_num
      · intro x; fin_cases x <;> simp [Fin.sum_univ_three] <;> norm_num
  4. PZ is a valid Markov transition kernel.

    Similarly, case analysis on x, z ∈ Fin 3 via fin_cases checks that all nine matrix entries are nonnegative, and expanding each row sum with Fin.sum_univ_three verifies that every row sums to 4/5 + 1/10 + 1/10 = 1.

    lines 15–16

    uses Fin.sum_univ_three

      · intro x y; fin_cases x <;> fin_cases y <;> norm_num
      · intro x; fin_cases x <;> simp [Fin.sum_univ_three] <;> norm_num
  5. Rigorous decimal lower and upper bounds on the fourth roots of the density ratios that appear in the mutual information sums.

    Applying power_divergence_quarter_root_bounds with fourth-power inequalities verified by norm_num, we obtain lower bounds (12/5)^(1/4) ≥ 1.2446 (a1) and (3/10)^(1/4) ≥ 0.7400 (a2), and upper bounds (32/11)^(1/4) ≤ 1.3060 (b1), (1/22)^(1/4) ≤ 0.4618 (b2), (24/17)^(1/4) ≤ 1.0901 (b3), and (3/17)^(1/4) ≤ 0.6482 (b4).

    lines 17–22

    uses power_divergence_quarter_root_bounds

      · obtain ⟨a1, -⟩ := power_divergence_quarter_root_bounds (12 / 5) 1.2446 1.2447 (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨a2, -⟩ := power_divergence_quarter_root_bounds (3 / 10) 0.7400 0.7401 (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨-, b1⟩ := power_divergence_quarter_root_bounds (32 / 11) 1.3059 1.3060 (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨-, b2⟩ := power_divergence_quarter_root_bounds (1 / 22) 0.4617 0.4618 (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨-, b3⟩ := power_divergence_quarter_root_bounds (24 / 17) 1.0900 1.0901 (by norm_num) (by norm_num) (by norm_num) (by norm_num)
        obtain ⟨-, b4⟩ := power_divergence_quarter_root_bounds (3 / 17) 0.6481 0.6482 (by norm_num) (by norm_num) (by norm_num) (by norm_num)
  6. The mutual power divergence information satisfies I(X; Y) + I(X; Z) < I(X; YZ), completing the counterexample. automation

    We unfold the definitions of mutual_f_information and the power divergence generator for β = 1/4. We convert the joint sum over YZ into iterated sums via Fintype.sum_prod_type, expand all finite sums over Fin 3 using Fin.sum_univ_three, and evaluate all matrix lookups using the Matrix indexing lemmas. After norm_num evaluates all rational arithmetic, the goal becomes a linear inequality in the fourth-root terms. Because the leading coefficient of u^(1/4) in the generator is negative (-16/3), the lower bounds a1 and a2 yield upper bounds for the left-hand side, while the upper bounds b1–b4 yield lower bounds for the right-hand side. Finally, linarith combines these inequalities to close the strict inequality.

    lines 23–27

    uses Fintype.sum_prod_type, Fin.sum_univ_three, Matrix.cons_val_zero, Matrix.cons_val_one, Matrix.cons_val_two, Matrix.head_cons, Matrix.tail_cons

        simp only [mutual_f_information, power_divergence_generator, Fintype.sum_prod_type,
          Fin.sum_univ_three, Fin.isValue, Matrix.cons_val_zero, Matrix.cons_val_one,
          Matrix.cons_val_two, Matrix.head_cons, Matrix.tail_cons]
        norm_num at a1 a2 b1 b2 b3 b4 ⊢
        linarith
Fin.sum_univ_three
A sum of a function over the three-element type Fin 3 equals the sum of its values at 0, 1, and 2: ∑ i, f i = f 0 + f 1 + f 2.
Fintype.sum_prod_type
A sum over a Cartesian product of two finite types decomposes as an iterated sum over each component: ∑ x, f x = ∑ x, ∑ y, f (x, y).
Matrix.cons_val_zero
The entry at index 0 of a vector formed by prepending x to u is x.
Matrix.cons_val_one
The entry at index 1 of a vector formed by prepending x to u is the 0-th entry of u.
Matrix.cons_val_two
The entry at index 2 of a vector formed by prepending x to u is the head of the tail of u.
Matrix.head_cons
The head of a vector formed by prepending x to u is x.
Matrix.tail_cons
The tail of a vector formed by prepending x to u is u.
power_divergence_quarter_root_bounds
For non-negative real numbers x and b, if a^4 ≤ x ≤ b^4, then a ≤ x^(1/4) ≤ 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_power_divergence_information_not_subadditive_quarter :    ∃ (pX : Fin 3 → ℝ) (PY PZ : Fin 3 → Fin 3 → ℝ),      (∀ 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 / 4)) (fun x y => pX x * PY x y) +          mutual_f_information (power_divergence_generator (1 / 4)) (fun x z => pX x * PZ x z) <        mutual_f_information (power_divergence_generator (1 / 4))          (fun x (yz : Fin 3 × Fin 3) => pX x * PY x yz.1 * PZ x yz.2) := by  refine ⟨fun _ => 1 / 3, ![![1/10, 4/5, 1/10], ![1/10, 1/10, 4/5], ![4/5, 1/10, 1/10]],    ![![4/5, 1/10, 1/10], ![1/10, 1/10, 4/5], ![1/10, 4/5, 1/10]], ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩  · intro x; norm_num  · norm_num [Fin.sum_univ_three]  · intro x y; fin_cases x <;> fin_cases y <;> norm_num  · intro x; fin_cases x <;> simp [Fin.sum_univ_three] <;> norm_num  · intro x y; fin_cases x <;> fin_cases y <;> norm_num  · intro x; fin_cases x <;> simp [Fin.sum_univ_three] <;> norm_num  · obtain ⟨a1, -⟩ := power_divergence_quarter_root_bounds (12 / 5) 1.2446 1.2447 (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨a2, -⟩ := power_divergence_quarter_root_bounds (3 / 10) 0.7400 0.7401 (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨-, b1⟩ := power_divergence_quarter_root_bounds (32 / 11) 1.3059 1.3060 (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨-, b2⟩ := power_divergence_quarter_root_bounds (1 / 22) 0.4617 0.4618 (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨-, b3⟩ := power_divergence_quarter_root_bounds (24 / 17) 1.0900 1.0901 (by norm_num) (by norm_num) (by norm_num) (by norm_num)    obtain ⟨-, b4⟩ := power_divergence_quarter_root_bounds (3 / 17) 0.6481 0.6482 (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_three, Fin.isValue, Matrix.cons_val_zero, Matrix.cons_val_one,      Matrix.cons_val_two, Matrix.head_cons, Matrix.tail_cons]    norm_num at a1 a2 b1 b2 b3 b4 ⊢    linarith
See it in the graphDiscuss this resultChallenge it