Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Linear systems with a fixed matrix and the block-sparse linear-system problem (Definition 3.10)

Definition
LatticePrepro_Reduction_LinearSystem

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

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

Fix a field FFF and a set XXX of instances.

  1. LinearSystemFamily F X. A family of linear systems Av=bxAv=b_xAv=bx​ (x∈Xx\in Xx∈X) with a fixed matrix. It consists of:

    • a finite set ι\iotaι of columns and a finite set β\betaβ of blocks;
    • a block map blk:ι→β\mathrm{blk}:\iota\to\betablk:ι→β such that every block contains exactly bbb columns, where bbb is the block size;
    • an FFF-vector space WWW of rows and an FFF-linear map A:Fι→WA:F^\iota\to WA:Fι→W, the fixed matrix;
    • a right-hand side bx∈Wb_x\in Wbx​∈W for every instance xxx.

    The number of blocks is D=∣β∣D=|\beta|D=∣β∣ (numBlocks).

  2. Solutions (IsSolution x v): v∈Fιv\in F^\iotav∈Fι with Av=bxAv=b_xAv=bx​.

  3. YES instances (IsYes x): some solution vvv is binary (vi∈{0,1}v_i\in\{0,1\}vi​∈{0,1} for all iii) and has at most one nonzero coordinate in each block.

  4. NO instances with gap ggg (IsNo g x): every solution vvv has Hamming weight wt⁡(v)>g⋅D\operatorname{wt}(v)>g\cdot Dwt(v)>g⋅D.

  5. Gap reductions (IsGapReduction Lang g), for a language Lang⊆X\mathrm{Lang}\subseteq XLang⊆X: every x∈Langx\in\mathrm{Lang}x∈Lang is a YES instance and every x∉Langx\notin\mathrm{Lang}x∈/Lang is a NO instance with gap ggg, that is,

x∈Lang⇒∃ v∈{0,1}ι: Av=bx, at most one nonzero per block;x∉Lang⇒∀v (Av=bx⇒wt⁡(v)>g⋅D).x\in\mathrm{Lang}\Rightarrow\exists\,v\in\{0,1\}^\iota:\ Av=b_x,\ \text{at most one nonzero per block};\qquad x\notin\mathrm{Lang}\Rightarrow\forall v\,\bigl(Av=b_x\Rightarrow\operatorname{wt}(v)>g\cdot D\bigr).x∈Lang⇒∃v∈{0,1}ι: Av=bx​, at most one nonzero per block;x∈/Lang⇒∀v(Av=bx​⇒wt(v)>g⋅D).

This formalizes the block-sparse linear-system problem with preprocessing, (D,b,g)(D,b,g)(D,b,g)-BSLSP (Definition 3.10). The matrix AAA and its block partition are the fixed input and bxb_xbx​ is the online input. IsGapReduction says that x↦bxx\mapsto b_xx↦bx​ maps the language to YES instances and its complement to NO instances. It is the conclusion of Theorems 4.6 and 4.8 and the input of the code and lattice conversions (Lemmas 3.11 and 3.12).

Formalization Note The matrix is an abstract FFF-linear map into an arbitrary FFF-module WWW rather than an h×nh\times nh×n matrix, and FFF is any field (the paper uses Fp\mathbb{F}_pFp​). The parameter conditions D,b,g≥1D,b,g\ge1D,b,g≥1 and b>gb>gb>g of Definition 3.10 are not part of these definitions; where needed they are stated separately (for example in GapReduction). Computability of the reduction is not modelled. The Fintype and DecidableEq instances are fields of the structure.

Definition code
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks

/-!
# Linear systems with a fixed matrix

A *linear system family* with a fixed matrix (cf. Section 3 of the paper) is a linear map
`A : (ι → F) →ₗ[F] W` together with a right-hand side `rhs x : W` for every instance `x`.
The columns `ι` are partitioned into blocks by `blk : ι → β`. The matrix `A` does not depend
on `x`; only `rhs x` does.

The *block-sparse linear-system problem with preprocessing* (Definition 3.10) asks to distinguish

* YES: `A v = rhs x` has a binary solution with at most one nonzero coordinate per block, from
* NO: every solution `v` of `A v = rhs x` has Hamming weight `> g · D`,

where `D = |β|` is the number of blocks and `g` the gap.
-/

namespace LatticePrepro

/-- A family of linear systems `A v = rhs x` with a fixed matrix and block-partitioned columns. -/
structure LinearSystemFamily (F : Type) [Field F] (X : Type) where
  /-- Column indices. -/
  ι : Type
  [fintypeι : Fintype ι]
  [decEqι : DecidableEq ι]
  /-- Block indices. -/
  β : Type
  [fintypeβ : Fintype β]
  [decEqβ : DecidableEq β]
  /-- The block partition of the columns. -/
  blk : ι → β
  /-- The block size. -/
  blockSize : ℕ
  card_fiber : ∀ s : β, (Finset.univ.filter fun i => blk i = s).card = blockSize
  /-- Codomain (rows). -/
  W : Type
  [addCommGroupW : AddCommGroup W]
  [moduleW : Module F W]
  /-- The fixed matrix. -/
  A : (ι → F) →ₗ[F] W
  /-- The right-hand side for instance `x`. -/
  rhs : X → W

namespace LinearSystemFamily

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

attribute [instance] fintypeι decEqι fintypeβ decEqβ addCommGroupW moduleW

variable (L : LinearSystemFamily F X)

/-- The number of blocks `D`. -/
abbrev numBlocks : ℕ := Fintype.card L.β

/-- Solutions of the system for instance `x`. -/
def IsSolution (x : X) (v : L.ι → F) : Prop := L.A v = L.rhs x

/-- YES instances of BSLSP: a binary block-sparse solution exists. -/
def IsYes [DecidableEq F] (x : X) : Prop :=
  ∃ v : L.ι → F, L.IsSolution x v ∧ IsBinary v ∧ AtMostOnePerBlock L.blk v

/-- NO instances of BSLSP with gap `g`: every solution has weight more than `g · D`. -/
def IsNo [DecidableEq F] (g : ℕ) (x : X) : Prop :=
  ∀ v : L.ι → F, L.IsSolution x v → g * L.numBlocks < hammingNorm v

/-- A reduction with gap `g` from a language `Lang` to the BSLSP promise problem. -/
def IsGapReduction [DecidableEq F] (Lang : Set X) (g : ℕ) : Prop :=
  (∀ x ∈ Lang, L.IsYes x) ∧ (∀ x ∉ Lang, L.IsNo g x)

end LinearSystemFamily

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.10 (\label{def:block-sparse-linear-system}); Lean: LatticePrepro/Reduction/LinearSystem.lean, LatticePrepro.LinearSystemFamily, LatticePrepro.LinearSystemFamily.numBlocks, LatticePrepro.LinearSystemFamily.IsSolution, LatticePrepro.LinearSystemFamily.IsYes, LatticePrepro.LinearSystemFamily.IsNo, LatticePrepro.LinearSystemFamily.IsGapReduction

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