Binary and block-sparse vectors (Definitions 3.10 and 4.4)
DefinitionLatticePrepro_Basic_BlocksFix a finite set of coordinates, a set of block labels, and a map assigning each coordinate to its block. Vectors are functions with entries in a type that has a zero (and a one, for binary vectors). The bundle defines:
- Binary vectors (
IsBinary): is binary if for every coordinate . - Support in a block (
blockSupport): for a block label ,
the set of nonzero coordinates of that lie in block .
- At most one nonzero coordinate per block (
AtMostOnePerBlock): for every . - Exactly one nonzero coordinate per block (
ExactlyOnePerBlock): for every .
These are the sparsity patterns used throughout the paper. YES instances of the block-sparse linear-system problem (Definition 3.10) have a binary solution with at most one nonzero coordinate per block, and the completeness property of a moment representation (Definition 4.4) asks for binary evaluation tables with exactly one nonzero coordinate in each block.
Formalization Note: The partition into blocks is encoded by the map ; blocks need not have equal size here (equal block sizes are imposed where needed, e.g. in moment representations). The conditions quantify over every label , so ExactlyOnePerBlock forces every label to have a nonempty block. blockSupport requires decidable equality on and on .
import Mathlib
/-!
# Block-sparse vectors
Vectors `y : ι → F` whose coordinates are partitioned into blocks by a map `blk : ι → β`.
We define binary vectors and vectors with at most (exactly) one nonzero entry per block,
and relate them to the Hamming weight `hammingNorm`.
-/
namespace LatticePrepro
variable {ι β F : Type*}
/-- A vector is binary if every coordinate is `0` or `1`. -/
def IsBinary [Zero F] [One F] (y : ι → F) : Prop := ∀ i, y i = 0 ∨ y i = 1
variable [Fintype ι] [DecidableEq β]
/-- The nonzero coordinates of `y` inside the block `s`. -/
def blockSupport [Zero F] [DecidableEq F] (blk : ι → β) (y : ι → F) (s : β) : Finset ι :=
Finset.univ.filter fun i => blk i = s ∧ y i ≠ 0
/-- At most one nonzero coordinate in every block. -/
def AtMostOnePerBlock [Zero F] [DecidableEq F] (blk : ι → β) (y : ι → F) : Prop :=
∀ s, (blockSupport blk y s).card ≤ 1
/-- Exactly one nonzero coordinate in every block. -/
def ExactlyOnePerBlock [Zero F] [DecidableEq F] (blk : ι → β) (y : ι → F) : Prop :=
∀ s, (blockSupport blk y s).card = 1
end LatticePrepro