Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The code family of a block-sparse linear system over the prime field (Lemma 3.11)

Definition
LatticePrepro_Conversions_Codes_Ext

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

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

This bundle adds one definition to the code side of Lemma 3.11.

The code family of a linear system (LinearSystemFamily.toCodeFamily). 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 of size bbb. Its code family has coordinate set ι⊔ι\iota\sqcup\iotaι⊔ι, the code

CL=ker⁡A×{0}⊆Fpι⊔ι,\mathcal C_L=\ker A\times\{0\}\subseteq\mathbb F_p^{\iota\sqcup\iota},CL​=kerA×{0}⊆Fpι⊔ι​,

and the targets yx=(vx,0)y_x=(v_x,0)yx​=(vx​,0) for a solution vxv_xvx​ of Av=bxAv=b_xAv=bx​ if the system is solvable, and yx=(0,1)y_x=(0,\mathbf 1)yx​=(0,1) otherwise.

The bundle also contains the lemma that each of the 2D2D2D blocks of the coordinate set ι⊔ι\iota\sqcup\iotaι⊔ι has exactly bbb elements (card_codeBlk_fiber).

This packages the code LinearSystemFamily.code and the targets LinearSystemFamily.codeTarget of the proof of Lemma 3.11 (Appendix B.1) as a CodeFamily.

Formalization Note. The solution vxv_xvx​ is picked by classical choice, so the family is noncomputable; the distance from yxy_xyx​ to the code does not depend on the choice.

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

/-! Further definitions from `LatticePrepro/Conversions/Codes.lean`, continuing `Def_LatticePrepro_Conversions_Codes`. -/

namespace LatticePrepro

section OfSystem

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

/-- The code family of Lemma 3.11 over the prime field. -/
noncomputable def LinearSystemFamily.toCodeFamily : CodeFamily (ZMod p) X where
  M := L.ι ⊕ L.ι
  code := L.code
  target := L.codeTarget

lemma LinearSystemFamily.card_codeBlk_fiber (s : L.β ⊕ L.β) :
    (Finset.univ.filter fun i => L.codeBlk i = s).card = L.blockSize := by
  rcases s with t | t
  · rw [← L.card_fiber t, Finset.card_filter, Finset.card_filter, Fintype.sum_sum_type]
    simp only [LinearSystemFamily.codeBlk, Sum.map_inl, Sum.map_inr, Sum.inl.injEq, reduceCtorEq,
      ite_false, Finset.sum_const_zero, add_zero]
  · rw [← L.card_fiber t, Finset.card_filter, Finset.card_filter, Fintype.sum_sum_type]
    simp only [LinearSystemFamily.codeBlk, Sum.map_inl, Sum.map_inr, Sum.inr.injEq, reduceCtorEq,
      ite_false, Finset.sum_const_zero, zero_add]

end OfSystem

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), 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.LinearSystemFamily.toCodeFamily, LatticePrepro.LinearSystemFamily.card_codeBlk_fiber

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