Motivation
Multiplying two polynomials directly computes every pair of coefficients. Evaluation gives another approach: evaluate both polynomials at enough points, multiply the resulting values pointwise, and interpolate. The method becomes fast when the evaluation points have enough symmetry to reuse work.
Roots of unity provide that symmetry. Their even and odd powers connect a transform of size to two transforms of size . We derive this radix-two fast Fourier transform, prove its inverse, and explain why polynomial multiplication needs zero padding to avoid wraparound.
Definitions and arithmetic model
Definition 1.7.1
(Discrete Fourier transform)
Let for an integer , and set . For a complex vector , define its discrete Fourier transform by
The sign convention is part of the definition and must be used consistently throughout the calculation. The inverse uses the opposite exponent. We count exact complex additions and multiplications as unit operations and assume the required roots of unity are available. This is an algebraic operation count, not a guarantee that floating-point computations or arbitrary-precision bit operations take constant time.
Theorem 1.7.2
(Radix-two transform)
For , the DFT can be computed using complex arithmetic operations by recursively transforming the even and odd indexed coefficients.
Theorem 1.7.3
(Inversion and convolution)
The inverse formula is
If two finite coefficient sequences are padded to a power-of-two length at least the length of their ordinary convolution, pointwise multiplication of their DFTs followed by the inverse DFT gives their ordinary convolution.
Split even and odd indices
Proof
(Even–odd splitting and butterflies)
For , write the transform as
Because , the two sums are length- DFTs of the even-indexed and odd-indexed vectors. Call their values and for . Since and the shorter transforms repeat with period ,
These paired updates are called butterflies. Each pair uses the same product twice. For , the transform is simply .
If is the arithmetic cost, the recursive split gives with . At every recursion depth, subproblem lengths sum to , and there are nontrivial levels. Thus the cost is . Precomputing all needed roots or generating them consistently can be included in this operation count; numerical accuracy is a separate issue.
Proof X-ray
Why the same two smaller transforms produce both halves
Squaring a length- root gives a length- root. Shifting an output index by leaves the smaller transforms unchanged but changes the sign of the odd contribution. One pair of smaller values therefore supplies two outputs.
Prove the inverse
Proof
(Inversion by orthogonality of roots of unity)
The key identity is
for . If , the ratio is a nontrivial th root of unity. Its geometric sum is . If , every term is one.
Substitute the forward transform into the proposed inverse and interchange the finite sums. The inner sum vanishes for every input index except , where it equals ; division by leaves exactly . The same radix-two recursion applies to the inverse transform using , followed by scaling all outputs by .
This proof handles : the only root sum is one, and the inverse returns the single input. It also shows why changing the sign in one convention requires changing the inverse consistently. Applying the forward transform twice without the appropriate reversal and scaling is not generally the inverse.
Concept lensAlgebraic
The transform as a matrix, convolution as diagonalization
Let be the matrix with entries , so . The inversion identity says , hence . Cyclic convolution is multiplication of by the circulant matrix , and the convolution theorem says exactly that : every circulant matrix is diagonal in the Fourier basis, with its transformed first column as eigenvalues.
Evaluation and uniqueness
Associate the vector with the polynomial . The forward transform is exactly evaluation of at the roots .
Proposition 1.7.4
(Roots of unity determine the coefficients)
Let and be complex polynomials of degree less than . If for all , then .
Proof
(Evaluation at distinct points determines a low-degree polynomial)
These points are distinct. If two polynomials of degree less than agree at all of them, their difference has at least distinct roots. A nonzero polynomial of degree at most cannot have that many roots, so the difference must be zero. Thus the values determine the coefficient vector uniquely.
The zero polynomial is the only polynomial of degree less than whose evaluations at all roots vanish. In linear-algebra terms the evaluation map is injective between two -dimensional complex vector spaces and hence bijective; the displayed inverse formula makes that bijection explicit. This uniqueness explains why evaluating, multiplying values and interpolating can recover a product when the transform length is large enough. It does not by itself yield a fast algorithm: evaluating at arbitrary points directly can take quadratic work, as can general interpolation. The butterfly recursion and the root-sum inverse exploit the particular evaluation points.
For real input values, for , where the index is interpreted modulo . This follows because and conjugation distributes over finite sums. It is a useful check on a computed transform, but it is not a substitute for the inversion proof. When the input is complex, this conjugate symmetry need not hold.
Following a recursion
At the first level, the algorithm separates indices by parity. At the next level, each subproblem again separates its own even and odd positions. Continuing reaches one-element vectors. A recursive implementation can return each shorter transform and combine it immediately with its sibling; it does not need to evaluate every output independently.
For , the first split uses original positions and . The even half next splits into and , and the odd half into and . Each level accounts for eight coefficient positions across all subproblems. The ordering of leaves in this recursive view differs from ordinary numerical index order; iterative in-place implementations often arrange data to accommodate that ordering. The mathematical recurrence does not depend on a particular in-place permutation.
The running-time bound counts an upper bound on operations for this algorithm. It is not a proof that every possible method requires operations in every computational model. Nor does it assert that an implementation with exact complex-number operations exists on a fixed-width machine. Those are separate questions from the algebraic identity.
Convolution and padding
Definition 1.7.5
(Cyclic convolution)
For length- vectors, define cyclic convolution by
Proof
(Convolution theorem and zero padding)
Its DFT is the pointwise product . Indeed, substitute the convolution into the transform, interchange finite sums, and write . The exponent splits into the factor for and the factor for ; powers are unchanged by indices modulo because . The two factors are exactly and .
For ordinary polynomials and , their product has coefficients for . Choose a power of two and pad both vectors with zeros to length . No nonzero coefficient of the ordinary product has index or more, so reducing indices modulo creates no wraparound. The inverse transform of the pointwise product gives all ordinary coefficients, followed by any zero padding.
For nonempty input sequences, the smallest such power of two is less than twice . Three FFTs and pointwise products therefore use complex operations. Empty polynomials can be handled separately as the zero polynomial.
Counterexample mode
Too little padding changes the product
Take coefficient vectors and but use a cyclic transform of length two. Their ordinary convolution is , while cyclic wraparound adds the last coefficient to the first and produces . Pointwise multiplication at length two computes the cyclic result, not the three ordinary coefficients.
Keeping cyclic and ordinary products separate
A length- cyclic convolution treats positions that differ by a multiple of as the same position. For example, a term of ordinary degree contributes to cyclic position two. In polynomial language, it is multiplication modulo . The DFT is perfectly correct for that cyclic product because every evaluation point satisfies ; evaluations at those points cannot distinguish from .
Zero padding prevents this ambiguity for a single ordinary product. If the highest possible degree is at most , no coefficient can wrap. Choosing the next power of two supports the radix-two recursion while preserving this inequality. The input lengths in the complexity bound are coefficient counts, including any explicitly supplied trailing zeros; removing known trailing zeros is an optional preprocessing step.
A concrete multiplication procedure therefore has four steps: select a power-of-two length satisfying the degree bound, pad both inputs, transform both padded vectors, and invert their pointwise product. The inverse returns a vector of that full length; only the first entries are coefficients that can be nonzero in the ordinary product. Writing down these lengths before implementation prevents an accidental loss of the highest-degree term.
For integer coefficients, one may hope to compute an approximate complex inverse and round each result to the nearest integer. Such rounding is justified only after proving that every coefficient error is strictly below one half. The exact-arithmetic theorem does not provide that numerical error bound. A carefully chosen finite-field transform and reconstruction method can avoid some floating-point issues, but a modulus must have an appropriate root and be large enough, or multiple moduli must be combined. Those further conditions are outside the present proof.
Worked examples
Worked example 1.7.6
(A four-point transform)
For , . Direct substitution gives . The first output is the sum of the entries, and the second and fourth are conjugates because the input is real.
Worked example 1.7.7
(One butterfly level)
For the same input, the even vector has two-point transform and the odd vector has transform . For , the butterfly gives and . For , multiplication by gives and .
Worked example 1.7.8
(A polynomial square)
The polynomial has coefficient vector . Pad to before transforming. Its DFT is ; squaring pointwise and applying the inverse gives . The last zero is padding, not an additional nonzero coefficient.
Worked example 1.7.9
(The one-point case)
For , the DFT and inverse both return the input value. Multiplying two constant polynomials needs only one pointwise product. No butterfly or nontrivial root is required.
Common mistakes
Common mistake
(Mixing sign conventions)
The FFT is an algorithm for a specified DFT; the transform itself is a linear map. Writing a forward exponent with the opposite sign is a valid alternative convention only if the inverse and examples are adjusted to match.
Common mistake
(Padding only to the longer input length)
Pointwise multiplication corresponds to cyclic convolution at the transform length. Ordinary polynomial multiplication needs enough padding to prevent coefficients with indices at least from wrapping into lower positions. Padding merely to the larger input length is not always enough.
Common mistake
(Treating a floating-point FFT as exact)
An exact algebraic proof does not automatically make a floating-point implementation exact. Rounding errors can affect coefficients, and rounding a numerical result to the nearest integer needs a separate error bound. Finite-field number-theoretic transforms also require suitable roots of unity and their own arithmetic assumptions.
Summary
The radix-two FFT splits a DFT into even and odd subtransforms and combines them with butterflies. Root-of-unity orthogonality proves the inverse. The transform turns cyclic convolution into pointwise multiplication, and sufficient zero padding makes it compute ordinary polynomial products within the stated complex-operation bound.
Exercises
Quick check
(Compute the two-point DFT of under the stated sign convention.)
Find first.
Solution · Answer
Since , the transform is .
Quick check
(For , compute the first and third entries of the four-point DFT.)
Use and note which powers appear.
Solution · Answer
and , because .
Quick check
(Why does multiplying length-two coefficient vectors with a length-two cyclic transform fail to recover all three ordinary coefficients in general?)
Where does the coefficient of go?
Solution · Answer
The ordinary convolution can have a nonzero coefficient at index two. A length-two cyclic convolution identifies index two with index zero, adding that coefficient into the first entry. Padding to a length at least three prevents this wraparound.
Quick check
(Explain why the inverse uses division by .)
Substitute the forward transform into the inverse formula.
Solution · Answer
The root-of-unity sum is zero for unequal input and output indices and equals when they agree. Substitution of the forward transform into the inverse therefore yields ; division by recovers .