Motivation
Multiplying two polynomials by pairing every coefficient of the first with every coefficient of the second can require a quadratic number of coefficient products. Evaluation suggests another route: evaluate both polynomials at the same points, multiply the values, and recover the product's coefficients.
The discrete Fourier transform chooses roots of unity as those points. Their symmetries let even and odd coefficients share smaller evaluations. We prove the inverse transform and the recursive butterfly calculation, then distinguish multiplication modulo a cyclic wraparound from the ordinary polynomial product obtained after enough zero padding.
Definitions
Definition 5.3.1
(Transform convention and cost model)
Let for an integer , and put . For a complex vector , its discrete Fourier transform is
We use a positive exponent in the forward transform. The inverse will use a negative exponent and a factor . For , take and the transform is the identity.
Operation counts below treat a complex addition, multiplication, or division by the known nonzero integer as a unit-cost exact operation, with the required roots of unity available or generated as specified. This algebraic model does not by itself bound floating-point error or bit complexity.
For coefficient lists and of positive lengths , their ordinary convolution is
where terms with an index outside its list are omitted. The associated product polynomial is . Leading or trailing input coefficients may be zero; the stated list length, not an assumed polynomial degree, sets the safe output range.
Theorem/Proposition
Theorem 5.3.2
(Inverse transform and butterflies)
For the transform above,
It can be computed recursively in exact complex operations. The same bound applies to the inverse, using the reciprocal root and a final scaling by .
Theorem 5.3.3
(Transform multiplication and padding)
If two vectors of length have transforms , then applying the inverse transform to the pointwise products gives their cyclic convolution
To compute the ordinary convolution of lists of lengths , choose a power of two , pad both lists with zeros to length , transform, multiply pointwise and invert. The first outputs are exactly the ordinary coefficients; the remaining outputs are zero in exact arithmetic.
Proof sketch or proof idea
A root sum makes the inverse work
Proof
(Inverse transform from the root sum)
For any integer , the geometric-series identity gives
If , the ratio differs from one while its th power equals one. If , every term is one. The identity also holds for , when every integer is divisible by one.
Substitute the forward transform into the proposed inverse and interchange the finite sums. The coefficient of in the recovered th entry is
which is one if and zero otherwise for . Thus the inverse formula recovers every input. In particular the transform is one-to-one: no two length- coefficient vectors have the same transform.
One butterfly combines two smaller transforms
Proof
(Even–odd splitting and its operation count)
For , split the input polynomial into its even and odd coefficient parts:
The number is a primitive th root of unity. Recursively compute the length- transforms and . For , the two values from one butterfly are
because and both points have the same square. At return the sole coefficient. Induction on proves that these butterflies compute exactly the stated transform in the stated output order.
At each recursion level there are butterflies across all subproblems. Each uses one multiplication by a twiddle factor and two additions or subtractions, so there are at most twiddle multiplications and additions for . Roots at a level can be generated by repeated multiplication by its primitive root, with linear additional work per level; alternatively they can be supplied in a table. The inverse uses the same construction with , then scales outputs. This gives the stated asymptotic bound, including the constant-size case.
Proof X-ray
The same square gives a pair of evaluations
The two points and share their square. One recursive even evaluation and one recursive odd evaluation therefore produce both outputs, with only a sign change in the second combination. The recursion is on coefficients, not on two unrelated copies of the full problem. The splitting step needs even at every level, which is why the length is a power of two; at there is nothing to split and the recursion stops.
Pointwise products wrap exponents modulo N
Proof
(Pointwise products and the padding rule)
Let and . At the transform points, is the pointwise product of the transformed vectors. Expanding and applying the inverse gives
The root sum removes all terms whose exponent is not congruent to modulo . Thus the natural output is cyclic: exponents differing by contribute to the same coefficient. Equivalently, it is the product reduced modulo .
For the original lists, . If , this range is strictly below , so no two possible exponents wrap to the same position. The cyclic coefficient at each position is the corresponding ordinary coefficient; all higher positions below receive no terms. The smallest power of two satisfying the inequality is less than twice unless that quantity is one, for which . Hence two forward transforms, pointwise products and one inverse use exact complex operations.
Concept lensAlgebraic
Pointwise multiplication in a quotient ring
The cyclic product is multiplication in the ring . Because has distinct roots, evaluation at these roots is a ring isomorphism onto with componentwise product, by the Chinese remainder theorem. The transform is this isomorphism written in coefficient coordinates, and pointwise multiplication is the ring product on the right-hand side.
Worked examples
Worked example 5.3.4
(A complete length-four calculation)
Multiply by . Pad both coefficient lists to length four and use . Their transforms are
Pointwise multiplication yields . Applying the inverse gives , so the product is . Here , and the final zero is a padding position.
Worked example 5.3.5
(Insufficient padding can wrap a coefficient)
Use the same inputs but transform at length two. The ordinary product has coefficients . Modulo , the term becomes a constant, producing cyclic output . The calculation is a correct cyclic convolution but does not return the ordinary three-coefficient list.
Worked example 5.3.6
(The length-one boundary)
The product of the constant lists and has . Choose : both transforms and the inverse are identities, and the single pointwise product is . No butterfly, nontrivial primitive root or division by a larger transform length is needed.
How the input and output sizes matter
The zero-padding condition is a sufficient worst-case condition for all coefficient values of the specified list lengths. If , wraparound can occur, as in the example, but it need not change every particular answer: some high coefficients may vanish or cancel. Conversely, simply observing a zero in one output position does not prove that no wraparound happened elsewhere.
The transform method produces an entire coefficient list. If only one coefficient is required, directly summing its eligible terms may be cheaper than computing the whole transform. If the lists have many zeros, a sparse representation or a different multiplication method may also be useful. Those alternatives have different input and operation models; the transform bound makes no claim that it is best for every instance.
Correlation is convolution after reversing one list
Suppose has length and has length . For an integer shift , define the finite cross-correlation
Reverse and conjugate the second list by setting for . If is the ordinary convolution of and , then
Indeed, the convolution index equation makes . Terms outside the two lists are omitted in both sums. The same zero-padding rule therefore computes all these shifts, but the output position must be translated back by ; it is not itself the signed shift.
For example, let and . The reversed list is and their ordinary convolution is . The entries correspond to shifts , respectively. At shift zero the value four is . Reversing without conjugating is sufficient for real lists but changes the definition for genuinely complex data.
A norm identity provides another check
The same root sum proves Parseval's finite identity for this convention:
Expand the squared magnitudes, exchange the finite sums and use the root sum on each pair of coefficient indices. Only equal indices remain. The factor is tied to the unscaled forward transform; a convention that scales the forward transform changes that factor. Agreement with the identity is a necessary consistency check, not a proof that each individual transform entry is correct.
Integer answers and approximate arithmetic
When both input lists contain integers, every ordinary coefficient is an integer. Suppose an implementation produces real numbers with a separately established guarantee
Rounding each to the nearest integer then returns the exact coefficient. The strict inequality avoids a tie between two integers. If the inverse calculation produces complex approximations, a bound of less than one half on the error of each real part is sufficient for this rounding step.
The transform identity itself does not provide that numerical guarantee. Approximate roots, arithmetic rounding, overflow and coefficient size must be controlled by a separate error analysis. Exact complex-operation counts likewise do not say that arbitrary large integers can be multiplied in constant bit time. A modular transform with a proved reconstruction bound is another exact approach, but it requires its own modulus and root hypotheses.
Conjugate symmetry and a verification check
If the input coefficients are real, complex conjugation gives for . The equality follows from and . In particular, for an even transform length the entries at indices zero and are real. This symmetry can help check a computed transform, although it does not by itself certify every output coefficient or its rounding error.
For a proposed product list, evaluation at any chosen point gives a necessary identity: the reported product evaluated there must equal the two input evaluations multiplied. One point alone is not a deterministic proof of equality for arbitrary polynomials, because two different polynomials can agree at that point. Comparing every coefficient or using enough distinct evaluation points with a degree bound gives a complete exact check.
Counterexample mode
One evaluation cannot certify all coefficients
At , the polynomials and both evaluate to one, but their coefficient lists differ. Agreement at a single point can detect some errors and miss others. The inverse transform succeeds because it uses all roots and the root-sum identity, not because one evaluation happens to agree.
Common mistakes
Common mistake
(Using the forward sign for the inverse)
Applying the forward transform twice does not return the input. Since , the root sum gives . For and , the transform is , and transforming it again with gives : the entries are reversed and scaled by . The inverse needs and the factor .
Common mistake
(Padding only to the longer list)
Choosing instead of lets exponents wrap. For , length returns the cyclic product , because and fold onto and . Taking returns .
Common mistake
(Reading rounded floating-point output as exact)
The identities above are exact statements about complex numbers. A floating-point run returns approximations, and rounding to integers is justified only when a separate argument shows every error is below one half. Without that bound, a rounded output can be a wrong integer even though the algebra is correct.
Summary
Roots of unity give an invertible evaluation map. Even–odd splitting computes it with butterfly recurrences in exact complex operations. Pointwise products give cyclic convolution; a length at least prevents exponent wraparound and returns ordinary polynomial coefficients. Exact operation counts, bit complexity and numerical rounding guarantees are separate claims.
Exercises
Quick check
(Compute the length-two transform of using the stated positive-exponent convention.)
Solution · Answer
The root is , so the transform is . The inverse uses the same two sums divided by two.
Quick check
(What transform length should be chosen for two lists of lengths three and four if it must be a power of two and use the stated padding rule?)
Solution · Answer
The ordinary product has at most coefficient positions. The smallest permitted power of two at least six is eight.
Quick check
(Give the length-two cyclic convolution of with itself, and compare it with the ordinary convolution.)
Solution · Answer
The ordinary convolution is . The constant and degree-two coefficients wrap together, giving cyclic output at length two.
Quick check
(Why does an absolute real-part error below one half justify rounding an integer coefficient, while an error exactly one half need not?)
Solution · Answer
An open interval of radius one half around an integer contains no other integer and does not reach a midpoint. At exactly one half, the approximation can lie midway between two integers, so rounding depends on the tie rule and need not return the desired one.