# Root of unity filter

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 (\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

• Never heard of this, so I'm just curious. But what's the utility of this theorem when we know the polynomial directly? Isn't it better to directly sum the coefficients than to evaluate the entire polynomial at every root of unity up to the $k$th? – Allawonder May 4 at 9:43
• I was doing a question which is as follow : $$(1+x)(1+x^2) \cdots (1+x^{2070})$$ we have to find the sum of coefficients of $x^{9k}$ to get the answer here we can easily find the answer using this tool , can you suggest another method @Allawonder – Advil Sell May 4 at 9:50
• I now see how it may be used for facility in some cases. I had been simply thinking of a polynomial strictly in the form $\sum a_nx^n.$ – Allawonder May 4 at 9:52

## 2 Answers

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$$.

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.