Theorem 1 — neighborhood block dynamics
OpenLocalOccupancyIS.Glauber.Supplement.theorem_1Let be a nonempty finite simple graph on vertices with degree at most , and suppose it has local occupancy parameters , all positive. Put , in nats, and . From every initial probability law , for every integer and independent uniform , neighborhood block dynamics satisfies
For every , the threshold gives . The block kernel is stochastic. Enumerating the neighborhood assignments implements exactly, the table has positive total weight, and the local counter update preserves the counters. There are absolute constants , chosen before every graph and fugacity, such that each enumerated block update costs at most 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
import Definitions.Def_LocalOccupancyIS_Glauber_Supplement_BlockDynamics import Definitions.Def_LocalOccupancyIS_Glauber_Supplement_MadParameters
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