Lemma 3.3 — Cost of the product-basis transform
ProvedVWZClique.basis_transformA single arithmetic program evaluates all product-basis inner products using operations on inputs.
import Definitions.Def_VWZClique_Operators import Definitions.Def_OAI_MatrixMultiplication_Arithmetic_omega open VWZClique OAI.MatrixMultiplication.Arithmetic
theorem VWZClique.basis_transform :
∃ C : ℕ, ∀ (F : Type*) [Field F] [CharZero F] (L : ℕ),
∃ (r : ℕ) (P : Program F (PairBits L) r) (out : BasisLabel L → Fin r),
P.cost ≤ C * (L + 1) * 4^L ∧ ∀ (w : PairBits L → F) j,
P.eval w (out j) = ∑ x, (basisEntry j x : F) * w x := by sorryRead-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6), independent blind auditor
There exists a natural number such that for every field of characteristic zero and every natural number there exist a natural number , a program with registers over , and a function assigning a register in to each length- label over . Let be the ordered pairs of length- bit strings. Starting with no registers, each step of adds a register containing a field constant, an input indexed by , or the sum, difference or product of two earlier register values. The newest register is indexed by , and previous register indices increase by one. Constants and input reads have cost zero, and each addition, subtraction or multiplication has cost one. The sum of these costs is at most . For every input assignment and every label , register has value
The product is taken over the rationals and mapped into . On the bit pairs in that order, with false written as , the value rows of are respectively , , and . The same and serve every at the specified and . At there is one input index and one label, the empty product is , and the selected register returns the single input. For every at least one label exists, so the output function requires at least one register.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.