HvdH eq. (2.1) — multidimensional convolution formula
ProvedIntMul.HvdH.eq_2_1complexity-theoryinteger-multiplication
Let be a commutative -algebra, , , and for each let satisfy and for every integer . Write . For arrays indexed by and units put
and let (componentwise subtraction mod ). Then for all arrays ,
This is the -dimensional analogue of Lemma 2.3 (IntMul.HvdH.lemma_2_3). As there, the norm condition in the paper's definition of a principal root is omitted because it plays no role.
Preamble
import Mathlib
Formal statement
namespace IntMul.HvdH
theorem eq_2_1 {R : Type*} [CommRing R] [Algebra ℂ R] {d : ℕ} (n : Fin d → ℕ)
[∀ i, NeZero (n i)] (ω : Fin d → Rˣ) (hω : ∀ i, ω i ^ n i = 1)
(hsum : ∀ i, ∀ j : ℤ, ¬ (n i : ℤ) ∣ j →
∑ k ∈ Finset.range (n i), ((ω i ^ j : Rˣ) : R) ^ k = 0)
(u v : ((i : Fin d) → ZMod (n i)) → R) :
let N : ℂ := ∏ i, (n i : ℂ)
let F : (Fin d → Rˣ) → (((i : Fin d) → ZMod (n i)) → R) → ((i : Fin d) → ZMod (n i)) → R :=
fun w x j => (1 / N) • ∑ k : (i : Fin d) → ZMod (n i),
(∏ i, ((w i ^ (-(((j i).val * (k i).val : ℕ) : ℤ)) : Rˣ) : R)) * x k
(1 / N) • (fun j => ∑ k : (i : Fin d) → ZMod (n i), u k * v (j - k)) =
N • F (fun i => (ω i)⁻¹) (fun j => F ω u j * F ω v j) := by sorry
end IntMul.HvdHSource
D. Harvey, J. van der Hoeven, Integer multiplication in time O(n log n), Ann. of Math. 193 (2021), https://doi.org/10.4007/annals.2021.193.2.4 (preprint https://hal.science/hal-02070778v2), §2.4, equation (2.1), p. 13.