Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Fixed codes with targets, Hamming distance to a code, and the code of a block-sparse linear system (Section 3, Appendix B.1)

Definition
LatticePrepro_Conversions_Codes

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

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

These definitions set up the code side of the conversion from block-sparse linear systems (Definition 3.10) to the nearest codeword problem with preprocessing (Lemma 3.11).

  1. Code families (CodeFamily F X). For a field FFF and a set of instances XXX: a finite coordinate set MMM, a linear code C⊆FM\mathcal C\subseteq F^MC⊆FM (an FFF-subspace, the same for every instance), and a target tx∈FMt_x\in F^Mtx​∈FM for each instance x∈Xx\in Xx∈X.
  2. Distance to a code (CodeFamily.codeDist, Definition 3.1). For y∈FMy\in F^My∈FM and a subspace C⊆FM\mathcal C\subseteq F^MC⊆FM,
Δ(y,C)=min⁡c∈CΔ(y,c),\Delta(y,\mathcal C)=\min_{c\in\mathcal C}\Delta(y,c),Δ(y,C)=c∈Cmin​Δ(y,c),

where Δ(y,c)\Delta(y,c)Δ(y,c) is the Hamming distance, the number of coordinates in which yyy and ccc differ. 3. Extension of scalars (CodeFamily.extend). For a prime ppp, a code family over Fp\mathbb F_pFp​ and a field FFF containing Fp\mathbb F_pFp​ (an Fp\mathbb F_pFp​-algebra): the code family over FFF with the same coordinates, the code span⁡FC⊆FM\operatorname{span}_F\mathcal C\subseteq F^MspanF​C⊆FM spanned by the codewords of C\mathcal CC read in FMF^MFM, and the same targets read in FMF^MFM. 4. The code of a linear system (LinearSystemFamily.code). Let LLL be a linear-system family over Fp\mathbb F_pFp​: a fixed linear map AAA on Fpι\mathbb F_p^{\iota}Fpι​ for a finite column set ι\iotaι, right-hand sides bxb_xbx​, and a partition of the columns into DDD blocks. Its code is

CL=ker⁡A×{0}={(u,u′)∈Fpι×Fpι: Au=0, u′=0},\mathcal C_L=\ker A\times\{0\}=\{(u,u')\in\mathbb F_p^{\iota}\times\mathbb F_p^{\iota}:\ Au=0,\ u'=0\},CL​=kerA×{0}={(u,u′)∈Fpι​×Fpι​: Au=0, u′=0},

with coordinate set ι⊔ι\iota\sqcup\iotaι⊔ι. 5. Its targets (LinearSystemFamily.codeTarget). yx=(v0,0)y_x=(v_0,0)yx​=(v0​,0) for a chosen solution v0v_0v0​ of Av=bxAv=b_xAv=bx​ if the system is solvable, and yx=(0,1)y_x=(0,\mathbf 1)yx​=(0,1) (all ones on the second copy) otherwise. 6. Its blocks (LinearSystemFamily.codeBlk). The coordinates ι⊔ι\iota\sqcup\iotaι⊔ι are partitioned into blocks indexed by two copies of the block set; each copy of ι\iotaι carries the block partition of the columns.

These are the code, targets and block structure of the proof of Lemma 3.11 (Appendix B.1): yx−CLy_x-\mathcal C_Lyx​−CL​ is the set of solutions of Av=bxAv=b_xAv=bx​ padded with zeros, which yields the gap (38), and extension of scalars carries the gap to any field of characteristic ppp. The same code and blocks are the starting point of the lattice reduction of Lemma 3.12.

Formalization Note. codeDist is a natural number, defined as the sInf of {Δ(y,c):c∈C}\{\Delta(y,c): c\in\mathcal C\}{Δ(y,c):c∈C}; this set is nonempty (0∈C0\in\mathcal C0∈C), so the infimum is attained and equals the paper's minimum. Codes are Submodule F (M → F), and the coordinate set MMM of a code family is a type with Fintype and DecidableEq instances. The solution v0v_0v0​ is picked by classical choice, so codeTarget is noncomputable. The paper's block length M=2nM=2nM=2n corresponds to the coordinate type ι ⊕ ι.

Definition code
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Reduction_LinearSystem

/-!
# From linear systems to codes (Lemma 3.11, Appendix B.1)

Given a linear system family `A · v = b_x` over `𝔽_p` with columns `ι`, we build a fixed code
`𝒞 = ker A × {0} ⊆ 𝔽_p^{ι ⊕ ι}` and targets `y_x`: a solution `(v_0, 0)` of the system when one
exists, and `(0, 1)` otherwise. Then `y_x - 𝒞` is the set of solutions (padded by zeros), so

* YES instances have a binary vector `e` with `y_x - e ∈ 𝒞`, at most one nonzero entry per block
  and weight `≤ D`;
* NO instances have `dist(y_x, 𝒞) > g · D`.

The code is then extended by scalars to any finite field `F ⊇ 𝔽_p`, which preserves distances
to targets over `𝔽_p`.
-/

namespace LatticePrepro

/-- A fixed linear code with a target for every instance. -/
structure CodeFamily (F : Type) [Field F] (X : Type) where
  /-- Coordinates. -/
  M : Type
  [fintypeM : Fintype M]
  [decEqM : DecidableEq M]
  /-- The code. -/
  code : Submodule F (M → F)
  /-- The target for instance `x`. -/
  target : X → (M → F)

namespace CodeFamily

variable {F : Type} [Field F] {X : Type}

attribute [instance] fintypeM decEqM

/-- Hamming distance from a word to a code (Definition 3.1). -/
noncomputable def codeDist [DecidableEq F] {M : Type} [Fintype M] (y : M → F)
    (C : Submodule F (M → F)) : ℕ :=
  sInf {d | ∃ c ∈ C, hammingDist y c = d}

end CodeFamily

section OfSystem

variable {p : ℕ} [Fact p.Prime] {X : Type} (L : LinearSystemFamily (ZMod p) X)

/-- The code `ker A × {0}` of Lemma 3.11. -/
def LinearSystemFamily.code : Submodule (ZMod p) (L.ι ⊕ L.ι → ZMod p) :=
  LinearMap.ker ((L.A.comp (LinearMap.funLeft (ZMod p) (ZMod p) Sum.inl)).prod
    (LinearMap.funLeft (ZMod p) (ZMod p) Sum.inr))

open Classical in
/-- The target `y_x` of Lemma 3.11. -/
noncomputable def LinearSystemFamily.codeTarget (x : X) : L.ι ⊕ L.ι → ZMod p :=
  if h : ∃ v, L.IsSolution x v then Sum.elim h.choose 0 else Sum.elim 0 1

/-- The block of a code coordinate. -/
def LinearSystemFamily.codeBlk : L.ι ⊕ L.ι → L.β ⊕ L.β := Sum.map L.blk L.blk

end OfSystem

section Extend

variable {p : ℕ} [Fact p.Prime] {X : Type} (F : Type) [Field F] [Algebra (ZMod p) F]

/-- The `F`-linear code spanned by a code over `𝔽_p`, with the targets mapped along
`algebraMap`. -/
noncomputable def CodeFamily.extend (C : CodeFamily (ZMod p) X) : CodeFamily F X where
  M := C.M
  code := Submodule.span F ((fun c : C.M → ZMod p => fun i => algebraMap (ZMod p) F (c i)) '' C.code)
  target := fun x i => algebraMap (ZMod p) F (C.target x i)

end Extend

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), Definition 3.1 (\label{def:code-lattice-distances}) and the proof of Lemma 3.11 (\label{lem:block-system-codes}) in Appendix B.1 (\label{subsec:affine-code-proof}); Lean: LatticePrepro/Conversions/Codes.lean, LatticePrepro.CodeFamily, LatticePrepro.CodeFamily.codeDist, LatticePrepro.CodeFamily.extend, LatticePrepro.LinearSystemFamily.code, LatticePrepro.LinearSystemFamily.codeTarget, LatticePrepro.LinearSystemFamily.codeBlk
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