🔢 mathematics

Restricted partition functions and additive complements

本文通过构造无穷正整数集，在确保每个正整数至少有一种表示形式的同时，使限制划分函数具有多项式增长性，从而对 Dai 和 Chen 在 2016 年提出的一个问题给出了肯定的回答。

原作者： Yuchen Ding

发布于 2026-06-17

📖 2 分钟阅读🧠 深度阅读

原作者： Yuchen Ding

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

想象一下，你拥有一个装满特殊积木的巨大、无限的工具箱。每块积木的大小都由一个名为 集合 A 的列表中的数字决定。你还拥有一本特殊的规则手册，名为 集合 M，它规定了你可以使用每种积木的数量。

数学家 Yuchen Ding 在这篇论文中提出了一个非常具体的问题：我们能否设计这两个列表（A 和 M），使得我们能够构建出每一个正整数（1, 2, 3 等等），同时又不让构建这些数字的方法变得失控？

以下是使用日常类比对这些概念进行的详细拆解：

1. 建筑积木（受限分拆）

把数字 $n$ （比如 100）想象成你想建造的一座塔。

集合 A 是你可用的积木尺寸列表（例如 1, 4, 16, 256...）。
集合 M 是关于“倍数”的规则手册。它规定：“你可以使用 0, 1 或 2 个 4 块积木，但对于 16 块积木，可能只能使用 0, 5 或 10 个。”
目标： 你希望能够根据这些规则构建出任何数字 $n$ 。
问题： 如果构建同一个数字的方法太多，数学处理起来就会变得非常混乱。作者想要证明，构建任何一座塔（ $p$ ）的方法数量增长得很慢——具体来说，是“多项式级增长”。

类比： 想象你正在烘焙饼干。

如果你有 100 种不同的巧克力豆饼干食谱，那要记录起来就非常麻烦。
“多项式级增长”意味着，随着你尝试制作越来越大的饼干批次，你发现的新独特食谱的数量并不会瞬间爆炸式增长。它的增长是可控的、可预测的。

2. “间隙”问题

在此之前，数学家们知道如何制作一些列表，使得我们可以构建出所有数字，但这些积木之间的“间隙”并不会很大。

问题： 我们能否制作一个列表，其中的积木尺寸增长得 极其迅速？想象一下这样一个列表：第一个积木大小是 1，下一个是 100，再下一个是 10,000，再下一个是 1,000,000。
这些数字之间的间隙如此之宽，以至于数学逻辑通常会崩溃，导致要么无法构建出所有数字，要么导致方案数量爆炸。

3. 解决方案：“完美配对”

Ding 证明了答案是 肯定的。你可以创造出这些巨大的间隙，同时仍能用可控的方案数量来构建出所有数字。

他通过引入一个涉及 加法补集（Additive Complements） 的巧妙技巧来实现这一点。

隐喻： 想象有两个团队，B 队和 S 队。
- B 队成员的数值是 2 的幂（1, 2, 4, 8, 16...）。
- S 队是一个特殊的数字组，它们负责填补 B 队留下的“空洞”。
- 在一起时，如果你从 B 队选一个人，再从 S 队选一个人，并将他们的“值”相加，你可以组成数轴上的 每一个 数字。它们是“互补”的。

Ding 利用数学家 Ruzsa 的一个著名结果，找到了一个足够稀疏以保证其趣味性、又足够稠密以填补间隙的 S 队。

4. 构建过程是如何运作的

Ding 根据这两个团队创建了他的两个神奇列表 A 和 M：

集合 A（积木）： 他取自 B 队中的数字，并将它们转化为 2 的幂（例如 $2^1, 2^2, 2^4, 2^8...$ ）。这创造了问题中所要求的“巨大间隙”。
集合 M（规则）： 他基于 S 队创建规则。这些规则允许你组合来自 S 队的小部分来形成系数（即“多少个”的部分）。

神奇之处： 因为 B 队和 S 队是完美的互补关系，所以你总能将任何数字分解为符合这些规则的和。因为 S 队是经过精心挑选的，所以这样做的方法数量不会爆炸；它会保持在“多项式”限制内（即一种可控的增长率）。

5. 为什么这很重要（根据论文所述）

这篇论文回答了 Dai 和 Chen 在 2016 年提出的一个特定问题。

问题： “是否存在两个无限集合，使得积木之间的间隙无限增大，但我们仍然可以用有限且可控的组合方式构建出所有数字？”
答案： 是的。Ding 构造了一个特定的例子，其中积木之间的间隙增长得如此之快，以至于它们对数的比值趋于无穷大，但该系统仍然完美运行。

关于“AI”成分的说明

作者 Yuchen Ding 公开表示，他在研究过程中使用了 AI 工具（ChatGPT）。

AI 做了什么： 它建议研究涉及 2 的幂的集合，并引导他关注 Ruzsa 关于“稀疏序列”（lacunary sequences，即具有大间隙的序列）的一个特定定理。
作者做了什么： 作者验证了数学逻辑，检查了推导过程，重新组织了证明，并撰写了最终论文。他对工作的准确性负全部责任。

总结

Yuchen Ding 解开了一个关于“数字构建”的谜题。他证明了你可以拥有一组间隔极其遥远（就像梯子的横档变得越来越宽）的建筑积木，以及一套使用它们的规则，使得：

你可以构建出 每一个 整数。
构建它们的方法数量 不会失控。

这就像是在证明，你可以拥有一把横档间距达一英里的梯子，但只要使用一套特定的、可控的攀爬技巧，你依然可以平稳地向上攀爬，而不会摔倒。

技术摘要：受限分拆函数与加性补集

问题陈述
本文探讨了加性数论中关于受限分拆函数的一个特定问题。令 $\mathbb{N}$ 为正整数集， $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$ 。对于子集 $A, M \subseteq \mathbb{N}$ ，受限分拆函数 $p(n, A, M)$ 计算将整数 $n$ 表示为如下形式的次数：
$n = \sum_{a \in A} m_a a$
其中对于所有 $a \in A$ ，有 $m_a \in M \cup \{0\}$ ，且仅有有限个 $m_a$ 非零。若存在常数 $c > 0$ 和 $n_0$ ，使得对于所有 $n \geq n_0$ ，都有 $p(n, A, M) \leq n^c$ ，则称该函数 $p$ 具有多项式增长性。

由 Dai 和 Chen 在 2016 年提出的核心问题（问题 1）是：是否存在两个无穷集合 $A = \{a_n\}_{n=1}^\infty$ 和 $M$ （均为正整数），满足以下条件：

集合 $A$ 是极度稀疏的，满足 $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ 。
对于所有充分大的 $n$ ， $p(n, A, M) > 0$ （即每个大整数皆可被表示）。
分拆函数 $p(n, A, M)$ 呈现多项式增长。

此前，Alon (2012) 和 Dai 与 Chen (2016) 的研究已经证明了在较宽松的稀疏性条件或特定的指数界限下（例如 $p(n) < n^{2+o(1)}$ ），存在满足此类条件的集合，但对于超对数级（super-logarithmic）稀疏性的情况，该问题仍悬而未决。

方法论
作者 Yuchen Ding 采用了一种基于加性补集和二进制展开的构造方法。其核心策略包括：

定义加性补集： 若两个集合 $B, S \subseteq \mathbb{N}_0$ 满足 $B + S = \mathbb{N}_0$ ，则称它们为完全加性补集。
构造集合 $A$ 和 $M$ ： 本文基于一对满足特定计数条件的加性补集 $B$ $B$ 和 $S$ $S$ 来构造 $A$ $A$ 和 $M$ $M$ 。具体而言：
- $A = \{2^b : b \in B\}$
- $M = \{ \sum_{d \in D} 2^d : D \subset S, 0 < |D| < \infty \}$ （来自 $S$ 的 2 的幂次的有限子集和）。
单射映射： 证明过程建立了一个从由 $p(n, A, M)$ 计算的表示形式到乘积空间 $S \times B$ 的有限子集的单射映射。通过利用二进制展开的唯一性，作者表明任何 $n$ 的表示都对应于一组满足 $s+b \leq \log_2 n$ 的对 $(s, b)$ 。
估计增长率： 这些表示的数量被限制在满足 $s+b \leq N$ （其中 $N \approx \log_2 n$ ）的对 $(s, b) \in S \times B$ 的数量之内。该计数被证明受限于 $S(N)B(N)$ 。若 $B(x)S(x) \ll x$ ，则所得的分拆函数呈多项式增长。

主要贡献与结果
本文通过以下结果，对 Dai 和 Chen 的问题 1 给出了肯定的回答：

定理 1： 设 $B$ 和 $S$ 为满足计数条件 $B(x)S(x) \ll x$ 的完全加性补集。若按照上述方式定义 $A$ 和 $M$ ，则对于每个 $n \in \mathbb{N}$ ，都有 $p(n, A, M) > 0$ ，且 $p(n, A, M)$ 具有多项式增长。
推论 1（解决问题 1）： 通过引用 Ruzsa (1972) 关于 2 的幂次之加性补集的结论，作者构造了满足定理 1 条件的具体集合 $A$ $A$ 和 $M$ $M$ 。
- 令 $B = \{0\} \cup \{2^k : k \geq 0\}$ 。
- 令 $S$ 为源自 Ruzsa 定理的 $\mathbb{N}$ 的子集，使得 $S(x) \ll x / \log x$ 且 $B+S = \mathbb{N}_0$ （在添加有限个元素后）。
- 由此产生的集合 $A$ 的元素为 $a_n = 2^{2^{n-2}}$ （对于 $n \geq 2$ ）。
- 该构造满足 $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ ，符合极度稀疏性的要求。
- 由于 $B(x) \ll \log x$ 且 $S(x) \ll x / \log x$ ，因此乘积 $B(x)S(x) \ll x$ 成立，确保了 $p(n, A, M)$ 的多项式增长。

意义
本文声称对 Dai 和 Chen 在 2016 年提出的问题给出了肯定的回答。它证明了即使在允许的部分集合 $A$ 非常稀疏（具体而言，满足相邻元素间的对数间隙增长速度快于任何 $\log n$ 的幂次）的情况下，构造出既是满射（表示所有正整数）又具有多项式增长的受限分拆函数是可能的。

这项工作通过将受限分拆函数的增长率直接与加性补集的计数性质联系起来，推广了先前的研究结果。作者指出，该构造最初是在生成式人工智能（ChatGPT）的辅助下进行探索的，AI 建议了集合的具体形式以及与 Ruzsa 定理的联系，但数学验证、重组及最终证明均为作者独立完成的工作。