Prove that : $$\sum _{x=0}^{p-1}e^{\frac {2\pi ix^{2}}{p}}={\begin{cases}{\sqrt {p}}&{\text{if}}\ p\equiv 1{\pmod {4}}\\i{\sqrt {p}}&{\text{if}}\ p\equiv 3{\pmod {4}}\end{cases}}$$ where $p$ is a prime number
Can someone give me hints for this, I am completely stuck in this problem. This was given in my roots of unity handout.
I first, took $S=\sum _{x=0}^{p-1}e^{\frac {2\pi ix^{2}}{p}}$.
The handout asked me to prove $|S|=\sqrt p$, but I am not able to proceed.
Thanks in advance!
On
Oh boy! This made me struggle a bit XD. All I could do, was to prove $|S|=\sqrt{p}$ as the handout suggests you to!
First of all, lets re-write the sum $S$. We will denote $\zeta := e^{2\pi i/p}$ and $(a|p)$ denotes the Legendre symbol which is defined as $$(a|p):=\begin{cases}1 & \text{if $a$ is a quadratic residue $\pmod{p}$}\\-1 & \text{if $a$ is a quadratic non residue $\pmod{p}$}\\0 &\text{if $p|a$}\end{cases}$$
We claim that $$S:=\sum_{x=0}^{p-1}\zeta^{x^2}=\sum_{x=0}^{p-1}(x|p)\zeta^{x}$$
The above claim is obviously gonna help us to deal with the $x^2$ in the exponent. For the proof of the claim, we note that we have $$\sum_{x=0}^{p-1}\zeta^x=0\tag*{(sum of all $p^{th}$ roots of unity is $0$)}$$ \begin{align}\implies &1+\sum_{\substack{x=1\\(x|p)=1}}^{p-1}\zeta^x +\sum_{\substack{x=1\\(x|p)=-1}}^{p-1}\zeta^x=0\\\implies & 1+\sum_{\substack{x=1\\(x|p)=1}}^{p-1}\zeta^x=\sum_{\substack{x=1\\(x|p)=-1}}^{p-1}-\zeta^x\\ \implies & 1 +2\sum_{\substack{x=1\\(x|p)=1}}^{p-1}\zeta^x = \sum_{\substack{x=1\\(x|p)=1}}^{p-1}\zeta^x+\sum_{\substack{x=1\\(x|p)=-1}}^{p-1}-\zeta^x = \sum_{x=0}^{p-1}(x|p)\zeta^x\tag*{(1)}\\\end{align}and as number of quadratic residues is $(p-1)/2$, we get, $$1+2\sum_{\substack{x=1\\(x|p)=1}}^{p-1}\zeta^x = 1+ \sum_{x=1}^{p-1}\zeta^{x^2}=\sum_{x=0}^{p-1}\zeta^{x^2}$$and thus, from $(1)$, we complete the proof of our claim.
Now, to show $|S|=\sqrt{p}$, we first investigate $S^2$. For that, note that, $$(-1|p)\sum_{x=0}^{p-1}(x|p)\zeta^{x}=\sum_{x=0}^{p-1}(x|p)\zeta^{-x}$$and so,$$\begin{align} (-1|p)S^2&= \left(\sum_{n=0}^{p-1}(n|p)\zeta^{n}\right)\left(\sum_{m=0}^{p-1}(m|p)\zeta^{-m}\right)\\ &=\sum_{n=0}^{p-1}\sum_{m=0}^{p-1} (n|p)(m|p)\zeta^{n-m}\\ &=\sum_{n=0}^{p-1}\sum_{m=0}^{p-1} (mn|p)\zeta^{n-m}\\ & =\sum_{d=0}^{p-1}\zeta^d \sum_{n=0}^{p-1}(n(n+d)|p) \end{align}$$and clearly, if $d\neq 0$, then the inner sum is just $-1$ and when $d=0$, the inner sum is $p-1$. Thus, $$(-1|p)S^2=(p-1)-\sum_{l=1}^{p-1}\zeta^l=p\implies S^2=(-1|p)p=(-1)^{(p-1)/2}p$$and thus, $$\boxed{\left(\sum_{x=0}^{p-1}e^{\frac{2\pi i x^2}{p}}\right)^2=\begin{cases}p &\text{if $p\equiv_4 1$}\\ -p &\text{if $p\equiv_4 3$}\end{cases}}\tag*{$\blacksquare$}$$
The following proof uses counting techniques, read with care. You won't need any knowledge about matrix eigenvalues.
Proof: The proof will proceed by counting the number of solutions $(x,y)\in(\mathbb{Z}/p\mathbb{Z})^2$ of the congruence $$x^2-y^2\equiv a\pmod{p}$$ If $p\mid a$ then we have to count the number of solutions to $x^2-y^2\equiv0\pmod{p}$ which is equivalent to $(x+y)(x-y)\equiv0\pmod{p}$. The solutions are given by $(x,x)$ and $(x,-x)$ where $x$ varies over $\mathbb{Z}/p\mathbb{Z}$. Since $(0,0)$ is counted twice and for $x\neq0$, $x\not\equiv_p -x$ we have total $2p-1$ solutions. Now if $a\neq0$ then it's equivalent to $(x+y)(x-y)\equiv a\pmod{p}$. Let $u=(x+y)$ and $v=(x-y)$. Then the solutions to the given congruence are in bijective correspondence with $uv\equiv a\pmod{p}$ as $p$ is an odd prime and the correspondence is given by $(u,v)\rightarrow(\frac{u+v}{2},\frac{u-v}{2})$. Since $\gcd(p,a)=1$ therefore for each $u\in(\mathbb{Z}/p\mathbb{Z})^*$ $\exists!$ $v\in(\mathbb{Z}/p\mathbb{Z})^*$ such that $uv\equiv a\pmod{p}$. Hence there are $p-1$ solutions in this case. Now we count the number of solutions in another way. We know that if $b$ is a quadratic residue modulo $p$ then $\exists$ $x\in(\mathbb{Z}/p\mathbb{Z})^*$ such that $b\equiv x^2\pmod{p}$. In fact there are two incongruent solutions modulo $p$ and they are $x$ and $p-x$. if $b$ is a quadratic non-residue modulo $p$ then there are no solutions. Hence the number of solutions to the congruence $x^2\equiv b\pmod{p}$ in $(\mathbb{Z}/p\mathbb{Z})^*$ is exactly $1+\left(\frac{b}{p}\right)$. Hence for fixed $y$ the number of solutions to $x^2\equiv a+y^2\pmod{p}$ is $1+\left(\frac{a+y^2}{p}\right)$. Hence summing over $y$ we get the number of solutions to be $p+\sum_{y=0}^{p-1}\left(\frac{a+y^2}{p}\right)$. Hence comparing two counts we are done!
Proof: For any $a$ in $\mathbb{Z}/p\mathbb{Z}$ we have, as before, the number of solutions to the congruence $$x^2+y^2\equiv a\pmod{p}$$ is given by $$p+\sum_{y=0}^{p-1}\left(\frac{a-y^2}{p}\right)$$ Now by claim 1, $$\sum_{y=0}^{p-1}\left(\frac{a-y^2}{p}\right)=\left(\frac{-1}{p}\right)\sum_{y=0}^{p-1}\left(\frac{y^2-a}{p}\right)=\begin{cases} \left(\frac{-1}{p}\right)(p-1)\quad\text{when $p\mid a$}\\ \\ \left(\frac{-1}{p}\right)(-1)\quad\text{otherwise} \end{cases}$$
Since $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$ we are done!
Proof: By definition of $\mathcal{G}$ we have $$\mathcal{G}^2=\sum_{x=0}^{p-1}\sum_{y=0}^{p-1}\omega_p^{(x^2+y^2)}$$ By claim 2 we get $$\mathcal{G}^2=p+(p-1)(-1)^{\frac{p-1}{2}}+(p-(-1)^{\frac{p-1}{2}})(\omega_p^{p-1}+\omega_p^{p-2}+\ldots+\omega_p)$$ Since $\omega_p$ is a root of $\Phi_p(X)$ we have $\omega_p^{p-1}+\omega_p^{p-2}+\ldots+\omega_p=-1$. Hence we get $$\mathcal{G}^2=p+(p-1)(-1)^{\frac{p-1}{2}}-(p-(-1)^{\frac{p-1}{2}})=(-1)^{\frac{p-1}{2}}p$$
Hence it's clear that $|\mathcal{G}|=\sqrt{p}$.
To prove the following, we need more work. $$\mathcal{G}=\begin{cases} \sqrt{p}\quad\;\;\,\text{if $p\equiv1\pmod{4}$}\\ i\sqrt{p}\quad\text{if $p\equiv3\pmod{4}$} \end{cases}$$ where $i^2=-1$.
Remark: The complex number $\mathcal{G}$ is known as quadratic Gauss sum.
Proof: It is well known that $$(1-\omega_p)(1-\omega_p^2)\cdots(1-\omega_p^{\frac{p-1}{2}})=p$$ The integers $\pm(4k-2)$ represents all non-zero residue classes modulo $p$ for $k\in\{1,2,\ldots,(p-1)/2\}$. Therefore we get,
$$p=\prod_{j=1}^{p-1}(1-\omega_p^j)=\prod_{j=1}^{\frac{p-1}{2}}(1-\omega_p^{4j-2})\prod_{j=1}^{\frac{p-1}{2}}(1-\omega_p^{-(4j-2)})\\=\prod_{j=1}^{\frac{p-1}{2}}\left(\omega_p^{-(2j-1)}-\omega_p^{2j-1)}\right)\prod_{j=1}^{\frac{p-1}{2}}\left(\omega_p^{2j-1}-\omega_p^{-(2j-1)}\right)\\=(-1)^{\frac{p-1}{2}}\prod_{j=1}^{\frac{p-1}{2}}\left(\omega_p^{2j-1}-\omega_p^{-(2j-1)}\right)$$ Hence the claim follows.
Proof: By claim 4, it's enough to compute the sign of the following quantity $$i^{\frac{p-1}{2}}\prod_{j=1}^{\frac{p-1}{2}}2\sin\frac{(4j-2)\pi}{p}$$ Observe that $$\sin\frac{(4j-2)\pi}{p}$$ when $\frac{p+2}{4}<j\leq\frac{p-1}{2}$. This implies that the product has exactly $\frac{p-1}{2}-\left\lfloor\frac{p+2}{4}\right\rfloor$ negative terms and you can easily verify that $$\frac{p-1}{2}-\left\lfloor\frac{p+2}{4}\right\rfloor=\begin{cases}\frac{p-1}{4}\quad\text{if $p\equiv1\pmod{4}$}\\\frac{p-3}{4}\quad\text{if $p\equiv3\pmod{4}$}\end{cases}$$ Hence the claim follows.
Now let $\varepsilon$ be the sign of the quadratic Gauss sum. Then from the two claims above we have $$\mathcal{G}=\varepsilon\prod_{j=1}^{\frac{p-1}{2}}\left(\omega_p^{2j-1}-\omega_p^{-(2j-1)}\right)\tag{1}$$
Proof:(due to Kronecker) Consider the polynomial $$\Psi(x)=\prod_{j=1}^{\frac{p-1}{2}}\left(\frac{j}{p}\right)x^j-\varepsilon\prod_{j=1}^{\frac{p-1}{2}}\left(x^{2j-1}-x^{-(2j-1)}\right)\tag{2}$$ Therefore $\Psi(\omega_p)=0$ by $(1)$. Since $\sum_{j=1}^{p-1}\left(\frac{j}{p}\right)=0$, we have $\Psi(1)=0$. Since $x-1$ and $\Phi_p(x)$ are relatively prime polynomials, we have $(x^p-1)\mid\Psi(x)$. Let $\Psi(x)=(x^p-1)f(x)$. Replacing $x$ by $e^t$ we get the following identity $$\prod_{j=1}^{p-1}\left(\frac{j}{p}\right)e^{jt}-\varepsilon\prod_{j=1}^{\frac{p-1}{2}}\left(e^{t(2j-1)}-e^{-t(2j-1)}\right)=(e^{tp}-1)f(e^t)$$ The coefficient of $t^{\frac{p-1}{2}}$ on the left hand side is $$\frac{\prod_{j=1}^{p-1}\left(\frac{j}{p}\right)j^{\frac{p-1}{2}}}{((p-1)/2)!}-\varepsilon\prod_{j=1}^{\frac{p-1}{2}}(4j-p-2)$$ and the coefficient of $t^{\frac{p-1}{2}}$ on the right side is $p\frac{m}{n}$ for some integers $m,n$ such that $p\nmid n$. Equating coefficients, multiplying by $n((p-1)/2)!$ and reducing modulo $p$ we get, $$\prod_{j=1}^{p-1}\left(\frac{j}{p}\right)j^{\frac{p-1}{2}}\equiv_p\varepsilon\left(\frac{p-1}{2}\right)!\prod_{j=1}^{\frac{p-1}{2}}(4j-2)\\\equiv_p\varepsilon(2\cdot4\cdots(p-1))\prod_{j=1}^{\frac{p-1}{2}}(2j-1)\\\equiv_p\varepsilon(p-1)!\\\equiv_p-\varepsilon$$ The last step follows from Wilson's theorem. Now from Euler's criterion, we know that $$j^{\frac{p-1}{2}}\equiv_p\left(\frac{j}{p}\right)$$ Hence we get $$\sum_{j=1}^{p-1}\left(\frac{j}{p}\right)^2\equiv_p(p-1)\equiv_p-\varepsilon\\\implies\varepsilon\equiv1\pmod{p}$$ Since $\varepsilon=\pm1$ and $p$ is an odd prime we must have $\varepsilon=1$. This completes the proof. $$\tag*{$\blacksquare$}$$