Lemma 3.12 — fixed lattices from block-sparse linear systems
ProvedLatticePrepro.exists_latticeReductionLet be a prime and a linear-system family over with instance set : a fixed linear map on , right-hand sides (), and columns partitioned into blocks of size each. Let with , assume , and let be a norm exponent, a real number or , with ( for ). Then there exist
- a lattice (an additive subgroup), the same for every instance, with and for some integer , so that has full rank;
- an integer target for every instance ;
- an integer radius with , the same for every instance;
- a residual weight for every instance and every ,
such that:
- YES instances. If has a solution with at most one nonzero coordinate per block, then for some .
- Weight bound. For every instance and every ,
- NO instances. If every solution of has Hamming weight greater than , then for every .
Parts 2 and 3 give for all on NO instances, so for the instances are -gap CVPP instances; this is how the paper phrases Lemma 3.12. It is the lattice half of the conversions: composed with the moment reduction (Theorem 4.8) it gives Theorem 5.1 for lattices, and the residual weight is the quantity tested in Lemma 5.2.
Formalization Note. The conclusion is Nonempty (LatticeReduction L g pn), i.e. such data exists; the structure LatticeReduction packages the lattice family , , and with the properties above. The lattice is a -submodule of (Submodule ℤ (M → ℤ)), and full rank is encoded by . The norm exponent is a PNorm, so every real and are covered, whereas the paper states the lemma for rational (needed only for computability). The hypotheses (L.blockSize) and (L.numBlocks) correspond to and in Definition 3.10; Lean's gap is the paper's . The polynomial-time claims (integer basis, membership test, computing ) are not formalized, and is an arbitrary function.
Note (existence form). This statement asserts only that some lattice reduction exists. The statement for the object that the paper constructs is LatticePrepro.LinearSystemFamily.exists_latticeReduction_eq.
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_ConstructionA import Definitions.Def_LatticePrepro_Conversions_Hadamard import Definitions.Def_LatticePrepro_Conversions_Lattices open LatticePrepro
theorem LatticePrepro.exists_latticeReduction {p : ℕ} [Fact p.Prime] {X : Type}
(L : LinearSystemFamily (ZMod p) X) {g : ℕ} (hg : g < L.blockSize) (hD : 0 < L.numBlocks)
(pn : PNorm) : Nonempty (LatticeReduction L g pn) := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.