# Primitive roots of unity

I am trying to show that,

If $$f\left( x\right) =a_{0}+a_{1}x+\ldots +a_{k}x^{k}$$ then $$\dfrac {1} {n}\left\{ f\left( x\right) +f\left( wx\right) +\ldots +f\left( w^{n-1}x\right) \right\} =a_{0}+a_{n}x^{n}+a_{2n}x^{2n}+\ldots +a_{\lambda n}x^{\lambda n}$$ $w$ being any root of $x^n=1$(except x= 1), and $\lambda n$ the greatest multiple of n contained in $k$. Show there is a similar formula for $a_{\mu }+a_{\mu +n}x^{n}+a_{\mu+2n}x^{2n}+\dots,$ where $0 < \mu < n$.

Now i know the question presents a result in the first statement and I am supposed to show the result in the second statement but as a challenge or for the fun of it i was hoping to prove both, Although i did n't get much far.

Starting with the LHS of the first result $$\dfrac {1} {n}\left\{ f\left( x\right) +f\left( wx\right) +\ldots +f\left( w^{n-1}x\right) \right\}$$ I thought of substituting values for those functions and then combining the terms $$\dfrac {1} {n}\left\{(a_{0}+a_{1}x+\ldots +a_{k}x^{k}) + (a_{0}+a_{1}wx+\ldots +a_{k}w^{k}x^{k} )+ \dots+ (a_{0}+a_{1}w^{n-1}x+\ldots +a_{k}w^{k(n-1)}x^{k}) \right\}$$

$$=\dfrac {1} {n}\{na_{0}+a_{1}x\left( 1+w +\ldots +w^{n-1}\right) +\dots+a_{k}x^{k}\left( 1+w^{k}+\ldots +w^{k(n-1)}\right)$$

Now I know that $\left( 1+w +\ldots +w^{n-1}\right) = 0$ and from my scratch work proof i highly suspect that $\left( 1+w^{p}+\ldots +w^{p(n-1)}\right) =0$ provided p is not divisible by n (p mod n > 0) as well. Although when p is a multiple of n we have positive but undefined sum.

$$1^{p}+w^{p}+w^{2p}+\ldots +w^{p\left( n-1\right) } = \dfrac {1} {2}+\dfrac {\sin\left( 2p\pi -\dfrac {p\pi } {n}\right) +i\cos \dfrac {p\pi } {n} -i\cos \left( 2p\pi -\dfrac {p\pi } {n}\right) } {2\sin \dfrac {p\pi } {n}}$$ Hence we are left with expected terms but what about the multiple n ? Where am i going wrong here. Also any help with the second part of the question would be much appreciated.

-
You seem to have replaced $w^{r}$ with $w_{r}$. – Aryabhata Apr 19 '12 at 20:32
The coefficient of $x$ in $f(w^r x)$. There is only one $w$ you are supposed to be using. But your resulting expression seems to have all of them... – Aryabhata Apr 19 '12 at 20:36
When $p$ is a multiple of $n$, $w^p=(w^n)^{p/n}=1$ so the sum is simply equal to $n$ :) – Generic Human Apr 19 '12 at 20:36
thanks i can see that mistake i shall revise it. – Comic Book Guy Apr 19 '12 at 20:37
Don't you need $w$ to be a primitive $n$th root? Otherwise: let $f(x)=x^2$, $w=-1$: $$\frac14\left\{f(x)+f(-x)+f((-1)^2x)+f((-1)^3x)\right\}=\frac{4x^2}4=x^2,$$ but $2$ is not divisible by $4$? – Jyrki Lahtonen Apr 19 '12 at 20:52

## 2 Answers

It helps to go the the root of why the formula is true, which is the following orthogonality law$^\dagger$:

$$g(l):=\frac{1}{n}\sum_{j=0} \omega^{jl}=\begin{cases}1 & l\equiv0\bmod n \\ 0 & \rm otherwise. \end{cases}$$

And this is where it comes into play (interpret $f$ as an infinite series with lots of $0$ coefficients):

$$\frac{1}{n}\sum_{j=0}^{n-1} f(\omega^jx) =\frac{1}{n}\sum_{j=0}^{n-1}\sum_{l=0}^\infty a_l(\omega^jx)^l=\sum_{l=0}^\infty a_l x^l\frac{1}{n}\sum_{j=0}^{n-1}\omega^{jl}=\sum_{l=0}^\infty a_l g(l) x^l=\sum_{v=0}^\infty a_{nv}x^{nv}.$$

Now let's work backwards from our given expression:

$$\sum_{v=0}^\infty a_{\mu+nv}x^{\mu+nv}=\sum_{l=0}^\infty a_l g(l-\mu)x^l=\sum_{l=0}^\infty a_l x^l \frac{1}{n}\sum_{j=0}^{n-1}\omega^{j(l-\mu)}=\cdots$$

Try and work it out from there on your own, it's not much further. :-)

$$\cdots=\frac{1}{n}\sum_{j=0}^{n-1}\omega^{-j\mu} \sum_{l=0}^\infty a_l(\omega^j x)^l=\frac{1}{n}\sum_{j=0}^{n-1}\omega^{-j\mu} f(\omega^j x).$$

$^\dagger$Would you like to know why this is true? Consider the fact that $\omega^j$ has order $n'=n/(j,n)$ and therefore is a primitive $n'$th root of unity. By symmetry, the sum of all these roots of unities is zero - consider the fact that its value is unchanged after multiplying by a non-unity $n'$th root - as long as $\omega\ne1$.

-
Thanks very much buddy u made it really simple. – Comic Book Guy Apr 19 '12 at 20:50

Hint: Both sides of the equation are linear functions of the polynomial $f$, so it suffices to handle the case, where $f(x)$ is a monomial.

-