Theorem 4.8 (choice of parameters) and Theorem A.8 — tables exist for every verifier
ProvedLatticePrepro.QuadraticVerifier.Tables.nonemptycoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Let be a prime and let be a quadratic verifier over with instance length , assignment coordinates, evaluation tables and language . For a gap exponent put (momentAxes) and with = gapExp p δ. Tables for and consist of an integer with and an explicit moment representation in the sense of Theorem A.8 with axes and representation bound . They do not depend on the instance.
Statement. If and , then tables for and exist.
The base is the one chosen in the proof of Theorem 4.8 (the least with ), and the moment representation is the one of Theorem A.8 for the parameters , and .
Formalization Note. The conclusion is Nonempty (V.Tables δ). The hypothesis is the one of Theorem A.8; it holds for the 3SAT verifier.
Preamble
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Reduction_LinearSystem
import Definitions.Def_LatticePrepro_Conversions_Codes
import Definitions.Def_LatticePrepro_Conversions_Codes_Ext
import Definitions.Def_LatticePrepro_Conversions_ConstructionA
import Definitions.Def_LatticePrepro_Conversions_ConstructionA_Ext
import Definitions.Def_LatticePrepro_Conversions_Hadamard
import Definitions.Def_LatticePrepro_Conversions_Hadamard_Ext
import Definitions.Def_LatticePrepro_Conversions_Padding
import Definitions.Def_LatticePrepro_Conversions_Lattices
import Definitions.Def_LatticePrepro_Conversions_Lattices_Ext
import Definitions.Def_LatticePrepro_Lattices_Distance
import Definitions.Def_LatticePrepro_Moments_Basic
import Definitions.Def_LatticePrepro_Moments_Representation
import Definitions.Def_LatticePrepro_Verifier_Quadratic
import Definitions.Def_LatticePrepro_Reduction_FixedSystem
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
import Definitions.Def_LatticePrepro_Lattices_Mathlib
import Definitions.Def_LatticePrepro_Main
import Definitions.Def_LatticePrepro_Verifier_Gates
import Definitions.Def_LatticePrepro_Verifier_Circuit
import Definitions.Def_LatticePrepro_Verifier_Expr
import Definitions.Def_LatticePrepro_Verifier_ThreeSAT
import Definitions.Def_LatticePrepro_ThreeSAT
import Definitions.Def_LatticePrepro_ThreeSAT_Ext
import Definitions.Def_LatticePrepro_Explicit
open LatticePrepro
open LatticePrepro.QuadraticVerifier
variable {p : ℕ} [hp : Fact p.Prime]
open LatticePrepro.QuadraticVerifier.Tables
variable {V : QuadraticVerifier p} {δ : ℝ}Formal statement
theorem LatticePrepro.QuadraticVerifier.Tables.nonempty (V : QuadraticVerifier p) (hS : 2 ≤ V.S) {δ : ℝ} (hδ1 : δ < 1) :
Nonempty (V.Tables δ) := by sorrySource
G. Fenzi, G. Weissenberg, Nearly Optimal Hardness for CVP and NCP with Preprocessing (STOC 2027 submission #847; IACR ePrint 2026/2634, https://eprint.iacr.org/2026/2634), proof of Theorem 4.8 (\label{thm:quantitative-affine-gap}), choice of the base, and Theorem A.8 (\label{thm:moment-representation-construction}); Lean: LatticePrepro/Explicit.lean, LatticePrepro.QuadraticVerifier.Tables.nonempty