命题

Lagrange 四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。

本篇文章将证明：每个正整数一定能表示成四个平方数之和，即对任意,不定方程

一定有解

引理

引理1：如果两个正整数可以表示成四个平方数之和，那么它们的乘积也是四个平方数之和。

证明：
不妨设:

从恒等式:

可以直接证明结论，不过我更想从线性代数角度推导一下这个式子。
考虑矩阵

从而 , 如果熟悉四元数乘法表的话，应该能注意到两者中蕴含某种联系，因此“四”平方和并非巧合的结果。

四元数乘法遵循以下的乘数表：

令

展开后即可得到上文所述恒等式。
由引理1和算数基本定理，我们将原命题转化为每个素数，均可表示为四个整数的平方和。
由于：

因此后文只需考虑奇素数的情况。

引理2：对于奇素数,同余方程

有解。

证明： 考虑 (p+1)/2 个整数 ， 其中 m 为 0, 1, …, (p-1)/2。 不难看到， 这些整数中的任意两个之差 $i2-j2 = (i+j)(i-j) $都不可能被 p 整除 (请读者想一想这是为什么？)， 这表明这些整数除以 p 所得的余数各不相同。
类似地， (p+1)/2 个整数 ， 其中 n 为 0, 1, …, (p-1)/2， 也具有同样的性质， 即除以 p 所得的余数各不相同。
现在把这两组数合在一起， 它们共有 p+1 个， 且各不相同 (为什么？)。 由于任何整数除以 p 所得的余数只能有 p 种可能性， 因此这两组数中起码有两个数除以 p 所得的余数相同。 如上所述， 这两个数必定分属两组， 这表明存在某个 与某个 ， 它们的差可以被 p 整除， 即： (k 显然为正整数)。 Q.E.D.
顺便提一下， 引理三事实上对任何奇数 p 都成立， 但我们的证明只适用于 p 为奇素数的情形 (对于我们的目的来说， 这就足够了)。 感兴趣的读者不妨思考一下， 我们的证明在什么地方有赖于 p 是素数这一条件？
由抽屉原理， 遍历 得到p+1个数，由于 和 自身两两不同余，所以必有 , 使得：

证毕。

引理3：对于奇素数,一定存在正整数, ,使得：

证明：事实上，取引理得到的解

由于

因此

原命题证明

由引理2知道：
存在, ,使得：

不妨设为满足条件的最小正整数，我们来证明 , 现在假设
事实上一定有 , 这是因为如果 , 取其素因子 ,必有 ,假如 则两边同时除以, 与最小性矛盾。
假如 ,那么 ,与 矛盾。
其次一定有为奇数， 假如是偶数，注意到右式中四个数必有偶数个奇数，故不妨设：

注意到恒等式:

因此

与最小性矛盾。

取为模的绝对最小剩余，

也就是

这里用到了是奇数

因此


因此设

假如, 不难得到,这与引理二的互素矛盾。
因此

由引理一：

其中如引理得到的形式表达

又因为


两边同时除以得到与最小性矛盾的式子：

因此整个定理证毕

拓展

细心的读者也许会注意到 Lagrange 四平方定理只是说任何一个正整数都可以表示成不超过四个整数的平方之和。 原则上这个表述并不排除任何一个正整数都可以表示成不超过三个整数的平方和之类的可能性。 但这种可能性是可以很容易地被排除的， 因为有一些正整数， 比如 ， 不可以写成少于四个整数的平方之和。 因此对于全体正整数而言， Lagrange 四平方定理中的 “四” 已经是最佳结果， 是不可以缩小的。

Lagrange 四平方定理是一些更普遍的定理的特例， 其中最著名的一个是 Fermat 多边形数定理， 另一个则是 Waring 问题， 我们分别简单提一下：

Fermat 多边形数定理 (Polygonal number theorem)： 任何一个正整数都可以写成不超过 n 个 n-边形数之和。

所谓 n-边形数， 指的是可以排列成正 n-边形的数， 比如三角形数是可以排列成正三角形的数， 即形如 1, 1+2, 1+2+3, …, 的数； 四边形数则是可以排列成正四边形 (即正方形) 的数， 如 1, 4, 9, 16， 也就是平方数 (因此四边形数定理就是 Lagrange 四平方定理)。 这个定理顾名思义， 是由 Fermat 首先提出的， 时间是 1638 年。 Fermat 声称自己有关于这一定理的证明， 但和他的许多类似声称一样， 人们从来没有找到过他的 “证明”。 这个定理真正的证明最早是由 Augustin Cauchy (1789-1857) 于 1813 年给出的。

Waring 问题： 对所有正整数 k， 存在一个相应的正整数 w(k)， 使得所有正整数都可以表示成不超过 w(k) 个正整数的 k 次方之和。

这个问题是 Edward Waring (1736-1798) 于 1770 年 (即 Lagrange 证明四平方定理的那一年) 提出的， 证明则是由 David Hilbert (1862-1943) 于 1909 年给出的。 对于 Waring 问题来说， 确定 w(k) 的最小可能值是一个很有意义的研究课题， 我们把这一最小可能值记为 g(k)。 Hilbert 的证明并没有给出 g(k) 的具体数值， 许多其他数学家对此做了研究， 其结果是： g(1)=1； g(2)=4 (即 Lagrange 四平方定理)； g(3)=9， g(4)=19， g(5)=37 (这是中国数学家陈景润于 1964 年证明的)。 而对于 k>5， 人们有一个猜测： %20%3D%20floor((3%2F2)%5Ek)%20%2B%202%5Ek%20-%202#card=math&code=g%28k%29%20%3D%20floor%28%283%2F2%29%5Ek%29%20%2B%202%5Ek%20-%202&id=Kra00)， 其中 floor(x) 为不大于 x 的最大整数。 这个猜测可以被证明是成立的， 前提是有人能够证明 %5Ek#card=math&code=%283%2F2%29%5Ek&id=oCO6D) 的分数部分小于或等于 %5Ek#card=math&code=1-%283%2F4%29%5Ek&id=JRH8q)。 但 - 你相信吗？ - 这个看似只有中学程度的不等式却是一个至今尚未得到证明的数学命题！

四平方和定理的一些推论

推论1：“四”不能被改进为“三”

事实上：时，不能表示成三个整数的平方和。

证明：考虑

两边mod 得到矛盾。
这是因为

高斯证明了更一般的结论：
不能表示成三个整数的平方和当且仅当

推论2：除去 每个正数都可以表示为五个正平方数之和

证明：注意到

时可以直接验证结论成立，
时，由四平方和定理：

再根据 中0的数量用关于的恒等式补齐即可证毕。

推论2的补充：

事实上推论2中的5从某种程度上来说同样不能被改进，这是因为：
时，不能表示为四个正数平方和。
这是因为：
对归纳， 时， 结论显然成立。假如 时结论成立， 若时结论不成立，有：

mod 知左式中四个数全为偶数

因此

矛盾！

LeetCode题目

279. Perfect Squares

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

动态规划思路

我们可以依据题目的要求写出状态表达式：表示最少需要多少个数的平方来表示整数$ i$。

这些数必然落在区间 。我们可以枚举这些数，假设当前枚举到 ，那么我们还需要取若干数的平方，构成 。此时我们发现该子问题和原问题类似，只是规模变小了。这符合了动态规划的要求，于是我们可以写出状态转移方程。

其中 为边界条件，实际上我们无法表示数字 0，只是为了保证状态转移过程中遇到 恰为 $\sqrt{i} $的情况合法。

同时因为计算 时所需要用到的状态仅有 ，必然小于 ，因此我们只需要从小到大地枚举 i 来计算 即可。

代码

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1);
        for (int i = 1; i <= n; i++) {
            int minn = INT_MAX;
            for (int j = 1; j * j <= i; j++) { //注意这里使用条件j * j <= i
                minn = min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
};

复杂度分析

• 时间复杂度：#card=math&code=O%28n%5Csqrt%7Bn%7D%29&id=LIZmv)，其中 n 为给定的正整数。状态转移方程的时间复杂度为 #card=math&code=O%28%5Csqrt%7Bn%7D%29&id=uxvNN)，共需要计算 n 个状态，因此总时间复杂度为 #card=math&code=O%28n%20%5Csqrt%7Bn%7D%29&id=DryQp)。
• 空间复杂度：#card=math&code=O%28n%29&id=W0fWz)。我们需要 #card=math&code=O%28n%29&id=rWy1V)的空间保存状态。

四平方和定理

四平方和定理 （英语：Lagrange’s four-square theorem） 说明每个正整数均可表示为4个整数的平方和。它是费马多边形数定理和华林问题的特例。

四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界。

同时四平方和定理包含了一个更强的结论：当且仅当 #card=math&code=n%20%5Cneq%204%5Ek%20%5Ctimes%20%288m%2B7%29&id=EMMMR)时，n 可以被表示为至多三个正整数的平方和。因此，当 #card=math&code=n%20%3D%204%5Ek%20%5Ctimes%20%288m%2B7%29&id=NcwYc) 时，n 只能被表示为四个正整数的平方和。此时我们可以直接返回 4。

当 #card=math&code=n%20%5Cneq%204%5Ek%20%5Ctimes%20%288m%2B7%29&id=GSQlX)n时，我们需要判断到底多少个完全平方数能够表示 n，我们知道答案只会是 1,2,3中的一个：

• 答案为 1 时，则必有 n 为完全平方数，这很好判断；
• 答案为 2 时，则有 ，我们只需要枚举所有的 #card=math&code=a%281%20%5Cleq%20a%20%5Cleq%20%5Csqrt%7Bn%7D%29&id=pV55u)，判断 是否为完全平方数即可；
• 答案为 3 时，我们很难在一个优秀的时间复杂度内解决它，但我们只需要检查答案为 1 或 2 的两种情况，即可利用排除法确定答案。

代码

class Solution {
public:
    // 判断是否为完全平方数
    bool isPerfectSquare(int x) {
        int y = sqrt(x);
        return y * y == x;
    }

    // 判断是否能表示为 4^k*(8m+7)
    bool checkAnswer4(int x) {
        while (x % 4 == 0) {
            x /= 4;
        }
        return x % 8 == 7;
    }

    int numSquares(int n) {
        if (isPerfectSquare(n)) {
            return 1;
        }
        if (checkAnswer4(n)) {
            return 4;
        }
        for (int i = 1; i * i <= n; i++) {
            int j = n - i * i;
            if (isPerfectSquare(j)) {
                return 2;
            }
        }
        return 3;
    }
};

复杂度分析

• 时间复杂度：#card=math&code=O%28%5Csqrt%7Bn%7D%29&id=QakPH)，其中 n 为给定的正整数。最坏情况下答案为 3，我们需要运行所有的判断，而判断答案是否为 1 的时间复杂度为 #card=math&code=O%281%29&id=gF9F3)，判断答案是否为 4 的时间复杂度为 #card=math&code=O%28%5Clog%20n%29&id=IMhxH)，剩余判断为 #card=math&code=O%28%5Csqrt%20n%29&id=QjNp4)，因此总时间复杂度为 %20%3D%20O(%5Csqrt%20n)#card=math&code=O%28%5Clog%20n%20%2B%20%5Csqrt%20n%29%20%3D%20O%28%5Csqrt%20n%29&id=S1Lv4)。
• 空间复杂度：#card=math&code=O%281%29&id=amTY9)。我们只需要常数的空间保存若干变量。

参考资料

Lagrange 四平方定理 初等数论随笔