AFTD Auto-Formalizing Theoretical Domains

mutual_power_divergence_not_subadditive_of_lt_golden_ratio

theoremverifiedformalization

For every exponent beta in (0, (sqrt 5 - 1)/2), the mutual power-divergence information with generator f_beta fails to be subadditive under Markov chains Y <- X -> Z.

Statement

theorem mutual_power_divergence_not_subadditive_of_lt_golden_ratio (β : ℝ)
    (hβ0 : 0 < β) (hβ : β < (Real.sqrt 5 - 1) / 2) :
    ¬ mutual_f_information_subadditive (power_divergence_generator β)
Formalizes
arXiv:2610.21231, On the Subadditivity of Mutual f-Information; Open Problem OP-726
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_information_subadditiveA function f is a subadditive generator for mutual f-information if for all finite random variables X, Y, Z forming a Markov chain Y -> X…
  • 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…
  • 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}…

Read back from the Lean

For any real number β such that 0 < β and β < (Real.sqrt 5 - 1) / 2, the mutual f-information subadditivity property fails for the function f = power_divergence_generator β. That is, it is not the case that for all types X, Y, Z with Fintype instances, and all functions pX : X → ℝ, PY : X → Y → ℝ, and PZ : X → Z → ℝ satisfying: 1. ∀ x, 0 ≤ pX x, 2. ∑ x, pX x = 1, 3. ∀ x y, 0 ≤ PY x y, 4. ∀ x, ∑ y, PY x y = 1, 5. ∀ x z, 0 ≤ PZ x z, 6. ∀ x, ∑ z, PZ x z = 1, the mutual f-information of the joint distribution on X × (Y × Z) given by (x, yz) ↦ pX x * PY x yz.1 * PZ x yz.2 is less than or equal to the mutual f-information of (x, y) ↦ pX x * PY x y plus the mutual f-information of (x, z) ↦ pX x * PZ x z.

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. Assuming that mutual power-divergence information with parameter β is subadditive, an auxiliary lemma supplies an explicit binary counterexample—a Markov chain Y ← X → Z on two-element alphabets—where the joint mutual information strictly exceeds the sum of the marginals. Applying the subadditivity hypothesis to this counterexample produces the opposite inequality, yielding an immediate contradiction.

  1. Assume for contradiction that mutual power-divergence information is subadditive.

    Assume the subadditivity hypothesis `hsub` for the power-divergence generator with parameter β, which reduces the goal to deriving False.

    line 5

      intro hsub
  2. There exists a binary Markov chain that strictly violates subadditivity.

    Using the assumptions 0 < β and β < (√5 - 1)/2, lemma `power_divergence_exists_binary_counterexample_of_lt_golden_ratio` supplies a strictly positive probability distribution pX on Fin 2 and strictly positive transition matrices PY and PZ from Fin 2 to Fin 2 (each row summing to 1) for which the sum of the marginal mutual informations is strictly smaller than the joint mutual information: I(X; Y) + I(X; Z) < I(X; (Y, Z)).

    lines 6–7

    uses power_divergence_exists_binary_counterexample_of_lt_golden_ratio

      rcases power_divergence_exists_binary_counterexample_of_lt_golden_ratio β hβ0 hβ with
        ⟨pX, PY, PZ, hpX_pos, hpX_sum, hPY_pos, hPY_sum, hPZ_pos, hPZ_sum, hlt⟩
  3. Under the subadditivity hypothesis, the joint mutual information is bounded above by the sum of marginal mutual informations.

    Because pX, PY, and PZ are strictly positive pointwise, they are non-negative. Specializing the assumed subadditivity `hsub` to the two-element alphabet Fin 2 with distribution pX and kernels PY and PZ yields I(X; (Y, Z)) ≤ I(X; Y) + I(X; Z).

    lines 8–11

      have hpX_nonneg : ∀ x, 0 ≤ pX x := fun x => (hpX_pos x).le
      have hPY_nonneg : ∀ x y, 0 ≤ PY x y := fun x y => (hPY_pos x y).le
      have hPZ_nonneg : ∀ x z, 0 ≤ PZ x z := fun x z => (hPZ_pos x z).le
      have hle := hsub (Fin 2) (Fin 2) (Fin 2) pX PY PZ hpX_nonneg hpX_sum hPY_nonneg hPY_sum hPZ_nonneg hPZ_sum
  4. Contradiction.

    Linear arithmetic (`linarith`) detects the contradiction between the strict inequality I(X; Y) + I(X; Z) < I(X; (Y, Z)) from the counterexample and the weak inequality I(X; (Y, Z)) ≤ I(X; Y) + I(X; Z) from subadditivity.

    line 12

      linarith
power_divergence_exists_binary_counterexample_of_lt_golden_ratio
For any exponent β with 0 < β < (√5 - 1)/2, there exist a strictly positive probability distribution on Fin 2 and strictly positive row-stochastic transition kernels on Fin 2 such that the sum of the marginal mutual power-divergence informations is strictly less than the joint mutual power-divergence information.

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 fails for mutual power-divergence information for any beta < (sqrt 5 - 1) / 2. -/theorem mutual_power_divergence_not_subadditive_of_lt_golden_ratio (β : ℝ)    (hβ0 : 0 < β) (hβ : β < (Real.sqrt 5 - 1) / 2) :    ¬ mutual_f_information_subadditive (power_divergence_generator β) := by  intro hsub  rcases power_divergence_exists_binary_counterexample_of_lt_golden_ratio β hβ0 hβ with    ⟨pX, PY, PZ, hpX_pos, hpX_sum, hPY_pos, hPY_sum, hPZ_pos, hPZ_sum, hlt⟩  have hpX_nonneg : ∀ x, 0 ≤ pX x := fun x => (hpX_pos x).le  have hPY_nonneg : ∀ x y, 0 ≤ PY x y := fun x y => (hPY_pos x y).le  have hPZ_nonneg : ∀ x z, 0 ≤ PZ x z := fun x z => (hPZ_pos x z).le  have hle := hsub (Fin 2) (Fin 2) (Fin 2) pX PY PZ hpX_nonneg hpX_sum hPY_nonneg hPY_sum hPZ_nonneg hPZ_sum  linarith
See it in the graphDiscuss this resultChallenge it