Hadamard image of a block-sparse binary vector (proof of Lemma B.2, YES case)
ProvedLatticePrepro.blockHad_lift_boundLet be a prime, a finite set of block indices and , and consider vectors indexed by , cut into the blocks of size . Let be binary (every coordinate is or ) with at most one nonzero coordinate in each block. Let be its integer lift (a -vector) and the block Hadamard map, . Then
where is the number of nonzero coordinates of .
This is the YES-instance step in the proof of Lemma B.2 (Hadamard blocks): each nonzero block of is mapped to a column of the Hadamard matrix, with entries . In the lattice reduction of Lemma 3.12 for , applied with , it bounds the residual by at most nonzero entries of absolute value at most , so the target lies within -distance of the lattice (within for ).
Formalization Note. The lift is liftZMod, binarity is IsBinary, block sparsity is AtMostOnePerBlock Prod.fst (the blocks are the fibres of the first projection), and the weight is Mathlib's hammingNorm. Lean writes the prime as p.
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
open Finset
variable {p : ℕ} [Fact p.Prime] {β : Type*} [Fintype β] [DecidableEq β] {k : ℕ}theorem LatticePrepro.blockHad_lift_bound {e : β × Hadamard.Idx k → ZMod p} (hb : IsBinary e)
(h1 : AtMostOnePerBlock Prod.fst e) :
(∀ su, |Hadamard.blockHad k (liftZMod e) su| ≤ 1) ∧
(univ.filter fun su => Hadamard.blockHad k (liftZMod e) su ≠ 0).card ≤
hammingNorm e * 2 ^ k := by sorry