= 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$.
Back to article page