🔢 mathematics

The largest 5th pivot may be the root of a 61st degree polynomial

本文通过结合 JuMP、Gröbner 基、判别式多项式及区间算术等数值与精确计算技术，证明了 1988 年发现的 $n=5$ 时高斯完全主元消去法最大增长因子 $4.1325\dots$ 精确对应一个 61 次多项式的根，并将该情形下的理论上界从 $4.94 $降低至$ 4.84$。

原作者： James Chen, Alan Edelman, John Urschel

发布于 2026-03-17

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： James Chen, Alan Edelman, John Urschel

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个关于数学计算稳定性的古老谜题，以及作者们如何用一种“数学 + 计算机”的混合魔法，终于找到了这个谜题在特定情况下的精确答案。

为了让你轻松理解，我们可以把这篇论文的故事想象成一场**“寻找最陡峭山峰”**的探险。

1. 背景：什么是“高斯消元”和“增长因子”？

想象你正在整理一堆杂乱的数字表格（矩阵），想要把它们变成一种更整齐、更容易计算的形式（上三角矩阵）。这个过程叫高斯消元法，是计算机处理线性方程组最基础的工具。

在这个过程中，计算机需要不断地做除法，把数字变小或变大。

增长因子（Growth Factor）：就是衡量在这个过程中，数字变得有多大的一个指标。
为什么这很重要？ 如果数字变得太大（比如从 1 变成了 1 亿），计算机的内存就会溢出，或者因为精度不够算出错误的结果。所以，数学家们非常关心：在最坏的情况下，数字最多能变大多少？

这就好比你在玩一个游戏，规则是每次操作都可能让分数翻倍。大家想知道：玩到第 5 关时，分数最高能涨到多少？

2. 谜题：第 5 关的“最高分”是多少？

对于这种“完全主元高斯消元”（一种非常谨慎、总是选最大数字做除数的策略），数学家们早就知道前几关的答案：

第 1 关：最大增长 1 倍。
第 2 关：最大增长 2 倍。
第 3 关：最大增长 2.25 倍。
第 4 关：最大增长 4 倍。

但是，到了第 5 关（5x5 的矩阵），大家卡住了。
几十年来，超级计算机用各种算法疯狂计算，发现了一个数值：4.1325...。
大家一直怀疑这就是最终答案，但没人能100% 证明它不是 4.1326，或者 4.13250001。因为可能的数字组合太多了，就像大海捞针。

3. 作者的“魔法”：如何找到精确答案？

这篇论文的作者（James Chen, Alan Edelman, John Urschel）没有继续盲目地用计算机“猜”数字，而是发明了一套**“先猜后证”**的绝妙组合拳：

第一步：用“直觉”找线索（数值优化）

他们先用现代软件（JuMP）像侦探一样，在数字的海洋里快速搜索，找到了那个看起来像“最高峰”的地方，数值大约是 4.1325...。

比喻：就像你在迷雾中用无人机快速扫描，发现了一座看起来最高的山。

第二步：用“代数”画地图（格罗布纳基）

一旦找到了这座山，他们不再看具体的数字，而是把这座山的形状用数学公式（多项式）描述出来。
他们发现，这个神秘的数字 4.1325... 并不是一个随机的无限小数，而是一个极其复杂的方程的根。

比喻：他们发现这座山不是随便长在那里的，而是由一个巨大的、有 61 层楼的数学公式（61 次多项式）严格定义的。只要解出这个公式，就能得到精确的坐标。

第三步：用“筛子”过滤（判别式）

为了证明这个公式里的根就是真正的“最高峰”，他们用了更高级的数学工具（判别式），像筛子一样，把那些不符合条件的“假山峰”全部筛掉，只留下了唯一的一个真答案。

结果： 他们证明了，4.1325... 这个数，精确地等于一个61 次多项式方程的唯一实数根。
这意味着，这个数不再是“看起来像”，而是数学上确凿无疑的。

4. 顺便做的“防守”：证明没有更高的山

除了证明“最低”有多高（下界），他们还试图证明“最高”不会超过多少（上界）。
以前大家知道最高不会超过 4.94。
作者们用一种叫“区间算术”的方法（把数字看作一个范围，而不是一个点），结合严密的逻辑推理，把这个上限从 4.94 降低到了 4.84。

比喻：以前大家说“山顶最高不超过 5000 米”，现在他们通过更精细的测量，说“其实最高不超过 4840 米”。虽然还没完全重合，但范围缩小了很多。

5. 总结与意义

这篇论文的核心成就在于：

揭示了数学之美：那个困扰了大家几十年的数字 4.1325...，竟然是一个61 次多项式的根。这就像发现了一个看似随机的自然现象，背后竟然有一个极其复杂但完美的数学结构。
方法论的创新：他们展示了如何将数值计算（快但不精确）和符号代数（慢但绝对精确）完美结合。先用计算机找方向，再用数学证明真理。
未来的猜想：作者们大胆猜想，这个 4.1325... 就是 5x5 矩阵的绝对最大值。虽然要完全证明这一点（排除所有其他可能性）还需要更多的创新，但这已经是最接近真相的一步了。

一句话总结：
作者们用“计算机找路 + 数学画地图”的方法，终于把那个困扰了 30 多年的数字谜题，从“大概是这样”变成了“精确的数学公式”，并发现这个神秘数字竟然藏在一个 61 层的数学迷宫里。

这是一份关于论文《The Largest 5th Pivot May Be the Root of a 61st Degree Polynomial》（最大的第 5 个主元可能是 61 次多项式的根）的详细技术总结。

1. 研究背景与问题 (Problem)

核心问题： 在高斯消元法（Gaussian Elimination）中使用**完全主元（Complete Pivoting）**策略时，**增长因子（Growth Factor）**的最大可能值是多少？

定义： 增长因子 $g(A)$ 定义为消元过程中出现的最大元素绝对值与初始矩阵最大元素绝对值的比值。它是衡量高斯消元数值稳定性的关键指标。
历史背景： 对于 $n \times n$ 矩阵，当 $n=1, 2, 3, 4$ 时，最大增长因子分别为 $1, 2, 2.25, 4$。
待解之谜： 对于 $n=5$ ，自 1960 年代以来，数值优化方法（如 1988 年的 NPSOL、1991 年的 LANCELOT 以及 2024 年的 JuMP）一致发现了一个约为 4.1325 的最大值。然而，长期以来无法确定这是否是理论上的最大值，也无法确定该数值的确切数学形式（即它是否是一个代数数，以及其对应的多项式次数）。
现有界限： 1969 年 Tornheim 给出的上界为 $4 \frac{17}{18} \approx 4.94$ 。

2. 方法论 (Methodology)

本文提出了一种结合数值优化与精确代数计算的混合方法，旨在解决这一复杂的非线性优化问题。主要技术路线包括：

数值优化引导 (JuMP)：
- 首先使用 Julia 语言的数学规划包 JuMP 进行大规模数值优化，寻找 $n=5$ 时增长因子最大的候选矩阵。
- 数值结果不仅给出了 $g \approx 4.1325$ 的近似值，还揭示了矩阵中哪些元素之间的约束是“紧”的（即取等号），从而确定了需要研究的特定代数结构。
精确代数推导 (Gröbner Basis)：
- 基于数值优化发现的紧约束结构，将问题转化为多项式方程组。
- 利用 Gröbner 基（Gröbner Basis） 计算来消除非线性变量。Gröbner 基是一种将多项式理想转化为特定基底的算法，能够有效地消去变量，将多变量方程组简化为单变量方程。
- 在此过程中，作者将矩阵元素和增长因子 $g$ 视为变量，通过消除中间变量（如 $x, y, z$ ），最终得到一个仅关于 $g$ 的高次多项式。
判别式优化 (Discriminant Polynomial)：
- 为了在约束条件下找到 $g$ 的极值，作者使用了**判别式（Discriminant）**技术。
- 通过计算关于某个参数（如 $z$ ）的多项式的判别式，找出使方程组有重根（即极值点）的 $g$ 值。这使得在代数上精确求解最大值成为可能，避免了数值舍入误差。
区间算术与分支定界 (Interval Arithmetic & Branch-and-Bound)：
- 为了证明该数值确实是全局最大值（或改进上界），作者结合了区间算术。
- 通过构建 $3 \times 3$ 子矩阵的覆盖集（Covers），利用分支定界算法严格验证某些区域不存在满足条件的矩阵，从而排除其他可能的解，并改进理论上的上界。

3. 主要贡献与结果 (Key Contributions & Results)

A. $n=5$ 的精确解

61 次多项式根： 论文证明了数值观察到的 $4.1325\dots$ $4.1325 \dots$ 实际上是某个61 次整系数多项式 $P_5(g)$ 的唯一实根，且该根位于区间 $[4, 5]$ $[4, 5]$ 内。
- 该多项式的系数极其巨大（例如常数项约为 $-4 \times 10^{79}$ ），展示了问题的代数复杂性。
- 给出了该根的 200 位小数精度： $g \approx 4.13251707863247285422\dots$
猜想 (Conjecture 2.1)： 作者提出猜想，认为这个由特定约束结构导出的下界，实际上就是 $n=5$ 完全主元消元的最大增长因子。虽然由于组合爆炸无法穷尽所有约束结构，但在 JuMP 建议的约束集下，该值已被证明是紧的（Theorem 2.2）。

B. 上界的改进

利用数学分析与区间算术，作者将 $n=5$ 的最大增长因子的上界从 1969 年的 $4.94$ 降低到了 4.84 (Theorem 3.5)。
虽然 4.84 与 4.1325 之间仍有差距，但这证明了通过结合区间算术和子矩阵分析可以进一步收紧界限。

C. 更高维度的结果 ( $n=6, 7, 8$ )

该方法被推广到 $n=6, 7, 8$ 的情况：

$n=6$ ： 最大增长因子为 5。
$n=7$ ： 最大增长因子是某个 6 次多项式 的根，约为 6.0569。
$n=8$ ： 最大增长因子为 8（由 Sylvester 的 Hadamard 矩阵达到，但也存在非 Hadamard 矩阵达到此值）。

D. 序列的新发现

如果猜想成立，最大增长因子序列 $n=1$ 到 $8$ 为：
$1, 2, 2.25, 4, \text{(61 次多项式根)}, 5, \text{(6 次多项式根)}, 8$ 。
这是一个令人惊讶的数学序列，揭示了数值线性代数中增长因子行为的深层代数结构。

4. 技术细节与数学意义

代数复杂性： 论文展示了最大增长因子是一个代数数。根据 Tarski-Seidenberg 定理，它必然是代数数，但此前对其次数上限的估计（ $n=5$ 时为 $1024$ 次）过于悲观。本文将其精确降为 61 次。
混合计算范式： 本文是“数值计算”与“精确符号计算”完美结合的典范。数值优化用于“猜测”结构，符号计算（Gröbner 基）用于“证明”精确值，区间算术用于“验证”全局性。
对 Nick Higham 的致敬： 论文特别致敬了已故的数值线性代数大师 Nick Higham，他长期关注高斯消元的增长因子问题，并推动了该领域的研究。

5. 总结与意义 (Significance)

这篇论文解决了数值线性代数中一个长达数十年的开放问题（关于 $n=5$ 增长因子的精确形式）。

理论突破： 首次给出了 $n=5$ 最大增长因子的精确代数描述（61 次多项式的根），打破了以往仅靠数值近似的局面。
方法创新： 建立了一套通用的方法论（JuMP + Gröbner Basis + Discriminant），可用于解决其他涉及复杂多项式不等式约束的优化问题。
实际影响： 虽然 $n=5$ 是较小的维度，但该研究加深了对高斯消元稳定性的理解，并为分析更大规模矩阵的数值行为提供了新的理论工具和思路。

简而言之，这项工作不仅给出了一个具体的数字，更重要的是揭示了该数字背后深刻的代数结构，并展示了现代计算数学工具在解决经典理论问题中的强大能力。