Exact-span counts
DefinitionSubspaceConv_Supplement_spanCountalgebraic-complexityfinite-fieldsp2o-gran-per-chapterp2o-plan-paperp2o-v1subspace-transforms
Let (repetitions and zero vectors allowed). For a subspace ,
Subsets are sets of indices, so repeated vectors are distinct choices, and the empty set (with span ) is counted in . These are the numbers computed in Theorem 5.
Formalization Note Indices are Fin ℓ (0-based), and ranges over finite sets of indices.
Definition code
import Mathlib
set_option autoImplicit false
open Classical
namespace SubspaceConv.Supplement
/-- The **exact-span count** (Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2), Theorem 5, p.14–15 (PDF p.15–16)): for vectors
`v_1, …, v_ℓ ∈ F^n` and a subspace `U`, `C(U) = #{A ⊆ [ℓ] : span{v_i : i ∈ A} = U}`.
**Formalization Note** Indices are `Fin ℓ` (0-based) and `A` ranges over `Finset (Fin ℓ)`, so
repeated and zero vectors are distinct indexed choices, and the empty set (span `{0}`) is counted
in `C(⊥)`, as on p.15. -/
noncomputable def spanCount {F : Type*} [Field F] {n ℓ : ℕ} (v : Fin ℓ → Fin n → F)
(U : Submodule F (Fin n → F)) : ℕ :=
(Finset.univ.filter
(fun A : Finset (Fin ℓ) => Submodule.span F (v '' (A : Set (Fin ℓ))) = U)).card
end SubspaceConv.Supplement
Source
Perles, Weinstein, A Fast Algorithm for Subspace Convolution, STOC 2027 submission manuscript (sha256 a8ffb1b4e583122875209a3e25ee95aa3a7af933526e165d47c274634e604ab2), Theorem 5, p.14–15 (PDF p.15–16)