Polynomial reduction modulo on coefficient lists has a polynomial realizer
ProvedOPI.W6.IsPR.reduceL_prPolynomials over are represented by lists of natural numbers, constant coefficient first. For a list (the coefficients of a monic ) and a list , one division step subtracts (coefficientwise modulo ) and drops the last entry. iterates this step times; for monic it returns the remainder of modulo as a list of coefficients.
means that has a polynomial realizer: a program of the underlying machine model whose running charge and output size are bounded by a monotone polynomial in the input size (natural numbers coded in unary, list sizes adding up).
Statement. The map has a polynomial realizer.
(The modulus is clamped to at least so that all intermediate coefficients stay reduced on every input; for this is the actual reduction.) Together with polynomial multiplication, this gives a polynomial realizer for multiplication in on coordinates, which the generator uses for all field computations (tables, row reduction).
import Definitions.Def_TwoFoldOPI_CL_Part03
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_GradientMethods
import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms
import Definitions.Def_QAlgorithms_Defs_OPIUniformity
import Definitions.Def_QAlgorithms_Defs_Fourier
import Definitions.Def_TwoFoldOPI_elemBits
import Definitions.Def_TwoFoldOPI_schurSquare
import Definitions.Def_TwoFoldOPI_schurFailureSum
import Definitions.Def_CodingTheory
import Definitions.Def_OAIThreeMachineSched01
import Definitions.Def_CookLevin_Cost
import Definitions.Def_TwoFoldOPI_codeOf
import Definitions.Def_TwoFoldOPI_solves
import Definitions.Def_TwoFoldOPI_Input
import Definitions.Def_TwoFoldOPI_CLSerializableF
open OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI.FM
variable {α : Type} [Coding α]
theorem OPI.W6.IsPR.reduceL_pr : IsPR (fun x : ℕ × List ℕ × List ℕ => reduceL (max x.1 2) x.2.1 x.2.2) := by sorry