Theorem A.8 — explicit moment representations
ProvedLatticePrepro.exists_explicit_momentRepresentationLet be a prime and let be integers with , and . Then there exists an explicit moment representation with these parameters. That is, there are
- a field of characteristic (an -algebra),
- elements that are linearly independent over (together with ),
- a natural number with
- and a moment representation over (Definition 4.4) with moment parameter and blocks of size : evaluation tables on a finite coordinate set partitioned into the blocks, an -linear constraint map , and -linear moment maps ,
such that the following hold.
- Completeness. For every there is a binary table with exactly one nonzero coordinate in each block, , and for .
- Soundness. For every with and , there is a finitely supported coefficient function on an algebraic closure of such that
Here is the number of nonzero coordinates of .
The paper proves these properties for the concrete output of Construction A.4: of degree (the least power of that is at least ) over a sample field of size (the least power of that is at least ), the encoding tuple , and the polynomial evaluation tables. Theorem 4.8 uses this representation to instantiate the fixed-verifier reduction (Construction 4.5, Theorem 4.6) with the stated size bounds.
Formalization Note: The statement is Nonempty (ExplicitMomentRepresentation p S m B), a structure bundling the field, the encoding tuple (indexed by Fin (S + 1) with ), the moment representation and with the equations above. It is an existence statement: the concrete construction, the finiteness of and the construction-time part (item 3 of Theorem A.8) are not part of it. Coefficient functions have type AlgebraicClosure K →₀ ZMod p, so all represented functions live on one fixed extension rather than on a finite extension depending on . The constraint matrix is an -linear map, and moment orders are indexed by Fin (2r - 1). The paper writes for .
import Mathlib import Definitions.Def_LatticePrepro_Basic_Blocks import Definitions.Def_LatticePrepro_Moments_Basic import Definitions.Def_LatticePrepro_Moments_Representation import Definitions.Def_LatticePrepro_Verifier_Quadratic import Definitions.Def_LatticePrepro_Tables_Digits import Definitions.Def_LatticePrepro_Tables_FieldSetup import Definitions.Def_LatticePrepro_Tables_Hankel import Definitions.Def_LatticePrepro_Tables_Construction import Definitions.Def_LatticePrepro_Tables_ElementTable import Definitions.Def_LatticePrepro_Tables_TableSoundness import Definitions.Def_LatticePrepro_Tables_Explicit open LatticePrepro open Polynomial open ExplicitTables
theorem LatticePrepro.exists_explicit_momentRepresentation (p : ℕ) [Fact p.Prime] (S m B : ℕ)
(hS : 2 ≤ S) (hm : 1 ≤ m) (hB : 2 ≤ B) : Nonempty (ExplicitMomentRepresentation p S m B) := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.