🔢 mathematics

Degree-Four Vector-Coordinate SoS Cannot Detect the MUB Upper Bound

本文证明了使用向量坐标形式（vector-coordinate formulations）的四次平方和（Sum-of-Squares）松弛在检测互不相容基（mutually unbiased bases）的已知数量上会失效（即使对于 $m > d+1$ 的情况），而使用投影算子坐标形式（projector-coordinate formulations）则能在相同次数下成功恢复该界限。

原作者： Shreyhaan Sarkar

发布于 2026-06-15

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Shreyhaan Sarkar

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

大局观：一场“完美无偏”的朋友游戏

想象一下，你正试图在一个高维房间（一个 $d$ 维空间）里组织一场派对。你想邀请若干组人（基，bases）按照特定的模式站立。

“相互无偏基”（MUB）的规则有点像一场关于完美平衡的游戏：

在组内： 每个人必须彼此保持完美的直角关系（正交）。
在组间： 如果你从 A 组选一个人，再从 B 组选一个人，他们之间的“角度”对于每一对可能的组合来说都必须完全相同。他们对彼此是“无偏”的。

数学家们知道这场游戏有一个硬性限制：你永远无法拥有超过 $d + 1$ 组这样的群体。例如，在一个 6 维房间（ $d=6$ ）里，你最多只能有 7 组。目前一个著名的悬案是：在 6 维房间里，我们是否真的能达到 7 组这个极限，还是说规则会在达到那里之前就崩溃了。

问题所在：计算机能“看见”这个极限吗？

这篇论文提出了一个关于一种被称为**平方和（Sum-of-Squares, SoS）**的计算机算法的具体问题。把 SoS 想象成一个非常聪明但有点近视的侦探。它试图通过观察描述人们位置的数学方程，来证明某种排列方式是不可能的。

这个侦探有一个“次数（degree）”限制。一个**4 次方（degree-4）**的侦探一次只能观察涉及最多四个变量的关系（比如观察四个人的位置是如何相互作用的）。

那个具体的问题（来自“Open Problem 23”）是：一个 4 次方的侦探能否证明在 6 维房间里不存在 7 组人？

发现：侦探用错了地图

作者 Shreyhaan Sarkar 发现，答案完全取决于你如何向侦探描述这些人。

1. “向量”地图（失败案例）

在第一种方法中，侦探被给予了每个人头、手、脚的原始坐标（向量的实部和虚部）。

诡计： 作者利用一群随机、独立的群体构建了一个“虚假现实”。在这个虚假世界里，这些群体在严格意义上并不完全是相互无偏的，但如果你只通过“4 次方透镜”去看，它们看起来却完美无偏。
类比： 想象你在看一张模糊的人群照片。从远处看（4 次方视角），人群看起来是完美平衡且随机的。侦探检查了数学计算，看到一切都加总为零，于是说：“嘿，这种排列是可能的！”
结果： 因为侦探会被这种“虚假现实”（称为伪期望，pseudoexpectation）所欺骗，所以它无法证明 7 组人是不可能的。它看不见 $d+1$ 这个极限。它甚至认为在 6 维房间里可能存在 100 组人，尽管我们知道这是错误的。

2. “投影器”地图（成功案例）

随后，作者尝试了另一种描述人的方式。他不再给侦探每个人的肢体坐标，而是给了侦探每个人投下的影子或投影的描述（在数学上，即 $P = vv^*$ ）。

区别： 在这种“投影器”语言中，关于“无偏性”的规则变得简单得多（从四次变为二次）。
结果： 当侦探使用这张地图时，“虚假现实”的诡计不再奏效。4 次方的侦探现在可以清晰地看到数学上的矛盾。它成功地证明了你无法拥有超过 $d+1$ 组人。

核心结论

论文得出结论：无法解决这个问题并不是因为数学太难，而是因为描述方式太弱了。

向量坐标： 就像试图通过一个一个观察拼图碎片来解决拼图问题。4 次方的侦探会感到困惑，并误以为拼图是可以完成的，而实际上并非如此。
投影器坐标： 就像看着拼图盒上的图案。4 次方的侦探可以立即看出规律，并意识到这个拼图是不可能完成的。

这对特定问题意味着什么

这篇论文专门回应了“Randomstrasse101 Open Problem 23”，该问题探讨了两种“向量”方法。

答案： 不能。 使用这些特定向量描述的 4 次方平方和证明无法证明 6 维空间中不存在 7 个相互无偏基。
提示： 这并不意味着不存在任何证明。它只是意味着这种特定的、直接的表达方式对于 4 次方算法来说太弱了。如果我们切换到“投影器”这种描述问题的方式，算法就会变得足够强大，从而找到那个极限。

简而言之： 论文表明，如果你使用原始坐标来描述问题，一个视觉有限（4 次方）的计算机会被骗，认为不可能的事是可能的。但如果你通过“影子”（投影器）来描述问题，同一个计算机就能看到真相。

技术摘要：四次向量坐标 SoS 无法检测 MUB 上界

问题陈述
本文探讨了 Randomstrasse101 Open Problem 23，该问题询问是否存在一个四次 Sum-of-Squares (SoS) 证明，能够证明在 $\mathbb{C}^6$ 中不存在七个相互无偏基（MUBs）。该问题使用两种特定的向量坐标编码进行构建：

四次等式公式化：约束被编码为关于向量分量实部和虚部的四次关系，即 $|\langle v, w \rangle|^2 = 1/d$ 。
$2 \times 2$ 厄米特半正定公式化：跨基条件被编码为涉及二次内积 $\langle v, w \rangle$ 的 $2 \times 2$ 厄米特矩阵的半正定约束。
更广泛的背景是已知的上界 $m \le d + 1$ 对于 MUB 的数量。虽然在素数幂维数下等号成立，但 $d=6$ 的情况仍然是一个悬而未决的问题，目前的猜想是 $m=7$ 是不可能的。

方法论
作者通过构造**四次伪期望（pseudoexpectations）**来分析四次 SoS 松弛的效力。一个四次伪期望是一个作用于最高四次多项式的线性泛函 $\tilde{\mathbb{E}}$ ，它满足正定性（ $\tilde{\mathbb{E}}[f^2] \ge 0$ ）并与约束保持一致。如果一个系统存在这样的伪期望，则不存在四次 SoS 反驳（即不可行性证明）。

核心方法包括：

Haar-Random 构造：作者基于独立 Haar-随机酉矩阵的期望定义了一个伪期望。具体而言，对于 $m$ 个基，向量取自独立 Haar-随机酉矩阵的列。
约束验证：
- 同基约束：对于随机构造，正交归一性是逐点（精确地）成立的。
- 跨基约束：对于独立的 Haar-随机单位向量 $x, y$ ，期望值 $\mathbb{E}[|\langle x, y \rangle|^2] = 1/d$ 。
仿射乘子分析：对于半正定公式化，作者证明了内积 $z = \langle x, y \rangle$ 作用于仿射线性函数时，其算子范数的特定界限。他们证明了 $|\mathbb{E}[p z q]| \le \frac{1}{d} \sqrt{\mathbb{E}[|p|^2]\mathbb{E}[|q|^2]}$ 。
公式对比：论文将向量坐标公式化与**投影算子坐标公式化（projector-coordinate formulation）**进行了对比，在后者中，变量是秩为一的投影算子 $P = vv^*$ 。在这种设定下，跨无偏条件变为二次项（ $\text{Tr}(P_i^{(k)} P_j^{(\ell)}) = 1/d$ ）。

主要贡献与结果

向量坐标公式化的下界：
主要结果（定理 5.1 和 7.1）确立了对于任何维度 $d$ 和任何提议的基数 $m$ ，标准的向量坐标 MUB 系统都存在一个由独立 Haar-随机基导出的四次伪期望。
- 四次等式：该伪期望满足四次约束，因为四次项 $|\langle x, y \rangle|^2 - 1/d$ 的期望值为零。由于约束是四次的，四次反驳只能通过常数进行乘法运算，而伪期望会使这些项湮灭。
- 半正定公式化：利用仿射乘子界限（定理 6.1），作者表明该伪期望满足 $2 \times 2$ 厄米特矩阵的四次局部化约束。
- 结论：在这些向量坐标公式化中，四次 SoS 无法反驳 $m$ 个 MUB 的存在性，即使当 $m > d + 1$ 时（此时 MUB 已知或被猜想是不可能的）。具体到 $d=6, m=7$ 的情况，不存在四次 SoS 的非存在性证明。
公式化分离（投影算子 vs. 向量）：
论文证明了这种失效是针对向量坐标编码特有的。在投影算子坐标公式化（定理 8.1）中，变量是中心化投影算子 $Q = P - I/d$ ，此时跨无偏约束是二次的。
- 作者证明，只要 $m > d + 1$ ，对于投影算子系统，就可以构造出一个四次 SoS 反驳。
- 这种反驳依赖于一个涉及投影算子平方和迹的 Gram 矩阵恒等式，当 $m > d + 1$ 时，该恒等式在模约束下会产生一个负常数。
- 结果：四次 SoS 可以在投影算子公式化中恢复基本的上界 $m \le d + 1$ 。

意义与主张
论文声称了低阶 SoS 层级在处理 MUB 问题时的公式化相关分离（formulation-dependent separation）：

对 Open Problem 23 的否定回答：对于问题陈述中描述的两种特定的向量坐标编码（四次方程和 $2 \times 2$ LMI），答案是否定的。四次 SoS 在本质上太弱，无法检测到基本的计数障碍（ $m \le d + 1$ ）。
公式化敏感性：无法解决该问题并非方法的普遍局限性，而是直接向量坐标松弛的局限性。相同的阶数在应用于投影算子坐标时，其强度明显更高，因为后者成功恢复了已知上界。
对 $d=6$ 的启示：虽然投影算子公式化恢复了 $m \le d + 1$ 对于 $d=6$ 的情况，但论文指出， $d=6, m=7$ 是该边界的“紧凑”情形。因此，该分离结果并未明确回答是否可以通过更强的投影算子变量四次证明来排除恰好七个 MUB 的情况，而仅表明它可以排除八个或更多的情况。

这项工作隔离了向量坐标 SoS 的特定四次障碍，表明任何成功的低阶 SoS 方法处理维度六的 MUB 问题，必须使用提升后的公式化（如投影算子），而非直接使用向量坐标。