Lemma 5.2 (lattices, NO instances) — every vector is rejected
ProvedLatticePrepro.LatticeReduction.not_accepts_of_isNoLet be a prime, a linear-system family over (fixed linear map , right-hand sides , blocks), , a norm exponent, and let Red be a lattice reduction for , and with lattice and residual weight . If is a NO instance of with gap , meaning that every solution of has Hamming weight greater than , then no integer vector is accepted:
This is the NO half of Lemma 5.2 (Testing search outputs) for lattices. Together with the YES half it shows that an approximate-CVPP search algorithm on these lattices, followed by the test, decides the underlying language; this is how the proof of Theorem 1.1 handles the search problem.
Formalization Note. The NO condition is L.IsNo g x, for the same gap as the reduction, and ranges over all of . No condition on an approximation factor is needed. The test is the predicate LatticeReduction.Accepts.
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
import Definitions.Def_LatticePrepro_Lattices_Distance
import Definitions.Def_LatticePrepro_Conversions_SearchTest
open LatticePrepro
open LatticePrepro.LatticeReduction
variable {p : ℕ} [Fact p.Prime] {X : Type} {L : LinearSystemFamily (ZMod p) X} {g : ℕ}
{pn : PNorm} (Red : LatticeReduction L g pn)theorem LatticePrepro.LatticeReduction.not_accepts_of_isNo {x : X} (hx : L.IsNo g x) (v : Red.Λ.M → ℤ) : ¬ Red.Accepts x v := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.