Discrete Fourier Transform of $\omega^{n(n-1)/2}$

Question

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?

Answer 1

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.