Grassmann-graph distance and intersection-kernel product
DefinitionSubspaceConv_Supplement_kernelMulalgebraic-complexityfinite-fieldsp2o-gran-per-chapterp2o-plan-paperp2o-v1subspace-transforms
Let with , and put . The Grassmann-graph distance of is
Given coefficients in a commutative ring and weights , the intersection kernel acts by
This is the product computed fast in Theorem 3.
Formalization Note The coefficients are a table indexed by ; since the distance never exceeds , the fallback value used to make the index typecheck is never reached.
Definition code
import Mathlib
import Definitions.Def_SubspaceConv_Supplement_Gr
set_option autoImplicit false
namespace SubspaceConv.Supplement
variable {F : Type*} [Field F] [Fintype F] {n k : ℕ}
/-- The **Grassmann-graph distance** on `V = Gr_q(n, k)` (Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2), §1.1.1, p.3 (PDF p.4)):
`dist(U, W) = k − dim(U ∩ W)`.
**Formalization Note** `U ∩ W` is the infimum `U ⊓ W` of submodules; the subtraction is in `ℕ`
and never truncates, since `dim(U ∩ W) ≤ dim U = k`. -/
noncomputable def grassDist (U W : Gr F n k) : ℕ :=
k - Module.finrank F ↥(U.1 ⊓ W.1)
/-- The **intersection-kernel product** (Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2), §1.1.1, p.3 (PDF p.4)): with `d = min(k, n − k)`,
coefficients `a_0, …, a_d` and weights `f : V → R`,
`(Kf)(U) = ∑_{W ∈ V} a_{dist(U,W)} f(W)`.
**Formalization Note** The coefficients are a table `a : Fin (d + 1) → A`. The distance never
exceeds `d` (paper p.3: "its maximum is d"), so the fallback value `0` in the dependent `if` is
never used; it only makes the index `dist(U, W)` typecheck as an element of `Fin (d + 1)`. -/
noncomputable def kernelMul {A : Type*} [CommRing A] (a : Fin (min k (n - k) + 1) → A)
(f : Gr F n k → A) (U : Gr F n k) : A :=
∑ W : Gr F n k,
(if h : grassDist U W < min k (n - k) + 1 then a ⟨grassDist U W, h⟩ else 0) * f W
end SubspaceConv.Supplement
Source
Perles, Weinstein, A Fast Algorithm for Subspace Convolution, STOC 2027 submission manuscript (sha256 a8ffb1b4e583122875209a3e25ee95aa3a7af933526e165d47c274634e604ab2), §1.1.1, p.3 (PDF p.4)