精读笔记

Problem Setting

论文标题：Sum-of-squares certificates for symmetric polynomials on the hypercube: a counterexample to a conjecture of De Klerk and Laurent（arXiv preprint / 2026）。

这篇论文实际处理的不是一般超立方体优化，也不是一般 Putinar bound，而是一个非常尖锐的 SoS membership threshold 问题：对偶数 n，最小 C_n 使得 x_1...x_n+C_n 属于 degree-n truncated quadratic module M_{n,n}(x_i-x_i^2)。De Klerk–Laurent 猜测 C_n=1/(n(n+2))；本文只需构造一个严格更小的可行 C 即可推翻“最优性”。

真正困难点有两个。第一，M_{n,n} 的证书空间很大，直接 Gram SDP 搜索不可控，尤其还要从浮点结果转成严格证书。第二，对称性不是标准 invariant SoS 的情形：目标多项式是 S_n-invariant，但生成元 g_i=x_i-x_i^2 本身不是 invariant，只是构成一个 S_n-invariant set。因此不能简单把所有东西投到 S_n-invariant polynomial cone 里，否则会丢掉 multiplier 的正确自由度。

以前方法卡在“小 n 数值验证 + n=2 显式公式”。这些证据足以形成猜想，但不足以说明最优性。关键矛盾是：猜想看起来由对称性强烈约束，但真正的 quadratic module 证书可能利用非平凡表示分量和 stabilizer multiplier 产生比纯对称直觉更低的常数。

Motivation

已有路线关注的是 explicit Putinar-type error bounds：如果能证明 x_1...x_r+1/(r(r+2)) 属于 M_{r,r}，就能把 Bernstein/preordering 证书转成 quadratic module 证书，并得到 O(r^{-2}) 级别的 monomial correction。注意，应用真正需要的是 membership upper bound，不是 minimality。De Klerk–Laurent 猜测的是更强的最优性，而本文正是攻击这个更强部分。

作者的核心观察是：猜测的最优性证据太依赖低维现象。n=2,4,6 的 tightness 可能只是小规模 SDP 的偶然，而不是结构定理。要检验它，需要一个能处理 n=8 的精确证书搜索框架。

关键缺口不是“没有 SDP”，而是没有适合 hypercube quadratic module 的对称化方式。标准 Gatermann–Parrilo invariant SDP 处理 invariant SoS；这里 multiplier 跟随生成元索引一起变换。于是自然的缺失对象是：针对 generator orbit 的 stabilizer-based reduction。本文填的就是这个缺口。

Core Idea

核心思想可以概括为：不要把 hypercube quadratic module 强行看成一个完全 S_n-invariant SoS cone，而要把它看成由一个 S_n-orbit of generators 诱导的 equivariant cone。对于对称 p，任何证书都可以平均化；平均化之后，主 SoS 项可以取 S_n-invariant，而所有 multiplier 可以由一个固定坐标 n 的 multiplier ρ 通过 transposition (i n) 生成。这个 ρ 只需对 stabilizer Stab(n)≅S_{n-1} 不变。

这个建模方式的本质变化是：证书搜索从“n 个独立 multiplier + 一个主 SoS”变成“一个全局 invariant SoS + 一个局部 stabilizer-invariant multiplier 的轨道”。它保留了非平凡 multiplier 的表达能力，又使表示论 block diagonalization 可用。相比 prior 的本质区别不是发明了新的 SoS 定理，而是把已有 symmetry reduction 正确放进“生成元集合不变但单个生成元不变”的 quadratic-module 语境。

直觉上它有效，是因为 x_1...x_n 本身没有偏好坐标；任何非对称证书都可以通过群平均变成轨道证书。平均不会破坏 SoS 或 degree bound。真正需要追踪的是 multiplier 与 g_i 的配对关系，而 stabilizer 正好编码“固定一个生成元后剩余自由度”。

Method

1. 证书规范化：Proposition 2.1 证明对称 p 属于 M_{n,2d} 当且仅当存在 S_n-invariant SoS σ 和 S_{n-1}-invariant SoS ρ，使 p=σ+∑_i ((i n)ρ)(x_i-x_i^2)。它解决的是对称目标下 multiplier 冗余的问题；必要性来自群平均；核心变化是把 quadratic module 的对称性表达为 orbit-stabilizer 结构。

2. Block diagonalization：对 σ 使用 S_n 代表向量，对 ρ 使用 S_{n-1} 代表向量，按 Specht modules 将 Gram matrices 分块。它解决的是 Gram SDP 规模问题；必要性来自 n=8 已经超出朴素 SDP 可操作范围；核心变化是 PSD 约束从单个大矩阵变成少数 representation blocks。

3. 稀疏支持发现：数值 SDP 显示 n=8 只需 Q_(8), Q_(6,2), Q_(5,3), R_(7) 等少数 blocks，再通过设置若干 diagonal entries 为零进一步缩小 active basis。这个步骤在证明中不是理论必要条件，而是 certificate mining。它解决的是从可解 SDP 到可 rationalize 证书的距离；核心变化是降低最终有理系统维度。

4. 有理化与精确验证：固定 C=11/1000，在 active support 上求一个带 PSD margin 的数值解；将 Gram entries 舍入为有理数，再用 A^T(AA^T)^{-1} 修正回精确 coefficient matching affine space；最后用有理主子式检查 PSD。它解决的是 numerical SDP 不能证明 membership 的问题；核心变化是把所有 heuristic 留在搜索阶段，把最终定理建立在 exact rational certificate 上。

Key Insight / Why It Works

最核心的贡献是 Proposition 2.1 所体现的 orbit-stabilizer SoS reduction。它不是普通降维，而是抓住了 hypercube quadratic module 的正确等变结构：g_i 单个不 invariant，但索引集合是 group orbit；固定一个 generator 后，剩余对称性就是 stabilizer。这个结构一旦写对，后面的 Specht block diagonalization 基本是标准工具。

真正有效的原因不是 SDP solver 更强，而是 latent symmetry 被正确暴露了。原问题的自由度主要来自 monomial orbits 与 irreducible representation multiplicities；直接 monomial Gram matrix 会把这些重复结构混在一起。block reduction 将等价自由度压缩，并把可能需要的非平凡表示分量显式列出。n=8 的反例也说明：只看 trivial/invariant intuition 可能低估证书空间；非平凡 Q_(6,2), Q_(5,3) block 参与后，常数可以低于猜测值。

稀疏化和 rational rounding 是辅助但关键的工程层。它们不解释为什么 11/1000 存在，只让证书可被发现和验证。这里的增益很大一部分是 symbolic/numeric hybrid engineering：高精度 SDP 找模式，人工/启发式剪枝找小支持，有理线性代数完成证明。若问“理论 insight”，应归因于 stabilizer reduction；若问“实际反例怎么拿到”，则主要归因于 numerical certificate mining。

文中关于 Boolean quotient 的观察很有意思：degree n 的 quadratic-module threshold 数值上似乎等于 Boolean/preordering threshold。若这是真的，De Klerk–Laurent 常数由 Boolean moment problem 决定，而不是由完整 polynomial quadratic module 决定。但目前只是 observation；文中未充分说明为什么 quadratic module 会在这个特殊族上达到 preordering/Boolean relaxation 的值。

Relation To Prior Work

最接近的技术谱系是 Gatermann–Parrilo 的 symmetry reduction for SoS/SDP，以及后续 symmetric polynomial optimization 中基于 S_n 表示论的 block diagonalization。本文没有在表示论本身上做根本创新；Young tableaux、Specht modules、representative sets 都是已有机制。

真正新增的是把这些机制用于“约束生成元形成群轨道”的 truncated quadratic module。prior invariant SoS 通常假设被表示的 SoS polynomial 本身 invariant；本文还要处理 ∑ σ_i g_i 中 σ_i 和 g_i 的协同变换。因此 S_n/S_{n-1} 双层结构是实质创新点。

和 De Klerk–Laurent 的关系上，本文不是改进其 Putinar bound 路线，而是拆掉其中一个更强的最优性猜想。它并不否定 x_1...x_n+1/(n(n+2)) 的 membership，也不否定相关 error bound 应用；反而 n=8 的更小 C 说明原 upper bound 仍然成立但不 tight。

和 Magron、Baldi–Slot、Gribling–de Klerk–Vera 等 quantitative Putinar/Lasserre 工作相比，本文问题更窄、更证书导向。那些工作研究一般 degree bounds/convergence rates；本文研究一个特殊 correction constant 的精确/反例性质。它的价值不是给出新的通用收敛率，而是揭示低维数值猜想在 SoS cone 中可能被非平凡表示分量打破。

Dataset / Evaluation

这里没有机器学习意义上的 dataset。evaluation 是数值 SDP + 精确证书验证。对论文核心 claim 来说，最重要的 evaluation 是 n=8 的 rational certificate：系数匹配在 Q 上精确成立，Gram blocks 的 PSD 也在 Q 上精确验证。这已经完全支撑“反驳最优性猜想”这一 claim。

表格中 n≤12 的 numerical SDP values 主要提供现象学证据：从 n=8 开始，C_{n,n} 明显低于 1/(n(n+2))，并暗示后续偏离更大。它们支持“猜想不是偶然只在 n=8 失败”的直觉，但不能作为数学结论。作者也明确说这些数值 optimum 不用于证明。

评估覆盖范围很窄：只围绕 x_1...x_n+C 和若干 degree choices C_{n,2d}。没有证明一般 symmetric polynomial 的实际效果，也没有展示该 reduction 在其他 semi-algebraic sets 上的系统表现。因此 evaluation 足以验证 counterexample，不足以验证广泛可扩展性或一般方法优越性。

Limitation

第一，论文没有给出 C_8 的最优值，只给出 C_8≤11/1000。数值 optimum 约为 0.010717，小于 0.011，但 exact certificate 没有达到该数值；因此最优阈值仍未被严格刻画。

第二，稀疏 block/support 的选择是启发式的。文中说移除某些 block 会导致 infeasible 或 objective 变差，但这不是结构定理。为什么 Q_(8), Q_(6,2), Q_(5,3), R_(7) 足够，为什么其他 block 可删，增益来源不清。这里很可能主要是 problem-specific certificate mining，而不是可预测的理论机制。

第三，scalability 上限不明确。表示论 reduction 能显著降维，但随着 n 和 d 增大，representative vectors、coefficient orbits、block sizes 仍会快速增长。exact rational verification 也可能成为瓶颈。本文展示 n=8 反例和 n≤12 数值探索，但没有说明这种 exact pipeline 能推到一般 n。

第四，Boolean quotient 现象目前只是数值观察。若未来证明 C_{n,n}^{bool}=C_n，那么本文证书可能只是完整 quadratic module 在这个特殊族上模拟 Boolean relaxation 的表现；若不成立，则当前数值模式可能是小 n 偶然。文中未充分说明这一机制。

第五，论文的理论影响要谨慎定位：它推翻的是 minimality conjecture，不是 Putinar-type upper bound 的可用性。若读者关心 general polynomial optimization error bounds，这篇论文更多是在校正常数 tightness 上给警示，而不是直接提供更强的一般 bound。

Takeaway

• 1. 对称 SoS 中最容易出错的是把“目标 invariant”误读成“所有证书组成部分都 invariant”。
• 当约束生成元只作为集合 invariant 时，正确对象是 stabilizer multiplier 的 orbit。
• 这一建模 insight 很值得迁移。
• 2. 低维 SoS 数值 tightness 不能轻易外推。

一句话总结

这篇论文是一个用 orbit-stabilizer symmetry reduction 加精确有理 SoS 证书挖掘得到的反例，实质贡献不是新的通用 SDP 算法，而是证明 De Klerk–Laurent 校正常数的最优性猜想在 n=8 已失败，并揭示 hypercube quadratic module 中非平凡表示结构会改变常数阈值。