Walsh–Hadamard matrices and the block Hadamard map (Lemma B.2)
DefinitionLatticePrepro_Conversions_Hadamardcoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
These definitions give the Hadamard matrices used for norm exponents . Blocks have size and are indexed by .
- Signs (
sgn): , , i.e. and . - Block index set (
Idx k): , the functions ; it has elements. - Inner product (
ip k): for . - Entries (
wh k): . - The Walsh–Hadamard matrix (
whMat k): the integer matrix . - The block Hadamard map (
blockHad k): for a set of blocks and an integer vector indexed by ,
that is, applied separately to each block .
is the block-diagonal Sylvester–Hadamard matrix of Lemma B.2 (Hadamard blocks). In the lattice reduction of Lemma 3.12 for , the lattice and the targets are multiplied by after the blocks have been padded to a power-of-two size.
Formalization Note. Indexing rows and columns by instead of identifies with Sylvester's matrix through the binary expansions of the indices. The bundle also contains the simp lemma sgn_zero (). The source module proves the properties used later (symmetry, , Parseval's identity for ).
Definition code
import Mathlib
/-!
# Walsh–Hadamard matrices and the block Hadamard map (Lemma B.2)
The Walsh–Hadamard matrix of order `2^k` is indexed by `Idx k = Fin k → ZMod 2`, with entries
`wh u w = (-1)^{⟨u, w⟩}`. It is symmetric with `H * H = 2^k • 1`. The block Hadamard map
`blockHad` applies `H` to every block of a vector indexed by `β × Idx k`; it is `ℤ`-linear,
satisfies `blockHad (blockHad v) = 2^k • v` and Parseval's identity
`∑ (blockHad v)² = 2^k ∑ v²`, and has entries bounded by the `ℓ_1` norm of the block.
-/
namespace LatticePrepro
namespace Hadamard
/-- The sign character `ZMod 2 → ℤ`, `0 ↦ 1`, `1 ↦ -1`. -/
def sgn (a : ZMod 2) : ℤ := if a = 0 then 1 else -1
@[simp] lemma sgn_zero : sgn 0 = 1 := rfl
variable (k : ℕ)
/-- The index set of a Hadamard block of size `2^k`. -/
abbrev Idx : Type := Fin k → ZMod 2
/-- The inner product `⟨u, w⟩ = ∑ u_i w_i` over `ZMod 2`. -/
def ip (u w : Idx k) : ZMod 2 := ∑ i, u i * w i
/-- Entries `(-1)^{⟨u, w⟩}` of the Walsh–Hadamard matrix. -/
def wh (u w : Idx k) : ℤ := sgn (ip k u w)
/-- The Walsh–Hadamard matrix. -/
def whMat : Matrix (Idx k) (Idx k) ℤ := Matrix.of fun u w => wh k u w
section Block
variable {β : Type*}
/-- The block Hadamard map: apply the Walsh–Hadamard matrix to every block. -/
def blockHad (v : β × Idx k → ℤ) : β × Idx k → ℤ :=
fun su => (whMat k).mulVec (fun w => v (su.1, w)) su.2
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}); Lean: LatticePrepro/Conversions/Hadamard.lean, LatticePrepro.Hadamard.sgn, LatticePrepro.Hadamard.Idx, LatticePrepro.Hadamard.ip, LatticePrepro.Hadamard.wh, LatticePrepro.Hadamard.whMat, LatticePrepro.Hadamard.blockHad