Cells written by a real-RAM run lie in a window
ProvedDetANN.cellsWritten_boundmachine-modelnearest-neighbor-searchprogram-verificationreal-ram
Let be a program of the real RAM PNormReg_Machine, let be an integer, and let be an -bounded state (definition PNormRegLib_AddressBound) such that is also a literal bound for . Write for the state after steps of from on the all-false tape DetANN.detTape. Then for every , every memory cell (real or integer) stored to during the first steps, as counted by DetANN.cellsWritten, has an address with
The data-structure specification DetANN.IsDetANNStructure bounds how many cells preprocessing writes but not where they are. This result locates them, so that several data structures can be placed in disjoint regions of memory.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_AddressBound import Definitions.Def_DetANN_DataStructure
Formal statement
namespace DetANN
/-- **Written cells lie in a window.** Under the hypotheses of `PNormRegLib.bounded_run`, every cell
stored to during the first `t` steps of `P` from `s` has address of absolute value at most
`X · 2^t`. -/
theorem cellsWritten_bound (P : PNormReg.Program) (X : ℤ) (s : PNormReg.State)
(hs : PNormRegLib.PBounded X s) (hlit : PNormRegLib.LitBound P X) (hX : 1 ≤ X) (t : ℕ) :
∀ c ∈ cellsWritten P s t, |c.2| ≤ X * 2 ^ t := 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.