Lemma 3.11, eq. (38), YES instances — a binary block-sparse error vector of weight at most
ProvedLatticePrepro.LinearSystemFamily.code_yesLet be a prime and a linear-system family over with instance set : a fixed linear map on ( a finite set of columns), right-hand sides , and a partition of into blocks. Let be its code and its targets, and give the block partition with a copy of the column blocks on each half (LinearSystemFamily.code, codeTarget, codeBlk).
Let be a YES instance of the block-sparse linear-system problem: has a solution with at most one nonzero coordinate in each block. Then there is such that
and has at most one nonzero coordinate in each block of . Here is the Hamming weight, the number of nonzero coordinates.
This is the YES half of the gap (38) in the proof of Lemma 3.11 (Appendix B.1), together with the paper's remark that can be chosen with at most one nonzero entry per block. It shows , so the code reduction has radius ; the block sparsity of is what the Hadamard step of the lattice reduction (Lemma B.2, Lemma 3.12) needs.
Formalization Note. "Binary" is IsBinary (every coordinate is or in ), block sparsity is AtMostOnePerBlock L.codeBlk, the weight is Mathlib's hammingNorm, and is L.numBlocks, the number of block indices. YES instances are L.IsYes x.
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_yes {x : X} (hx : L.IsYes x) :
∃ e : L.ι ⊕ L.ι → ZMod p, IsBinary e ∧ AtMostOnePerBlock L.codeBlk e ∧
hammingNorm e ≤ L.numBlocks ∧ L.codeTarget x - e ∈ L.code := by sorry