🔢 mathematics

An entropic analogue of the MMS conjecture

本文证明了对于任何和为零的 $n$ 个实数的多重集，随机抽取 $k$ 个元素的和的香农熵，其下界为均值为 $k/n$ 的伯努利随机变量的熵，这一锐利结果作为 Manickam-Miklós-Singhi 猜想的熵学类比。

原作者： Jianhang Ai, Ondřej Kuželka, Christos Pelekis

发布于 2026-06-30✓ Author reviewed ⓘ

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Jianhang Ai, Ondřej Kuželka, Christos Pelekis

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

想象一下你有一个装满弹珠的袋子。有些弹珠上涂着正数（比如 +1, +5），有些则涂着负数（比如 -2, -10）。游戏的规则是：如果你把袋子里每一颗弹珠上的数字全部加起来，总和必须正好等于零。

现在，想象你闭着眼睛从袋子里抓了一把 $k$ 颗弹珠。你把这几颗弹珠上的数字相加。我们把这个和称为 $X$ 。

论文提出了一个非常具体的问题：这个和的结果有多“令人惊讶”或有多“不确定”？

在信息论的世界里，“惊讶度”是用 香农熵（Shannon Entropy） 来衡量的：

低熵： 结果是非常可预测的。例如，如果你每次得到的和都一样，熵就是零。这很枯燥。
高熵： 结果是非常不可预测的。你可能会得到许多不同的和，而且这些和出现的概率都差不多。这很令人兴奋且具有混沌感。

核心问题

作者想要寻找的是：无论你如何排列袋子里的数字（只要它们的总和为零），你能得到的最低程度的惊讶度（最小熵）是多少。

他们发现了一个“黄金分割点”式的场景：当你的袋子尽可能地“失衡”时，不确定性最低。

“极端”袋子： 想象一个袋子里有一个巨大的正数（比如 +100）和许多微小的负数（比如每个都是 -0.01）来抵消它。
结果： 当你从这个特定的袋子里抓取一把时，其总和是出人意料地容易预测的。你要么得到了那个巨大的正数（如果你抓到了它），要么没得到（如果你没抓到）。这几乎就像是一次抛硬币。

主要发现（“熵的类比”）

论文证明了，无论你如何排列你的数字，你和的不确定性（熵）永远 不会低于 一个简单的硬币投掷所产生的确定性（其中硬币出现正数的概率为 $k/n$ ，即抓到那个“特殊”弹珠的概率）。

他们称之为 “MMS 猜想的熵类比”。

旧猜想 (MMS)： 一个来自 40 年前的著名数学问题曾问道：“我的和为正数的概率最小值是多少？”
新论文： “我的和的不确定性（熵）最小值是多少？”

他们发现，对于这两个问题，答案指向了同一个“最坏情况”：即那个拥有一个巨大正数和许多微小负数的袋子。

他们是如何证明的（“魔力阶梯”）

为了证明这一点，作者使用了沉重的数学工具，但这里有一个简单的类比：

偏序集（阶梯）： 他们将所有可能的抓取弹珠的方式想象成一座巨大阶梯上的不同阶梯。
“符号拆分”规则： 他们根据你抓到的是正数还是负数，对这座阶梯进行了分类整理。
“主次化”（Majorization）技巧： 他们证明了来自任何一袋弹珠的和的分布，都比来自那个特定的“极端袋子”的分布更“平滑”且更“分散”。
- 可以这样理解：如果你把水（概率）倒入一个杯子（极端袋子），水会保持高度集中。如果你把水倒入任何其他的杯子（任何其他的数字组合），水就会散开得更多。
- 在数学中，当一个分布比另一个分布更“分散”时，它的熵就更高。
结论： 由于“极端袋子”拥有最集中（最不分散）的分布，因此它的熵最低。因此，任何其他的袋子都具有更高的熵。

“抛硬币”对比

论文得出结论，你的和的不确定性总是至少与一个 伯努利随机变量（Bernoulli random variable） 的不确定性一样高。

那是什么？ 这只是一个关于“加权硬币投掷”的专业术语。
如果你有 10 颗弹珠并抓取 3 颗，那么“最坏情况”下的不确定性，就等同于抛一枚硬币，其正面出现的概率为 30%，反面出现的概率为 70%。

为什么这很重要？

这篇论文并不声称它能解决气候变化或治愈疾病。相反，它解决了一个 组合数学（研究计数和排列的数学）中的深层谜题。

它连接了两个不同的世界：

概率论： 我的和为正数的可能性有多大？
信息论： 当我看到这个和时，我获得了多少信息？

通过证明“极端袋子”对于概率和信息而言都是最坏情况，作者将这两个不同的数学视角统一了起来。他们还提供了两种不同的证明方式：一种是使用复杂的“阶梯”逻辑（斯佩纳理论/Sperner theory），另一种是使用更简单的“链”逻辑，这感觉就像是一个巧妙的魔术。

简而言之： 无论你如何混合正数和负数，所得的和总会至少像一次加权硬币投掷那样具有不可预测性。唯一的办法是让你的袋子里有一个巨大的数字和许多微小的数字，从而降低这种不可预测性。

技术摘要：MMS 猜想的熵类比

问题陈述
本文研究了一个关于从具有零均值的有限实数总体中进行不放回抽样的概率问题。设 $P = \{x_1, \dots, x_n\}$ 为一个由 $n \ge 2$ 个实数组成的多元集，满足 $\sum x_i = 0$ 且 $\sum |x_i| > 0$ 。令 $k < n$ 为正整数。从中进行大小为 $k$ 的均匀不放回抽样，并令 $X_P$ 表示抽样元素的总和。

作者探讨了寻找 $H(X_P)$ 的一个紧下界的问题。这一探究被框架化为 Manickam-Miklós-Singhi (MMS) 猜想的一个“熵类比”。经典的 MMS 猜想（猜想 1）指出，当 $n \ge 4k$ 时， $P(X_P \ge 0) \ge k/n$ 。一个改进版本（由 Aydinian 和 Blinovsky 提出的猜想 2）建议，最小概率 $P(X_P \ge 0)$ 由特定的“极端”总体实现，这些总体由 $i$ 个正值和 $n-i$ 个负值组成，并通过缩放保持零均值。作者试图确定对于香农熵是否也存在类似的极值原理。

方法论
本文采用了两种不同的方法论途径来建立 $H(X_P)$ 的下界：

Sperner 理论与 majorization（主值化/优势关系）：
- 作者定义了一个与总体 $P$ 相关的“符号分裂偏序集” $Q = (\binom{[n]}{k}, \le)$ 。该偏序集的元素是索引的 $k$ -子集，其顺序基于这些子集与非负索引集合 ( $A$ ) 及负索引集合 ( $B$ ) 的交集情况。
- 他们证明了这个偏序集具有 强 Sperner 性质（引理 2），通过展示它是一个“正规偏序集”（满足归一化匹配性质）。
- 一个关键观察（引理 1）是：产生特定总和值的子集集合在该偏序集中构成一个 反链 (antichain)。
- 利用强 Sperner 性质，作者表明 $X_P$ 的概率质量函数 (PMF) 被超几何随机变量 $H_i \sim \text{Hyp}(n, i, k)$ 的 PMF 主值化 (majorized)（引理 3）。
- 由于香农熵是一个 Schur 凹函数，这种主值化关系意味着 $H(X_P) \ge H(H_i)$ 。
初等熵论证：
- 第二种证明主不等式的方法避开了 Sperner 理论和主值化。它从 Lubell 对 LYM 不等式的证明中汲取灵感。
- 该方法涉及使用正元素和负元素的随机排列来构造一个随机极大链。
- 通过证明从所选子集的秩到其总和的映射是单射，作者表明对 $X_P$ 进行抽样等价于对超几何变量 $H_i$ 进行抽样并应用一个严格递增的变换。
- 利用条件化不会增加熵的性质，他们推导出 $H(X_P) \ge H(H_i)$ 。

核心结果

定理 2（熵类 Aydinian-Blinovsky 猜想）： 对于任何非平凡零均值总体 $P$ ，样本总和的熵满足：
$H(X_P) \ge \min_{i \in [n-1]} H(H_i)$
其中 $H_i \sim \text{Hyp}(n, i, k)$ 。这确立了 Aydinian 和 Blinovsky 定义的“极端”总体（即具有 $i$ 个正值和 $n-i$ 个负值的总体）也是熵的极小值点。
定理 1（主要结果）： 作者解决了关于 $i$ 的最小化问题。他们证明了最小熵在 $i=1$ （或对称地 $i=n-1$ ）时取得，对应的总体为 $P = \{1, -\frac{1}{n-1}, \dots, -\frac{1}{n-1}\}$ 。
$H(X_P) \ge H(\text{Ber}(k/n))$
其中 $\text{Ber}(k/n)$ 是均值为 $k/n$ 的伯努利随机变量。该不等式是紧致的，且对于上述总体取等号。
定理 3（Littlewood-Offord 型结果）： 作为主值化论证的副产品，本文建立了 $X_P$ 最大点概率（众数）的界限：
$\sup_{x \in \mathbb{R}} P(X_P = x) \le \max_{i \in [n-1]} P(H_i = m_i)$
其中 $m_i$ 是超几何变量 $H_i$ 的一个众数。

意义与主张
本文声称提供了第一个 MMS 猜想的熵类比。其意义在于：

领域桥接： 它将组合设计理论（特别是 MMS 猜想和 Johnson 方案不变性）与信息论（香农熵）联系起来。
极值原理： 它证实了在非负总和概率最小化（在 Aydinian-Blinovsky 猜想背景下）的总体同时也使样本总和的香农熵最小。
方法论贡献： 该工作展示了 Sperner 理论和主值化在推导和变量（不放回抽样中的和）的 PMF 相关的熵不等式中的效用，这与以往涉及独立变量的应用不同。
泛化性： 作者指出，他们的基于主值化的方法（引理 3）适用于任何关于 PMF 的 Schur 凹函数，这表明了向 Rényi 熵扩展的潜力（推论 5），尽管针对一般 $\alpha$ 的具体最小化仍是一个开放的数值问题。

本文并不声称解决了原始的 MMS 猜想（关于概率的猜想），而是建立了一个平行的、严谨的熵结果，为样本和的极值行为提供了一个新的视角。