Theorem 5 — exact-span counts in operations over
OpenSubspaceConv.Supplement.theorem_5Let ; the vectors may repeat and may be zero. For every subspace let
Then all the numbers , , can be computed in
arithmetic operations over , where is the number of subspaces of .
For a uniformly random subset of the indices, is the probability that its span is exactly .
Formalization Note "Arithmetic operations over " is an arithmetic straight-line program (SubspaceConv.Supplement.ArithSLP) with no inputs, evaluated over with , whose gates may be chosen depending on the vectors (normalizing and indexing the vectors is charged separately by the paper, p.15). It contains no integer-scaling gate, so its only free constants are and ; additions, subtractions, multiplications and multiplications by cost one each. is the published SubLE F n n and the published Mq F n n. One constant depends only on the field; is natural.
Differences from the source:
- reading: arithmetic operations over Q (the vectors given) → a straight-line program over ℚ with no inputs, wiring chosen from (n, ℓ, v), free constants 0 and 1 only, no integer-scaling gate; reason: the paper charges indexing separately (p.15); with free integer scalings each output would cost one gate, so this is the non-trivial reading, and the proof of p.15 (doublings, two transforms) fits it
import Mathlib import Definitions.Def_SubspaceConv_SubLE import Definitions.Def_SubspaceConv_Mq import Definitions.Def_SubspaceConv_Supplement_ArithSLP import Definitions.Def_SubspaceConv_Supplement_spanCount set_option autoImplicit false
namespace SubspaceConv.Supplement
/-- **Theorem 5** (Counting exact spans), Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2), p.14–15 (PDF p.15–16). Given
`v_1, …, v_ℓ ∈ F_q^n`, all numbers `C(U) = #{A ⊆ [ℓ] : span{v_i : i ∈ A} = U}`, `U ∈ Gr_q(n)`, can be
computed in `O_q(ℓ + N_q(n) log N_q(n))` arithmetic operations over `Q`. The vectors may repeat
and may be zero.
**Formalization Note** "Arithmetic operations over `Q`" is an arithmetic straight-line program
`SubspaceConv.Supplement.ArithSLP` with no inputs, evaluated over `ℚ` with `pinv = 1/p`
(`p = ringChar F`); its wiring may depend on `(n, ℓ, v)` (the paper charges normalizing and
indexing the vectors separately, "in addition", p.15). It has no integer-scaling gate
(`NoZmul`), so its only free constants are `0` and `1`; every `add`, `sub`, `mul`, `invp` costs
one. `Gr_q(n)` is the set of all subspaces, the published `SubLE F n n`, and `N_q(n)` is the
published `Mq F n n`. One real constant `C` depends only on `F`; `log` is natural. -/
theorem theorem_5 (F : Type) [Field F] [Fintype F] [DecidableEq F] :
∃ C : ℝ, ∀ (n ℓ : ℕ) (v : Fin ℓ → Fin n → F),
∃ P : ArithSLP Empty (SubLE F n n),
P.WellFormed ∧ P.NoZmul ∧
(P.cost : ℝ) ≤ C * ((ℓ : ℝ) + (Mq F n n : ℝ) * Real.log (Mq F n n : ℝ)) ∧
∀ U : SubLE F n n,
P.eval ((ringChar F : ℚ)⁻¹) (fun e => Empty.elim e) U = (spanCount v U.1 : ℚ) := by sorry
end SubspaceConv.Supplement