Loops of the BSP construction block
ProvedDetANN.HPIM.BD.loop_specsapproximate-nearest-neighborcomputational-geometrydata-structures
Eight loop facts about the program of definition DetANN_HPIMBuildProg, with BoxAt, psum, t1, t2, rmax and side from the same definition.
Each conjunct is a loop lemma by induction on the number of iterations left. Let contain at offset , and let be a non-halted state at the loop head, with the index in the stated register, equal to the trip count, and the loop invariant for the first iterations. Then some within the stated bound brings the run to the stated exit pc, without halting. The result holds for all iterations; only the listed registers and the target cells change; the work is ; and the written cells are the target cells.
- Distances (head 53, exit 86, at most steps): from the partial sums , in reals 42, 43, it ends with and for the point at pointer 47 and the box at pointer 43.
- Near box update (93 → 126, ): the box at (pointer 48) becomes the coordinatewise .
- First near point (116 → 126, ): the box at becomes , and the flag .
- Core box (134 → 161, ): the box at becomes (with in real 49).
- Sides (172 → 197, ): reals 51, 52 end with and .
- Longest axis (201 → 210, ): given an axis with side , it stops at the least with side , with reals .
- Copy (261 → 268, ): real cells from pointer 50 to pointer 56 (pointer ).
- Root box copy (13 → 20, ): real cells from pointer 17 to pointer 43.
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMBuildProg import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_Exec import Definitions.Def_DetANN_DataStructure import Definitions.Def_PNormRegLib_Reloc import Definitions.Def_DetANN_HPIMBuild import Definitions.Def_DetANN_HPIMPreBlocks
Formal statement
namespace DetANN.HPIM.BD
open PNormReg PNormRegLib DetANN DetANN.HPIM
theorem loop_specs :
(∀ {m : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (lo hi pt : Fin m → ℝ),
∀ (k j : ℕ) (s : State), j + k = m → s.core.pc = off + 53 → s.halted = false → s.core.ptrs 1 = m → 1 ≤ m → s.core.ptrs 46 = j → s.core.regs 53 = 2 → (∀ jj : Fin m, s.core.mem (s.core.ptrs 47 + jj) = pt jj) → BoxAt s (s.core.ptrs 43) lo hi → s.core.regs 42 = psum (t1 lo hi pt) j → s.core.regs 43 = psum (t2 lo hi pt) j → ∃ t, t ≤ 33 * k + 1 ∧ (run Q s detTape t).core.pc = off + 86 ∧ (run Q s detTape t).halted = false ∧ (run Q s detTape t).core.regs 42 = boxDist2 lo hi pt ∧ (run Q s detTape t).core.regs 43 = boxMaxDist2 lo hi pt ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape t).core.ptrs x = s.core.ptrs x) ∧ (∀ x, x ≠ 42 → x ≠ 43 → x ≠ 44 → x ≠ 45 → x ≠ 46 → x ≠ 47 → x ≠ 48 → x ≠ 54 → (run Q s detTape t).core.regs x = s.core.regs x) ∧ (run Q s detTape t).core.mem = s.core.mem ∧ (run Q s detTape t).integerMemory = s.integerMemory ∧ (run Q s detTape t).work = s.work + t ∧ cellsWritten Q s t = ∅) ∧
(∀ {m : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (pt mn0 mx0 : Fin m → ℝ),
∀ (k j : ℕ) (s : State), j + k = m → s.core.pc = off + 93 → s.halted = false → s.core.ptrs 1 = m → 1 ≤ m → s.core.ptrs 46 = j → s.core.regs 53 = 2 → s.core.ptrs 48 + 2 * m ≤ s.core.ptrs 47 → (∀ jj : Fin m, s.core.mem (s.core.ptrs 47 + jj) = pt jj) → (∀ jj : Fin m, (jj : ℕ) < j → s.core.mem (s.core.ptrs 48 + jj) = min (mn0 jj) (pt jj) ∧ s.core.mem (s.core.ptrs 48 + jj + m) = max (mx0 jj) (pt jj)) → (∀ jj : Fin m, j ≤ (jj : ℕ) → s.core.mem (s.core.ptrs 48 + jj) = mn0 jj ∧ s.core.mem (s.core.ptrs 48 + jj + m) = mx0 jj) → ∃ t, t ≤ 23 * k + 1 ∧ (run Q s detTape t).core.pc = off + 126 ∧ (run Q s detTape t).halted = false ∧ BoxAt (run Q s detTape t) (s.core.ptrs 48) (fun jj => min (mn0 jj) (pt jj)) (fun jj => max (mx0 jj) (pt jj)) ∧ (∀ z, (z < s.core.ptrs 48 ∨ s.core.ptrs 48 + 2 * m ≤ z) → (run Q s detTape t).core.mem z = s.core.mem z) ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape t).core.ptrs x = s.core.ptrs x) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 54 → (run Q s detTape t).core.regs x = s.core.regs x) ∧ (run Q s detTape t).integerMemory = s.integerMemory ∧ (run Q s detTape t).work = s.work + t ∧ ∀ c ∈ cellsWritten Q s t, c.1 = true ∧ s.core.ptrs 48 ≤ c.2 ∧ c.2 < s.core.ptrs 48 + 2 * m) ∧
(∀ {m : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (pt : Fin m → ℝ),
∀ (k j : ℕ) (s : State), j + k = m → s.core.pc = off + 116 → s.halted = false → s.core.ptrs 1 = m → 1 ≤ m → s.core.ptrs 46 = j → s.core.ptrs 48 + 2 * m ≤ s.core.ptrs 47 → (∀ jj : Fin m, s.core.mem (s.core.ptrs 47 + jj) = pt jj) → (∀ jj : Fin m, (jj : ℕ) < j → s.core.mem (s.core.ptrs 48 + jj) = pt jj ∧ s.core.mem (s.core.ptrs 48 + jj + m) = pt jj) → ∃ t, t ≤ 9 * k + 2 ∧ (run Q s detTape t).core.pc = off + 126 ∧ (run Q s detTape t).halted = false ∧ BoxAt (run Q s detTape t) (s.core.ptrs 48) pt pt ∧ (∀ z, (z < s.core.ptrs 48 ∨ s.core.ptrs 48 + 2 * m ≤ z) → (run Q s detTape t).core.mem z = s.core.mem z) ∧ (run Q s detTape t).core.ptrs 49 = 1 ∧ (∀ x, x ≠ 46 → x ≠ 49 → x ≠ 57 → (run Q s detTape t).core.ptrs x = s.core.ptrs x) ∧ (∀ x, x ≠ 44 → (run Q s detTape t).core.regs x = s.core.regs x) ∧ (run Q s detTape t).integerMemory = s.integerMemory ∧ (run Q s detTape t).work = s.work + t ∧ ∀ c ∈ cellsWritten Q s t, c.1 = true ∧ s.core.ptrs 48 ≤ c.2 ∧ c.2 < s.core.ptrs 48 + 2 * m) ∧
(∀ {m : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (mn0 mx0 lo hi : Fin m → ℝ) (r2 : ℝ),
∀ (k j : ℕ) (s : State), j + k = m → s.core.pc = off + 134 → s.halted = false → s.core.ptrs 1 = m → 1 ≤ m → s.core.ptrs 46 = j → s.core.regs 53 = 2 → s.core.regs 49 = r2 → s.core.ptrs 48 + 2 * m ≤ s.core.ptrs 43 → BoxAt s (s.core.ptrs 43) lo hi → (∀ jj : Fin m, (jj : ℕ) < j → s.core.mem (s.core.ptrs 48 + jj) = max (mn0 jj - r2) (lo jj) ∧ s.core.mem (s.core.ptrs 48 + jj + m) = min (mx0 jj + r2) (hi jj)) → (∀ jj : Fin m, j ≤ (jj : ℕ) → s.core.mem (s.core.ptrs 48 + jj) = mn0 jj ∧ s.core.mem (s.core.ptrs 48 + jj + m) = mx0 jj) → ∃ t, t ≤ 27 * k + 1 ∧ (run Q s detTape t).core.pc = off + 161 ∧ (run Q s detTape t).halted = false ∧ BoxAt (run Q s detTape t) (s.core.ptrs 48) (fun jj => max (mn0 jj - r2) (lo jj)) (fun jj => min (mx0 jj + r2) (hi jj)) ∧ (∀ z, (z < s.core.ptrs 48 ∨ s.core.ptrs 48 + 2 * m ≤ z) → (run Q s detTape t).core.mem z = s.core.mem z) ∧ (∀ x, x ≠ 46 → x ≠ 50 → x ≠ 57 → (run Q s detTape t).core.ptrs x = s.core.ptrs x) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 54 → (run Q s detTape t).core.regs x = s.core.regs x) ∧ (run Q s detTape t).integerMemory = s.integerMemory ∧ (run Q s detTape t).work = s.work + t ∧ ∀ c ∈ cellsWritten Q s t, c.1 = true ∧ s.core.ptrs 48 ≤ c.2 ∧ c.2 < s.core.ptrs 48 + 2 * m) ∧
(∀ {m : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (tlo thi lo hi : Fin m → ℝ),
∀ (k j : ℕ) (s : State), j + k = m → 1 ≤ j → s.core.pc = off + 172 → s.halted = false → s.core.ptrs 1 = m → s.core.ptrs 46 = j → s.core.regs 53 = 2 → BoxAt s (s.core.ptrs 48) tlo thi → BoxAt s (s.core.ptrs 43) lo hi → s.core.regs 51 = rmax (side tlo thi) (j - 1) → s.core.regs 52 = rmax (side lo hi) (j - 1) → ∃ t, t ≤ 25 * k + 1 ∧ (run Q s detTape t).core.pc = off + 197 ∧ (run Q s detTape t).halted = false ∧ (run Q s detTape t).core.regs 51 = rmax (side tlo thi) (m - 1) ∧ (run Q s detTape t).core.regs 52 = rmax (side lo hi) (m - 1) ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape t).core.ptrs x = s.core.ptrs x) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 51 → x ≠ 52 → x ≠ 54 → (run Q s detTape t).core.regs x = s.core.regs x) ∧ (run Q s detTape t).core.mem = s.core.mem ∧ (run Q s detTape t).integerMemory = s.integerMemory ∧ (run Q s detTape t).work = s.work + t ∧ cellsWritten Q s t = ∅) ∧
(∀ {m : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (lo hi : Fin m → ℝ) (σ : ℝ) (ks : ℕ) (hks : ks < m) (hσ : σ ≤ hi ⟨ks, hks⟩ - lo ⟨ks, hks⟩),
∀ (d k : ℕ) (s : State), k + d = ks → s.core.pc = off + 201 → s.halted = false → s.core.ptrs 1 = m → s.core.ptrs 53 = k → s.core.regs 52 = σ → BoxAt s (s.core.ptrs 43) lo hi → ∃ t k0, ∃ hk0 : k0 < m, k ≤ k0 ∧ k0 ≤ ks ∧ t ≤ 9 * d + 7 ∧ σ ≤ hi ⟨k0, hk0⟩ - lo ⟨k0, hk0⟩ ∧ (∀ j (hj : j < m), k ≤ j → j < k0 → ¬ σ ≤ hi ⟨j, hj⟩ - lo ⟨j, hj⟩) ∧ (run Q s detTape t).core.pc = off + 210 ∧ (run Q s detTape t).halted = false ∧ (run Q s detTape t).core.ptrs 53 = k0 ∧ (run Q s detTape t).core.regs 44 = lo ⟨k0, hk0⟩ ∧ (run Q s detTape t).core.regs 45 = hi ⟨k0, hk0⟩ ∧ (∀ x, x ≠ 53 → x ≠ 57 → (run Q s detTape t).core.ptrs x = s.core.ptrs x) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 54 → (run Q s detTape t).core.regs x = s.core.regs x) ∧ (run Q s detTape t).core.mem = s.core.mem ∧ (run Q s detTape t).integerMemory = s.integerMemory ∧ (run Q s detTape t).work = s.work + t ∧ cellsWritten Q s t = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (src : ℕ → ℝ) (L : ℕ),
∀ (k j : ℕ) (s : State), j + k = L → s.core.pc = off + 261 → s.halted = false → 1 ≤ s.core.ptrs 1 → s.core.ptrs 60 = L → s.core.ptrs 46 = j → s.core.ptrs 56 + L ≤ s.core.ptrs 50 → (∀ z, z < L → s.core.mem (s.core.ptrs 50 + z) = src z) → (∀ z, z < j → s.core.mem (s.core.ptrs 56 + z) = src z) → ∃ t, t ≤ 7 * k + 1 ∧ (run Q s detTape t).core.pc = off + 268 ∧ (run Q s detTape t).halted = false ∧ (∀ z, z < L → (run Q s detTape t).core.mem (s.core.ptrs 56 + z) = src z) ∧ (∀ z, (z < s.core.ptrs 56 ∨ s.core.ptrs 56 + L ≤ z) → (run Q s detTape t).core.mem z = s.core.mem z) ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape t).core.ptrs x = s.core.ptrs x) ∧ (∀ x, x ≠ 55 → (run Q s detTape t).core.regs x = s.core.regs x) ∧ (run Q s detTape t).integerMemory = s.integerMemory ∧ (run Q s detTape t).work = s.work + t ∧ ∀ c ∈ cellsWritten Q s t, c.1 = true ∧ s.core.ptrs 56 ≤ c.2 ∧ c.2 < s.core.ptrs 56 + L) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (src : ℕ → ℝ) (L : ℕ),
∀ (k j : ℕ) (s : State), j + k = L → s.core.pc = off + 13 → s.halted = false → 1 ≤ s.core.ptrs 1 → s.core.ptrs 60 = L → s.core.ptrs 46 = j → s.core.ptrs 43 + L ≤ s.core.ptrs 17 → (∀ z, z < L → s.core.mem (s.core.ptrs 17 + z) = src z) → (∀ z, z < j → s.core.mem (s.core.ptrs 43 + z) = src z) → ∃ t, t ≤ 7 * k + 1 ∧ (run Q s detTape t).core.pc = off + 20 ∧ (run Q s detTape t).halted = false ∧ (∀ z, z < L → (run Q s detTape t).core.mem (s.core.ptrs 43 + z) = src z) ∧ (∀ z, (z < s.core.ptrs 43 ∨ s.core.ptrs 43 + L ≤ z) → (run Q s detTape t).core.mem z = s.core.mem z) ∧ (∀ x, x ≠ 46 → x ≠ 50 → (run Q s detTape t).core.ptrs x = s.core.ptrs x) ∧ (∀ x, x ≠ 55 → (run Q s detTape t).core.regs x = s.core.regs x) ∧ (run Q s detTape t).integerMemory = s.integerMemory ∧ (run Q s detTape t).work = s.work + t ∧ ∀ c ∈ cellsWritten Q s t, c.1 = true ∧ s.core.ptrs 43 ≤ c.2 ∧ c.2 < s.core.ptrs 43 + L) := by sorry
end DetANN.HPIM.BDSource
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as part of a floor-free proof of DetANN.lemma_3_3 (Feng, Indyk, STOC 2027 submission, Lemma 3.3, p.7). These are pieces of the BSP construction block of DetANN.HPIM.build_block, split out so that each proof fits the verifier's time limit. The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.