Polynomials as Points: DFT and Roots of Unity
Pillar: Shape --- "Roots of unity are evenly spaced on the unit circle --- evaluating a polynomial at these SHAPE-constrained points makes the transform invertible and opens the door to \(O(n \log n)\) multiplication."
The Setup
Ch11 L1 showed that polynomial multiplication is the computational core of counting problems. But naive multiplication is \(O(n^2)\). For polynomials of degree \(10^5\), that's \(10^{10}\) operations. Way too slow.
The path to \(O(n \log n)\) starts with a surprising idea: don't work with coefficients at all. Instead, represent a polynomial by its values at carefully chosen points. In point-value form, multiplication is trivially \(O(n)\) --- just multiply corresponding values. The hard part is switching between representations efficiently.
The "carefully chosen points" are the roots of unity. Their geometric structure --- evenly spaced on the unit circle --- is what makes fast conversion possible.
Coefficient Form vs. Point-Value Form
A polynomial of degree \(n-1\) has \(n\) coefficients: \(P(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1}\).
Coefficient form: store the vector \((a_0, a_1, \ldots, a_{n-1})\).
Point-value form: store \(n\) pairs \((x_0, P(x_0)), (x_1, P(x_1)), \ldots, (x_{n-1}, P(x_{n-1}))\) where the \(x_i\) are \(n\) distinct points.
A fundamental fact from algebra: a polynomial of degree at most \(n-1\) is uniquely determined by its values at \(n\) distinct points. So both representations carry exactly the same information.
Why care about point-value form? Because multiplication becomes trivial:
| Operation | Coefficient Form | Point-Value Form |
|---|---|---|
| Multiply | \(O(n^2)\) convolution | \(O(n)\) pointwise: \(C(x_k) = A(x_k) \cdot B(x_k)\) |
| Add | \(O(n)\) | \(O(n)\) |
| Evaluate at arbitrary point | \(O(n)\) Horner's | Lagrange interpolation \(O(n^2)\) |
The plan for fast polynomial multiplication:
- Convert \(A\) and \(B\) from coefficients to point-values. (Evaluation)
- Multiply pointwise: \(C(x_k) = A(x_k) \cdot B(x_k)\) for each \(k\). (Pointwise multiply)
- Convert \(C\) from point-values back to coefficients. (Interpolation)
If steps 1 and 3 each take \(O(n \log n)\), and step 2 takes \(O(n)\), the whole pipeline is \(O(n \log n)\).
The Problem with Arbitrary Points
Evaluating a degree \(n-1\) polynomial at \(n\) arbitrary points using Horner's method is \(O(n)\) per point, \(O(n^2)\) total. No speedup.
The inverse (interpolation via Lagrange's formula) is also \(O(n^2)\) for arbitrary points.
To beat \(O(n^2)\), you need evaluation points with special algebraic structure that enables a divide-and-conquer approach. This is where roots of unity enter.
Roots of Unity: Definition and Properties
The \(n\)-th roots of unity are the \(n\) complex numbers \(\omega\) satisfying \(\omega^n = 1\). They are:
The primitive \(n\)-th root of unity is \(\omega_n = e^{2\pi i / n}\). All roots are powers of this one value: the \(n\)-th roots are \(\omega_n^0, \omega_n^1, \ldots, \omega_n^{n-1}\).
Geometrically, these are \(n\) points equally spaced around the unit circle in the complex plane, starting at \(1\) (the point \((1, 0)\)) and moving counterclockwise. For \(n = 4\): the points are \(1, i, -1, -i\). For \(n = 8\): they're at angles \(0, 45, 90, 135, 180, 225, 270, 315\) degrees.
The shape matters. Evenly spaced points have algebraic properties that random points don't.
Three Properties That Make Everything Work
Property 1: Cancellation
Equivalently, \(\omega_n^{k + n/2} = -\omega_n^k\). The roots come in pairs: each root and its negative are both in the set. This is because the points at angle \(\theta\) and \(\theta + \pi\) are negatives of each other.
Property 2: Halving
When \(n\) is even, squaring the \(n\)-th roots of unity gives you the \((n/2)\)-th roots of unity, each appearing twice:
The squared roots \((\omega_n^0)^2, (\omega_n^1)^2, \ldots, (\omega_n^{n-1})^2\) cycle through \(\omega_{n/2}^0, \omega_{n/2}^1, \ldots, \omega_{n/2}^{n/2-1}\) exactly twice.
This is the halving property, and it's the entire reason FFT achieves \(O(n \log n)\). When you split a polynomial into even and odd parts and substitute \(x^2\), the evaluation points collapse from \(n\) roots to \(n/2\) roots --- a subproblem of half the size.
Property 3: Summation (Orthogonality)
This is a geometric series. When \(j \not\equiv 0 \pmod{n}\), the sum telescopes to \(\frac{(\omega_n^j)^n - 1}{\omega_n^j - 1} = \frac{1 - 1}{\omega_n^j - 1} = 0\). The roots are "balanced" --- they cancel out perfectly.
This orthogonality property is why the DFT is invertible. It's the same reason the Fourier transform has a clean inverse formula.
The Discrete Fourier Transform (DFT)
The Discrete Fourier Transform of a coefficient vector \((a_0, a_1, \ldots, a_{n-1})\) is the vector of values obtained by evaluating the polynomial \(P(x) = \sum_{j=0}^{n-1} a_j x^j\) at each \(n\)-th root of unity:
In matrix form, this is \(\mathbf{y} = F_n \mathbf{a}\), where \(F_n\) is the \(n \times n\) DFT matrix:
The entry in row \(k\), column \(j\) is \(\omega_n^{jk}\). So row \(k\) evaluates the polynomial at \(\omega_n^k\).
For \(n = 4\) with \(\omega_4 = i\):
Worked Example: DFT of \((1, 2, 3, 4)\)
\(P(x) = 1 + 2x + 3x^2 + 4x^3\). The \(4\)th roots of unity are \(1, i, -1, -i\).
| \(k\) | \(\omega_4^k\) | \(P(\omega_4^k) = 1 + 2\omega_4^k + 3\omega_4^{2k} + 4\omega_4^{3k}\) | Result |
|---|---|---|---|
| \(0\) | \(1\) | \(1 + 2 + 3 + 4\) | \(10\) |
| \(1\) | \(i\) | \(1 + 2i + 3(-1) + 4(-i) = -2 - 2i\) | \(-2 - 2i\) |
| \(2\) | \(-1\) | \(1 - 2 + 3 - 4\) | \(-2\) |
| \(3\) | \(-i\) | \(1 - 2i + 3(-1) + 4(i) = -2 + 2i\) | \(-2 + 2i\) |
DFT output: \((10, \; -2-2i, \; -2, \; -2+2i)\).
Notice that \(y_3 = \overline{y_1}\) (complex conjugate). This always happens when the input coefficients are real: \(y_{n-k} = \overline{y_k}\).
The Inverse DFT
Given the point values \((y_0, y_1, \ldots, y_{n-1})\), how do you recover the coefficients?
The inverse DFT is:
In matrix form: \(\mathbf{a} = \frac{1}{n} F_n^{-1} \mathbf{y}\), where \((F_n^{-1})_{j,k} = \omega_n^{-jk}\).
The inverse matrix is just the DFT matrix with \(\omega_n\) replaced by \(\omega_n^{-1} = \overline{\omega_n}\) (the conjugate), scaled by \(\frac{1}{n}\).
Verify with the example: recover \(a_0\) from \((10, -2-2i, -2, -2+2i)\):
Why Is the DFT Invertible?
The DFT matrix \(F_n\) is invertible because its rows (and columns) are orthogonal. Specifically, \(F_n\) is a unitary matrix up to scaling: \(F_n \cdot \overline{F_n}^T = n \cdot I_n\).
This follows directly from the summation property. Take two rows \(k_1\) and \(k_2\) of \(F_n\). Their inner product is:
By the summation property, this is \(n\) when \(k_1 = k_2\) and \(0\) otherwise. The rows are orthogonal. So \(F_n\) is always invertible, and the inverse has the clean formula above.
No special conditions needed. No worrying about whether the matrix is singular. The geometric structure of the roots --- equally spaced on the circle --- guarantees invertibility.
The \(O(n^2)\) Baseline
The naive DFT evaluates the polynomial at \(n\) points, each evaluation costing \(O(n)\):
using Complex = complex<double>;
const double PI = acos(-1.0);
vector<Complex> naiveDFT(const vector<Complex>& coefficients) {
int length = coefficients.size();
vector<Complex> pointValues(length);
Complex primitiveRoot = exp(Complex(0, 2.0 * PI / length));
for (int k = 0; k < length; k++) {
Complex evaluationPoint = pow(primitiveRoot, k);
Complex value = 0;
Complex powerOfPoint = 1;
for (int j = 0; j < length; j++) {
value += coefficients[j] * powerOfPoint;
powerOfPoint *= evaluationPoint;
}
pointValues[k] = value;
}
return pointValues;
}
The inverse DFT is structurally identical --- evaluate at \(\omega_n^{-k}\) instead of \(\omega_n^k\), then divide by \(n\):
vector<Complex> naiveInverseDFT(const vector<Complex>& pointValues) {
int length = pointValues.size();
vector<Complex> coefficients(length);
Complex primitiveRoot = exp(Complex(0, -2.0 * PI / length));
for (int j = 0; j < length; j++) {
Complex evaluationPoint = pow(primitiveRoot, j);
Complex value = 0;
Complex powerOfPoint = 1;
for (int k = 0; k < length; k++) {
value += pointValues[k] * powerOfPoint;
powerOfPoint *= evaluationPoint;
}
coefficients[j] = value / Complex(length, 0);
}
return coefficients;
}
Complexity: \(O(n^2)\) for both DFT and inverse DFT. This is the baseline that FFT improves.
The Full Multiplication Pipeline (Preview)
With the DFT and its inverse, the fast polynomial multiplication recipe is:
- Pad both polynomials to length \(n\) (a power of \(2\) that's at least \(\deg A + \deg B + 1\)).
- Compute \(\text{DFT}(A)\) and \(\text{DFT}(B)\) --- evaluate both at the \(n\)-th roots of unity.
- Pointwise multiply: \(\text{DFT}(C)[k] = \text{DFT}(A)[k] \cdot \text{DFT}(B)[k]\) for all \(k\).
- Compute \(C = \text{IDFT}(\text{DFT}(C))\) --- recover the product coefficients.
With the naive \(O(n^2)\) DFT, the pipeline is still \(O(n^2)\). The FFT in Ch11 L3 exploits the halving property to compute the DFT in \(O(n \log n)\), making the entire pipeline \(O(n \log n)\).
The point-value approach works because polynomial multiplication corresponds to pointwise multiplication of values. If \(C(x) = A(x) \cdot B(x)\), then \(C(x_k) = A(x_k) \cdot B(x_k)\) at every evaluation point. This is why we convert to point-value form, multiply in \(O(n)\), and convert back.
Common Mistakes
-
Forgetting to pad to sufficient length. If \(A\) has degree \(d_A\) and \(B\) has degree \(d_B\), the product has degree \(d_A + d_B\). You need at least \(d_A + d_B + 1\) evaluation points. Pad to the next power of \(2\) that's \(\geq d_A + d_B + 1\). Using too few points causes aliasing --- the DFT wraps around and the recovered coefficients are wrong.
-
Confusing DFT and inverse DFT. The DFT evaluates at \(\omega_n^k\) (counterclockwise roots). The inverse uses \(\omega_n^{-k}\) (clockwise roots) and divides by \(n\). Swapping them gives garbage. The only structural difference is the sign in the exponent and the \(\frac{1}{n}\) scaling.
-
Expecting exact integer results from floating-point DFT. The complex number DFT introduces floating-point errors. After IDFT, round the real parts to the nearest integer. For problems requiring exact results modulo a prime, use NTT instead (Ch11 L4).
Quick Recap
- A polynomial can be represented by coefficients or by its values at \(n\) distinct points. Both representations are equivalent for degree \(< n\).
- In point-value form, multiplication is \(O(n)\) (pointwise). The bottleneck is converting between representations.
- The DFT evaluates a polynomial at the \(n\)-th roots of unity. The inverse DFT recovers coefficients from point values.
- Roots of unity have three key properties: cancellation (\(\omega^{n/2} = -1\)), halving (squaring maps \(n\) roots to \(n/2\) roots), and summation/orthogonality (makes the DFT matrix invertible).
- The naive DFT is \(O(n^2)\). The halving property is the gateway to the \(O(n \log n)\) FFT in the next lesson.
Problems
| Problem | Link | Difficulty | Focus |
|---|---|---|---|
| CSES -- Polynomial Multiplication | cses.fi/problemset/task/2111 | Medium | Direct DFT/IDFT pipeline (use FFT from L3 for speed) |
| CF 993E -- Nikita and Order Statistics | codeforces.com/problemset/problem/993/E | Medium | Reduce to polynomial multiplication via counting |
| Kattis -- polymul2 | open.kattis.com/problems/polymul2 | Medium | Bare polynomial multiplication, test your DFT implementation |
Next lesson: FFT --- the Cooley-Tukey divide-and-conquer algorithm that computes the DFT in \(O(n \log n)\) using the halving property.