Incidence transform and its transpose
DefinitionSubspaceConv_Supplement_incidencealgebraic-complexityfinite-fieldsp2o-gran-per-chapterp2o-plan-paperp2o-v1subspace-transforms
Let be a commutative ring and . The incidence transform sends a table to the table on given by
Its transpose sends to for .
For , this sums weights on projective points over every hyperplane. The transform is the object of Theorem 2 (fast algorithm) and Theorem 7 (matching lower bound).
Formalization Note The formulas are written for all ; the theorems impose .
Definition code
import Mathlib
import Definitions.Def_SubspaceConv_Supplement_Gr
set_option autoImplicit false
open Classical
namespace SubspaceConv.Supplement
variable {F : Type*} [Field F] [Fintype F] {n : ℕ}
/-- The **incidence transform** `I_n^{a,b}` (Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2), §1.1 "Low-Rank Summation", p.2 (PDF p.3)):
for `f : Gr_q(n, a) → R` and `W ∈ Gr_q(n, b)`,
`(I_n^{a,b} f)(W) = ∑_{U ≤ W, dim U = a} f(U)`.
**Formalization Note** The paper defines it for `0 ≤ a ≤ b ≤ n`; the formula is written for all
`a, b` (the theorems impose `a ≤ b ≤ n`). Values lie in any commutative ring `A`. -/
noncomputable def incidence {A : Type*} [CommRing A] (a b : ℕ) (f : Gr F n a → A)
(W : Gr F n b) : A :=
∑ U ∈ Finset.univ.filter (fun U : Gr F n a => U.1 ≤ W.1), f U
/-- The **transpose** of the incidence transform (Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2), p.2 (PDF p.3): "The transpose sends
weights on b-dimensional subspaces to sums over those containing each a-dimensional subspace"):
for `g : Gr_q(n, b) → R` and `U ∈ Gr_q(n, a)`, `(I^T g)(U) = ∑_{W ≥ U, dim W = b} g(W)`. -/
noncomputable def incidenceT {A : Type*} [CommRing A] (a b : ℕ) (g : Gr F n b → A)
(U : Gr F n a) : A :=
∑ W ∈ Finset.univ.filter (fun W : Gr F n b => U.1 ≤ W.1), g W
end SubspaceConv.Supplement
Source
Perles, Weinstein, A Fast Algorithm for Subspace Convolution, STOC 2027 submission manuscript (sha256 a8ffb1b4e583122875209a3e25ee95aa3a7af933526e165d47c274634e604ab2), §1.1 "Low-Rank Summation", p.2 (PDF p.3)