Native fixed-width words for all dense-region sweep and repair parameters
DefinitionStableMSR_SweepWordsalgorithmsclusteringformal-verificationgraph-theory
A fixed-width word records a distance pair, an integral scale multiplier with a separate end marker, a grid index, and up to h flagged pairs of ball endpoints. Its row label is determined by the least covering active ball or its canonical coarse signature. The evaluation program acts only on a table of already materialized words.
Definition code
import Definitions.Def_StableMSR_ExplicitWindowScenes
open scoped Classical
set_option autoImplicit false
open StableMSR.Recovery StableMSR.Recovery.OracleQueries StableMSR.Recovery.Compiler
open StableMSR.Recovery.BallCoverCatalog StableMSR.Recovery.WindowSweep StableMSR.Recovery.WindowCSP
open StableMSR.Recovery.Supplement.BinaryRecovery.Regional
namespace StableMSR.Recovery.SweepWords
def slots (h : ℕ) := 2*h+3
noncomputable def rawR (x : World) (r : ℕ) :=
MinSumFPT.oracleAnswer x.dist (center x r 0) (witness x r 0)
def multiplier (x : World) (r : ℕ) :=
if witness x r 1=0 then (center x r 1).toNat else x.n
noncomputable def activeHits (x : World) (h r : ℕ) (p : Point x.n) :=
(Finset.range h).filter (fun j=>0< center x r (h+j+3) ∧
MinSumFPT.oracleAnswer x.dist (center x r (j+3)) (p.val:ℤ) ≤
MinSumFPT.oracleAnswer x.dist (center x r (j+3)) (witness x r (j+3)))
noncomputable def wordKey (x : World) (e : ℚ) (h r : ℕ) (p : Point x.n) : ℕ ⊕ (Cluster x.n × Cluster x.n) :=
let S:=activeHits x h r p
if ne : S.Nonempty then .inl (S.min' ne) else
let R:=rawR x r
.inr (coarseKey x.dist R ((multiplier x r:ℝ)*R) ((e:ℝ)*R/4) (center x r 2).toNat p)
def evaluateSpec (e : ℚ) (P : Polynomial ℕ) (cmd : Cmd) :=
∀(x : World) (s : Store),2≤ x.n → x.k=slots (coarseBudget (e:ℝ)) → Ready x s →
∃t z,Executes x.dist cmd s t z ∧ z≤ P.eval x.cap ∧
let y:=worldOf (x.mem 1).toNat x.rows x.dist t
Ready y t ∧ ∀r< x.rows,scale y r=rawR x r ∧ ∀p q : Point x.n,
label y r p=label y r q ↔ wordKey x e (coarseBudget (e:ℝ)) r p=wordKey x e (coarseBudget (e:ℝ)) r q
end StableMSR.Recovery.SweepWords
Source
Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Lemmas 3.3, 3.8, 3.9(iii), 4.4, Proposition 4.2, Algorithm 1, and Appendix A.4–A.6. Alternative pairwise formulation using bounded-overlap window traces in the mission’s real-distance model.