1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Your answer doesn't make sense. Not only does it not depend on the givens, it also doesn't depend too strongly on the polynomial! So it can't be true, since we know that DFT is an injective operator. $\endgroup$ Commented Apr 30, 2015 at 14:19

1 Answer 1

0
$\begingroup$

You haven't explained what you mean by the DFT of a polynomial, so I'm assuming you mean the polynomial evaluated at all $n$th roots of unity, that is, $$ v_i = P(\omega^i), $$ where $\omega = e^{2\pi i/n}$ is a primitive $n$th root of unity. Let now $Q(x) = P(x^2)$, and let $\varpi = e^{\pi i/n}$ be a primitive $2n$th root of unity, $\varpi^2 = \omega$. Let us examine its DFT $w_1,\ldots,w_{2n}$: $$ w_k = Q(\varpi^k) = P(\varpi^{2k}) = P(\omega^k) = v_{k \mod{n}}. $$ We conclude that the DFT of $Q$ is $$ v_1,\ldots,v_n,v_1,\ldots,v_n. $$

$\endgroup$
3
  • $\begingroup$ Thank you Yuval. Several things I don't understand: 1) The leftmost equality - $w_k = Q(\varpi^{2k})$. 2) The rightmost equality - $P(w^k)= v_{k\mod n}$ . If I understand correctly the index k can get values up to 2n. I understand that this equality stands from the given, but how is it justified for k > n? 3) I'm sure my answer is incorrect, but where is the error in the reasoning? $\endgroup$
    – Kardom
    Commented Apr 30, 2015 at 17:55
  • $\begingroup$ 1) I am taking $Q(\varpi^k)$ as the definition of $w_k$. 2) This is because $\omega^n = 1$, so that $\omega^k = \omega^{k \mod{n}}$. 3) I can't make any sense out of your proof. $\endgroup$ Commented May 1, 2015 at 0:54
  • $\begingroup$ Great, I understand now. I misread the notation and confused $\omega$ with $w$. Makes sense now, Thank you. $\endgroup$
    – Kardom
    Commented May 1, 2015 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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