mutual_power_divergence_information_not_subadditive_quarter
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).
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.
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]], ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
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.
uses
Fin.sum_univ_three· intro x; norm_num · norm_num [Fin.sum_univ_three]
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.
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
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.
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
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).
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)
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.
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_conssimp 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.
- The strict inequality I(X; Y) + I(X; Z) < I(X; YZ) is verified without transcendental function evaluation: linarith treats the fourth-root terms as formal variables and checks that the system of linear inequalities defined by the upper and lower bounds in lines 17–22 implies the strict inequality.
- The hypotheses for power_divergence_quarter_root_bounds (the fourth-power bounds such as 1.2446^4 ≤ 12/5 ≤ 1.2447^4) are discharged purely by exact rational arithmetic inside norm_num.
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.
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