# Calculating DFT for specific polynomial

1. Apr 29, 2015

### aka mor

Hello everyone,

This seems like a simple problem but I get the impression that I'm missing something.

1. The problem statement, all variables and given/known data

Given the values $v_1,v_2,...,v_n$ such that DFTn $(P(x)) = (v_1, v_2, \ldots, v_n)$ and $deg(P(x)) < n$, find DFT2n$P(x^2)$

2. Relevant equations

3. The attempt at a solution

My attempt:
Let $P(x) = \sum\limits_{i=0}^{k} a_ix^i$ .
First, expand $P(x^2)$ :
$$P(x^2) = a_0 + a_1x^2 + a_2x^4 + \ldots + a_kx^{2k}$$
Let's denote by $W^j_n$ the j'th root of unity of order n.
We have:
$$W^j_{2n} = e^{\frac{2\pi i j}{2n}} = e^{\frac{\pi i j}{n }}$$
Using this information, let's expand a term p of $P(x^2)$ on $W^j_{2n}$:
$$a_p(x^2) = a_p(e^\frac{\pi ij}{n})^{2p} = a_p(e^{2\pi i}) ^\frac{jp}{n} = a_p$$ (since $e^{2\pi i} = 1$ ).
So, when evaluating any term of the compound polynomial on some unity root of order 2n we get $\sum\limits_{i=0} ^k ak$ and therefore the final answer is:
$$(\sum\limits_{i=0} ^k ak, \sum\limits_{i=0} ^k ak,\ldots, \sum\limits_{i=0} ^k ak)$$.

This doesn't seem right, I didn't even use the information about $(v_1, \ldots, v_n)$ (answer should be in terms of those?).

Any help would be appreciated.

Last edited by a moderator: May 2, 2015
2. May 4, 2015