The inverse trace-dual re-encoding equals an explicit search over coordinate vectors
ProvedOPI.FM.RLinv_eqLet with , let , and let a symbol occupy bits. A field element has two bit encodings, both made of blocks of bits:
- , whose blocks are the power-basis coordinates of (coefficients of );
- , whose blocks are the trace-dual coordinates , .
The map is defined using a choice function. If the bit list has length and equals for some , it returns ; otherwise it returns . The argument is ignored.
The explicit function , where is the coefficient list of , does the following. If and every -bit block of has value , it reads the blocks as numbers, scans all vectors in a fixed order, takes the first whose list of traces (computed with list arithmetic modulo ) equals those numbers, and outputs encoded in -bit blocks. Otherwise it returns .
Statement. For all bit lists ,
The gadget re-encodes symbols between the two encodings. This lemma replaces the choice-based inverse re-encoding by a function computed from alone, as needed to show that the circuits can be generated uniformly.
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 OPI.FM open TwoFoldOPI QAlgorithms open scoped Classical variable (F : AvgCaseTI.FieldPres)
theorem OPI.FM.RLinv_eq (c y : List Bool) : Fq.RLinv F c y = RLinvL F.p F.f.natDegree (Fq.w F) (flOf F) y := by sorry