Algorithm 1: processing a vertex whose group has a front
ProvedDirKECC1549.Asm.a1Test_specIf the group of has a front, the test branch of Algorithm 1 runs the four searches against the front and then unites with the front or splits the group, establishing the invariant and memory representation for within ticks.
Context. This lemma belongs to the machine-checked word-RAM implementation of Lemma 1 (p.11): Algorithm 1 refining by small -out sets, with the deterministic local search of [GKK+26, Proposition 6] (FindOutPaths and recursive path reversals). The program is written in the structured language Stmt compiled to the published word-RAM; Run E s mem Q states that the statement s, started on mem, reaches its end in a state satisfying Q t mem' within t ticks. The input cells double as registers; they are saved at SV and read through the image ImgAt. All definitions are in the Definitions.Def_DirKECC1549_Impl_* modules.
import Definitions.Def_DirKECC1549_Impl_L1Alg6
set_option autoImplicit false
open WordRAM Classical Finset
open DirKECC1549.Main DirKECC1549.Main.CostAux
open DirKECC1549 DirKECC1549.Asm
variable {w : Width} {n m : ℕ}theorem DirKECC1549.Asm.a1Test_spec (E : Env) (orig : Memory w) (hm : 0 < m) (P : LP) (OR PR IR HR TR : ℕ)
(G : Fin m → Fin n × Fin n) (σ τ : Equiv.Perm (Fin m)) (K Δ FR W k : ℕ)
(hst : AlgStat P OR PR IR HR TR orig G σ τ) (hL : LsLay P n m K Δ FR W w.bits)
(hE : EnvOK E lsBody) (hs : ∀ x ∈ E.sites, x < 2 ^ w.bits) (hk : K = k - 1) (hk2 : 2 ≤ k)
(L0 : Fin n → ℕ) (hlab : ∀ u v : Fin n, L0 u = L0 v ↔ KEdgeConnected K G u v)
(GIb FRb OUTb : ℕ) (hlay : ALay P n m FR GIb FRb OUTb)
(x : Fin n) (gi : Fin n → ℕ) (frt : ℕ → ℕ) (ng : ℕ) (ρ : Fin n → Fin n)
(hA : AInv (eqvA k Δ G L0) L0 x gi frt ng ρ) (hfn : frt (gi x) ≠ n)
(m1 : Memory w) (harr : AlgArr P GIb FRb OUTb x gi frt ng ρ m1) (h66 : (m1 (P.SV + 66)).toNat = x)
(h74 : (m1 (P.SV + 74)).toNat = gi x) (h2 : (m1 2).toNat = frt (gi x))
(hdyn : AlgDyn (n := n) P orig m1) (hZ : VisZero n P m1) (hc : AlgCells (n := n) P OR PR IR HR TR FR K Δ W m1) :
Run E (.seq (.code mbTest) (.seq ls4 (.seq (.code mbRes) (.ite .eq (rg 0) (imm 0) (.code mbUnite)
(.seq splitLoop (.seq frontUpd (.code mbSelf))))))) m1
(fun t mm' => APost P OR PR IR HR TR FR K Δ W orig k G L0 GIb FRb OUTb x
(4 * lsTT K Δ E.sites.length K + 12 * (Δ + 1) + 400) t mm') := by sorry