The preprocessing input layout is bounded
ProvedDetANN.pbounded_inputStatemachine-modelnearest-neighbor-searchprogram-verificationreal-ram
Let , let and . The preprocessing input state of DetANN.inputState (integer cells hold ; real memory holds and the points) is
in the sense of the definition PNormRegLib_AddressBound.
This is the starting bound needed to apply the address bound PNormRegLib.bounded_run to preprocessing.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_AddressBound import Definitions.Def_DetANN_DataStructure
Formal statement
namespace DetANN
/-- The preprocessing input layout of `N` points in `ℝ^m` is `PBounded (N + m + 1)`. -/
theorem pbounded_inputState {N m : ℕ} (Y : Fin N → EuclideanSpace ℝ (Fin m)) (θ : ℝ) :
PNormRegLib.PBounded ((N : ℤ) + m + 1) (inputState Y θ) := 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.