claimroutineinferred_dep

Complex convolution via coefficient twist

Coefficient twist by

\zeta^k

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

\Theta:\mathbb C[x_d]/(x_d^r-1)\to\mathcal R_r=\mathbb C[y]/(y^r+1)

x_d\mapsto\zeta y

with

\zeta=e^{\pi i/r}

, is a well-defined isomorphism that multiplies coefficient

k

\zeta^k

and preserves the coefficient sup norm, with inverse multiplying coefficient

k

\zeta^{-k}

. Consequently normalized complex cyclic convolution satisfies

\mathcal M_{\mathbb C}(f,g):=D_-\iota^{-1}\mathcal M_r(\iota D_+f,\iota D_+g)=\frac{f*g}{T}

, and

\mathcal M_{\mathbb C}

is a bilinear contraction. Moreover, for disk-grid inputs

f,g

with one of norm at most

.7

, the computed convolution

\widetilde{\mathcal M}_{\mathbb C}(f,g)=Q_p(\widetilde\theta^-\cdot\iota^{-1}h')

, with

f'=Q_p(\widetilde\theta^+\cdot f)

g'=Q_p(\widetilde\theta^+\cdot g)

h'=\widetilde{\mathcal M}_r(\iota f',\iota g')

, has total twist cost

O(Tp^{1+\delta})

, and the headers and the exact normalization of

h'

from width

w_M

w_{\rm c}

bits cost

O(Tp)

with no numerical truncation.

In plain English

Twisting coefficient

k

\zeta^k

with

\zeta=e^{\pi i/r}

is a norm-preserving isomorphism from

\mathbb C[x_d]/(x_d^r-1)

\mathcal R_r=\mathbb C[y]/(y^r+1)

. So the normalized cyclic convolution

\mathcal M_{\mathbb C}(f,g)

equals

(f*g)/T

and is a bilinear contraction, and its computed version on disk-grid inputs (one of norm at most

.7

) has twist cost

O(Tp^{1+\delta})

, plus

O(Tp)

for headers and exact normalization from width

w_M

w_{\rm c}

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

\zeta

converts

x_d^r-1

into

y^r+1

and leaves the sup norm unchanged. It also shows the twisting steps add only

O(Tp^{1+\delta})

cost and that the normalization step adds no numerical error, so later chirp and error-propagation arguments can use

\widetilde{\mathcal M}_{\mathbb C}

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.

Uses

propSynthetic convolution: error, cost, and formatlemCost and accuracy of synthetic transformlemExact negacyclic product with one truncation

Used by

claimChirp transform and source transform proceduresclaimDisk margins and error propagation through transforms

Sources

PaperOpen

Section: §9.4 Complex convolution by a coefficient twist
Page: —
Label: —
Line: sections/08-assembly.tex:310

Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

info
inferred_dep
outline: "Complex cyclic convolution via coefficient twist" rests on prop:synthetic-convolution
info
inferred_dep
outline: "Complex cyclic convolution via coefficient twist" rests on lem:synthetic-transform-cost
info
inferred_dep
outline: "Complex cyclic convolution via coefficient twist" rests on lem:signed-ring-product