op_1355_empty_graph_equality
On the edgeless graph (⊥ : SimpleGraph V) on a finite type V with decidable equality, for all positive vertex fugacities lam and all nonnegative observable weights a, the weighted hard-core variance hardCoreWeightedVar (⊥ : SimpleGraph V) lam a equals the weighted closed-neighborhood bound hardCoreWeightedClosedNeighborhoodBound (⊥ : SimpleGraph V) lam a.
Statement
theorem op_1355_empty_graph_equality {V : Type*} [Fintype V] [DecidableEq V] (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v) : hardCoreWeightedVar (⊥ : SimpleGraph V) lam a = hardCoreWeightedClosedNeighborhoodBound (⊥ : SimpleGraph V) lam a
- Formalizes
- OP-1355
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- hardCoreWeightedVarGiven a finite graph G on a type V with decidable equality, vertex fugacities lam, and observable weights a, hardCoreWeightedVar G lam a…
- hardCoreWeightedClosedNeighborhoodBoundGiven a finite graph G on a type V with decidable equality, vertex fugacities lam, and observable weights a,…
Read back from the Lean
For any finite type $V$ with decidable equality, any function $\lambda : V \to \mathbb{R}$ such that $\lambda(v) > 0$ for all $v \in V$, and any function $a : V \to \mathbb{R}$ such that $a(v) \ge 0$ for all $v \in V$, the hard-core weighted variance hardCoreWeightedVar on the empty graph $(\bot : \text{SimpleGraph } V)$ with fugacity function $\lambda$ and vertex weights $a$ is equal to the closed neighborhood bound hardCoreWeightedClosedNeighborhoodBound on the empty graph with the same $\lambda$ and $a$.
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
On an edgeless graph, every subset of vertices is an independent set and the open neighborhood of every vertex is empty, so each closed neighborhood is a singleton. The hard-core distribution therefore factors as an independent product of Bernoulli variables with success probabilities λ(v) / (1 + λ(v)). The proof establishes by finite-set induction that the variance of the linear observable ∑_{v ∈ I} a(v) under this product measure is the sum of the per-vertex Bernoulli variances, relying on recurrence relations for the partition function and the first two unnormalized moments upon adjoining a vertex. Evaluating this identity on the full vertex set V matches the closed-neighborhood bound term by term.
The partition function sum on the power set of T ∪ {b} splits into subsets of T and subsets containing b, where the product weight on I ∪ {b} factors as λ(b) times the product weight on I.
Using Finset.sum_powerset_insert, the sum over the power set of T ∪ {b} is decomposed into subsets belonging to the power set of T and subsets formed by adjoining b to a subset I ⊆ T. Since b ∉ T, b cannot belong to any I ⊆ T by Finset.mem_powerset.mp, so Finset.prod_insert factors the product weight over I ∪ {b} into λ(b) ∏_{v ∈ I} λ(v).
uses
Finset.sum_powerset_insert,Finset.mem_powerset.mp,Finset.prod_insertrw [Finset.sum_powerset_insert hb] have h2 : ∀ I ∈ T.powerset, (∏ v ∈ insert b I, lam v) = lam b * ∏ v ∈ I, lam v := by intro I hI have hbi : b ∉ I := fun h => hb (Finset.mem_powerset.mp hI h) rw [Finset.prod_insert hbi]
The partition function satisfies the recurrence Z(T ∪ {b}) = (1 + λ(b)) Z(T).
Rewriting with the factored product using Finset.sum_congr, combining the two sums via Finset.sum_add_distrib, and pulling out the common factor with Finset.mul_sum, ring arithmetic verifies that the sum of the unweighted and λ(b)-weighted sums equals (1 + λ(b)) times the original sum.
uses
Finset.sum_congr,Finset.sum_add_distrib,Finset.mul_sumrw [Finset.sum_congr rfl h2, ← Finset.sum_add_distrib, Finset.mul_sum] apply Finset.sum_congr rfl intro x hx ring
The first moment sum on T ∪ {b} splits into subsets of T and subsets containing b, with each term for I ∪ {b} expanding to λ(b) (∏_{v ∈ I} λ(v)) (∑_{v ∈ I} w(v)) + λ(b) w(b) ∏_{v ∈ I} λ(v).
Applying Finset.sum_powerset_insert separates the power set sum. For I ⊆ T, since b ∉ I by Finset.mem_powerset.mp, Finset.prod_insert and Finset.sum_insert factor the product weight as λ(b) ∏_{v ∈ I} λ(v) and the weight sum as w(b) + ∑_{v ∈ I} w(v). Multiplying out these factors yields the first-moment and partition-function components on I.
uses
Finset.sum_powerset_insert,Finset.mem_powerset.mp,Finset.prod_insert,Finset.sum_insertrw [Finset.sum_powerset_insert hb] have h2 : ∀ I ∈ T.powerset, (∏ v ∈ insert b I, lam v) * (∑ v ∈ insert b I, w v) = lam b * ((∏ v ∈ I, lam v) * (∑ v ∈ I, w v)) + (lam b * w b) * (∏ v ∈ I, lam v) := by intro I hI have hbi : b ∉ I := fun h => hb (Finset.mem_powerset.mp hI h) rw [Finset.prod_insert hbi, Finset.sum_insert hbi] ring
The first moment satisfies the recurrence A(T ∪ {b}) = (1 + λ(b)) A(T) + λ(b) w(b) Z(T).
Replacing the expanded terms with Finset.sum_congr, distributing addition across sums with Finset.sum_add_distrib, and pulling constants outside sums with Finset.mul_sum, ring arithmetic groups the terms into (1 + λ(b)) times the first moment on T plus λ(b) w(b) times the partition function on T.
uses
Finset.sum_congr,Finset.sum_add_distrib,Finset.mul_sumrw [Finset.sum_congr rfl h2, Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum] ring
The second moment sum on T ∪ {b} splits into subsets of T and subsets containing b, expanding the squared observable (w(b) + ∑_{v ∈ I} w(v))^2 for subsets containing b.
By Finset.sum_powerset_insert, the sum splits. For I ⊆ T, b ∉ I by Finset.mem_powerset.mp, so Finset.prod_insert and Finset.sum_insert rewrite the product and observable on I ∪ {b}. Expanding (w(b) + ∑_{v ∈ I} w(v))^2 into the square, cross term, and constant term gives three pieces corresponding to the second moment, first moment, and partition function weights on I.
uses
Finset.sum_powerset_insert,Finset.mem_powerset.mp,Finset.prod_insert,Finset.sum_insertrw [Finset.sum_powerset_insert hb] have h2 : ∀ I ∈ T.powerset, (∏ v ∈ insert b I, lam v) * (∑ v ∈ insert b I, w v) ^ 2 = lam b * ((∏ v ∈ I, lam v) * (∑ v ∈ I, w v) ^ 2) + (2 * lam b * w b) * ((∏ v ∈ I, lam v) * (∑ v ∈ I, w v)) + (lam b * (w b) ^ 2) * (∏ v ∈ I, lam v) := by intro I hI have hbi : b ∉ I := fun h => hb (Finset.mem_powerset.mp hI h) rw [Finset.prod_insert hbi, Finset.sum_insert hbi] ring
The second moment satisfies the recurrence B(T ∪ {b}) = (1 + λ(b)) B(T) + 2 λ(b) w(b) A(T) + λ(b) w(b)^2 Z(T).
Using Finset.sum_congr to substitute the expanded terms, Finset.sum_add_distrib to split the three-part sum, and Finset.mul_sum to factor out the scalar multipliers, ring arithmetic groups the expression into the claimed linear combination of B(T), A(T), and Z(T).
uses
Finset.sum_congr,Finset.sum_add_distrib,Finset.mul_sumrw [Finset.sum_congr rfl h2, Finset.sum_add_distrib, Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum, ← Finset.mul_sum] ring
The variance identity holds in the base case S = ∅.
Induction on S is initiated using Finset.induction_on. When S = ∅, the power set consists only of {∅}, both moments vanish, the partition function is 1, and the right-hand sum over ∅ is empty; simp simplifies both sides to 0.
uses
Finset.induction_oninduction S using Finset.induction_on with | empty => simp
In the induction step for S = T ∪ {b}, substituting the recurrence relations and inductive hypothesis reduces the variance equality to a rational identity.
The recurrence relations op_1355_empty_graph_equality_B_insert, op_1355_empty_graph_equality_A_insert, and op_1355_empty_graph_equality_Z_insert express the moments and partition function on T ∪ {b} in terms of those on T. The right-hand sum is split into the b-term and the sum on T using Finset.sum_insert, and the induction hypothesis replaces the sum on T with the variance on T.
uses
op_1355_empty_graph_equality_B_insert,op_1355_empty_graph_equality_A_insert,op_1355_empty_graph_equality_Z_insert,Finset.sum_insert| insert b T hb ih => rw [op_1355_empty_graph_equality_B_insert lam w b T hb, op_1355_empty_graph_equality_A_insert lam w b T hb, op_1355_empty_graph_equality_Z_insert lam w b T hb, Finset.sum_insert hb, ← ih]The denominators Z(T) and 1 + λ(b) are strictly positive, hence nonzero.
By op_1355_empty_graph_equality_Zsum, Z(T) factors as ∏_{v ∈ T} (1 + λ(v)). Since each λ(v) > 0, linear arithmetic shows 1 + λ(v) > 0, so the product is strictly positive by Finset.prod_pos, which gives Z(T) ≠ 0 via ne_of_gt. Similarly, λ(b) > 0 implies 1 + λ(b) ≠ 0.
uses
op_1355_empty_graph_equality_Zsum,Finset.prod_pos,ne_of_gthave hZ : (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) ≠ 0 := by rw [op_1355_empty_graph_equality_Zsum lam T] exact ne_of_gt (Finset.prod_pos (fun v _ => by linarith [hlam v])) have hu : (1 + lam b) ≠ 0 := by linarith [hlam b]
Clearing denominators confirms that the variance on T ∪ {b} equals the variance on T plus the variance contribution from b.
With the nonvanishing of denominators verified, field_simp clears the fractions. The resulting polynomial identity in Z(T), A(T), B(T), w(b), and λ(b) is verified by ring, completing the inductive step.
field_simp ring
On the edgeless graph ⊥, every subset of vertices is an independent set, and the power set of Finset.univ is Finset.univ.
Since the edgeless graph has no edges, no two vertices are adjacent, which is checked by simp. Thus Set.pairwise_of_forall shows every subset is pairwise non-adjacent, making every subset independent. Filtering Finset.univ by independence therefore retains the entire set by Finset.filter_true_of_mem, and Finset.powerset_univ equates the power set of Finset.univ to Finset.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 weighted hard-core variance on ⊥ is the variance of the linear observable over the full power set of all vertices.
Unfolding hardCoreWeightedVar with simp only defines the variance in terms of sums over the independent sets. Rewriting with the fact that all subsets are independent and that their collection is Finset.univ.powerset expresses both moments and the partition function over the full power set.
have hvar : hardCoreWeightedVar (⊥ : SimpleGraph V) lam a = (∑ I ∈ (Finset.univ : Finset V).powerset, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v) ^ 2) / (∑ I ∈ (Finset.univ : Finset V).powerset, ∏ v ∈ I, lam v) - ((∑ I ∈ (Finset.univ : Finset V).powerset, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)) / (∑ I ∈ (Finset.univ : Finset V).powerset, ∏ v ∈ I, lam v)) ^ 2 := by simp only [hardCoreWeightedVar] rw [hfil, ← hpu]
The weighted closed-neighborhood bound on ⊥ simplifies to ∑_{v ∈ V} a(v)^2 λ(v) / (1 + λ(v))^2.
Unfolding hardCoreWeightedClosedNeighborhoodBound, the bound involves the closed neighborhood N[v] = insert v (⊥.neighborFinset v). In the edgeless graph, the open neighborhood is empty, so N[v] reduces to the singleton {v}, and the sum of fugacities in the denominator reduces to λ(v). Simplifying each term with Finset.sum_congr and simp yields the per-vertex sum.
uses
Finset.sum_congrhave hbound : hardCoreWeightedClosedNeighborhoodBound (⊥ : SimpleGraph V) lam a = ∑ v ∈ (Finset.univ : Finset V), a v ^ 2 * lam v / (1 + lam v) ^ 2 := by simp only [hardCoreWeightedClosedNeighborhoodBound] refine Finset.sum_congr rfl fun v _ => ?_ simp
The weighted hard-core variance on the edgeless graph equals the weighted closed-neighborhood bound.
Substituting the power-set variance expression and the simplified closed-neighborhood bound reduces the goal to the finite-set variance formula op_1355_empty_graph_equality_var_finset evaluated on S = Finset.univ with observable weights w = a, concluding the proof.
uses
op_1355_empty_graph_equality_var_finsetrw [hvar, hbound, op_1355_empty_graph_equality_var_finset lam a hlam Finset.univ]
Finset.sum_powerset_insert- For an element not in a finite set, the sum of a function over the power set of the set with that element adjoined splits into the sum over subsets not containing the element and the sum over subsets containing it.
Finset.mem_powerset.mp- An element belongs to the power set of a finite set if and only if it is a subset of that set.
Finset.prod_insert- The product of a function over a finite set with a new element adjoined equals the value at that element multiplied by the product over the original set.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every element.
Finset.sum_add_distrib- The sum over a finite set of a pointwise sum of functions equals the sum of the individual sums.
Finset.mul_sum- Multiplication by a scalar distributes over a finite sum.
Finset.sum_insert- The sum of a function over a finite set with a new element adjoined equals the value at that element plus the sum over the original set.
Finset.induction_on- A property holds for all finite sets if it holds for the empty set and is preserved whenever a new element is adjoined.
op_1355_empty_graph_equality_B_insert- When an element is adjoined to a set, the unnormalized second moment sum on the enlarged power set satisfies B(T ∪ {b}) = (1 + λ(b)) B(T) + 2 λ(b) w(b) A(T) + λ(b) w(b)^2 Z(T).
op_1355_empty_graph_equality_A_insert- When an element is adjoined to a set, the unnormalized first moment sum on the enlarged power set satisfies A(T ∪ {b}) = (1 + λ(b)) A(T) + λ(b) w(b) Z(T).
op_1355_empty_graph_equality_Z_insert- When an element is adjoined to a set, the partition function sum on the enlarged power set satisfies Z(T ∪ {b}) = (1 + λ(b)) Z(T).
op_1355_empty_graph_equality_Zsum- On any finite set, the partition function sum over all subsets equals the product of (1 + λ(v)) over all elements v.
ne_of_gt- If one real number is strictly greater than another, then they are not equal.
Finset.prod_pos- A finite product of strictly positive real numbers is strictly positive.
Finset.filter_true_of_mem- Filtering a finite set by a predicate that holds for all members returns the set unchanged.
Set.pairwise_of_forall- If a binary relation holds for all pairs of elements, then every subset is pairwise related.
Finset.powerset_univ- The power set of the universal finset on a finite type equals the universal finset of subsets.
op_1355_empty_graph_equality_var_finset- For any finite set and strictly positive fugacities, the weighted hard-core variance of a linear observable over the full power set is the sum of the per-element Bernoulli variances w(v)^2 λ(v) / (1 + λ(v))^2.
- On paper, the fact that the variance of the linear observable is the sum of the per-vertex Bernoulli variances is immediate from the mutual independence of vertex indicators on an edgeless graph. In Lean, this is verified directly from first principles by induction on finite sets using recurrences for the partition function and the first two unnormalized moments, followed by clearing denominators and polynomial reduction.
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.
/-- On an edgeless graph all subsets occur, so the partition function is a full product. -/private lemma op_1355_empty_graph_equality_Zsum {V : Type*} [DecidableEq V] (lam : V → ℝ) (T : Finset V) : (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) = ∏ v ∈ T, (1 + lam v) := (Finset.prod_one_add (f := lam) T).symm/-- Recursion for the partition function when a vertex is adjoined to the ground set. -/private lemma op_1355_empty_graph_equality_Z_insert {V : Type*} [DecidableEq V] (lam _w : V → ℝ) (b : V) (T : Finset V) (hb : b ∉ T) : (∑ I ∈ (insert b T).powerset, ∏ v ∈ I, lam v) = (1 + lam b) * ∑ I ∈ T.powerset, ∏ v ∈ I, lam v := by rw [Finset.sum_powerset_insert hb] have h2 : ∀ I ∈ T.powerset, (∏ v ∈ insert b I, lam v) = lam b * ∏ v ∈ I, lam v := by intro I hI have hbi : b ∉ I := fun h => hb (Finset.mem_powerset.mp hI h) rw [Finset.prod_insert hbi] rw [Finset.sum_congr rfl h2, ← Finset.sum_add_distrib, Finset.mul_sum] apply Finset.sum_congr rfl intro x hx ring/-- Recursion for the first moment of the observable when a vertex is adjoined. -/private lemma op_1355_empty_graph_equality_A_insert {V : Type*} [DecidableEq V] (lam w : V → ℝ) (b : V) (T : Finset V) (hb : b ∉ T) : (∑ I ∈ (insert b T).powerset, (∏ v ∈ I, lam v) * (∑ v ∈ I, w v)) = (1 + lam b) * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (∑ v ∈ I, w v)) + lam b * w b * (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) := by rw [Finset.sum_powerset_insert hb] have h2 : ∀ I ∈ T.powerset, (∏ v ∈ insert b I, lam v) * (∑ v ∈ insert b I, w v) = lam b * ((∏ v ∈ I, lam v) * (∑ v ∈ I, w v)) + (lam b * w b) * (∏ v ∈ I, lam v) := by intro I hI have hbi : b ∉ I := fun h => hb (Finset.mem_powerset.mp hI h) rw [Finset.prod_insert hbi, Finset.sum_insert hbi] ring rw [Finset.sum_congr rfl h2, Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum] ring/-- Recursion for the second moment of the observable when a vertex is adjoined. -/private lemma op_1355_empty_graph_equality_B_insert {V : Type*} [DecidableEq V] (lam w : V → ℝ) (b : V) (T : Finset V) (hb : b ∉ T) : (∑ I ∈ (insert b T).powerset, (∏ v ∈ I, lam v) * (∑ v ∈ I, w v) ^ 2) = (1 + lam b) * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (∑ v ∈ I, w v) ^ 2) + 2 * lam b * w b * (∑ I ∈ T.powerset, (∏ v ∈ I, lam v) * (∑ v ∈ I, w v)) + lam b * (w b) ^ 2 * (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) := by rw [Finset.sum_powerset_insert hb] have h2 : ∀ I ∈ T.powerset, (∏ v ∈ insert b I, lam v) * (∑ v ∈ insert b I, w v) ^ 2 = lam b * ((∏ v ∈ I, lam v) * (∑ v ∈ I, w v) ^ 2) + (2 * lam b * w b) * ((∏ v ∈ I, lam v) * (∑ v ∈ I, w v)) + (lam b * (w b) ^ 2) * (∏ v ∈ I, lam v) := by intro I hI have hbi : b ∉ I := fun h => hb (Finset.mem_powerset.mp hI h) rw [Finset.prod_insert hbi, Finset.sum_insert hbi] ring rw [Finset.sum_congr rfl h2, Finset.sum_add_distrib, Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum, ← Finset.mul_sum] ring/-- The weighted hard-core variance over the full power set of `S` is the sum of theper-vertex Bernoulli variances. -/private lemma op_1355_empty_graph_equality_var_finset {V : Type*} [DecidableEq V] (lam w : V → ℝ) (hlam : ∀ v, 0 < lam v) (S : Finset V) : (∑ I ∈ S.powerset, (∏ v ∈ I, lam v) * (∑ v ∈ I, w v) ^ 2) / (∑ I ∈ S.powerset, ∏ v ∈ I, lam v) - ((∑ I ∈ S.powerset, (∏ v ∈ I, lam v) * (∑ v ∈ I, w v)) / (∑ I ∈ S.powerset, ∏ v ∈ I, lam v)) ^ 2 = ∑ v ∈ S, w v ^ 2 * lam v / (1 + lam v) ^ 2 := by induction S using Finset.induction_on with | empty => simp | insert b T hb ih => rw [op_1355_empty_graph_equality_B_insert lam w b T hb, op_1355_empty_graph_equality_A_insert lam w b T hb, op_1355_empty_graph_equality_Z_insert lam w b T hb, Finset.sum_insert hb, ← ih] have hZ : (∑ I ∈ T.powerset, ∏ v ∈ I, lam v) ≠ 0 := by rw [op_1355_empty_graph_equality_Zsum lam T] exact ne_of_gt (Finset.prod_pos (fun v _ => by linarith [hlam v])) have hu : (1 + lam b) ≠ 0 := by linarith [hlam b] field_simp ring/-- On an edgeless graph, the weighted hard-core variance equals the weighted closed-neighborhood bound. -/theorem op_1355_empty_graph_equality {V : Type*} [Fintype V] [DecidableEq V] (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v) : hardCoreWeightedVar (⊥ : SimpleGraph V) lam a = hardCoreWeightedClosedNeighborhoodBound (⊥ : SimpleGraph V) lam a := 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 : hardCoreWeightedVar (⊥ : SimpleGraph V) lam a = (∑ I ∈ (Finset.univ : Finset V).powerset, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v) ^ 2) / (∑ I ∈ (Finset.univ : Finset V).powerset, ∏ v ∈ I, lam v) - ((∑ I ∈ (Finset.univ : Finset V).powerset, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)) / (∑ I ∈ (Finset.univ : Finset V).powerset, ∏ v ∈ I, lam v)) ^ 2 := by simp only [hardCoreWeightedVar] rw [hfil, ← hpu] have hbound : hardCoreWeightedClosedNeighborhoodBound (⊥ : SimpleGraph V) lam a = ∑ v ∈ (Finset.univ : Finset V), a v ^ 2 * lam v / (1 + lam v) ^ 2 := by simp only [hardCoreWeightedClosedNeighborhoodBound] refine Finset.sum_congr rfl fun v _ => ?_ simp rw [hvar, hbound, op_1355_empty_graph_equality_var_finset lam a hlam Finset.univ]