The dedupe loop of the construction program
ProvedDetANN.Supplement.Thm32.pre_dedup_specapproximate-nearest-neighborprogram-verificationreal-ram
Let contain at offset , let , and let with the points () in the real cells . Let be a running state at with pointer 22 , pointer 3 and pointer 23 .
Then for some the run is at after steps, has not halted, and:
- (definition
DetANN_Supplement_PreDedup); - pointer 28 holds , pointer 26 holds , pointer 23 holds ;
- the pointers other than 10, 11, 20, 23, 26–32 and the reals other than 0–2 are unchanged;
- the real cells below and the integer memory are unchanged, and the work grows by exactly .
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_DetANN_DataStructure import Definitions.Def_PNormRegLib_Reloc import Definitions.Def_DetANN_Sylvester import Definitions.Def_DetANN_SignedBlocks import Definitions.Def_DetANN_Supplement_EvProg import Definitions.Def_DetANN_Supplement_PreProg import Definitions.Def_DetANN_Supplement_PreDedup
Formal statement
namespace DetANN.Supplement.Thm32
open PNormReg PNormRegLib DetANN
/-- **The dedupe loop of `pre`.** From `off + 67`, with the points `x i` at the real cells `1 + i·d`
and `top = Db ≥ 1 + n·d`, the program `pre q` reaches `off + 115` with the list `ddList x n`
(definition `DetANN_Supplement_PreDedup`) stored at `Db` (`TableAt`), its length in pointer `28` and
`top = Db + |ddList x n|·d`. Cells below `Db` are unchanged. -/
theorem pre_dedup_spec :
∀ {d : ℕ} (Q : Program) (off : ℕ) (q : ℚ) (hE : Embeds Q (pre q off) off) (hd1 : 1 ≤ d)
(n : ℕ) (x : ℕ → EuclideanSpace ℝ (Fin d)) (Db : ℤ) (hDb : ((1 + n * d : ℕ) : ℤ) ≤ Db)
(s : State) (hpc : s.core.pc = off + 67) (hh : s.halted = false)
(h22 : s.core.ptrs 22 = n) (h3 : s.core.ptrs 3 = d) (h23 : s.core.ptrs 23 = Db)
(hx : ∀ i' : ℕ, i' < n → ∀ c : Fin d, s.core.mem ((1 + i' * d + c : ℕ) : ℤ) = x i' c),
∃ t, t ≤ n * (n * pairB d (n * n) + 8) + 7 ∧ (run Q s detTape t).core.pc = off + 115 ∧
(run Q s detTape t).halted = false ∧
(run Q s detTape t).core.ptrs 23 = Db + (((ddList x n).length * d : ℕ) : ℤ) ∧
(run Q s detTape t).core.ptrs 28 = (ddList x n).length ∧
(run Q s detTape t).core.ptrs 26 = Db ∧
(∀ y, y ≠ 10 → y ≠ 11 → y ≠ 20 → y ≠ 23 → y ≠ 26 → y ≠ 27 → y ≠ 28 → y ≠ 29 → y ≠ 30 →
y ≠ 31 → y ≠ 32 → (run Q s detTape t).core.ptrs y = s.core.ptrs y) ∧
(∀ y, y ≠ 0 → y ≠ 1 → y ≠ 2 → (run Q s detTape t).core.regs y = s.core.regs y) ∧
TableAt (run Q s detTape t).core.mem Db (ddList x n) ∧
(∀ z, z < Db → (run Q s detTape t).core.mem z = s.core.mem z) ∧
(run Q s detTape t).integerMemory = s.integerMemory ∧
(run Q s detTape t).work = s.work + t := by sorry
end DetANN.Supplement.Thm32Source
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as part of a proof of DetANN.Supplement.theorem_3_2 (Feng, Indyk, STOC 2027 submission, Theorem 3.2, p.7; the construction of §6.1, p.14, and Lemma 6.2). The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.