Algorithm 1: processing one vertex
ProvedDirKECC1549.Asm.a1Body_specFrom the invariant and the memory representation of the abstract state before , one iteration of Algorithm 1 establishes them for (APost), 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.a1Body_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 ρ)
(mm : Memory w) (harr : AlgArr P GIb FRb OUTb x gi frt ng ρ mm) (h66 : (mm (P.SV + 66)).toNat = x)
(hdyn : AlgDyn (n := n) P orig mm) (hZ : VisZero n P mm) (hc : AlgCells (n := n) P OR PR IR HR TR FR K Δ W mm) :
Run E a1Body mm (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) + 420) t mm') := by sorry