Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Straight-line segments of the BSP construction block: init, dispatch and scan

Proved
DetANN.HPIM.BD.scan_steps

by milia · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximate-nearest-neighborcomputational-geometrydata-structures

Twenty-three straight-line facts about the program bd\mathrm{bd}bd of definition DetANN_HPIMBuildProg: the start, the task dispatch, the end and the point scan.

Every conjunct has the same shape. Let QQQ contain bd(o)\mathrm{bd}(o)bd(o) at offset ooo (Embeds Q (bd off) off), and let sss be a non-halted state at the stated pc with 1≤1\le1≤ pointer 1 and the stated hypotheses. Then after exactly the stated number ttt of steps, the run of QQQ from sss:

  • is at the stated pc (relative to ooo) and has not halted;
  • has the stated values in the changed registers and cells;
  • leaves all other pointer and real registers and all other real and integer cells unchanged;
  • has work s.work+ts.\mathrm{work}+ts.work+t, and its cellsWritten set consists of the listed cells.

Pointer 1 holds mmm, pointer 11 holds nnn, and ZZZ, RRR denote pointers 13, 14 of sss.

  1. Init 0→130\to130→13 (13 steps): pointer 40:=Z40:=Z40:=Z, 60:=2m60:=2m60:=2m, 68:=168:=168:=1, 69:=069:=069:=0; reals 40:=r240:=r^240:=r2, 41:=(cr)241:=(cr)^241:=(cr)2, 47:=cr47:=cr47:=cr, 49:=2r49:=2r49:=2r, 50:=050:=050:=0, 53:=253:=253:=2 (with r,cr,cr,c = reals 11, 12); pointers 14,43:=R−2m14,43:=R-2m14,43:=R−2m (the root box), 46:=046:=046:=0.
  2. Copy step 13→1313\to1313→13 (7): when i<2mi<2mi<2m (iii = pointer 46), real cell p43+ip_{43}+ip43​+i gets the value of p17+ip_{17}+ip17​+i, and i:=i+1i:=i+1i:=i+1.
  3. Copy exit 13→2013\to2013→20 (1): when i≥2mi\ge2mi≥2m.
  4. Root task 20→3420\to3420→34 (14): pointers 59,44:=Z−159,44:=Z-159,44:=Z−1 (the root slot), and the entry [p43,Z−1,p40][p_{43},Z-1,p_{40}][p43​,Z−1,p40​] is pushed at Z−4Z-4Z−4; pointers 13,42:=Z−413,42:=Z-413,42:=Z−4.
  5. Empty stack 34→39534\to39534→395 (1): when pointer 40≤40\le40≤ pointer 42.
  6. End 395→396395\to396395→396 (1): pointer 17:=I[p59]17:=I[p_{59}]17:=I[p59​].
  7. Pop 34→4534\to4534→45 (11): when the stack pointer eee (pointer 42) satisfies e<p40e<p_{40}e<p40​: pointers 43:=I[e]43:=I[e]43:=I[e], 44:=I[e+1]44:=I[e+1]44:=I[e+1], 42:=I[e+2]42:=I[e+2]42:=I[e+2]; the near box qqq: pointers 14,48:=R−2m14,48:=R-2m14,48:=R−2m; flag 49:=049:=049:=0, index 45:=045:=045:=0.
  8. Scan exit 45→13145\to13145→131 (1): when i≥ni\ge ni≥n (iii = pointer 45).
  9. Scan head 45→5345\to5345→53 (8): pointer 47 := the address of point iii; reals 42,43:=042,43:=042,43:=0; 46:=046:=046:=0.
  10. Distance exit 53→8653\to8653→86 (1): when j≥mj\ge mj≥m.
  11. Distance step 53→5353\to5353→53 (33): adds the jjj-th terms of both squared distances (point at pointer 47, box at pointer 43) to reals 42, 43; j:=j+1j:=j+1j:=j+1.
  12. Far 86→12686\to12686→126 (3): when real 42>42>42> real 40 (which holds r2r^2r2 under Env).
  13. Good 86→12886\to12886→128 (4): when real 42≤42\le42≤ real 40 and real 43≤43\le43≤ real 41 ((cr)2(cr)^2(cr)2).
  14. Near, update 86→9386\to9386→93 (6): when near, not good, and the flag (pointer 49) exceeds pointer 69 (0).
  15. Near, first 86→11686\to11686→116 (6): when near, not good, and the flag is at most pointer 69.
  16. Update exit 93→12693\to12693→126 (1).
  17. Update step 93→9393\to9393→93 (23): coordinate jjj of qqq becomes [min⁡(qj,xj),max⁡(qm+j,xj)][\min(q_j,x_j),\max(q_{m+j},x_j)][min(qj​,xj​),max(qm+j​,xj​)] for the point xxx.
  18. First step 116→116116\to116116→116 (9): coordinate jjj of qqq becomes [xj,xj][x_j,x_j][xj​,xj​].
  19. First exit 116→126116\to126116→126 (2): flag 49:=149:=149:=1.
  20. Next point 126→45126\to45126→45 (2): i:=i+1i:=i+1i:=i+1.
  21. Certified leaf 128→383128\to383128→383 (3): pointer 61:=i+161:=i+161:=i+1.
  22. No near point 131→383131\to383131→383 (2): when the flag is 0: pointer 61:=061:=061:=0.
  23. Near points 131→134131\to134131→134 (3): when the flag is 1: pointers 46:=046:=046:=0, 61:=061:=061:=0.
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 scan_steps :
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 0) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 13).core.pc = off + 13 ∧ (run Q s detTape 13).halted = false ∧ (run Q s detTape 13).core.ptrs 14 = s.core.ptrs 14 - 2 * s.core.ptrs 1 ∧ (run Q s detTape 13).core.ptrs 40 = s.core.ptrs 13 ∧ (run Q s detTape 13).core.ptrs 43 = s.core.ptrs 14 - 2 * s.core.ptrs 1 ∧ (run Q s detTape 13).core.ptrs 46 = 0 ∧ (run Q s detTape 13).core.ptrs 60 = 2 * s.core.ptrs 1 ∧ (run Q s detTape 13).core.ptrs 68 = 1 ∧ (run Q s detTape 13).core.ptrs 69 = 0 ∧ (∀ x, x ≠ 14 → x ≠ 40 → x ≠ 43 → x ≠ 46 → x ≠ 60 → x ≠ 68 → x ≠ 69 → (run Q s detTape 13).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 13).core.regs 40 = (s.core.regs 11 * s.core.regs 11) ∧ (run Q s detTape 13).core.regs 41 = ((s.core.regs 12 * s.core.regs 11) * (s.core.regs 12 * s.core.regs 11)) ∧ (run Q s detTape 13).core.regs 47 = (s.core.regs 12 * s.core.regs 11) ∧ (run Q s detTape 13).core.regs 49 = (s.core.regs 11 + s.core.regs 11) ∧ (run Q s detTape 13).core.regs 50 = (0 : ℝ) ∧ (run Q s detTape 13).core.regs 53 = (2 : ℝ) ∧ (∀ x, x ≠ 40 → x ≠ 41 → x ≠ 47 → x ≠ 49 → x ≠ 50 → x ≠ 53 → (run Q s detTape 13).core.regs x = s.core.regs x) ∧ (run Q s detTape 13).core.mem = s.core.mem ∧ (run Q s detTape 13).integerMemory = s.integerMemory ∧ (run Q s detTape 13).work = s.work + 13 ∧ cellsWritten Q s 13 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (x : ℝ) (s : State) (hpc : s.core.pc = off + 13) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 17 + s.core.ptrs 46) = x) (hb0 : s.core.ptrs 46 < s.core.ptrs 60) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 7).core.pc = off + 13 ∧ (run Q s detTape 7).halted = false ∧ (run Q s detTape 7).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 7).core.ptrs 50 = s.core.ptrs 43 + s.core.ptrs 46 ∧ (∀ x, x ≠ 46 → x ≠ 50 → (run Q s detTape 7).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 7).core.regs 55 = x ∧ (∀ x, x ≠ 55 → (run Q s detTape 7).core.regs x = s.core.regs x) ∧ (run Q s detTape 7).core.mem (s.core.ptrs 43 + s.core.ptrs 46) = x ∧ (∀ z, z ≠ s.core.ptrs 43 + s.core.ptrs 46 → (run Q s detTape 7).core.mem z = s.core.mem z) ∧ (run Q s detTape 7).integerMemory = s.integerMemory ∧ (run Q s detTape 7).work = s.work + 7 ∧ ∀ c ∈ cellsWritten Q s 7, c = (true, s.core.ptrs 43 + s.core.ptrs 46)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 13) (hh : s.halted = false) (hb0 : s.core.ptrs 60 ≤ s.core.ptrs 46) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 1).core.pc = off + 20 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs = s.core.ptrs ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 20) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 14).core.pc = off + 34 ∧ (run Q s detTape 14).halted = false ∧ (run Q s detTape 14).core.ptrs 13 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 14).core.ptrs 42 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 14).core.ptrs 44 = s.core.ptrs 13 - 1 ∧ (run Q s detTape 14).core.ptrs 57 = s.core.ptrs 13 - 2 ∧ (run Q s detTape 14).core.ptrs 59 = s.core.ptrs 13 - 1 ∧ (∀ x, x ≠ 13 → x ≠ 42 → x ≠ 44 → x ≠ 57 → x ≠ 59 → (run Q s detTape 14).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 14).core.regs = s.core.regs ∧ (run Q s detTape 14).core.mem = s.core.mem ∧ (run Q s detTape 14).integerMemory (s.core.ptrs 13 - 4) = s.core.ptrs 43 ∧ (run Q s detTape 14).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 13 - 1 ∧ (run Q s detTape 14).integerMemory (s.core.ptrs 13 - 2) = s.core.ptrs 40 ∧ (∀ z, z ≠ s.core.ptrs 13 - 4 → z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 13 - 2 → (run Q s detTape 14).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 14).work = s.work + 14 ∧ ∀ c ∈ cellsWritten Q s 14, c = (false, s.core.ptrs 13 - 4) ∨ c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 13 - 2)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 34) (hh : s.halted = false) (hb0 : s.core.ptrs 40 ≤ s.core.ptrs 42) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 1).core.pc = off + 395 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs = s.core.ptrs ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (rt : ℤ) (s : State) (hpc : s.core.pc = off + 395) (hh : s.halted = false) (fi0 : s.integerMemory (s.core.ptrs 59) = rt) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 1).core.pc = off + 396 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs 17 = rt ∧ (∀ x, x ≠ 17 → (run Q s detTape 1).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (ep esl elink : ℤ) (s : State) (hpc : s.core.pc = off + 34) (hh : s.halted = false) (fi0 : s.integerMemory (s.core.ptrs 42) = ep) (fi1 : s.integerMemory (s.core.ptrs 42 + 1) = esl) (fi2 : s.integerMemory (s.core.ptrs 42 + 2) = elink) (hb0 : s.core.ptrs 42 < s.core.ptrs 40) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 11).core.pc = off + 45 ∧ (run Q s detTape 11).halted = false ∧ (run Q s detTape 11).core.ptrs 14 = s.core.ptrs 14 - s.core.ptrs 60 ∧ (run Q s detTape 11).core.ptrs 42 = elink ∧ (run Q s detTape 11).core.ptrs 43 = ep ∧ (run Q s detTape 11).core.ptrs 44 = esl ∧ (run Q s detTape 11).core.ptrs 45 = 0 ∧ (run Q s detTape 11).core.ptrs 48 = s.core.ptrs 14 - s.core.ptrs 60 ∧ (run Q s detTape 11).core.ptrs 49 = 0 ∧ (run Q s detTape 11).core.ptrs 57 = s.core.ptrs 42 + 2 ∧ (∀ x, x ≠ 14 → x ≠ 42 → x ≠ 43 → x ≠ 44 → x ≠ 45 → x ≠ 48 → x ≠ 49 → x ≠ 57 → (run Q s detTape 11).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 11).core.regs = s.core.regs ∧ (run Q s detTape 11).core.mem = s.core.mem ∧ (run Q s detTape 11).integerMemory = s.integerMemory ∧ (run Q s detTape 11).work = s.work + 11 ∧ cellsWritten Q s 11 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 45) (hh : s.halted = false) (hb0 : s.core.ptrs 11 ≤ s.core.ptrs 45) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 1).core.pc = off + 131 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs = s.core.ptrs ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (ki pa : ℤ) (s : State) (hpc : s.core.pc = off + 45) (hh : s.halted = false) (fi0 : s.integerMemory (s.core.ptrs 10 + s.core.ptrs 45) = ki) (fi1 : s.integerMemory (s.core.ptrs 12 + ki) = pa) (hb0 : s.core.ptrs 45 < s.core.ptrs 11) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 8).core.pc = off + 53 ∧ (run Q s detTape 8).halted = false ∧ (run Q s detTape 8).core.ptrs 46 = 0 ∧ (run Q s detTape 8).core.ptrs 47 = pa ∧ (run Q s detTape 8).core.ptrs 57 = s.core.ptrs 12 + ki ∧ (∀ x, x ≠ 46 → x ≠ 47 → x ≠ 57 → (run Q s detTape 8).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 8).core.regs 42 = (0 : ℝ) ∧ (run Q s detTape 8).core.regs 43 = (0 : ℝ) ∧ (∀ x, x ≠ 42 → x ≠ 43 → (run Q s detTape 8).core.regs x = s.core.regs x) ∧ (run Q s detTape 8).core.mem = s.core.mem ∧ (run Q s detTape 8).integerMemory = s.integerMemory ∧ (run Q s detTape 8).work = s.work + 8 ∧ cellsWritten Q s 8 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 53) (hh : s.halted = false) (hb0 : s.core.ptrs 1 ≤ s.core.ptrs 46) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 1).core.pc = off + 86 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs = s.core.ptrs ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (x lo hi : ℝ) (s : State) (hpc : s.core.pc = off + 53) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 47 + s.core.ptrs 46) = x) (fr1 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 46) = lo) (fr2 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 46 + s.core.ptrs 1) = hi) (hb0 : s.core.ptrs 46 < s.core.ptrs 1) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 33).core.pc = off + 53 ∧ (run Q s detTape 33).halted = false ∧ (run Q s detTape 33).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 33).core.ptrs 57 = s.core.ptrs 43 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape 33).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 33).core.regs 42 = (s.core.regs 42 + (((((lo - x) + (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)) + Real.sqrt (((lo - x) - (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)) * ((lo - x) - (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)))) / s.core.regs 53) * ((((lo - x) + (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)) + Real.sqrt (((lo - x) - (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)) * ((lo - x) - (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)))) / s.core.regs 53))) ∧ (run Q s detTape 33).core.regs 43 = (s.core.regs 43 + (((((x - lo) + (hi - x)) + Real.sqrt (((x - lo) - (hi - x)) * ((x - lo) - (hi - x)))) / s.core.regs 53) * ((((x - lo) + (hi - x)) + Real.sqrt (((x - lo) - (hi - x)) * ((x - lo) - (hi - x)))) / s.core.regs 53))) ∧ (run Q s detTape 33).core.regs 44 = x ∧ (run Q s detTape 33).core.regs 45 = lo ∧ (run Q s detTape 33).core.regs 46 = hi ∧ (run Q s detTape 33).core.regs 47 = ((((x - lo) + (hi - x)) + Real.sqrt (((x - lo) - (hi - x)) * ((x - lo) - (hi - x)))) / s.core.regs 53) ∧ (run Q s detTape 33).core.regs 48 = (hi - x) ∧ (run Q s detTape 33).core.regs 54 = (((((x - lo) + (hi - x)) + Real.sqrt (((x - lo) - (hi - x)) * ((x - lo) - (hi - x)))) / s.core.regs 53) * ((((x - lo) + (hi - x)) + Real.sqrt (((x - lo) - (hi - x)) * ((x - lo) - (hi - x)))) / s.core.regs 53)) ∧ (∀ x, x ≠ 42 → x ≠ 43 → x ≠ 44 → x ≠ 45 → x ≠ 46 → x ≠ 47 → x ≠ 48 → x ≠ 54 → (run Q s detTape 33).core.regs x = s.core.regs x) ∧ (run Q s detTape 33).core.mem = s.core.mem ∧ (run Q s detTape 33).integerMemory = s.integerMemory ∧ (run Q s detTape 33).work = s.work + 33 ∧ cellsWritten Q s 33 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 86) (hh : s.halted = false) (hb0 : ¬ (s.core.regs 42 - s.core.regs 40) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 3).core.pc = off + 126 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs = s.core.ptrs ∧ (run Q s detTape 3).core.regs 54 = (s.core.regs 42 - s.core.regs 40) ∧ (∀ x, x ≠ 54 → (run Q s detTape 3).core.regs x = s.core.regs x) ∧ (run Q s detTape 3).core.mem = s.core.mem ∧ (run Q s detTape 3).integerMemory = s.integerMemory ∧ (run Q s detTape 3).work = s.work + 3 ∧ cellsWritten Q s 3 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 86) (hh : s.halted = false) (hb0 : (s.core.regs 42 - s.core.regs 40) ≤ 0) (hb1 : (s.core.regs 43 - s.core.regs 41) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 4).core.pc = off + 128 ∧ (run Q s detTape 4).halted = false ∧ (run Q s detTape 4).core.ptrs = s.core.ptrs ∧ (run Q s detTape 4).core.regs 54 = (s.core.regs 43 - s.core.regs 41) ∧ (∀ x, x ≠ 54 → (run Q s detTape 4).core.regs x = s.core.regs x) ∧ (run Q s detTape 4).core.mem = s.core.mem ∧ (run Q s detTape 4).integerMemory = s.integerMemory ∧ (run Q s detTape 4).work = s.work + 4 ∧ cellsWritten Q s 4 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 86) (hh : s.halted = false) (hb0 : (s.core.regs 42 - s.core.regs 40) ≤ 0) (hb1 : ¬ (s.core.regs 43 - s.core.regs 41) ≤ 0) (hb2 : s.core.ptrs 69 < s.core.ptrs 49) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 6).core.pc = off + 93 ∧ (run Q s detTape 6).halted = false ∧ (run Q s detTape 6).core.ptrs 46 = 0 ∧ (∀ x, x ≠ 46 → (run Q s detTape 6).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 6).core.regs 54 = (s.core.regs 43 - s.core.regs 41) ∧ (∀ x, x ≠ 54 → (run Q s detTape 6).core.regs x = s.core.regs x) ∧ (run Q s detTape 6).core.mem = s.core.mem ∧ (run Q s detTape 6).integerMemory = s.integerMemory ∧ (run Q s detTape 6).work = s.work + 6 ∧ cellsWritten Q s 6 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 86) (hh : s.halted = false) (hb0 : (s.core.regs 42 - s.core.regs 40) ≤ 0) (hb1 : ¬ (s.core.regs 43 - s.core.regs 41) ≤ 0) (hb2 : s.core.ptrs 49 ≤ s.core.ptrs 69) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 6).core.pc = off + 116 ∧ (run Q s detTape 6).halted = false ∧ (run Q s detTape 6).core.ptrs 46 = 0 ∧ (∀ x, x ≠ 46 → (run Q s detTape 6).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 6).core.regs 54 = (s.core.regs 43 - s.core.regs 41) ∧ (∀ x, x ≠ 54 → (run Q s detTape 6).core.regs x = s.core.regs x) ∧ (run Q s detTape 6).core.mem = s.core.mem ∧ (run Q s detTape 6).integerMemory = s.integerMemory ∧ (run Q s detTape 6).work = s.work + 6 ∧ cellsWritten Q s 6 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 93) (hh : s.halted = false) (hb0 : s.core.ptrs 1 ≤ s.core.ptrs 46) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 1).core.pc = off + 126 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs = s.core.ptrs ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (x mn mx : ℝ) (s : State) (hpc : s.core.pc = off + 93) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 47 + s.core.ptrs 46) = x) (fr1 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46) = mn) (fr2 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = mx) (hb0 : s.core.ptrs 46 < s.core.ptrs 1) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 23).core.pc = off + 93 ∧ (run Q s detTape 23).halted = false ∧ (run Q s detTape 23).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 23).core.ptrs 57 = s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape 23).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 23).core.regs 44 = x ∧ (run Q s detTape 23).core.regs 45 = mx ∧ (run Q s detTape 23).core.regs 47 = (((mx + x) + Real.sqrt ((mx - x) * (mx - x))) / s.core.regs 53) ∧ (run Q s detTape 23).core.regs 54 = Real.sqrt ((mx - x) * (mx - x)) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 54 → (run Q s detTape 23).core.regs x = s.core.regs x) ∧ (run Q s detTape 23).core.mem (s.core.ptrs 48 + s.core.ptrs 46) = (((mn + x) - Real.sqrt ((mn - x) * (mn - x))) / s.core.regs 53) ∧ (run Q s detTape 23).core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = (((mx + x) + Real.sqrt ((mx - x) * (mx - x))) / s.core.regs 53) ∧ (∀ z, z ≠ s.core.ptrs 48 + s.core.ptrs 46 → z ≠ s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1 → (run Q s detTape 23).core.mem z = s.core.mem z) ∧ (run Q s detTape 23).integerMemory = s.integerMemory ∧ (run Q s detTape 23).work = s.work + 23 ∧ ∀ c ∈ cellsWritten Q s 23, c = (true, s.core.ptrs 48 + s.core.ptrs 46) ∨ c = (true, s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (x : ℝ) (s : State) (hpc : s.core.pc = off + 116) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 47 + s.core.ptrs 46) = x) (hb0 : s.core.ptrs 46 < s.core.ptrs 1) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 9).core.pc = off + 116 ∧ (run Q s detTape 9).halted = false ∧ (run Q s detTape 9).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 9).core.ptrs 57 = s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape 9).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 9).core.regs 44 = x ∧ (∀ x, x ≠ 44 → (run Q s detTape 9).core.regs x = s.core.regs x) ∧ (run Q s detTape 9).core.mem (s.core.ptrs 48 + s.core.ptrs 46) = x ∧ (run Q s detTape 9).core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = x ∧ (∀ z, z ≠ s.core.ptrs 48 + s.core.ptrs 46 → z ≠ s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1 → (run Q s detTape 9).core.mem z = s.core.mem z) ∧ (run Q s detTape 9).integerMemory = s.integerMemory ∧ (run Q s detTape 9).work = s.work + 9 ∧ ∀ c ∈ cellsWritten Q s 9, c = (true, s.core.ptrs 48 + s.core.ptrs 46) ∨ c = (true, s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1)) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 116) (hh : s.halted = false) (hb0 : s.core.ptrs 1 ≤ s.core.ptrs 46) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 2).core.pc = off + 126 ∧ (run Q s detTape 2).halted = false ∧ (run Q s detTape 2).core.ptrs 49 = 1 ∧ (∀ x, x ≠ 49 → (run Q s detTape 2).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 2).core.regs = s.core.regs ∧ (run Q s detTape 2).core.mem = s.core.mem ∧ (run Q s detTape 2).integerMemory = s.integerMemory ∧ (run Q s detTape 2).work = s.work + 2 ∧ cellsWritten Q s 2 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 126) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 2).core.pc = off + 45 ∧ (run Q s detTape 2).halted = false ∧ (run Q s detTape 2).core.ptrs 45 = s.core.ptrs 45 + 1 ∧ (∀ x, x ≠ 45 → (run Q s detTape 2).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 2).core.regs = s.core.regs ∧ (run Q s detTape 2).core.mem = s.core.mem ∧ (run Q s detTape 2).integerMemory = s.integerMemory ∧ (run Q s detTape 2).work = s.work + 2 ∧ cellsWritten Q s 2 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 128) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 3).core.pc = off + 383 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs 61 = s.core.ptrs 45 + 1 ∧ (∀ x, x ≠ 61 → (run Q s detTape 3).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 3).core.regs = s.core.regs ∧ (run Q s detTape 3).core.mem = s.core.mem ∧ (run Q s detTape 3).integerMemory = s.integerMemory ∧ (run Q s detTape 3).work = s.work + 3 ∧ cellsWritten Q s 3 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 131) (hh : s.halted = false) (hb0 : s.core.ptrs 49 ≤ s.core.ptrs 69) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 2).core.pc = off + 383 ∧ (run Q s detTape 2).halted = false ∧ (run Q s detTape 2).core.ptrs 61 = 0 ∧ (∀ x, x ≠ 61 → (run Q s detTape 2).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 2).core.regs = s.core.regs ∧ (run Q s detTape 2).core.mem = s.core.mem ∧ (run Q s detTape 2).integerMemory = s.integerMemory ∧ (run Q s detTape 2).work = s.work + 2 ∧ cellsWritten Q s 2 = ∅) ∧
    (∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 131) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 49) (hm1 : 1 ≤ s.core.ptrs 1),
      (run Q s detTape 3).core.pc = off + 134 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs 46 = 0 ∧ (run Q s detTape 3).core.ptrs 61 = 0 ∧ (∀ x, x ≠ 46 → x ≠ 61 → (run Q s detTape 3).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 3).core.regs = s.core.regs ∧ (run Q s detTape 3).core.mem = s.core.mem ∧ (run Q s detTape 3).integerMemory = s.integerMemory ∧ (run Q s detTape 3).work = s.work + 3 ∧ cellsWritten Q s 3 = ∅) := by sorry

end DetANN.HPIM.BD
Source
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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me