四平方和问题与 Theta 级数

· · 算法·理论

第一期：因子和函数卷积恒等式
第二期：Ramanujan Tau 函数的积性
第三期：模形式的空间结构

现在我们来讨论一下四平方和问题，用一些初等方法也能推导出答案，不过我们要用模形式方法找到其背后更一般的性质。我们在全模群上学习过一些基础知识，而对同余子群几乎一无所知，现在我们尝试推广。

对 q = \text e^{2\pi \text i z}，设 theta 级数：

\theta(z):=\sum_{n \in \Z} q^{n^2}=1+2q+2q^4+\cdots

那么我们想要对正整数 n 快速计算 [q^n]\theta(z)^4。首先，我们显然有 \theta(z)=\theta(z+1)，也不难判断 \theta(z) 在 \mathcal H 上解析，那么是否有 \theta(-1/z)=z^k \theta(z) 呢？若可以，就能用熟悉的方法研究它了。
坏消息：并没有这样的性质；好消息：仍然有类似的变换。

\sqrt {\frac{2z}{\text i}}\theta(z)=\theta\left( -\frac{1}{4z}\right) \quad \texttt{(1)}

:::info[\theta(z) 的模变换推导]

我们知道 Poisson 求和公式（弱化版）如下：

对于平方可积的光滑函数 f:\R \to \mathbb C 则：

\sum_{n \in \Z}f(n)=\sum_{n \in \Z} \tilde f(n) \tilde f(y):=\int_{-\infty}^\infty f(x) \text e^{2\pi\text i yx}\text dx

弱化版的证明是很简单的，在此略过。对 \theta(z) 使用此公式就能得到相应的变换。具体地设 f(x)=\text e^{-\pi t x^2}，其中 t >0。则我们可以直接计算 \tilde f (y)：

\tilde f(y)=\int_{-\infty}^\infty \text e^{2\pi \text i yx-\pi t x^2} \text dx=\frac{\text e^{-\pi y^2/t}}{\sqrt t}\int_{-\infty}^\infty \text e^{-\pi u^2}\text du=\frac{\text e^{-\pi y^2/t}}{\sqrt t}

第二步做了换元：u=\sqrt t (x - \text i y/t)，最后的积分就是经典结论了。由此可知

\sum_{n \in \Z}\text e^{-\pi t n^2}=\frac{1}{\sqrt t}\sum_{n \in \Z}\text e^{-\pi n^2/t}

容易发现，左式就是 \theta(\text i t/2)，由此可得 \theta(\text it/2)=\theta(\text i/(2t))/\sqrt t，这证明了 z=\text i t 在正虚轴的情形，这就足够了。因为解析延拓的唯一性告诉我们，两个在开域 D 上解析函数在一条线段上相等时，它们必然在 D 上相等。稍作整理即得 \texttt{(1)} 式。

:::

这里开平方不会有支割线的问题，因为 2z/\text i 的辐角范围只有 \pi。这个 \texttt{(1)} 的变换让我们觉得 \theta(z) 像是 \varGamma_1 某个子群上权为 1/2 的模形式。暂时先不讨论非整数权的问题，直接来看 \theta(z)^4 的情况，性质会好一些。这里设 f_k(z)=\theta(z)^k：

f_4(z)=-\frac{1}{4z^2}f_4\left( -\frac{1}{4z}\right) \quad \texttt{(2)}

在以往 S,T 变换的基础上，我们再定义 W_n:=\frac{1}{\sqrt n}\begin{pmatrix}0 & -1 \\ n & 0\end{pmatrix}。之前对群作用性质的证明，推广到 \operatorname{SL}(2,\R) 的任意子群也是成立的。显然 W_4(z)=-1/(4z)，故

\tilde T(z) :=(W_4^{-1} T^{-1}W_4)(z)= \begin{pmatrix}1 & 0 \\ 4 & 1 \end{pmatrix} (z)=\frac{z}{4z+1}

所以给 \texttt{(2)} 式先做变换 z \mapsto z-1，再做 z \mapsto -1/(4z)，就会得到

f_4(z)=(4z+1)^{-2}f_4 \left( \frac{z}{4z+1}\right) \quad \texttt{(3)}

现在我们有两个矩阵 T,\tilde T \in \varGamma_1，它们都能使 f_4(z)=(f_4 \mid_2 T)(z)=(f_4 \mid_2 \tilde T)(z)。由这两个矩阵生成的群正好就是 \varGamma_1 模 4 的同余子群，记为 \varGamma_0(4)。

定义（同余子群）： 设 \varGamma_1 的子群 \varGamma_0(N) 满足任意 \gamma = \begin{pmatrix} a & b \\ c &d \end{pmatrix}\in \varGamma_1，都有 N \mid c \Leftrightarrow \gamma \in \varGamma_0(N)，则 \varGamma_0(N) 就称为是 \varGamma_1 模 N 的同余子群。

证明 T,\tilde T 能生成 \varGamma_0(4)/\{1,-1\} 是容易的，但要计算一般的 \varGamma_0(N) 的生成系较为复杂，在此先不讲。

总之，现在我们知道 f_4(z) 是 \varGamma_0(4) 上权为 2 的模形式了，即 f_4(z) \in M_2(\varGamma_0(4))。除它之外，还能找到哪些 M_2(\varGamma_0(4)) 的元素呢？可以尝试从 \varGamma_1 上权为 2 的准模形式推一下。

我们知道对任意 \gamma \in \varGamma_1 和 z \in \mathcal H 都有

G_2(\gamma(z))= (cz+d)^2 G_2(z)- \pi \text i c(cz+d)

设 \mathbb G_2^*(z)=-\frac{1}{4 \pi^2}G_2(z)+\frac{1}{8 \pi \Im(z)}，则

\begin{aligned}\mathbb G_2^*(\gamma(z))&=-\frac{1}{4\pi^2}((cz+d)^2G_2(z)-\pi \text i c(cz+d))+\frac{|cz+d|^2}{8 \pi \Im(z)} \\ \mathbb G_2^*(\gamma(z)) &= (cz+d)^2 \mathbb G_2^*(z)\end{aligned}

同样是把 z 的实部和虚部拆开计算得到的，只是稍有些繁琐。注意 \mathbb G_2^*(z) 虽然满足权为 2 的自守条件，但不满足增长条件。而以下两个函数：

\begin{aligned}\mathbb G_2^*(z)-2\mathbb G_2^*(2z) &=-\frac{1}{4\pi^2}(G_2(z)-2G_2(2z)) \\ \mathbb G^*_2(2z)-2\mathbb G_2^*(4z)&=\frac{1}{24} + q^2 + q^4 + 4 q^6 + q^8 + 6 q^{10}+\cdots\end{aligned} \quad \texttt{(4)}

就都满足增长条件了，但自守条件又不在整个 \varGamma_1 中都成立。

事实上，若 f(z) 使得任意 \gamma \in \varGamma_1 都有 f \mid_k \gamma = f（注意，这里不要求是模形式，只要求满足自守条件）；对于正整数 N，任取正整数 d \mid N 设 g(z)=f(dz)，则 g \mid_k \gamma' = g 对任意 \gamma' \in \varGamma_0(N) 都成立。也就是说，\texttt{(4)} 中找到的两个都是 \varGamma_0(4) 上权为 2 的模形式。

如果我们能证明 \dim M_2(\varGamma_0(4)) = 2，那么 f_4(z) 必然就是 \texttt{(4)} 的线性组合。如果进一步算出更高权的维数，结合 Hecke 算子理论，也将能解决 4k 平方和计数问题。一般情况的维数公式还是过于复杂，不过简单分析还是能得到一个上界。

定理（维数上界） 设 \varGamma 是 \varGamma_1 的含有 -I 的子群，对于正偶数 k，有

\dim M_k(\varGamma) \leq \frac{\mu k}{12}+1 \quad \texttt{(5)}

其中 \mu 为 \varGamma 对 \varGamma_1 的指数（即 [\varGamma_1 : \varGamma]）。

应用此定理，会直接得到 \dim M_2 (\varGamma_0(4)) \leq 2，也就会得到 f_4(z)=8(\mathbb G^*_2(z)-2\mathbb G_2^*(2z))+16(\mathbb G^*_2(2z)-2\mathbb G_2^*(4z))，直接提取系数即可解决四平方和计数问题。接下来我们证明一下这个定理。

:::info[证明]

设 (-I) \in \varGamma \leqslant \varGamma_1，k 为正偶数，f 是 \varGamma 上权为 k 的模形式，[\varGamma_1 : \varGamma] = \mu。取陪集分解 \gamma_1,\cdots,\gamma_\mu 使得 \bigsqcup_{i=1}^\mu \varGamma \gamma_i=\varGamma_1。那么

F(z)=\prod_{i=1}^\mu (f \mid_k \gamma_i)(z)

就是 \varGamma_1 上权为 \mu k 的模形式。因为对任意 a,b\in \varGamma \gamma_i，都有 f \mid_k a = f \mid_k b。
现在设 d=\lfloor k \mu /12 \rfloor +1，我们要证明 \dim M_k(\varGamma) \leq d，可以考虑反证法。

若 \dim M_k(\varGamma) > d，则必然存在线性无关的模形式 v_1,\cdots v_{d+1} \in M_k(\varGamma)。设 \mathcal F 是一个包含 \widetilde{\mathcal F}_1 的对于 \varGamma 的基本域。取 \mathcal F 上不为 \text i,\omega 轨道上的点 P_1,\cdots,P_d，则必然存在线性组合 f=c_1v_1+\cdots c_{d+1}v_{d+1} 在这些点上都为 0。

现在 f 作为一个特殊的 \varGamma 上的模形式，构造对应的 F，其中固定 \gamma_1=I。
根据零点阶数公式，若 F 不恒为零则：

\operatorname{ord}_\infty (F)+\sum_{P \in \widetilde{\mathcal F}_1}\frac{\operatorname{ord}_P(F)}{n_P}=\frac{\mu k}{12}

而我们知道 F(z) = f(z) \prod_{i=1}^{\mu-1}(f \mid_k \gamma_i)(z)，在 \widetilde{\mathcal F}_1 内的零点阶数之和至少为 d> \mu k /12，故 F(z) 恒为零，由此得到 f(z) 恒为零，所以 v_1,\cdots,v_{d+1} 线性相关，产生了矛盾。

故假设不成立，\dim M_k(\varGamma) \leq d。 :::

不难计算得到，[\varGamma_1 : \varGamma_0(4)]=6。

:::info[同余子群的指数] 讲一下一般情况 \varGamma_0(4) 指数的计算，虽然这期只用到 N=4 的情况。
设 \varGamma_1(N) \leqslant \varGamma_1 为主同余子群，其元素模 N 后为单位矩阵，则

[\varGamma_1 : \varGamma_1(N)] = |\mathrm{SL}(2,\Z / N\Z)|=N^3 \prod_{p \mid N}\left( 1 - \frac{1}{p^2}\right)

此结果见 P1951 题解的推导，这里就不复读了。显然 \varGamma_1(N) \leqslant \varGamma_0(N)，考虑计算 [\varGamma_0(N) : \varGamma_1(N)]，设群同态

\begin{aligned} \psi : \varGamma_0(N) &\to \mathrm{SL}(2,\Z/N\Z) \\ \begin{pmatrix} a & b \\ Nc & d \end{pmatrix} & \mapsto \begin{pmatrix} a \bmod N & b \bmod N \\ 0 & d \bmod N\end{pmatrix}\end{aligned}

不难发现，\ker \psi = \varGamma_1(N)，设 \psi 的像 B(N)，主对角线元素相乘模 N 为 1，故确定主对角线有 \varphi(N) 种可能；而在模 N 后右上角元素有 N 种可能，故 |B(N)|=N \varphi(N)。根据群同态基本定理 \varGamma_0(N)/\varGamma_1(N) \cong B(N)，利用指数公式即得 [\varGamma_0(N):\varGamma_1(N)]=|B(N)|。

最后我们有

[\varGamma_1 : \varGamma_0(N)] = \frac{[\varGamma_1 : \varGamma_1(N)]}{[\varGamma_0(N) : \varGamma_1(N)]}=N \prod_{p \mid N}\left(1+\frac 1p \right)

:::

这样就得到了对于正偶数 k，\dim M_k(\varGamma_0(4)) \leq k/2 + 1。设 g_1(z)=(\mathbb G_2^*(z)-2\mathbb G^*(2z)) 和 g_2(z)=(\mathbb G_2^*(2z)-2\mathbb G^*(4z))，我们已经证明了 g_1,g_2 是 M_2(\varGamma_0(4)) 的一组基。根据上期对 M_k(\varGamma_1) 的分析，我们也能类似地证明 M_k(\varGamma_0(4)) 存在一组基为：

v_i = g_1^i g_2^{k/2-i} \ , \ (0 \leq i \leq k/2)

（如果看过上期证明，就会发现这是显然的）

现在要计算 \theta(z)^{4k} 的系数，依照以往的方法，将其用 M_{2k}(\varGamma_0(4)) 中刚才构造的基线性表示，然后计算 Hecke 算子的矩阵即可，所以我们想要扩展 Hecke 算子在同余子群上的定义。

回顾一下 Hecke 算子的原始定义，我们不难写出 T_m 作用于 f，f \in M_k(\varGamma_0(N)) 的结果是这样的：

T_m f(z) = m^{k-1}\sum_{\gamma \in \mathcal M_m/\varGamma_0(N)} (f \mid_k \gamma)(z)

显然 T_mf(z) \in M_k (\varGamma_0(N))。也是按照相同的研究方法，我们可以取 \mathcal M_m / \varGamma_0(N) 的一组代表元为 \begin{pmatrix} a & b \\ 0 & d \end{pmatrix} \in \varGamma_0(N)，其中 ab = m,\gcd(a,N)=1, b<d，且 a,b,d 均为非负整数。进一步也能计算 Fourier 系数的变化：

[q^n] (T_m f(z))= \sum_{d \mid \gcd(n,m)}[\gcd(d,N)=1] d^{k-1}[q^{nm/d^2}] f(z) \quad \texttt{(6)}

最后，我们想要的 Hecke 算子的美妙性质，稍作修改后仍然存在：

T_n T_m = \sum_{d \mid \gcd(n,m)}[\gcd(d,N)=1] d^{k-1}T_{nm/d^2} \quad \texttt{(7)}

不过实际计算中我们只需要互质与素数幂递推性质就足够，这两个性质都较为容易证明。需要注意的是，p \mid N 时会有 T_{p^n} = (T_p)^n，比一般的素数幂递推更简单。用 基础模形式练习题 后半部分的做法，就能轻松解决 4k 平方和问题了。

一份参考代码，可以计算 p^n 用 4k 个整数的平方和表示的计数问题。其中的 solve 部分是朴素递推，可以用矩阵快速幂等方法来加速。

看到这你也许会问，二平方和的情况应该比四平方简单啊，为什么不讲呢？因为 \theta(z)^2 是带有 Dirichlet 特征的模形式，还需要将以上内容继续扩展来得到其相关理论。限于篇幅，这期就先到此为止了。