Roots-of-unity filter (source code)

= Roots-of-unity filter
{title2=$\frac1m\sum_{j=0}^{m-1}\omega^{j(n-r)}$}

Let $\omega=e^{2\pi i/m}$ be a primitive $m$th <root of unity>. The finite <geometric series> gives
$$
\frac1m\sum_{j=0}^{m-1}\omega^{j(n-r)}=\begin{cases}1&n\equiv r\pmod m,\\0&n\not\equiv r\pmod m.\end{cases}
$$
Consequently, for a <polynomial> $F(z)=\sum_n a_nz^n$, the expression $m^{-1}\sum_j\omega^{-jr}F(\omega^jz)$ keeps exactly the terms whose exponents are congruent to $r$ modulo $m$. This is <orthogonality of characters> for a <cyclic group> in concrete form.

For $m=2$, the even and odd parts are $(F(z)+F(-z))/2$ and $(F(z)-F(-z))/2$. Taking $F(z)=(1+z)^N$ extracts sums of <binomial coefficients> in chosen residue classes. The same calculation works for <formal power series> coefficient by coefficient over a coefficient <field> containing $\omega$ and $1/m$.