🔢 mathematics

On the Monotonicity of Higher-Fold Representation Functions

本文确定了特定 4 进制集合的高阶表示函数相邻值之差的多项式增长阶，并构造了一个密度为 1 的余无限集，使得对于所有 $h \ge 3$ 的阶，其表示函数均为严格递增的，从而解决了由 Dombi 在 2002 年提出的猜想与问题。

原作者： Csaba Sándor, Quan-Hui Yang

发布于 2026-06-30

📖 1 分钟阅读🧠 深度阅读

原作者： Csaba Sándor, Quan-Hui Yang

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

想象一下，你有一个装满编号瓷砖的巨大、无限的袋子：0, 1, 2, 3，以此类推。你决定挑选出一组特定的瓷砖放入一个特殊的盒子中。我们把这个盒子称为集合 A。

现在，想象你想用来自你盒中的恰好 $h$ 块瓷砖来建造一座高度为 $n$ 的塔。你可以多次使用同一个数字，且顺序很重要（例如，先 1 后 2 的塔与先 2 后 1 的塔是不同的）。

表示函数（Representation Function） 仅仅是一个计数器。它在问：“使用我盒中恰好 $h$ 块瓷砖，建造高度为 $n$ 的塔有多少种不同的方法？”

核心问题：数量是否总是会增加？

这个论文探讨了一个关于**单调性（monotonicity）**的谜题。如果你建造高度为 1, 2, 3, 4... 的塔，这种方法数量会一直增加吗？还是说有时会下降？

旧规则： 长期以来，数学家们认为，如果你的盒子缺少了无穷多个瓷砖（即“余无限”集合），那么建造塔的方法数量最终会开始随机跳动。你无法让它实现严格的持续增长。
惊喜： 一位名叫 Shallit 的数学家证明了这个旧规则对于高度为 3 ( $h=3$ ) 的塔是错误的。他发现了一个特殊的盒子，尽管该盒子缺少了无穷多个数字，但建造塔的方法数量却始终在增加。

作者的新发现

这篇由 Csaba Sándor 和 Quan-Hui Yang 撰写的论文深入研究了 Shallit 的发现。他们研究了任何高度（ $h \ge 3$ ）的塔，并提出了两个主要问题：

1. 数量增长得有多快？

Shallit 展示了数量在增加。Sándor 和 Yang 则追问：增加得有多快？

他们发现了一个特定的“特殊盒子”（我们称之为盒子 B），它是基于 4 进制数中的一种模式（就像我们的数字是基于 10 进制的，但这里是 0, 1, 2, 3）。

类比： 想象盒子 B 就像一个筛子，它只允许那些 4 进制“地址”以 1 或 2 开头的数字通过。这是一个非常特定且有节奏的模式。
结果： 他们证明了对于这个盒子 B，高度为 $n+1$ $n + 1$ 的塔与高度为 $n$ $n$ 的塔之间的数量差，是以一种可预测的多项式速度增长的。
- 如果你有一个高度为 3 的塔，“增长速度”大约与 $n^1$ 成正比（一条直线）。
- 如果你有一个高度为 4 的塔，“增长速度”大约与 $n^2$ 成正比（一条曲线）。
- 通常情况下，对于高度 $h$ ，增长速度与 $n^{h-2}$ 成正比。

这是一个重大的发现，因为它表明，尽管这个盒子存在巨大的空隙（缺失数字），但建造塔的方法数量表现得非常平滑，几乎就像你拥有盒中所有数字一样。

2. 我们能解决“密度”问题吗？

这里还有另一个谜题。上述提到的特殊盒子 B 有一个奇怪的属性：如果你计算直到某个点为止盒子中包含的瓷砖数量，其百分比会剧烈波动。它不会稳定在一个单一的数值上。

一位名叫 Dombi 的数学家问道：“我们能否找到一个盒子，其瓷砖的百分比能稳定在一个特定的数值（比如 60% 或 90%），并且建造塔的方法数量仍然严格递增？”

解决方案： 作者构建了一个新的盒子，盒子 C。
运作方式： 盒子 C 几乎包含了所有的数字，它只是移除了一组非常稀疏的数字（具体来说，是像 1024, 2048 等 2 的幂次方）。
结果： 因为他们只移除了这些零星散布的数字，所以盒子的“密度”本质上是 100%（或 1）。
神奇之处： 尽管移除了这些特定的数字，但对于任何高度（ $h \ge 3$ ）的塔，建造塔的方法数量仍然严格递增。这回答了 Dombi 的问题：是的，你可以拥有一个“几乎全满”的盒子，并且依然保持这种严格递增的性质。

“要点”总结

模式： 存在一种特定的、有节奏的选取数字的方式（盒子 B），使得无论你如何堆叠（只要高度为 3 或更高），求和的方法数量总是在增加。
速度： 他们精确地计算了这种增长速度。它遵循一个整齐的数学曲线（ $n^{h-2}$ ），这与你拥有所有数字时的增长速度是一致的，尽管盒子 B 缺失了无穷多个数字。
密度修复： 他们还构建了第二个盒子（盒子 C），它是“几乎所有数字”（99.9% 完整）的集合，并且依然保持着方法数量严格递增。这解决了关于盒子的“充实度”是否会影响这一性质的问题。

简而言之，这篇论文证明了，你并不需要一个“完美”的数字集合，也能获得一个完美的、始终递增的组合模式。即使存在特定的、有节奏的间隙，数学运算依然展现出了优美的规律。

技术摘要：关于高阶表示函数的单调性

问题陈述
本文研究了有序 $h$ -阶表示函数 $R_{A,h}(n)$ 的单调性性质，其中 $R_{A,h}(n)$ 定义为满足 $n = a_1 + \dots + a_h$ 且 $a_i \in A$ 的有序解的数量，这里 $A \subseteq \mathbb{N}$ 。核心问题在于，对于一个其补集 $\mathbb{N} \setminus A$ 为无限集（即余无限集）的集合 $A$ ， $R_{A,h}(n)$ 是否可以严格递增。

在历史上，Erdős、Sárközy 和 Sós 证明了对于 $h=2$ 的情况，严格单调性意味着 $A$ 是余有限集（即其补集是有限的）。对于 $h \ge 3$ ，Dombi 曾猜想，如果 $\mathbb{N} \setminus A$ 是无限的，则 $R_{A,h}(n)$ 不可能最终严格递增。这一猜想被 Shallit 所推翻，他利用自动机理论构造了一个余无限集 $A$ ，使得 $R_{A,3}(n)$ 是严格递增的。具体而言，Shallit 利用集合 $B = \{0\} \cup \{m \ge 1 : m \text{ 的四进制展开以 1 或 2 开头}\}$ 进行了研究。虽然 Shallit 确立了对于固定的 $h \ge 3$ ，集合 $B$ 的 $R_{B,h}(n)$ 具有严格单调性，但差分函数 $R_{B,h}(n+1) - R_{B,h}(n)$ 的精确增长率仍是一个开放的定量问题。此外，Dombi 提出了一个关于是否存在渐近密度 $\alpha \neq 1/2$ （或具体而言 $\alpha \neq 1$ ）的此类集合的问题。

研究方法
作者结合了生成函数、由集合 $B$ 的自相似结构导出的递推关系以及卷积论证，来建立差分函数 $\Delta_h(n) = R_{B,h}(n+1) - R_{B,h}(n)$ 的界限。

集合 $B$ 的递推分析：
集合 $B$ 由其指示序列 $c_n$ 定义，该序列满足生成函数 $C(x) = \sum c_n x^n$ 的泛函方程：
$C(x) = (1+x+x^2+x^3)C(x^4) - x^3$
通过对该方程进行平方和立方运算，作者推导出了二阶（ $\beta_n$ ）和三阶（ $\alpha_n$ ）表示函数差值的递推关系。
- 引理 2.1 & 2.2： 这些引理建立了基于索引 $n/4$ 处的 $\beta_n$ 和 $\alpha_n$ 的递归公式。
- $\beta_n$ 的界限： 引理 3.1 证明了二阶函数的差值是有界的： $-1 \le \beta_n \le 2$ 。
- $\alpha_n$ 的界限： 利用 $\beta_n$ 的界限和递推关系，引理 3.2 确立了线性下界 $\alpha_n \ge n/5 + 4$ （对于 $n \ge 78$ ），而引理 3.3 则提供了线性上界 $\alpha_n \le 3n + 2$ 。
卷积提升：
为了将 $h=3$ 的结果扩展到任意 $h \ge 3$ ，作者利用了卷积恒等式：
$R_{p+q}(n) = \sum_{u=0}^n R_p(n-u)R_q(u)$
这导致了差分关系的建立：
$\Delta_{p+q}(n) = \sum_{u=0}^n \Delta_p(n-u)R_q(u) + R_p(0)R_q(n+1)$
通过令 $p=3$ 且 $q=h-3$ ， $\Delta_h(n)$ 的行为受到已知的 $\Delta_3(n)$ （即 $\alpha_n$ ）的行为以及 $R_{h-3}(n)$ 增长性的控制。
集合 $C$ 的构造：
为了解决 Dombi 关于渐近密度的难题，作者构造了一个集合 $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$ 。他们通过分析生成函数 $G_C(x) = (1-x)^{-1} - D(x)$ （其中 $D(x)$ 对应于被移除的 2 的幂次）来研究该集合。由于被移除集合的稀疏性，他们能够对差分 $R_{C,h}(n+1) - R_{C,h}(n)$ 进行显式估计。

主要贡献与结果

多项式阶增长（定理 1.1）：
本文证明了对于集合 $B$ ，差分 $R_{B,h}(n+1) - R_{B,h}(n)$ 以 $n^{h-2}$ 的多项式阶增长。具体而言，对于每一个整数 $h \ge 3$ ，存在常数 $c_h, C_h > 0$ ，使得对于所有 $n \ge 1$ ：
$c_h n^{h-2} \le R_{B,h}(n+1) - R_{B,h}(n) \le C_h n^{h-2}$
这一结果证实，尽管 $B$ 拥有一个具有巨大间隙的无限补集，其表示函数的行为在渐近意义上仍与全集 $\mathbb{N}$ （其差分为 $\binom{n+h-1}{h-2} \asymp n^{h-2}$ ）保持一致。
任意 $h \ge 3$ 的严格单调性：
作者严格证明了对于所有 $n \ge 0$ 及所有 $h \ge 3$ ，均有 $R_{B,h}(n+1) > R_{B,h}(n)$ 。这改进了 Shallit 的结果，因为 Shallit 的研究仅侧重于此类集合的存在性，而未量化所有 $h$ 的增长率。
解决 Dombi 的密度问题（定理 1.2）：
本文构造了一个余无限集 $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$ ，使得：
- 其渐近密度存在且等于 1： $\lim_{n \to \infty} C(n)/n = 1$ 。
- 其表示函数 $R_{C,h}(n)$ 对于每个整数 $h \ge 3$ 都是严格递增的。
  这通过提供一个密度为 1 的集合（不同于此前已知的密度为 1/2 的例子）回答了 Dombi 的问题，该集合依然保持着严格单调性。

意义
本文完善了对余无限集中加法表示函数的理解。它表明，在 $h \ge 3$ 的情况下，我们在 $h=2$ 时发现的单调性障碍并不存在，即使该集合拥有一个“巨大”的无限补集。通过确立差分函数的精确多项式阶，作者展示了集合 $B$ 在表示增长方面保留了全集整数的“平滑性”。此外，集合 $C$ 的构造扩展了此类集合的已知范畴，表明严格单调性可以与渐近密度 1 相容，从而缩小了余有限集与余无限集行为之间的差距，这在加法数论中具有重要意义。

作者最后提出了关于是否存在具有任意给定密度 $d \in [0, 1)$ 以及具有特定下极限和上极限密度的此类集合的开放问题，表明对于表示函数的单调性条件的完整表征仍是一个活跃的研究领域。