表达式求和

mathe

记ω是n次单位根$e^{(2πi)/n}$， 求`a_n=\frac1n{\left(\D\sum_{h=0}^{n-1}ω^{h^2}\right)^2}`

nyy

mma能解决吗？
要是不能的话，
绝大多数人应该解决不了这个问题
这个问题有没有什么背景意义？

mathe

使用计算机计算容易验证使用计算机计算容易验证\(a_n =\begin{cases}2i&n\equiv 0\pmod 4\\1&n\equiv 1\pmod 4\\0&n\equiv 2\pmod 4\\-1&n\equiv 3\pmod 4\end{cases}\), 主要问题在于如何证明这个问题。

任意选择\((k,n)=1\), 我们可以先查看表达式\(H(n)=\sum_{s=0}^{n-1}\sum_{t=0}^{n-1}\omega^{2kst}\)
很显然，由于\(\omega\)是n次本原单位根，所以当\(\omega^{2s} \neq 1\)时，总有\(\sum_{t=0}^{n-1}\omega^{2kst}=0\)
所以当n为奇数\(H(n)=n\),当n为偶数\(H(n)=2n\).

又因为\(\sum_{t=0}^{n-1}\omega^{2kst+s^2}=\omega^{s^2}\sum_{t=0}^{n-1}\omega^{2kst}\), 所以在\(\omega^{2s}\neq 1\)时，总有\(\sum_{t=0}^{n-1}\omega^{2kst+s^2}=\sum_{t=0}^{n-1}\omega^{2kst}\)， 因为这时两者都是0. 而在\(\omega^{2s}=1\)时，必然有\(s=0\)或\(s=\frac n2\), 其中\(s=0\)时，显然等式\(\sum_{t=0}^{n-1}\omega^{2kst+s^2}=\sum_{t=0}^{n-1}\omega^{2kst}\)也成立，而\(s=\frac n 2\)时，n必须为偶数，所以其中n为4的倍数时，也有\(\sum_{t=0}^{n-1}\omega^{2kst+s^2}=\sum_{t=0}^{n-1}\omega^{2kst}\) （这时两者都是n)；但是单n除以4余数为2时，由于\(\omega^{s^2}=-1\),两者不相等，分别为n和-n.
由此得到\(\sum_{t=0}^{n-1}\omega^{2kst+s^2}=\sum_{t=0}^{n-1}\omega^{2kst}-R(n,s)\),
其中\(R(n,s)=\begin{cases}2n&n\equiv 2\pmod 4 \& 2s=n\\0&others\end{cases}\).
由此得到\(\sum_{s=0}^{n-1}\sum_{t=0}^{n-1}\omega^{2kst+s^2} = H(n) -R(n,\frac n 2)\)
所以交换求和顺序我们得到\(H(n) -R(n,\frac n 2)=\sum_{t=0}^{n-1}\sum_{s=0}^{n-1}\omega^{s^2+2kst}=\sum_{t=0}^{n-1}\omega^{-k^2t^2}\sum_{s=0}^{n-1}\omega^{(s+kt)^2}=\sum_{t=0}^{n-1}\omega^{-k^2t^2}\sum_{s=0}^{n-1}\omega^{s^2}\).
特别的，在\(n\equiv 2\pmod 4, k=1\)时，我们有\(\left|\sum_{s=0}^{n-1}\omega^{s^2}\right|^2=0\),所以这时\(\sum_{s=0}^{n-1}\omega^{s^2}=0\)

mathe

现在我们可以再次查看\(K(n)=\sum_{s=0}^{n-1}\sum_{t=0}^{n-1}\omega^{4st}\), 同样容易计算处\(K(n)\)在n为奇数时等于n,在n为4的倍数时为4n,在n除以4余2时为2n.
类似上面的计算，我们可以有\(\sum_{t=0}^{n-1}\omega^{4st+s^2}=\omega^{s^2}\sum_{t=0}^{n-1}\omega^{4st}\).
所以等式\(\sum_{t=0}^{n-1}\omega^{4st+s^2}=\sum_{t=0}^{n-1}\omega^{4st}\)在大部分情况成立，
同样我们可以记\(\sum_{t=0}^{n-1}\omega^{4st+s^2}=\sum_{t=0}^{n-1}\omega^{4st}-Q(n,s)\), 容易计算出\(Q(n,s)=\begin{cases}(1-\omega^{m^2})n&n=4m\&(s=m或s=3m)\\2n&n=4m+2\&s=2m+1\\0&others\end{cases}\).
然后我们可以得到\(K(n)-Q(n,\frac n4)-Q(n,\frac n2)-Q(n,\frac{3n}4) = \sum_{t=0}^{n-1}\sum_{s=0}^{n-1}\omega^{s^2+4st}=\sum_{t=0}^{n-1}\omega^{-4t^2}\sum_{s=0}^{n-1}\omega^{(s+2t)^2}=\sum_{t=0}^{n-1}\omega^{-4t^2}\sum_{s=0}^{n-1}\omega^{s^2}\).
所以n为奇数时\(\sum_{t=0}^{n-1}\omega^{-4t^2}\sum_{s=0}^{n-1}\omega^{s^2}=n\)
当n为4m+2时\(\sum_{t=0}^{n-1}\omega^{-4t^2}\sum_{s=0}^{n-1}\omega^{s^2}=2n-2n=0 \)
当n为4m时\(\sum_{t=0}^{n-1}\omega^{-4t^2}\sum_{s=0}^{n-1}\omega^{s^2}=4n-Q(4m,m)-Q(4m,3m)=2(\omega^{m^2}+1)n \).
需要注意的是，这两层计算中，我们其实并不需要严格要求\(\omega=\exp(\frac{\pi i}n)\),而只要求\(\omega\)是n次本原单位根即可。

mathe

为了避免歧义，我们记\(\omega_n=\exp(\frac{2\pi i}n)\),
对于奇数n, 我们有\(\sum_{s=0}^{n-1}\omega_n^{s^2}=\sum_{s=0}^{n-1}\omega_n^{(s+\frac{n+1}2)^2}=\omega_n^{(\frac{n+1}2)^2}\sum_{s=0}^{n-1}\omega_n^{s(s+1)}\)
而\(\sum_{s=0}^{4n-1}\omega_{4n}^{s^2}=\sum_{s=0}^{2n-1}\omega_{4n}^{(2s)^2}+\sum_{s=0}^{2n-1}\omega_{4n}^{(2s+1)^2}=2\sum_{s=0}^{n-1}\omega_n^{s^2}+2\omega_{4n}\sum_{s=0}^{n-1}\omega_n^{s(s+1)}=(2+2\omega_{4n}\omega_n^{-(\frac{n+1}2)^2})\sum_{s=0}^{n-1}\omega_n^{s^2}=(2+2\omega_{4n}^{-(n^2+2n)})\sum_{s=0}^{n-1}\omega_n^{s^2}=2(1+(-i)^{n+2})\sum_{s=0}^{n-1}\omega_n^{s^2}\)

mathe

引理1：对于任意奇素数p, 存在整数u,v使得\(u^2+v^2\equiv -1\pmod p\).
证明： 由于\((4p, 2p-1)=1\),  由狄利克雷定理，存在n使得\(q=4np+(2p-1)\)是素数，又因为\(q\equiv 1\pmod 4\)，根据费马平方和定义，
存在整数u,v使得\(q=u^2+v^2\), 所以\(u^2+v^2=q\equiv -1\pmod p\).得到证明。

引理2：对于任意奇素数的幂\(q=p^s\), 存在整数u,v使得\(u^2+v^2\equiv -1 \pmod q\).
我们只需要对s用数学归纳法即可，由于根据引理1，对于s=1时，已经存在\(u_1^2+v_1^2 \equiv -1 \pmod p\)
假设对于s,存在\(u_s^2+v_s^2 \equiv -1 \pmod {p^s}\), 不妨设\(u_s^2+v_s^2=r_s p^s -1\)
如果\(r_s\equiv 0\pmod p\), 那么我们取\(u_{s+1}=u_s,v_{s+1}=v_s\)即可，不然如果\(u_s \neq 0 \pmod p\), 我们选择
我们设\(u_{s+1}=-r_s (2u_s)^{-1}p^s+u_s,v_{s+1}=v_s\)代入可以满足要求；而如果\(u_s \neq 0 \pmod p\),那么必然\(v_s \neq 0 \pmod p\),类似也可以构造\(u_{s+1}=u_s, v_{s+1}=-r_s(2v_s)^{-1}p_s+v_s\)即可。由此我们证明了引理2.

mathe

引理3：对于奇素数的幂q, 表达式\((\sum_{s=0}^{q-1} \omega_q^{s^2})^2\)是实数。
证明: 根据引理2,存在\(u,v\)使得\(u^2+v^2\equiv -1\pmod q\),
我们构造映射\(f(a,b)=(au-bv, av+bu) \pmod q\), 映射\(g(a,b)=(au+bv, av-bu)\pmod q\)
计算可以知道\(g(f((a,b))=(u^2+v^2)(a,b)=(-a,-b) \pmod q\), 所以映射-g 模q是f的逆映射，由此我们知道f在模q下是一一映射。
而且如果存在(a,b)使得\(f((a,b))= (a,b) \pmod q\) ，那么必然\(g(a,b)=-(a,b) \pmod q\),由此我们得到方程
\(\begin{cases}au=bv+a \pmod q\\ -av=bu-b \pmod q\\-au=bv+a\pmod q\\av=bu-b\pmod q\end{cases}\)
由此得出必须\(au=av=0\pmod q\), 由于u,v不同时为0，所以\(a=0\pmod q\). 由此再次得出bu=bv=0,所以\(b=0\pmod q\).
也就是f只有唯一不动点\((0,0)\pmod q\).
现在我们记\(S_h=\{(a,b)| 0 \le a\lt q, 0\le b\lt q, a^2+b^2\equiv h \pmod q\}\).
于是我们容易得出\(f(S_h)=S_{q-h}\), 由此得出\(|S_h|=|S_{q-h}|\).

所以 \((\sum_{s=0}^{q-1} \omega_q^{s^2})^2=\sum_{s=0}^{q-1}\sum_{t=0}^{q-1}\omega_q^{s^2+t^2}=\sum_{h=0}^{q-1} |S_h|\omega_q^h=|S_0|+\sum_{h=1}^{\frac{q-1}2}|S_h|(\omega_q^h+\omega_q^{-h}) \)显然是实数。

mathe

引理4： 如果\((m,n)=1\), 那么\(\sum_{s=0}^{m-1}\omega_m^{s^2}\sum_{t=0}^{n-1}\omega_n^{t^2}=\sum_{s=0}^{mn-1} \omega_{mn}^{s^2}\).
这个是因为
\(\sum_{s=0}^{m-1}\sum_{t=0}^{n-1}\omega_{mn}^{ns^2+mt^2}=\sum_{s=0}^{m-1}\sum_{t=0}^{n-1}\omega_{mn}^{(ns+mt)^2}=\sum_{s=0}^{mn-1}\omega_{mn}^{s^2}\)

mathe

现在根据引理4，我们知道对于本题，我们只需要解决各个素数幂的情况，就能够证明通用的情况。
而引理3说明对于奇数n情况，\((\sum_{s=0}^{n-1}\omega_n^{s^2})^2\)是实数，再根据3#中k=1情况，我们知道\(|\sum_{s=0}^{n-1}\omega_n^{s^2}|^2=n\)， 我们可以得出\((\sum_{s=0}^{n-1}\omega_n^{s^2})^2=\pm n\),现在唯一的问题是符号还确定不了。
另外我们还需要对2的幂计算本题。

mathe

对于\(n=2^h,h\ge 4\)我们可以统一处理，
首先我们可以分析出\((2k+1)^2 \pmod n, k=0,...,2^{h-1}-1\)等价于\(8k+1, k=0,...,2^{h-3}-1\)中所有元素都重复出现4次。
由此得到
\(\sum_{t=0}^{n-1} \omega_n^{t^2}=\sum_{t=0}^{n/2-1} \omega_n^{(2t)^2}+\sum_{t=0}^{n/2-1} \omega_n^{(2t+1)^2}=2\sum_{t=0}^{n/4-1} \omega_{n/4}^{t^2}+4\sum_{t=0,n/8-1}\omega_n^{8t+1}=2\sum_{t=0}^{n/4-1} \omega_{n/4}^{t^2}\)