Bounds for Greedy $B_h$-sets

技术摘要：贪婪 $B_h$-集的界限

问题陈述
本文研究了应用于构造 $B_h$-集的贪婪算法的渐近行为。一个非负整数集合 $A$ 被定义为 $B_h$-集，如果对于方程 $a_1 + \dots + a_h = b_1 + \dots + b_h$（其中 $a_i, b_i \in A$）的每一个解，都意味着多重集 $\{a_1, \dots, a_h\}$ 与 $\{b_1, \dots, b_h\}$ 是相同的。研究的核心对象是贪婪 $B_h$-集，记作 $G(h) = \{\gamma_0, \gamma_1, \gamma_2, \dots\}$，它是通过字典序构造的，设定 $\gamma_0 = 0, \gamma_1 = 1$，并定义 $\gamma_{k+1}$ 为使得 $\{\gamma_0, \dots, \gamma_{k+1}\}$ 仍为 $B_h$-集的最小整数。

核心问题在于确定在固定 $k$ 的情况下，第 $k$ 个元素 $\gamma_k(h)$ 关于 $h$ 的增长率。虽然对于 $k \le 4$ 已知精确公式，但对于 $k \ge 5$ 的行为在计算枚举之外仍很大程度上未被探索。本文旨在为 $\gamma_k(h)$ 建立非平凡的上界和下界，特别针对第五个元素 $\gamma_5(h)$ 以及针对 $k \ge 5$ 的一般界限。

方法论
作者结合了组合分析、递归定界和详细的案例枚举：

1. 组合界限： 本文利用了这样一个观察：大小为 $k+1$ 的集合的互异 $h$ 次和的数量为 $\binom{k+h}{k}$。由于这些和必须落在区间 $[h\gamma_0, h\gamma_k]$ 内，这给出了一个基准下界 $\gamma_k(h)$。
2. “Mex”特征： 一个关键引理确立了 $\gamma_{k+1} = \text{mex}(F^{(k)})$，其中 $F^{(k)}$ 是在特定约束下由 $\frac{1}{r}\sum_{i=1}^k \gamma_i(m_i - m'_i)$ 表示的所有整数构成的集合。这一特征允许作者通过计算 $F^{(k)}$ 中超过某一阈值的“禁止”值的数量来限定 $\gamma_{k+1}$。
3. 下界构造 ($\gamma_5$)： 为了证明 $\gamma_5(h)$ 的下界，作者定义了一个特定的整数向量集 $\Delta$，代表前四个元素的有效系数组合。通过按照特定的（基于某种“里程表”风格的）排序方式对这些向量进行排序，并分析这些向量与 $\langle \gamma_1, \gamma_2, \gamma_3, \gamma_4 \rangle$ 的点积的像，作者证明了它们的像形成了一个连续区间。这确保了“mex”（第一个缺失的整数）至少是这些像的一个特定子集的最大值。
4. 上界构造 ($\gamma_k$)： 对于上界，作者采用了归纳法。假设 $\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$，作者估计了集合 $F^{(k)}$ 在阈值 $\beta_k h^k$ 之上的规模。通过根据最大元素 $\gamma_k$ 的重数对集合 $F^{(k)}$ 进行分层，并应用“隔板法”组合计数，作者推导出了关于系数 $\alpha_k$ 的递推关系。该序列 $\alpha_k$ 被构造为非增且收敛于零。

主要贡献与结果

• $\gamma_5(h)$ 的下界： 本文为第五个贪婪 $B_h$-集元素建立了非平凡的下界：
  $$\gamma_5(h) \ge \frac{1}{8}h^4 + \frac{1}{2}h^3$$
  该结果是通过对前四个元素生成的禁止和进行的严格分析得出的。

• $\gamma_k(h)$ 的上界 ($k \ge 5$)： 本文提供了 $k \ge 5$ 时 $\gamma_k(h)$ 的第一个非平凡上界。具体而言，它证明了：
  $$\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$$
  其中常数 $\alpha_k$ 是递归定义的。本文明确计算了：

  • $\alpha_5 \approx 0.467214$
  • $\alpha_6 \approx 0.382978$
  • $\alpha_7 \approx 0.269877$
  • 对于 $k \ge 7$，$\alpha_{k+1} = \frac{1}{2} \alpha_k + \frac{1}{2^k k!} \sum_{j=0}^{k-1} \binom{k-1}{j} \binom{k}{j} 2^j$。
    该序列 $\alpha_k$ 被证明快速衰减，这意味着 $\gamma_k(h)$ 的增长速度比此前可能未证实的估计要慢。

• 关于 $\gamma_5(h)$ 的猜想： 基于对 $h \le 47$ 的计算数据，作者提出了一个精确的渐近公式猜想：
  $$\gamma_5(h) = \frac{1}{3}h^4 + O(h^3)$$
  这表明 $1/8$ 的下界并不紧致，真实的领先系数很可能是 $1/3$。

• 一般下界： 本文重申并阐释了一般下界 $\gamma_k(h) \ge \frac{1}{k!}h^{k-1} + O(h^{k-2})$，确认了贪婪算法产生的集合具有正确的固定 $k$ 时的增长阶。

意义与主张
作者从三个主要方面阐述了这项工作的意义：

1. 审美与理论必要性： $B_h$-集是组合数论中的基本对象。作者认为，理解贪婪算法对这些集合的输出是一个自然的问题，值得寻求答案，且独立于直接的应用。
2. 贪婪分析的可行性： 本文将分析贪婪算法与非贪婪构造（如使用有限域的 Singer 构造）的难度进行了对比。虽然通过有限域构造一个包含 11 个元素的 $B_{100}$-集需要处理 $\mathbb{F}_{101}^{11}$（这在计算上是不可行的），但寻找 $B_{100}$-集的第 10 个元素的公式被描述为“困难但可行”。这项工作是使这种分析在 $k \ge 5$ 时实现严谨化的第一步。
3. 理解贪婪算法： 主要动机是更好地理解用于 $B_2$-集（Sidon 集）的贪婪算法，这些集合在物理现实世界中有实际应用（例如 Golomb 尺）。由于贪婪算法是加法问题中一种标准的启发式方法，因此为 $B_h$-集建立界限有助于更深入地理解加法数论中的贪婪策略。

文章最后列出了开放问题，包括证明 $\gamma_k$ 的拟多项式公式、元素在同余类中的均匀分布，以及使得贪婪 $B_h$-集的倒数幂之和收敛的 $s$ 的下确界。作者保持谦逊，指出虽然这些界限是非平凡的，但可能并不紧致，且对于 $k \ge 5$ 的精确系数仍处于猜想阶段。