AFTD Auto-Formalizing Theoretical Domains

mutual_f_information_subadditive_full_support_of_weight_bound

theoremverifiedformalization

Theorem 1 of arXiv:2610.21231, on full-support distributions. Let f with f(1) = 0 be convex and four times continuously differentiable on (0, ∞), and g(x) = x² f''(x). If g''(x) < 0 for all x > 0 and there are constants η > 0 and ℓ with g(x) + 2(g'(x) - η)²/(-g''(x)) ≤ 2η + (x - 1)ℓ for all x > 0, then Ĩ_f(X; YZ) ≤ Ĩ_f(X; Y) + Ĩ_f(X; Z) for every full-support Markov chain Y → X → Z on finite sets.

Statement

theorem mutual_f_information_subadditive_full_support_of_weight_bound (f : ℝ → ℝ)
    (hf1 : f 1 = 0) (hconv : ConvexOn ℝ (Set.Ioi 0) f)
    (hsmooth : ContDiffOn ℝ 4 f (Set.Ioi 0))
    (hg2 : ∀ x > 0, deriv (deriv (subadditive_f_weight f)) x < 0)
    (hbound : ∃ η ℓ : ℝ, 0 < η ∧ ∀ x > 0,
      subadditive_f_weight f x + 2 * (deriv (subadditive_f_weight f) x - η) ^ 2 /
        (-deriv (deriv (subadditive_f_weight f)) x) ≤ 2 * η + (x - 1) * ℓ) :
    mutual_f_information_subadditive_full_support f
Formalizes
arXiv:2610.21231 (On the subadditivity of mutual f-information), Theorem 1. Differs: the conclusion is for full-support distributions (the case the proof in Appendix B reduces to), and f is only constrained on (0, ∞) (the paper also asks continuity of f on [0, ∞), which full-support distributions never use).
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • subadditive_f_weightThe weight g(x) = x² f''(x) attached to a generator f in Theorem 1 of arXiv:2610.21231 (f'' is the iterated derivative deriv (deriv f)).
  • mutual_f_information_subadditive_full_supportSubadditivity of mutual f-information on full-support distributions: for all finite X, Y, Z, every p_X > 0 and channels p_{Y|X} > 0,…
  • mutual_f_thetaThe function Θ_{p_X,p_{Y|X}}(r_X) of eq. (14)/(19) of arXiv:2610.21231: Σ_y r_Y(y) D_f(r_{X|y} ‖ p_X) - D_f(r_X ‖ p_X), with r_{YX} = r_X…
  • mutual_f_theta_concaveOn_of_weight_boundLemma 4 of arXiv:2610.21231: under the assumptions of Theorem 1 (g = x² f'' with g'' < 0 and g + 2(g' - η)²/(-g'') ≤ 2η + (x-1)ℓ), for…
  • 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}…
  • mutual_f_theta_selfΘ_{p_X,p_{Y|X}}(p_X) = Ĩ_f(X;Y) when f(1) = 0 (step (17)-(18) of the proof of Theorem 1 of arXiv:2610.21231).
  • mutual_f_information_markov_sub_eq_sum_thetaFor a full-support Markov chain Y → X → Z, Ĩ_f(X;YZ) - Ĩ_f(X;Z) = Σ_z p_Z(z) Θ_{p_X,p_{Y|X}}(p_{X|Z=z}) (eq. (13) of arXiv:2610.21231).
Used by 1

The proof, explained

The proof establishes the subadditivity of mutual $f$-information along the Markov chain $Y \to X \to Z$ by rewriting it as $\tilde{I}_f(X; YZ) - \tilde{I}_f(X; Z) \le \tilde{I}_f(X; Y)$. A conditioning identity decomposes the difference into an expectation over $z$ of an auxiliary functional $\theta_f$ evaluated at the posterior distributions $r_z$. Under the differential inequality hypothesis on $f$, $\theta_f$ is concave, so Jensen's inequality bounds this average above by $\theta_f$ at the mixture $\sum_z p_Z(z) r_z = p_X$, which is precisely $\tilde{I}_f(X; Y)$.

  1. Decompose the difference $\tilde{I}_f(X; YZ) - \tilde{I}_f(X; Z)$ as the average of the functional $\theta_f$ over posterior distributions, and establish that $\theta_f$ is concave.

    We introduce the finite sets $X, Y, Z$, the prior distribution $p_X$, and the transition kernels $P_Y, P_Z$, all assumed strictly positive and normalized. Lemma `mutual_f_information_markov_sub_eq_sum_theta` writes $\tilde{I}_f(X; YZ) - \tilde{I}_f(X; Z)$ as $\sum_z p_Z(z) \theta_f(r_z)$, where $p_Z(z) = \sum_x p_X(x) P_Z(x, z)$ and $r_z(x) = p_X(x) P_Z(x, z) / p_Z(z)$. Under the differential weight bound on $f$, lemma `mutual_f_theta_concaveOn_of_weight_bound` shows that $\theta_f$ is concave on the simplex of strictly positive distributions on $X$.

    lines 9–12

    uses mutual_f_information_markov_sub_eq_sum_theta, mutual_f_theta_concaveOn_of_weight_bound

      intro X Y Z _ _ _ pX PY PZ hpX hsX hPY hsY hPZ hsZ
      have hdec := mutual_f_information_markov_sub_eq_sum_theta f pX PY PZ hpX hsX hPY hsY hPZ hsZ
      have hcc := mutual_f_theta_concaveOn_of_weight_bound f hf1 hconv hsmooth hg2 hbound
        pX PY hpX hsX hPY hsY
  2. The set $X$ is nonempty. automation

    Suppose, for contradiction, that $X$ were empty (`not_nonempty_iff`). Then the sum $\sum_{x \in X} p_X(x)$ would be empty and therefore equal to $0$, contradicting the assumption $\sum_x p_X(x) = 1$. Simplification closes the resulting contradiction $0 = 1$.

    lines 13–16

    uses not_nonempty_iff

      have hX : Nonempty X := by
        by_contra h
        rw [not_nonempty_iff] at h
        simp at hsX
  3. The marginal distribution $p_Z(z) = \sum_x p_X(x) P_Z(x, z)$ is strictly positive for every $z$ and sums to $1$.

    Each term $p_X(x) P_Z(x, z)$ is strictly positive by `mul_pos`, and since $X$ is nonempty, the sum defining $p_Z(z)$ is strictly positive by `Finset.sum_pos`. Swapping the order of summation (`Finset.sum_comm`) and using $\sum_z P_Z(x, z) = 1$ and $\sum_x p_X(x) = 1$ via `Finset.mul_sum` and `mul_one` shows that $\sum_z p_Z(z) = 1$.

    lines 17–23

    uses Finset.sum_pos, mul_pos, Classical.arbitrary, Finset.mem_univ, Finset.sum_comm, Finset.mul_sum, mul_one

      set pZ : Z → ℝ := fun z => ∑ x, pX x * PZ x z with hpZ
      have hpZpos : ∀ z, 0 < pZ z := fun z =>
        Finset.sum_pos (fun x _ => mul_pos (hpX x) (hPZ x z)) ⟨Classical.arbitrary X, Finset.mem_univ _⟩
      have hsZ1 : ∑ z, pZ z = 1 := by
        simp only [hpZ]
        rw [Finset.sum_comm]
        simp only [← Finset.mul_sum, hsZ, mul_one, hsX]
  4. For every $z \in Z$, the posterior distribution $r_z(x) = p_X(x) P_Z(x, z) / p_Z(z)$ is strictly positive and sums to $1$ over $x$.

    For each $z$, $r_z(x) > 0$ for all $x$ because both the numerator and denominator are positive (`div_pos`, `mul_pos`). Factoring out the denominator with `Finset.sum_div`, the sum $\sum_x r_z(x)$ evaluates to $(\sum_x p_X(x) P_Z(x, z)) / p_Z(z) = p_Z(z) / p_Z(z) = 1$ by `div_self`.

    lines 24–30

    uses div_pos, mul_pos, Finset.sum_div, div_self

      set rz : Z → X → ℝ := fun z x => pX x * PZ x z / pZ z with hrz
      have hmem : ∀ z ∈ (Finset.univ : Finset Z),
          rz z ∈ {r : X → ℝ | (∀ x, 0 < r x) ∧ ∑ x, r x = 1} := by
        intro z _
        refine ⟨fun x => div_pos (mul_pos (hpX x) (hPZ x z)) (hpZpos z), ?_⟩
        simp only [hrz, ← Finset.sum_div]
        exact div_self (hpZpos z).ne'
  5. By Jensen's inequality, $\sum_z p_Z(z) \theta_f(r_z) \le \theta_f\left(\sum_z p_Z(z) r_z\right)$.

    Because $\theta_f$ is concave on the simplex of strictly positive probability distributions, $p_Z$ is a non-negative probability vector summing to $1$, and each $r_z$ belongs to that simplex, Jensen's inequality for concave functions (`ConcaveOn.le_map_sum`, invoked via `hcc.le_map_sum`) bounds the weighted average of function values by the function value at the convex combination.

    lines 31–32

      have hj := hcc.le_map_sum (t := Finset.univ) (w := pZ) (p := rz)
        (fun z _ => (hpZpos z).le) hsZ1 hmem
  6. The mixture of posteriors recovers the prior: $\sum_z p_Z(z) r_z = p_X$.

    Evaluating at each $x \in X$, the sum is $\sum_z p_Z(z) \cdot \frac{p_X(x) P_Z(x, z)}{p_Z(z)}$. Cancelling $p_Z(z)$ (`mul_div_cancel₀`) leaves $\sum_z p_X(x) P_Z(x, z) = p_X(x) \sum_z P_Z(x, z) = p_X(x) \cdot 1 = p_X(x)$ using `Finset.mul_sum` and `mul_one`.

    lines 33–38

    uses Finset.sum_apply, Pi.smul_apply, smul_eq_mul, mul_div_cancel₀, Finset.mul_sum, mul_one

      have hsum : ∑ z, pZ z • rz z = pX := by
        funext x
        simp only [Finset.sum_apply, Pi.smul_apply, smul_eq_mul, hrz]
        have : ∀ z, pZ z * (pX x * PZ x z / pZ z) = pX x * PZ x z := fun z =>
          mul_div_cancel₀ _ (hpZpos z).ne'
        simp only [this, ← Finset.mul_sum, hsZ, mul_one]
  7. $\tilde{I}_f(X; YZ) \le \tilde{I}_f(X; Y) + \tilde{I}_f(X; Z)$. automation

    Substituting $\sum_z p_Z(z) r_z = p_X$ into Jensen's inequality and using lemma `mutual_f_theta_self` (which identifies $\theta_f(p_X)$ with $\tilde{I}_f(X; Y)$) yields $\sum_z p_Z(z) \theta_f(r_z) \le \tilde{I}_f(X; Y)$. Combining this with the decomposition $\tilde{I}_f(X; YZ) - \tilde{I}_f(X; Z) = \sum_z p_Z(z) \theta_f(r_z)$, linear arithmetic (`linarith`) completes the proof of subadditivity.

    lines 39–41

    uses mutual_f_theta_self, smul_eq_mul

      rw [hsum, mutual_f_theta_self f hf1 pX PY hpX hsY] at hj
      simp only [smul_eq_mul] at hj
      linarith
mutual_f_information_markov_sub_eq_sum_theta
For a Markov chain $Y \to X \to Z$, the difference $\tilde{I}_f(X; YZ) - \tilde{I}_f(X; Z)$ equals the expectation over $z$ of the conditional mutual $f$-information functional $\theta_f(r_z)$ evaluated at the posterior distributions $r_z(x) = p_X(x) P_Z(x, z) / p_Z(z)$.
mutual_f_theta_concaveOn_of_weight_bound
Under the differential inequality hypothesis on $f$, the functional $r \mapsto \theta_f(r)$ is concave on the simplex of strictly positive probability distributions on $X$.
not_nonempty_iff
A type is not nonempty if and only if it is empty.
Finset.sum_pos
The sum of strictly positive elements over a nonempty finite set is strictly positive.
mul_pos
The product of two strictly positive real numbers is strictly positive.
Classical.arbitrary
Chooses an arbitrary element from a nonempty type.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.sum_comm
Double summation over finite sets can be interchanged: $\sum_{x \in s} \sum_{y \in t} f(x, y) = \sum_{y \in t} \sum_{x \in s} f(x, y)$.
Finset.mul_sum
Multiplication distributes over finite sums: $a \sum_{i \in s} f(i) = \sum_{i \in s} a f(i)$.
mul_one
Multiplying by 1 leaves any element unchanged: $a \cdot 1 = a$.
div_pos
The quotient of two strictly positive real numbers is strictly positive.
Finset.sum_div
Division distributes over finite sums: $(\sum_{i \in s} f(i)) / a = \sum_{i \in s} (f(i) / a)$.
div_self
Any non-zero real number divided by itself equals 1: $a / a = 1$.
Finset.sum_apply
A sum of functions evaluated at an argument equals the sum of their values: $(\sum_{c \in s} g(c))(a) = \sum_{c \in s} g(c)(a)$.
Pi.smul_apply
Scalar multiplication of a function evaluated at an index equals the scalar multiple of the value: $(a \cdot f)(i) = a \cdot f(i)$.
smul_eq_mul
Scalar multiplication of real numbers coincides with ordinary multiplication: $a \cdot b = a * b$.
mul_div_cancel₀
Multiplying by $b$ cancels a division by $b$ when $b \neq 0$: $b \cdot (a / b) = a$.
mutual_f_theta_self
The auxiliary functional $\theta_f$ evaluated at the prior $p_X$ itself equals the mutual $f$-information $\tilde{I}_f(X; Y)$.

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_f_information_subadditive_full_support_of_weight_bound (f : ℝ → ℝ)    (hf1 : f 1 = 0) (hconv : ConvexOn ℝ (Set.Ioi 0) f)    (hsmooth : ContDiffOn ℝ 4 f (Set.Ioi 0))    (hg2 : ∀ x > 0, deriv (deriv (subadditive_f_weight f)) x < 0)    (hbound : ∃ η ℓ : ℝ, 0 < η ∧ ∀ x > 0,      subadditive_f_weight f x + 2 * (deriv (subadditive_f_weight f) x - η) ^ 2 /        (-deriv (deriv (subadditive_f_weight f)) x) ≤ 2 * η + (x - 1) * ℓ) :    mutual_f_information_subadditive_full_support f := by  intro X Y Z _ _ _ pX PY PZ hpX hsX hPY hsY hPZ hsZ  have hdec := mutual_f_information_markov_sub_eq_sum_theta f pX PY PZ hpX hsX hPY hsY hPZ hsZ  have hcc := mutual_f_theta_concaveOn_of_weight_bound f hf1 hconv hsmooth hg2 hbound    pX PY hpX hsX hPY hsY  have hX : Nonempty X := by    by_contra h    rw [not_nonempty_iff] at h    simp at hsX  set pZ : Z → ℝ := fun z => ∑ x, pX x * PZ x z with hpZ  have hpZpos : ∀ z, 0 < pZ z := fun z =>    Finset.sum_pos (fun x _ => mul_pos (hpX x) (hPZ x z)) ⟨Classical.arbitrary X, Finset.mem_univ _⟩  have hsZ1 : ∑ z, pZ z = 1 := by    simp only [hpZ]    rw [Finset.sum_comm]    simp only [← Finset.mul_sum, hsZ, mul_one, hsX]  set rz : Z → X → ℝ := fun z x => pX x * PZ x z / pZ z with hrz  have hmem : ∀ z ∈ (Finset.univ : Finset Z),      rz z ∈ {r : X → ℝ | (∀ x, 0 < r x) ∧ ∑ x, r x = 1} := by    intro z _    refine ⟨fun x => div_pos (mul_pos (hpX x) (hPZ x z)) (hpZpos z), ?_⟩    simp only [hrz, ← Finset.sum_div]    exact div_self (hpZpos z).ne'  have hj := hcc.le_map_sum (t := Finset.univ) (w := pZ) (p := rz)    (fun z _ => (hpZpos z).le) hsZ1 hmem  have hsum : ∑ z, pZ z • rz z = pX := by    funext x    simp only [Finset.sum_apply, Pi.smul_apply, smul_eq_mul, hrz]    have : ∀ z, pZ z * (pX x * PZ x z / pZ z) = pX x * PZ x z := fun z =>      mul_div_cancel₀ _ (hpZpos z).ne'    simp only [this, ← Finset.mul_sum, hsZ, mul_one]  rw [hsum, mutual_f_theta_self f hf1 pX PY hpX hsY] at hj  simp only [smul_eq_mul] at hj  linarith
See it in the graphDiscuss this resultChallenge it