Theorem 2 — and its transpose in operations
OpenSubspaceConv.Supplement.theorem_2Let be a finite field of characteristic , and let be any commutative ring in which is invertible. For let be the incidence transform, for , and put
the total input and output length. Then and its transpose can each be applied in
arithmetic operations, with a constant depending only on .
The transform replaces the full subspace table (of size ) by tables of size for low-rank summation, such as summing weights of projective points over every hyperplane; Theorem 7 shows the bound is optimal for in the bounded-coefficient model.
Formalization Note The model is the published linear straight-line program SubspaceConv.LinSLP (free input reads and zero; additions, subtractions, integer scalings and multiplications by cost one each). One constant , depending only on the field, bounds both programs for every , boundary cases included; is natural, and . Each program is one ring-uniform program valid over every commutative ring with .
Differences from the source:
- encoding: under the coefficient assumption of theorem 1, O_q(·) arithmetic operations → one well-formed ring-uniform program evaluated over every commutative ring A with p·pinv = 1; one real constant C chosen after F only; reason: the published convention of SubspaceConv.theorem_1; same instances
import Mathlib import Definitions.Def_SubspaceConv_LinSLP import Definitions.Def_SubspaceConv_Supplement_Gr import Definitions.Def_SubspaceConv_Supplement_incidence set_option autoImplicit false universe u
namespace SubspaceConv.Supplement
/-- **Theorem 2**, Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2), p.2 (PDF p.3). Under the coefficient assumption of theorem 1,
`I_n^{a,b}` and its transpose take `O_q(S log S)` arithmetic operations, where
`S = |Gr_q(n, a)| + |Gr_q(n, b)|` is the total input and output length.
**Formalization Note** The model is the published `SubspaceConv.LinSLP` of Theorem 1 (free input
reads and zero; every addition, subtraction, integer scaling and multiplication by `p⁻¹` costs
one operation). `O_q`: one real constant `C`, depending only on the field `F` (chosen before
`n, a, b`), bounds both programs for every `0 ≤ a ≤ b ≤ n`, boundary cases included; `log` is the
natural logarithm, and `S ≥ 2` always. "Under the coefficient assumption of theorem 1": one
well-formed program, evaluated over every commutative ring `A` with an element `pinv`,
`p · pinv = 1` (`p = ringChar F`), computes `I_n^{a,b} f` for every table `f : Gr(n,a) → A`; a
second computes the transpose on every table `g : Gr(n,b) → A`. -/
theorem theorem_2 (F : Type) [Field F] [Fintype F] [DecidableEq F] :
∃ C : ℝ, ∀ n a b : ℕ, a ≤ b → b ≤ n →
∃ (P : LinSLP (Gr F n a) (Gr F n b)) (Q : LinSLP (Gr F n b) (Gr F n a)),
P.WellFormed ∧ Q.WellFormed ∧
(P.cost : ℝ) ≤ C * ((Fintype.card (Gr F n a) + Fintype.card (Gr F n b) : ℕ) : ℝ) *
Real.log ((Fintype.card (Gr F n a) + Fintype.card (Gr F n b) : ℕ) : ℝ) ∧
(Q.cost : ℝ) ≤ C * ((Fintype.card (Gr F n a) + Fintype.card (Gr F n b) : ℕ) : ℝ) *
Real.log ((Fintype.card (Gr F n a) + Fintype.card (Gr F n b) : ℕ) : ℝ) ∧
∀ (A : Type u) [CommRing A] (pinv : A), (ringChar F : A) * pinv = 1 →
(∀ f : Gr F n a → A, P.eval pinv f = incidence a b f) ∧
∀ g : Gr F n b → A, Q.eval pinv g = incidenceT a b g := by sorry
end SubspaceConv.Supplement