Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — neighborhood block dynamics

Open
LocalOccupancyIS.Glauber.Supplement.theorem_1

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 on nnn vertices with degree at most Δ\DeltaΔ, and suppose it has local occupancy parameters (λ,β,γ)(\lambda,\beta,\gamma)(λ,β,γ), all positive. Put Γ=β+γΔ\Gamma=\beta+\gamma\DeltaΓ=β+γΔ, H0=DKL(ν0∥μG,λ)H_0=D_{\rm KL}(\nu_0\|\mu_{G,\lambda})H0​=DKL​(ν0​∥μG,λ​) in nats, and Hλ=nlog⁡((1+λ)/min⁡{1,λ})H_\lambda=n\log((1+\lambda)/\min\{1,\lambda\})Hλ​=nlog((1+λ)/min{1,λ}). From every initial probability law ν0\nu_0ν0​, for every integer T≥1T\ge1T≥1 and independent uniform J∈{0,…,T−1}J\in\{0,\ldots,T-1\}J∈{0,…,T−1}, neighborhood block dynamics satisfies

E∣IJ∣≥nΓ(1−(β2+γ2Δ2)H02T).\mathbb E|I_J|\ge\frac n\Gamma\left(1-\sqrt{\frac{(\beta^2+\gamma^2\Delta^2)H_0}{2T}}\right).E∣IJ​∣≥Γn​(1−2T(β2+γ2Δ2)H0​​​).

For every 0<ϵ<10<\epsilon<10<ϵ<1, the threshold T≥(β2+γ2Δ2)Hλ/(2ϵ2)T\ge(\beta^2+\gamma^2\Delta^2)H_\lambda/(2\epsilon^2)T≥(β2+γ2Δ2)Hλ​/(2ϵ2) gives E∣IJ∣≥(1−ϵ)n/Γ\mathbb E|I_J|\ge(1-\epsilon)n/\GammaE∣IJ​∣≥(1−ϵ)n/Γ. The block kernel is stochastic. Enumerating the neighborhood assignments implements QuQ_uQu​ exactly, the table has positive total weight, and the local counter update preserves the counters. There are absolute constants C,c>0C,c>0C,c>0, chosen before every graph and fugacity, such that each enumerated block update costs at most CecΔCe^{c\Delta}CecΔ charged operations, including degree zero.

This gives the occupancy guarantee without rapid mixing or reversibility hypotheses. The cost model uses exact real arithmetic and exact finite random choice; it asserts no bit-cost bound for arbitrary real inputs.

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: the random time and the statement that a block can be enumerated in time 2^{O(Δ)} → the finite time mean, an explicit enumerated kernel, maintained-counter update and charged traces with an absolute exponential bound; reason: these specify the process and source arithmetic/random-choice convention without assuming its guarantee
Preamble
import Definitions.Def_LocalOccupancyIS_Glauber_Supplement_BlockDynamics
import Definitions.Def_LocalOccupancyIS_Glauber_Supplement_MadParameters
Formal statement
namespace LocalOccupancyIS.Glauber.Supplement
/-- Theorem 1, p.4, including the enumerated block implementation.
C and c are absolute; exact-real arithmetic and exact weighted choice are charged primitives. -/
theorem theorem_1 :
    ∃ C c : ℝ, 0 < C ∧ 0 < c ∧
    ∀ {V : Type} [Fintype V] [DecidableEq V] [Nonempty V],
    ∀ (G : SimpleGraph V) [DecidableRel G.Adj] (Δ : ℝ), RealDegreeBound G Δ →
    ∀ lam β γ : ℝ, 0 < lam → LocalOccupancy G lam β γ →
      MarkovMixing.IsStochastic (blockKernel G lam) ∧
      (∀ u, enumerationQ G lam u = Q G lam u ∧
        (∀ σ : State G, 0 < tableMass G lam u σ (counters G σ)) ∧
        (∀ (σ τ : State G),
          (∀ v ∉ insert u (G.neighborFinset u), τ.val v = σ.val v) →
          maintainedCounts G u σ τ (counters G σ) = counters G τ) ∧
        (blockWork G u : ℝ) ≤ C * Real.exp (c * Δ)) ∧
      ∀ ν : State G → ℝ, MarkovMixing.IsDist ν →
        let H₀ := kl ν (HardCoreBochner.hcLaw G lam)
        let Hlam := entropyBound (Fintype.card V) lam
        let Γ := β + γ * Δ
        ∀ T : ℕ, 1 ≤ T →
          blockMean G lam ν T ≥ Fintype.card V / Γ *
            (1 - Real.sqrt ((β^2 + γ^2 * (Δ : ℝ)^2) * H₀ / (2*T))) ∧
          ∀ ε : ℝ, 0 < ε → ε < 1 →
            (β^2 + γ^2 * (Δ : ℝ)^2) * Hlam / (2*ε^2) ≤ T →
            blockMean G lam ν T ≥ (1-ε) * Fintype.card V / Γ := by sorry
end LocalOccupancyIS.Glauber.Supplement
Source
Ewan Davies, Brian Tan, STOC 2027 submission #982 (October 2026), p.4, Theorem 1, equation (3); proof §3 pp.12–13

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