The run of Lemma 1 when the graph has edges
ProvedDirKECC1549.Asm.l1Body_specFor , , , and input labels whose equality is -edge-connectivity, the program l1Body ends with output labels at that are equal exactly when the input labels are equal and the vertices are -connected, 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_L1Top
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.l1Body_spec (E : Env) (hE : EnvOK E lsBody) (hs : ∀ x ∈ E.sites, x < 2 ^ w.bits) (mem : Memory w)
(G : Fin m → Fin n × Fin n) (k Δ : ℕ) (σ τ : Equiv.Perm (Fin m))
(hin : ∀ a < 2 * m + 2, (mem a).toNat = edgeListCell n m G a)
(hts : ∀ v ≤ n, (mem ((n + 2 * m + 3) + v)).toNat = (univ.filter (fun e => ((G e).1 : ℕ) < v)).card)
(hσm : Monotone (fun i => (G (σ i)).1)) (hσv : ∀ i : Fin m, (mem (2 * (n + 2 * m + 3) + i)).toNat = σ i)
(hhs : ∀ v ≤ n, (mem (3 * (n + 2 * m + 3) + v)).toNat = (univ.filter (fun e => ((G e).2 : ℕ) < v)).card)
(hτm : Monotone (fun i => (G (τ i)).2)) (hτv : ∀ i : Fin m, (mem (4 * (n + 2 * m + 3) + i)).toNat = τ i)
(hn : 1 ≤ n) (hm : 0 < m) (hk2 : 2 ≤ k) (hkΔ : k - 1 ≤ Δ)
(hkp : (mem (5 * (n + 2 * m + 3))).toNat = k) (hΔp : (mem (5 * (n + 2 * m + 3) + 1)).toNat = Δ)
(hlab : ∀ u v : Fin n, (mem (6 * (n + 2 * m + 3) + u)).toNat = (mem (6 * (n + 2 * m + 3) + v)).toNat ↔
KEdgeConnected (k - 1) G u v)
(hw : 10 * (8 * (n + 2 * m + 3) + 128 + 13 * n + 2 * m + 8 + (k - 1 + 2) * (8 + (2 * (k - 1) + 1) * (n + 1))) +
4 * ((2 * (k - 1) + 1) * (Δ + 1)) + 4 * n + 4 * m + k + Δ + 2000 < 2 ^ w.bits) :
Run E l1Body mem (fun t q => t ≤ n * (4 * lsTT (k - 1) Δ E.sites.length (k - 1) + 12 * (Δ + 1) + 433) +
80 * n + 500 ∧ ∀ u v : Fin n, (q (7 * (n + 2 * m + 3) + u) = q (7 * (n + 2 * m + 3) + v) ↔
eqvA k Δ G (fun y => (mem (6 * (n + 2 * m + 3) + y)).toNat) u v)) := by sorry