Lemma 5.2 (codes, NO instances) — every vector is rejected
ProvedLatticePrepro.CodeFamily.not_accepts_of_ltcoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Let be a field and a code family over with coordinate set . Let and let be an instance with
Then no vector is accepted by the test with threshold : it is not the case that and . Here is the Hamming distance and .
This is the NO half of Lemma 5.2 (Testing search outputs) for codes. In Theorem 5.1 for codes it is applied with and the gap , using on NO instances (Lemma 3.11): whatever a search algorithm returns on a NO instance, the test rejects it.
Formalization Note. The NO condition is given directly as the bound on , a natural number (codeDist), and ranges over all of , not only over codewords. The test is the predicate CodeFamily.Accepts g R x c.
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_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.CodeFamily
variable {F : Type} [Field F] [DecidableEq F] {X : Type} (C : CodeFamily F X)Formal statement
theorem LatticePrepro.CodeFamily.not_accepts_of_lt {g R : ℕ} {x : X} (hx : g * R < codeDist (C.target x) C.code)
(c : C.M → F) : ¬ C.Accepts g R x c := 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), Lemma 5.2 (\label{lem:search-test}), codes, NO instances; Lean: LatticePrepro/Conversions/SearchTest.lean, LatticePrepro.CodeFamily.not_accepts_of_lt
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.