Root of unity filter

Question

Can some one help me understand the technique called "Root of unity filter" . I just know how to use it. It's as follow:

For series $f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n$ we need to find the sum of coefficient of terms in which the power is a multiple of any number say $k$ for finding the same we have $\omega $ as $\mathrm{k^{th}}$ of unity and write $$ \dfrac{f(1)+f(\omega)+f(\omega ^2)+ \cdots+ f(\omega^{k-1})}{k}=(a_0 + a_k + a_{2k}+\cdots)$$

please help me understand why and how this works , I tried googling but didn't get any satisfactory answer

Answer 1

Theorem: (Root of Unity Filter)

Define $\omega=e^{2\pi i/n}$ for a positive integer $n$. For any polynomial $F(x)=a_0+a_1x+a_2x^2+\dots$(where we take $a_k=0$ if $k>deg(F)$), the sum $a_0+a_n+a_{2n}+...$ is given by $$a_0+a_n+a_{2n}+\dots=\frac{1}{n}(F(1)+F(\omega)+\dots+F(\omega^{n-1}))$$

Proof: Let $s_k=1+\omega^k+\dots+\omega^{(n-1)k}$

If $n$ divides $k$, then $\omega^k=1$ and so $s_k=1+1+1\dots+1=n$ otherwise $s_k=\frac{1-\omega^{nk}}{1-\omega^k}=0$. So

$F(1)+F(\omega)+\dots+F(\omega^{n-1})=a_0s_0+a_1s_1+a_2s_2+\dots=n(a_0+a_n+a_{2n}+\dots)$

Divide the both sides of the equation by $n$ and the proof is complete.

Source of my knowledge: http://zacharyabel.com/papers/Multi-GF_A06_MathRefl.pdf

There are some examples also which may help you. Please have a look at Problem $2 $ on page $3$.

Answer 2

Hint: This technique is called series multisection.

• Some instructive examples can be found in H.S. Wilf's book generatingfunctionology (2.4.5) to (2.4.9).

• Setting $\omega_r=\exp\left(\frac{2\pi i}{r}\right), r\geq 1$ an integral value, the formula \begin{align*} \sum_{k=0}^{\left\lfloor\frac{n-a}{r}\right\rfloor}\binom{n}{a+kr}x^{a+kr}=\frac{1}{r}\sum_{k=1}^{r}\left(\omega_{r}^k\right)^{-a}\left(1+x\omega_r^k\right)^n, \qquad 0\leq a\leq n,a\leq r-1 \end{align*} is stated as (6.20) in Binomial Identities Derived from Trigonometric and Exponential Series by H.W. Gould.

An application proving a binomial identity can be found e.g. in this MSE answer.