One iteration of the inner loop of the local search
ProvedDirKECC1549.Asm.lsIter_specAt level , with candidate stored as a simple trail of length at most , one iteration reverses the candidate, calls the procedure at level , reverses it back and advances ; it keeps the precondition at level , reports found sets, sets the found flag when a good reversal history through this candidate exists, and takes at most 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_L1Ls3
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.lsIter_spec (E : Env) (orig : Memory w) (hm : 0 < m) (P : LP) (B : Fin m → Fin n × Fin n)
(perm : Equiv.Perm (Fin m)) (v s : Fin n) (K Δ FR W sl : ℕ) (hL : LsLay P n m K Δ FR W w.bits)
(i : ℕ) (hi : i < K) (F : Finset (Fin m)) (NC c : ℕ)
(hcall : ∀ (F' : Finset (Fin m)) (q : Memory w), LPre P orig B perm v s K Δ FR W (i + 1) F' q →
Run E .call q (fun t q' => LPost P orig B perm v s K Δ FR W sl (i + 1) F' q t q'))
(q : Memory w) (hpre : LPre P orig B perm v s K Δ FR W i F q)
(h1 : (q (FR + i * W + 1)).toNat = c) (h2 : (q (FR + i * W + 2)).toNat = NC) (hc : c < NC)
(hNC : NC ≤ 2 * K + 1) (Lm : ℕ) (hLm : Lm ≤ lsLmax K Δ)
(hslots : ∀ c' < NC, ∃ L : List (Fin m), SlotEnc q (FR + i * W + 8 + c' * (n + 1)) L ∧ L.Nodup ∧
L.length ≤ Lm ∧ L.length ≤ n ∧ ∃ z, IsTrail (flipEdges B F) v L z ∧ SimpleP (flipEdges B F) L) :
Run E lsIter q (fun t q' => LPre P orig B perm v s K Δ FR W i F q' ∧ (q' (FR + i * W + 1)).toNat = c + 1 ∧
(∀ a, (KeepLS P m FR W K i a ∨ (FR + i * W ≤ a ∧ a < FR + i * W + W ∧ a ≠ FR + i * W + 1)) → q' a = q a) ∧
LsFound P B v s K Δ q' ∧
((∃ S : Finset (Fin n), v ∈ S ∧ s ∉ S ∧ GoodHist B v S F i ∧ outCount B S = K ∧ vol B S ≤ Δ ∧
∃ L z, SlotEnc q (FR + i * W + 8 + c * (n + 1)) L ∧ (IsTrail (flipEdges B F) v L z ∧ SimpleP (flipEdges B F) L) ∧ z ∉ S) →
(q' (P.SV + 42)).toNat = 1) ∧
((q' 0).toNat = 1 ↔ c + 1 < NC ∧ (q' (P.SV + 42)).toNat ≠ 1) ∧
t ≤ 100 * Lm + lsTT K Δ sl (K - (i + 1)) + 100) := by sorry