Composite parts of the BSP construction block: the split and the two peels
ProvedDetANN.HPIM.BD.peel_specsapproximate-nearest-neighborcomputational-geometrydata-structures
Three composite facts about the program of definition DetANN_HPIMBuildProg, stated with Env, BoxAt and Fr from the same definition. In each, contains at offset , is not halted, Env s pts r c Z0 holds and . , are pointers 13, 14 of .
- Split (from 197, when , real 52 holds of the task box at pointer 43, and ). Some and with bring the run to 34 (not halted). With :
- there is a cut node at , with ;
- the left half is stored at and the right half at ;
- the entries at and at are pushed, with pointers and ;
- the constant registers, pointers below 13 and between 14 and 42, 59, 60, 68, 69, and reals below 44 and 49, 50, 53 are kept;
- real cells outside and integer cells outside are kept, and the writes stay in these windows.
- Low peel (from 283 with axis , the current box at pointer 54 and the core at pointer 48, when ; the current slot satisfies , and , , ). Some gives , the pc 326,
Envfor , and:- pointers , , , , with 48 and 53 kept;
- a cut node at , with ;
- the entry at ;
- the low slab at and the rest at .
- High peel (from 326, when ; same hypotheses). The same as 2, except that the pc is 283, the axis is , the current slot is , the entry is , the high slab is at and the rest is at .
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 peel_specs :
(∀ {m n : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (pts : Fin n → Fin m → ℝ) (r c : ℝ) (Z0 : ℤ) (hm : 1 ≤ m) (lo hi : Fin m → ℝ) (s : State) (hpc : s.core.pc = off + 197) (hh : s.halted = false) (hEnv : Env s pts r c Z0) (h52 : s.core.regs 52 = sigma lo hi) (hc : ¬ (s.core.regs 51 + s.core.regs 51 - s.core.regs 52 ≤ 0)) (hB : BoxAt s (s.core.ptrs 43) lo hi) (hsl : s.core.ptrs 13 ≤ s.core.ptrs 44) (hp : s.core.ptrs 14 ≤ s.core.ptrs 43),
∃ (t : ℕ) (s' : State) (k : Fin m), run Q s detTape t = s' ∧ t ≤ 37 * m + 91 ∧ longestAxis lo hi = some k ∧ s'.core.pc = off + 34 ∧ s'.halted = false ∧ s'.core.ptrs 13 = s.core.ptrs 13 - 10 ∧ s'.core.ptrs 14 = s.core.ptrs 14 - 4 * m ∧ s'.core.ptrs 42 = s.core.ptrs 13 - 10 ∧ s'.integerMemory (s.core.ptrs 13 - 4) = 1 ∧ s'.integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 43 ∧ s'.integerMemory (s.core.ptrs 44) = s.core.ptrs 13 - 4 ∧ s'.integerMemory (s.core.ptrs 13 - 7) = s.core.ptrs 14 - 2 * m ∧ s'.integerMemory (s.core.ptrs 13 - 6) = s.core.ptrs 13 - 2 ∧ s'.integerMemory (s.core.ptrs 13 - 5) = s.core.ptrs 42 ∧ s'.integerMemory (s.core.ptrs 13 - 10) = s.core.ptrs 14 - 4 * m ∧ s'.integerMemory (s.core.ptrs 13 - 9) = s.core.ptrs 13 - 1 ∧ s'.integerMemory (s.core.ptrs 13 - 8) = s.core.ptrs 13 - 7 ∧ BoxAt s' (s.core.ptrs 14 - 2 * m) lo (setCoord hi k ((lo k + hi k) / 2)) ∧ BoxAt s' (s.core.ptrs 14 - 4 * m) (setCoord lo k ((lo k + hi k) / 2)) hi ∧ (∀ x, (x < 13 ∨ (14 < x ∧ x < 42) ∨ x = 40 ∨ x = 59 ∨ x = 60 ∨ x = 68 ∨ x = 69) → s'.core.ptrs x = s.core.ptrs x) ∧ (∀ x, (x < 44 ∨ x = 49 ∨ x = 50 ∨ x = 53) → s'.core.regs x = s.core.regs x) ∧ (∀ z, (z < s.core.ptrs 14 - 4 * m ∨ s.core.ptrs 14 ≤ z) → s'.core.mem z = s.core.mem z) ∧ (∀ z, (z < s.core.ptrs 13 - 10 ∨ s.core.ptrs 13 ≤ z) → z ≠ s.core.ptrs 44 → s'.integerMemory z = s.integerMemory z) ∧ s'.work = s.work + t ∧ (∀ w ∈ cellsWritten Q s t, (w.1 = false ∧ ((s.core.ptrs 13 - 10 ≤ w.2 ∧ w.2 < s.core.ptrs 13) ∨ w.2 = s.core.ptrs 44)) ∨ (w.1 = true ∧ s.core.ptrs 14 - 4 * m ≤ w.2 ∧ w.2 < s.core.ptrs 14))) ∧
(∀ {m n : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (pts : Fin n → Fin m → ℝ) (r c : ℝ) (Z0 : ℤ) (hm : 1 ≤ m) (s : State) (hpc : s.core.pc = off + 283) (hh : s.halted = false) (hEnv : Env s pts r c Z0) (k : ℕ) (hk : k < m) (h53 : s.core.ptrs 53 = k) (tlo thi lo hi : Fin m → ℝ) (hQ : BoxAt s (s.core.ptrs 48) tlo thi) (hB : BoxAt s (s.core.ptrs 54) lo hi) (hlow : lo ⟨k, hk⟩ < tlo ⟨k, hk⟩) (hcsl : s.core.ptrs 13 ≤ s.core.ptrs 55) (hcb : s.core.ptrs 14 ≤ s.core.ptrs 54) (hq : s.core.ptrs 14 ≤ s.core.ptrs 48) (hZ : s.core.ptrs 13 ≤ 0) (hcsl0 : s.core.ptrs 55 < 0) (hR : s.core.ptrs 14 ≤ 0),
∃ (t : ℕ) (s' : State), Fr Q s s' t (fun z => z = s.core.ptrs 55) ∧ t ≤ 28 * m + 80 ∧ s'.core.pc = off + 326 ∧ s'.halted = false ∧ Env s' pts r c Z0 ∧ s'.core.ptrs 13 = s.core.ptrs 13 - 7 ∧ s'.core.ptrs 14 = s.core.ptrs 14 - 4 * m ∧ s'.core.ptrs 42 = s.core.ptrs 13 - 7 ∧ s'.core.ptrs 48 = s.core.ptrs 48 ∧ s'.core.ptrs 53 = k ∧ s'.core.ptrs 54 = s.core.ptrs 14 - 4 * m ∧ s'.core.ptrs 55 = s.core.ptrs 13 - 1 ∧ s'.integerMemory (s.core.ptrs 13 - 4) = 1 ∧ s'.integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 54 ∧ s'.integerMemory (s.core.ptrs 55) = s.core.ptrs 13 - 4 ∧ s'.integerMemory (s.core.ptrs 13 - 7) = s.core.ptrs 14 - 2 * m ∧ s'.integerMemory (s.core.ptrs 13 - 6) = s.core.ptrs 13 - 2 ∧ s'.integerMemory (s.core.ptrs 13 - 5) = s.core.ptrs 42 ∧ BoxAt s' (s.core.ptrs 14 - 2 * m) lo (setCoord hi k (tlo ⟨k, hk⟩)) ∧ BoxAt s' (s.core.ptrs 14 - 4 * m) (setCoord lo k (tlo ⟨k, hk⟩)) hi) ∧
(∀ {m n : ℕ} (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (pts : Fin n → Fin m → ℝ) (r c : ℝ) (Z0 : ℤ) (hm : 1 ≤ m) (s : State) (hpc : s.core.pc = off + 326) (hh : s.halted = false) (hEnv : Env s pts r c Z0) (k : ℕ) (hk : k < m) (h53 : s.core.ptrs 53 = k) (tlo thi lo hi : Fin m → ℝ) (hQ : BoxAt s (s.core.ptrs 48) tlo thi) (hB : BoxAt s (s.core.ptrs 54) lo hi) (hhigh : hi ⟨k, hk⟩ > thi ⟨k, hk⟩) (hcsl : s.core.ptrs 13 ≤ s.core.ptrs 55) (hcb : s.core.ptrs 14 ≤ s.core.ptrs 54) (hq : s.core.ptrs 14 ≤ s.core.ptrs 48) (hZ : s.core.ptrs 13 ≤ 0) (hcsl0 : s.core.ptrs 55 < 0) (hR : s.core.ptrs 14 ≤ 0),
∃ (t : ℕ) (s' : State), Fr Q s s' t (fun z => z = s.core.ptrs 55) ∧ t ≤ 28 * m + 80 ∧ s'.core.pc = off + 283 ∧ s'.halted = false ∧ Env s' pts r c Z0 ∧ s'.core.ptrs 13 = s.core.ptrs 13 - 7 ∧ s'.core.ptrs 14 = s.core.ptrs 14 - 4 * m ∧ s'.core.ptrs 42 = s.core.ptrs 13 - 7 ∧ s'.core.ptrs 48 = s.core.ptrs 48 ∧ s'.core.ptrs 53 = k + 1 ∧ s'.core.ptrs 54 = s.core.ptrs 14 - 4 * m ∧ s'.core.ptrs 55 = s.core.ptrs 13 - 2 ∧ s'.integerMemory (s.core.ptrs 13 - 4) = 1 ∧ s'.integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 54 ∧ s'.integerMemory (s.core.ptrs 55) = s.core.ptrs 13 - 4 ∧ s'.integerMemory (s.core.ptrs 13 - 7) = s.core.ptrs 14 - 2 * m ∧ s'.integerMemory (s.core.ptrs 13 - 6) = s.core.ptrs 13 - 1 ∧ s'.integerMemory (s.core.ptrs 13 - 5) = s.core.ptrs 42 ∧ BoxAt s' (s.core.ptrs 14 - 2 * m) (setCoord lo k (thi ⟨k, hk⟩)) hi ∧ BoxAt s' (s.core.ptrs 14 - 4 * m) lo (setCoord hi k (thi ⟨k, hk⟩))) := 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.