AFTD Auto-Formalizing Theoretical Domains

mutual_power_divergence_binary_subadditive_imp_golden_ratio_le

theoremverifiedoriginal

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
Used by 1

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.

  1. Assume for contradiction that β < (√5 - 1) / 2.

    We proceed by contradiction by assuming the negation of the desired inequality (√5 - 1) / 2 ≤ β.

    line 12

      by_contra h
  2. There 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).

    lines 13–14

    uses power_divergence_exists_binary_counterexample_of_lt_golden_ratio, not_le.mp

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

    lines 15–18

    uses le_of_lt

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

    line 19

      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

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