I'm interested in proving the following:
Where $p$ is an odd prime and $z$ is a primitive $p$th root of unity, we let $Q(p)=\sum^{p−1}_{k=0}z^{k^2}$. Prove: $|Q(p)|=\sqrt{p}$.
Specifically, I want to use Plancherel's Theorem to do this proof. I looked at one relevant resource here, but the author was somewhat unclear, so I couldn't fully complete the proof.
Can anyone show me (in reasonable detail) how to prove the proposition using Plancherel's Theorem?
Let $G$ be an abelian group. The dual group $\widehat{G}$ is the set of group homomorphisms $G\to\Bbb T$ equipped with pointwise multiplication as a group operation. Here $\Bbb T$ is the circle group, the set of complex numbers with modulus $1$, and these homomorphisms $G\to\Bbb T$ are called characters. The dual group is more generally defined for locally compact topological groups (and the characters must be continuous maps to be in the dual group) in the setting of Pontryagin duality, but that is far afield.
Let $R$ be a ring, preferably a field. An additive character is a character on the underlying additive group of $R$. One can similarly define a multiplicative character $\chi$ as a character on $R^\times$, with the added proviso that $\chi$ takes the value $0$ on nonunits. Therefore, an additive character is one which satisfies $e(x+y)=e(x)e(y)$ for all $x,y\in R$ and a multiplicative one satisfies $\chi(xy)=\chi(x)\chi(y)$ for all units $x,y$ and $\chi(z)=0$ for nonunits.
If $f:G\to\Bbb C$ is a complex-valued function, its Fourier transform $\widehat{f}:\widehat{G}\to\Bbb C$ is given by
$$\widehat{f}(\chi)=\int_G f(g)\overline{\chi(g)}dg,$$
where there is some Haar measure on $G$ which allows us to integrate functions on it. For discrete groups, in particular finite groups (which almost always by default are given the discrete topology) the integral is simply a sum over the elements of $G$ appropriately normalized.
For us, "appropriately normalized" means so that $f\mapsto\widehat{f}$ is a unitary operator. This means the inner product $\langle \varphi,\psi\rangle=\int_G\varphi(g)\overline{\psi(g)}dg$ is preserved as $\langle\varphi,\psi\rangle=\langle\widehat{\varphi},\widehat{\psi}\rangle$. In particular this implies that the Fourier transform is an isometry with respect to the $L^2$ norm (induced by $\langle\cdot,\cdot\rangle$).
For $\Bbb R$, the characters $\Bbb R\to\Bbb T$ are all of the form $\chi_\omega:x\mapsto e^{2\pi i\omega x}$. Thus, the elements of the dual group can be parametrized by $\Bbb R$ (via $\chi_\omega\leftrightarrow \omega$). In fact, this is a topological group isomorphism, so this allows us to conveniently notationally suppress much of what's going on:
$$\widehat{f}(\chi_w)=\int_{\Bbb R} f(x)\overline{\chi_w(x)}dx\quad {\rm written~as}\quad \widehat{f}(\omega)=\int_{\Bbb R}f(x)e^{-2\pi i\omega x}dx.$$
Since we have identified $\widehat{\Bbb R}$ with $\Bbb R$, we are interpreting $\widehat{f}$ as a function taking real arguments, as opposed to a function whose arguments are characters on the additive group of reals.
With $\Bbb F_p=\Bbb Z/p\Bbb Z$, the additive characters are $e_a(x)=e^{2\pi i a/p}$ for $a\in\Bbb F_p$. The Fourier transform of a function $f:\Bbb F_p\to\Bbb C$ is given by $\widehat{f}(e_a)=|\Bbb F_p|^{-1/2}\sum_{x\in\Bbb F_p}f(x)\overline{e_a(x)}$, or simply
$$\widehat{f}(a)=\frac{1}{\sqrt{p}}\sum_{x\in\Bbb F_p}f(x)e^{-2\pi i ax/p}.$$
I leave it as a quick exercise to verify that $p^{-1/2}$ is indeed the correct scaling factor to make the Fourier transform a unitary operator on the complex vector space of functions $\Bbb F_p\to\Bbb C$.
Consider the Legendre symbol $\chi_\ell(a)$ which is $1$ if $a\in\Bbb F_p^\times$ is a perfect square and $-1$ otherwise (except $\chi_\ell(0)=0$). This is a multiplicative character, it is the isomorphism $\Bbb F_p^\times/(\Bbb F_p^\times)^2\to\{\pm1\}$, more or less. As $k=0,\cdots,p-1$, the values $k^2$ trace out all quadratic residues twice, zero once, and nonresidues no times. This implies
$$Q(p)=\sum_{k=0}^{p-1}e^{2\pi i k^2/p}=\sum_{x\in\Bbb F_p}(\chi_\ell(x)+1)e^{2\pi i x/p}=\sqrt{p}\,\widehat{\chi}_\ell(1).$$
As it turns out, we can compute $|\widehat{\chi}(a)|$ for all multiplicative characters $\chi$ and $a\in\Bbb F_p$.
First consider $a=0$ trivial. We get
$$\widehat{\chi}(0)=\frac{1}{\sqrt{p}}\sum_{x\in\Bbb F_p}\chi(x)=\begin{cases} p^{1/2}-p^{-1/2} & \chi~{\rm trivial} \\ 0 & \rm otherwise \end{cases}$$
Otherwise suppose $a\in\Bbb F_p^\times$ is a unit. Since $a^{p-1}=1$, we know $\chi(a)^{p-1}=1$, so $\chi(a^{-1})=\overline{\chi(a)}$.
$$\widehat{\chi}(a)=\frac{1}{\sqrt{p}}\sum_{x\in\Bbb F_p}\chi(x)e^{-2\pi i ax/p}=\frac{1}{\sqrt{p}}\sum_{x\in \Bbb F_p}\chi(a^{-1}x)e^{-2\pi ix/p}=\overline{\chi(a)}\widehat{\chi}(1),$$
so it suffices to determine $\widehat{\chi}(1)$. If $\chi$ is trivial then $\widehat{\chi}(1)=-p^{-1/2}$. Otherwise we need to use
Plancherel's theorem: the Fourier transform is an isometry, i.e. $|f|_2=|\widehat{f}|_2$.
Recall this follows from the exercise earlier (related to the scaling factor $p^{-1/2}$). Note that the $L^2$ norm in this context is given by $|f|_2=(\sum_{x\in\Bbb F_p}|f(x)|^2)^{1/2}$ and similarly for $|\widehat{f}|_2$.
Clearly $|\chi|_2^2=\sum |\chi(x)|^2=p-1$ (since $|\chi(x)|=1$ for $x\ne0$ and $\chi(0)=0$) and
$$|\widehat{\chi}|_2^2=\sum_{x\in\Bbb F_p}|\widehat{\chi}(x)|^2=\sum_{x\in\Bbb F_p^\times} |\overline{\chi(x)}\widehat{\chi}(1)|=(p-1)|\widehat{\chi}(1)|.$$
Applying Plancheral's theorem with $f=\chi$, we get $(p-1)=(p-1)|\widehat{\chi}(1)|$, hence $|\widehat{\chi}(1)|=1$ for any nontrivial multiplicative character $\chi$. In particular for the Legendre character, we get
$$|Q(p)|=|\sqrt{p}\,\widehat{\chi_\ell}(1)|=\sqrt{p}|\chi_\ell(1)|=\sqrt{p}.$$
That the Fourier transform is unitary is an elegant property that is sometimes foregone in different scalings of the transform. You can see in the linked source that there is no $p^{-1/2}$ factor to balance everything out, and as a result Plancheral's theorem is "off-tilt" an extra factor of $p$. I made it unitary in my discussion for an aesthetic reason: it unifies the language of harmonic analysis used between $\Bbb R$ and $\Bbb F_p$.
In number theory, the context of finite fields, these "(additive) Fourier transforms of multiplicative characters" without the scaling factors are called Gauss sums. Here is a nice survey of them. They have branched out into all different types of sums that weigh additive and multiplicative twisting factors against each other, which are still under investigation today.
I can't help but mention Tate's thesis, because it also concerns mixing additive and multiplicative transforms and characters in order to achieve number-theoretic ends. In $\Bbb R$ the fixed point of the additive transform is the "Gaussian" $g(x)=e^{-\pi x^2}$. Its multiplicative transform (i.e. its Mellin transform) is $\pi^{-s/2}\Gamma(s/2)$. In the field of $\Bbb Q_p$ of $p$-adic numbers (which is the completion of $\Bbb Q$ with respect to the $p$-adic metric) if we take the multiplicative transform of the fixed point of the additive transform, we get the Euler factor $(1-p^{-s})^{-1}$. Multiplying all of these factors together gives us the completed zeta function $\xi(s)=\pi^{-s/2}\Gamma(s/2)\zeta(s)$, which satisfies Riemann's historical functional equation $\xi(s)=\xi(1-s)$. One can unify the whole process and do this whole thing over the adeles, in which case the functional equation is just a particular application of Poisson summation.