Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8 — exact one sweep and bounded local mad

Open
LocalOccupancyIS.Glauber.Supplement.theorem_8

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theoryindependent-setsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability

Let GGG be a nonempty finite simple graph with degree at most Δ\DeltaΔ and let λ>0\lambda>0λ>0.

  1. If GGG is triangle free, any deterministic full sweep of N(u)N(u)N(u) equals QuQ_uQu​ as a kernel, for every center. For any valid local occupancy parameters (λ,β,γ)(\lambda,\beta,\gamma)(λ,β,γ), these sweeps satisfy the certificate with η=0\eta=0η=0 and occurrence bound κ≤Δ\kappa\le\Deltaκ≤Δ. With Γ=β+γΔ\Gamma=\beta+\gamma\DeltaΓ=β+γΔ and C1=β+Δmax⁡{βp,γΔ}C_1=\beta+\Delta\max\{\beta p,\gamma\Delta\}C1​=β+Δmax{βp,γΔ}, from every initial probability law the full Theorem 2 consequence is
E∣IJ∣≥nΓ(1−C1H02T).\mathbb E|I_J|\ge\frac n\Gamma\left(1-C_1\sqrt{\frac{H_0}{2T}}\right).E∣IJ​∣≥Γn​(1−C1​2TH0​​​).

Its threshold T≥C12Hλ/(2ϵ2)T\ge C_1^2H_\lambda/(2\epsilon^2)T≥C12​Hλ​/(2ϵ2) yields (1−ϵ)n/Γ(1-\epsilon)n/\Gamma(1−ϵ)n/Γ, for T≥1T\ge1T≥1 and 0<ϵ<10<\epsilon<10<ϵ<1.

  1. For Δ≥1\Delta\ge1Δ≥1 and a≥0a\ge0a≥0, if every neighborhood has maximum average degree at most aaa, the computed equation (19) parameters give local occupancy and
Γ=β19+γ19Δ=ewp=Δ(1+λ)alog⁡(1+λ)pW(Δ(1+λ)alog⁡(1+λ)).\Gamma=\beta_{19}+\gamma_{19}\Delta=\frac{e^w}{p}=\frac{\Delta(1+\lambda)^a\log(1+\lambda)}{pW(\Delta(1+\lambda)^a\log(1+\lambda))}.Γ=β19​+γ19​Δ=pew​=pW(Δ(1+λ)alog(1+λ))Δ(1+λ)alog(1+λ)​.

Any two full neighborhood sweeps, whose deterministic orders may differ, satisfy the same certificate with η=0\eta=0η=0 and κ≤2Δ\kappa\le2\Deltaκ≤2Δ. From every initial state,

T≥(β19+2Δmax⁡{β19p,γ19Δ})2Hλ2ϵ2⟹E∣IJ∣≥(1−ϵ)nΓ.T\ge\frac{(\beta_{19}+2\Delta\max\{\beta_{19}p,\gamma_{19}\Delta\})^2H_\lambda}{2\epsilon^2}\quad\Longrightarrow\quad\mathbb E|I_J|\ge\frac{(1-\epsilon)n}{\Gamma}.T≥2ϵ2(β19​+2Δmax{β19​p,γ19​Δ})2Hλ​​⟹E∣IJ​∣≥Γ(1−ϵ)n​.

Here JJJ is independent and uniform on the first TTT times. The result includes edgeless neighborhoods and all positive fugacities; the parameters and certificate are conclusions, not supplied guarantees.

Differences from the source:

  • encoding: uniform random choice of a vertex in a finite graph → an explicit Nonempty vertex-type instance; reason: the source dynamics require at least one vertex for uniform site selection, while edgeless nonempty graphs remain allowed
  • encoding: local maximum average degree at most a, arbitrary feasible exteriors, and uniform random time → HereditaryDensity G 1 a, equality of full state-space kernels, and the finite time mean; reason: t=1 density is precisely induced average degree; kernel equality includes every feasible exterior and state
Preamble
import Definitions.Def_LocalOccupancyIS_Glauber_Supplement_MadParameters
Formal statement
namespace LocalOccupancyIS.Glauber.Supplement
/-- Theorem 8(a),(b), pp.15–17. Sweep orders are deterministic and may differ.
HereditaryDensity G 1 a is exactly the source's local maximum average degree bound. -/
theorem theorem_8 {V : Type} [Fintype V] [DecidableEq V] [Nonempty V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (Δ lam : ℝ)
    (hdeg : RealDegreeBound G Δ) (hlam : 0 < lam) :
    (TriangleFree G →
      (∀ (u : V) (w : List V), IsSweep (G.neighborFinset u) w →
        word G lam w = Q G lam u) ∧
      ∀ β γ : ℝ, LocalOccupancy G lam β γ →
        ∀ w : V → List V, (∀ u, IsSweep (G.neighborFinset u) (w u)) →
          WordCertificate G lam β γ 0 w ∧ (occurrences w : ℝ) ≤ Δ ∧
          ∀ ν : State G → ℝ, MarkovMixing.IsDist ν →
            let C₁ := β + Δ * max (β * p lam) (γ * Δ)
            let Γ := β + γ * Δ
            ∀ T : ℕ, 1 ≤ T →
              timeMean G lam ν T ≥ Fintype.card V / Γ *
                (1 - C₁ * Real.sqrt (kl ν (HardCoreBochner.hcLaw G lam) / (2*T))) ∧
              ∀ ε : ℝ, 0 < ε → ε < 1 →
                C₁^2 * entropyBound (Fintype.card V) lam / (2*ε^2) ≤ T →
                timeMean G lam ν T ≥ (1-ε) * Fintype.card V / Γ) ∧
    (1 ≤ Δ → ∀ a : ℝ, 0 ≤ a → HereditaryDensity G 1 a →
      let β := madBeta Δ a lam
      let γ := madGamma Δ a lam
      let w₀ := madW Δ a lam
      LocalOccupancy G lam β γ ∧
      β + γ * Δ = Real.exp w₀ / p lam ∧
      β + γ * Δ = Δ * (1+lam)^a * Real.log (1+lam) / (p lam * w₀) ∧
      ∀ w₁ w₂ : V → List V,
        (∀ u, IsSweep (G.neighborFinset u) (w₁ u)) →
        (∀ u, IsSweep (G.neighborFinset u) (w₂ u)) →
        WordCertificate G lam β γ 0 (fun u => w₁ u ++ w₂ u) ∧
        (occurrences (fun u => w₁ u ++ w₂ u) : ℝ) ≤ 2*Δ ∧
        ∀ (σ : State G) (T : ℕ), 1 ≤ T →
          ∀ ε : ℝ, 0 < ε → ε < 1 →
            (β + 2*Δ * max (β * p lam) (γ * Δ))^2 *
              entropyBound (Fintype.card V) lam / (2*ε^2) ≤ T →
            timeMean G lam (point σ) T ≥
              (1-ε) * Fintype.card V / (β + γ * Δ)) := by sorry
end LocalOccupancyIS.Glauber.Supplement
Source
Ewan Davies, Brian Tan, STOC 2027 submission #982 (October 2026), p.15, Theorem 8 and equations (19)–(20); proof pp.16–17

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me