The node contract
ProvedDetANN.HPIM.PP.node_specapproximate-nearest-neighborcomputational-geometrydata-structures
Let be blocks with Blocks.WF and ChildOK B, , injective and . If the constants satisfy Budgets (definition DetANN_HPIMPreProg), then the node contract NodeOK holds at every fuel .
In words: from NODE with a well-formed record for a set of at most points, the run reaches RETURN with the global invariant intact, and:
- it stores at the record;
- it uses at most work and , heap cells;
- it writes only its record, the new heap and bounded scratch windows.
The proof is by induction on , combining the node head (median, ladder), lk_loop and kids_loop, and a tail call on the representatives.
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMPreProg import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_Exec import Definitions.Def_DetANN_DataStructure import Definitions.Def_DetANN_HPIMLayout import Definitions.Def_DetANN_HPIMWF import Definitions.Def_PNormRegLib_Reloc import Definitions.Def_DetANN_HPIMPreBlocks
Formal statement
namespace DetANN.HPIM.PP
open PNormReg PNormRegLib SmaleNinth DetANN DetANN.HPIM Classical
variable {m N : ℕ} (Y : Fin N → EuclideanSpace ℝ (Fin m)) (δ : ℝ) (T0 : ℕ) (v0 : ℤ)
/-- **The node contract at every fuel.** -/
theorem node_spec (B : Blocks) (hB : B.WF) (ch : ChildOK B) (hm : 1 ≤ m)
(hY : Function.Injective Y) (hδ : 0 < δ) (hδ' : δ < 1 / 2) (KW KH KR WbI WbR : ℕ)
(bu : Budgets Y δ T0 B ch KW KH KR WbI WbR) :
∀ f, NodeOK Y δ T0 v0 B KW KH KR WbI WbR f := by sorry
end DetANN.HPIM.PPSource
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 the intermediate steps of the reduction of DetANN.HPIM.hpim_preprocessing, split so that each proof fits the verifier's time limit. The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.