方程 x³+y³+z³=33 是否存在整数解？ 第1页

[文末有更新]

我们都知道暴力穷举是不现实的，那这次找到整数解的 Timothy Browning 是怎么算的呢？ 我试着去找了找他的算法。虽然他本人好像还没公布，但我搜到了之前的一些成果。Elsenhans and Jahnel (2009) 的搜索上界 是 ，Huisman (2016) 将上界提升到了 （并找到了 的整数解），这次 Browning 则是把上界进一步提高到了 。Elsenhans and Jahnel 与 Huisman 用的是同一种方法（该方法最早由Noam Elkies提出，感谢 @rainbow zyop 补充），可能 Browning 用的也是类似的方法吧。本来直接放上论文链接就结束了，但他们的文章中对具体方法的实现细节着墨很少，我也是费了一番功夫才感觉大致理解了他们的方法，所以这里就简单讲下我个人的理解。

首先，不妨假定 。问题等价于 ，此处 要远小于 （否则就直接穷举了）。两边同时除以 ，

此处 也可以是负数，我们可以不失一般性地假定 。由于 要比 小的多，因而 会是个很小的数。令 、 ，于是问题就变为了在曲线 附近找有理数点。因为 ，只需搜索 之间的值。

对于曲线上的一点 ，可以在其四周定义一个很小的平行四边形，其中两条边平行于 轴，另两条边平行于该点处切线。这个平行四边形可以由

表示。 和 的值是根据搜索的 和 的范围来确定的。接下来要做的就是在 范围内的一个个小平行四边形中找到所有的有理数点 ，然后计算对应的 ，看看是不是 33 或 -33 就行了。

令 的搜索上界为 ，即 。由上面的两个式子可以得到

加上 ，一共有三个约束条件。于是，我们其实是要解一个线性方程组

上面这个方程组共有四个解，加上原点正好组成一个棱锥，然后在棱锥中遍历所有的整数点就好了。但问题在于这个棱锥的高度会远大于另两个锥度，也就是说棱锥的顶点会非常尖。这样直接遍历的效率相当低。为了提高效率，我们可以把上面的方程组改写为

令这个矩阵的三个列向量分别为 。这三个向量可以看作是一个格（lattice） 的格基。现在问题就转化为了找到 上原点附近的一些格点对应的坐标 。这是一个已知的问题。先通过 LLL（Lenstra–Lenstra–Lovász）格基规约算法计算出 上近似正交的一组格基 ，再使用 Fincke-Pohst 算法就能找到所有满足条件的 了。

Huisman (2016) 提到他将上界提高到 总共用了大约 10万个CPU小时。我自己的科研中有些大的 case 会跑几百万CPU小时，所以按同样的方法把上界提高到 甚至 应该还是很可行的。

----

更新：感谢 @rainbow zyop 提醒，这次算出整数解的其实是 Andrew Booker（论文见此）。由于 Browning 把结果放在了自己的网页上，大家一开始就都以为是他解出来的。Booker 用的方法和之前的不太一样。上面说的方法适合于在一定范围的 （比如 ）中找到所有的整数解。但如果只是想针对具体的 （比如 33）来算的话，Booker 的方法更有效率。他计算了 等于 33 和 42 的情况，在 的范围内找到了 的一个解。这样，42 就成了 100 以内仅剩的一个还无解的数了。他的计算用了十几万CPU小时，比 Huisman (2016) 稍多一些，但在一个量级上。