Roots of Unity

Definition

In the complex field, a number \( x \) is called an nth root of unity if \( x^n = 1 \).

There are exactly \( n \) distinct nth roots of unity. Arranged by increasing argument, the kth root (\( 0 \leq k < n \)) is:

\[ x_k = e^{i \cdot \frac{2k\pi}{n}} \]

All roots lie on the unit circle, equally spaced. A primitiev root of unity is one whose powers generate all n roots. The first root, \( x_1 = e^{i \cdot \frac{2\pi}{n}} \), is primitive. Denote the primitive root as:

\[ \omega_n = e^{i \cdot \frac{2\pi}{n}} = \cos\left(\frac{2\pi}{n}\right) + i \sin\left(\frac{2\pi}{n}\right) \]

Properties

For even \( n \):

• \( (\omega_n^k)^2 = \omega_{n/2}^k \)
• \( \omega_n^{n/2 + k} = -\omega_n^k \)

Fast Fourier Transform (FFT)

Evaluating an nth-degree polynomial at all nth roots of unity is the Discrete Fourier Trasnform (DFT). Reconstructing the polynomial from these values is the Inverse DFT (IDFT).

DFT

Given a polynomial \( A(x) = \sum_{i=0}^{n-1} a_i x^i \), the DFT computes:

\[ b_k = \sum_{i=0}^{n-1} a_i \omega_n^{ik} \]

FFT Algorithm

Split \( A(x) \) into even and odd terms:

\[ A(x) = A_0(x^2) + x A_1(x^2) \]

where \( A_0(x) = \sum_{i=0}^{m-1} a_{2i} x^i \) and \( A_1(x) = \sum_{i=0}^{m-1} a_{2i+1} x^i \), with \( m = n/2 \).

Using root properties:

• For \( 0 \leq k < m \): \( A(\omega_n^k) = A_0(\omega_m^k) + \omega_n^k A_1(\omega_m^k) \)
• For \( m \leq k < n \): \( A(\omega_n^k) = A_0(\omega_m^{k-m}) - \omega_n^{k-m} A_1(\omega_m^{k-m}) \)

This divide-and-conquer approach reduces complexity to \( O(n \log n) \).

IDFT

Given DFT values \( b_k \), the original coefficients are:

\[ a_k = \frac{1}{n} \sum_{i=0}^{n-1} b_i \omega_n^{-ki} \]

Since \( \omega_n^{-k} = \omega_n^{n-k} \), IDFT can reuse the FFT procedure with conjugated roots.

Iterative Optimization

Replace recursion with bit-reversal permutation. For index i, compute reversed bits:

rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);

Then reorder coefficients and perform butterfly operations layer by layer.

Two-FFT Trick

To convolve polynomials \( A \) and \( B \), form \( C(x) = A(x) + iB(x) \). Compute \( C(x)^2 \), then:

\[ \text{Im}(C(x)^2) = 2A(x)B(x) \]

This reduces the number of FFT calls.

Number Theoretic Transform (NTT)

NTT replaces complex roots with primitive roots modulo a prime, avoiding floating-point operations.

Primitive Roots

For prime modulus \( p \), a primitive root \( g \) satisfies \( \operatorname{ord}_p g = p-1 \). The nth root of unity modulo \( p \) is \( g^{(p-1)/n} \), requiring \( n \mid p-1 \). Common primes: 998244353, 167772161, 1004535809, with primitive root 3.

NTT Code

void NTT(ll *A, int n) {
    calc_rev(n);
    for (int i = 1; i < n; i++)
        if (rev[i] > i) swap(A[i], A[rev[i]]);
    for (int len = 2; len <= n; len <<= 1) {
        ll wlen = qpow(g, (mod-1)/len, mod);
        for (int i = 0; i < n; i += len) {
            ll w = 1;
            for (int j = 0; j < len/2; j++) {
                ll u = A[i+j], v = w * A[i+j+len/2] % mod;
                A[i+j] = (u+v) % mod;
                A[i+j+len/2] = (u-v+mod) % mod;
                w = w * wlen % mod;
            }
        }
    }
}

Divide-and-Conquer FFT

Solve recurrences of the form \( f[i] = \sum_{j=0}^{i} f[i-j] g[j] \).

Process intervals \([l, r]\) recursively. Compute contribution from \([l, mid]\) to \([mid+1, r]\) via convolution with \( g \). Complexity: \( O(n \log^2 n) \).

Implementation

void solve(int l, int r) {
    if (l == r) return;
    int mid = (l+r) >> 1;
    solve(l, mid);
    // Convolve f[l..mid] with g[0..r-l]
    // Add result to f[mid+1..r]
    solve(mid+1, r);
}