###### tags: 高斯和

# 二次高斯和 Quadratic Gauss sum (下)

- 先備知識：[二次高斯和 Quadratic Gauss sum (上)](https://hackmd.io/@5aUqcH0AS2yowIphs8Q2Kw/rJ332XC_Jx)
## 複習

二次高斯和，以下簡稱高斯和，定義為$$g(n)=\sum_{k=0}^{n-1}\zeta_{n}^{k^2}$$其中 $\zeta_{n}=e^{\frac{2\pi i}{n}}$ 是 $n$ 次單位根。利用勒讓得符號 (Legendre symbol)，在 $n$ 是質數 $p$ 的情況下，也可以將高斯和寫成$$g(p)=\sum_{k=1}^{p-1}\left(\frac{k}{p}\right)\zeta_{p}^{k}$$

我們的最終目標是證明：對所有正奇數 $n$，$$g(n)=\sqrt{(-1)^{\frac{n-1}{2}}n}$$而我們在上文已經證明了 $n$ 是質數 $p$ 的情況，本文要處理一般奇數 $n$ 的情況，換句話說，將 $n$ 做質因數分解後得到 $p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}$，則每一個 $p_{i}$ 都是奇質數。

## 證明 (n為正奇數)

### Definition
> 給定整數 $a$ 和正奇數 $n$，假設 $(a,n)=1$，定義二次高斯和為$$g(a,n)=\sum_{k=0}^{n-1}\zeta_{n}^{ak^2}$$定義 $g(a,1)=1$。

當 $n$ 是質數時，該定義和上一篇提及的定義相同。

### Proposition
> 給定整數 $a$ 和正奇數 $m,n$，若 $(m,n)=(a,mn)=1$，則 $g(a,mn)=g(am,n)\cdot g(an,m)$
#### 證明
> 已知 $g(a,mn)=\sum_{k=0}^{mn-1}\zeta_{mn}^{ak^2}=\sum_{k=0}^{mn-1}e^{\frac{2ak^2 \pi i}{mn}}$，因為 $\zeta_{mn}^mn=1$ 且 $(a,mn)=1$，故我們可以選取一個有 $mn$ 個元素的集合 $S$，該集合在 mod $mn$ 下會等於集合 $T=\{0,1,2,...,mn-1\}$，則 $aS^2\equiv aT^2$ (mod $mn$)，其中$aS^2:=\{ak^2\,|\, k\in S\}$，因此我們有
> $$\sum_{k\in S}\zeta_{mn}^{ak^2}=\sum_{k=0}^{mn-1}\zeta_{mn}^{ak^2}$$
> 不難看出集合 $S=\{sm+tn\,|\,0\leq s\leq m-1,\,0\leq t\leq n-1\}$ 滿足性質。
>> 說明：因為 $S$ 剛好有 $mn$ 個元素，因此只須證明不存在兩個相異落在 $S$ 的元素使得 mod $mn$ 下是一樣的。假設存在，令兩個相異元素為 $sm+tn,s'm+t'n$，其中 $0\leq s,s'\leq m-1$，$0\leq t,t'\leq n-1$。則$$(s-s')m+(t-t')n\equiv 0 \,\,\mbox{ (mod $mn$) }\Rightarrow mn\,|\,(s-s')m+(t-t')n$$特別地，$m\,|\,(s-s')m+(t-t')n$ 推得 $m\,|\,(t-t')$，利用 $(m,n)=1$。然而 $-(m-1)\leq t-t'\leq m-1$，因此 $t-t'=0$，得到 $$mn\,|\,(s-s')m\Rightarrow n|(s-s')m\Rightarrow n|(s-s')$$同樣的討論得到 $s=s'$，但這和 $sm+tn,s'm+t'n$ 相異矛盾，得證。
>
> 因此\begin{align*}g(a,mn)&=\sum_{s=0}^{m-1}\sum_{t=0}^{n-1}\zeta_{mn}^{a(sm+tn)^2}=\sum_{s=0}^{m-1}\sum_{t=0}^{n-1}\zeta_{mn}^{as^2m^2}\zeta_{mn}^{2astmn}\zeta_{mn}^{at^2n^2}\\
> &=\sum_{s=0}^{m-1}\sum_{t=0}^{n-1}\zeta_{n}^{as^2m}\cdot 1\cdot\zeta_{m}^{at^2n}=\left(\sum_{s=0}^{m-1}\zeta_{n}^{as^2m}\right)\left(\sum_{t=0}^{n-1}\zeta_{m}^{at^2n}\right)\\
> &=g(am,n)\cdot g(an,m)
> \end{align*}
>
對上面的 Proposition 用數學歸納法後，可以得到以下的 Corollary：
### Corollary
>若 $n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}$ 為 正奇數 $n$ 的質因數分解，則$$g(1,n)=\prod_{i=1}^{k}g\left(\frac{n}{p_{i}^{r_{i}}},\,p_{i}^{r_{i}}\right)$$
### Proposition
> 給定整數 $a$ 和與其互質之質數 $p$ 和整數 $m\geq 2$，則 $g(a,p^m)=p\cdot g(a,p^{m-2})$
#### 證明
> 已知 $g(a,p^m)=\sum_{k=1}^{p^{m}}\zeta_{p^m}^{ak^2}$，考慮將 $k=1,...,p^m$ 排列成 $p\times p^{m-1}$ 的長方形，不難看出每一個 $k$ 可以被唯一寫成 $sp^{m-1}+t$ 的形式，且 $0\leq s\leq p-1,0\leq 1\leq p^{m-1}$，因此$$g(a,p^m)=\sum_{t=1}^{p^{m-1}}\sum_{s=0}^{p-1}\zeta_{p^m}^{a(sp^{m-1}+t)^2}=\sum_{t=1}^{p^{m-1}}\sum_{s=0}^{p-1}\zeta_{p^{m}}^{as^2p^{2m-2}}\zeta_{p^{m}}^{2astp^{m-1}}\zeta_{p^{m}}^{at^2}$$因為 $2m-2\geq m$，$\zeta_{p^{m}}^{as^2p^{2m-2}}=1$，又因$\zeta_{p^m}^{p^{m-1}}=\zeta_{p}$，原式可被整理成$$\sum_{t=1}^{p^{m-1}}\left[\zeta_{p^{m}}^{at^2}\cdot \left(\sum_{s=0}^{p-1}\zeta_{p}^{2ast}\right)\right]$$我們討論小括號內的值。當 $p\,|\,t$ 時，括號內的每一項都等於 $1$，總和等於 $p$；當 $p\nmid t$ 時，$2at$ 和 $p$ 互質，故總和等於 $0$ (詳情可參考上一篇文的Lemma 1)。因此上式只需要考慮 $p\,|\,t$ 的情況，不妨令 $t=pr$，則 $1\leq r\leq p^{m-2}$，原式變成$$\sum_{r=1}^{p^{m-2}}\zeta_{p^m}^{ap^2r^2}\cdot(p)=\sum_{r=1}^{p^{m-2}}\zeta_{p^{m-2}}^{ar^2}=g(a,p^{m-2})$$證畢。
>
容易看到上述的 Proposition 可以一直歸納下去，直到 $m=0$ 或 $m=1$，分別取決於一開始的 $m$ 是 偶數 或 奇數。根據上一篇文章的 Proposition 2，我們可以得到以下的 Corollary：
### Corollary
> 給定整數 $a$ 和與其互質之質數 $p$ 和整數 $m\geq 2$，則
> $$g(a,p^m)=\begin{cases}p^{m/2},\,\,\mbox{ if }2\,|\,m\\ (\frac{a}{p})\sqrt{(-1)^{(p-1)/2}p^m},\,\,\mbox{ if }2\nmid m\end{cases}$$
### Theorem
> 給定正奇數 $n\geq 3$，$g(n)=g(1,n)=\sqrt{(-1)^{\frac{n-1}{2}}n}$
#### 證明 (我寫的草稿，如果可以更簡略歡迎與我聯絡)
> 若 $n$ 為質數，已經在上一篇文章證明過是正確的。假設 $$n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{I}^{r_{I}}q_{1}^{s_{1}}q_{2}^{s_{2}}\cdots q_{J}^{s_{J}}e_{1}^{t_{1}}e_{2}^{t_{2}}\cdots e_{K}^{t_{K}}$$ 是 $n$ 的質因數分解，其中 $p_{i},q_{j},e_{k}$ 為相異奇質數且 $$p_{i}\equiv 1\mbox{ (mod $4$)},\, q_{j}\equiv 3\mbox{ (mod $4$)},\, 2\nmid r_{i}, \, 2\nmid s_{j},\, 2\,|\,t_{k}$$因此根據 Corollary，\begin{align*}g(1,n)&=\left[\prod_{i=1}^{I}g\left(\frac{n}{p_{i}^{r_{i}}},\,p_{i}^{r_{i}}\right)\right]\left[\prod_{j=1}^{J}g\left(\frac{n}{q_{j}^{s_{j}}},\,q_{j}^{s_{j}}\right)\right]\left[\prod_{k=1}^{K}g\left(\frac{n}{e_{k}^{t_{k}}},\,e_{k}^{t_{k}}\right)\right]\\
> &=\left[\prod_{i=1}^{I}\left(\frac{n/p_{i}^{r_{i}}}{p_{i}}\right)\sqrt{(-1)^{\frac{p_{i}-1}{2}}p_{i}^{r_{i}}}\right]\left[\prod_{j=1}^{J}\left(\frac{n/q_{j}^{s_{j}}}{q_{j}}\right)\sqrt{(-1)^{\frac{q_{j}-1}{2}}q_{j}^{s_{j}}}\right]\left[\prod_{k=1}^{K} \sqrt{e_{k}^{t_{k}}}\right]\\
> &=\left[\prod_{i=1}^{I}\left(\frac{n/p_{i}^{r_{i}}}{p_{i}}\right)\cdot\prod_{i=1}^{I}\left(\frac{n/q_{j}^{s_{j}}}{q_{j}}\right)\right]\cdot i^{J}\cdot \sqrt{n}\,:= A\cdot i^{J}\cdot \sqrt{n}\end{align*}因為 $(2x+1)^2\equiv 1$ (mod $4$)，我們有 $e_{k}^{t_{k}}\equiv (e_{k}^2)^{t_{k}/2}\equiv 1^{t_{k}/2}=1$ (mod $4$)，同理有 $p_{i}^{r_{i}}\equiv p_{i}\equiv 1$ (mod $4$) 和 $q_{j}^{s_{j}}\equiv q_{j}\equiv 3$ (mod $4$)，因此 $n\equiv 3^{J}\equiv (-1)^{J}$ (mod $4$)。
> 當 $J$ 是偶數，$n\equiv 1$ (mod $4$)，故 $\sqrt{(-1)^{(n-1)/2}n}=\sqrt{n}$，因此只須證明 $Ai^{J}=1\Leftrightarrow A(-1)^{J/2}=1$；當 $J$ 是奇數，$n\equiv 3$ (mod $4$)，故 $\sqrt{(-1)^{(n-1)/2}n}=i\sqrt{n}$，因此只須證明 $Ai^{J-1}=1\Leftrightarrow A(-1)^{(J-1)/2}=1$。
> 因為 $t_{k}$ 是偶數，我們有 $\left(\dfrac{e_{k}^{t_{k}}}{p_{i}}\right)=1$，同理其他得到\begin{align*}\left(\frac{n/p_{i}^{r_{i}}}{p_{i}}\right)&=\left(\frac{p_{1}^{r_{1}}\cdots \hat{p_{i}}\cdots p_{I}^{r_{I}}}{p_{i}}\right)\left(\frac{q_{1}^{s_{1}}\cdots q_{J}^{s_{J}}}{p_{i}}\right)\left(\frac{e_{1}^{t_{1}}\cdots e_{K}^{t_{K}}}{p_{i}}\right)\\
> &=\left(\frac{p_{1}\cdots \hat{p_{i}}\cdots p_{I}}{p_{i}}\right)\left(\frac{q_{1}\cdots q_{J}}{p_{i}}\right)\\
> &=\left(\frac{p_{1}}{p_{i}}\right)\cdots\widehat{\left(\frac{p_{i}}{p_{i}}\right)}\cdots\left(\frac{p_{I}}{p_{i}}\right)\cdot\left(\frac{q_{1}}{p_{i}}\right)\cdots\left(\frac{q_{J}}{p_{i}}\right)
> \end{align*} 其中 $\hat{a}$ 表示跳過該項。同理 $A$ 的其他項，經過適當的配對，可以將 $A$ 整理成\begin{align*}A&=\left[\prod_{1\leq i<i'\leq I}\left(\frac{p_{i}}{p_{i'}}\right)\left(\frac{p_{i'}}{p_{i}}\right)\right]\left[\prod_{1\leq j<j'\leq J}\left(\frac{q_{j}}{q_{j'}}\right)\left(\frac{q_{j'}}{q_{j}}\right)\right]\left[\prod_{1\leq i\leq I,1\leq j\leq J}\left(\frac{p_{i}}{q_{j}}\right)\left(\frac{q_{j}}{p_{i}}\right)\right]\\
> &=\left[\prod_{1\leq i<i'\leq I}(-1)^{\frac{p_{i}-1}{2}\frac{p_{i'}-1}{2}}\right]\left[\prod_{1\leq j<j'\leq J}(-1)^{\frac{q_{j}-1}{2}\frac{q_{j'}-1}{2}}\right]\left[\prod_{1\leq i\leq I,1\leq j\leq J}(-1)^{\frac{p_{i}-1}{2}\frac{q_{j}-1}{2}}\right]\\
> &=1\cdot (-1)^{\frac{J(J-1)}{2}}\cdot 1\end{align*}其中，第二個等號是利用[二次互反律](https://en.wikipedia.org/wiki/Quadratic_reciprocity)，第三個等號則是根據 $p_{i},q_{j}$ 模 $4$ 後的結果。因此，當 $J$ 是偶數，$A(-1)^{\frac{J}{2}}=(-1)^{\frac{J^2}{2}}=1$，因為 $J^2$ 是 $4$ 的倍數；當 $J$ 是奇數，$A(-1)^{\frac{J-1}{2}}=(-1)^{\frac{J^2-1}{2}}=1$，利用 $(2x+1)^2\equiv 1$ (mod $4$)，這裡 $J=2x+1$，證畢。
>> 備註：看起來我假設了 $I,J,K$ 的存在性，但就算不存在這個證明依舊 work，只要把不存在的 index 設成 0 即可。

綜上討論，我們已經證明了以下的結果：
令 $$\varepsilon_{n}=\begin{cases}1,\mbox{ 若 }n\equiv 1\mbox{ (mod $4$)}\\ i,\mbox{ 若 }n\equiv 3\mbox{ (mod $4$)}\end{cases}$$則$$g(n)=\varepsilon_{n}\sqrt{n},\mbox{ 若 $n\equiv 1$ or $3$ (mod $4$)}$$這讓人好奇，如果 $n\equiv 2$ or $0$ (mod $4$)，結論會一樣乾淨嗎？答案是正確的，完整的公式為$$g(n)=\begin{cases}\varepsilon_{n}\sqrt{n},\,\,\,\,\,\,\,\,\,\,\,\mbox{ 若 $n\equiv 1$ or $3$ (mod $4$)}\\
0,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mbox{ 若 $n\equiv 2 $ (mod $4$)}\\ (1+i)\sqrt{n}, \mbox{ 若 $n\equiv 0 $ (mod $4$)}\end{cases}$$