Appendix A — uniform RAM implementation of the indexed polynomial construction
OpenITPIRPreproc.MatchVec.polynomial_indexed_computabilityUse Appendix A's least word length , prime-power exponents , degree cutoff , and explicit binomial-inversion coefficients. There exist injective row enumerations of distinct words in , bijective coordinate enumerations by of all with , absolute constants , and two deterministic word-RAM programs, uniform in .
For every , the first program receives and outputs the two polynomial matching vectors of row in the selected coordinate order within work . The second receives and outputs the full table in row order within work and working storage . Every coordinate is encoded in the existing three-bit encoding of .
This is the implementation part of Appendix A's final paragraph, isolated from its algebraic correctness and dimension analysis. The intended row enumeration is the first lexicographic words. The statement permits any injective row enumeration and bijective coordinate enumeration realized by the programs. It requires actual halting, outputs, and resource bounds in the mission's word-RAM model; mathematical computability alone does not suffice.
import Definitions.Def_ITPIRPreproc_MatchVec_PolynomialParameters open ITPIRPreproc.MatchVec ITPIRPreproc.MatchVec.PolynomialConstruction
theorem ITPIRPreproc.MatchVec.polynomial_indexed_computability :
∃ (dim : ℕ → ℕ)
(rows : ∀ h : ℕ, Fin (2^h) ↪ (Fin (wordLength h) → Fin (wordLength h)))
(coords : ∀ h : ℕ, Fin (dim h) ≃
Coordinate (wordLength h) (degree (exponent2 h) (exponent3 h)))
(C₀ : ℝ) (c₀ : ℕ) (vecProg tableProg : WordRAM.Program),
MVComputable dim
(fun h r j => leftVector (coefficient (wordLength h) (exponent2 h) (exponent3 h))
(rows h r) (coords h j))
(fun h r j => rightVector (rows h r) (coords h j))
C₀ c₀ vecProg tableProg := by sorry