Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.