Parseval's theorem for the Number Theoretic Transform

172 Views Asked by At

What is Parseval's theorem for the discrete Fourier transform (aka Number Theoretic Transform)?

Namely, I have $\alpha$ a principal $n$th root of unity in a finite field $\mathbb{F}$ (say $\mathbb{Z}_p$ for $p$ prime) and for any $(\varphi_0,\dots,\varphi_{n-1})\in\mathbb{F}^n$, we define the transform $\hat{\varphi}\in\mathbb{F}^n$ via $$ \hat{\varphi}_k := \frac{1}{\sqrt{n}}\sum_{j=0}^{n-1}\alpha^{jk}\varphi_j\,. $$

We have the orthogonality relation $$ \frac{1}{n}\sum_{j=0}^{n-1}\alpha^{jk} = \delta_{k,0} \qquad(k=0,\dots,n-1)$$

but what is the equivalent of Parseval's theorem in this context? Since we don't have complex conjugation on $\mathbb{F}$ I am getting the weird relation $$ \sum_{j=0}^{n-1}\varphi_j\psi_j = \sum_{j=0}^{n-1}\hat{\varphi}_j\hat{\psi}_{-j}\,. $$

What am I doing wrong?