mutual_power_divergence_binary_subadditive_imp_golden_ratio_le
For any positive exponent beta, if the mutual power-divergence information with generator f_beta satisfies subadditivity for all binary Markov chains Y <- X -> Z, then beta >= (Real.sqrt 5 - 1) / 2.
Statement
theorem mutual_power_divergence_binary_subadditive_imp_golden_ratio_le (β : ℝ) (hβ0 : 0 < β) (hsub : ∀ (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 β) (fun x (yz : Fin 2 × Fin 2) => pX x * PY x yz.1 * PZ x yz.2) ≤ mutual_f_information (power_divergence_generator β) (fun x y => pX x * PY x y) + mutual_f_information (power_divergence_generator β) (fun x z => pX x * PZ x z)) : (Real.sqrt 5 - 1) / 2 ≤ β
- Related work
- arXiv:2610.21231 'On the Subadditivity of Mutual f-Information'
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- power_divergence_exists_binary_counterexample_of_lt_golden_ratioFor every exponent beta in (0, (sqrt 5 - 1)/2), there exist strictly positive binary probability mass functions pX, PY, PZ forming a…
- 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…
- 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}…
- Used by 1
- mutual_power_divergence_subadditive_imp_golden_ratio_leFor any positive exponent beta, if the mutual power-divergence information with generator f_beta is subadditive under all finite Markov…
Read back from the Lean
For any real number $\beta > 0$, if for every probability distribution $p_X$ on $\text{Fin } 2$ (i.e., $p_X(x) \ge 0$ for all $x$ and $\sum_{x} p_X(x) = 1$) and every pair of transition probability matrices $P_Y, P_Z : \text{Fin } 2 \to \text{Fin } 2 \to \mathbb{R}$ (i.e., $P_Y(x, y) \ge 0$ with $\sum_y P_Y(x, y) = 1$ for all $x$, and $P_Z(x, z) \ge 0$ with $\sum_z P_Z(x, z) = 1$ for all $x$), the mutual $f$-information with respect to the $\beta$-power divergence generator satisfies the subadditivity inequality $$I_{f_\beta}(X; (Y, Z)) \le I_{f_\beta}(X; Y) + I_{f_\beta}(X; Z)$$ for the conditionally independent joint distributions: - on $\text{Fin } 2 \times (\text{Fin } 2 \times \text{Fin } 2)$ given by $(x, (y, z)) \mapsto p_X(x) P_Y(x, y) P_Z(x, z)$, - on $\text{Fin } 2 \times \text{Fin } 2$ given by $(x, y) \mapsto p_X(x) P_Y(x, y)$, and - on $\text{Fin } 2 \times \text{Fin } 2$ given by $(x, z) \mapsto p_X(x) P_Z(x, z)$, then $\frac{\sqrt{5} - 1}{2} \le \beta$.
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 theorem is proved by contradiction. If β is strictly less than the golden ratio conjugate (√5 - 1) / 2, an existing counterexample theorem provides a binary Markov chain whose mutual power-divergence information strictly violates subadditivity. However, evaluating the assumed universal subadditivity hypothesis on this valid Markov chain yields the reverse inequality, which is an immediate contradiction.
Assume for contradiction that β < (√5 - 1) / 2.
We proceed by contradiction by assuming the negation of the desired inequality (√5 - 1) / 2 ≤ β.
by_contra hThere exists a binary Markov chain that strictly violates subadditivity for the given β.
Since ¬((√5 - 1) / 2 ≤ β) means β < (√5 - 1) / 2 by not_le.mp, the counterexample theorem power_divergence_exists_binary_counterexample_of_lt_golden_ratio provides prior probabilities pX and transition matrices PY, PZ on a binary alphabet with strictly positive entries summing to 1 such that If(X; Y) + If(X; Z) < If(X; Y, Z).
uses
power_divergence_exists_binary_counterexample_of_lt_golden_ratio,not_le.mpobtain ⟨pX, PY, PZ, hpXpos, hpXsum, hPYpos, hPYsum, hPZpos, hPZsum, hlt⟩ := power_divergence_exists_binary_counterexample_of_lt_golden_ratio β hβ0 (not_le.mp h)The universal subadditivity hypothesis implies If(X; Y, Z) ≤ If(X; Y) + If(X; Z) for this Markov chain.
Because the probabilities and transition probabilities of the counterexample are strictly positive, they are in particular non-negative (via le_of_lt). Along with their row sums being 1, they satisfy all the preconditions of the assumed subadditivity property hsub, which therefore asserts that If(X; Y, Z) ≤ If(X; Y) + If(X; Z).
uses
le_of_lthave hpXnonneg : ∀ x, 0 ≤ pX x := fun x => le_of_lt (hpXpos x) have hPYnonneg : ∀ x y, 0 ≤ PY x y := fun x y => le_of_lt (hPYpos x y) have hPZnonneg : ∀ x z, 0 ≤ PZ x z := fun x z => le_of_lt (hPZpos x z) have hle := hsub pX PY PZ hpXnonneg hpXsum hPYnonneg hPYsum hPZnonneg hPZsum
The two inequalities contradict each other. automation
The strict inequality If(X; Y) + If(X; Z) < If(X; Y, Z) from the counterexample contradicts the non-strict subadditivity bound If(X; Y, Z) ≤ If(X; Y) + If(X; Z). Linear arithmetic detects this contradiction and closes the proof.
linarith
power_divergence_exists_binary_counterexample_of_lt_golden_ratio- For any exponent β with 0 < β < (√5 - 1) / 2, there exists a binary Markov chain (given by strictly positive probability distributions pX, PY, PZ summing to 1) for which the mutual power-divergence information strictly violates subadditivity.
not_le.mp- In a linear order, if a ≤ b is false, then b < a.
le_of_lt- In a preorder, a strict inequality a < b implies the non-strict inequality a ≤ 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
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.
/-- Subadditivity of mutual power-divergence information on binary alphabets implies beta >= (sqrt 5 - 1) / 2. -/theorem mutual_power_divergence_binary_subadditive_imp_golden_ratio_le (β : ℝ) (hβ0 : 0 < β) (hsub : ∀ (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 β) (fun x (yz : Fin 2 × Fin 2) => pX x * PY x yz.1 * PZ x yz.2) ≤ mutual_f_information (power_divergence_generator β) (fun x y => pX x * PY x y) + mutual_f_information (power_divergence_generator β) (fun x z => pX x * PZ x z)) : (Real.sqrt 5 - 1) / 2 ≤ β := by by_contra h obtain ⟨pX, PY, PZ, hpXpos, hpXsum, hPYpos, hPYsum, hPZpos, hPZsum, hlt⟩ := power_divergence_exists_binary_counterexample_of_lt_golden_ratio β hβ0 (not_le.mp h) have hpXnonneg : ∀ x, 0 ≤ pX x := fun x => le_of_lt (hpXpos x) have hPYnonneg : ∀ x y, 0 ≤ PY x y := fun x y => le_of_lt (hPYpos x y) have hPZnonneg : ∀ x z, 0 ≤ PZ x z := fun x z => le_of_lt (hPZpos x z) have hle := hsub pX PY PZ hpXnonneg hpXsum hPYnonneg hPYsum hPZnonneg hPZsum linarith