claimroutineinferred_dep
Complex convolution via coefficient twist
Coefficient twist by gives complex cyclic convolution
adapts the synthetic convolution to cyclic form
Claim·§9.4 Complex convolution by a coefficient twist·inside thmInteger multiplication in O(n (lg n)^{1-κ}) time
Statement (paper)
The map , with , is a well-defined isomorphism that multiplies coefficient by and preserves the coefficient sup norm, with inverse multiplying coefficient by . Consequently normalized complex cyclic convolution satisfies , and is a bilinear contraction. Moreover, for disk-grid inputs with one of norm at most , the computed convolution , with , , , has total twist cost , and the headers and the exact normalization of from width to bits cost with no numerical truncation.
In plain English
Twisting coefficient by with is a norm-preserving isomorphism from to . So the normalized cyclic convolution equals and is a bilinear contraction, and its computed version on disk-grid inputs (one of norm at most ) has twist cost , plus for headers and exact normalization from width to .
Why it's here
This turns the negacyclic synthetic convolution of the earlier proposition into a cyclic complex convolution, because multiplying coefficients by powers of converts into and leaves the sup norm unchanged. It also shows the twisting steps add only cost and that the normalization step adds no numerical error, so later chirp and error-propagation arguments can use as a black box.
Classified routine:
Standard weighted-transform twist converting cyclic to negacyclic convolution by multiplying coefficient k by ζ^k (as in Schönhage–Strassen and Crandall–Fagin's weighted transforms), combined with the earlier synthetic convolution proposition and bookkeeping of the twist and normalization costs.