For the primitive roots of unity $\omega_n = e^{i2\pi/n}$ I want to prove that $$\sum_{k=0}^{n-1} \omega_n^{lk} = 0$$ if $n$ doesn't divide $l$.

I have already proven the well-known result $$\sum_{k=0}^{n-1} \omega_n^{k} = 0$$ so I only need to show that if I raise the $\omega_n$s to the power of $l$, I get every power of $w_n$ exactly once. This is a simple algebraic statement but I don't see how to prove it.

  • 3
    $\begingroup$ What you're trying to show is wrong : if $n=4$ and $l=2$, the elements $\omega_4^{2k}$ for $k=0,1,2,3$ are $1,-1,1,-1$. $\endgroup$ – Arnaud D. Jun 20 '16 at 17:21
  • $\begingroup$ Ah, thank you for catching this! $\endgroup$ – Marc Jun 20 '16 at 17:42
  • 1
    $\begingroup$ I believe the @ArnaudD. comment was intended to go under the "Fly by night" answer. One would ordinarily interpret "what you're trying to show" as the statement in the original question $\sum_{k=0}^{n-1} \omega_n^{lk}=0$, in which case it looks like the Arnaud comment is claiming $1 + -1 + 1 + -1 \neq 0$ (though I think it is really claiming $\{-1, 1, -1\}$ is not a permutation of $\{e^{i4\pi/4}, e^{i6\pi/4}, e^{i 8 \pi/4}\}$. $\endgroup$ – Michael Jun 20 '16 at 17:50
  • $\begingroup$ Thanks for posting this clarification. I understood what he meant but it is a bit ambiguous. $\endgroup$ – Marc Jun 20 '16 at 17:56
  • 1
    $\begingroup$ Yes sorry, my comment was about the sentence "I only need to show that if I raise the $\omega_n$s to the power of $l$, I get every power of $\omega_n$ exactly once.", but not about the original question. I should have been more precise. $\endgroup$ – Arnaud D. Jun 20 '16 at 18:43

Say that sum is $s$. Show that $\omega_n^l s=s$ and that $\omega_n^l\ne 1$.

  • $\begingroup$ Thanks, this proves my identity directly. $\endgroup$ – Marc Jun 20 '16 at 17:35

Hint: Show that $(\omega_n^{\ell 1},\ldots,\omega_n^{\ell (n-1)})$ gives a permutation of $(\omega_n^{1},\ldots,\omega_n^{n-1})$ when $\ell$ and $n$ are coprime.

  • $\begingroup$ In fact the sum is $0$ assuming just that $n$ does not divide $l$. $\endgroup$ – David C. Ullrich Jun 20 '16 at 17:24
  • $\begingroup$ This is my question in a different wording. It doesn't seem difficult but I don't know how to prove this. $\endgroup$ – Marc Jun 20 '16 at 17:36
  • $\begingroup$ @Marc No, it's not the same. He's assuming that $n$ and $l$ are coprime, not just that $n$ does not divide $l$. Did you see the comment to your question? The thing about this being a permutation of that is false under your hypotheses... $\endgroup$ – David C. Ullrich Jun 20 '16 at 17:40
  • $\begingroup$ Ah, ok. So this doesn't lead anywhere for my proof. But just for the record: how would I prove this hint? $\endgroup$ – Marc Jun 20 '16 at 17:44
  • $\begingroup$ @Marc If $F$ is a finite set and $f:F\to F$ is surjective or injective then $f$ is bijective. $\endgroup$ – David C. Ullrich Jun 20 '16 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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