HvdH Proposition 5.4, step (2) — Agarwal–Cooley isomorphism
ProvedIntMul.HvdH.agarwal_cooleycomplexity-theoryinteger-multiplication
Let and let be pairwise coprime integers, . Then there is a ring isomorphism
sending the class of to the class of .
This is the isomorphism "induced by the Chinese remainder theorem" used in step (2) of the proof of Proposition 5.4 to turn a one-dimensional cyclic convolution of length into a -dimensional one. (Under it, .)
Preamble
import Mathlib
Formal statement
namespace IntMul.HvdH
theorem agarwal_cooley (d : ℕ) (s : Fin d → ℕ) (hs : ∀ i, 1 ≤ s i)
(hcop : Pairwise fun i j => Nat.Coprime (s i) (s j)) :
∃ e : (Polynomial ℤ ⧸ Ideal.span {(Polynomial.X ^ (∏ i, s i) - 1 : Polynomial ℤ)}) ≃+*
(MvPolynomial (Fin d) ℤ ⧸
Ideal.span (Set.range fun i => (MvPolynomial.X i ^ s i - 1 : MvPolynomial (Fin d) ℤ))),
e (Ideal.Quotient.mk _ Polynomial.X) = Ideal.Quotient.mk _ (∏ i, MvPolynomial.X i) := 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), proof of Proposition 5.4, step (2) 'Reduce to d-dimensional convolution over Z', p. 41; R. C. Agarwal, J. W. Cooley, New algorithms for digital convolution, IEEE Trans. ASSP 25 (1977).