Lemma 3.4 — Cost of the doubly projected contraction
ProvedVWZClique.two_projectionsFor two fixed subsets of product-basis labels with at most elements each, the entire contraction over factorized channels has arithmetic cost . The program receives the unary and pairwise tables.
import Definitions.Def_VWZClique_Contraction open VWZClique OAI.MatrixMultiplication.Arithmetic
theorem VWZClique.two_projections :
∀ (F : Type*) [Field F] [CharZero F] (δ : ℝ), 0 < δ → δ ≤ 1 →
∀ η : ℝ, 0 < η → ∃ C : ℝ, 0 < C ∧ ∀ (L : ℕ)
(Λ Γ : Finset (BasisLabel L)) (d e : BasisLabel L → F),
(Λ.card : ℝ) ≤ ((2 : ℝ)^L)^(2-δ) →
(Γ.card : ℝ) ≤ ((2 : ℝ)^L)^(2-δ) →
computesWithin (doubleProjection Λ Γ d e)
(C * ((2 : ℝ)^L)^(3 * omega F - (omega F - 1)*δ + η)) := by sorryRead-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6), independent blind auditor
For every characteristic-zero field , every real with and every real , there exists a real such that the assertion below holds for every natural number , every two finite sets of length- labels over and every two field-valued functions on all such labels. Put . If and , there exist a natural number , a straight-line program with registers, and one designated register among them such that, for every field-valued input table , the designated register equals
Here are independently summed over length- Boolean words, over ordered triples of words and over ordered word pairs. For put and . The rows on are , with entries mapped into . Put . For each , has independent input positions for each single slot and its word and for each ordered pair of slots and their two words, using two tagged copies of as the slots. places its two argument triples on those copies in order, then multiplies the six corresponding unary entries and all 36 corresponding binary entries, including the diagonal. The program may load arbitrary field constants and given inputs at zero cost, and may add, subtract or multiply previously computed registers at unit cost. Its total cost is at most . Here is the real infimum of the exponents for which, for every real , some gives, for every integer , a program of this same kind with designated outputs computing every entry of the product of every pair of matrices over from their entries at cost at most . The constant is uniform in ; the program and output register may depend on them, and the same program and output register work for all . Empty label sets are allowed and make the displayed scalar zero if either is empty. At , each word or label space is a singleton and each empty coordinate product is one.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.