Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

ℓp\ell_pℓp​ norms, fixed lattices with integer targets, and the lattice reduction structure (Section 3, Lemma 3.12)

Definition
LatticePrepro_Conversions_Lattices

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

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

These definitions fix the lattice-side notions and package the output of the lattice reduction (Lemma 3.12).

  1. Norm exponents (PNorm): either a real number p≥1p\ge1p≥1 or p=∞p=\inftyp=∞.
  2. ℓp\ell_pℓp​ norms (PNorm.norm): for v∈RMv\in\mathbb R^Mv∈RM, ∥v∥p=(∑i∣vi∣p)1/p\|v\|_p=\bigl(\sum_i|v_i|^p\bigr)^{1/p}∥v∥p​=(∑i​∣vi​∣p)1/p for finite ppp, and ∥v∥∞=sup⁡i∣vi∣\|v\|_\infty=\sup_i|v_i|∥v∥∞​=supi​∣vi​∣.
  3. The exponent sss (PNorm.s): s=min⁡{p,2}s=\min\{p,2\}s=min{p,2}, with s=2s=2s=2 for p=∞p=\inftyp=∞.
  4. Lattice families (LatticeFamily X): a finite coordinate set MMM, a lattice Λ⊆ZM\Lambda\subseteq\mathbb Z^MΛ⊆ZM given as an additive subgroup (Z\mathbb ZZ-submodule) of ZM\mathbb Z^MZM that is the same for every instance, and an integer target tx∈ZMt_x\in\mathbb Z^Mtx​∈ZM for every instance x∈Xx\in Xx∈X.
  5. Distances to integer vectors (LatticeFamily.toReal, LatticeFamily.dist): integer vectors are read in RM\mathbb R^MRM, and the distance from the target of xxx to v∈ZMv\in\mathbb Z^Mv∈ZM is ∥tx−v∥p\|t_x-v\|_p∥tx​−v∥p​.
  6. Lattice reductions (LatticeReduction L g pn). For a prime p\mathsf pp, a linear-system family LLL over Fp\mathbb F_{\mathsf p}Fp​ with nnn columns in DDD blocks, a gap g∈Ng\in\mathbb Ng∈N and a norm exponent ppp: a lattice family (Λ,(tx))(\Lambda,(t_x))(Λ,(tx​)) on MMM coordinates, a radius R∈NR\in\mathbb NR∈N, a natural number NNN, and a residual weight w(x,v)∈Nw(x,v)\in\mathbb Nw(x,v)∈N for each instance xxx and each v∈ZMv\in\mathbb Z^Mv∈ZM, such that
    • 1≤R≤M1\le R\le M1≤R≤M and 2n≤M<4n2n\le M<4n2n≤M<4n;
    • N>0N>0N>0 and N⋅ZM⊆ΛN\cdot\mathbb Z^M\subseteq\LambdaN⋅ZM⊆Λ (so Λ\LambdaΛ has full rank);
    • for every YES instance xxx of LLL, some v∈Λv\in\Lambdav∈Λ has ∥tx−v∥p≤R\|t_x-v\|_p\le R∥tx​−v∥p​≤R;
    • for every instance xxx and every v∈Λv\in\Lambdav∈Λ, w(x,v)≤16⋅D⋅(∥tx−v∥p/R)sw(x,v)\le16\cdot D\cdot\bigl(\|t_x-v\|_p/R\bigr)^{s}w(x,v)≤16⋅D⋅(∥tx​−v∥p​/R)s;
    • for every NO instance xxx with gap ggg and every v∈Λv\in\Lambdav∈Λ, w(x,v)>g⋅Dw(x,v)>g\cdot Dw(x,v)>g⋅D.

The lattice and the radius depend only on LLL; only the targets depend on the instance, as in a preprocessing reduction. The residual weight is the quantity checked by the search test of Lemma 5.2.

Formalization Note. PNorm covers every real p≥1p\ge1p≥1 and p=∞p=\inftyp=∞; the paper states Lemma 3.12 for rational ppp and p=∞p=\inftyp=∞, which matters only for computability. The sup norm is ⨆ i, |v i|, and powers with real exponents are Real.rpow. The polynomial-time computability of the basis, targets, membership test and residual weight is not formalized: weight is an arbitrary function. Full rank is encoded by N⋅ZM⊆ΛN\cdot\mathbb Z^M\subseteq\LambdaN⋅ZM⊆Λ; Lattices/Mathlib.lean shows that this makes the real image of Λ\LambdaΛ a Mathlib IsZLattice. Lean writes the prime as p and the norm exponent as pn.

Definition code
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

/-!
# From codes to lattices (Lemma 3.12, Appendix B.2–B.3)

* `ℓ_p` norms on `M → ℝ` for `1 ≤ p < ∞` and `p = ∞` (`PNorm`).
* Construction A: `Λ_𝒞 = {v ∈ ℤ^M : v mod p ∈ 𝒞}` (Lemma B.1).
* The block Hadamard map (Lemma B.2): for `2 ≤ p ≤ ∞`, multiply lattice and target by a
  block-diagonal matrix of Sylvester–Hadamard matrices.
* The lattice reduction (Lemma 3.12, `LatticeReduction`, `exists_latticeReduction`): a fixed
  lattice `Λ`, an integer radius `R`, targets `t_x` and a residual weight such that YES instances
  have a lattice vector within distance `R` and NO instances have every lattice vector at distance
  more than `(g / 16)^{1/s} · R`, where `s = min {p, 2}`.
-/

namespace LatticePrepro

/-- A norm exponent: a real `p ≥ 1`, or `∞`. -/
inductive PNorm
  | fin (p : ℝ) (hp : 1 ≤ p)
  | inf

namespace PNorm

/-- The `ℓ_p` norm of a real vector. -/
noncomputable def norm {M : Type} [Fintype M] : PNorm → (M → ℝ) → ℝ
  | fin p _ => fun v => (∑ i, |v i| ^ p) ^ (1 / p)
  | inf => fun v => ⨆ i, |v i|

/-- The exponent `s = min {p, 2}` (`s = 2` for `p = ∞`). -/
noncomputable def s : PNorm → ℝ
  | fin p _ => min p 2
  | inf => 2

end PNorm

/-- A fixed lattice `Λ ⊆ ℤ^M` with an integer target for every instance. -/
structure LatticeFamily (X : Type) where
  /-- Coordinates. -/
  M : Type
  [fintypeM : Fintype M]
  [decEqM : DecidableEq M]
  /-- The lattice, as a `ℤ`-submodule of `ℤ^M`. -/
  lattice : Submodule ℤ (M → ℤ)
  /-- The target for instance `x`. -/
  target : X → (M → ℤ)

namespace LatticeFamily

attribute [instance] fintypeM decEqM

variable {X : Type} (Λ : LatticeFamily X)

/-- The real vector of an integer vector. -/
def toReal {M : Type} (v : M → ℤ) : M → ℝ := fun i => (v i : ℝ)

/-- Distance in `ℓ_p` from the target to a lattice vector. -/
noncomputable def dist (pn : PNorm) (x : X) (v : Λ.M → ℤ) : ℝ :=
  pn.norm (toReal (Λ.target x - v))

end LatticeFamily

/-! ### Padding the code to blocks of size a power of two -/

/-! ### Block-sparse binary vectors under the Hadamard map -/

/-! ### Real-number bounds for the radius -/

/-! ### The lattice reduction: statement -/

/-- The output of Lemma 3.12 for a linear system family `L`, a gap `g` and a norm exponent `pn`:
a fixed lattice `Λ ⊆ ℤ^M` with `2 n ≤ M < 4 n` (`n = |ι|`), containing `N · ℤ^M` for some
`N > 0` (full rank), an integer radius `1 ≤ R ≤ M`, and a *residual weight* `w = weight x v`
computable from a lattice vector `v`, such that

* YES instances have a lattice vector within `ℓ_p`-distance `R` of the target;
* `w ≤ 16 · D · (dist / R)^s` for every lattice vector, and `w > g · D` on NO instances.

The residual weight is the quantity tested in Lemma 5.2 (`Conversions/SearchTest.lean`). -/
structure LatticeReduction {p : ℕ} [Fact p.Prime] {X : Type} (L : LinearSystemFamily (ZMod p) X)
    (g : ℕ) (pn : PNorm) where
  /-- The fixed lattice and the targets. -/
  Λ : LatticeFamily X
  /-- The radius. -/
  R : ℕ
  one_le_R : 1 ≤ R
  R_le_card : R ≤ Fintype.card Λ.M
  two_mul_card_le : 2 * Fintype.card L.ι ≤ Fintype.card Λ.M
  card_lt_four_mul : Fintype.card Λ.M < 4 * Fintype.card L.ι
  /-- The lattice contains `N · ℤ^M`. -/
  N : ℕ
  N_pos : 0 < N
  smul_mem : ∀ v : Λ.M → ℤ, (N : ℤ) • v ∈ Λ.lattice
  /-- The residual weight of a lattice vector. -/
  weight : X → (Λ.M → ℤ) → ℕ
  yes : ∀ x, L.IsYes x → ∃ v ∈ Λ.lattice, Λ.dist pn x v ≤ R
  weight_le : ∀ x, ∀ v ∈ Λ.lattice,
    (weight x v : ℝ) ≤ 16 * L.numBlocks * (Λ.dist pn x v / R) ^ pn.s
  lt_weight : ∀ x, L.IsNo g x → ∀ v ∈ Λ.lattice, g * L.numBlocks < weight x v

/-! ### The three cases of the lattice reduction -/

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), Section 3 (Preliminaries, \label{sec:preliminaries}) and Lemma 3.12 (\label{lem:block-system-lattices}); Lean: LatticePrepro/Conversions/Lattices.lean, LatticePrepro.PNorm, LatticePrepro.PNorm.norm, LatticePrepro.PNorm.s, LatticePrepro.LatticeFamily, LatticePrepro.LatticeFamily.toReal, LatticePrepro.LatticeFamily.dist, LatticePrepro.LatticeReduction
Human review
  • Endorsed by Shuze Chen · Nov 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by WizardOfMenlo · Nov 15, 2026

    Confirmed by the mission captain (proposal self-audit).

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