Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
You seem to have replaced $w^{r}$ with $w_{r}$. –  Aryabhata Apr 19 '12 at 20:32
1  
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. –  Hardy 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
show 2 more comments

2 Answers

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|improve this answer
    
Thanks very much buddy u made it really simple. –  Hardy Apr 19 '12 at 20:50
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.