Calculating DFT for specific polynomial

[aka mor]

Hello everyone,

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

1. Homework Statement
Given the values $v_1,v_2,...,v_n$ such that DFT_n $(P(x)) = (v_1, v_2, \ldots, v_n)$ and $deg(P(x)) < n$, find DFT_2n$P(x^2)$

Homework Equations

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.

 

[KataKoniK]

Hello,

Your approach seems to be on the right track, but I believe you are missing a key step in your solution. In order to find DFT2n(P(x^2)), we need to first find the DFT2n of P(x). This can be done by using the DFT2n formula, which is:

DFT2n(P(x)) = (v_1, v_2, ..., v_n, v_{n+1}, ..., v_{2n})

Where v_{n+1}, ..., v_{2n} are the conjugates of v_1, ..., v_n respectively. So, in order to find DFT2n(P(x^2)), we need to first find DFT2n(P(x)) and then use the same formula to find DFT2n(P(x^2)). Your approach is correct in finding the DFT2n of P(x^2), but we need to first find DFT2n(P(x)) using the given values of v_1, ..., v_n. I hope this helps. Let me know if you have any further questions.