claimroutineinferred_dep
Chirp transform and source transform procedures
Chirp transform approximates ; source transform approximates
computed transforms used by the multiplication algorithm
Claim·§9.5 Chirp and source-transform procedures·inside thmInteger multiplication in O(n (lg n)^{1-κ}) time
Statement (paper)
For every disk-grid target tensor with , the arrays satisfy , so the computed convolution applies, and the computed chirp transform returns a disk-grid array approximating . Chirp construction costs in total, with . For a source disk-grid tensor of norm at most , the procedure (linewise approximation to , then , then linewise approximation to , then exact multiplication of the grid numerators by ) has exact counterpart , returns disk-grid outputs in -bit components after an exact normalization scan costing , and the opposite-sign procedure has exact counterpart .
In plain English
On disk-grid inputs of sup norm at most .6, the computed chirp transform approximates , with chirp construction costing and error . The source procedure (for source tensors of norm at most .5) has exact counterpart , returns disk-grid outputs after an normalization scan, and its opposite-sign version has exact counterpart .
Why it's here
This turns the chirp identity into an actual computed procedure: chirp-multiply, then the computed complex convolution, then chirp-multiply, with the input norm bound ensuring the convolution black box applies. Wrapping it with the linewise resampling maps gives a computable version of and, by conjugation, of , which the multiplication algorithm and the later error-propagation and margin arguments use.
Classified routine:
Assembles Bluestein's chirp transform (chirp multiply, convolve, chirp multiply) with the earlier chirp identity, the tensor resampling lemma and the computed complex convolution. The work is bookkeeping on norms, errors and costs, following the Harvey–van der Hoeven n log n framework.