op_1340_empty_graph_equality
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.
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.
uses
Finset.sum_powerset_insert,Finset.mul_sum,Finset.sum_congr,Finset.mem_powerset.mp,Finset.prod_insertrw [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
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.
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_notMemrw [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
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.
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_notMemrw [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 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.
uses
Finset.prod_add_one,Finset.prod_posrw [← Finset.prod_add_one (f := lam) S] exact Finset.prod_pos fun i _ => by linarith [hpos i]
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.
uses
mul_ne_zerohave hP1 : (1 + w) * P ≠ 0 := mul_ne_zero h1 hP field_simp ring
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.
uses
Finset.induction_oninduction S using Finset.induction_on with | empty => simp
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.
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]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.
uses
Finset.filter_true_of_mem,Set.pairwise_of_forall,Finset.powerset_univhave 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
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.
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]
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.
uses
op_1340_empty_graph_equality_var_finset,Finset.sum_congrrw [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.
- In the formalization, the variance formula is proved via explicit algebraic moment recurrences and finite set induction rather than invoking probabilistic independence of vertex indicators directly.
- The fact that every subset of vertices in the edgeless graph is independent is verified formally using Set.pairwise_of_forall on the empty adjacency relation.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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