The query layout preserves boundedness
ProvedDetANN.pbounded_queryStatemachine-modelnearest-neighbor-searchprogram-verificationreal-ram
Let be an integer, let be an -bounded state of the real RAM (definition PNormRegLib_AddressBound), and let . Then the query start state of DetANN.queryState on for is
The query layout resets all pointers to and keeps the integer memory, so the bound reached at the end of preprocessing carries over to the start of every query.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_AddressBound import Definitions.Def_DetANN_DataStructure
Formal statement
namespace DetANN
/-- The query layout on a `PBounded X` state (with `X ≥ 0`) is `PBounded X`: pointers are reset to
`0` and the integer memory is kept. -/
theorem pbounded_queryState (X : ℤ) (s : PNormReg.State) (hs : PNormRegLib.PBounded X s)
(hX : 0 ≤ X) (m : ℕ) (q : EuclideanSpace ℝ (Fin m)) :
PNormRegLib.PBounded X (queryState m s q) := by sorry
end DetANN
Source
Original library result for the PNormReg machine (definition PNormReg_Machine: Adil, Bullins, O'Carroll, Sidford, Solving p-norm regression in matrix multiplication time, STOC 2027 submission), written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' at the captain's invitation (mission discussion, 2026-11-14). No external source is claimed; the doubling argument is the standard one for machines whose only integer arithmetic is addition and subtraction.