Lemma 3.12 for the paper's lattice — the reduction is realized by Construction A and its Walsh–Hadamard transform
ProvedLatticePrepro.LinearSystemFamily.exists_latticeReduction_eqLet be a linear-system family over with blocks of size , let be an integer, and let be a real norm exponent or , with . Let be the lattice of the paper for and : the Construction A lattice of the padded code if , and its blockwise Walsh–Hadamard transform otherwise, with its integer targets . Let be the radius for , for , and for , where is the padded block size.
Then and are the lattice and the radius of a lattice reduction in the sense of Lemma 3.12. That is, with the number of columns of and the dimension of :
- , , and for some integer ;
- for every YES instance there is with ;
- there is a residual weight with for all and all , and for every NO instance and all .
This is Lemma 3.12 with the lattice named. The existence form (exists_latticeReduction) asserts that some lattice reduction exists; this statement says which lattice and radius it uses.
Formalization Note. The conclusion is the existence of a LatticeReduction whose lattice family equals L.latticeFamily and whose radius equals L.latticeRadius. The statement holds for every real (the paper takes rational). Computability of the lattice basis, of the targets and of the residual weight is not formalized.
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.LinearSystemFamily
variable {p : ℕ} [Fact p.Prime] {X : Type} (L : LinearSystemFamily (ZMod p) X)theorem LatticePrepro.LinearSystemFamily.exists_latticeReduction_eq {g : ℕ} (hg : g < L.blockSize) (hD : 0 < L.numBlocks)
(pn : PNorm) :
∃ Red : LatticeReduction L g pn, Red.Λ = L.latticeFamily pn ∧ Red.R = L.latticeRadius pn := by sorry