Roots of Unity Filter

Average a polynomial over roots of unity to sum coefficients in one residue class.

The idea

The roots of unity filter extracts from a generating function the sum of the coefficients whose index lies in one residue class modulo $n$. Reach for it when a problem asks for a sum of coefficients — or a count of objects — restricted to every $n$th index, and the full generating function is easy to evaluate: setting $x = 1$ sums all the coefficients, and the filter keeps only the wanted ones.

Fix $n$ and let $\omega = e^{2\pi i/n}$ be a primitive $n$th root of unity. When $n$ divides $k$, the powers $\omega^{0k}, \omega^{k}, \dots, \omega^{(n-1)k}$ all equal $1$. Otherwise $\omega^{k} \neq 1$, and the powers form a geometric series summing to $\dfrac{(\omega^{k})^{n} - 1}{\omega^{k} - 1} = 0$. The average

$\frac{1}{n}\sum_{j=0}^{n-1} \omega^{jk}$

therefore equals $1$ when $n \mid k$ and $0$ otherwise. For $n = 3$ the picture is three arrows in the plane: when $3 \nmid k$ they point $120°$ apart and cancel, and when $3 \mid k$ they align.

Now average the generating function over the $n$ evaluation points $x = 1, \omega, \dots, \omega^{n-1}$. Each coefficient of $x^{k}$ is multiplied by exactly this average, so the terms whose index $n$ does not divide cancel, and the sum of the coefficients whose index $n$ divides survives. An extra factor $\omega^{-jr}$ in the average moves the surviving class to the indices congruent to $r$ modulo $n$.

Ways to work on it

• Walkthrough. Build the filter and sum every third binomial coefficient.
• Practice. Sum every nth binomial coefficient via the filter.
• Hardest. Filter with i: track the phase of (1+i) to sum every fourth coefficient.

Not sure where to start? Take the ten-question placement test.