Every real-RAM program has a literal bound
ProvedPNormRegLib.exists_litBoundmachine-modelprogram-verificationreal-ram
For every program of the real RAM PNormReg_Machine there is an integer such that
that is, has literal bound in the sense of the definition PNormRegLib_AddressBound.
Together with the address bound PNormRegLib.bounded_run, this lets one bound the addresses used by a program that is only known to exist.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_AddressBound
Formal statement
namespace PNormRegLib /-- Every program has an integer-literal bound `L ≥ 1`. -/ theorem exists_litBound (P : PNormReg.Program) : ∃ L : ℤ, 1 ≤ L ∧ LitBound P L := by sorry end PNormRegLib
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.