**受限整数分拆函数的多项式增长与加法补集——对Dai-Chen问题的肯定解答**

《Bulletin of the Australian Mathematical Society》：RESTRICTED PARTITION FUNCTIONS AND ADDITIVE COMPLEMENTS

　　

设?为正整数集。对于子集??, ? ? ?和n ∈ ?，令p(n, ??, ?)表示n的形如n = ∑_a∈?? m_a a的表示数（representation number），其中对于所有a ∈ ??，m_a ∈ ? ∪ {0}，且仅有有限多个m_a非零。研究人员证明了存在两个无限正整数集?? = {a_n}_n=1^∞和?，使得lim_n→∞((log a_n+1 ? log a_n)/log n) = +∞，对每个n ∈ ?有p(n, ??, ?) > 0，且p具有多项式增长（polynomial growth）。更一般地，研究人员提供了一个构造，将具有多项式增长的受限分拆函数（restricted partition function）与满足简单计数条件的加法补集（additive complements）联系起来。这肯定地回答了Dai和Chen的问题。

## 论文解读：受限分拆函数的多项式增长与加法补集

### 一、研究背景与问题提出

受限整数分拆函数（restricted integer partition function）由Canfield和Wilf首次引入，记作p(n, ??, ?)，定义为将正整数n表示为集合??中元素的线性组合的方式数，其中系数必须取自集合? ∪ {0}，且仅有有限多个系数可以非零。若存在常数c > 0和整数n₀，使得对所有n ≥ n₀均有p(n, ??, ?) ≤ n^c，则称该分拆函数p具有多项式增长（polynomial growth）。

围绕受限分拆函数的多项式增长问题，学界已有若干重要进展。Alon对Canfield-Wilf问题给出了更强的回答，证明了存在两个显式的无限正整数集??和?，使得对所有n ≥ 1有p(n, ??, ?) = 1。对于?? = {n!}_n≥1或?? = {nⁿ}_n≥1，Alon进一步证明了存在n₀和无限集?，使得对所有n > n₀有0 < p(n, ??, ?) < n^8+o(1)，从而肯定地回答了Ljuji?和Nathanson的两个问题。2016年，Dai和Chen通过初等归纳论证将Alon结果中的指数从8+o(1)改进为2+o(1)。更一般地，Dai和Chen对所有满足

c₁(n+1)^θ₁ a_n ≤ a_n+1 ≤ c₂(n+1)^θ₂ a_n（n = 1, 2, 3, …）

的集合?? = {1 = a₁ < a₂ < …}（其中c₂ > c₁ > 0和θ₂ ≥ θ₁ > 0为常数）得到了统一结果。

基于上述工作，Dai和Chen提出了一个更具挑战性的问题（Question 1）：是否存在两个无限正整数集?? = {a_n}_n=1^∞和?，使得

lim_n→∞(log a_n+1 ? log a_n)/log n = +∞，

对所有充分大的n有p(n, ??, ?) > 0，且p具有多项式增长？该条件的苛刻之处在于，它要求序列{a_n}的增长速度远超Dai-Chen统一结果所涵盖的范围——相邻项的比值不再受多项式因子控制，而是可以任意快速地增长。这迫使研究人员寻求全新的构造思路。

### 二、研究内容与重要意义

本文的核心贡献是肯定地回答了Dai-Chen问题。研究人员首先建立了一个更具一般性的定理（定理2），该定理深刻地揭示了加法补集（additive complements）与受限分拆函数多项式增长之间的内在联系。在此基础上，研究人员利用Ruzsa关于2的幂的加法补集的经典结果（命题3），具体构造出满足Dai-Chen问题极端增长条件的集合??和?（推论4），从而完整地解决了该问题。这一工作的意义不仅在于回答了一个悬而未决的问题，更在于提供了将加法补集理论应用于受限分拆函数研究的通用框架。

### 三、关键技术方法

研究人员使用的主要技术方法包括：（1）二进制展开（binary expansion）与加法补集的结合——利用任意正整数可唯一表示为2的幂之和这一基本事实，将整数的二进制展开与完全加法补集的分解性质相结合，实现从任意表示到受限分拆形式的转换；（2）计数函数（counting function）估计——通过分析加法补集的计数函数上界?(x)??(x) ? x，估计满足s+b ≤ N的数对(s,b) ∈ ??×?的数量，从而导出分拆函数的多项式增长上界；（3）Ruzsa关于lacunary序列（项与项之间间隔迅速增大的序列）的加法补集定理——该定理断言存在稀疏子集?? ? ?满足??(x) ? x/log x，使得每个充分大的整数均可表示为2^k+s的形式（k ∈ ?, s ∈ ??），为构造满足极端增长条件的??序列提供了关键工具。论文的构造是纯存在性的，不涉及具体的样本队列或实验数据。

### 四、主要研究结果

**定理2：加法补集到受限分拆函数的通用构造。** 设?和??是完全加法补集（complete additive complements），即? + ?? = ?₀（?₀ = ? ∪ {0}为非负整数集），且满足计数条件?(x)??(x) ? x。令

?? = {2^b : b ∈ ?}，? = {∑_d∈?? 2^d : ?? ? ??, 0 < |??| < ∞}，

则对每个n ∈ ?有p(n, ??, ?) > 0，且p具有多项式增长。

定理2的证明分两步。第一步证明p(n, ??, ?) > 0：将n进行二进制展开，得n = ∑_j∈?? 2^j（?? ? ?₀为有限非空集）。由? + ?? = ?₀，每个j可写为j = s_j + b_j，其中s_j ∈ ??，b_j ∈ ?。于是n = ∑_j∈?? 2^s_j 2^b_j。将具有相同b_j的项合并，得n = ∑_b∈? (∑_{j∈??, bj=b} 2^s_j)·2^b。由于j互异，对应相同b的s_j也互异，故每个非零内和均属于?，从而该表示被p(n, ??, ?)计数。

第二步证明多项式增长：对任意被计数的表示n = ∑_b∈? m_2^b 2^b，由二进制展开的唯一性，每个非零系数m_2^b对应唯一的有限非空集??_b ? ??。由此确定集合?? = {(s,b) ∈ ??×? : s+b ≤ N}（其中N = log n/log 2），且从表示到??的映射是单射。因此p(n, ??, ?) ≤ 2^f(N)，其中f(N) = #{(s,b) ∈ ??×? : s+b ≤ N} ≤ ??(N)?(N) ≤ c₀N（c₀ > 0为常数）。代入N = log n/log 2即得p(n, ??, ?) ≤ 2^{c₀ log n/log 2} ≤ n^c₀，完成证明。

**推论4：Dai-Chen问题的肯定回答。** 取? = {0} ∪ {2^k : k = 0, 1, 2, …}。由Ruzsa定理（命题3），存在?? ? ?₀满足??(x) ? x/log x，且? + ?? = ?₀（因0 ∈ ?，有限多个缺失值可直接补入??而不影响渐近估计）。由于当x ≥ 2时?(x) ? log x，故?(x)??(x) ? x，定理2的条件全部满足。令?? = {2^b : b ∈ ?} = {a_n}_n=1^∞（按递增排列），则a₁ = 1，对n ≥ 2有a_n = 2^2n?2，直接计算得

lim_n→∞(log a_n+1 ? log a_n)/log n = lim_n→∞((2^n?1 ? 2^n?2)log 2)/log n = +∞。

令? = {∑_d∈?? 2^d : ?? ? ??, 0 < |??| < ∞}，由??的无限性知?为无限集。根据定理2，对每个n ∈ ?有p(n, ??, ?) > 0，且p具有多项式增长。Dai-Chen问题由此得到肯定回答。

### 五、总结与结论

本文通过建立加法补集与受限分拆函数之间的深刻联系，不仅肯定地回答了Dai-Chen问题，而且提供了一个通用的构造框架。定理2的证明巧妙地利用二进制展开作为桥梁，将受限分拆的系数约束转化为对加法补集的组合操作，展示了数论中不同领域交叉运用的效力。推论4的构造表明，即使在序列增长极快的情况下，仍可存在相应的系数集?使得分拆函数既保持处处为正又具有多项式增长，这大大拓展了人们对受限分拆函数行为的认识。

研究结论（翻译自摘要）：研究人员证明了存在两个无限正整数集?? = {a_n}_n=1^∞和?，使得lim_n→∞((log a_n+1 ? log a_n)/log n) = +∞，对每个n ∈ ?有p(n, ??, ?) > 0，且p具有多项式增长。更一般地，研究人员提供了一个构造，将具有多项式增长的受限分拆函数与满足简单计数条件的加法补集联系起来，从而肯定地回答了Dai和Chen的问题。