📊 statistics

Randomstrasse101: Open Problems of 2025

本文档旨在作为 2025 年发布在 Randomstrasse101 博客（专注于概率论、计算、组合学及统计学等领域的数学开放问题）上的开放问题之稳定记录，以方便学术引用。

原作者： Afonso S. Bandeira, Daniil Dmitriev, Kevin Lucca, Petar Nizić-Nikolac, Almut Rödder

发布于 2026-04-01

📖 1 分钟阅读☕ 轻松阅读

原作者： Afonso S. Bandeira, Daniil Dmitriev, Kevin Lucca, Petar Nizić-Nikolac, Almut Rödder

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

这篇文档其实是一份**“数学界的未解之谜清单”**，由瑞士苏黎世联邦理工学院（ETH Zurich）的一群数学家在 2025 年整理而成。

想象一下，数学界就像是一个巨大的**“未解之谜博物馆”。这份文件就是 2025 年新增的 16 个“镇馆之宝”的导览手册。这些谜题大多集中在概率论、计算机科学、组合数学和统计学**领域。

作者们并不要求你立刻解决它们（那太难了！），而是希望把这些有趣的问题记录下来，方便大家引用和讨论。

为了让你更容易理解，我们把这 16 个问题（文档中列出了第 8 到第 14 号）用生活中的比喻来解释：

1. 张量浓度不等式 (Tensor Concentration Inequalities)

通俗解释：想象你在玩一个巨大的**“多维骰子游戏”**。普通的骰子是二维的（点数），但这里的“张量”是三维甚至更高维的“超级骰子”。
核心问题：当你扔很多个这样的超级骰子并试图计算它们的“最大威力”时，我们想知道这个威力会不会像普通骰子那样，随着数量增加而稳定在一个可预测的范围内？
比喻：就像你想知道，如果有一群人在一个巨大的房间里随机走动，他们聚集在一起的最大密度大概是多少？目前的数学工具在处理这种“高维混乱”时还不够精准，作者希望找到一个完美的公式来预测这种“混乱的极限”。

2. 随机循环图的 Lovász 数 (The Lovász number of random circulant graphs)

通俗解释：想象一张**“社交网络图”**，每个人是一个点，朋友之间连线。
- 团 (Clique)：一群互相都认识的人。
- 染色 (Chromatic number)：给这群人分组，让同组的人互不认识，最少需要分几组？
核心问题：计算这两个数字非常难（是 NP-hard 问题）。Lovász 数是一个聪明的“数学捷径”（半定规划），它能给出一个很好的估算值。
比喻：这就好比你想估算一个混乱派对里“最亲密的小圈子”有多大。对于完全随机的派对，我们大概知道答案；但对于一种**“有规律但看起来随机”**的派对（循环图），我们还没搞清楚这个“数学捷径”给出的估算值到底是不是最准的。作者猜测它和完全随机的情况差不多。

3. 相位恢复的注入性与稳定性 (Injectivity and Stability of Phase Retrieval)

通俗解释：想象你在拍一张**“只有亮度没有颜色/相位”的照片**。你只能看到光有多亮，但看不到光波的起伏（相位）。
核心问题：能不能仅凭这些“亮度信息”就完美还原出原来的图像？
- 注入性：能不能唯一确定原图？（会不会有两张完全不同的图，拍出来的亮度图一模一样？）
- 稳定性：如果测量有一点点误差，还原出来的图会不会变得面目全非？
比喻：就像你只能听到一个人说话的音量大小，却听不到语调。你能仅凭音量大小还原出他说的每一个字吗？如果音量稍微测错了一点，还原出来的句子会不会变成乱码？作者正在研究需要多少个“音量传感器”才能确保还原成功且稳定。

4. 互无偏基与 Zauner 猜想 (Mutually Unbiased Bases, ETFs, and Zauner's Conjecture)

通俗解释：这是量子物理里的概念。想象你有几套不同的**“坐标系”**（比如 X-Y 轴，或者旋转 45 度的轴）。
核心问题：能不能找到一套特殊的坐标系，使得你在任何一套坐标系里看，另一套坐标系里的点都显得“完全均匀、毫无偏向”？
比喻：就像你要设计一套**“万能密码本”**。无论敌人用哪种语言（坐标系）来破解，你的密码看起来都是完全随机、无法预测的。
- Zauner 猜想：作者猜想，对于任何维度的空间，我们都能找到这种完美的“万能密码本”（特别是当向量数量是维度的平方时）。这在量子加密中非常重要。

5. Paley 图的团数 (On the clique number of the Paley Graph)

通俗解释：Paley 图是一种由数论规则（二次剩余）生成的特殊图，它看起来像随机图，但其实是完全确定的。
核心问题：在这个图里，最大的“互相认识的小圈子”（团）有多大？
比喻：想象一个由数学公式生成的**“迷宫”**。虽然它看起来杂乱无章，但里面最大的“死胡同”（团）到底能有多长？目前的数学工具（如 Lovász 数）只能给出一个比较宽泛的上限，作者希望找到更精确的“尺子”来量出这个团的大小，甚至猜想它其实非常小（像对数级别那么小）。

6. KLS 猜想 (The KLS Conjecture)

通俗解释：这是一个关于**“形状和边界”**的问题。
背景：在二维平面上，周长固定时，圆形的面积最大（等周不等式）。但在高维空间里，情况变得很复杂。
核心问题：对于一类叫做“对数凹”的分布（比如高斯分布，或者均匀分布在凸多面体里），是否存在一个**“通用的瓶颈”**？也就是说，无论这个形状多复杂，它是否总是像高斯分布那样，不容易被“切”成两半？
比喻：想象一个**“高维气球”**。KLS 猜想认为，无论这个气球被吹成什么奇怪形状（只要它是凸的），你很难找到一条“细线”把它切成两半而不切破它。如果这个猜想成立，意味着我们在高维空间里采样、计算会快得多。最近这个领域有重大突破，但完全证明还在路上。

7. 图矩阵的精确界限 (Sharp Bounds for Graph Matrices)

通俗解释：这是关于**“算法如何判断问题难度”**的。
背景：在计算机科学里，我们常用一种叫“求和平方”（Sum-of-Squares, SoS）的算法来解决优化问题。
核心问题：这种算法在处理某些随机生成的图（比如社交网络）时，到底能有多强？
比喻：想象你在玩一个**“找茬游戏”（比如找出一群互相认识的人）。SoS 算法是一个超级侦探。作者发现，这个侦探手里拿的“放大镜”（图矩阵）在某些情况下，其“威力”（谱范数）是可以被精确预测的。目前的预测公式里还带着一些多余的“噪音”（对数因子），作者希望把这些噪音去掉，得到一个“完美公式”**，从而更准确地知道这个侦探什么时候会失效，什么时候能成功。

总结

这份文档就像是一份**“数学探险地图”**。

有的探险是关于**“高维混乱中的秩序”**（张量、KLS 猜想）；
有的是关于**“看不见的信息如何还原”**（相位恢复）；
有的是关于**“完美对称的结构”**（互无偏基、Paley 图）；
还有的是关于**“算法能力的边界”**（图矩阵）。

作者们说：“这些问题很有趣，我们还没完全解开，但解开它们会让我们的世界（从量子计算到算法设计）变得更清晰、更高效。”

一句话总结：这是一群聪明的数学家在 2025 年留下的“寻宝图”，上面标记了 16 个还没找到宝藏的地点，邀请全世界的聪明人去挑战。

这篇论文《Randomstrasse101: Open Problems of 2025》是由 ETH 苏黎世数学系及相关机构的研究人员（Afonso S. Bandeira 等）撰写的一份技术报告，旨在记录并整理 2025 年发表在同名博客上的 16 个开放数学问题（本文收录了其中的第 8 至 14 号问题）。该文档聚焦于概率论、计算理论、组合数学、统计学及相关领域的核心未解难题。

以下是对该文档中涉及的主要技术内容的详细总结：

1. 核心问题概述

文档并未提出单一的新定理，而是汇集了多个前沿领域的开放问题（Open Problems）和猜想（Conjectures）。这些问题主要集中在高维概率、随机矩阵理论、组合优化、量子信息理论以及凸几何的交叉领域。主要涵盖的主题包括：

张量集中不等式：随机张量的范数界限。
图论与谱图理论：随机循环图的 Lovász 数、Paley 图的团数（Clique number）。
相位恢复（Phase Retrieval）：测量的注入性与稳定性。
量子信息：互无偏基（MUBs）、等角紧架（ETFs）及 Zauner 猜想。
凸几何与等周不等式：KLS 猜想及其与薄壳猜想、切片问题的联系。
计算复杂性：Sum-of-Squares (SoS) 层次结构下的图矩阵界限。

2. 方法论与理论框架

文档中各条目采用了不同的数学工具和分析方法：

随机过程与覆盖数（Entropy Integrals）：在张量集中不等式中，利用高斯过程的 supremum 性质，通过 Dudley 熵积分和覆盖数（Covering numbers）来估计随机张量算子范数的期望。
半定规划（SDP）与线性规划（LP）：
- 利用 Lovász $\vartheta$ 函数作为图团数和色数的凸松弛（SDP 形式）。
- 对于循环图，利用离散傅里叶变换（DFT）将 SDP 转化为线性规划（LP），并在“时域”和“频域”之间切换进行分析。
- 使用 Sum-of-Squares (SoS) 层次结构作为凸松弛工具，研究其在证明图性质（如团数上界）时的局限性。
随机矩阵理论：
- 引入**图矩阵（Graph Matrices）和矩阵混沌（Matrix Chaos）**模型。
- 利用非交换 Khintchine 不等式、自由概率（Free Probability）理论以及伪校准（Pseudo-calibration）启发式方法来分析随机矩阵的谱范数。
几何概率与局部化技术：
- 在 KLS 猜想中，使用**随机局部化（Stochastic Localization）**技术（Eldan 方法）将高维测度分解为高斯混合，从而推导等周常数。
- 利用 Poincaré 不等式和 Lipschitz 集中不等式建立几何性质与概率界限之间的联系。

3. 关键贡献与主要猜想/结果

A. 张量集中不等式 (Entry 8)

问题：确定对称张量 $T_i$ 与高斯变量 $g_i$ 加权和的 $\ell_p$ 注入范数期望的上界。
猜想 16：提出了张量的 Type-2 常数猜想，认为期望值受 $\sqrt{\sum ||T_i||^2}$ 控制，并带有维度相关的对数因子。
现状：在 $p \ge 2r$ 时已有部分结果，但在 $p < 2r$ 时（特别是 $r=p=2$ 的矩阵情形）仍缺乏纯几何证明。独立项张量已有更精确的界限，但一般情况仍困难。

B. 随机循环图的 Lovász 数 (Entry 9)

问题：研究随机稠密循环图（Random dense circulant graphs）的 Lovász 数 $\vartheta(G)$ 的渐近行为。
猜想 18：对于随机循环图， $\mathbb{E}\vartheta(G) \sim \sqrt{n}$ ，这与 Erdős-Rényi 随机图 $G(n, 1/2)$ 的行为一致。
进展：利用受限等距性质（RIP）和修改后的线性规划，已给出下界和 $O(\sqrt{n} \log \log n)$ 的上界。

C. 相位恢复的注入性与稳定性 (Entry 10)

问题：确定相位恢复中线性测量矩阵 $A$ 的注入性所需的最小测量数 $N$ ，以及重构的稳定性。
背景：在复数域 $\mathbb{C}$ 中， $N \ge 4M-4$ 的猜想已被证伪（存在 $N=11, M=4$ 的反例）。
猜想 19 & 20：
- 猜想 19：在 $N=4M-5$ 时，随机矩阵几乎不可能是注入的。
- 猜想 20 (Balan-Wang)：关于稳定性常数 $\omega(A)$ 的上界，涉及矩阵行向量的范数。
开放问题 21：高斯随机矩阵的 $\omega(A)$ 具体值及其满足的界限。

D. 互无偏基 (MUBs) 与 Zauner 猜想 (Entry 11)

问题：确定 $\mathbb{C}^d$ 中最大互无偏基的数量 $MUB(d)$。
猜想 22：$MUB(6) < 7$（即 6 维空间中不存在 7 个 MUBs）。这是该领域最著名的未解问题之一。
方法：尝试使用 4 次 Sum-of-Squares (SoS) 证明来排除 7 个 MUBs 的存在性。
Zauner 猜想 (猜想 24)：对于任意维度 $d$ ，存在 $d^2$ 个向量的等角紧架（ETF），即 SIC-POVM。近期进展表明该猜想与数论中的 Stark 猜想有关。

E. Paley 图的团数 (Entry 12)

问题：Paley 图 $G_p$ 的团数 $\omega(G_p)$ 的上界。
猜想 25： $\omega(G_p) = O(\text{polylog}(p))$ ，即团数是对数级的（类似于随机图）。
现状：已知上界为 $\sqrt{p}$ 。Hanson 和 Petridis 改进为 $(1+o(1))\sqrt{p/2}$ 。
猜想 26-28：
- 通过局部化（Localization）技术（如 1-localization, 2-localization）和 Lovász $\vartheta$ 函数，期望能进一步降低上界。
- 猜想 28：4 次 SoS 松弛可能将上界改进为 $O(p^{1/2-\epsilon})$ 。
关联：该问题与 Paley ETF 的受限等距性质（RIP）猜想紧密相关（猜想 29）。

F. KLS 猜想与凸几何 (Entry 13)

问题：对数凹测度（Log-concave measures）的等周常数是否由半空间最小化决定（即是否存在与维度无关的下界）。
猜想 30 (KLS 猜想)：存在通用常数 $C$ ，使得 $\psi_\mu \ge C / \sqrt{\|A\|_{op}}$ 。
进展：
- 从 $n^{-1/2}$ 改进到 $n^{-1/4}$ ，再到 Chen (2021) 的 $e^{-\sqrt{\log n}}$ 。
- 最新突破：Klartag (2023) 利用改进的 Lichnerowicz 不等式将下界提升至 $C (\log n)^{-1/2}$ 。
- 关联定理：KLS 猜想蕴含薄壳猜想（Thin Shell Conjecture，2025 年已证）和 Bourgain 切片问题（2024 年已证）。这些问题的解决反过来也支持了 KLS 猜想的当前最佳界限。

G. 图矩阵的精确界限 (Entry 14)

问题：确定随机图矩阵 $M_\alpha$ （Graph Matrices）的谱范数期望的精确渐近行为。
背景：图矩阵是分析 SoS 层次结构下界的关键工具。
猜想 31：对于固定形状 $\alpha$ ， $\mathbb{E}\|M_\alpha\| = \Theta(n^{f(\alpha)} (\log n)^{g(\alpha)})$ 。
意义：目前的工具（如迭代自由概率）往往包含不必要的对数因子。证明该猜想将消除这些因子，从而得到更紧的 SoS 下界，并深化对伪校准（Pseudo-calibration）启发式的理解。

4. 结果与意义

学术价值：该文档不仅是一个问题列表，更是一个研究路线图。它清晰地指出了当前概率论、组合数学和理论计算机科学交叉领域的瓶颈所在。
理论突破的潜力：
- KLS 猜想的进展直接推动了高维凸几何和随机矩阵理论的融合，其解决（或进一步逼近）对理解高维空间的几何结构至关重要。
- Zauner 猜想和 MUB(6) 问题的解决将直接推动量子信息理论的发展，特别是量子态层析和量子密码学。
- SoS 层次结构的界限研究对于理解计算复杂性（如 Planted Clique 问题）中多项式时间算法的极限具有核心意义。
方法论的启示：文档强调了多种现代数学工具的融合，如随机局部化、矩阵混沌理论、Sum-of-Squares 代数以及谱图理论。解决这些问题往往需要跨学科的工具创新。
对算法设计的指导：理解这些随机结构的精确界限（如张量范数、图矩阵谱）有助于设计更高效的近似算法，或者证明某些问题在特定模型下是计算困难的。

总结

这篇文档是 2025 年数学开放问题的一次重要汇编，反映了当前数学界在高维概率与离散结构交叉领域的前沿动态。它不仅记录了如 KLS 猜想、Zauner 猜想等经典难题的最新状态，还提出了关于随机张量、图矩阵和相位恢复稳定性的一系列具体猜想。这些问题的解决将深刻影响我们对高维空间几何、量子信息基础以及计算复杂性界限的理解。