Questions: Fast Fourier Transform and Polynomial Multiplication

Question 1

The naive algorithm for multiplying two degree-n polynomials takes O(n^2) time. Why does the FFT-based approach achieve O(n log n)?

• A. The FFT compresses the polynomial coefficients, reducing the problem size
• B. The FFT converts polynomial multiplication from coefficient representation (where multiplication requires convolution, O(n^2)) to point-value representation (where multiplication is pointwise, O(n)); the conversions (FFT and inverse FFT) each take O(n log n), giving O(n log n) total
• C. The FFT uses matrix multiplication, which is faster than O(n^2)
• D. The FFT avoids multiplications entirely by using only additions

Answer: (B)

Polynomial multiplication in coefficient form requires computing the convolution of the two coefficient vectors, which is inherently O(n^2) for the naive approach. The key insight is that in point-value form (polynomial evaluated at 2n points), multiplication is just pointwise multiplication of the values, O(n). The FFT converts between coefficient form and point-value form in O(n log n) by evaluating the polynomial at the 2n-th roots of unity. The full pipeline: (1) FFT on coefficients of A and B to get point values (two O(n log n) transforms), (2) pointwise multiply to get point values of AB (O(n)), (3) inverse FFT to recover coefficients of AB (O(n log n)). Total: O(n log n).

Question 2

The Cooley-Tukey FFT algorithm splits a polynomial A(x) = A_even(x^2) + x * A_odd(x^2) and recursively evaluates at the n-th roots of unity. What property of roots of unity makes this work?

Model answer: The critical property is that squaring the n-th roots of unity gives the (n/2)-th roots of unity: if omega = e^(2*pi*i/n) is a primitive n-th root, then {omega^0, omega^1, ..., omega^(n-1)} squared gives {omega^0, omega^2, ..., omega^(2n-2)} = {(omega^2)^0, (omega^2)^1, ..., (omega^2)^(n/2-1)} repeated twice, and omega^2 is a primitive (n/2)-th root of unity. This means evaluating A_even and A_odd at the (n/2)-th roots of unity (a problem of half the size) gives us exactly the values we need to combine into A's values at the n-th roots of unity. The recurrence T(n) = 2T(n/2) + O(n) solves to T(n) = O(n log n).

This 'halving' property is unique to roots of unity and is why the FFT uses these specific evaluation points. If you evaluated at arbitrary points, the recursive decomposition would not produce subproblems of half the size. The collapsing property — n evaluation points become n/2 after squaring — is the algebraic miracle that enables the divide-and-conquer structure.

Question 3

The inverse FFT recovers polynomial coefficients from point values. It is computed by running the FFT with omega^(-1) instead of omega, then dividing by n.

• T. True
• F. False

Answer: True

The DFT can be expressed as a matrix-vector product: y = F_n * a, where F_n is the n x n DFT matrix with entries F_n[j,k] = omega^(jk). The inverse DFT is a^hat = F_n^(-1) * y. The crucial fact is that F_n^(-1) = (1/n) * conjugate(F_n) = (1/n) * F_n(omega^(-1)): the inverse DFT matrix has entries (1/n) * omega^(-jk). This means the inverse FFT is the same algorithm as the forward FFT, with omega replaced by omega^(-1) = e^(-2*pi*i/n) and a final division by n. This symmetry between forward and inverse transforms is both elegant and practical — a single FFT implementation handles both directions.

Question 4

The FFT requires the input length to be a power of 2.

• T. True
• F. False

Answer: False

The Cooley-Tukey radix-2 FFT requires n to be a power of 2, but this is not a fundamental limitation. For arbitrary n, three approaches work: (1) zero-pad the input to the next power of 2 (simple, at most doubles the input size), (2) use the mixed-radix FFT (Cooley-Tukey generalizes to any factorization n = n_1 * n_2, recursing into FFTs of sizes n_1 and n_2), (3) use Bluestein's algorithm, which reduces an FFT of any size n to a convolution of size 2n, which can be computed via a power-of-2 FFT of size >= 2n. Rader's algorithm handles the special case of prime n by reducing the DFT to a cyclic convolution of size n-1. In practice, zero-padding to a power of 2 is by far the most common approach.

Question 5

Explain how the FFT connects to integer multiplication via the Schonhage-Strassen algorithm.

Model answer: Two n-bit integers can be viewed as polynomials: write a = sum a_i * B^i and b = sum b_i * B^i where B is a base (e.g., 2^16) and the a_i, b_i are 'digits' in base B. The product ab = convolution of the digit sequences, followed by carry propagation. The convolution step is exactly polynomial multiplication, computable in O(n log n) via FFT. Schonhage-Strassen (1971) refined this by working modulo (2^m + 1) for appropriate m (a Fermat number ring), where 2 is a root of unity, eliminating the need for floating-point arithmetic and complex numbers. This gives O(n log n log log n) integer multiplication, which was the asymptotic record for 36 years until Furer (2007). Harvey and van der Hoeven (2021) achieved the conjectured optimal O(n log n), settling a major open problem.

The connection between polynomial multiplication and integer multiplication is that integer multiplication IS polynomial multiplication followed by carries. The FFT handles the polynomial part; carries are a linear-time postprocessing step. Schonhage-Strassen's innovation was doing the FFT over rings where exact arithmetic is possible (no floating-point issues), using the number-theoretic transform (NTT) with modular arithmetic instead of complex roots of unity.