AFTD Auto-Formalizing Theoretical Domains

op_1355_clique_components_variance_ge_bound

theoremverifiedformalization

For any finite simple graph G on a finite type V with decidable equality whose connected components are all cliques, and for all positive vertex fugacities lam and all nonnegative observable weights a, the weighted hard-core closed-neighborhood bound hardCoreWeightedClosedNeighborhoodBound G lam a is at most the weighted hard-core variance hardCoreWeightedVar G lam a.

Statement

theorem op_1355_clique_components_variance_ge_bound
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v)
    (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) :
    hardCoreWeightedClosedNeighborhoodBound G lam a ≤ hardCoreWeightedVar G lam a
Formalizes
knowledgebase
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7

Read back from the Lean

For any finite type $V$ with decidable equality, any simple graph $G$ on $V$ with decidable adjacency, any positive weight function $\lambda : V \to \mathbb{R}$ (i.e., $\lambda(v) > 0$ for all $v \in V$), and any non-negative function $a : V \to \mathbb{R}$ (i.e., $a(v) \ge 0$ for all $v \in V$): if every connected component of $G$ is a clique (that is, for every connected component $c \in G\text{.ConnectedComponent}$, the vertex set $c\text{.supp}$ induces a clique in $G$), then the weighted closed-neighborhood bound hardCoreWeightedClosedNeighborhoodBound G lam a is less than or equal to the variance under the hard-core model hardCoreWeightedVar G lam 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

The theorem establishes that for any finite graph whose connected components are cliques, the weighted hard-core closed-neighborhood bound is at most the weighted hard-core variance. Because each component is a clique, an independent set contains at most one vertex per component, allowing independent sets and their weight polynomials to be decomposed component by component. This product structure yields step recurrences for the partition function and its first two moments, which via an additive recurrence lemma decompose the total variance into a sum of component variances. Likewise, since the closed neighborhood of any vertex is its entire component, the closed-neighborhood bound also decomposes as a sum of complete-graph bounds over the components. Comparing the two sums term by term using the Cauchy-Schwarz inequality and an algebraic inequality for complete graphs yields the result.

  1. For distinct vertices u and v in a new component c ∉ S, the families of sets obtained by inserting u versus inserting v into independent sets supported on S are disjoint.

    Suppose toward a contradiction that some set belongs to both image families, so insert u J = insert v K for J, K ∈ cliqueIndep G S. Then u ∈ insert v K, which means u = v (contradicting u ≠ v) or u ∈ K. But every vertex of K has its component in S, which would imply c ∈ S, contradicting c ∉ S.

    lines 17–35

    uses Finset.disjoint_left, Finset.mem_insert_self

      intro u hu v hv hne
      simp only [compFiber, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hu hv
      dsimp [Function.onFun]
      rw [Finset.disjoint_left]
      intro I hI
      simp only [cliqueIndep, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at hI
      rcases hI with ⟨J, ⟨hJ, -⟩, rfl⟩
      intro h_mem
      simp only [cliqueIndep, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at h_mem
      rcases h_mem with ⟨K, ⟨hK, -⟩, heq⟩
      have hu_in : u ∈ insert v K := by
        rw [heq]
        exact Finset.mem_insert_self u J
      simp only [Finset.mem_insert] at hu_in
      rcases hu_in with rfl | huK
      · exact hne rfl
      · have hcomp := hK u huK
        rw [hu] at hcomp
        exact hc hcomp
  2. For any vertex u in a new component c ∉ S, the insertion map J ↦ insert u J is injective on cliqueIndep G S.

    If insert u J = insert u K, then since all vertices of J and K have components in S while u has component c ∉ S, u cannot belong to J or K. Therefore, any element x belongs to J if and only if it belongs to K, which proves J = K.

    lines 40–60

      simp only [compFiber, Finset.mem_filter, Finset.mem_univ, true_and] at hu
      intro J hJ K hK heq
      simp only [cliqueIndep, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hJ hK
      have huJ : u ∉ J := by
        intro h
        have := hJ.1 u h
        rw [hu] at this
        exact hc this
      have huK : u ∉ K := by
        intro h
        have := hK.1 u h
        rw [hu] at this
        exact hc this
      ext x
      have hx : x ∈ insert u J ↔ x ∈ insert u K := by rw [heq]
      simp only [Finset.mem_insert] at hx
      by_cases hxu : x = u
      · subst hxu
        simp [huJ, huK]
      · simp [hxu] at hx
        exact hx
  3. Every independent set supported on S ∪ {c} either is supported entirely on S, or is obtained by inserting a unique vertex from c into an independent set supported on S.

    Let I be an independent set supported on S ∪ {c}. We case split on whether I contains a vertex in component c. If it contains some u with component c, then because the component map is injective on I, u is the unique such vertex. Removing u leaves an independent set I \ {u} whose vertices all lie in S, so I = insert u (I \ {u}). If I contains no vertex in c, all its vertices already lie in S.

    lines 65–94

    uses Finset.insert_erase

      classical
      ext I
      simp only [cliqueIndep, Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and,
        Finset.mem_biUnion, Finset.mem_image]
      constructor
      · rintro ⟨hS, hinj⟩
        by_cases he : ∃ u ∈ I, G.connectedComponentMk u = c
        · obtain ⟨u,huI,huc⟩ := he
          right
          refine ⟨u, ?_, I.erase u, ?_, Finset.insert_erase huI⟩
          · simp [compFiber, huc]
          · constructor
            · intro v hv
              have hvI := (Finset.mem_erase.mp hv).2
              have hm := hS v hvI
              simp only [Finset.mem_insert] at hm
              rcases hm with hvc | hvS
              · have hvu := hinj hvI huI (hvc.trans huc.symm)
                exact ((Finset.mem_erase.mp hv).1 hvu).elim
              · exact hvS
            · intro v hv w hw heq
              exact hinj (Finset.mem_erase.mp hv).2 (Finset.mem_erase.mp hw).2 heq
        · left
          refine ⟨?_, hinj⟩
          intro v hv
          have hm := hS v hv
          simp only [Finset.mem_insert] at hm
          rcases hm with hvc | hvS
          · exact (he ⟨v,hv,hvc⟩).elim
          · exact hvS
  4. Conversely, any independent set supported on S, and any set formed by inserting a vertex from component c into an independent set supported on S, is an independent set supported on S ∪ {c}.

    In the first case, any independent set on S already has all vertices in S ⊆ S ∪ {c}. In the second case, inserting u ∈ c into J ∈ cliqueIndep G S adds a vertex outside S, so u ∉ J; the resulting set insert u J has all vertices in S ∪ {c}, and the component map remains injective because u is the only vertex mapping to c and J has no vertex mapping to c.

    lines 95–120

    uses Finset.mem_insert_of_mem

      · rintro (⟨hS, hinj⟩ | ⟨u,hu,J,⟨hJ,hinj⟩,rfl⟩)
        · refine ⟨?_, hinj⟩
          intro v hv
          exact Finset.mem_insert_of_mem (hS v hv)
        · have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu
          have huJ : u ∉ J := by
            intro huJ
            apply hc
            simpa [huc] using hJ u huJ
          refine ⟨?_, ?_⟩
          · intro v hv
            simp only [Finset.mem_insert] at hv
            rcases hv with rfl | hv
            · simpa [huc]
            · exact Finset.mem_insert_of_mem (hJ v hv)
          · intro v hv w hw heq
            simp only [Finset.coe_insert, Set.mem_insert_iff] at hv hw
            rcases hv with rfl | hv <;> rcases hw with rfl | hw
            · rfl
            · have : G.connectedComponentMk w ∈ S := hJ w hw
              rw [← heq, huc] at this
              exact (hc this).elim
            · have : G.connectedComponentMk v ∈ S := hJ v hv
              rw [heq, huc] at this
              exact (hc this).elim
            · exact hinj hv hw heq
  5. The family of independent sets supported on S is disjoint from the union of families of sets containing a vertex from component c.

    Any set in the latter union contains a vertex u with component c. If it were also supported on S, the component of u would have to belong to S, which contradicts c ∉ S.

    lines 125–133

    uses Finset.disjoint_left, Finset.mem_insert_self

      classical
      apply Finset.disjoint_left.mpr
      intro I hI hnew
      obtain ⟨u,hu,himg⟩ := Finset.mem_biUnion.mp hnew
      obtain ⟨J,hJ,hJI⟩ := Finset.mem_image.mp himg
      subst I
      have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu
      have hI' := (Finset.mem_filter.mp hI).2.1 u (Finset.mem_insert_self u J)
      exact hc (huc ▸ hI')
  6. Any sum of a function over independent sets supported on S ∪ {c} splits into the sum over S plus a double sum over u ∈ c and independent sets on S with u inserted.

    By the decomposition lemma, cliqueIndep G (insert c S) is the disjoint union of cliqueIndep G S and the union over u ∈ c of the image families. Applying the disjoint union sum formula, the pairwise disjoint union sum formula over u ∈ c, and the image sum formula using injectivity of insertion gives the desired identity.

    lines 139–146

    uses cliqueIndep_insert_decomposition, Finset.sum_union, cliqueIndep_disjoint_old_new, Finset.sum_biUnion, cliqueIndep_pairwiseDisjoint, Finset.sum_image, cliqueIndep_insert_injOn

      classical
      rw [cliqueIndep_insert_decomposition G c S hc,
        Finset.sum_union (cliqueIndep_disjoint_old_new G c S hc),
        Finset.sum_biUnion (cliqueIndep_pairwiseDisjoint G c S hc)]
      congr 1
      apply Finset.sum_congr rfl
      intro u hu
      exact Finset.sum_image (cliqueIndep_insert_injOn G c S hc u hu)
  7. A vertex in a component c ∉ S cannot belong to any independent set supported on S.

    If u ∈ I where I ∈ cliqueIndep G S, then the component of u would belong to S, which contradicts c ∉ S.

    lines 150–153

      intro hui
      have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu
      have hS := (Finset.mem_filter.mp hI).2.1 u hui
      exact hc (huc ▸ hS)
  8. The partition function Z satisfies the step recurrence Z(S ∪ {c}) = (1 + ∑_{u ∈ c} λ(u)) * Z(S).

    Apply the sum decomposition to the product weight ∏_{v ∈ I} λ(v). For each term with u inserted, the weight factors as λ(u) * ∏_{v ∈ I} λ(v) because u ∉ I. Factoring the sum over u ∈ c out of the inner sum over I and combining with the base term Z(S) yields (1 + ∑_{u ∈ c} λ(u)) * Z(S).

    lines 159–171

    uses cliqueIndep_sum_insert, Finset.prod_insert, cliqueIndep_fresh

      classical
      rw [cliqueIndep_sum_insert G c S hc]
      have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S, ∏ v ∈ insert u I, lam v) =
          (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by
        rw [Finset.sum_mul]
        apply Finset.sum_congr rfl
        intro u hu
        rw [Finset.mul_sum]
        apply Finset.sum_congr rfl
        intro I hI
        exact Finset.prod_insert (cliqueIndep_fresh G c S hc u hu I hI)
      rw [h]
      ring
  9. The first-moment sum A satisfies the step recurrence A(S ∪ {c}) = (1 + ∑_{u ∈ c} λ(u)) * A(S) + (∑_{u ∈ c} λ(u) a(u)) * Z(S).

    Applying the sum decomposition to the first-moment terms, the sum ∑_{v ∈ insert u I} a(v) splits into a(u) + ∑_{v ∈ I} a(v) since u ∉ I. Distributing the product weight and regrouping sums yields (1 + ∑ λ(u)) * A(S) from the ∑_{v ∈ I} a(v) part, and (∑ λ(u) a(u)) * Z(S) from the a(u) part.

    lines 179–195

    uses cliqueIndep_sum_insert, Finset.prod_insert, Finset.sum_insert, cliqueIndep_fresh

      classical
      rw [cliqueIndep_sum_insert G c S hc]
      have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S,
          (∏ v ∈ insert u I, lam v) * ∑ v ∈ insert u I, a v) =
          (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) +
          (∑ u ∈ compFiber G c, lam u * a u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by
        rw [Finset.sum_mul, Finset.sum_mul, ← Finset.sum_add_distrib]
        apply Finset.sum_congr rfl
        intro u hu
        rw [Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib]
        apply Finset.sum_congr rfl
        intro I hI
        have hf := cliqueIndep_fresh G c S hc u hu I hI
        rw [Finset.prod_insert hf, Finset.sum_insert hf]
        ring
      rw [h]
      ring
  10. The second-moment sum B satisfies the step recurrence B(S ∪ {c}) = (1 + ∑_{u ∈ c} λ(u)) * B(S) + 2 * (∑_{u ∈ c} λ(u) a(u)) * A(S) + (∑_{u ∈ c} λ(u) a(u)^2) * Z(S).

    Expanding the square (a(u) + ∑_{v ∈ I} a(v))^2 into (∑ a(v))^2 + 2 a(u) ∑ a(v) + a(u)^2 and applying the sum decomposition produces three groups of terms corresponding to B(S), A(S), and Z(S) with the stated coefficients.

    lines 205–226

    uses cliqueIndep_sum_insert, Finset.prod_insert, Finset.sum_insert, cliqueIndep_fresh

      classical
      rw [cliqueIndep_sum_insert G c S hc]
      have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S,
          (∏ v ∈ insert u I, lam v) * (∑ v ∈ insert u I, a v)^2) =
          (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)^2) +
          2 * (∑ u ∈ compFiber G c, lam u * a u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) +
          (∑ u ∈ compFiber G c, lam u * a u^2) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by
        have htwo : 2 * (∑ u ∈ compFiber G c, lam u * a u) =
            ∑ u ∈ compFiber G c, 2 * (lam u * a u) := by rw [Finset.mul_sum]
        rw [htwo, Finset.sum_mul, Finset.sum_mul, Finset.sum_mul,
          ← Finset.sum_add_distrib, ← Finset.sum_add_distrib]
        apply Finset.sum_congr rfl
        intro u hu
        rw [Finset.mul_sum, Finset.mul_sum, Finset.mul_sum,
          ← Finset.sum_add_distrib, ← Finset.sum_add_distrib]
        apply Finset.sum_congr rfl
        intro I hI
        have hf := cliqueIndep_fresh G c S hc u hu I hI
        rw [Finset.prod_insert hf, Finset.sum_insert hf]
        ring
      rw [h]
      ring
  11. The collection of independent sets supported on the empty set of components consists solely of the empty set.

    Any set whose vertices have components in ∅ must be empty, and the empty set vacuously satisfies the injectivity and membership requirements.

    lines 236–244

    uses Finset.notMem_empty

      ext I
      simp only [cliqueIndep, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton]
      constructor
      · rintro ⟨h, -⟩
        ext x
        simp only [Finset.notMem_empty, iff_false]
        exact fun hx => Finset.notMem_empty _ (h x hx)
      · rintro rfl
        refine ⟨by simp, by simp [Set.InjOn]⟩
  12. When every connected component of G is a clique, cliqueIndep G Finset.univ equals the set of all independent sets of G.

    In a disjoint union of cliques, a subset of vertices is independent if and only if it contains at most one vertex from each component, which is precisely the injectivity of the component projection on that subset.

    lines 249–252

    uses simple_graph_clique_components_independent_iff_injective

      ext I
      simp only [cliqueIndep, Finset.mem_filter, Finset.mem_univ, true_and]
      rw [simple_graph_clique_components_independent_iff_injective G hclique]
      simp
  13. The partition function Z(S) is strictly positive for positive vertex fugacities λ > 0.

    The empty set belongs to cliqueIndep G S and has weight 1. Since all weights are non-negative, the total sum is at least 1, hence strictly positive.

    lines 256–262

    uses zero_lt_one, Finset.single_le_sum

      unfold cliqueZ
      refine lt_of_lt_of_le zero_lt_one ?_
      have h_empty : (∏ v ∈ (∅ : Finset V), lam v) = 1 := Finset.prod_empty
      rw [← h_empty]
      have hem : (∅ : Finset V) ∈ cliqueIndep G S := by simp [cliqueIndep, Set.InjOn]
      exact Finset.single_le_sum (f := fun I : Finset V => ∏ v ∈ I, lam v)
        (fun I _ => Finset.prod_nonneg fun v _ => le_of_lt (hlam v)) hem
  14. The weighted closed-neighborhood bound splits into a sum over connected components.

    In a graph whose components are cliques, the closed neighborhood of any vertex v is the entire connected component containing v. Grouping the sum fiberwise by connected components, the denominator is constant on each component and factors out, giving the componentwise sum.

    lines 269–281

    uses Finset.sum_fiberwise, Finset.sum_div, simple_graph_clique_components_closed_neighborhood

      classical
      unfold hardCoreWeightedClosedNeighborhoodBound
      rw [← Finset.sum_fiberwise Finset.univ G.connectedComponentMk
        (fun v => (a v ^ 2 * lam v) / (1 + ∑ u ∈ insert v (G.neighborFinset v), lam u)^2)]
      apply Finset.sum_congr rfl
      intro c hc
      rw [Finset.sum_div]
      apply Finset.sum_congr rfl
      intro v hv
      have hvc : G.connectedComponentMk v = c := by simpa [compFiber] using hv
      rw [simple_graph_clique_components_closed_neighborhood G hclique v, hvc]
      change (a v^2 * lam v) / (1 + ∑ u ∈ compFiber G c, lam u)^2 = _
      ring
  15. The weighted hard-core variance decomposes as a sum of component variances.

    By cliqueIndep_univ, the total variance is B(univ)/Z(univ) - (A(univ)/Z(univ))^2. The step recurrences for Z, A, and B match the hypotheses of the general additive variance recurrence theorem finite_variance_recurrence_additive with base values A(∅) = B(∅) = 0 and strictly positive partition function. Applying this recurrence expresses the total variance as the sum over all components of the variance on each component.

    lines 290–311

    uses cliqueZ_pos, cliqueIndep_empty, finite_variance_recurrence_additive, cliqueIndep_Z_step, cliqueIndep_A_step, cliqueIndep_B_step, cliqueIndep_univ

      classical
      have hZ : ∀ S, cliqueZ G lam S ≠ 0 := fun S => ne_of_gt (cliqueZ_pos G lam hlam S)
      have hs : ∀ c, 1 + (∑ v ∈ compFiber G c, lam v) ≠ 0 := by
        intro c
        have h : 0 ≤ ∑ v ∈ compFiber G c, lam v := Finset.sum_nonneg fun v _ => le_of_lt (hlam v)
        linarith
      have hb : cliqueA G lam a ∅ = 0 ∧ cliqueB G lam a ∅ = 0 := by
        simp [cliqueA, cliqueB, cliqueIndep_empty]
      have hrec := finite_variance_recurrence_additive (cliqueZ G lam) (cliqueA G lam a) (cliqueB G lam a)
        (fun c => ∑ v ∈ compFiber G c, lam v)
        (fun c => ∑ v ∈ compFiber G c, lam v * a v)
        (fun c => ∑ v ∈ compFiber G c, lam v * a v^2)
        hZ hs hb
        (fun c S hc => cliqueIndep_Z_step G lam c S hc)
        (fun c S hc => cliqueIndep_A_step G lam a c S hc)
        (fun c S hc => cliqueIndep_B_step G lam a c S hc) Finset.univ
      have hv : hardCoreWeightedVar G lam a =
          cliqueB G lam a Finset.univ / cliqueZ G lam Finset.univ -
            (cliqueA G lam a Finset.univ / cliqueZ G lam Finset.univ)^2 := by
        unfold hardCoreWeightedVar cliqueB cliqueA cliqueZ
        rw [cliqueIndep_univ G hclique]
      rw [hv, hrec]
  16. The closed-neighborhood bound is at most the hard-core variance.

    Both the closed-neighborhood bound and the variance decompose as sums over the connected components of G. For each component c, with S = ∑ λ(v), M1 = ∑ λ(v) a(v), and M2 = ∑ λ(v) a(v)^2, Cauchy-Schwarz gives M1^2 ≤ S * M2. The complete-graph variance inequality op_1355_complete_graph_div_sq_le_div_sub_div_sq then implies that the component closed-neighborhood bound M2 / (1+S)^2 is at most the component variance M2 / (1+S) - (M1 / (1+S))^2. Summing these inequalities over all components completes the proof.

    lines 317–322

    uses cliqueBound_eq, cliqueVar_eq_sum, Finset.sum_le_sum, op_1355_complete_graph_div_sq_le_div_sub_div_sq, op_1355_complete_graph_weighted_cauchy_schwarz

      rw [cliqueBound_eq G hclique lam a, cliqueVar_eq_sum G hclique lam a hlam]
      apply Finset.sum_le_sum
      intro c hc
      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 (compFiber G c) lam a fun v _ => le_of_lt (hlam v)
  17. On any finite graph whose connected components are cliques, the weighted closed-neighborhood bound is at most the weighted hard-core variance.

    This main theorem directly invokes In703.in703_main.

    line 332

    uses In703.in703_main

      exact In703.in703_main G lam hlam a ha hclique
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_insert_self
An element always belongs to the set obtained by inserting it into any finite set.
Finset.insert_erase
Inserting an element into a finite set after erasing it recovers the original set, provided the element was originally in the set.
Finset.mem_insert_of_mem
Any element of a finite set is also an element of the set obtained by inserting an additional element.
cliqueIndep_insert_decomposition
Independent sets supported on S ∪ {c} partition into those supported on S and those obtained by inserting some vertex u from component c into an independent set supported on S.
Finset.sum_union
The sum of a function over the union of two disjoint finite sets is the sum of the sums over each set.
cliqueIndep_disjoint_old_new
The family of independent sets supported on S is disjoint from the family of sets obtained by inserting a vertex from a component c ∉ S.
Finset.sum_biUnion
The sum of a function over a pairwise disjoint indexed union of finite sets equals the iterated sum over indices and member sets.
cliqueIndep_pairwiseDisjoint
For c ∉ S, inserting distinct vertices from component c into sets of cliqueIndep G S produces disjoint families of sets.
Finset.sum_image
Summing over the image of an injective map on a finite set equals summing the composed function over the domain set.
cliqueIndep_insert_injOn
Inserting a vertex u from a component c ∉ S is an injective map on independent sets supported on S.
cliqueIndep_fresh
A vertex in a component outside S cannot belong to any independent set supported on S.
cliqueIndep_sum_insert
A sum over independent sets on S ∪ {c} equals the sum over S plus the sum over u in component c of sums with u inserted.
Finset.prod_insert
The product of a function over an inserted element and a set equals the value at the element times the product over the set, if the element was not in the set.
Finset.sum_insert
The sum of a function over an inserted element and a set equals the value at the element plus the sum over the set, if the element was not in the set.
Finset.notMem_empty
No element belongs to the empty set.
simple_graph_clique_components_independent_iff_injective
In a graph whose connected components are cliques, a set of vertices is independent if and only if the component map is injective on that set.
zero_lt_one
Zero is strictly less than one.
Finset.single_le_sum
For any non-negative function on a finite set, the value at any single element is at most the sum over the entire set.
Finset.sum_fiberwise
A sum over a finite set equals the sum over the fibers of a function on that set.
Finset.sum_div
Division of a finite sum by a scalar distributes over each term of the sum.
simple_graph_clique_components_closed_neighborhood
In a graph whose components are cliques, the closed neighborhood of any vertex is the entire connected component containing that vertex.
cliqueZ_pos
For strictly positive fugacities, the partition function restricted to any subset of components is strictly positive.
cliqueIndep_empty
The only independent set whose vertices all belong to the empty set of components is the empty set.
finite_variance_recurrence_additive
Given partition functions and moment sums satisfying linear step recurrences with base values zero, the variance of the combined system equals the sum of the individual component variances.
cliqueIndep_Z_step
The partition function multiplies by 1 + ∑ λ(u) over component c when adding component c.
cliqueIndep_A_step
The first-moment sum satisfies the linear step recurrence when adding a new component c.
cliqueIndep_B_step
The second-moment sum satisfies the quadratic step recurrence when adding a new component c.
cliqueIndep_univ
When all components are cliques, independent sets supported on all components are precisely the independent sets of the graph.
cliqueBound_eq
The weighted closed-neighborhood bound equals the sum over components of the complete-graph bound for each component.
cliqueVar_eq_sum
The weighted hard-core variance equals the sum over components of the complete-graph variance for each component.
Finset.sum_le_sum
If one function is pointwise less than or equal to another on a finite set, its sum is at most the other's sum.
op_1355_complete_graph_div_sq_le_div_sub_div_sq
For non-negative S and moments satisfying Cauchy-Schwarz, the complete-graph neighborhood bound is at most the complete-graph variance.
op_1355_complete_graph_weighted_cauchy_schwarz
The Cauchy-Schwarz inequality for weighted sums with non-negative weights.
In703.in703_main
The main variance bound theorem for graphs with clique components, proved in the In703 namespace.

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

set_option maxHeartbeats 1000000set_option maxRecDepth 10000namespace In703open scoped Classicalvariable {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)noncomputable def compFiber (c : G.ConnectedComponent) : Finset V :=  Finset.univ.filter (fun v => G.connectedComponentMk v = c)noncomputable def cliqueIndep (S : Finset G.ConnectedComponent) : Finset (Finset V) :=  Finset.univ.filter fun I =>    (∀ v ∈ I, G.connectedComponentMk v ∈ S) ∧ (I : Set V).InjOn G.connectedComponentMklemma cliqueIndep_pairwiseDisjoint (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent) (hc : c ∉ S) :    (↑(compFiber G c) : Set V).PairwiseDisjoint (fun u => (cliqueIndep G S).image (insert u)) := by  intro u hu v hv hne  simp only [compFiber, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hu hv  dsimp [Function.onFun]  rw [Finset.disjoint_left]  intro I hI  simp only [cliqueIndep, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at hI  rcases hI with ⟨J, ⟨hJ, -⟩, rfl⟩  intro h_mem  simp only [cliqueIndep, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at h_mem  rcases h_mem with ⟨K, ⟨hK, -⟩, heq⟩  have hu_in : u ∈ insert v K := by    rw [heq]    exact Finset.mem_insert_self u J  simp only [Finset.mem_insert] at hu_in  rcases hu_in with rfl | huK  · exact hne rfl  · have hcomp := hK u huK    rw [hu] at hcomp    exact hc hcomplemma cliqueIndep_insert_injOn (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent) (hc : c ∉ S)    (u : V) (hu : u ∈ compFiber G c) :    Set.InjOn (insert u) (cliqueIndep G S : Set (Finset V)) := by  simp only [compFiber, Finset.mem_filter, Finset.mem_univ, true_and] at hu  intro J hJ K hK heq  simp only [cliqueIndep, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hJ hK  have huJ : u ∉ J := by    intro h    have := hJ.1 u h    rw [hu] at this    exact hc this  have huK : u ∉ K := by    intro h    have := hK.1 u h    rw [hu] at this    exact hc this  ext x  have hx : x ∈ insert u J ↔ x ∈ insert u K := by rw [heq]  simp only [Finset.mem_insert] at hx  by_cases hxu : x = u  · subst hxu    simp [huJ, huK]  · simp [hxu] at hx    exact hxlemma cliqueIndep_insert_decomposition (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent)    (hc : c ∉ S) : cliqueIndep G (insert c S) =      cliqueIndep G S ∪ (compFiber G c).biUnion (fun u => (cliqueIndep G S).image (insert u)) := by  classical  ext I  simp only [cliqueIndep, Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and,    Finset.mem_biUnion, Finset.mem_image]  constructor  · rintro ⟨hS, hinj⟩    by_cases he : ∃ u ∈ I, G.connectedComponentMk u = c    · obtain ⟨u,huI,huc⟩ := he      right      refine ⟨u, ?_, I.erase u, ?_, Finset.insert_erase huI⟩      · simp [compFiber, huc]      · constructor        · intro v hv          have hvI := (Finset.mem_erase.mp hv).2          have hm := hS v hvI          simp only [Finset.mem_insert] at hm          rcases hm with hvc | hvS          · have hvu := hinj hvI huI (hvc.trans huc.symm)            exact ((Finset.mem_erase.mp hv).1 hvu).elim          · exact hvS        · intro v hv w hw heq          exact hinj (Finset.mem_erase.mp hv).2 (Finset.mem_erase.mp hw).2 heq    · left      refine ⟨?_, hinj⟩      intro v hv      have hm := hS v hv      simp only [Finset.mem_insert] at hm      rcases hm with hvc | hvS      · exact (he ⟨v,hv,hvc⟩).elim      · exact hvS  · rintro (⟨hS, hinj⟩ | ⟨u,hu,J,⟨hJ,hinj⟩,rfl⟩)    · refine ⟨?_, hinj⟩      intro v hv      exact Finset.mem_insert_of_mem (hS v hv)    · have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu      have huJ : u ∉ J := by        intro huJ        apply hc        simpa [huc] using hJ u huJ      refine ⟨?_, ?_⟩      · intro v hv        simp only [Finset.mem_insert] at hv        rcases hv with rfl | hv        · simpa [huc]        · exact Finset.mem_insert_of_mem (hJ v hv)      · intro v hv w hw heq        simp only [Finset.coe_insert, Set.mem_insert_iff] at hv hw        rcases hv with rfl | hv <;> rcases hw with rfl | hw        · rfl        · have : G.connectedComponentMk w ∈ S := hJ w hw          rw [← heq, huc] at this          exact (hc this).elim        · have : G.connectedComponentMk v ∈ S := hJ v hv          rw [heq, huc] at this          exact (hc this).elim        · exact hinj hv hw heqlemma cliqueIndep_disjoint_old_new (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent)    (hc : c ∉ S) : Disjoint (cliqueIndep G S)      ((compFiber G c).biUnion (fun u => (cliqueIndep G S).image (insert u))) := by  classical  apply Finset.disjoint_left.mpr  intro I hI hnew  obtain ⟨u,hu,himg⟩ := Finset.mem_biUnion.mp hnew  obtain ⟨J,hJ,hJI⟩ := Finset.mem_image.mp himg  subst I  have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu  have hI' := (Finset.mem_filter.mp hI).2.1 u (Finset.mem_insert_self u J)  exact hc (huc ▸ hI')lemma cliqueIndep_sum_insert (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent)    (hc : c ∉ S) (f : Finset V → ℝ) :    (∑ I ∈ cliqueIndep G (insert c S), f I) =      (∑ I ∈ cliqueIndep G S, f I) + ∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S, f (insert u I) := by  classical  rw [cliqueIndep_insert_decomposition G c S hc,    Finset.sum_union (cliqueIndep_disjoint_old_new G c S hc),    Finset.sum_biUnion (cliqueIndep_pairwiseDisjoint G c S hc)]  congr 1  apply Finset.sum_congr rfl  intro u hu  exact Finset.sum_image (cliqueIndep_insert_injOn G c S hc u hu)lemma cliqueIndep_fresh (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent)    (hc : c ∉ S) (u : V) (hu : u ∈ compFiber G c) (I : Finset V) (hI : I ∈ cliqueIndep G S) : u ∉ I := by  intro hui  have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu  have hS := (Finset.mem_filter.mp hI).2.1 u hui  exact hc (huc ▸ hS)lemma cliqueIndep_Z_step (lam : V → ℝ) (c : G.ConnectedComponent)    (S : Finset G.ConnectedComponent) (hc : c ∉ S) :    (∑ I ∈ cliqueIndep G (insert c S), ∏ v ∈ I, lam v) =      (1 + ∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by  classical  rw [cliqueIndep_sum_insert G c S hc]  have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S, ∏ v ∈ insert u I, lam v) =      (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by    rw [Finset.sum_mul]    apply Finset.sum_congr rfl    intro u hu    rw [Finset.mul_sum]    apply Finset.sum_congr rfl    intro I hI    exact Finset.prod_insert (cliqueIndep_fresh G c S hc u hu I hI)  rw [h]  ringlemma cliqueIndep_A_step (lam a : V → ℝ) (c : G.ConnectedComponent)    (S : Finset G.ConnectedComponent) (hc : c ∉ S) :    (∑ I ∈ cliqueIndep G (insert c S), (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) =      (1 + ∑ u ∈ compFiber G c, lam u) *        (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) +      (∑ u ∈ compFiber G c, lam u * a u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by  classical  rw [cliqueIndep_sum_insert G c S hc]  have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S,      (∏ v ∈ insert u I, lam v) * ∑ v ∈ insert u I, a v) =      (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) +      (∑ u ∈ compFiber G c, lam u * a u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by    rw [Finset.sum_mul, Finset.sum_mul, ← Finset.sum_add_distrib]    apply Finset.sum_congr rfl    intro u hu    rw [Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib]    apply Finset.sum_congr rfl    intro I hI    have hf := cliqueIndep_fresh G c S hc u hu I hI    rw [Finset.prod_insert hf, Finset.sum_insert hf]    ring  rw [h]  ringlemma cliqueIndep_B_step (lam a : V → ℝ) (c : G.ConnectedComponent)    (S : Finset G.ConnectedComponent) (hc : c ∉ S) :    (∑ I ∈ cliqueIndep G (insert c S), (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)^2) =      (1 + ∑ u ∈ compFiber G c, lam u) *        (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)^2) +      2 * (∑ u ∈ compFiber G c, lam u * a u) *        (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) +      (∑ u ∈ compFiber G c, lam u * a u^2) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by  classical  rw [cliqueIndep_sum_insert G c S hc]  have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S,      (∏ v ∈ insert u I, lam v) * (∑ v ∈ insert u I, a v)^2) =      (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)^2) +      2 * (∑ u ∈ compFiber G c, lam u * a u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) +      (∑ u ∈ compFiber G c, lam u * a u^2) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by    have htwo : 2 * (∑ u ∈ compFiber G c, lam u * a u) =        ∑ u ∈ compFiber G c, 2 * (lam u * a u) := by rw [Finset.mul_sum]    rw [htwo, Finset.sum_mul, Finset.sum_mul, Finset.sum_mul,      ← Finset.sum_add_distrib, ← Finset.sum_add_distrib]    apply Finset.sum_congr rfl    intro u hu    rw [Finset.mul_sum, Finset.mul_sum, Finset.mul_sum,      ← Finset.sum_add_distrib, ← Finset.sum_add_distrib]    apply Finset.sum_congr rfl    intro I hI    have hf := cliqueIndep_fresh G c S hc u hu I hI    rw [Finset.prod_insert hf, Finset.sum_insert hf]    ring  rw [h]  ringnoncomputable def cliqueZ (lam : V → ℝ) (S : Finset G.ConnectedComponent) : ℝ :=  ∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam vnoncomputable def cliqueA (lam a : V → ℝ) (S : Finset G.ConnectedComponent) : ℝ :=  ∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a vnoncomputable def cliqueB (lam a : V → ℝ) (S : Finset G.ConnectedComponent) : ℝ :=  ∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)^2lemma cliqueIndep_empty : cliqueIndep G ∅ = {∅} := by  ext I  simp only [cliqueIndep, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton]  constructor  · rintro ⟨h, -⟩    ext x    simp only [Finset.notMem_empty, iff_false]    exact fun hx => Finset.notMem_empty _ (h x hx)  · rintro rfl    refine ⟨by simp, by simp [Set.InjOn]⟩lemma cliqueIndep_univ [DecidableRel G.Adj]    (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) :    cliqueIndep G Finset.univ = ({I | G.IsIndepSet (↑I : Set V)} : Finset (Finset V)) := by  ext I  simp only [cliqueIndep, Finset.mem_filter, Finset.mem_univ, true_and]  rw [simple_graph_clique_components_independent_iff_injective G hclique]  simplemma cliqueZ_pos (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (S : Finset G.ConnectedComponent) :    0 < cliqueZ G lam S := by  unfold cliqueZ  refine lt_of_lt_of_le zero_lt_one ?_  have h_empty : (∏ v ∈ (∅ : Finset V), lam v) = 1 := Finset.prod_empty  rw [← h_empty]  have hem : (∅ : Finset V) ∈ cliqueIndep G S := by simp [cliqueIndep, Set.InjOn]  exact Finset.single_le_sum (f := fun I : Finset V => ∏ v ∈ I, lam v)    (fun I _ => Finset.prod_nonneg fun v _ => le_of_lt (hlam v)) hemlemma cliqueBound_eq [DecidableRel G.Adj]    (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) (lam a : V → ℝ) :    hardCoreWeightedClosedNeighborhoodBound G lam a =      ∑ c : G.ConnectedComponent, (∑ v ∈ compFiber G c, lam v * a v^2) /        (1 + ∑ u ∈ compFiber G c, lam u)^2 := by  classical  unfold hardCoreWeightedClosedNeighborhoodBound  rw [← Finset.sum_fiberwise Finset.univ G.connectedComponentMk    (fun v => (a v ^ 2 * lam v) / (1 + ∑ u ∈ insert v (G.neighborFinset v), lam u)^2)]  apply Finset.sum_congr rfl  intro c hc  rw [Finset.sum_div]  apply Finset.sum_congr rfl  intro v hv  have hvc : G.connectedComponentMk v = c := by simpa [compFiber] using hv  rw [simple_graph_clique_components_closed_neighborhood G hclique v, hvc]  change (a v^2 * lam v) / (1 + ∑ u ∈ compFiber G c, lam u)^2 = _  ringlemma cliqueVar_eq_sum [DecidableRel G.Adj]    (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) (lam a : V → ℝ)    (hlam : ∀ v, 0 < lam v) :    hardCoreWeightedVar G lam a =      ∑ c : G.ConnectedComponent,        ((∑ v ∈ compFiber G c, lam v * a v^2) / (1 + ∑ v ∈ compFiber G c, lam v) -        ((∑ v ∈ compFiber G c, lam v * a v) / (1 + ∑ v ∈ compFiber G c, lam v))^2) := by  classical  have hZ : ∀ S, cliqueZ G lam S ≠ 0 := fun S => ne_of_gt (cliqueZ_pos G lam hlam S)  have hs : ∀ c, 1 + (∑ v ∈ compFiber G c, lam v) ≠ 0 := by    intro c    have h : 0 ≤ ∑ v ∈ compFiber G c, lam v := Finset.sum_nonneg fun v _ => le_of_lt (hlam v)    linarith  have hb : cliqueA G lam a ∅ = 0 ∧ cliqueB G lam a ∅ = 0 := by    simp [cliqueA, cliqueB, cliqueIndep_empty]  have hrec := finite_variance_recurrence_additive (cliqueZ G lam) (cliqueA G lam a) (cliqueB G lam a)    (fun c => ∑ v ∈ compFiber G c, lam v)    (fun c => ∑ v ∈ compFiber G c, lam v * a v)    (fun c => ∑ v ∈ compFiber G c, lam v * a v^2)    hZ hs hb    (fun c S hc => cliqueIndep_Z_step G lam c S hc)    (fun c S hc => cliqueIndep_A_step G lam a c S hc)    (fun c S hc => cliqueIndep_B_step G lam a c S hc) Finset.univ  have hv : hardCoreWeightedVar G lam a =      cliqueB G lam a Finset.univ / cliqueZ G lam Finset.univ -        (cliqueA G lam a Finset.univ / cliqueZ G lam Finset.univ)^2 := by    unfold hardCoreWeightedVar cliqueB cliqueA cliqueZ    rw [cliqueIndep_univ G hclique]  rw [hv, hrec]theorem in703_main [DecidableRel G.Adj]    (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v)    (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) :    hardCoreWeightedClosedNeighborhoodBound G lam a ≤ hardCoreWeightedVar G lam a := by  rw [cliqueBound_eq G hclique lam a, cliqueVar_eq_sum G hclique lam a hlam]  apply Finset.sum_le_sum  intro c hc  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 (compFiber G c) lam a fun v _ => le_of_lt (hlam v)end In703/-- On any finite graph whose connected components are cliques, the weighted hard-core closed-neighborhood variance bound holds. -/theorem op_1355_clique_components_variance_ge_bound    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v)    (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) :    hardCoreWeightedClosedNeighborhoodBound G lam a ≤ hardCoreWeightedVar G lam a := by  exact In703.in703_main G lam hlam a ha hclique
See it in the graphDiscuss this resultChallenge it