###### tags: 高斯和

# 二次高斯和 Quadratic Gauss sum (上)
- 先備知識：無(介紹)、基本數論(證明)
## 介紹

高中有學過 $e^{i\theta}=\cos\theta+i\sin\theta$，在複數平面上的座標為 $(\cos\theta,\sin\theta)$，落在單位圓上。因此對所有正整數 $n\geq 3$，我們有以下式子$$\sum_{k=0}^{n-1}e^{2\pi ki/n}=0$$其中 $e^{2\pi ki/n}$ 又被稱為 **n次單位根** (n-th root of unity)，因為其為 $x^n=1$ 的根且長度等於1。當 $k=1$ 時我們用 $\zeta_{n}$ 來代替，因此原式可以被替換成
$$\sum_{k=0}^{n-1}\zeta_{n}^{k}=0$$

一般來說，高斯和 (Gauss sum) 有更廣的定義 (牽涉到character theory)，但本文討論的高斯和是指二次高斯和 (Quadratic Gauss sum)，以下簡稱高斯和，僅限於討論$$g(n)=\sum_{k=0}^{n-1}\zeta_{n}^{k^{2}}$$
的值。美妙的是，當 $n$ 為正奇數時， $g(n)$ 有非常漂亮的結果。以下是我們接下來的目標：
1. 當 $n\geq 3$ 為質數 $p$ 時，找到 $g(p)$ 的公式 (上)
2. 當 $n\geq 3$ 為正奇數時，找到 $g(n)$ 的公式 (下)

## 猜測 (n=3,5,7)

### n=3
$\zeta_{3}=\cos(\frac{2\pi}{3})+i\sin(\frac{2\pi}{3})=\frac
{-1}{2}+\frac{\sqrt{3}}{2}i$ 滿足 $\zeta_{3}^{3}=1$，因此
$$g(3)=\zeta_{3}^{0^2}+\zeta_{3}^{1^2}+\zeta_{3}^{2^2}=1+2\zeta_{3}=i\sqrt{3} $$

### n=5
$\zeta_{5}=\cos(\frac{2\pi}{5})+i\sin(\frac{2\pi}{5})$ 滿足 $\zeta_{5}^{5}=1$，因此
$$g(5)=\zeta_{5}^{0^2}+\zeta_{5}^{1^2}+\zeta_{5}^{2^2}+\zeta_{5}^{3^2}+\zeta_{5}^{4^2}=1+2\zeta_{5}=1+2\zeta_{5}+2\zeta_{5}^4 $$令 $\alpha=\zeta_{5}+\zeta_{5}^{4}$, $\beta=\zeta_{5}^2+\zeta_{5}^3$，則
$$
\begin{cases}
\alpha+\beta=\sum_{k=1}^{4}\zeta_{5}^{k}=-1 \\
\alpha\beta=\zeta_{5}^{3}+\zeta_{5}^{4}+\zeta_{5}^{6}+\zeta_{5}^{7}=-1
\end{cases}
$$因此根據根與係數，$\alpha,\beta$ 是 $x^2+x-1=0$ 的根。利用公式解，解得 $\alpha=\frac{-1+\sqrt{5}}{2}$，$\beta=\frac{-1-\sqrt{5}}{2}$。因此 $g(5)=1+2\alpha=\sqrt{5}$。
### n=7
$\zeta_{7}=\cos(\frac{2\pi}{7})+i\sin(\frac{2\pi}{7})$ 滿足 $\zeta_{7}^{7}=1$，因此
$$g(7)=\zeta_{7}^{0}+\zeta_{7}^{1}+\zeta_{7}^{4}+\zeta_{7}^{9}+\zeta_{7}^{16}+\zeta_{7}^{25}+\zeta_{7}^{36}=1+2(\zeta_{7}+\zeta_{7}^{2}+\zeta_{7}^{4}) $$ 令 $\alpha=\zeta_{7}+\zeta_{7}^{2}+\zeta_{7}^{4}$, $\beta=\zeta_{7}^3+\zeta_{7}^{5}+\zeta_{7}^{6}$，則
$$
\begin{cases}
\alpha+\beta=\sum_{k=1}^{6}\zeta_{7}^{k}=-1 \\
\alpha\beta=\zeta_{7}^{4}+\zeta_{7}^{5}+\zeta_{7}^{7}+\zeta_{7}^{6}+\zeta_{7}^{7}+\zeta_{7}^{9}+\zeta_{7}^{7}+\zeta_{7}^{8}+\zeta_{7}^{10}=2
\end{cases}
$$因此根據根與係數，$\alpha,\beta$ 是 $x^2+x+2=0$ 的根。利用公式解，解得 $\alpha=\frac{-1+i\sqrt{7}}{2}$，$\beta=\frac{-1-i\sqrt{7}}{2}$。因此 $g(7)=1+2\alpha=i\sqrt{7}$。

根據規律，我們猜測 $g(n)$ 有以下公式：
$$g(n)=\sqrt{(-1)^{\frac{n-1}{2}}n}$$事實上該公式成立於對所有的正奇數 $n$，當 $n$ 是偶數顯然不合，因為 $(-1)^{1/4}$ 無意義。接下來我們將先證明該式成立於所有的奇質數，再推廣到一般的正奇數。

## 勒讓德符號 (Legendre symbol)
### Definition
> $p$ 為奇質數，$a$ 為整數，定義勒讓德符號為
$$\left(\dfrac{a}{p}\right)=
\begin{cases}
0, \mbox{ 若 }a\equiv 0 \mbox{ (mod $p$)}\\
1, \mbox{ 若 }a\not\equiv 0 \mbox{ (mod $p$) 且存在 } x \mbox{ 使得 }x^2\equiv a\mbox{ (mod $p$)}\\
-1, \mbox{ 若不存在 }x\mbox{ 使得 } x^2\equiv a\mbox{ (mod $p$)}
\end{cases}
$$

### Properties
> 1. 若 $a\equiv b$ (mod $p$)，則 $(\frac{a}{p})=(\frac{b}{p})$
> 2. $(\frac{a^2}{p})=1$
> 3. $(\frac{a}{p})\equiv a^{\frac{p-1}{2}}$ (mod $p$)
> 4. $(\frac{a}{p})(\frac{b}{p})=(\frac{ab}{p})$

### Lemma
> 1. $\sum_{a=0}^{p-1}(\frac{a}{p})=0$
> 2. $g(n)=\sum_{a=0}^{p-1}(\frac{a}{p})\zeta_{p}^{a}$

## 證明 (n為奇質數)
從以下開始，$p$ 是奇質數，$\zeta=\zeta_{p}$。
### Lemma 1
> 當 $a\equiv0$ (mod $p$)，$\sum_{k=0}^{p-1}\zeta^{ka}=p$，否則 $\sum_{k=0}^{p-1}\zeta^{ka}=0$.
#### 證明
> 當 $a\equiv0$ (mod $p$)，結果顯然。否則，$\sum_{k=0}^{p-1}\zeta^{ka}=(\zeta^{pa}-1)/(\zeta^a-1)=0$。
### Corollary 1
> $p^{-1}\sum_{a=0}^{p-1}\zeta^{a(x-y)}=\delta(x,y)$, 其中 $\delta(x,y)=1$ 當 $x\equiv y$ (mod $p$)，否則 $=0$。

接下來，我們定義更廣義的高斯和。
### Definition
> a為正整數，定義高斯和 $$g(a,p)=\sum_{k=0}^{p-1}\zeta^{ak^2}$$根據上一章的properties 4，我們同樣可以定義
>> $$g(a,p)=\sum_{k=1}^{p-1}\left(\dfrac{k}{p}\right)\zeta^{ak}$$

### Proposition 2
> $g(a,p)=(\frac{a}{p})g(1,p)$
#### 證明
> 當 $a\equiv0$ (mod $p$)，左式=右式=0。當$a\not\equiv0$ (mod $p$)，
> $$\left(\frac{a}{p}\right)g(a,p)=\sum_{k=1}^{p-1}\left(\frac{ak}{p}\right)\zeta^{ak}=\sum_{x=1}^{p-1}\left(\frac{x}{p}\right)\zeta^{x}=g(1,p)$$中間的等號來自於變數變換 $x=ak$，因為 $p\nmid a$，所以 $k=1,...,p-1$ 送到的 $x$ 也會在 mod $p$ 後變成不同的 $p-1$ 個等價類，且勒讓德符號和 $\zeta^{x}$ 在 mod $p$ 下擁有相同的值。最後兩邊乘以$(\frac{a}{p})$，因為 $p\nmid a$，$(\frac{a}{p})^2=1$，證畢。

下一個定理描述了高斯和的絕對值，但這還不足以證明我們的猜想，實際上高斯花了更多的時間在證明高斯和的「正負號」。
### Theorem 3
> $g(1,p)^2=(-1)^{(p-1)/2}p$
#### 證明
> 證明的想法是用兩種不同的方法計算 $S=\sum_{a=1}^{p-1} g(a,p)g(-a,p)$。首先，當 $a=1,...,p-1$，$$g(a,p)g(-a,p)=\left(\frac{a}{p}\right)\left(\frac{-a}{p}\right)g(1,p)^2=\left(\frac{-1}{p}\right)g(1,p)^2$$故 $S=(\frac{-1}{p})(p-1)g(1,p)^2$。另一方面，注意到$$g(a,p)g(-a,p)=\sum_{x=1}^{p-1}\sum_{y=1}^{p-1}\left(\frac{x}{p}\right)\left(\frac{y}{p}\right)\zeta^{a(x-y)}$$根據 Corollary 1，得到 $$S=\sum_{x}\sum_{y}\left(\frac{x}{p}\right)\left(\frac{y}{p}\right) \left[\sum_{a}\zeta^{a(x-y)}\right]=p\sum_{x}\sum_{y}\left(\frac{x}{p}\right)\left(\frac{y}{p}\right)\delta(x,y)$$因為 $x,y$ 都是從 $1$ 到 $p-1$，故 $\delta(x,y)=1\Leftrightarrow x=y$。故$$\left(\frac{-1}{p}\right)(p-1)g(1,p)^2=S=p\sum_{x=y}\left(\frac{x}{p}\right)\left(\frac{x}{p}\right)=p(p-1)$$又 $(\frac{-1}{p})\equiv (-1)^{(p-1)/2}$ (mod $p$)，因為右式只能是$\pm 1$，因此 $(\frac{-1}{p})= (-1)^{(p-1)/2}$，證畢。

根據 Theorem 3，我們得到 $g(p)=\pm\sqrt{(-1)^{(p-1)/2}p}$ 。接下來將證明高斯和的正負號，為此需要做很多的準備。
### Lemma 3
> $1+x+...+x^{p-1}$ 在 $\mathbb{Q}[x]$ 中不可約，即不存在有理係數多項式 $h(x),k(x)$ 使得 $1+x+...+x^{p-1}=h(x)k(x)$。
#### 證明
> 令 $f(x-1)=1+x+...+x^{p-1}$，則$f(x)=\frac{(x+1)^p-1}{(x+1)-1}=x^{p-1}+...+\binom{p}{2}x+p$。注意到 $f(x-1)$ 不可約若且唯若 $f(x)$ 不可約，因此我們只需證明 $f(x)$ 不可約。根據 $\binom{n}{k}$ 的定義，對所有 $k\geq 1$，$\binom{p}{k}$ 的分子包含質數 $p$，但分母並沒辦法把 $p$ 消去，故 $p|\binom{p}{k}$，因此 $f(x)$ 除了領導項的係數均是 $p$ 的倍數，且常數項不是 $p^2$ 的倍數。因此根據[艾森斯坦判別法](https://zh.wikipedia.org/wiki/%E8%89%BE%E6%A3%AE%E6%96%AF%E5%9D%A6%E5%88%A4%E5%88%A5%E6%B3%95)，$f(x)$不可約。
### Lemma 4
> $\prod_{k=1}^{(p-1)/2}(\zeta^{2k-1}-\zeta^{-(2k-1)})^2=(-1)^{(p-1)/2}p$
#### 證明
> 因為 $x^p-1=(x-1)\prod_{j=1}^{p-1}(x-\zeta^{j})$，兩邊除以 $(x-1)$ 後用 $x=1$ 代入，得到 $p=\prod_{j=1}^{p-1}(1-\zeta^{j})$。如同 Proposition 2 的證明中的說明，注意到該乘積可以是 $p-1$ 個元素的集合，且該集合 mod $p$ 後和 $\{1,2,...,p-1\}$ 相同。不難看出 $S=\{\pm(4k-2): k=1,2,...,(p-1)/2\}$ 滿足條件。因此
> \begin{align*}
> p&=\prod_{j\in S}(1-\zeta^{j})=\prod_{k=1}^{(p-1)/2}(1-\zeta^{4k-2})\prod_{k=1}^{(p-1)/2}(1-\zeta^{-(4k-2)})\\
> &=\prod_{k=1}^{(p-1)/2}(\zeta^{-(2k-1)}-\zeta^{2k-1})\prod_{k=1}^{(p-1)/2}(\zeta^{2k-1}-\zeta^{-(2k-1)})\\
> &=(-1)^{(p-1)/2}\prod_{k=1}^{(p-1)/2}(\zeta^{2k-1}-\zeta^{-(2k-1)})^2
> \end{align*}兩邊同乘以 $(-1)^{(p-1)/2}$，因為 $p$ 是奇質數，因此 $(-1)^{p-1}=1$，證畢。

### Proposition 5
> $\prod_{k=1}^{(p-1)/2}(\zeta^{2k-1}-\zeta^{-(2k-1)})=\sqrt{(-1)^{(p-1)/2}p}$
#### 證明
>根據上一個 Lemma，我們得知左式 $=\pm$ 右式。不難看出 $$左式=i^{(p-1)/2}\prod_{k=1}^{(p-1)/2}2\sin\frac{(4k-2)\pi}{p}$$注意到$$\sin\frac{(4k-2)\pi}{p}<0\Leftrightarrow \frac{p+2}{4}<k\leq\frac{p-1}{2}$$
當 $p\equiv 1$ (mod $4$) 時，得到 $\frac{p+3}{4}\leq k\leq \frac{p-1}{2}$。因此共有 $\frac{p-1}{2}-\frac{p-1}{4}=\frac{p-1}{4}$ 個負號在該乘積裡。令 $p=4n+1$，若 $n$ 是偶數，則 $i^{(p-1)/2}=(-1)^n=1$ 以及偶數 ($n$) 個負號，故左式為正，顯然右式 $=\sqrt{p}$，得證；若 $n$ 是奇數，則 $i^{(p-1)/2}=(-1)^n=-1$ 以及奇數 ($n$) 個負號，故左式同樣為正，右式同樣 $=\sqrt{p}$，得證。當 $p\equiv 3$ (mod $4$) 時做類似的討論。

### Theorem 6
> $g(p)=\prod_{k=1}^{(p-1)/2}(\zeta^{2k-1}-\zeta^{-(2k-1)})$
#### 證明
> 已知 $g(p)^2=\prod_{k=1}^{(p-1)/2}(\zeta^{2k-1}-\zeta^{-(2k-1)})^2$，故 $g(p)=\varepsilon\prod_{k=1}^{(p-1)/2}(\zeta^{2k-1}-\zeta^{-(2k-1)})$，其中 $\varepsilon=\pm 1$。考慮$$f(x)=\sum_{j=1}^{p-1}\left(\frac{j}{p}\right)x^j-\varepsilon\prod_{k=1}^{(p-1)/2}(x^{2k-1}-x^{p-(2k-1)})$$則 $f(x)$ 有以下性質：
> 1. $f(x)$ 是整係數多項式
> 2. $f(\zeta)=0$，因為 $\sum_{j=1}^{p-1}\left(\frac{j}{p}\right)\zeta^j=g(p)$
> 3. $f(1)=0$，因為 $\sum_{j=1}^{p-1}\left(\frac{j}{p}\right)=0$
>根據上述 + Lemma 3，得到 $(1+x+...+x^{p-1})\,|\,f(x)$ 和 $(x-1)\,|\, f(x)$，因此存在整係數多項式 $h(x)$ 使得 $f(x)=(x^p-1)h(x)$。令 $x=e^z$ 代回原式，得到
>$$(e^{pz}-1)h(e^z)=f(e^z)=\sum_{j=1}^{p-1}\left(\frac{j}{p}\right)e^{jz}-\varepsilon\prod_{k=1}^{(p-1)/2}(e^{(2k-1)z}-e^{(p-(2k-1))z})$$因為 $e^x=\sum_{k=0}^{\infty}\frac{x^k}{k!}$ 在 $x^k$ 的係數為 $1/k!$，我們比較兩邊泰勒展開後在 $z^{(p-1)/2}$ 的係數：
右式在 $z^{(p-1)/2}$ 的係數等於 $\sum_{j=1}^{p-1}(\frac{j}{p})\frac{j^{(p-1)/2}}{(\frac{p-1}{2})!}-\varepsilon\prod_{k=1}^{(p-1)/2}(4k-p-2)$
>>說明：顯然 $\sum_{j=1}^{p-1}\left(\frac{j}{p}\right)e^{jz}$ 在 $z^{(p-1)/2}$ 的係數是 $\sum_{j=1}^{p-1}(\frac{j}{p})\frac{j^{(p-1)/2}}{(\frac{p-1}{2})!}$，另一項是$\frac{p-1}{2}$個乘積，且每一項都是無窮多項式，因此要求在 $z^{(p-1)/2}$ 的係數，要嘛就是每一項都找 $z^1$ 的係數再乘起來，要嘛就是會有一項找到 $z^0$ 的係數。然而 $(e^{(2k-1)z}-e^{(p-(2k-1))z})$ 泰勒展開後的常數項等於 $0$，因此所求的係數只能是求每一項在 $z^1$ 的係數再乘起來，而 $(e^{(2k-1)z}-e^{(p-(2k-1))z})$ 在 $z^1$ 的係數為
>>$\frac{(2k-1)^1}{1!}-\frac{(p-2k+1)^1}{1!}=(4k-p-2)$，證畢。
>
>左式在 $z^{(p-1)/2}$ 的係數為 $\frac{pA}{B}$，其中 $A,B\in\mathbb{Z}$ 且 $p\nmid B$。
>>說明：令 $e^{pz}-1=\sum_{i} a_{i}z^i$ 和 $h(e^z)=\sum_{j} b_{j}z^j$，則所求之係數等於 $a_{\frac{p-1}{2}}b_{1}+...+a_{1}b_{\frac{p-3}{2}}+a_{0}b_{\frac{p-1}{2}}$。不難看出：$a_{0}=0$、$p\,|\,a_{i}$ 對所有 $i\geq 1$，即 $a_{i}=\frac{pA}{B}$ 且 $p\nmid B$。因為 $h(x)$ 是整係數多項式，故 $b_{i}\in\mathbb{Q}$ 的分母不會是 $p$ 的倍數，因此 $a_{\frac{p-1}{2}}b_{1}+...+a_{1}b_{\frac{p-3}{2}}+a_{0}b_{\frac{p-1}{2}}$ 依舊是 $\frac{pA}{B}$ 且 $p\nmid B$ 的形式。
>
>綜上討論，我們有$$\frac{pA}{B}=\sum_{j=1}^{p-1}\left(\frac{j}{p}\right)\frac{j^{(p-1)/2}}{(\frac{p-1}{2})!}-\varepsilon\prod_{k=1}^{(p-1)/2}(4k-p-2)$$兩邊同乘以 $B(\frac{p-1}{2})!$ 再 mod $p$，我們得到
>\begin{align*}\sum_{j=1}^{p-1}\left(\frac{j}{p}\right)j^{\frac{p-1}{2}}&\equiv\varepsilon \left(\frac{p-1}{2}\right)!\prod_{k=1}^{(p-1)/2}(4k-2)\,\,\,\,\,\,\mbox{ (mod $p$)}\\
>&\equiv\varepsilon \left[\left(\frac{p-1}{2}\right)!\,\cdot 2^{\frac{p-1}{2}}\right]\prod_{k=1}^{(p-1)/2}(2k-1)\,\,\,\,\,\,\mbox{ (mod $p$)}\\
>&\equiv\varepsilon \,(2\cdot 4\cdots (p-1))(1\cdot 3\cdots (p-2))\,\,\,\,\,\,\mbox{ (mod $p$)}\\
>&\equiv\varepsilon \,(p-1)!\,\,\,\,\,\,\mbox{ (mod $p$)}\\
>&\equiv -\varepsilon\,\,\,\,\,\,\mbox{ (mod $p$)}
>\end{align*}最後一個等號是利用[威爾遜定理](https://en.wikipedia.org/wiki/Wilson%27s_theorem)。利用上一章的 Properties ，左式在 mod $p$ 下會等於 $\sum_{j=1}^{p-1}(\frac{j}{p})(\frac{j}{p})\equiv p-1\equiv -1$ (mod $p$)，因此 $\varepsilon\equiv 1$ (mod $p$)。因為 $\varepsilon=\pm 1$，得到 $\varepsilon=1$，帶回原式故得證。

最後，根據 Theorem 6 和 Proposition 5，得到
$$g(p)=\prod_{k=1}^{(p-1)/2}(\zeta^{2k-1}-\zeta^{-(2k-1)})=\sqrt{(-1)^{(p-1)/2}p}$$得證我們的猜想在 $n$ 是質數的情況下是正確的。