Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The blockwise Walsh–Hadamard transform as a linear map (Lemma B.2)

Definition
LatticePrepro_Conversions_Hadamard_Ext

by WizardOfMenlo · Nov 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

Fix k≥0k\ge0k≥0 and a set β\betaβ of blocks. Coordinates are pairs (s,u)(s,u)(s,u) of a block s∈βs\in\betas∈β and a position u∈F2ku\in\mathbb F_2^{k}u∈F2k​, and HkH_kHk​ is the 2k×2k2^{k}\times2^{k}2k×2k Walsh–Hadamard matrix with entries (−1)⟨u,w⟩(-1)^{\langle u,w\rangle}(−1)⟨u,w⟩.

The blockwise transform (Hadamard.blockHadₗ) is the Z\mathbb ZZ-linear map on Zβ×F2k\mathbb Z^{\beta\times\mathbb F_2^{k}}Zβ×F2k​ that applies HkH_kHk​ inside every block:

(Hv)(s,u)=∑w∈F2k(−1)⟨u,w⟩ v(s,w).(Hv)_{(s,u)}=\sum_{w\in\mathbb F_2^{k}}(-1)^{\langle u,w\rangle}\,v_{(s,w)}.(Hv)(s,u)​=w∈F2k​∑​(−1)⟨u,w⟩v(s,w)​.

It is the function Hadamard.blockHad as a linear map.

The bundle also contains the lemmas that make it one: ∣F2k∣=2k|\mathbb F_2^{k}|=2^{k}∣F2k​∣=2k (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 p>2p>2p>2.

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ₗ

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me