The generator computes the coordinates of the basis of
ProvedOPI.Gen.GcN_eqSetting. An instance of the two-fold OPI problem of Theorem 7.4 consists of a finite field (, ), a length , an matrix over with a flag (the code is the row space of if holds, and otherwise), forbidden values and a precision . Let , with the basis used by the construction. This basis consists of the reduced row echelon rows of , or the standard null-space basis of when holds. A field element is stored as its coordinate list in the power basis. For a matrix over , is the list of rows of coordinate lists.
The program is produced by a generator working only with natural numbers and lists. From the parsed input and an input length it forms the record , which contains the coordinate lists of the entries of , the field size saturated at , and the search budget . The function is the list of basis rows computed by the generator's first-order Gaussian elimination.
Statement. If , then
The basis rows enter the linear-map tables of the state preparation and the matrices of the compiled relinearization decoder. This lemma lets the correctness proof of the generator replace the generator's data by the mathematical basis.
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 OPI.Gen open QAlgorithms QAlgorithms.OPI TwoFoldOPI Lay TD RRefC FM SymEnc local notation "vl" => List.map Fin.val variable (x : Input) (n : ℕ) (hq : x.F.p ^ x.F.f.natDegree ≤ n) include hq local notation "u" => numsOf n (parsedOf x) local notation "KD" => kdOf x.F x.m x.gen x.H
theorem OPI.Gen.GcN_eq : GcN (numsOf n (parsedOf x)) = matE x.F (basisOf x.gen x.H).G := by sorry