关于正定整系数n元二次型表示整数的通用算法问询
我最近刚入门二次型理论（只断断续续啃完了Conway和Fung那本《THE SENSUAL (quadratic) FORM》的第一讲），之前了解到一个叫15定理的结论——如果一个带整数矩阵的正定二次型能表示所有1到15的正整数，那它就能表示所有正整数。这让我好奇：有没有通用算法可以判断某个整数能不能被给定的正定整系数n元二次型表示？
先把问题严格化一下：给定正整数n，正定整系数n阶矩阵A，以及自然数k，是否存在通用算法找到（或判断是否存在）$x \in Kn$（K分别取$\mathbb{R}$、$\mathbb{Q}$、$\mathbb{Z}$）使得$xT A x = k$？我自己琢磨了一阵子，也调整了几次问题方向，现在把各个场景的疑问和梳理的结论整理如下：
Question 0：$K = \mathbb{R}$（实数域）的情况
这个其实是最简单的，答案是必然存在解，而且构造起来也很直接。因为A是正定矩阵，对应的二次型$x^T A x$在$x=0$时取到最小值0，而且随着x的模长不断增大，二次型的值可以无限变大。根据连续性，对于任意正整数k，肯定能找到实数向量x满足等式。甚至你可以手动构造解：随便找一个非零实向量$x_0$，计算$c=x_0^T A x_0$，然后取$x=\sqrt{k/c} \cdot x_0$，代入就能验证$x^T A x = k$。
Question 1：$K = \mathbb{Q}$（有理数域）的情况
这个属于有理二次型的经典数论问题，核心可以用Hasse-Minkowski定理来解决：一个有理二次型能表示有理数k，当且仅当它在所有局部域（包括$\mathbb{Q}$的p-adic完备化$\mathbb{Q}_p$，以及实数域$\mathbb{R}$）上都能表示k。
放在我们的场景里，A是正定的，所以$\mathbb{R}$上的可表示性已经满足（参考Question 0），剩下的就是对每个素数p，检查二次型在$\mathbb{Q}_p$上能不能表示k。这一步是有明确算法的：
- 首先可以把原二次型有理对角化（所有有理二次型都能做到），转化为更易处理的对角形式；
- 然后针对每个素数p，利用p-adic域上二次型的判别式、Hasse不变量等工具，判断k是否能被该二次型表示。
只要所有局部域的检查都通过，就说明存在有理解，而且也有算法可以构造出具体的有理向量x。
Question 2：$K = \mathbb{Z}$（整数域）的情况
这个是最复杂的，也是15定理这类结果聚焦的领域。我们可以分两步来思考：
- 先做有理解的判断：如果连有理解都不存在，那肯定没有整数解；如果存在有理解，我们可以把解的分母去掉，转化为判断$k \cdot m^2$（m是正整数）能否被原二次型以整数向量表示；
- 整数解的搜索与判断：
- 约化方法：正定二次型可以通过Lagrange约化、Hermite约化等方法转化为等价的“更简洁”的二次型，等价的二次型能表示的整数集合是完全相同的，这样可以大幅简化问题；
- 有限搜索+数论剪枝：因为正定二次型$x^T A x = k$，每个分量$x_i$的绝对值有上限（比如$x_i^2 \leq k / \lambda_{\text{min}}$，$\lambda_{\text{min}}$是A的最小特征值），所以搜索范围是有限的。虽然k很大时范围会变大，但结合数论必要条件（比如模某个数的剩余类限制）可以快速缩小搜索空间；
- 利用已知定理简化：比如15定理，要是你的二次型能表示1到15的所有正整数，那直接就能得出所有正整数都能被表示的结论；还有类似的290定理，针对更一般的正定整系数二次型场景。
另外你提到的那个“33问题”（无法用$x3+y3+z^3$表示的数）是三次型的问题，和二次型不是一回事，但二次型里确实也存在需要非常大整数解的情况。不过对于正定二次型，因为有明确的分量上限，理论上总能通过有限搜索找到解（或者证明不存在），只是效率问题。
还要提一下希尔伯特第11问题，这个问题本质上就是问有没有算法判断整数系数二次型能否表示给定整数。对于正定二次型，答案是存在算法的；而不定二次型的情况会更复杂，不过我们的问题聚焦正定场景，所以不用太担心。
备注：内容来源于stack exchange，提问作者Sirawit 'Plum' P.
