Ring-uniform arithmetic straight-line programs
DefinitionSubspaceConv_Supplement_ArithSLPAn arithmetic straight-line program with inputs indexed by and outputs indexed by is a list of gates evaluated in order, gate producing register , together with an output register for each . The gates are: read input ; the constants and ; , and for earlier registers ; for an integer ; and , where is the characteristic of . Reading inputs and the constants are free; each of the other five gates costs one arithmetic operation. One program is evaluated over every commutative ring , given an element .
A program is well formed if every operand is an earlier register and every output is a register. The predicate NoZmul says that no integer-scaling gate occurs.
This is the cost model of "arithmetic operations in " for the bilinear kernel product of Theorem 3 and of "arithmetic operations over " for the exact-span counts of Theorem 5.
Formalization Note It extends the published linear model SubspaceConv.LinSLP of Theorem 1 by the free constant and the multiplication gate. Without the NoZmul restriction, a program whose wiring may depend on the data could write every integer output with one scaling gate.
import Mathlib
set_option autoImplicit false
namespace SubspaceConv.Supplement
/-!
# Ring-uniform arithmetic straight-line programs
The model of "arithmetic operations" of Theorems 3 and 5 of Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2) (p.3, PDF p.4; p.14–15,
PDF p.15–16), with the count of §2 ("We count ring additions, subtractions, and
multiplications", p.11, PDF p.12).
**Formalization Note** This follows the published `SubspaceConv.LinSLP` gate for gate and adds
two gates: `one` (the constant 1) and `mul a b` (the product of two earlier registers). Gates:
`input i`, `zero`, `one` (free), `add a b`, `sub a b`, `mul a b`, `zmul z a` (integer `z` times a
register) and `invp a` (a register times `p⁻¹`), each of the last five costing one operation
whatever its integer. The only free constants are `0` and `1`. One program is evaluated over every
commutative ring `A` given an element `pinv : A` (the theorems require `p · pinv = 1`).
`WellFormed` requires every operand to be an earlier register and every output to be a register,
so the default value `0` of an out-of-range read never occurs. `NoZmul` says no `zmul` gate
occurs (used by Theorem 5, where integer scalings would make every count a single gate).
-/
/-- A gate of an arithmetic straight-line program with inputs indexed by `ι`. -/
inductive AGate (ι : Type*) where
| input (i : ι)
| zero
| one
| add (a b : ℕ)
| sub (a b : ℕ)
| mul (a b : ℕ)
| zmul (z : ℤ) (a : ℕ)
| invp (a : ℕ)
/-- An arithmetic straight-line program with inputs `ι` and outputs `κ`: a list of gates and,
for each output, the register holding it. -/
structure ArithSLP (ι κ : Type*) where
gates : List (AGate ι)
out : κ → ℕ
namespace AGate
variable {ι : Type*}
/-- Every operand of the gate is a register below `k`. -/
def RefsBelow : AGate ι → ℕ → Prop
| input _, _ => True
| zero, _ => True
| one, _ => True
| add a b, k => a < k ∧ b < k
| sub a b, k => a < k ∧ b < k
| mul a b, k => a < k ∧ b < k
| zmul _ a, k => a < k
| invp a, k => a < k
/-- The gate is an arithmetic operation (it is counted in the cost). -/
def IsOp : AGate ι → Bool
| input _ => false
| zero => false
| one => false
| _ => true
/-- The gate is an integer scaling `zmul`. -/
def IsZmul : AGate ι → Bool
| zmul _ _ => true
| _ => false
/-- The value of the gate given the earlier registers `vals`. -/
def value {A : Type*} [CommRing A] (pinv : A) (inp : ι → A) (vals : List A) : AGate ι → A
| input i => inp i
| zero => 0
| one => 1
| add a b => vals.getD a 0 + vals.getD b 0
| sub a b => vals.getD a 0 - vals.getD b 0
| mul a b => vals.getD a 0 * vals.getD b 0
| zmul z a => (z : A) * vals.getD a 0
| invp a => vals.getD a 0 * pinv
end AGate
namespace ArithSLP
variable {ι κ : Type*}
/-- The registers after evaluating the gates in order, starting from the registers `vals`. -/
def evalGates {A : Type*} [CommRing A] (pinv : A) (inp : ι → A) :
List (AGate ι) → List A → List A
| [], vals => vals
| g :: gs, vals => evalGates pinv inp gs (vals ++ [g.value pinv inp vals])
/-- The outputs of the program on the input table `inp`, with `pinv` used as `p⁻¹`. -/
def eval {A : Type*} [CommRing A] (P : ArithSLP ι κ) (pinv : A) (inp : ι → A) (o : κ) : A :=
(evalGates pinv inp P.gates []).getD (P.out o) 0
/-- Operands refer to earlier registers and outputs to registers. -/
def WellFormed (P : ArithSLP ι κ) : Prop :=
(∀ (k : ℕ) (h : k < P.gates.length), P.gates[k].RefsBelow k) ∧ ∀ o, P.out o < P.gates.length
/-- The number of arithmetic operations: the gates `add`, `sub`, `mul`, `zmul`, `invp`. -/
def cost (P : ArithSLP ι κ) : ℕ :=
P.gates.countP AGate.IsOp
/-- No integer-scaling gate `zmul` occurs in the program. -/
def NoZmul (P : ArithSLP ι κ) : Prop :=
∀ g ∈ P.gates, g.IsZmul = false
end ArithSLP
end SubspaceConv.Supplement