AFTD Auto-Formalizing Theoretical Domains

op_1355_complete_graph_variance_ge_bound

theoremverifiedformalization

On the complete 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 is at least the weighted closed-neighborhood bound hardCoreWeightedClosedNeighborhoodBound (⊤ : SimpleGraph V) lam a.

Statement

theorem op_1355_complete_graph_variance_ge_bound
    {V : Type*} [Fintype V] [DecidableEq V]
    (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v) :
    hardCoreWeightedClosedNeighborhoodBound (⊤ : SimpleGraph V) lam a ≤
      hardCoreWeightedVar (⊤ : 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,…
Used by 1

Read back from the Lean

For any finite type $V$ with decidable equality, any activity/fugacity function $\lambda : V \to \mathbb{R}$ such that $\lambda(v) > 0$ for all $v \in V$, and any weight function $a : V \to \mathbb{R}$ such that $a(v) \ge 0$ for all $v \in V$, the hard-core weighted closed neighborhood bound on the complete graph $\top$ on $V$ with fugacities $\lambda$ and weights $a$ is less than or equal to the hard-core weighted variance on the complete graph $\top$ on $V$ with fugacities $\lambda$ and weights $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 the complete graph, the independent sets are just the empty set and the singletons. This allows explicit evaluation of both the hard-core variance and the closed-neighborhood bound in terms of moments of the observable weights. The desired variance lower bound then reduces to an algebraic inequality on real fractions, which holds by weighted Cauchy-Schwarz.

  1. The weighted closed-neighborhood bound is at most the weighted variance.

    By rewriting both sides and applying the scalar inequality with weighted Cauchy-Schwarz.

    lines 116–119

    uses op_1355_complete_graph_closed_neighborhood_top_bound, op_1355_complete_graph_hard_core_weighted_var_top, op_1355_complete_graph_div_sq_le_div_sub_div_sq, op_1355_complete_graph_weighted_cauchy_schwarz

      rw [op_1355_complete_graph_closed_neighborhood_top_bound, op_1355_complete_graph_hard_core_weighted_var_top]
      apply op_1355_complete_graph_div_sq_le_div_sub_div_sq
      · exact Finset.sum_nonneg fun v _ => le_of_lt (hlam v)
      · exact op_1355_complete_graph_weighted_cauchy_schwarz Finset.univ lam a fun v _ => le_of_lt (hlam v)

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

lemma op_1355_complete_graph_weighted_cauchy_schwarz {V : Type*} (s : Finset V) (p q : V → ℝ) (hp : ∀ v ∈ s, 0 ≤ p v) :    (∑ v ∈ s, p v * q v) ^ 2 ≤ (∑ v ∈ s, p v) * (∑ v ∈ s, p v * q v ^ 2) := by  have h := Finset.sum_mul_sq_le_sq_mul_sq s (fun v => Real.sqrt (p v)) (fun v => Real.sqrt (p v) * q v)  have h1 : (∑ v ∈ s, (Real.sqrt (p v)) ^ 2) = ∑ v ∈ s, p v :=    Finset.sum_congr rfl fun v hv => Real.sq_sqrt (hp v hv)  have h2 : (∑ v ∈ s, (Real.sqrt (p v) * q v) ^ 2) = ∑ v ∈ s, p v * q v ^ 2 := by    refine Finset.sum_congr rfl fun v hv => ?_    rw [mul_pow, Real.sq_sqrt (hp v hv)]  have h3 : (∑ v ∈ s, Real.sqrt (p v) * (Real.sqrt (p v) * q v)) = ∑ v ∈ s, p v * q v := by    refine Finset.sum_congr rfl fun v hv => ?_    rw [← mul_assoc, ← sq, Real.sq_sqrt (hp v hv)]  rw [h1, h2, h3] at h  exact hlemma op_1355_complete_graph_indep_top_eq {V : Type*} [Fintype V] [DecidableEq V] :    ({I | (⊤ : SimpleGraph V).IsIndepSet (↑I : Set V)} : Finset (Finset V)) =      insert ∅ (Finset.univ.image (fun v : V => ({v} : Finset V))) := by  ext I  rw [Finset.mem_filter]  simp only [Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_image]  constructor  · intro h    rcases Finset.eq_empty_or_nonempty I with rfl | ⟨v, hv⟩    · left; rfl    · right; refine ⟨v, ?_⟩      ext u      simp only [Finset.mem_singleton]      constructor      · rintro rfl; exact hv      · intro hu        by_contra hne        exact h hu hv hne hne  · rintro (rfl | ⟨v, rfl⟩)    · intro u hu; simp at hu    · intro u hu w hw hne      simp only [Finset.coe_singleton, Set.mem_singleton_iff] at hu hw      subst hu hw      exact (hne rfl).elimlemma op_1355_complete_graph_empty_not_mem_image_singleton {V : Type*} [Fintype V] [DecidableEq V] :    (∅ : Finset V) ∉ Finset.univ.image (fun v : V => ({v} : Finset V)) := by  simp only [Finset.mem_image, Finset.mem_univ, true_and]  rintro ⟨v, hv⟩  exact Finset.ne_empty_of_mem (Finset.mem_singleton_self v) hvlemma op_1355_complete_graph_sum_top_indep_lam {V : Type*} [Fintype V] [DecidableEq V] (lam : V → ℝ) :    (∑ I ∈ ({I | (⊤ : SimpleGraph V).IsIndepSet (↑I : Set V)} : Finset (Finset V)), ∏ v ∈ I, lam v) =      1 + ∑ v, lam v := by  rw [op_1355_complete_graph_indep_top_eq, Finset.sum_insert op_1355_complete_graph_empty_not_mem_image_singleton]  simp only [Finset.prod_empty]  congr 1  rw [Finset.sum_image Finset.singleton_injective.injOn]  simp only [Finset.prod_singleton]lemma op_1355_complete_graph_sum_top_indep_lam_mul_a {V : Type*} [Fintype V] [DecidableEq V] (lam a : V → ℝ) :    (∑ I ∈ ({I | (⊤ : SimpleGraph V).IsIndepSet (↑I : Set V)} : Finset (Finset V)),      (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) =      ∑ v, lam v * a v := by  rw [op_1355_complete_graph_indep_top_eq, Finset.sum_insert op_1355_complete_graph_empty_not_mem_image_singleton]  simp only [Finset.prod_empty, Finset.sum_empty, mul_zero, zero_add]  rw [Finset.sum_image Finset.singleton_injective.injOn]  simp only [Finset.prod_singleton, Finset.sum_singleton]lemma op_1355_complete_graph_sum_top_indep_lam_mul_sq {V : Type*} [Fintype V] [DecidableEq V] (lam a : V → ℝ) :    (∑ I ∈ ({I | (⊤ : SimpleGraph V).IsIndepSet (↑I : Set V)} : Finset (Finset V)),      (∏ v ∈ I, lam v) * (∑ v ∈ I, a v) ^ 2) =      ∑ v, lam v * (a v) ^ 2 := by  rw [op_1355_complete_graph_indep_top_eq, Finset.sum_insert op_1355_complete_graph_empty_not_mem_image_singleton]  simp only [Finset.prod_empty, Finset.sum_empty, sq, mul_zero, zero_add]  rw [Finset.sum_image Finset.singleton_injective.injOn]  simp only [Finset.prod_singleton, Finset.sum_singleton]lemma op_1355_complete_graph_closed_neighborhood_top_bound {V : Type*} [Fintype V] [DecidableEq V]    (lam a : V → ℝ) :    hardCoreWeightedClosedNeighborhoodBound (⊤ : SimpleGraph V) lam a =      (∑ v, lam v * a v ^ 2) / (1 + ∑ u, lam u) ^ 2 := by  unfold hardCoreWeightedClosedNeighborhoodBound  have h_nhbr : ∀ v : V, insert v ((⊤ : SimpleGraph V).neighborFinset v) = Finset.univ := by    intro v    ext u    simp  simp_rw [h_nhbr]  rw [← Finset.sum_div]  congr 1  refine Finset.sum_congr rfl fun v _ => mul_comm _ _lemma op_1355_complete_graph_hard_core_weighted_var_top {V : Type*} [Fintype V] [DecidableEq V]    (lam a : V → ℝ) :    hardCoreWeightedVar (⊤ : SimpleGraph V) lam a =      (∑ v, lam v * a v ^ 2) / (1 + ∑ v, lam v) -        ((∑ v, lam v * a v) / (1 + ∑ v, lam v)) ^ 2 := by  unfold hardCoreWeightedVar  dsimp only  rw [op_1355_complete_graph_sum_top_indep_lam, op_1355_complete_graph_sum_top_indep_lam_mul_a, op_1355_complete_graph_sum_top_indep_lam_mul_sq]lemma op_1355_complete_graph_div_sq_le_div_sub_div_sq (S M1 M2 : ℝ) (hS : 0 ≤ S)    (hCS : M1 ^ 2 ≤ S * M2) :    M2 / (1 + S) ^ 2 ≤ M2 / (1 + S) - (M1 / (1 + S)) ^ 2 := by  have hpos : 0 < 1 + S := by linarith  have hpos2 : 0 < (1 + S) ^ 2 := by positivity  rw [div_pow]  have h_eq : M2 / (1 + S) = (M2 * (1 + S)) / (1 + S) ^ 2 := by    rw [sq]    exact (mul_div_mul_right M2 (1 + S) (ne_of_gt hpos)).symm  rw [h_eq, ← sub_div, div_le_div_iff_of_pos_right hpos2]  calc M2 = M2 * 1 := (mul_one M2).symm  _ ≤ M2 * 1 + (S * M2 - M1 ^ 2) := by linarith  _ = M2 * (1 + S) - M1 ^ 2 := by ring/-- On a complete graph, the weighted hard-core variance is at least the weighted closed-neighborhood bound by Cauchy-Schwarz. -/theorem op_1355_complete_graph_variance_ge_bound    {V : Type*} [Fintype V] [DecidableEq V]    (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v) :    hardCoreWeightedClosedNeighborhoodBound (⊤ : SimpleGraph V) lam a ≤      hardCoreWeightedVar (⊤ : SimpleGraph V) lam a := by  rw [op_1355_complete_graph_closed_neighborhood_top_bound, op_1355_complete_graph_hard_core_weighted_var_top]  apply op_1355_complete_graph_div_sq_le_div_sub_div_sq  · exact Finset.sum_nonneg fun v _ => le_of_lt (hlam v)  · exact op_1355_complete_graph_weighted_cauchy_schwarz Finset.univ lam a fun v _ => le_of_lt (hlam v)
See it in the graphDiscuss this resultChallenge it