🔢 mathematics

Extremal densities for forbidden configurations in $S$ -smooth numbers

本文研究了禁止配置在 $S$ -光滑数中的极值密度问题，证明了最大无禁止配置子集的大小渐近于 $\frac{r}{r+1}\Psi_S(X)$ ，并建立了相关密度常数的表示、递归公式及结构性质。

原作者： Nikola Veselinov

发布于 2026-04-20

📖 1 分钟阅读🧠 深度阅读

原作者： Nikola Veselinov

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

这篇论文探讨了一个非常有趣的数学问题，我们可以把它想象成一场**“数字积木的搭建游戏”**。

1. 游戏背景：特殊的积木（S-平滑数）

想象你有一堆特殊的积木，这些积木不是普通的整数，而是由几个特定的“基础积木”（质数，比如 2 和 3）通过乘法组合而成的。

如果你选的基础积木是 $\{2, 3\}$ ，那么你能搭出的数字有：1, 2, 3, 4 ( $2\times2$ ), 6 ( $2\times3$ ), 8 ( $2\times2\times2$ ), 9 ( $3\times3$ ), 12... 这些就是论文里说的"S-平滑数”。
论文研究的范围就是这些由特定质数生成的“数字家族”。

2. 游戏规则：禁止的“三连星”

现在，我们要从这些数字里挑出一个最大的子集（比如挑出 100 个数字），但是有一个严格的禁忌规则：
你不能同时选中三个数字，如果它们能组成“倍数关系链”。

具体来说，如果你选了一个数字 $n$ ，你就不能同时选它的 $p_1$ 倍、 $p_2$ 倍……直到 $p_r$ 倍。

以 $\{2, 3\}$ 为例：如果你选了数字 1，你就不能同时选 2 和 3。因为 $\{1, 2, 3\}$ 构成了一个“坏的组合”（ $1\times2=2, 1\times3=3$ ）。
如果你选了 2，你就不能同时选 4 和 6。

核心问题： 在不超过某个大数 $X$ 的所有这类特殊数字中，我们最多能选出多少个数字，才能不违反这个规则？

3. 主要发现：神奇的“三分之二”法则

作者通过复杂的数学推导（把数字问题转化成了几何空间里的点阵问题），发现了一个非常漂亮的规律：

无论你的基础质数有多少个（只要大于等于 2 个），随着数字越来越大，你能选出的最大数字比例，会稳定在一个固定的数值附近。

结论： 如果你有一大堆这样的数字，你最多能保留大约 $\frac{r}{r+1}$ 的比例。
- 如果基础质数有 2 个（比如 2 和 3），你能保留的比例大约是 $2/3$ （约 66.7%）。
- 如果基础质数有 3 个，你能保留的比例大约是 $3/4$ （75%）。
- 以此类推。

这就好比你在一个拥挤的房间里，虽然不能让大家手拉手站成特定的三角形，但你依然可以留下房间里 三分之二 的人，只要大家站得稍微“错开”一点。

4. 数学家的“工具箱”：如何计算？

为了得到这个结论，作者用了几种巧妙的方法：

染色法（给积木涂色）：
想象给每个数字涂上红、黄、蓝等颜色。作者发现，只要把某种颜色的所有数字都扔掉，剩下的数字就绝对不会出现“坏组合”。通过这种“牺牲一部分，保全大部分”的策略，他们证明了至少能留下那么多。
几何视角（多维空间）：
作者把每个数字看作多维空间里的一个点。那个“坏组合”在几何上就像一个“小角”（Unit Corner）。问题就变成了：在一个巨大的多面体里，最多能放多少个点，使得没有三个点连成一个“小角”？
递归公式（像剥洋葱）：
对于更精确的计算，作者设计了一套像剥洋葱一样的公式。你可以先算出前几个数字的答案，然后利用公式一步步推算出后面更大数字的答案，并且能算出误差范围。这意味着，理论上我们可以把那个“神奇的比例”算得无限精确。

5. 一些有趣的“意外”发现

没有简单的规律：
通常，如果数字序列有规律，我们就能轻松预测。但作者发现，在这个问题里，决定“选还是不选”的序列，并不是那种简单的重复模式（比如“选、不选、选、不选”循环）。它更像是一种看似随机、实则受深层结构控制的复杂舞蹈。
经典案例（2 和 3）：
当只考虑 2 和 3 时，作者不仅算出了那个著名的常数（约 0.66...），还证明了在这个游戏中，不存在一种“完美且嵌套”的选法。也就是说，你不能简单地先选前 10 个的最优解，再选前 11 个的最优解，然后发现前 10 个刚好包含在前 11 个里。随着数字增加，最优的“选法”结构会发生剧烈的重组，就像搭积木时，为了加一块新积木，你可能需要把前面搭好的部分完全拆掉重搭。

总结

这篇论文就像是在探索**“数字宇宙中的生存法则”**。它告诉我们，在由特定质数生成的数字世界里，虽然存在严格的“连坐”规则（选了小的就不能选特定的大的），但我们依然可以保留大部分数字（约 $\frac{r}{r+1}$ ）。

作者不仅给出了这个比例，还发明了一套精密的“计算器”，让我们可以算出这个比例到底是多少，甚至精确到小数点后很多位。这展示了组合数学和数论结合时产生的美妙与深度。

这是一份关于 Nikola Veselinov 论文《S-光滑数中禁止构型的极值密度》（Extremal Densities for Forbidden Configurations in S-Smooth Numbers）的详细技术总结。

1. 研究背景与问题定义

核心问题：
本文研究的是在由有限素数集 $S = \{p_1, \dots, p_r\}$ 生成的乘法半群 $M(S)$ （即 $S$ -光滑数集合）中，寻找最大子集 $A$ 的问题，使得 $A$ 中不包含特定的“禁止构型”（forbidden configuration）。
具体而言，禁止构型定义为：对于任意 $n \in A$ ，集合 $\{n, p_1n, \dots, p_rn\}$ 不能全部包含在 $A$ 中。

符号定义：

$M(S)$ ：由 $S$ 生成的 $S$ -光滑数集合。
$\Psi_S(X)$ ：不超过 $X$ 的 $S$ -光滑数的个数。
$F_S(X)$ ：在 $M(S) \cap [1, X]$ 中，不包含任何 $\{n, p_1n, \dots, p_rn\}$ 的子集的最大大小。
$f_S(k)$ ：在前 $k$ 个 $S$ -光滑数 $\{d_1, \dots, d_k\}$ 中，满足上述条件的子集的最大大小。
目标：确定当 $X \to \infty$ 时 $F_S(X)$ 的渐近行为，以及对应的密度常数。

历史背景：
该问题推广了经典的 Graham-Witsenhausen-Spencer 问题（即 $S=\{2, 3\}$ 时，寻找不含 $\{x, 2x, 3x\}$ 的最大子集）。此前研究主要集中在整数区间 $[1, N]$ 上，而本文专注于 $S$ -光滑数这一稀疏子集上的极值问题。

2. 方法论与数学工具

作者结合了组合数论、格点几何和解析数论的方法：

指数坐标与加权单纯形（Weighted Lattice Simplex）：
- 将 $S$ -光滑数 $n = p_1^{a_1} \cdots p_r^{a_r}$ 映射到指数向量 $(a_1, \dots, a_r) \in \mathbb{Z}_{\ge 0}^r$ 。
- 禁止构型 $\{n, p_1n, \dots, p_rn\}$ 对应于格点中的“单位角”（unit corner）： $\{a, a+e_1, \dots, a+e_r\}$ ，其中 $e_i$ 是标准基向量。
- 问题转化为在加权单纯形 $\Sigma_S(u) = \{a \in \mathbb{Z}_{\ge 0}^r : \sum a_i \log p_i \le u\}$ 中寻找最大无角子集。
模着色论证（Modular Coloring Argument）：
- 为了获得下界，定义了一个从 $\mathbb{Z}_{\ge 0}^r$ 到 $\mathbb{Z}/(r+1)\mathbb{Z}$ 的着色函数： $\chi(a) = \sum_{i=1}^r i \cdot a_i \pmod{r+1}$ 。
- 引理证明每个单位角恰好包含每种颜色各一个点。因此，移除任意一种颜色类即可破坏所有单位角。
- 通过计算各颜色类的分布，得出下界估计。
恒等式与上界推导：
- 利用向后移位（backward shift）算子和计数恒等式，建立了无角子集大小与单纯形边界点数量之间的关系。
- 证明了 $|A| \le \frac{r}{r+1}|\Sigma_S(u)| + O(u^{r-1})$ 。
递归与尾部估计：
- 对于全区间 $[1, N]$ 的问题，利用 $S$ -光滑数的唯一分解性质（ $n = m \cdot d$ ，其中 $d \in M(S)$ 且 $(m, P_S)=1$ ），将问题分解为 $S$ -光滑数子问题。
- 推导了密度常数 $\alpha_S$ 的显式级数表示，并给出了计算倒数尾部（reciprocal tail）的递归公式。

3. 主要结果

3.1 渐近公式（定理 1.1）

对于 $r \ge 2$ 的素数集 $S$ ，当 $X \to \infty$ 时：
$F_S(X) = \frac{r}{r+1} \Psi_S(X) + O_S((\log X)^{r-1})$
等价地，对于前 $k$ 个 $S$ -光滑数：
$f_S(k) = \frac{r}{r+1} k + O_S(k^{(r-1)/r})$
意义： 在 $S$ -光滑数集合中，最大无禁止构型子集的密度趋近于 $\frac{r}{r+1}$ 。这与全整数区间上的密度常数不同，体现了光滑数结构的特殊性。

3.2 全区间密度常数（推论 1.2 & 1.3）

对于全区间 $[1, N]$ 上的最大子集大小 $G_S(N)$ ，存在常数 $\alpha_S$ 使得：
$G_S(N) = \alpha_S N + O_S((\log N)^r)$
其中密度常数 $\alpha_S$ 可表示为：
$\alpha_S = c_S \sum_{k \ge 1} \frac{\Delta f_S(k)}{d_k^{(S)}}$
这里 $c_S = \prod_{p \in S} (1 - 1/p)$ ， $\Delta f_S(k) \in \{0, 1\}$ 表示第 $k$ 个光滑数是否被选入最优解。
计算性： 作者给出了嵌套的可计算上下界 $L_{S,N} \le \alpha_S \le U_{S,N}$ ，其宽度随 $N$ 增大而减小，允许任意精度计算 $\alpha_S$ 。

3.3 有理倒数和的非周期性（命题 1.4）

发现： 即使倒数和 $\sum \frac{c_k}{d_k^{(S)}}$ 是有理数，二进制序列 $(c_k)$ 也不一定是最终周期的（eventually periodic）。
意义： 打破了以往关于此类级数有理性与序列周期性之间关系的直觉，展示了 $S$ -光滑数序列结构的复杂性。

3.4 经典情况 $S=\{2, 3\}$

恢复了 Graham-Spencer-Witsenhausen 常数 $\alpha$ 。
给出了显式的尾部公式。
结构命题（命题 6.2）： 证明了不存在嵌套的最优子集序列 $A_1 \subseteq A_2 \subseteq \dots$ 。即随着 $k$ 增加，最优解的结构会发生“跳跃”，不能通过简单地在前一个最优解中添加元素得到。

4. 关键贡献与意义

解决了光滑数上的极值问题： 首次给出了 $S$ -光滑数集合中禁止构型问题的精确渐近公式，确定了主项系数为 $\frac{r}{r+1}$ 。
建立了与全区间问题的联系： 通过分解技术，将光滑数子问题与全整数区间问题联系起来，提供了计算经典密度常数 $\alpha_S$ 的有效算法框架。
揭示了结构复杂性： 证明了最优解不具备嵌套性（nestedness），且有理倒数和不一定对应周期序列，丰富了组合数论中对禁止构型结构的理解。
提供了计算工具： 提出的递归公式和嵌套界限使得计算具体的密度常数成为可能，并提供了开源代码支持数值验证。

5. 总结

这篇论文通过巧妙的格点几何映射和组合着色技术，成功刻画了 $S$ -光滑数中避免特定乘法构型的最大子集密度。其结果不仅推广了经典的整数极值问题，还揭示了光滑数集合独特的算术结构（如非嵌套的最优解和非周期的有理级数），为解析数论和组合数学的交叉研究提供了新的视角和工具。