Lemma 3.11, eq. (38), NO instances — every codeword is far from the target
ProvedLatticePrepro.LinearSystemFamily.code_noLet be a prime and a linear-system family over : a fixed linear map on , right-hand sides , and a partition of the columns into blocks of size each. Let and be its code and targets (LinearSystemFamily.code, codeTarget). Let be a natural number with , and assume .
If is a NO instance with gap , meaning that every solution of has Hamming weight , then
where is the Hamming distance. Equivalently, .
This is the NO half of the gap (38) in the proof of Lemma 3.11 (Appendix B.1). Together with the YES half it gives a -gap NCPP instance with radius , and it is the source of the NO bounds in the lattice reduction of Lemma 3.12.
Formalization Note. The gap is in the paper and in Lean; the block size is L.blockSize and is L.numBlocks. The hypotheses and are explicit here; in the paper they are part of Definition 3.10 (, ). The paper states the conclusion as a bound on ; Lean states it for every codeword.
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Reduction_LinearSystem
import Definitions.Def_LatticePrepro_Conversions_Codes
open LatticePrepro
variable {p : ℕ} [Fact p.Prime] {X : Type} (L : LinearSystemFamily (ZMod p) X)theorem LatticePrepro.LinearSystemFamily.code_no {g : ℕ} (hg : g < L.blockSize) (hD : 0 < L.numBlocks) {x : X}
(hx : L.IsNo g x) :
∀ c ∈ L.code, g * L.numBlocks < hammingDist (L.codeTarget x) c := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.