Linear systems with a fixed matrix and the block-sparse linear-system problem (Definition 3.10)
DefinitionLatticePrepro_Reduction_LinearSystemFix a field and a set of instances.
-
LinearSystemFamily F X. A family of linear systems () with a fixed matrix. It consists of:- a finite set of columns and a finite set of blocks;
- a block map such that every block contains exactly columns, where is the block size;
- an -vector space of rows and an -linear map , the fixed matrix;
- a right-hand side for every instance .
The number of blocks is (
numBlocks). -
Solutions (
IsSolution x v): with . -
YES instances (
IsYes x): some solution is binary ( for all ) and has at most one nonzero coordinate in each block. -
NO instances with gap (
IsNo g x): every solution has Hamming weight . -
Gap reductions (
IsGapReduction Lang g), for a language : every is a YES instance and every is a NO instance with gap , that is,
This formalizes the block-sparse linear-system problem with preprocessing, -BSLSP (Definition 3.10). The matrix and its block partition are the fixed input and is the online input. IsGapReduction says that 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 -linear map into an arbitrary -module rather than an matrix, and is any field (the paper uses ). The parameter conditions and 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.
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