AFTD Auto-Formalizing Theoretical Domains

op_1340_empty_graph_equality

theoremverifiedoriginal

On the empty (edgeless) graph (⊥ : SimpleGraph V) on a finite type V with decidable equality and positive vertex fugacities lam, hardCoreVarSize (⊥ : SimpleGraph V) lam is equal to hardCoreClosedNeighborhoodBound (⊥ : SimpleGraph V) lam.

Statement

theorem op_1340_empty_graph_equality
    {V : Type*} [Fintype V] [DecidableEq V]
    (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) :
    hardCoreVarSize (⊥ : SimpleGraph V) lam =
      hardCoreClosedNeighborhoodBound (⊥ : SimpleGraph V) lam
Related work
OP-1340; knowledgebase
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • hardCoreClosedNeighborhoodBoundGiven a finite graph G on a type V with decidable equality and positive vertex fugacities lam, the closed-neighborhood variance lower…
  • hardCoreVarSizeGiven a finite graph G on a type V with decidable equality and vertex fugacities lam, the variance of the independent set size…

Read back from the Lean

For any finite type $V$ with decidable equality, and any function $\lambda : V \to \mathbb{R}$ such that $\lambda(v) > 0$ for all $v \in V$, the variance of the size of an independent set under the hard-core model on the empty graph $\bot$ on $V$ with vertex weights $\lambda$ (hardCoreVarSize (⊥ : SimpleGraph V) lam) equals the closed neighborhood bound for the empty graph with weights $\lambda$ (hardCoreClosedNeighborhoodBound (⊥ : SimpleGraph V) lam).

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

To show that the hard-core variance of the independent set size on the edgeless graph equals the closed-neighborhood bound, the proof establishes that vertex inclusions are independent. First, it derives explicit linear recurrences for the partition function and the first two moment sums when adjoining an isolated vertex. These recurrences imply, via finite set induction and elementary rational algebra, that the variance on any set S is the sum of lam v / (1 + lam v)^2 over v ∈ S. Finally, on the edgeless graph every subset of vertices is independent and every closed neighborhood consists solely of the vertex itself, making the hard-core variance equal the closed-neighborhood bound term by term.

  1. Adding a vertex a ∉ T multiplies the partition function on T by 1 + lam a.

    Decompose the sum over the powerset of insert a T into subsets of T and subsets containing a using Finset.sum_powerset_insert. For subsets containing a, since a ∉ I by Finset.mem_powerset.mp, the product factors as lam a * ∏ v ∈ I, lam v via Finset.prod_insert. Factoring out lam a with Finset.mul_sum and Finset.sum_congr, the total partition function simplifies to (1 + lam a) * ∑ I ∈ T.powerset, ∏ v ∈ I, lam v by ring arithmetic.

    lines 6–13

    uses Finset.sum_powerset_insert, Finset.mul_sum, Finset.sum_congr, Finset.mem_powerset.mp, Finset.prod_insert

      rw [Finset.sum_powerset_insert ha]
      have h2 : ∑ I ∈ T.powerset, (∏ v ∈ insert a I, lam v)
          = lam a * ∑ I ∈ T.powerset, ∏ v ∈ I, lam v := by
        rw [Finset.mul_sum]
        refine Finset.sum_congr rfl fun I hI => ?_
        have hai : a ∉ I := fun h => ha (Finset.mem_powerset.mp hI h)
        rw [Finset.prod_insert hai]
      rw [h2]; ring
  2. Adding a vertex a ∉ T updates the first moment sum Q(T) to (1 + lam a) * Q(T) + lam a * P(T).

    Decompose the sum over the powerset using Finset.sum_powerset_insert. For subsets containing a, the cardinality is |I| + 1 by Finset.card_insert_of_notMem and the product factors out lam a by Finset.prod_insert. Expanding (lam a * w(I)) * (|I| + 1) = lam a * w(I) * |I| + lam a * w(I) and distributing the sums with Finset.sum_add_distrib and Finset.mul_sum expresses this part as lam a * Q(T) + lam a * P(T). Adding the subsets of T not containing a yields the claimed recurrence by ring arithmetic.

    lines 21–30

    uses Finset.sum_powerset_insert, Finset.mul_sum, Finset.sum_add_distrib, Finset.sum_congr, Finset.mem_powerset.mp, Finset.prod_insert, Finset.card_insert_of_notMem

      rw [Finset.sum_powerset_insert ha]
      have hB : ∑ I ∈ T.powerset, (∏ v ∈ insert a I, lam v) * ((insert a I).card : ℝ)
          = lam a * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (I.card : ℝ))
            + lam a * (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) := by
        rw [Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib]
        refine Finset.sum_congr rfl fun I hI => ?_
        have hai : a ∉ I := fun h => ha (Finset.mem_powerset.mp hI h)
        rw [Finset.prod_insert hai, Finset.card_insert_of_notMem hai]
        push_cast; ring
      rw [hB]; ring
  3. Adding a vertex a ∉ T updates the second moment sum R(T) to (1 + lam a) * R(T) + 2 * lam a * Q(T) + lam a * P(T).

    Split the powerset sum using Finset.sum_powerset_insert. For subsets containing a, expand the squared cardinality (|I| + 1)^2 = |I|^2 + 2|I| + 1 using Finset.card_insert_of_notMem and factor out lam a via Finset.prod_insert. Distributing the sum with Finset.mul_sum and Finset.sum_add_distrib gives lam a * R(T) + 2 * lam a * Q(T) + lam a * P(T). Adding the subsets not containing a yields the full recurrence by ring arithmetic.

    lines 39–50

    uses Finset.sum_powerset_insert, Finset.mul_sum, Finset.sum_add_distrib, Finset.sum_congr, Finset.mem_powerset.mp, Finset.prod_insert, Finset.card_insert_of_notMem

      rw [Finset.sum_powerset_insert ha]
      have hB : ∑ I ∈ T.powerset, (∏ v ∈ insert a I, lam v) * ((insert a I).card : ℝ)^2
          = lam a * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (I.card : ℝ)^2)
            + 2 * lam a * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (I.card : ℝ))
            + lam a * (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) := by
        rw [Finset.mul_sum, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib,
          ← Finset.sum_add_distrib]
        refine Finset.sum_congr rfl fun I hI => ?_
        have hai : a ∉ I := fun h => ha (Finset.mem_powerset.mp hI h)
        rw [Finset.prod_insert hai, Finset.card_insert_of_notMem hai]
        push_cast; ring
      rw [hB]; ring
  4. The partition function of the hard-core model on any finite set of vertices is strictly positive.

    Rewrite the partition function sum over the powerset as the product ∏ v ∈ S, (lam v + 1) using Finset.prod_add_one. Since every fugacity lam v > 0, each factor lam v + 1 is strictly positive by linear arithmetic, so the product is strictly positive by Finset.prod_pos.

    lines 56–57

    uses Finset.prod_add_one, Finset.prod_pos

      rw [← Finset.prod_add_one (f := lam) S]
      exact Finset.prod_pos fun i _ => by linarith [hpos i]
  5. Under the linear moment recurrences with fugacity w, the variance of the independent set size increases by w / (1 + w)^2.

    Since P ≠ 0 and 1 + w ≠ 0, their product (1 + w) * P is non-zero by mul_ne_zero. Clearing denominators with field_simp reduces the identity to a polynomial equation that is verified by ring.

    lines 64–66

    uses mul_ne_zero

      have hP1 : (1 + w) * P ≠ 0 := mul_ne_zero h1 hP
      field_simp
      ring
  6. The variance formula holds for the empty set of vertices.

    Apply finite set induction using Finset.induction_on. In the base case S = ∅, both sides evaluate directly to 0, which is closed by simp.

    lines 75–76

    uses Finset.induction_on

      induction S using Finset.induction_on with
      | empty => simp
  7. For an edgeless graph on any finite set S, the variance of the independent set size is ∑ v ∈ S, lam v / (1 + lam v)^2.

    In the inductive step with S = insert a T where a ∉ T, rewrite the partition function and moments using op_1340_empty_graph_equality_P_insert, op_1340_empty_graph_equality_Q_insert, and op_1340_empty_graph_equality_R_insert. Expanding the sum with Finset.sum_insert and using the induction hypothesis, the goal reduces to showing the variance increases by lam a / (1 + lam a)^2. Strict positivity of the partition function from op_1340_empty_graph_equality_P_pos (via ne_of_gt) and 1 + lam a ≠ 0 allow applying op_1340_empty_graph_equality_var_alg, closing the induction step.

    lines 77–83

    uses op_1340_empty_graph_equality_P_insert, op_1340_empty_graph_equality_Q_insert, op_1340_empty_graph_equality_R_insert, Finset.sum_insert, ne_of_gt, op_1340_empty_graph_equality_P_pos, op_1340_empty_graph_equality_var_alg

      | insert a T ha ih =>
        rw [op_1340_empty_graph_equality_P_insert lam ha, op_1340_empty_graph_equality_Q_insert lam ha,
          op_1340_empty_graph_equality_R_insert lam ha, Finset.sum_insert ha, ← ih]
        have hP : (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) ≠ 0 :=
          ne_of_gt (op_1340_empty_graph_equality_P_pos lam hpos T)
        have h1 : (1 + lam a) ≠ 0 := by linarith [hpos a]
        rw [op_1340_empty_graph_equality_var_alg _ _ _ _ hP h1]
  8. Every subset of vertices is an independent set in the edgeless graph ⊥, so the collection of independent sets is the entire powerset.

    In the edgeless graph, no two vertices are adjacent, which holds universally by Set.pairwise_of_forall. Therefore, every subset of V is an independent set, so filtering the universal finset by independence preserves all subsets by Finset.filter_true_of_mem. Furthermore, the powerset of the universal finset of vertices is the universal finset of all finsets by Finset.powerset_univ.

    lines 91–96

    uses Finset.filter_true_of_mem, Set.pairwise_of_forall, Finset.powerset_univ

      have hfil : (Finset.univ.filter (fun I : Finset V => (⊥ : SimpleGraph V).IsIndepSet (↑I)))
          = Finset.univ := by
        rw [Finset.filter_true_of_mem]
        intro x _
        exact Set.pairwise_of_forall _ _ (fun a b => by simp)
      have hpu : (Finset.univ : Finset V).powerset = Finset.univ := Finset.powerset_univ
  9. The hard-core size variance on the edgeless graph equals the powerset variance formula on the full vertex set.

    Unfolding the definition of hardCoreVarSize, the filtered independent sets are rewritten to the unconstrained powerset of the universal finset using the equalities established in the previous step.

    lines 97–103

      have hvar : hardCoreVarSize (⊥ : SimpleGraph V) lam
          = (∑ I ∈ (Finset.univ : Finset V).powerset, (∏ v ∈ I, lam v) * (I.card : ℝ)^2)
              / (∑ I ∈ (Finset.univ : Finset V).powerset, ∏ v ∈ I, lam v)
            - ((∑ I ∈ (Finset.univ : Finset V).powerset, (∏ v ∈ I, lam v) * (I.card : ℝ))
                / (∑ I ∈ (Finset.univ : Finset V).powerset, ∏ v ∈ I, lam v))^2 := by
        simp only [hardCoreVarSize]
        rw [hfil, ← hpu]
  10. On the edgeless graph ⊥, hardCoreVarSize (⊥ : SimpleGraph V) lam equals hardCoreClosedNeighborhoodBound (⊥ : SimpleGraph V) lam.

    Rewrite the hard-core variance using the finset formula op_1340_empty_graph_equality_var_finset to obtain ∑ v ∈ Finset.univ, lam v / (1 + lam v)^2. By Finset.sum_congr, it suffices to match each summand. In the edgeless graph ⊥, the neighborhood of any vertex v is empty, so its closed neighborhood insert v (⊥.neighborFinset v) reduces to {v}, and the closed-neighborhood bound term simplifies to lam v / (1 + lam v)^2 via simp.

    lines 104–106

    uses op_1340_empty_graph_equality_var_finset, Finset.sum_congr

      rw [hvar, op_1340_empty_graph_equality_var_finset lam hlam]
      refine Finset.sum_congr rfl fun v _ => ?_
      simp
Finset.sum_powerset_insert
Decomposes a sum over all subsets of insert a s (where a ∉ s) into the sum over subsets of s plus the sum over subsets with a inserted.
Finset.mul_sum
Multiplication distributes over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on every element.
Finset.mem_powerset.mp
If a finite set belongs to the powerset of s, then it is a subset of s.
Finset.prod_insert
The product of a function over insert a s (where a ∉ s) equals f a times the product over s.
Finset.sum_add_distrib
The sum of a pointwise sum of two functions equals the sum of their individual sums.
Finset.card_insert_of_notMem
Inserting an element into a finite set that does not contain it increases its cardinality by 1.
Finset.prod_add_one
The product ∏ i ∈ s, (f i + 1) expands as the sum over all subsets t ⊆ s of ∏ i ∈ t, f i.
Finset.prod_pos
A finite product of strictly positive real numbers is strictly positive.
mul_ne_zero
The product of two non-zero real numbers is non-zero.
Finset.induction_on
Induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved under adjoining a new element.
op_1340_empty_graph_equality_P_insert
Adding a new vertex a to T multiplies the hard-core partition function on T by 1 + lam a.
op_1340_empty_graph_equality_Q_insert
Adding a new vertex a to T updates the first moment sum Q(T) to (1 + lam a) * Q(T) + lam a * P(T).
op_1340_empty_graph_equality_R_insert
Adding a new vertex a to T updates the second moment sum R(T) to (1 + lam a) * R(T) + 2 * lam a * Q(T) + lam a * P(T).
Finset.sum_insert
A sum over insert a s (where a ∉ s) equals f a plus the sum over s.
ne_of_gt
If a number is strictly greater than another, they are not equal.
op_1340_empty_graph_equality_P_pos
The partition function of the hard-core model on an edgeless graph is strictly positive when all vertex fugacities are positive.
op_1340_empty_graph_equality_var_alg
Algebraic identity showing that under the linear recurrences for P, Q, and R, the variance updates by adding w / (1 + w)^2.
op_1340_empty_graph_equality_var_finset
For an edgeless graph on a finite set S, the variance of the independent set size equals ∑ v ∈ S, lam v / (1 + lam v)^2.
Finset.filter_true_of_mem
Filtering a finite set by a predicate that holds for all its members returns the entire set.
Set.pairwise_of_forall
If a binary relation holds for all pairs of elements, then any set is pairwise related under it.
Finset.powerset_univ
The powerset of the universal finset of a fintype is the universal finset of subsets.

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

/-- Adding a vertex multiplies the partition function by `1 + lam a`. -/private lemma op_1340_empty_graph_equality_P_insert {V : Type*} [DecidableEq V] (lam : V → ℝ)    {a : V} {T : Finset V} (ha : a ∉ T) :    (∑ I ∈ (insert a T).powerset, ∏ v ∈ I, lam v)      = (1 + lam a) * ∑ I ∈ T.powerset, ∏ v ∈ I, lam v := by  rw [Finset.sum_powerset_insert ha]  have h2 : ∑ I ∈ T.powerset, (∏ v ∈ insert a I, lam v)      = lam a * ∑ I ∈ T.powerset, ∏ v ∈ I, lam v := by    rw [Finset.mul_sum]    refine Finset.sum_congr rfl fun I hI => ?_    have hai : a ∉ I := fun h => ha (Finset.mem_powerset.mp hI h)    rw [Finset.prod_insert hai]  rw [h2]; ring/-- Recurrence of the first moment sum when adding a vertex. -/private lemma op_1340_empty_graph_equality_Q_insert {V : Type*} [DecidableEq V] (lam : V → ℝ)    {a : V} {T : Finset V} (ha : a ∉ T) :    (∑ I ∈ (insert a T).powerset, (∏ v ∈ I, lam v) * (I.card : ℝ))      = (1 + lam a) * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (I.card : ℝ))        + lam a * (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) := by  rw [Finset.sum_powerset_insert ha]  have hB : ∑ I ∈ T.powerset, (∏ v ∈ insert a I, lam v) * ((insert a I).card : ℝ)      = lam a * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (I.card : ℝ))        + lam a * (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) := by    rw [Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib]    refine Finset.sum_congr rfl fun I hI => ?_    have hai : a ∉ I := fun h => ha (Finset.mem_powerset.mp hI h)    rw [Finset.prod_insert hai, Finset.card_insert_of_notMem hai]    push_cast; ring  rw [hB]; ring/-- Recurrence of the second moment sum when adding a vertex. -/private lemma op_1340_empty_graph_equality_R_insert {V : Type*} [DecidableEq V] (lam : V → ℝ)    {a : V} {T : Finset V} (ha : a ∉ T) :    (∑ I ∈ (insert a T).powerset, (∏ v ∈ I, lam v) * (I.card : ℝ)^2)      = (1 + lam a) * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (I.card : ℝ)^2)        + 2 * lam a * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (I.card : ℝ))        + lam a * (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) := by  rw [Finset.sum_powerset_insert ha]  have hB : ∑ I ∈ T.powerset, (∏ v ∈ insert a I, lam v) * ((insert a I).card : ℝ)^2      = lam a * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (I.card : ℝ)^2)        + 2 * lam a * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (I.card : ℝ))        + lam a * (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) := by    rw [Finset.mul_sum, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib,      ← Finset.sum_add_distrib]    refine Finset.sum_congr rfl fun I hI => ?_    have hai : a ∉ I := fun h => ha (Finset.mem_powerset.mp hI h)    rw [Finset.prod_insert hai, Finset.card_insert_of_notMem hai]    push_cast; ring  rw [hB]; ring/-- The partition function of the hard-core model on an edgeless graph is positive. -/private lemma op_1340_empty_graph_equality_P_pos {V : Type*} [DecidableEq V] (lam : V → ℝ)    (hpos : ∀ v, 0 < lam v) (S : Finset V) :    0 < ∑ I ∈ S.powerset, ∏ v ∈ I, lam v := by  rw [← Finset.prod_add_one (f := lam) S]  exact Finset.prod_pos fun i _ => by linarith [hpos i]/-- The elementary algebra of the variance recursion under adding one vertex. -/private lemma op_1340_empty_graph_equality_var_alg (P Q R w : ℝ) (hP : P ≠ 0) (h1 : 1 + w ≠ 0) :    ((1 + w) * R + 2 * w * Q + w * P) / ((1 + w) * P)      - (((1 + w) * Q + w * P) / ((1 + w) * P))^2    = w / (1 + w)^2 + (R / P - (Q / P)^2) := by  have hP1 : (1 + w) * P ≠ 0 := mul_ne_zero h1 hP  field_simp  ring/-- For an edgeless graph on `S`, the variance of the independent-set size equals`∑ v ∈ S, lam v / (1 + lam v)^2`. -/private lemma op_1340_empty_graph_equality_var_finset {V : Type*} [DecidableEq V] (lam : V → ℝ)    (hpos : ∀ v, 0 < lam v) (S : Finset V) :    (∑ I ∈ S.powerset, (∏ v ∈ I, lam v) * (I.card : ℝ)^2) / (∑ I ∈ S.powerset, ∏ v ∈ I, lam v)      - ((∑ I ∈ S.powerset, (∏ v ∈ I, lam v) * (I.card : ℝ)) / (∑ I ∈ S.powerset, ∏ v ∈ I, lam v))^2    = ∑ v ∈ S, lam v / (1 + lam v)^2 := by  induction S using Finset.induction_on with  | empty => simp  | insert a T ha ih =>    rw [op_1340_empty_graph_equality_P_insert lam ha, op_1340_empty_graph_equality_Q_insert lam ha,      op_1340_empty_graph_equality_R_insert lam ha, Finset.sum_insert ha, ← ih]    have hP : (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) ≠ 0 :=      ne_of_gt (op_1340_empty_graph_equality_P_pos lam hpos T)    have h1 : (1 + lam a) ≠ 0 := by linarith [hpos a]    rw [op_1340_empty_graph_equality_var_alg _ _ _ _ hP h1]/-- On an edgeless graph (empty graph), the hard-core variance of |I| equals the closed-neighborhood bound. -/theorem op_1340_empty_graph_equality    {V : Type*} [Fintype V] [DecidableEq V]    (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) :    hardCoreVarSize (⊥ : SimpleGraph V) lam =      hardCoreClosedNeighborhoodBound (⊥ : SimpleGraph V) lam := by  have hfil : (Finset.univ.filter (fun I : Finset V => (⊥ : SimpleGraph V).IsIndepSet (↑I)))      = Finset.univ := by    rw [Finset.filter_true_of_mem]    intro x _    exact Set.pairwise_of_forall _ _ (fun a b => by simp)  have hpu : (Finset.univ : Finset V).powerset = Finset.univ := Finset.powerset_univ  have hvar : hardCoreVarSize (⊥ : SimpleGraph V) lam      = (∑ I ∈ (Finset.univ : Finset V).powerset, (∏ v ∈ I, lam v) * (I.card : ℝ)^2)          / (∑ I ∈ (Finset.univ : Finset V).powerset, ∏ v ∈ I, lam v)        - ((∑ I ∈ (Finset.univ : Finset V).powerset, (∏ v ∈ I, lam v) * (I.card : ℝ))            / (∑ I ∈ (Finset.univ : Finset V).powerset, ∏ v ∈ I, lam v))^2 := by    simp only [hardCoreVarSize]    rw [hfil, ← hpu]  rw [hvar, op_1340_empty_graph_equality_var_finset lam hlam]  refine Finset.sum_congr rfl fun v _ => ?_  simp
See it in the graphDiscuss this resultChallenge it