HvdH Lemma 2.3 — convolution formula
ProvedIntMul.HvdH.lemma_2_3complexity-theoryinteger-multiplication
Let be a commutative -algebra, , and with and for every integer . For define the DFT by
and the cyclic convolution (indices mod ). Then for all ,
where is the pointwise product.
Formalization note: vectors are functions ZMod n → R; the exponent uses the representatives . The paper's definition of a principal root also asks for a norm on ; that condition plays no role in this lemma and is omitted, so the statement covers every commutative -algebra.
Preamble
import Mathlib
Formal statement
namespace IntMul.HvdH
theorem lemma_2_3 {R : Type*} [CommRing R] [Algebra ℂ R] (n : ℕ) [NeZero n] (ω : Rˣ)
(hω : ω ^ n = 1)
(hsum : ∀ j : ℤ, ¬ (n : ℤ) ∣ j → ∑ k ∈ Finset.range n, ((ω ^ j : Rˣ) : R) ^ k = 0)
(u v : ZMod n → R) :
let F : Rˣ → (ZMod n → R) → ZMod n → R := fun w x j =>
(1 / (n : ℂ)) • ∑ k : ZMod n, ((w ^ (-((j.val * k.val : ℕ) : ℤ)) : Rˣ) : R) * x k
(1 / (n : ℂ)) • (fun j => ∑ k : ZMod n, u k * v (j - k)) =
(n : ℂ) • F ω⁻¹ (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), Lemma 2.3, p. 12 (with the definitions of principal root of unity, F_ω, u·v and u*v in §2.4, pp. 11–12).