Introduction to harmonic analysis over finite fields

These are notes I made for my graduate student seminar talk given on February 1st 2019 at Yale. These are also available in pdf format.

Finite Abelian groups

Let $G$ be a finite abelian group. We denote by $\hat{G}$ the collection of characters (i.e. homomorphisms) $\chi:G\rightarrow\mathbb{C}^{\times}$ . $\hat{G}$ has a group structure by pointwise multiplication, and is called the character group of $G$ . Note that since $\chi^{\left|G\right|}=1$ , we have that $\left|\chi\left(g\right)\right|=1$ for every $g\in G$ , and therefore $\chi\left(-g\right)=\chi\left(g\right)^{-1}=\overline{\chi\left(g\right)}$ .

Example: Let $G=\mathbb{Z}/n\mathbb{Z}$ . Then $\chi\left(1\right)^{n}=\chi\left(n\right)=\chi\left(0\right)=1$ , and therefore $\chi\left(1\right)=e^{\frac{2\pi ik}{n}}$ for some $k$ , and then $\chi\left(j\right)=\chi\left(1\right)^{j}=e^{\frac{2\pi ik}{n}j}$ . It can be verified that $\chi_{k}\left(j\right)=e^{\frac{2\pi ik}{n}j}$ is indeed a character of $G$ . Therefore we have that $G\cong\hat{G}$ by $k\mapsto\chi_{k}$ .
Example: Let $G,H$ be two finite abelian groups. Then $\hat{G}\times\hat{H}\cong\widehat{G\times H}$ by $\left(\chi,\mu\right)\mapsto\left(g,h\right)\mapsto\chi\left(g\right)\mu\left(h\right)$ .
Recall that if $G$ is a finite abelian group, then $G$ is isomorphic to a finite product of finite cyclic groups. Therefore we have
Corollary: $G\cong\hat{G}$ .
This isomorphism is far from being canonical, it depends on the choice of generators for the cyclic groups.

We will now use the character group $\hat{G}$ in order to expand functions $f:G\rightarrow\mathbb{C}$ in terms of characters. Denote $S\left(G\right)=\left\{ f:G\rightarrow\mathbb{C}\right\} $ the space of all functions from $G$ to $\mathbb{C}$ . We have an inner product defined on $S\left(G\right)$ by

$$\begin{aligned} \left\langle f_{1},f_{2}\right\rangle =\sum_{g\in G}f_{1}\left(g\right)\overline{f_{2}\left(g\right)} & & f_{1},f_{2}\in S\left(G\right).\end{aligned}$$

Lemma: Let $\chi_{1},\chi_{2}\in S\left(G\right)$ . Then $\left\langle \chi_{1},\chi_{2}\right\rangle =\begin{cases} 0 & \chi_{1}\ne\chi_{2}\\ \left|G\right| & \chi_{1}=\chi_{2} \end{cases}$ .

Proof: If $\chi_{1}=\chi_{2}=\chi$ then $\left\langle \chi_{1},\chi_{2}\right\rangle =\sum_{g\in G}\chi\left(g\right)\overline{\chi\left(g\right)}=\sum_{g\in G}1=\left|G\right|$ .

If $\chi_{1}\ne\chi_{2}$ , then there exists $g_{0}\in G$ with $\chi_{1}\left(g_{0}\right)\ne\chi_{2}\left(g_{0}\right)$ and then
$$\begin{aligned} \left\langle \chi_{1},\chi_{2}\right\rangle & =\sum_{g\in G}\chi_{1}\left(g\right)\overline{\chi_{2}\left(g\right)}\\ & =\sum_{g\in G}\chi_{1}\left(g_{0}+g\right)\overline{\chi_{2}\left(g_{0}+g\right)}\\ & =\chi_{1}\left(g_{0}\right)\chi_{2}\left(g_{0}\right)^{-1}\left\langle \chi_{1},\chi_{2}\right\rangle ,\end{aligned}$$
and since $\chi_{1}\left(g_{0}\right)\chi_{2}\left(g_{0}\right)^{-1}\ne1$ , we get $\left\langle \chi_{1},\chi_{2}\right\rangle =0$ . $\blacksquare$

Since we know that $S\left(G\right)$ is a vector space of dimension $\left|G\right|$ over $\mathbb{C}$ , and since $\left|\hat{G}\right|=\left|G\right|$ , we have that

Corollary: The set $\left(\frac{1}{\sqrt{\left|G\right|}}\chi\right)_{\chi\in\hat{G}}$ forms an orthonormal basis for $S\left(G\right)$ .

Given a function $f\in S\left(G\right)$ , we can write its expansion with respect to this basis by
$$f=\sum_{\chi\in\hat{G}}\left\langle f,\frac{1}{\sqrt{G}}\chi\right\rangle \frac{1}{\sqrt{G}}\chi.$$
We denote $\hat{f}\left(\chi\right)=\left\langle f,\frac{1}{\sqrt{G}}\chi^{-1}\right\rangle $ . $\hat{f}$ is a function $\hat{f}:\hat{G}\rightarrow\mathbb{C}$ , i.e. $\hat{f}\in S\left(\hat{G}\right)$ . Then we have $f=\sum_{\chi\in\hat{G}}\hat{f}\left(\chi^{-1}\right)\frac{1}{\sqrt{G}}\chi.$ From this expansion we get Plancherel’s theorem:

Theorem (Plancherel): The map $f\mapsto\hat{f}$ is unitary.

Proof: Since $\left(\frac{1}{\sqrt{G}}\chi\right)_{\chi\in\hat{G}}$ is an orthonormal basis, we have that $\newcommand{\Norm}[1]{\left\Vert #1\right\Vert }$ $\Norm f^{2}=\sum_{\chi\in\hat{G}}\left|\hat{f}\left(\chi^{-1}\right)\right|^{2}=\sum_{\chi\in\hat{G}}\left|\hat{f}\left(\chi\right)\right|^{2}=\Norm{\hat{f}}^{2}$ , and therefore $f\mapsto\hat{f}$ preserves length and is unitary. $\blacksquare$

We have a canonical map $\varphi:G\rightarrow\hat{\hat{G}}$ by $\varphi\left(g\right)\left(\chi\right)=\chi\left(g\right)$ . One can check that this is an isomorphism. By definition
$$\begin{aligned} \hat{f}\left(\chi\right)=\left\langle f,\chi^{-1}\right\rangle & =\sum_{g\in G}f\left(g\right)\frac{1}{\sqrt{\left|G\right|}}\chi\left(g\right)\\ & =\sum_{g\in G}f\left(g\right)\frac{1}{\sqrt{\left|G\right|}}\varphi\left(g\right)\left(\chi\right).\end{aligned}$$
Therefore the coefficient of $\varphi\left(g\right)^{-1}=\varphi\left(-g\right)$ in $\hat{f}\left(\chi\right)$ is $f\left(-g\right)$ , and we get

Theorem (Fourier Inversion formula): $\hat{\hat{f}}\left(\varphi\left(g\right)\right)=f\left(-g\right)$ .
If we write $g$ for $\varphi\left(g\right)$ (identifying $\hat{\hat{G}}$ with $G$ via $\varphi$ ), we have $\hat{\hat{f}}\left(g\right)=f\left(-g\right)$ .

Finite fields

Let $\mathbb{F}$ be a finite field. Then $\mathbb{F}$ is a finite extension of $\mathbb{F}_{p}$ for $p=\operatorname{char}\mathbb{F}$ . Denote $k=\left[\mathbb{F}:\mathbb{F}_{p}\right]$ . Let $\psi^0:\mathbb{F}_{p}\rightarrow\mathbb{C}^{\times}$ be a nontrivial character. Denote $\psi = \psi^0 \circ \mathrm{Tr}_{\mathbb{F}/\mathbb{F}_{p}} \in \hat{\mathbb{F}}$ . Consider the map $\mathbb{F}\rightarrow\hat{\mathbb{F}}$ defined by $a\mapsto\psi_{a}$ , where $\psi_{a}\left(x\right)=\psi \left( a x \right)=\psi^0\left(\mathrm{Tr}_{\mathbb{F}/\mathbb{F}_{p}}\left(ax\right)\right)$ . This is a homomorphism, and it is injective: let $b\in\mathbb{F}$ with $\mathrm{Tr}\left(b\right)\ne0$ (such $b$ exists because $\mathrm{Tr}_{\mathbb{F}/\mathbb{F}_{p}}b=0$ $\iff$ $b^{p^{k-1}}+b^{p^{k-1}}+\dots+b=0$ , this is a polynomial of degree $p^{k-1}$ , and therefore can has at most $p^{k-1}$ roots. Therefore there exists an element of $\mathbb{F}$ with $\mathrm{Tr}_{\mathbb{F}/\mathbb{F}_{p}}\left(b\right)\ne0$). Then if $a\ne0$ , $\psi_{a}\left(\frac{1}{\mathrm{Tr}\left(b\right)}ba^{-1}\right)=\psi^0\left(1\right)\ne1$ .

Since $\left|\mathbb{F}\right|=\left|\hat{\mathbb{F}}\right|$ , the map $a\mapsto\psi_{a}$ is an isomorphism $\mathbb{F}\rightarrow\hat{\mathbb{F}}$ .

Corollary: Let $\psi:\left(\mathbb{F},+\right)\rightarrow\mathbb{C}^{\times}$ be a non-trivial character. Then for every $\psi'\in\hat{\mathbb{F}}$ there exists a unique $a\in\mathbb{F}$ , such that $\psi'\left(x\right)=\psi\left(ax\right)$ .

Recall that for $\mathbb{R}$ , we have that every unitary (continuous) character is of the form $x\mapsto e^{i\xi x}$ , for some $\xi\in\mathbb{R}$ . The above is an analog of the following statement for finite fields.

For a non-trivial character $\psi:\mathbb{F}\rightarrow\mathbb{C}$ , denote $\psi_{a}:\mathbb{F}\rightarrow\mathbb{C}$ by $\psi_{a}\left(x\right)=\psi\left(ax\right)$ . We will denote the Fourier transform of $f\in S\left(\mathbb{F}\right)$ with respect to the character $\psi$ by $\left(\mathcal{F}_{\psi}f\right)\left(a\right)=\hat{f}\left(\psi_{a}\right)$ , i.e. $$\left(\mathcal{F}_{\psi}f\right)\left(a\right)=\hat{f}\left(\psi_{a}\right)=\left\langle f,\frac{1}{\sqrt{\left|\mathbb{F}\right|}}\psi_{a}^{-1}\right\rangle =\frac{1}{\sqrt{\left|\mathbb{F}\right|}}\sum_{x\in\mathbb{F}}f\left(x\right)\psi\left(ax\right).$$
Under this identification $\left(\mathcal{F}_{\psi}\mathcal{F}_{\psi}f\right)\left(x\right)=f\left(-x\right)$ , and $\left(\mathcal{F}_{\psi^{-1}}\mathcal{F}_{\psi}f\right)\left(x\right)=f\left(x\right)$ , where the latter follows from the relation $\left(\mathcal{F}_{\psi^{-1}}f\right)\left(a\right)=\left(\mathcal{F}_{\psi}f\right)\left(-a\right)$ .

Mellin transform

Given a function $f:\mathbb{F}^{\times}\rightarrow\mathbb{C}$ , its Mellin transform is the function $\mathcal{M}f:\widehat{\mathbb{F}^{\times}}\rightarrow\mathbb{C}$ defined by $\left(\mathcal{M}f\right)\left(\theta\right)=\frac{1}{\left|\mathbb{F}^{\times}\right|}\sum_{x\in\mathbb{F}^{\times}}f\left(x\right)\theta\left(x\right)$ . This is exactly the Fourier transform of $f$ with respect to the abelian group $\mathbb{F}^{\times}$ .

Given a function $f:\mathbb{F}\rightarrow\mathbb{C}$ , we can restrict it to $\mathbb{F}^{\times}$ and then take its Mellin transform. By abuse of
notation denote this as $\mathcal{M}\left(f\right)$ . A natural question to ask is what is the relation between $\mathcal{M}\left(f\right)$ and $\mathcal{M}\left(\mathcal{F}_{\psi}f\right)$ .

Example (Tate): The (continuous) characters on $\mathbb{R}^{\times}$ are of the form $x\mapsto\left|x\right|^{s}$ and $x\mapsto\left|x\right|^{s}\cdot\mathrm{sgn}x$ for $s\in\mathbb{C}$ . The Mellin transform of a function $f:\mathbb{R}\rightarrow\mathbb{C}$ is the function
$$\begin{aligned} \left(\mathcal{M}f\right)\left(\theta\right) & =\begin{cases} \int_{-\infty}^{\infty}f\left(x\right)\left|x\right|^{s}\frac{dx}{\left|x\right|} & \theta=\left|x\right|^{s},\\ \int_{-\infty}^{\infty}f\left(x\right)\left|x\right|^{s}\mathrm{sgn}x\frac{dx}{\left|x\right|} & \theta=\left|x\right|^{s}\mathrm{sgn}x \end{cases}.\end{aligned}$$
The Fourier transform of a function with respect to the character $\psi\left(x\right)=e^{-2\pi ix}$ is $\left(\mathcal{F}_{\psi}f\right)\left(y\right)=\int_{-\infty}^{\infty}f\left(x\right)e^{-2\pi ixy}dx$ . We have the following relation
$$\left(\mathcal{M}f\right)\left(\theta\right)=\gamma\left(\theta,\psi\right)^{-1}\left(\mathcal{M}\left(\mathcal{F}_{\psi}f\right)\right)\left(\hat{\theta}\right),$$
where $\hat{\theta}\left(x\right)=\frac{\left|x\right|}{\theta\left(x\right)}$ and $$\gamma\left(\theta,\psi\right)^{-1}=\begin{cases} 2^{1-s}\pi^{-s}\cos\left(\frac{\pi}{2}s\right)\Gamma\left(s\right) & \theta=\left|x\right|^{s},\\ 2^{1-s}\pi^{-s}\sin\left(\frac{\pi}{2}s\right)\Gamma\left(s\right)i & \theta=\left|x\right|^{s}\mathrm{sgn}x \end{cases}.$$

Theorem (Tate’s local functional equation analog): Denote for $f\in S\left(\mathbb{F}\right)$ and $\theta\in\widehat{\mathbb{F}^{\times}}$ , $$Z\left(f,\theta\right)=\sum_{x\in\mathbb{F}^{\times}}f\left(x\right)\theta\left(x\right)=\sqrt{\left|\mathbb{F}^{\times}\right|}\left(\mathcal{M}f\right)\left(\theta\right).$$
Then $$\frac{1}{\sqrt{\left|\mathbb{F}\right|}}f\left(0\right)\sum_{x\in\mathbb{F}^{\times}}\theta\left(x\right)+\gamma\left(\theta,\psi\right)Z\left(f,\theta\right)=Z\left(\mathcal{F}_{\psi}f,\theta^{-1}\right),$$ where $\gamma\left(\theta,\psi\right)=\frac{1}{\sqrt{\left|\mathbb{F}\right|}}\sum_{x\in\mathbb{F}^{\times}}\theta^{-1}\left(x\right)\psi\left(x\right)$ .

Proof: If $\theta=1$ then
$$\begin{aligned} Z\left(\mathcal{F}_{\psi}f,\theta^{-1}\right) & =\sum_{x\in\mathbb{F}^{\times}}\mathcal{F}_{\psi}f\left(x\right)\\ & =\frac{1}{\sqrt{\left|\mathbb{F}\right|}}\sum_{x\in\mathbb{F}^{\times}}\sum_{y\in\mathbb{F}}f\left(y\right)\psi\left(xy\right)\\ & =\frac{1}{\sqrt{\left|\mathbb{F}\right|}}\sum_{x\in\mathbb{F}^{\times}}\sum_{y\in\mathbb{F}^{\times}}f\left(y\right)\psi\left(xy\right)+\frac{1}{\sqrt{\left|\mathbb{F}\right|}}\sum_{x\in\mathbb{F}^{\times}}f\left(0\right)\cdot1\\ & =\frac{1}{\sqrt{\mathbb{F}}}\sum_{x\in\mathbb{F}^{\times}}\underbrace{\theta^{-1}\left(x\right)}_{=1}\psi\left(x\right)\sum_{y\in\mathbb{F}^{\times}}f\left(y\right)+\frac{f\left(0\right)}{\sqrt{\left|\mathbb{F}\right|}}\sum_{x\in\mathbb{F}^{\times}}\underbrace{\theta\left(x\right)}_{=1}\end{aligned}$$

If $\theta\ne1$ , then $\sum_{x\in\mathbb{F}^{\times}}\theta\left(x\right)=0$ .
We prove that $Z\left(f_{1},\theta\right)Z\left(\mathcal{F}_{\psi}f_{2},\theta^{-1}\right)=Z\left(f_{2},\theta\right)Z\left(\mathcal{F}_{\psi}f_{1},\theta^{-1}\right)$ , for every $f_{1},f_{2}$ . Then we choose a good substitution for $f_{2}$ .

$$\begin{aligned} Z\left(f_{1},\theta\right)Z\left(\mathcal{F}_{\psi}f_{2},\theta^{-1}\right) & =\sum_{x\in\mathbb{F}^{\times}}f_{1}\left(x\right)\theta\left(x\right)\sum_{y\in\mathbb{F}^{\times}}\mathcal{F}_{\psi}f_{2}\left(y\right)\theta\left(y^{-1}\right)\\ & =\frac{1}{\sqrt{\left|\mathbb{F}\right|}}\sum_{x\in\mathbb{F}^{\times}}\sum_{y\in\mathbb{F}^{\times}}\sum_{z\in\mathbb{F}}f_{1}\left(x\right)f_{2}\left(z\right)\theta\left(xy^{-1}\right)\psi\left(zy\right)\end{aligned}$$

If $z=0$ , we get a sum $\sum_{y\in\mathbb{F}^{\times}}\theta\left(xy^{-1}\right)=0$ , as $\theta^{-1}\ne1$ . Therefore we have

$$\begin{aligned} Z\left(f_{1},\theta\right)Z\left(\mathcal{F}_{\psi}f_{2},\theta^{-1}\right) & =\frac{1}{\sqrt{\left|\mathbb{F}\right|}}\sum_{x\in\mathbb{F}^{\times}}\sum_{y\in\mathbb{F}^{\times}}\sum_{z\in\mathbb{F}^{\times}}f_{1}\left(x\right)f_{2}\left(z\right)\theta\left(xy^{-1}\right)\psi\left(zy\right)\\ & =\frac{1}{\sqrt{\left|\mathbb{F}\right|}}\sum_{x\in\mathbb{F}^{\times}}\sum_{y\in\mathbb{F}^{\times}}\sum_{z\in\mathbb{F}^{\times}}f_{1}\left(x\right)f_{2}\left(z\right)\theta\left(xzy^{-1}\right)\psi\left(y\right).\end{aligned}$$

It is clear that the last sum is symmetric with respect to $f_{1},f_{2}$ , and therefore $$Z\left(f_{1},\theta\right)Z\left(\mathcal{F}_{\psi}f_{2},\theta^{-1}\right)=Z\left(f_{2},\theta\right)Z\left(\mathcal{F}_{\psi}f_{1},\theta^{-1}\right).$$

Now take $f_{2}=\delta_{1}$ the indicator function of $1$ , then $\left(\mathcal{F}_{\psi}f_{2}\right)\left(y\right)=\frac{1}{\sqrt{\left|\mathbb{F}\right|}}\psi\left(y\right)$ . Therefore we have $Z\left(f_{2},\theta\right)=1$ and $Z\left(\mathcal{F}_{\psi}f_{2},\theta^{-1}\right)=\frac{1}{\sqrt{\left|\mathbb{F}\right|}}\sum_{x\in\mathbb{F}^{\times}}\theta^{-1}\left(x\right)\psi\left(x\right)=\gamma\left(\theta,\psi\right)$ , i.e. we proved that for every $f\in S\left(\mathbb{F}\right)$ , $Z\left(f,\theta\right)\gamma\left(\theta,\psi\right)=Z\left(\mathcal{F}_{\psi}f,\theta^{-1}\right)$ . $\blacksquare$

For $\theta\ne1$ we have that $$\begin{aligned} \gamma\left(\theta,\psi\right)Z\left(f,\theta\right) & =Z\left(\mathcal{F}_{\psi}f,\theta^{-1}\right)\\ Z\left(f,\theta\right)=Z\left(\mathcal{F}_{\psi^{-1}}\mathcal{F}_{\psi}f,\theta\right) & =\gamma\left(\theta^{-1},\psi^{-1}\right)Z\left(\mathcal{F}_{\psi}f,\theta^{-1}\right)\\ & =\gamma\left(\theta^{-1},\psi^{-1}\right)\gamma\left(\theta,\psi\right)Z\left(f,\theta\right),\end{aligned}$$ and therefore $\gamma\left(\theta^{-1},\psi^{-1}\right)\gamma\left(\theta,\psi\right)=1$ . By definition $\overline{\gamma\left(\theta,\psi\right)}=\gamma\left(\theta^{-1},\psi^{-1}\right)$ , and therefore $\left|\gamma\left(\theta,\psi\right)\right|=1$ , i.e. $\sum_{x\in\mathbb{F}^{\times}}\theta^{-1}\left(x\right)\psi\left(x\right)$ has norm $\sqrt{\left|\mathbb{F}\right|}$ .

Quadratic reciprocity law

Let $q$ be an odd prime. Let $\mathbb{F}_{q}$ be a field with $q$ elements. A character $\theta_{q}:\mathbb{F}_{q}^{\times}\rightarrow\mathbb{C}^{\times}$ is a quadratic character if $\theta_{q}:\mathbb{F}_{q}^{\times}\rightarrow\left\{ \pm1\right\} $ . Such a non-trivial character exists and is unique: let $\xi$ be a generator of the cyclic group $\mathbb{F}_{q}^{\times}$ . Then $\theta:\mathbb{F}_{q}^{\times}\rightarrow\mathbb{C}^{\times}$ is determined by the image of $\xi$ . Therefore $\theta_{q}\left(\xi^{k}\right)=\left(-1\right)^{k}$ is the unique non-trivial quadratic character on $\mathbb{F}_{q}^{\times}$ . Furthermore, recall that for every $a\in\mathbb{F}_{q}^{\times}$ we have $a^{q-1}=1$ . Then $a^{\frac{q-1}{2}}\equiv\pm1$ . Therefore we have a character $\mathbb{F}_{q}^{\times}\rightarrow\left\{ \pm1\right\} \subseteq\mathbb{C}^{\times}$ by $a\mapsto a^{\frac{q-1}{2}}$ . Note that $\xi^{\frac{q-1}{2}}\ne1$ , as $\xi$ is a generator of the cyclic group, and therefore $\xi^{\frac{q-1}{2}}=-1$ , which implies that the above two characters agree, i.e. $\theta_{q}\left(a\right)\equiv a^{\frac{q-1}{2}}\left(\mod q\right)$ . Finally note that if $a=b^{2}$ , then $a^{\frac{q-1}{2}}=b^{q-1}=1$ , now $\theta_{q}\left(\xi^{k}\right)=1$ if $k$ is even (and then $\xi^{k}=\left(\xi^{\frac{k}{2}}\right)^{2}$ is a square), and $\theta_{q}\left(\xi^{k}\right)=-1$ if $k$ is odd (and then $\xi^{k}$ can’t be a square). We denote $\theta_{q}\left(a\right)=\left(\frac{a}{q}\right)$ the Legendre symbol.

Let $p,q$ be odd primes with $p\ne q$ . Let $\psi:\mathbb{F}_{q}\rightarrow\mathbb{C}^{\times}$ be a non-trivial additive character, and let $\theta_{q}:\mathbb{F}_{q}^{\times}\rightarrow\mathbb{C}^{\times}$ be a non trivial quadratic character. Then $\theta_{q}^{2}=1$ , which implies $\gamma\left(\theta_{q}^{-1},\psi^{-1}\right)=\gamma\left(\theta_{q},\psi^{-1}\right)=\theta_{q}\left(-1\right)\gamma\left(\theta_{q},\psi\right)$ . Denote $\tau=\sum_{x\in\mathbb{F}_{q}^{\times}}\theta_{q}^{-1}\left(x\right)\psi\left(x\right)$ , then $\tau^{2}=\theta_{q}\left(-1\right)\cdot q$ . Note that since $\gcd\left(p,q\right)=1$ , $$\sum_{x\in\mathbb{F}_{q}^{\times}}\theta_{q}^{-1}\left(x\right)\psi\left(px\right)=\theta_{q}\left(p\right)\sum_{x\in\mathbb{F}_{q}^{\times}}\theta_{q}^{-1}\left(x\right)\psi\left(x\right)=\theta_{q}\left(p\right)\tau.$$ Now $\tau\in\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]$ is an algebraic integer. We claim that the map $\mathbb{Z}/p\mathbb{Z}\rightarrow\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]/p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]$ is an inclusion: otherwise $j\in p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]$ for some $0 < j < p$ , which implies that $\frac{j}{p}$ is an algebraic integer, which is a contradiction.

Passing to the quotient $\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]/p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]$ we have that $\tau^{2}=\theta_{q}\left(-1\right)\cdot q$ implies that $\tau$ is invertible in the quotient, as $q$ and $\theta_{q}\left(-1\right)$ are invertible modulo $p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]$ . Next we consider

$$\begin{aligned} \tau^{p} & \equiv\sum_{x\in\mathbb{F}_{q}^{\times}}\theta_{q}^{-p}\left(x\right)\psi\left(px\right)\left(\mod p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]\right)\\ & =\sum_{x\in\mathbb{F}_{q}^{\times}}\theta_{q}^{-1}\left(x\right)\psi\left(px\right)\left(\mod p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]\right)\\ & =\theta_{q}\left(p\right)\tau\left(\mod p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]\right).\end{aligned}$$

Now $\tau^{p}=\tau\cdot\left(\tau^{2}\right)^{\frac{p-1}{2}}=\tau\cdot\theta_{q}\left(-1\right)^{\frac{p-1}{2}}\cdot q^{\frac{p-1}{2}}$ , and on the other hand $\tau^{p}=\theta_{q}\left(p\right)\tau\left(\mod p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]\right)$ , therefore modulo $p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]$ we get $\theta_{q}\left(p\right)\tau=\theta_{q}\left(-1\right)^{\frac{p-1}{2}}\cdot q^{\frac{p-1}{2}}\tau\left(\mod p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]\right)$ . Since $\tau$ is invertible modulo $p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]$ , we have $\theta_{q}\left(p\right)=\theta_{q}\left(-1\right)^{\frac{p-1}{2}}\cdot q^{\frac{p-1}{2}}\left(\mod p\mathbb{Z}\left[e^{\frac{2\pi i}{q}}\right]\right)$ .
Using the fact that $\left(\frac{q}{p}\right)=q^{\frac{p-1}{2}}\left(\mod p\right)$ and $\theta_{q}\left(a\right)=\left(\frac{a}{q}\right)$ , $\theta_{q}\left(-1\right)=\left(-1\right)^{\frac{q-1}{2}}$ , we get $$\left(\frac{p}{q}\right)=\left(-1\right)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\left(\frac{q}{p}\right),$$ which implies $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$ .