The first-order reduced row echelon form has a polynomial realizer
ProvedOPI.W6.IsPR.rrefC_prPolynomial realizers. For coded types , for means that is computed by a realizer (a program of the underlying stack-machine model) together with a monotone polynomial bounding both its running charge and the size of its output by . Sizes are encoding volumes; a natural number has volume (unary).
The function. Elements of , , are handled as lists of coordinates; a vector of length is a list of such lists. For a context ( the coefficient list of , a search budget) and a list of vectors, folds the insertion step over , starting from no rows. A state is a list of rows with pivot column . Inserting : reduce it to ; if it has a first nonzero column , scale it by the inverse of its -th entry (found by searching all coordinate lists, provided ), clear column from the old rows, and append the new row. Every field operation normalizes its output to exactly coordinates reduced modulo .
Statement. The map has a polynomial realizer.
This is how the generator computes, in polynomial time, the basis of the dual code (its pivots, dimension and the Schur products of its rows) from the input matrix.
import Definitions.Def_TwoFoldOPI_CL_Part05
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 OPI.FM OPI.RRefC
variable {α : Type} [Coding α]
theorem OPI.W6.IsPR.rrefC_pr : IsPR (fun x : RCtx × List (List (List ℕ)) =>
rrefC x.1.1 x.1.2.1 x.1.2.2.1 x.1.2.2.2.1 x.1.2.2.2.2 x.2) := by sorry