op_1355_claw_strict_variance_violation
On the complete bipartite claw graph completeBipartiteGraph (Fin 1) (Fin 3), there exist positive vertex fugacities lam and nonnegative observable weights a such that the weighted hard-core variance hardCoreWeightedVar is strictly less than the weighted closed-neighborhood bound hardCoreWeightedClosedNeighborhoodBound.
Statement
theorem op_1355_claw_strict_variance_violation :
∃ (lam : Fin 1 ⊕ Fin 3 → ℝ) (hlam : ∀ v, 0 < lam v) (a : Fin 1 ⊕ Fin 3 → ℝ) (ha : ∀ v, 0 ≤ a v),
hardCoreWeightedVar (completeBipartiteGraph (Fin 1) (Fin 3)) lam a <
hardCoreWeightedClosedNeighborhoodBound (completeBipartiteGraph (Fin 1) (Fin 3)) lam a- Formalizes
- knowledgebase
- 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
There exist fugacities $\lambda : \text{Fin } 1 \oplus \text{Fin } 3 \to \mathbb{R}$ with $\lambda(v) > 0$ for all $v$, and weights $a : \text{Fin } 1 \oplus \text{Fin } 3 \to \mathbb{R}$ with $a(v) \ge 0$ for all $v$, such that the hard-core weighted variance on the complete bipartite graph $K_{1, 3} = \text{completeBipartiteGraph}(\text{Fin } 1, \text{Fin } 3)$ with parameters $\lambda$ and $a$ is strictly less than the closed-neighborhood bound hardCoreWeightedClosedNeighborhoodBound on $K_{1, 3}$ with parameters $\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
To show that the weighted hard-core variance can be strictly less than the closed-neighborhood bound on the claw graph $K_{1,3}$, we construct explicit fugacities (1 at the center, 100 at each of the three leaves) and observable weights (1 at the center, 0 at the leaves). By exhaustively determining all nine independent sets of $K_{1,3}$, the partition function and expectations are computed explicitly, yielding a variance of $\frac{1}{1030302} - \left(\frac{1}{1030302}\right)^2$. In contrast, the closed-neighborhood bound evaluates to $\frac{1}{91204}$, and the strict inequality is verified by rational arithmetic.
Adjacency in the complete bipartite graph $K_{1,3}$ is decidable.
In the complete bipartite graph $K_{1,3}$, two vertices are adjacent if and only if one is the center (the left component `Fin 1`) and the other is a leaf (the right component `Fin 3`). This reduces adjacency to a boolean condition whose decidability is inferred automatically by typeclass resolution.
local instance : DecidableRel G702.Adj := fun v w => by change Decidable ((v.isLeft = true ∧ w.isRight = true) ∨ (v.isRight = true ∧ w.isLeft = true)) infer_instance
The independent sets of $K_{1,3}$ are precisely the 9 sets enumerated in `sets702`. automation
Since $K_{1,3}$ has only 4 vertices, the decision procedure `decide` exhaustively evaluates all $2^4 = 16$ candidate subsets to confirm that the independent sets are the empty set, the singleton center $\{c\}$, and all 7 non-empty subsets of the three mutually non-adjacent leaves.
lemma indeps702 : ({I | G702.IsIndepSet (↑I : Set V702)} : Finset (Finset V702)) = sets702 := by decide
The weighted hard-core variance on $K_{1,3}$ with fugacities `lam702` and weights `a702` is $\frac{1}{1030302} - \left(\frac{1}{1030302}\right)^2$. automation
Unfolding `hardCoreWeightedVar` and rewriting with `indeps702` substitutes the 9 independent sets. The partition function evaluates to $Z = 1 + 1 + 3 \times 100 + 3 \times 100^2 + 100^3 = 1030302$. Since the observable $a$ is 1 at the center and 0 on all leaves, the sum of weights is 1 on $\{c\}$ and 0 on every other independent set, giving expectations $E_1 = E_2 = \frac{1}{1030302}$, so $E_2 - E_1^2$ yields the claimed variance.
uses
indeps702,Finset.sum_insert,Finset.prod_insertlemma var702 : hardCoreWeightedVar G702 lam702 a702 = (1 : ℝ) / 1030302 - (1 / 1030302)^2 := by classical unfold hardCoreWeightedVar rw [indeps702] simp (disch := decide) [sets702, c702, l702, lam702, a702, Finset.sum_insert, Finset.prod_insert] <;> norm_num
The open neighborhood of the center vertex consists of the three leaf vertices. automation
By extensionality on vertices, the center vertex `Sum.inl 0` is not adjacent to itself, while each of the three leaf vertices `Sum.inr i` is adjacent to the center in the bipartite graph $K_{1,3}$, as verified by case analysis.
uses
SimpleGraph.mem_neighborFinsetclassical have hneigh : G702.neighborFinset (Sum.inl 0) = {Sum.inr 0, Sum.inr 1, Sum.inr 2} := by ext v cases v with | inl x => fin_cases x <;> simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph] | inr x => fin_cases x <;> simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph]
The weighted closed-neighborhood bound on $K_{1,3}$ with `lam702` and `a702` is $\frac{1}{91204}$. automation
In the definition of `hardCoreWeightedClosedNeighborhoodBound`, the terms for the three leaves vanish because $a(l_i) = 0$. For the center vertex $c$, $a(c) = 1$, $\lambda(c) = 1$, and its closed neighborhood has sum of fugacities $\lambda(c) + \sum_{i=0}^2 \lambda(l_i) = 1 + 300 = 301$. The denominator is $(1 + 301)^2 = 302^2 = 91204$, so the bound evaluates to $\frac{1}{91204}$.
uses
Finset.sum_insert,Fintype.sum_sum_type,Fin.sum_univ_succ,Fin.sum_univ_zerosimp (disch := decide) [hardCoreWeightedClosedNeighborhoodBound, lam702, a702, Fintype.sum_sum_type, Fin.sum_univ_succ, Fin.sum_univ_zero, hneigh, Finset.sum_insert] <;> norm_num
Provide explicit fugacities `lam702` and observable weights `a702` as witnesses.
We instantiate the existential quantifiers in the theorem with `lam702` (assigning 1 to the center vertex and 100 to each leaf) and `a702` (assigning 1 to the center and 0 to each leaf).
refine ⟨lam702, ?_, a702, ?_, ?_⟩The fugacities `lam702` are strictly positive everywhere. automation
Evaluating `lam702` by cases on vertices gives $1 > 0$ for the center and $100 > 0$ for the leaves.
· intro v; cases v <;> norm_num [lam702]
The observable weights `a702` are nonnegative everywhere. automation
Evaluating `a702` by cases on vertices gives $1 \ge 0$ for the center and $0 \ge 0$ for the leaves.
· intro v; cases v <;> norm_num [a702]
The variance is strictly less than the closed-neighborhood bound. automation
Rewriting with the precomputed values `var702` and `bound702` reduces the goal to $\frac{1}{1030302} - \left(\frac{1}{1030302}\right)^2 < \frac{1}{91204}$, which is verified by rational arithmetic since $\approx 9.7 \times 10^{-7} < 1.1 \times 10^{-5}$.
uses
var702,bound702· rw [var702, bound702]; norm_num
indeps702- The collection of all independent sets of the bipartite graph $G_{702}$ ($K_{1,3}$) is equal to the finite set `sets702` of 9 subsets.
Finset.sum_insert- If an element $a$ is not in a finite set $s$, the sum of $f$ over $\{a\} \cup s$ equals $f(a)$ plus the sum of $f$ over $s$.
Finset.prod_insert- If an element $a$ is not in a finite set $s$, the product of $f$ over $\{a\} \cup s$ equals $f(a)$ times the product of $f$ over $s$.
SimpleGraph.mem_neighborFinset- A vertex $w$ belongs to the neighbor finset of $v$ if and only if $v$ and $w$ are adjacent in the graph.
Fintype.sum_sum_type- The sum of a function over a disjoint sum type $\alpha_1 \oplus \alpha_2$ equals the sum over $\alpha_1$ plus the sum over $\alpha_2$.
Fin.sum_univ_succ- The sum of a function over $\mathrm{Fin}(n+1)$ equals its value at 0 plus the sum of the remaining terms over $\mathrm{Fin}(n)$.
Fin.sum_univ_zero- The sum of any function over the empty index set $\mathrm{Fin}(0)$ is zero.
var702- The weighted hard-core variance on $K_{1,3}$ with fugacities `lam702` and weights `a702` evaluates to $\frac{1}{1030302} - \left(\frac{1}{1030302}\right)^2$.
bound702- The weighted closed-neighborhood bound on $K_{1,3}$ with fugacities `lam702` and weights `a702` evaluates to $\frac{1}{91204}$.
- The classification of all independent sets of $K_{1,3}$ (`indeps702`) is discharged entirely by finite exhaustive evaluation (`decide`).
- The verification of the neighborhood of the center vertex and the evaluation of the sums defining the variance and closed-neighborhood bound rely heavily on automated normalization and simplification (`simp` and `norm_num`).
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.
open SimpleGraphopen scoped Classicalset_option maxRecDepth 10000set_option maxHeartbeats 1000000abbrev V702 := Fin 1 ⊕ Fin 3abbrev G702 := completeBipartiteGraph (Fin 1) (Fin 3)local instance : DecidableRel G702.Adj := fun v w => by change Decidable ((v.isLeft = true ∧ w.isRight = true) ∨ (v.isRight = true ∧ w.isLeft = true)) infer_instancedef c702 : V702 := Sum.inl 0def l702 (i : Fin 3) : V702 := Sum.inr idef lam702 : V702 → ℝ := fun v => match v with | Sum.inl _ => 1 | Sum.inr _ => 100def a702 : V702 → ℝ := fun v => match v with | Sum.inl _ => 1 | Sum.inr _ => 0def sets702 : Finset (Finset V702) := {∅, {c702}, {l702 0}, {l702 1}, {l702 2}, {l702 0, l702 1}, {l702 0, l702 2}, {l702 1, l702 2}, {l702 0, l702 1, l702 2}}lemma indeps702 : ({I | G702.IsIndepSet (↑I : Set V702)} : Finset (Finset V702)) = sets702 := by decidelemma var702 : hardCoreWeightedVar G702 lam702 a702 = (1 : ℝ) / 1030302 - (1 / 1030302)^2 := by classical unfold hardCoreWeightedVar rw [indeps702] simp (disch := decide) [sets702, c702, l702, lam702, a702, Finset.sum_insert, Finset.prod_insert] <;> norm_numlemma bound702 : hardCoreWeightedClosedNeighborhoodBound G702 lam702 a702 = (1 : ℝ) / 91204 := by classical have hneigh : G702.neighborFinset (Sum.inl 0) = {Sum.inr 0, Sum.inr 1, Sum.inr 2} := by ext v cases v with | inl x => fin_cases x <;> simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph] | inr x => fin_cases x <;> simp [SimpleGraph.mem_neighborFinset, completeBipartiteGraph] simp (disch := decide) [hardCoreWeightedClosedNeighborhoodBound, lam702, a702, Fintype.sum_sum_type, Fin.sum_univ_succ, Fin.sum_univ_zero, hneigh, Finset.sum_insert] <;> norm_num/-- The claw graph K_{1,3} strictly violates the weighted hard-core closed-neighborhood variance bound for suitable positive fugacities and nonnegative observable weights. -/theorem op_1355_claw_strict_variance_violation : ∃ (lam : Fin 1 ⊕ Fin 3 → ℝ) (hlam : ∀ v, 0 < lam v) (a : Fin 1 ⊕ Fin 3 → ℝ) (ha : ∀ v, 0 ≤ a v), hardCoreWeightedVar (completeBipartiteGraph (Fin 1) (Fin 3)) lam a < hardCoreWeightedClosedNeighborhoodBound (completeBipartiteGraph (Fin 1) (Fin 3)) lam a := by refine ⟨lam702, ?_, a702, ?_, ?_⟩ · intro v; cases v <;> norm_num [lam702] · intro v; cases v <;> norm_num [a702] · rw [var702, bound702]; norm_num