🔢 mathematics

Monochromatic products in random integer sets

本文研究了在二染色条件下，随机整数子集几乎处处包含方程 $ab=c $的单色解时所对应的阈值概率，确立了介于$ n^{-1/9-o(1)} $与$ n^{-1/11}$ 之间的界限，并证明了此类非线性方程的行为及证明技术与线性方程有着显著的不同。

原作者： Roger Lidón, Darío Martínez, Patrick Morris, Miquel Ortega

发布于 2026-01-15

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Roger Lidón, Darío Martínez, Patrick Morris, Miquel Ortega

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

想象一下，你有一个装满编号瓷砖的大袋子，编号从 1 到 $n$ 。你决定随机抽取一小把瓷砖留着，方法是为每一块瓷砖抛一次硬币：正面，你就留下；反面，你就扔掉。保留一块瓷砖的概率为 $p$ 。

现在，想象你有一桶含有 $r$ 种不同颜色的油漆。你想把你随机抽到的那一小把瓷砖全部涂上颜色。核心问题在于：是否有可能通过某种涂色方式，来避免产生一个“单色乘积”？

所谓的“单色乘积”，是指三个瓷砖 $(a, b, c)$ 的颜色完全相同，且满足 $a \times b = c$ 。例如，如果你抽到的瓷砖 2、3 和 6 全都被涂成了红色，那么你就得到了一个“红色乘积”，因为 $2 \times 3 = 6$ 。

这是一篇关于寻找精确临界点（阈值）的数学侦探故事：无论你多么巧妙地涂色，是否都能避开这些颜色相同的三元组。

背景：加法与乘法

数学家们早就知道，如果你拥有足够多的数字，你就无法避免出现“单色和”（即 $a + b = c$ ）。这是一个著名的结果，被称为舒尔定理（Schur's Theorem）。

在 20 世纪 90 年代，研究人员提出了一个问题：“如果我们的数字集合非常稀疏，我们需要抽取多少个数字，才能保证找到一个单色和？”他们发现，如果你抽取的数字概率大约为 $1/\sqrt{n}$ ，你就能保证找到一个和。如果你抽取的更少，通常是可以避免的。

本文探讨的问题是：针对乘法（ $a \times b = c$ ）而非加法，情况又是如何呢？

主要发现：一个新的转折点

作者发现，乘法的规则与加法的规则截然不同。

“加法”规则： 对于加法，转折点大约在 $n^{-1/2}$ （1 除以平方根 $n$ ）。
“乘法”规则： 对于乘法，转折点要低得多。作者证明，对于一个随机数集，若要保证其中一定存在单色乘积，抽取一个数字的概率必须处于 $n^{-1/9}$ 到 $n^{-1/11}$ 之间。

类比：
把“加法”问题想象成试图在一堆沙子中寻找特定的形状。你需要适量的沙子才能确保形状的存在。
而“乘法”问题则像是寻找一种非常罕见的特定晶体结构。因为乘法增长得极快（2 乘以 3 是 6，但 10 乘以 10 是 100），所以这些“晶体”（三元组 $a, b, c$ ）更难形成。你需要更密集的数字堆（更高的概率 $p$ ）来保证找到它，但矛盾的是，由于乘法的结构如此稀疏且不规则，其阈值的指数实际上要更低。

如何解决：两路进攻

为了找到这个阈值，作者必须证明两件事：

1. “坏消息”（下界）：
他们证明了，如果你抽取的数字过于稀疏（低于 $n^{-1/9}$ ），你几乎总能用两种颜色（比如红色和蓝色）进行涂色，使得不存在红色三元组，也不存在蓝色三元组。

方法： 他们使用了一种“贪心算法”。想象你正按从小到大的顺序为数字涂色。你尝试把一个数字涂成红色。如果涂红会导致与你已经涂过色的数字产生红色乘积，你就改涂成蓝色。如果涂成蓝色也会导致产生蓝色乘积，你就陷入了困境。
结果： 他们证明，如果集合足够稀疏，这种贪心涂色过程几乎永远不会陷入困境。你可以成功地为整个集合涂色，而不产生任何单色乘积。

2. “好消息”（上界）：
他们证明了，如果你抽取的数字足够密集（高于 $n^{-1/11}$ ），那么无论你怎么涂色，都保证会找到一个单色乘积。

方法： 他们没有试图对整个集合进行涂色，而是寻找了一个微小的、特定的“陷阱”模式。他们发现了一组由 15 个数字组成的特定集合，如果这些数字全部出现在你的随机集合中，那么它们无法在不产生单色乘积的情况下完成涂色。这就像是一个没有解的数学谜题。
结果： 他们证明，如果你的概率 $p$ 足够高，你的随机集合几乎肯定会包含这个“陷阱”模式。一旦陷阱出现，单色乘积就不可避免了。

为什么这很重要

这篇论文之所以重要，是因为它打破了常规。几十年来，数学家们一直认为随机集合中加法和乘法的规则是相似的。这篇论文表明它们有着本质的区别。

加法是规则且可预测的。
乘法是混沌且不规则的。

数学家通常用来解决这类问题的工具（依赖于加法的规则性）在处理乘法时失效了。作者必须发明更具创造性的新方法来计数可能性并构建他们的“陷阱”。

多色彩的转折

论文还研究了当你拥有 3 种、4 种或更多颜色时会发生什么。

对于加法，颜色的数量不会显著改变转折点。
对于乘法，颜色的数量会剧烈改变阈值。颜色越多，强制出现单色乘积就越难，阈值也会随之显著移动。

总结

简而言之，这篇论文告诉我们，如果你从一个巨大的列表中随机抽取数字，那么抽取这些数字的概率存在一个非常特定的“金中则乐区”（Goldilocks zone）。

如果你抽取的太少，你可以通过精心的涂色来躲避“乘法陷阱”。
如果你抽取的足够多，宇宙就会强行让一个单色乘积出现，无论你如何试图规避。

作者将这个区域缩小到了一个特定的范围内，证明了随机乘法的世界比随机加法的世界更加复杂且有趣。

技术摘要：随机整数集中的单色乘积问题

问题陈述
本文研究了二项随机子集 $[n]_p$ （其中每个元素 $\{1, \dots, n\}$ 以概率 $p$ 独立包含）具有“乘积-舒尔”（product-Schur）性质的阈值概率 $p = p(n)$ 。一个集合 $A$ 被定义为 $r$ -乘积-舒尔，如果任何对 $A$ 的 $r$ -着色都会产生一个关于方程 $ab = c $（其中$ a, b, c \in A $）的单色解。虽然线性方程（如$ a+b=c$ 的舒尔定理）的阈值已通过拉多定理（Rado's theorem）及随后的传递原理得到了充分研究，但对于非线性方程（如 $ab=c $）在随机集中的行为，目前仍很大程度上处于空白。作者旨在确定临界密度$ p^$，即随机集从几乎确定（a.a.s.）不具备乘积-舒尔性质到几乎确定具备*乘积-舒尔性质的转变点。

方法论
本文针对下界（ $(0)$ -陈述）和上界（ $(1)$ -陈述）采用了不同的证明策略，并指出传统的随机拉姆齐理论工具不足以处理非线性情形。

$(0)$ -陈述（下界）：
为了证明当 $p$ 较小时 $[n]_p$ 不是乘积-舒尔的，作者利用了一种贪心着色算法。他们尝试通过按递增顺序迭代元素，将随机集划分为两个无乘积集（红色和蓝色）。如果一个元素不会与先前着色的元素形成单色乘积，则为其分配一种颜色。
- 障碍分析： 该算法仅在随机集中存在特定的“禁止构型”时才会失效。这些构型涉及复杂的乘法依赖关系（例如 $c = ab = def $，$ a = xyz $，$ b = uvw$）。
- 计数论证： 作者进行了详细的禁止构型情况分析，根据不同元素的数量和重复情况对其进行分类。他们应用了联合概率界限（union bound），利用约数界限（ $D(n) = n^{o(1)}$ ）来证明，对于 $p \le n^{-1/9 - o(1)}$ ，任何此类构型出现的概率为 $o(1)$ 。
$(1)$ -陈述（上界）：
为了证明当 $p$ 较大时 $[n]_p$ 是乘积-舒尔的，作者构造了一个特定的有限乘积-舒尔模式（一个无论如何进行 2-着色都会强制产生单色解的小整数集）。
- 模式构造： 他们定义了一个包含由四个基数整数生成的 14 个元素的集合 $S_{a,b,c,d}$ 。他们通过情况分析证明，任何对该集合的 2-着色都会产生一个关于 $xy=z$ 的单色解。
- 存在性证明： 他们证明了如果 $p = \omega(n^{-1/11})$ ，则随机集 $[n]_p$ 几乎确定包含该模式的副本。这是通过分阶段揭示随机集的过程实现的，并证明寻找必要的基数整数（ $a, b, c, d$ ）及其所需乘积的失败概率是微不足道的。
- 与标准方法的差异： 作者明确指出，标准的传递原理和超图容器方法（hypergraph container methods，其依赖于“超饱和性”——即稠密集合包含许多单色解的性质）在此处失效。对于乘积而言，存在某些着色方式使得单色解的比例趋于零，从而使得基于超饱和性的证明失效。
向 $r$ 种颜色的扩展：
对于 $r \ge 3$ ，作者利用舒尔数（ $S(r)$ ）和双和舒尔数（ $S'(r)$ ）推广了结果。
- 下界： 他们构造了一种基于缩放比例为 $n^{1/S'(r)}$ 的区间的着色方法，从而避开单色和以及偏移和，这转化为避开单色乘积。
- 上界： 他们利用集合 $U_x = \{x, x^2, \dots, x^{S(r)}\}$ ，根据 $S(r)$ 的定义，该集合不是 $r$ -乘积可着色的。他们证明了对于 $p = \omega(n^{-1/S(r)^2})$ ，该集合会几乎确定地出现。

主要结果

定理 1.2（两种颜色）： $[n]_p$ $[n]_{p}$ 为乘积-舒尔的阈值位于 $n^{-1/9 - o(1)}$ $n^{- 1/9 - o (1)}$ 和 $n^{-1/11}$ $n^{- 1/11}$ 之间。具体而言：
- 如果 $p \le n^{-1/9 - o(1)}$ ， $[n]_p$ 几乎确定不是乘积-舒尔的。
- 如果 $p \ge \omega(n^{-1/11})$ ， $[n]_p$ 几乎确定是乘积-舒尔的。
定理 1.4（ $r$ 种颜色）： 对于 $r \ge 2$ $r \geq 2$ ，阈值 $p^*_r$ $p_{r}^{*}$ 满足：
- $p^*_r \le n^{-1/S'(r)}$ （阈值的下界 / 不存在的上界）。
- $p^*_r \ge n^{-1/S(r)^2}$ （阈的上界 / 存在的下界）。
- 至关重要的是，与线性方程中阈值与颜色无关的情况不同，乘积的阈值取决于颜色的数量。

意义与主张
本文声称是第一篇探讨非线性方程（特别是单色乘积）的随机集拉姆齐性质的研究。其主要贡献在于：

建立阈值界限： 提供了第一个非平凡的乘积-舒尔阈值界限，表明其与线性情形（ $n^{-1/2}$ ）截然不同。
方法论创新： 证明了非线性拉姆齐性质的证明技术与线性性质存在显著差异。作者认为，由于乘积集中缺乏超饱和性，导致能够解决线性拉多型问题的强大传递原理和容器方法失效，因此必须采用诸如贪心着色分析和特定模式嵌入等新方法。
对颜色的依赖性： 强调了对于非线性方程，阈值取决于颜色数 $r$ ，这与在线性拉多定理中观察到的颜色无关性形成了对比。

猜想与未来方向
作者猜想真实的阈值是 $n^{-1/11}$ ，与其上界一致。他们认为这是由用于证明的特定有界规模构型的出现所决定的。他们承认，若要提高下界（ $n^{-1/9}$ ），可能需要超越精细化贪心着色之外的新思路。最后，他们提出这些技术可以应用于其他非线性方程，如 $a^2 = bc$ 或 $ab = cd$。