The generator computes the pivot columns of the basis of
ProvedOPI.Gen.pivW_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 . The construction uses a basis of together with pivot columns such that . This basis consists of the reduced row echelon rows of if is false, and of the standard null-space basis (whose pivots are the free columns) if is true.
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 generator's pivot list, computed by a first-order Gaussian elimination.
Statement. If , then
as lists of natural numbers (the left side is ).
The pivots determine the repeat-until-success jobs that prepare the pivot registers, and the linear map from pivot coordinates to codewords of . This lemma is one of the equalities that identify the generated program with the intended one.
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.pivW_eq : pivW (basisOf x.gen x.H).piv = pivN (numsOf n (parsedOf x)) := by sorry