AFTD Auto-Formalizing Theoretical Domains

op_1355_claw_strict_variance_violation

theoremverifiedformalization

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.

  1. 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.

    lines 8–11

    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
  2. 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.

    lines 26–27

    lemma indeps702 : ({I | G702.IsIndepSet (↑I : Set V702)} : Finset (Finset V702)) = sets702 := by
      decide
  3. 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.

    lines 29–35

    uses indeps702, Finset.sum_insert, Finset.prod_insert

    lemma 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
  4. 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.

    lines 38–43

    uses SimpleGraph.mem_neighborFinset

      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]
  5. 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}$.

    lines 44–47

    uses Finset.sum_insert, Fintype.sum_sum_type, Fin.sum_univ_succ, Fin.sum_univ_zero

      simp (disch := decide) [hardCoreWeightedClosedNeighborhoodBound, lam702, a702,
        Fintype.sum_sum_type, Fin.sum_univ_succ, Fin.sum_univ_zero, hneigh,
        Finset.sum_insert]
      <;> norm_num
  6. 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).

    line 54

      refine ⟨lam702, ?_, a702, ?_, ?_⟩
  7. 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.

    line 55

      · intro v; cases v <;> norm_num [lam702]
  8. 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.

    line 56

      · intro v; cases v <;> norm_num [a702]
  9. 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}$.

    line 57

    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}$.

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 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
See it in the graphDiscuss this resultChallenge it