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

The problem

Given the values $v_1, v_2, \ldots, v_n$ such that $DFT_n(P(x)) = (v_1, v_2, \ldots, v_n) $ for $ P(x) = \sum\limits_{i=0}^k a_ix^i$ , $k < n$ - find $ DFT_{2n}(P(x^2)) $

My attempt:

First expand $P(x^2) $ : $$P(x^2) = a_0 + a_1x^2 + \ldots + a_k^{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 ij}{2n} = e^\frac{\pi i j}{n}$$ Using this information, let's evaluate a term p of $P(x^2)$ on some $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 seems wrong, I don't even use the information about $(v_1, \ldots, v_n)$(should the answer be in terms of those?)

Any help would be appreciated.

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top