Olympiad MethodsDifficulty 65-100269 tagged problems

Roots of Unity Filter

Roots of Unity Filter is the habit of using complex roots of unity to isolate terms by congruence class in sums or counts. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\frac{1}{n}\sum_{j=0}^{n-1} f\!\left(\omega^j\right) = \sum_{k \equiv 0 \ (\mathrm{mod}\ n)} a_k, \qquad \omega = e^{2\pi i/n}, \ f(x)=\sum_k a_k x^k.$$

Averaging a polynomial (or series) over the $n$-th roots of unity keeps exactly the coefficients whose index is a multiple of $n$ and cancels all the rest — letting you sum every $n$-th term.

Why It Works

1
Let $\omega = e^{2\pi i/n}$ and consider the sum $S = \frac{1}{n}\sum_{j=0}^{n-1} f(\omega^j)$ for $f(x) = \sum_k a_k x^k$.
2
Swap the order of summation: $S = \sum_k a_k \cdot \frac{1}{n}\sum_{j=0}^{n-1} \omega^{jk}$.
3
The inner geometric sum $\frac{1}{n}\sum_{j=0}^{n-1}(\omega^k)^j$ equals $1$ when $n \mid k$ (every term is $1$) and equals $0$ otherwise (the roots sum to zero since $\omega^k \ne 1$).
4
Thus only the terms with $n \mid k$ survive: $S = \sum_{n\mid k} a_k$. Shifting by a power $\omega^{-r}$ inside (filtering $f(x)x^{-r}$) instead isolates indices $\equiv r \pmod n$.

Worked Examples

Example 1

Evaluate $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \cdots$, the sum of binomial coefficients with index divisible by $3$.

1
Take $f(x) = (1+x)^n = \sum_k \binom{n}{k} x^k$ and filter mod $3$ with $\omega = e^{2\pi i/3}$, a primitive cube root of unity.
2
The filter gives the desired sum as $\frac{1}{3}\left[(1+1)^n + (1+\omega)^n + (1+\omega^2)^n\right]$.
3
Since $1+\omega+\omega^2=0$, we have $1+\omega = -\omega^2$ and $1+\omega^2 = -\omega$; with $|{-}\omega|=1$ and arguments $\pm\frac{\pi}{3}$, $(1+\omega)^n + (1+\omega^2)^n = 2\cos\!\frac{n\pi}{3}$.
4
Therefore the sum equals $\frac{1}{3}\left(2^n + 2\cos\frac{n\pi}{3}\right)$.

Answer:

$\dfrac{1}{3}\left(2^n + 2\cos\dfrac{n\pi}{3}\right)$.

Warm-up

Evaluate $\binom{6}{0} + \binom{6}{2} + \binom{6}{4} + \binom{6}{6}$ using a roots-of-unity filter, and confirm the closed form $2^{n-1}$.

1
Filter $f(x) = (1+x)^6$ on even indices: take $n = 2$, $\omega = e^{2\pi i/2} = -1$, giving $\tfrac{1}{2}\bigl[f(1) + f(-1)\bigr]$.
2
Compute $f(1) = 2^6 = 64$ and $f(-1) = 0^6 = 0$, so the sum is $\tfrac{1}{2}(64 + 0) = 32$.
3
Direct check: $\binom60 + \binom62 + \binom64 + \binom66 = 1 + 15 + 15 + 1 = 32 = 2^{5} = 2^{6-1}$. ✓

Answer:

$32$ (the general even-index sum is $2^{n-1}$).

Olympiad / Challenge

How many subsets of $\{1, 2, \dots, n\}$ have size divisible by $4$? Give a closed form.

1
Sizes are indexed by $\binom{n}{k}$, so we want $\sum_{4\mid k}\binom{n}{k}$ — a mod-$4$ filter of $f(x) = (1+x)^n$ with $\omega = i$.
2
The filter gives $\tfrac{1}{4}\bigl[(1+1)^n + (1+i)^n + (1-1)^n + (1-i)^n\bigr] = \tfrac{1}{4}\bigl[2^n + (1+i)^n + (1-i)^n\bigr]$ (the $(1-1)^n$ term vanishes).
3
Write $1 \pm i = \sqrt2\, e^{\pm i\pi/4}$, so $(1+i)^n + (1-i)^n = 2\cdot 2^{n/2}\cos\tfrac{n\pi}{4} = 2^{n/2 + 1}\cos\tfrac{n\pi}{4}$.
4
Hence the count is $\tfrac{1}{4}\bigl(2^n + 2^{n/2+1}\cos\tfrac{n\pi}{4}\bigr) = 2^{n-2} + 2^{n/2 - 1}\cos\tfrac{n\pi}{4}$. Check $n = 4$: $2^2 + 2^{1}\cos\pi = 4 - 2 = 2 = \binom40 + \binom44$. ✓

Answer:

$2^{n-2} + 2^{\,n/2 - 1}\cos\dfrac{n\pi}{4}$.

Going Deeper

The filter is finite Fourier analysis on $\mathbb{Z}/n\mathbb{Z}$: averaging $f(\omega^j)$ projects onto the indices $\equiv 0$; multiplying by $\omega^{-rj}$ first shifts the projection to indices $\equiv r \pmod n$.
It is the standard AIME/Putnam route for 'sum every $k$-th term' of a binomial or generating function, and for counting configurations whose count is constrained modulo $n$ (e.g. subset-sum divisibility).
Pitfall: $\omega$ must be a PRIMITIVE $n$-th root of unity, and you must average over ALL $n$ of $\omega^0,\dots,\omega^{n-1}$. Using a non-primitive root (e.g. $\omega = -1$ when filtering mod $4$) collapses the wrong residue classes and gives the wrong sum.

Spot the Signal

Look for problems where the key step is using complex roots of unity to isolate terms by congruence class in sums or counts.
You can describe the hard part as using complex roots of unity to isolate terms by congruence class in sums or counts, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the olympiad structure that calls for roots of unity filter, then rewrite the givens around it.
Name the relation that makes Roots of Unity Filter legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Roots of Unity Filter just because the surface looks familiar; verify the required condition first.
Applying Roots of Unity Filter because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let roots of unity filter reveal the structural theorem; then compute only what remains.

Try it on:

Practice a contest problem where the key step is using complex roots of unity to isolate terms by congruence class in sums or counts.

Back to techniques

Olympiad MethodsDifficulty 65-100269 tagged problems

Roots of Unity Filter

Practice this technique Match my level

The Key Result

$$\frac{1}{n}\sum_{j=0}^{n-1} f\!\left(\omega^j\right) = \sum_{k \equiv 0 \ (\mathrm{mod}\ n)} a_k, \qquad \omega = e^{2\pi i/n}, \ f(x)=\sum_k a_k x^k.$$

Averaging a polynomial (or series) over the $n$-th roots of unity keeps exactly the coefficients whose index is a multiple of $n$ and cancels all the rest — letting you sum every $n$-th term.

Why It Works

1
Let $\omega = e^{2\pi i/n}$ and consider the sum $S = \frac{1}{n}\sum_{j=0}^{n-1} f(\omega^j)$ for $f(x) = \sum_k a_k x^k$.
2
Swap the order of summation: $S = \sum_k a_k \cdot \frac{1}{n}\sum_{j=0}^{n-1} \omega^{jk}$.
3
The inner geometric sum $\frac{1}{n}\sum_{j=0}^{n-1}(\omega^k)^j$ equals $1$ when $n \mid k$ (every term is $1$) and equals $0$ otherwise (the roots sum to zero since $\omega^k \ne 1$).
4
Thus only the terms with $n \mid k$ survive: $S = \sum_{n\mid k} a_k$. Shifting by a power $\omega^{-r}$ inside (filtering $f(x)x^{-r}$) instead isolates indices $\equiv r \pmod n$.

Worked Examples

Example 1

Evaluate $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \cdots$, the sum of binomial coefficients with index divisible by $3$.

1
Take $f(x) = (1+x)^n = \sum_k \binom{n}{k} x^k$ and filter mod $3$ with $\omega = e^{2\pi i/3}$, a primitive cube root of unity.
2
The filter gives the desired sum as $\frac{1}{3}\left[(1+1)^n + (1+\omega)^n + (1+\omega^2)^n\right]$.
3
Since $1+\omega+\omega^2=0$, we have $1+\omega = -\omega^2$ and $1+\omega^2 = -\omega$; with $|{-}\omega|=1$ and arguments $\pm\frac{\pi}{3}$, $(1+\omega)^n + (1+\omega^2)^n = 2\cos\!\frac{n\pi}{3}$.
4
Therefore the sum equals $\frac{1}{3}\left(2^n + 2\cos\frac{n\pi}{3}\right)$.

Answer:

$\dfrac{1}{3}\left(2^n + 2\cos\dfrac{n\pi}{3}\right)$.

Warm-up

Evaluate $\binom{6}{0} + \binom{6}{2} + \binom{6}{4} + \binom{6}{6}$ using a roots-of-unity filter, and confirm the closed form $2^{n-1}$.

1
Filter $f(x) = (1+x)^6$ on even indices: take $n = 2$, $\omega = e^{2\pi i/2} = -1$, giving $\tfrac{1}{2}\bigl[f(1) + f(-1)\bigr]$.
2
Compute $f(1) = 2^6 = 64$ and $f(-1) = 0^6 = 0$, so the sum is $\tfrac{1}{2}(64 + 0) = 32$.
3
Direct check: $\binom60 + \binom62 + \binom64 + \binom66 = 1 + 15 + 15 + 1 = 32 = 2^{5} = 2^{6-1}$. ✓

Answer:

$32$ (the general even-index sum is $2^{n-1}$).

Olympiad / Challenge

How many subsets of $\{1, 2, \dots, n\}$ have size divisible by $4$? Give a closed form.

1
Sizes are indexed by $\binom{n}{k}$, so we want $\sum_{4\mid k}\binom{n}{k}$ — a mod-$4$ filter of $f(x) = (1+x)^n$ with $\omega = i$.
2
The filter gives $\tfrac{1}{4}\bigl[(1+1)^n + (1+i)^n + (1-1)^n + (1-i)^n\bigr] = \tfrac{1}{4}\bigl[2^n + (1+i)^n + (1-i)^n\bigr]$ (the $(1-1)^n$ term vanishes).
3
Write $1 \pm i = \sqrt2\, e^{\pm i\pi/4}$, so $(1+i)^n + (1-i)^n = 2\cdot 2^{n/2}\cos\tfrac{n\pi}{4} = 2^{n/2 + 1}\cos\tfrac{n\pi}{4}$.
4
Hence the count is $\tfrac{1}{4}\bigl(2^n + 2^{n/2+1}\cos\tfrac{n\pi}{4}\bigr) = 2^{n-2} + 2^{n/2 - 1}\cos\tfrac{n\pi}{4}$. Check $n = 4$: $2^2 + 2^{1}\cos\pi = 4 - 2 = 2 = \binom40 + \binom44$. ✓

Answer:

$2^{n-2} + 2^{\,n/2 - 1}\cos\dfrac{n\pi}{4}$.

Going Deeper

The filter is finite Fourier analysis on $\mathbb{Z}/n\mathbb{Z}$: averaging $f(\omega^j)$ projects onto the indices $\equiv 0$; multiplying by $\omega^{-rj}$ first shifts the projection to indices $\equiv r \pmod n$.
It is the standard AIME/Putnam route for 'sum every $k$-th term' of a binomial or generating function, and for counting configurations whose count is constrained modulo $n$ (e.g. subset-sum divisibility).
Pitfall: $\omega$ must be a PRIMITIVE $n$-th root of unity, and you must average over ALL $n$ of $\omega^0,\dots,\omega^{n-1}$. Using a non-primitive root (e.g. $\omega = -1$ when filtering mod $4$) collapses the wrong residue classes and gives the wrong sum.

Spot the Signal

Look for problems where the key step is using complex roots of unity to isolate terms by congruence class in sums or counts.
You can describe the hard part as using complex roots of unity to isolate terms by congruence class in sums or counts, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the olympiad structure that calls for roots of unity filter, then rewrite the givens around it.
Name the relation that makes Roots of Unity Filter legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Roots of Unity Filter just because the surface looks familiar; verify the required condition first.
Applying Roots of Unity Filter because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let roots of unity filter reveal the structural theorem; then compute only what remains.

Try it on:

Practice a contest problem where the key step is using complex roots of unity to isolate terms by congruence class in sums or counts.