Polynomials and fft

Polynomials and the FFT

Overview

The FFT chapter is about changing representation at the right points. Polynomial multiplication is expensive in coefficient form, cheap in point-value form, and fast overall only when the evaluation and interpolation points have roots-of-unity structure.

Core principle: never treat FFT as a magic multiplication primitive. State the representation, degree-bound, evaluation length, root system, inverse transform, and exactness model before giving an algorithm or bound.

Shared CLRS Conventions

Follow the parent clrs skill for mathematical formatting, formula-free headings, direct polished answers, and CLRS-wide answer style. Keep formulas in display blocks, including degree-bounds, roots of unity, DFT definitions, recurrence equations, and convolution identities.

When to Use

• A prompt asks for polynomial multiplication, convolution, coefficient representation, point-value representation, interpolation, or evaluation at many points.
• A prompt mentions DFT, inverse DFT, FFT, roots of unity, twiddle factors, butterflies, bit reversal, or FFT circuits.
• A prompt tries to multiply degree-bounded polynomials using too few point-value pairs.
• A prompt asks whether textbook complex FFT is safe for exact integer answers.
• A prompt asks for proof moves involving cancellation, halving, summation over roots of unity, or Vandermonde uniqueness.

Do not use this skill for general signal-processing design unless the algorithmic question is the discrete transform, convolution, or roots-of-unity structure.

First Decision: Which Representation Is the Work In?

Workload	Representation to prefer	Watch for
Add two polynomials already in coefficient form	Coefficients	Add coordinatewise; multiplication is the hard operation
Evaluate one polynomial at one point	Coefficients with Horner's rule	This is linear, not FFT-worthy
Multiply many coefficients directly	Convert through point values	Degree-bound must grow before interpolation
Add or multiply values at the same evaluation points	Point values	The points must match between inputs
Recover coefficients from arbitrary points	Interpolation	General interpolation is slower and numerically fragile
Recover coefficients from roots of unity	Inverse DFT	Divide by the transform length after using inverse roots

Use the chapter's two representations as an API contract:

$$ A(x)=\sum_{j=0}^{n-1}a_jx^j $$

The coefficient vector is the stored form above. A point-value form stores distinct points and their values:

$$ {(x_0,y_0),(x_1,y_1),\ldots,(x_{n-1},y_{n-1})} $$

where each value satisfies the relation below.

$$ y_k=A(x_k) $$

Degree-Bound Discipline

The most common FFT mistake is forgetting that multiplication changes the degree-bound. If two inputs have the same degree-bound, the product can require almost twice as many coefficients.

For two coefficient vectors with the degree-bound below:

$$ \operatorname{degree}(A)<n $$

$$ \operatorname{degree}(B)<n $$

the product satisfies the bound below.

$$ \operatorname{degree}(AB)<2n-1 $$

CLRS often pads to a simpler bound for FFT work:

$$ \operatorname{degree\mbox{-}bound}(AB)=2n $$

Operational rule: evaluate both inputs at enough common points to interpolate the product, not merely enough points to represent each input. For radix-two FFT, pad to an FFT length that is a power of two and at least the output coefficient count.

If a teammate says that the original number of point-value pairs is enough, answer with the degree-bound failure first, then the fix. With too few points, interpolation is underdetermined and practical FFT-style multiplication produces aliasing or a circular convolution rather than the desired coefficient product.

Polynomial Multiplication Pipeline

Use this checklist for coefficient-form multiplication:

1. Double the degree-bound. Add high-order zero coefficients so each input has room for the product representation.
2. Evaluate using roots of unity. Compute the DFT of each padded vector at the selected transform length.
3. Pointwise multiply. Multiply corresponding transformed values.
4. Interpolate with the inverse transform. Apply the inverse DFT and scale by the transform length.
5. Trim or report the meaningful coefficients. Keep the coefficients supported by the product degree-bound.

The coefficient formula for direct multiplication is convolution:

$$ c_j=\sum_{k=0}^{j}a_kb_{j-k} $$

The FFT pipeline computes the same convolution through transform space:

$$ a\otimes b=\operatorname{DFT}^{-1}{2n}\left(\operatorname{DFT}{2n}(a)\cdot\operatorname{DFT}_{2n}(b)\right) $$

where the dot in the expression above is componentwise multiplication and the inputs are padded before the transforms.

State the running time as dominated by the forward and inverse transforms:

$$ T(n)=\Theta(n\lg n) $$

Roots of Unity Proof Moves

The roots-of-unity lemmas are not decorative. They are the reason divide-and-conquer evaluation and inverse interpolation work.

The principal root is:

$$ \omega_n=e^{2\pi i/n} $$

All roots are powers of the principal root:

$$ 1,\omega_n,\omega_n^2,\ldots,\omega_n^{n-1} $$

Use these proof moves:

Move	Use it when	What it buys
Cancellation	Changing root order or relating roots at different lengths	Powers of a larger root become powers of a smaller root
Halving	Splitting even and odd coefficients in FFT	Squared roots collapse to the half-size root set
Summation	Proving inverse DFT matrix entries	Off-diagonal geometric sums vanish
Half-turn sign	Combining the second half of FFT outputs	The second half differs by a sign on the odd part

Display the key identities when proving them:

$$ \omega_{dn}^{dk}=\omega_n^k $$

For even transform length, the half-turn relation is:

$$ \omega_n^{n/2}=-1 $$

The summation lemma says the root powers cancel unless the exponent is divisible by the transform length:

$$ \sum_{j=0}^{n-1}\left(\omega_n^k\right)^j=0 $$

Use the expression above only under its precondition: the exponent is nonzero modulo the transform length.

DFT and FFT Reference

The DFT evaluates a coefficient vector at all roots of unity for the chosen transform length:

$$ y_k=A\left(\omega_n^k\right)=\sum_{j=0}^{n-1}a_j\omega_n^{kj} $$

The FFT is the divide-and-conquer algorithm for this evaluation when the transform length is an exact power of two. Split the coefficients into even-indexed and odd-indexed polynomials:

$$ A(x)=A^{\mathrm{even}}(x^2)+xA^{\mathrm{odd}}(x^2) $$

Then recursively evaluate the even and odd parts at the half-size roots and combine them with twiddle factors.

For each index in the first half, the combine equations are:

$$ y_k=y_k^{\mathrm{even}}+\omega_n^k y_k^{\mathrm{odd}} $$

$$ y_{k+n/2}=y_k^{\mathrm{even}}-\omega_n^k y_k^{\mathrm{odd}} $$

The recurrence is:

$$ T(n)=2T(n/2)+\Theta(n) $$

Therefore the transform time is:

$$ T(n)=\Theta(n\lg n) $$

When writing pseudocode, include these obligations:

1. base case returns the single input value,
2. recursive calls receive even and odd coefficient subvectors,
3. the running twiddle factor starts at one,
4. the twiddle factor is multiplied by the principal root each loop,
5. the two outputs per loop are a sum and a difference.

Inverse DFT and Interpolation

Interpolation at roots of unity is the inverse DFT, not arbitrary Vandermonde solving. The inverse matrix has conjugate root powers and a scaling factor.

Recover coefficients with:

$$ a_j=\frac{1}{n}\sum_{k=0}^{n-1}y_k\omega_n^{-jk} $$

Implementation rule: run the same FFT structure with inverse roots, then divide every output by the transform length. Missing the final division is a correctness bug, not a constant-factor detail.

When proving inverse correctness, multiply the DFT matrix by the claimed inverse and use the summation lemma. The diagonal entries survive; off-diagonal entries vanish because their exponent difference is not divisible by the transform length.

FFT Circuits and Iterative Implementations

The circuit view translates recursive FFT into a staged parallel computation.

Use these terms precisely:

• Butterfly: one twiddle multiplication followed by one sum and one difference.
• Twiddle factor: the root power multiplying the odd-side value before the sum and difference.
• Bit-reversal permutation: the input order produced by repeatedly splitting on low-order index bits.
• Stage: a layer of independent butterflies that can run in parallel.

For an input length that is a power of two, the circuit has logarithmically many stages and a linear number of butterflies per stage:

$$ \Theta(\lg n) $$

stages and

$$ \Theta(n\lg n) $$

butterfly operations in total.

Use the bit-reversal lesson when moving from recursive pseudocode to iterative code: either permute inputs first and run bottom-up stages, or keep an equivalent indexing scheme. Do not claim the recursive split disappears; it becomes the input permutation and stage layout.

Exactness and Production Use

Textbook complex FFT is mathematically exact over complex numbers, but real implementations use finite-precision arithmetic. For exact integer polynomial products, do not promise correctness from a plain floating-point FFT unless coefficient and length bounds justify safe rounding.

Production checklist:

1. Bound the largest possible output coefficient before choosing an exact method.
2. If using floating-point FFT, prove the error margin stays below the rounding threshold or use a library with documented guarantees for the input range.
3. If exactness is required, prefer number-theoretic transforms over suitable modular rings or fields.
4. Choose a modulus and root so the needed transform length has a principal root of unity and inverse scaling is valid.
5. Use enough moduli and CRT reconstruction when one modulus cannot cover the coefficient range.

The chapter's modular exercise highlights a modulus form where powers of two can serve as roots in modular arithmetic:

$$ m=2^{tn/2}+1 $$

and uses the candidate root below.

$$ \omega=2^t $$

The later modular-FFT problem uses prime moduli whose multiplicative group contains an element of the required order. In either setting, verify that the transform and inverse transform are well-defined: the root has the required order, the transform length is invertible modulo the modulus, and the summation lemma analogue holds.

Proof and Exercise Patterns

Prompt type	Reusable move
Uniqueness of interpolation	Convert point-value constraints to a Vandermonde system and cite distinct evaluation points
Lagrange interpolation	Build basis polynomials that are one at their own point and zero at all others
Reverse polynomial values	Substitute reciprocal points and account for the degree-bound factor
Cartesian sums of integer sets	Encode membership as polynomial coefficients and use convolution counts
Power-of-three FFT	Split coefficients by index residue and recurse on cubed roots
Chirp transform	Rewrite the exponent to expose a convolution
Multidimensional DFT	Apply one-dimensional transforms along each axis; separability makes order irrelevant
Multipoint evaluation	Build a product tree of linear factors and pass remainders down the tree

For exercises that ask for an algorithm, always state:

1. representation of inputs and outputs,
2. padding or degree-bound assumptions,
3. root or modulus preconditions,
4. whether the result is mathematical exactness or numerical computation,
5. the recurrence or summation that gives the running time.

RED Pressure Failures This Skill Prevents

Baseline failure	Required correction
Saying the original point count is enough for multiplying two degree-bounded inputs	State that the product has a larger degree-bound and needs enough common evaluation points for interpolation
Explaining FFT multiplication without padding	Add high-order zero coefficients before forward transforms
Giving inverse FFT without scaling	Use inverse roots and divide every output by the transform length
Treating roots-of-unity lemmas as optional facts	Use halving for recursive subproblems and summation for inverse correctness
Recommending complex FFT for exact integer products without qualification	Discuss roundoff, coefficient bounds, modular transforms, and CRT reconstruction
Drawing the circuit but ignoring the input permutation	Connect recursive even-odd splitting to bit reversal and staged butterflies
Calling any transform-space product a convolution without checking length	Distinguish linear convolution from circular aliasing caused by insufficient padding

Common Mistakes

Mistake	Correction
Confusing degree with degree-bound	Degree is the highest nonzero term; degree-bound is any strict upper bound used for representation
Multiplying point-value forms evaluated at different points	Pointwise operations require the same evaluation points in the same order
Interpolating a product from too few values	Use enough values for the product degree-bound, usually a padded power-of-two transform length
Forgetting that FFT assumes a power-of-two length in the chapter	Pad or explicitly switch to a generalized transform outside the chapter scope
Using the forward root for inverse DFT	Use inverse powers and then scale
Treating floating-point FFT as exact algebra	State numerical error assumptions or switch to modular arithmetic
Hand-rolling FFT for production by default	Prefer mature numerical or NTT libraries unless the exercise asks for the textbook mechanism
Ignoring coefficient growth in integer convolution	Bound output coefficients before selecting moduli or rounding strategy

Verification Pressure Tests

Use these prompts to check future answers:

1. Multiplication pipeline: Given two coefficient vectors with the same degree-bound, the answer should pad to a product-safe transform length, run two forward DFTs, pointwise multiply, run an inverse DFT, scale, trim, and state the transform-dominated bound.
2. Too-few-points trap: If someone proposes multiplying two point-value forms with only the original number of values, the answer should diagnose the product degree-bound and explain underdetermination or aliasing.
3. Inverse transform: Given transformed values at roots of unity, the answer should use inverse root powers and divide by the transform length.
4. Roots proof: A proof of FFT correctness should invoke halving for squared roots and the half-turn sign for the second half of outputs.
5. Exact integer service: The answer should reject unconditional floating-point exactness and require coefficient bounds, modular roots, invertible transform length, enough moduli, and CRT if needed.
6. Circuit mapping: The answer should identify butterflies, twiddle factors, bit reversal, stage count, and total butterfly work.

Static Checks

• clrs/polynomials-and-fft/SKILL.md exists and its frontmatter name matches the directory slug.
• clrs/SKILL.md routes FFT, DFT, convolution, and polynomial multiplication prompts to this skill.
• No heading contains a formula.
• No Markdown table cell contains display math delimiters.
• The skill includes RED failures for padding, point-count, inverse scaling, exactness, and circuit permutation traps.
• The skill distinguishes educational FFT mechanics from production exactness and library judgment.