AFTD Auto-Formalizing Theoretical Domains

finite_variance_recurrence_additive

theoremverified

If partition functions and the first two unnormalized moments satisfy the independent-component recurrences with nonzero denominators, the total variance is the sum of the component variances.

Statement

theorem finite_variance_recurrence_additive {C : Type*} [DecidableEq C]
    (Z A B : Finset C → ℝ) (s m₁ m₂ : C → ℝ)
    (hZ : ∀ T, Z T ≠ 0) (hs : ∀ c, 1 + s c ≠ 0)
    (hbase : A ∅ = 0 ∧ B ∅ = 0)
    (hZstep : ∀ c T, c ∉ T → Z (insert c T) = (1+s c) * Z T)
    (hAstep : ∀ c T, c ∉ T → A (insert c T) = (1+s c) * A T + m₁ c * Z T)
    (hBstep : ∀ c T, c ∉ T → B (insert c T) = (1+s c) * B T + 2 * m₁ c * A T + m₂ c * Z T)
    (T : Finset C) :
    B T / Z T - (A T / Z T)^2 = ∑ c ∈ T, (m₂ c / (1+s c) - (m₁ c / (1+s c))^2)
Source
Component decomposition for op_1355_clique_components_variance_ge_bound.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem is proved by induction on the finite set T using Finset.induction_on. The base case T = ∅ is straightforward because the unnormalized moments vanish on the empty set. For the inductive step, the recurrence relations express the moments and partition function on T ∪ {c} in terms of those on T. A purely algebraic identity (hstep) shows that the variance of the combined system decomposes into the variance of T plus the variance contribution of the new component c, which completes the induction.

  1. The variance identity holds for the empty set T = ∅.

    We induct on the finite set T using Finset.induction_on. In the base case T = ∅, the base hypothesis hbase gives A(∅) = 0 and B(∅) = 0. Substituting these values into the left-hand side yields 0 / Z(∅) - (0 / Z(∅))² = 0. The right-hand side is an empty sum, which is also 0.

    lines 12–13

    uses Finset.induction_on

      induction T using Finset.induction_on with
      | empty => simp [hbase.1, hbase.2]
  2. In the inductive step, the recurrence relations and sum splitting express both sides for T ∪ {c} in terms of T and c.

    For the inductive step, we assume the identity holds for T (the induction hypothesis ih) and consider adding an element c ∉ T. Applying the recurrence relations hZstep, hAstep, and hBstep rewrites Z(T ∪ {c}), A(T ∪ {c}), and B(T ∪ {c}) on the left-hand side. On the right-hand side, Finset.sum_insert splits the summation over T ∪ {c} into the summand at c plus the sum over T.

    lines 14–15

    uses Finset.sum_insert

      | @insert c T hc ih =>
        rw [hZstep c T hc, hAstep c T hc, hBstep c T hc, Finset.sum_insert hc]
  3. The variance of T ∪ {c} decomposes into the variance of T plus the variance contribution of c.

    We prove the algebraic transition identity (hstep). Since 1 + s(c) ≠ 0 by hypothesis hs and Z(T) ≠ 0 by hZ, their product (1 + s(c)) * Z(T) is nonzero by mul_ne_zero. Clearing denominators across all rational terms with field_simp reduces the identity to an equality between two polynomials, which ring verifies.

    lines 16–21

    uses mul_ne_zero

        have hstep : ((1+s c) * B T + 2 * m₁ c * A T + m₂ c * Z T) / ((1+s c) * Z T) -
            (((1+s c) * A T + m₁ c * Z T) / ((1+s c) * Z T))^2 =
            (B T / Z T - (A T / Z T)^2) + (m₂ c / (1+s c) - (m₁ c / (1+s c))^2) := by
          have h1 : (1 + s c) * Z T ≠ 0 := mul_ne_zero (hs c) (hZ T)
          field_simp [hZ T, hs c]
          ring
  4. The inductive step is completed.

    Rewriting the goal using the transition identity (hstep) and the induction hypothesis (ih) replaces the variance at T by the sum over T. Both sides now consist of the sum over T plus the term for c, and the ring tactic verifies that the two sides are equal by commutativity of addition.

    lines 22–23

        rw [hstep, ih]
        ring
Finset.induction_on
To prove a property for all finite sets, it suffices to prove it for the empty set and show that if it holds for a finite set s, it also holds for s with any new element inserted.
Finset.sum_insert
The sum of a function over a finite set with a new element inserted equals the value at that element plus the sum over the original set.
mul_ne_zero
In a type without zero divisors (such as ℝ), the product of two nonzero elements is nonzero.

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

open scoped Classicaltheorem finite_variance_recurrence_additive {C : Type*} [DecidableEq C]    (Z A B : Finset C → ℝ) (s m₁ m₂ : C → ℝ)    (hZ : ∀ T, Z T ≠ 0) (hs : ∀ c, 1 + s c ≠ 0)    (hbase : A ∅ = 0 ∧ B ∅ = 0)    (hZstep : ∀ c T, c ∉ T → Z (insert c T) = (1+s c) * Z T)    (hAstep : ∀ c T, c ∉ T → A (insert c T) = (1+s c) * A T + m₁ c * Z T)    (hBstep : ∀ c T, c ∉ T → B (insert c T) = (1+s c) * B T + 2 * m₁ c * A T + m₂ c * Z T)    (T : Finset C) :    B T / Z T - (A T / Z T)^2 = ∑ c ∈ T, (m₂ c / (1+s c) - (m₁ c / (1+s c))^2) := by  induction T using Finset.induction_on with  | empty => simp [hbase.1, hbase.2]  | @insert c T hc ih =>    rw [hZstep c T hc, hAstep c T hc, hBstep c T hc, Finset.sum_insert hc]    have hstep : ((1+s c) * B T + 2 * m₁ c * A T + m₂ c * Z T) / ((1+s c) * Z T) -        (((1+s c) * A T + m₁ c * Z T) / ((1+s c) * Z T))^2 =        (B T / Z T - (A T / Z T)^2) + (m₂ c / (1+s c) - (m₁ c / (1+s c))^2) := by      have h1 : (1 + s c) * Z T ≠ 0 := mul_ne_zero (hs c) (hZ T)      field_simp [hZ T, hs c]      ring    rw [hstep, ih]    ring
See it in the graphDiscuss this resultChallenge it