🔢 mathematics

Making Non-Negative Polynomials into Sums of Squares

本文建立了一套关于多项式空间上线性算子与半群的理论，具体构建了一种高效的变换，该变换能将具有非空内点的集合上的非负多项式映射为平方和，同时仅需极少的内存与计算操作。

原作者： Philipp J. di Dio

发布于 2026-06-15

📖 1 分钟阅读🧠 深度阅读

原作者： Philipp J. di Dio

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

想象一下，你有一个巨大的、杂乱无章的房间，里面堆满了各种物体。其中一些物体是“好的”（它们是非负的，即等于零或大于零），而另一些是“坏的”（它们是负数）。在数学的世界里，这些物体就是多项式（带有变量如 $x$ 和 $y$ 的方程）。

数学家们长期以来一直致力于解决一个特定的问题：如何将一个“好的”物体（它不是一个完美的平方，比如完美的立方体或完美的球体）转化为一个平方和（Sum of Squares）。

为什么这很重要？因为“平方和”是“好物体”中的“金标准”。它们易于检查、易于计算且非常稳定。如果你能将任何“好的”物体转化为“平方和”，你就能更快地解决极其困难的大型问题。

这篇论文旨在构建一台神奇的机器（一个线性算子），它能完成这项工作：它接收一堆杂乱的“好”多项式，并将它们转化为整齐有序的“平方和”堆。

以下是作者 Philipp di Dio 如何使用简单的概念来解释这台机器的运作机制的：

1. “时间旅行”机器

通常，如果你想改变一个形状，你可能会尝试拉伸或扭转它。但本文使用了一个流（flow）的概念。想象一下你有一个房间的视频。你按下“播放”，随着时间的推移，房间里的物体慢慢发生形变。

作者研究了一种特定的机器，它运行在一个“时间拨盘”（ $t$ ）上。当你向前转动拨盘时，机器会对多项式施加一种轻微且连续的推动。

目标： 找到正确的“推力”（生成元 $A$ ），使得如果你让机器运行一定的时间，每一个“好的”多项式最终都会变成一个“平方和”。
结果： 论文证明了，对于给定大小（次数/degree）内的多项式，存在一个特定的时间 $\tau$ ，如果你运行这台机器，所有的非负多项式都会变成平方和。

2. “无限图书馆”与“有限书架”

多项式可以是无限复杂的。你可能会有一个包含 $x^{1,000,000}$ 的多项式。

问题： 如果你试图同时为所有多项式构建一台机器，这就像是在试图整理一座无限大的图书馆。这样做效率极低，且几乎是不可能的。
解决方案： 作者意识到，在现实世界中，我们通常只关心一定大小范围内的多项式（例如，次数在 10 或 20 以内的多项式）。
魔术技巧： 论文表明，尽管图书馆是无限的，但机器每次只需要观察一个有限的书架。它将无限的图书馆视为一叠有限书架的堆叠。这使得机器可以在不陷入无限循环的情况下进行工作。

3. “超高效”计算器

这是论文中最令人惊讶的部分。通常，转换一个数字列表（矩阵）就像搬运一座大山。

旧方法： 如果你有 $N$ 个项目，转换它们通常需要大约 $N^3$ 步（例如，对于一个小列表，需要 $1,000,000$ 步）。这很慢，且计算成本很高。
新方法： 作者设计的机器非常特殊，它只需要大约 $N^2$ 步（例如，$1,000$ 步）。
“一键”逆运算： 更令人惊叹的是，如果你想撤销这个转换（回到最初杂乱的房间），这台机器不需要进行复杂的计算。它只需要执行一次简单的除法。这就像拥有一个能瞬间倒转时间的魔法按钮。

4. “不可能的任务”

论文还划定了一条界限。它证明了如果你试图为宇宙中的每一个多项式（而不限制其大小）做这件事，那是不可能的。

隐喻： 想象试图把无尽的海洋装进一个有限的水桶里。论文表明，无论你的机器多么聪明，如果你允许多项式的规模变得无限大，你就无法将每一个非负多项式转化为平方和。你必须设定一个大小限制（次数界限），魔法才能生效。

5. 窥见混沌（“非马尔可夫”示例）

在最后一部分，作者展示了当你使用一台并非这种完美、平滑流动的机器时会发生什么。他利用了一个流体力学中的方程（Burgers 方程）来展示，如果规则变化得过于剧烈，那些“好的”物体会在有限的时间内突然变成“坏的”（负数）。这就像一条平滑的河流突然撞上了瀑布，并陷入了混乱。这起到了警示作用：论文主体部分所描述的那种平滑、可预测的机器是非常特殊且必要的。

总结

这篇论文构建了一台数学时间机器，只要设置好正确的速度，它就能瞬间将任何“好的”多项式（在一定大小范围内）整理成完美的“平方和”。

它极其快速（比标准方法快得多）。
它是可逆的，且几乎无需任何代价。
它只有在限制多项式大小的情况下才能完美运行。

作者的核心观点是：“我们找到了一种方法，可以将一堆杂乱、难以检查的数字转化为一堆整洁、易于检查的数字，而且我们构建的这台机器运行成本之低，令人惊讶。”

技术摘要：将非负多项式转化为平方和形式

问题陈述
本文探讨了将非负多项式集合（记作对于闭集 $K \subseteq \mathbb{R}^n$ 的 $\text{Pos}(K)$ ）转化为平方和（SOS）锥（记作 $\Sigma \mathbb{R}[x_1, \dots, x_n]^2$ ）的挑战。虽然非负多项式和矩序列已得到广泛研究，但它们在计算上非常困难，因为并非所有非负多项式都是平方和（Motzkin, 1967），且并非所有平方正泛函都是矩泛函（Scheiderer, 1979）。作者研究了线性算子 $T: \mathbb{R}[x_1, \dots, x_n] \to \mathbb{R}[x_1, \dots, x_n]$ ，这些算子将 $\text{Pos}(K)$ 映射到 SOS 锥中，从而有效地对非负多项式集合进行“预处理”，使其变为更易处理的形式。这在优化应用中具有启发意义，即通过将在集合 $S$ 上的泛函最小化问题转化为在 $TS$ 上的最小化问题，可以提高数值稳定性或实现对基于 SOS 求解器的调用。

方法论
核心方法论依赖于正则 Fréchet 李群理论及其相关的李代数在多项式空间上的作用。

算子半群： 作者研究了形式为 $T_t = e^{tA}$ 的算子，其中 $A$ 是线性生成元。这类生成元的集合（记作 $\mathfrak{g}$ ）的特征是 $e^{tA}$ 对于所有 $t \in \mathbb{R}$ 都将多项式映射为多项式。
规范表示： 利用线性算子在多项式上的规范表示 $T = \sum q_\alpha \cdot \partial^\alpha$ ，本文通过定理 1.1 (来自 dD25) 将 $K$ -正性保持器与 $K$ -矩序列联系起来。
有限维不变子空间： 一个关键的技术工具是定理 3.3，该定理确立了对于任何 $A \in \mathfrak{g}$ ，都存在覆盖多项式环的有限维不变子空间序列 $V_i$ 。这使得无限维算子的指数可以通过这些有限子空间上的矩阵指数极限来计算。
特定算子构造： 为了实现从非负多项式到 SOS 的映射，作者构造了一个特定的秩一算子 $A$ ，其定义为 $Ap = \ell(p) \cdot f$ ，其中 $\ell$ 是在锥上正的线性泛函， $f$ 是目标 SOS 锥的一个内点。

主要贡献与结果

生成元的特征化 ( $\mathfrak{g}$ )： 本文完整地刻画了作为多项式环上良定义群的生成元集合 $\mathfrak{g}$ 。研究表明 $\mathfrak{g}$ 是一个锥，但不是向量空间（通常对于加法和乘法不封闭）。然而，拥有共同有限维不变子集的 $\mathfrak{g}$ 的子集构成了正则 Fréchet 李代数。
Stochel 定理（三线证明）： 作者提供了一个简洁的证明，用于证明 Stochel 定理 (2001)，该定理指出：一个序列是 $K$ -矩序列，当且仅当其截断是截断 $K$ -矩序列。该证明依赖于多项式与序列之间的对偶性以及 Haviland 定理。
$K$ -正性保持半群的生成元： 定理 6.3 提供了对于保持 $K$ -正性的生成元 $A \in \mathfrak{g}$ 的解算子描述。这推广了以往的结果，并提供了一个完整但抽象的特征化。
向平方和的转化 (定理 7.1)： 核心结果表明，对于固定的度数限制 $d$ ，存在线性算子 $T = e^{\tau A}$ ，能将任何非负多项式集合 $S \subseteq \text{Pos}(K)_{\le 2d}$ 映射到平方和锥 $\Sigma \mathbb{R}[x_1, \dots, x_n]^2_{\le d}$ 中。
计算效率： 本文强调了所构造算子 $T$ $T$ 的特定结构（对单位矩阵的秩一更新）带来了极高的计算效率：
- 内存： 存储算子矩阵 $\tilde{T}$ 仅需 $2N + 1$ 个标量（其中 $N = \dim \mathbb{R}[x]_{\le 2d}$ ），将存储需求从 $O(N^2)$ 降低到 $O(N)$ 。
- 复杂度： 矩阵-向量乘法 ($Tv $) 最多需要$ 4N + 1 $次运算。矩阵-矩阵乘法 ($ \tilde{T}M $) 最多需要$ 4N^2 + 1$ 次运算。
- 求逆： 计算逆算子 $\tilde{T}^{-1}$ 仅需一次操作（一次除法），这与标准矩阵求逆的 $O(N^3)$ 或更高复杂度形成鲜明对比。
不可能结果 (定理 7.5)： 本文证明了对于紧集 $K$ ，不存在单射线性算子 $T$ 能在没有度数限制的情况下将整个无限维锥 $\text{Pos}(K)$ 映射到 SOS 锥。这凸显了主定理中度数约束的必要性。
非马尔可夫示例： 第 8 节使用 Burgers 方程的示例说明了非齐次马尔可夫过程的时间演化，证明了 $e^{tA}$ 理论并不涵盖所有可能的多项式演化。

意义与主张
本文声称，所开发的理论提供了一种将非负多项式转化为平方和的可行计算方法，而由于非负性与 SOS 之间的差距，这一任务通常是困难的。其意义在于所提议变换的算法效率。通过利用具有特定结构属性的正则 Fréchet 李群中的算子，作者实现的复杂度达到了矩阵运算的平凡下界 ( $O(N^2)$ )，并将求逆简化为单次操作。

作者明确指出，虽然变换 $T$ 及其逆运算是高效的，但该方法受限于固定的度数限制。本文并不声称解决了将所有非负多项式表示为 SOS 的一般问题（这是不可能的），而是提供了一种工具，旨在将特定的非负多项式子集移动到 SOS 锥中，以用于优化或数值稳定性（预处理）。这项工作构成了无限维李群抽象理论与实际计算代数几何之间的桥梁。

1. “时间旅行”机器

2. “无限图书馆”与“有限书架”

3. “超高效”计算器

4. “不可能的任务”

5. 窥见混沌（“非马尔可夫”示例）

总结

类似论文