The blockwise Walsh–Hadamard transform as a linear map (Lemma B.2)
DefinitionLatticePrepro_Conversions_Hadamard_Extcoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Fix and a set of blocks. Coordinates are pairs of a block and a position , and is the Walsh–Hadamard matrix with entries .
The blockwise transform (Hadamard.blockHadₗ) is the -linear map on that applies inside every block:
It is the function Hadamard.blockHad as a linear map.
The bundle also contains the lemmas that make it one: (card_Idx), the displayed formula (blockHad_apply), additivity and homogeneity (blockHad_add, blockHad_smul).
This is the transform of Lemma B.2, which spreads a vector with one nonzero entry per block over its block; Lemma 3.12 applies it to the Construction A lattice when .
Definition code
import Mathlib
import Definitions.Def_LatticePrepro_Conversions_Hadamard
/-! Further definitions from `LatticePrepro/Conversions/Hadamard.lean`, continuing `Def_LatticePrepro_Conversions_Hadamard`. -/
namespace LatticePrepro
namespace Hadamard
variable (k : ℕ)
lemma card_Idx : Fintype.card (Idx k) = 2 ^ k := by
simp [ZMod.card]
section Block
variable {β : Type*}
lemma blockHad_apply (v : β × Idx k → ℤ) (su : β × Idx k) :
blockHad k v su = ∑ w, wh k su.2 w * v (su.1, w) := by
simp [blockHad, Matrix.mulVec, dotProduct, whMat]
lemma blockHad_add (v w : β × Idx k → ℤ) : blockHad k (v + w) = blockHad k v + blockHad k w := by
funext su; simp [blockHad_apply, mul_add, Finset.sum_add_distrib]
lemma blockHad_smul (c : ℤ) (v : β × Idx k → ℤ) : blockHad k (c • v) = c • blockHad k v := by
funext su; simp [blockHad_apply, Finset.mul_sum, mul_left_comm]
/-- The block Hadamard map as a `ℤ`-linear map. -/
def blockHadₗ : (β × Idx k → ℤ) →ₗ[ℤ] (β × Idx k → ℤ) where
toFun := blockHad k
map_add' := blockHad_add k
map_smul' := blockHad_smul k
@[simp] lemma blockHadₗ_apply (v : β × Idx k → ℤ) : blockHadₗ k v = blockHad k v := rfl
end Block
end Hadamard
end LatticePrepro
Source
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 B.2 (\label{lem:embeddings}) in Appendix B.2 (\label{subsec:conversion-proof}); Lean: LatticePrepro/Conversions/Hadamard.lean, LatticePrepro.Hadamard.blockHadₗ