题解：P2019 四平方和定理
2022dyx
·
·
题解
2025.8.6 upd：修改了打错的公式。
这是一道非常强大的数学题，虽然打表找规律是容易的，但严格的证明却很难。由于目前题解区只有一篇基于模形式的推导，而蒟蒻苦学无果后，看到知乎上有一个纯 OGF 推式子的做法，打算详细总结整理下来，方便像我这样的蒟蒻食用，于是就有了这篇题解。
首先肯定要先写出答案的 OGF，根据基础的 OGF 知识，不难写出：
ans=[x^n](\sum_{i=-\infin}^{\infin}x^{i^2})^4
容易发现最大的问题就是 \sum 外面还要四次幂，暴力展开显然是不可行的，因此一个方法是将 \sum 转化成更好处理的 \prod，这样就能把四次幂放到 \prod 里面，之后再想办法将 \prod 换回 \sum 就能求出答案。
按照上面的步骤，首先要选取一个带有形如 x^{i^2} 项的恒等式来转化，因此我们选取一个著名的组合恒等式：
\begin{aligned}
\prod_{i=1}^{\infin}(1+kx^{2i-1})(1+k^{-1}x^{2i-1})(1-x^{2i})=\sum_{i=-\infin}^{\infin}k^ix^{i^2}
\end{aligned}
下面我们来证明它。由于左式中 k，k^{-1} 同时出现在前两项中，所以我们设：
f_{m}(k)=\prod_{i=1}^m(1+kx^{2i-1})(1+k^{-1}x^{2i-1})
此时显然 k 和 k^{-1} 的系数是相同的，我们设这个系数为 a_j，则有：
\prod_{i=1}^m(1+kx^{2i-1})(1+k^{-1}x^{2i-1})=\sum_{i=0}^{m}a_i(k^i+k^{-i})
观察 k^m 和 k^{-m} 项的系数，不难发现这个值为 x^{1+2+...+2m-1}=x^{m^2}，因此我们有 a_m=x^{m^2}，之后考虑如何递推，我们只要代入 f_m(kx^2)，就可以错开一位，进而求出递推式，此时左式有：
\begin{aligned}
f_m(kx^2)&=\prod_{i=1}^m(1+kx^{2i+1})(1+k^{-1}x^{2i-3})\\
&=\frac{1+kx^{2m+1}}{1+kx}\prod_{i=1}^m(1+kx^{2i-1})\frac{1+k^{-1}x^{-1}}{1+k^{-1}x^{2m-1}}\prod_{i=1}^m(1+k^{-1}x^{2i-1})\\
&=\frac{1+kx^{2m+1}}{kx+x^{2m}}\prod_{i=1}^m(1+kx^{2i-1})(1+k^{-1}x^{2i-1})
\end{aligned}
即 (kx+x^{2m})f_m(kx^2)=(1+kx^{2m+1})f_m(k)，此时我们再将这个关系带入右式就可以得到递推关系，有：
\begin{aligned}
[k^i](kx+x^{2m})\sum_{i=0}^ma_i((kx^2)^i+(kx^2)^{-i})&=[k^i](1+kx^{2m+1})\sum_{i=0}^ma_i(k^i+k^{-i})\\
x^{2(m+i)}a_i+x^{2i-1}a_{i-1}&=a_i+x^{2m+1}a_{i-1}\\
a_{i-1}&=\frac{1-x^{2(m+i)}}{x^{2i-1}(1-x^{2(m-i+1)})}a_i
\end{aligned}
转通项公式是容易的，我们有：
\begin{aligned}
a_i&=x^{2^m}\prod_{j=i+1}^{m}\frac{1-x^{2(m+j)}}{x^{2j-1}(1-x^{2(m-j+1)})}\\
&=\frac{\prod_{j=1}^mx^{2j-1}}{\prod_{j=i+1}^mx^{2j-1}}\frac{\prod_{j={i+1}}^m(1-x^{2(m+j)})}{\prod_{j=i+1}^{m}(1-x^{2(m-j+1)})}\\
&=x^{i^2}\frac{\prod_{j={m+i+1}}^{2m}(1-x^{2j})}{\prod_{j=1}^{m-i}(1-x^{2j})}
\end{aligned}
不要忘了我们的目标，现在我们把 (1-x^{2i}) 塞回去，我们就有：
\begin{aligned}
b_i&=a_i\prod_{j=1}^m(1-x^{2j})\\
&=x^{i^2}\frac{\prod_{j=1}^{m}(1-x^{2j})}{\prod_{j=1}^{m-i}(1-x^{2j})}\prod_{j={m+i+1}}^{2m}(1-x^{2j})\\
&=x^{i^2}\prod_{j=m-i+1}^m(1-x^{2j})\prod_{j={m+i+1}}^{2m}(1-x^{2j})
\end{aligned}
当 m 趋于 +\infin 时，后面的两个 \prod 只要位于收敛半径内就一定会趋向于 1，因此有：
\lim_{m\to\infin}b_i=x^{i^2}
带回到原式中，就有：
\begin{aligned}
\prod_{i=1}^{\infin}(1+kx^{2i-1})(1+k^{-1}x^{2i-1})(1-x^{2i})&=\sum_{i=0}^{\infin}x^{i^2}(k^i+k^{-i})\\
&=\sum_{i=-\infin}^{\infin}k^ix^{i^2}
\end{aligned}
因此 (1) 式成立。
在进行下一步之前，我们先把接下来的证明过程中会反复用到的式子整理在这里：
\begin{align}
\prod_{i=1}^{\infin}(1+kx^{2i-1})(1+k^{-1}x^{2i-1})(1-x^{2i})&=\sum_{i=-\infin}^{\infin}k^ix^{i^2}\\
(1+x^i)(1-x^i)&=1-x^{2i}\\
\prod_{i=1}^{\infin}(1\pm x^{2i-1})(1\pm x^{2i})&=\prod_{i=1}^{\infin}(1\pm x^i)
\end{align}
后两个式子成立是显然的，(2) 式是平方差公式，(3) 式是 (2\mathbb{Z}^+-1)\cup(2\mathbb{Z}^+)=\mathbb{Z}^+。通过这两个式子，我们可以将 \prod(1\pm x^i)、\prod(1\pm x^{2i-1})、\prod(1-x^{2i}) 关联起来进行推导。
注意到直接将 k=1 带入 (1) 式中后，左式会出现一个 (1+x^{2i-1})^2，而 x^{2i-1} 并不好处理，硬上公式就要和 x^{4i} 打交道了，所以我们不这么做，而是带入 k=-1，此时就只有可以用 (2) 式直接化简的式子了，只要化简之后做一个 x\to-x 的换元即可得到答案，于是我们有：
\begin{aligned}
(\sum_{i=-\infin}^{\infin}(-1)^ix^{i^2})^4&=\prod_{i=1}^{\infin}((1-x^{2i-1})^2(1-x^{2i}))^4\\
&=\prod_{i=1}^{\infin}(\frac{(1-x^i)^2}{1-x^{2i}})^4\\
&=\prod_{i=1}^{\infin}(\frac{1-x^i}{1+x^i})^4
\end{aligned}
这看起来好多了，但是还是不能直接得到答案，我们还需要进一步的转化。上面我们好不容易证明的 (1) 式显然不只有这一点用，所以接下来我们要靠 (1) 式的变形来得到这个形式。为了尽可能多的 1-x^i 和 1+x^i，以及后面式子的简便，我们带入 k=-k^2x^{\frac{1}{2}}，x=x^{\frac{1}{2}}，进行一些化简，则有：
\begin{aligned}
\prod_{i=1}^{\infin}(1-k^2x^i)(1-k^{-2}x^{i-1})(1-x^i)&=\sum_{i=-\infin}^{\infin}(-1)^ik^{2i}x^{\frac{i(i+1)}{2}}\\
(1-k^{-2})\prod_{i=1}^{\infin}(1-k^2x^i)(1-k^{-2}x^i)(1-x^i)&=\sum_{i=-\infin}^{\infin}(-1)^ik^{2i}x^{\frac{i(i+1)}{2}}\\
(k-k^{-1})\prod_{i=1}^{\infin}(1-k^2x^i)(1-k^{-2}x^i)(1-x^i)&=\sum_{i=-\infin}^{\infin}(-1)^ik^{2i+1}x^{\frac{i(i+1)}{2}}
\end{aligned}
此时设左式中的积式为 f(k)，如果想要直接带入 k=1，无论 f(k) 等于多少，(k-k^{-1})=0 会直接让左式为 0，把我们要的形式消掉，肯定是不行的。但我们注意到 k=1 时左式导数的形式非常好看，因为 (k-k^{-1})f'(x) 在带入 k=1 时会直接等于 0，那就只会剩下 (k-k^{-1})'f(x)=(1+k^{-2})f(x)=2f(x) 了，右侧也同样求导并带入 k=1 后，我们就有：
\prod_{i=1}^{\infin}(1-x^i)^3=\frac{1}{2}\sum_{i=\infin}^{\infin}(-1)^i(2i+1)x^{\frac{i(i+1)}{2}}
为了凑出最后的四次方，仅仅停在这里肯定还不行。由于目前唯一更改 1-x^i 的次数的方法就是运用 (1) 式来获得更多无穷乘积，因此我们一定需要对目前看起来还没有开发完全的右式变形后再运用 (1) 式来凑四次方。目前右式的复杂程度还不够调整到需要的形式，同时也为了增大次数，我们等式两边平方，有：
\prod_{i=-\infin}^{\infin}(1-x^i)^6=\frac{1}{4}\sum_{i,j=-\infin}^{\infin}(-1)^{i+j}(2i+1)(2j+1)x^{\frac{i(i+1)+j(j+1)}{2}}
$$R=\frac{1}{4}(\sum_{2\mid i+j}(2i+1)(2j+1)x^{\frac{i(i+1)+j(j+1)}{2}}-\sum_{2\nmid i+j}(2i+1)(2j+1)x^{\frac{i(i+1)+j(j+1)}{2}})$$
此时 $i$ 和 $j$ 完全混在了一起，而我们又没有二元的恒等式，因此第一要务就是分开它们。而且 $\sum$ 下的约束也不太自然，为了解决这些问题，就有了下面的换元：
$$R=\frac{1}{4}(\sum_{2\mid(s+t)+(s-t)}(2(s+t)+1)(2(s-t)+1)x^{\frac{(s+t)(s+t+1)+(s-t)(s-t+1)}{2}}-\sum_{2\nmid(t+s)+(t-s-1)}(2(t+s)+1)(2(t+s-1)+1)x^{\frac{(t+s)(t+s+1)+(t-s-1)(t-s)}{2}}）$$
此时 $\sum$ 下的约束已经变成了废话，$i$ 和 $j$ 混在一起的乘积项也配成了平方差，可以分开，再做一些化简工作就有：
$$
\begin{aligned}
R&=\frac{1}{4}(\sum_{s,t=-\infin}^{\infin}((2s+1)^2-(2t)^2)x^{s(s+1)+t^2}-\sum_{s,t=-\infin}^{\infin}((2t)^2-(2s-1)^2)x^{s(s+1)+t^2})\\
&=\frac{1}{2}\sum_{s,t=-\infin}^{\infin}((2s+1)^2-(2t)^2)x^{s(s+1)+t^2}\\
&=\frac{1}{2}(\sum_{s=-\infin}^{\infin}(2s+1)^2x^{s(s+1)}\sum_{t=-\infin}^{\infin}x^{t^2}-\sum_{s=-\infin}^{\infin}x^{s(s+1)}\sum_{t=-\infin}^{\infin}(2t)^2x^{t^2})\\
&=\frac{1}{2}(\sum_{i=-\infin}^{\infin}(2i+1)^2x^{i(i+1)}\sum_{i=-\infin}^{\infin}x^{i^2}-\sum_{i=-\infin}^{\infin}x^{i(i+1)}\sum_{i=-\infin}^{\infin}(2i)^2x^{i^2})
\end{aligned}
$$
现在就很像是 $(1)$ 式的形式了，$x^{i^2}$ 自不必说，$x^{i(i+1)}$ 也可以通过带入 $k=x$ 来使用，问题就在只剩下了让 $x$ 的幂次前的系数消失。乍一看很棘手，其实仔细观察就会发现，前面的系数都能通过后面的次数的常数倍再加上常数来表示。具体地，我们有 $(2i+1)^2=4i(i+1)+1$，$(2i)^2=4i^2$，这就提醒了我们使用 $x\mathrm{D}$ 算符来让次数下来，其中 $\mathrm{D}$ 为微分算符。也就是说，我们有：
$$R=\frac{1}{2}((1+4x\mathrm{D})\sum_{i=-\infin}^{\infin}x^{i(i+1)}\sum_{i=-\infin}^{\infin}x^{i^2}-\sum_{i=-\infin}^{\infin}x^{i(i+1)}(4x\mathrm{D})\sum_{i=-\infin}^{\infin}x^{i^2})$$
之后就可以直接套 $(1)$ 式化简了，有：
$$
\begin{aligned}
R&=\frac{1}{2}((1+4x\mathrm{D})2\prod_{i=1}^{\infin}(1+x^{2i})^2(1-x^{2i})\times\prod_{i=1}^{\infin}(1+x^{2i-1})^2(1-x^{2i})-2\prod_{i=1}^{\infin}(1+x^{2i})^2(1-x^{2i})\times(4x\mathrm{D})\prod_{i=1}^{\infin}(1+x^{2i-1})^2(1-x^{2i}))\\
&=(1+8\sum_{i=1}^{\infin}\frac{2ix^{2i}}{1+x^{2i}}-4\sum_{i=1}^{\infin}\frac{2ix^{2i}}{1-x^{2i}})\prod_{i=1}^{\infin}(1+x^{2i})^2(1+x^{2i-1})^2(1-x^{2i})^2-(8\sum_{i=1}^{\infin}\frac{(2i-1)x^{2i-1}}{1+x^{2i-1}}-4\sum_{i=1}^{\infin}\frac{2ix^{2i}}{1-x^{2i}})\prod_{i=1}^{\infin}(1+x^{2i})^2(1+x^{2i-1})^2(1-x^{2i})^2\\
&=(1+8\sum_{i=1}^{\infin}(\frac{2ix^{2i}}{1+x^{2i}}-\frac{(2i-1)x^{2i-1}}{1+x^{2i-1}}))\prod_{i=1}^{\infin}(1+x^{2i})^2(1+x^{2i-1})^2(1-x^{2i})^2\\
&=(1+8\sum_{i=1}^{\infin}(\frac{2ix^{2i}}{1+x^{2i}}-\frac{(2i-1)x^{2i-1}}{1+x^{2i-1}}))\prod_{i=1}^{\infin}(1-x^i)^2(1+x^i)^4
\end{aligned}
$$
即：
$$
\begin{aligned}
\prod_{i=-\infin}^{\infin}(1-x^i)^6&=(1+8\sum_{i=1}^{\infin}(\frac{2ix^{2i}}{1+x^{2i}}-\frac{(2i-1)x^{2i-1}}{1+x^{2i-1}}))\prod_{i=1}^{\infin}(1-x^i)^2(1+x^i)^4\\
\prod_{i=1}^{\infin}(\frac{1-x^i}{1+x^i})^4&=1+8\sum_{i=1}^{\infin}(\frac{2ix^{2i}}{1+x^{2i}}-\frac{(2i-1)x^{2i-1}}{1+x^{2i-1}})
\end{aligned}
$$
看起来非常接近我们的目标了，接下来有：
$$(\sum_{i=-\infin}^{\infin}(-1)^ix^{i^2})^4=\prod_{i=1}^{\infin}(\frac{1-x^i}{1+x^i})^4=1+8\sum_{i=1}^{\infin}(\frac{2ix^{2i}}{1+x^{2i}}-\frac{(2i-1)x^{2i-1}}{1+x^{2i-1}})$$
别忘了取 $x=-x$，我们总算有答案的一个表达式了！接下来的部分就没什么特别的了，纯粹是 OGF 基本功，其实还是在用无穷求和中 $\mathbb{Z^+}$，$\mathbb{2Z^+}$ 和 $\mathbb{4Z^+}$ 间的关系化简，总之我们有：
$$
\begin{aligned}
ans=[x^n](\sum_{i=-\infin}^{\infin}x^{i^2})^4&=[x^n](1+8\sum_{i=1}^{\infin}(\frac{2ix^{2i}}{1+x^{2i}}+\frac{(2i-1)x^{2i-1}}{1-x^{2i-1}}))\\
&=[x^n](1+8\sum_{i=1}^{\infin}(\frac{2ix^{2i}}{1+x^{2i}}+\frac{ix^i}{1-x^i}-\frac{2ix^{2i}}{1-x^{2i}}))\\
&=[x^n](1+8\sum_{i=1}^{\infin}\frac{ix^i}{1-x^i}+8\sum_{i=1}^{\infin}(\frac{2ix^{2i}}{1+x^{2i}}-\frac{2ix^{2i}}{1-x^{2i}}))\\
&=[x^n](1+8\sum_{i=1}^{\infin}\frac{ix^i}{1-x^i}-8\sum_{i=1}^{\infin}\frac{4ix^{4i}}{1-x^{4i}})\\
&=[x^n](1+8\sum_{i\ge1,4\nmid i}\frac{ix^i}{1-x^i})\\
\end{aligned}
$$
观察展开式，有：
$$\frac{1}{1-x^i}=8\sum_{j=1}^{\infin}x^{ij}$$
也就是说，只有 $i\mid n$ 时才会对答案有 $i$ 的贡献，因此我们终于能写出答案的一个可计算的式子了！答案就是：
$$ans=8\sum_{i\mid n,4\nmid i}i$$