For the sequence $x_0$, $x_1$, $\ldots$,$x_{N-1}$, let $\omega=e^{2\pi i/N}$ and define the discrete Fourier transform as

$$X_k = \frac{1}{\sqrt{N}}\sum_{n=0}^{N-1}x_n\omega^{nk}\,.$$

I'm interested in the transform of $x_n=\omega^{n(n-1)/2}$. When $N$ is odd, I found by playing around with Mathematica that

$$X_n = \omega^{-n(n-1)/2}\omega^{(N-1)/8}\,.$$

Any ideas how to prove this identity?

  • $\begingroup$ This looks suspiciously related to Gauss sums (adding tags). What range of values of $N$ did you test this on? Primes only? $\endgroup$ – Jyrki Lahtonen Jul 8 '15 at 19:57
  • $\begingroup$ All odd numbers up to 23 so far. $\endgroup$ – Tarvoc Jul 8 '15 at 21:33
  • $\begingroup$ So that short sentence is 3rd line should read: When $N$ is odd. Or? $\endgroup$ – Jyrki Lahtonen Jul 8 '15 at 21:42
  • $\begingroup$ Yes, sorry, I fixed it. $\endgroup$ – Tarvoc Jul 8 '15 at 21:43

The sequence is closely related to what is called a Zadoff-Chu sequence, or Frank-Zadoff-Chu (FZC) sequence or just a Chu sequence depending on who is doing the name-calling. One of the properties of FZC sequences is that their Discrete Fourier Transforms are another FZC sequence, conjugated, scaled, and possibly time-scaled as well. These sequences are used in modern cellular communication systems. For more details, see the references in the Wikipedia link provided above.

  • $\begingroup$ Thanks! From the article: "If $N_\text{ZC}$ is prime, Discrete Fourier Transform of Zadoff–Chu sequence is another Zadoff–Chu sequence conjugated, scaled and time scaled." So the fact that the identity holds not only for all primes up to 23, but for all odd numbers up to 23, may actually be a coincidence and not be true for larger non-prime odd numbers? $\endgroup$ – Tarvoc Jul 9 '15 at 7:25

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.