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

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?

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

• 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? – Tarvoc Jul 9 '15 at 7:25