Components block
ProvedDetANN.HPIM.comps_blockapproximate-nearest-neighborcomputational-geometrydata-structures
There are a block of fixed length (definition DetANN_HPIMPreBlocks) and a constant such that the following holds in every host program that embeds at .
Assume:
- , and the local points are stored (
LocalPts); - real register holds a threshold ;
- the run starts at , not halted;
- the integer scratch top (pointer ) is .
Then the run reaches without halting, and:
- for every , integer cell holds , the least index in the component of in the threshold graph at ;
- all host registers are unchanged;
- it writes only integer scratch cells in ;
- its work is at most .
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMPreBlocks import Definitions.Def_DetANN_HPIMLayout
Formal statement
namespace DetANN.HPIM
open PNormReg PNormRegLib
/-- **Components block.** On `n` local points and a threshold `d ≥ 0` (real register `10`), it
writes `compMin pts d i` to integer cell `Z − 1 − i` for every `i < n` (`Z` = pointer `13`). It
writes only integer scratch cells `[Z − C(n+1), Z)`, and its work is at most `C (n+1)^3 (m+1)`. -/
theorem comps_block :
∃ blk : ℕ → Program, ∃ L C : ℕ, IsBlock blk L ∧
∀ (off : ℕ) (Q : Program), Embeds Q (blk off) off →
∀ (m n : ℕ) (pts : Fin n → EuclideanSpace ℝ (Fin m)) (d : ℝ) (s : State),
1 ≤ m → 1 ≤ n → s.core.pc = off → s.halted = false →
LocalPts s (fun i j => pts i j) → s.core.regs 10 = d → 0 ≤ d → s.core.ptrs 13 ≤ 0 →
∃ t, (run Q s detTape t).core.pc = off + L ∧ (run Q s detTape t).halted = false ∧
(∀ i : Fin n, (run Q s detTape t).integerMemory (s.core.ptrs 13 - 1 - i) = compMin pts d i) ∧
KeepsLow s (run Q s detTape t) [] [] ∧
WritesOnly Q s t (fun c => c.1 = false ∧
s.core.ptrs 13 - C * (n + 1) ≤ c.2 ∧ c.2 < s.core.ptrs 13) ∧
(run Q s detTape t).work ≤ s.work + C * (n + 1) ^ 3 * (m + 1) := by sorry
end DetANN.HPIMSource
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): the preprocessing program of DetANN.HPIM.hpim_preprocessing is assembled from these blocks. The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.