On the Frobenius Number and Genus of a Collection of Semigroups Generalizing Repunit Numerical Semigroups

这是一篇关于数值半群（Numerical Semigroups）中**弗罗贝尼乌斯数（Frobenius number）和亏格（Genus）**问题的研究论文。作者刘飞虎（Feihu Liu）、辛国策（Guoce Xin）、叶苏婷（Suting Ye）和尹晶晶（Jingjing Yin）提出了一种统一的方法，解决了一类广义生成元序列的弗罗贝尼乌斯问题，并推广了包括 Repunit（单位数）、Mersenne（梅森数）、Thabit 和 Proth 数值半群在内的多种已知结果。

以下是该论文的详细技术总结：

1. 研究问题 (Problem)

核心问题：给定一个由互素正整数序列 $A = (a_1, a_2, \dots, a_n)$ 生成的数值半群 $\langle A \rangle$，确定其弗罗贝尼乌斯数 $F(A)$（即不在半群中的最大整数）和亏格 $g(A)$（即不在半群中的正整数个数）。

具体背景：

• 对于 $n=2$，Sylvester 给出了闭式解。
• 对于 $n \ge 3$，Curtis 证明了不存在通用的闭式公式。
• 现有的研究主要集中在特殊序列上，如等差数列、等比数列、Repunit 序列、Mersenne 序列、Thabit 序列和 Proth 序列等。
• 本文目标：构建一个统一的框架，处理一类形式更为广泛的生成元序列，特别是允许参数 $d$ 为负整数的情况，并解决 Proth 数值半群的一个开放问题。

2. 方法论 (Methodology)

论文的核心方法论基于**阿佩里集（Apéry set）和贪心算法（Greedy Algorithm）**的结合。

2.1 阿佩里集与弗罗贝尼乌斯数的关系

利用 Brauer 和 Shockley 的引理，弗罗贝尼乌斯数 $F(A)$ 和亏格 $g(A)$ 可以通过半群中模 $a$（生成元中最小的一个）的阿佩里集 $\text{Ape}(A, a) = \{N_0, N_1, \dots, N_{a-1}\}$ 来计算：

• $F(A) = \max(N_r) - a$
• $g(A) = \frac{1}{a} \sum N_r - \frac{a-1}{2}$
  其中 $N_r$ 是模 $a$ 余 $r$ 的最小半群元素。

2.2 引入广义集合 (Collection GCNS)

作者定义了一类广义数值半群 Collection GCNS，其生成元形式为：
$$A = (a, h_1a + db_1, h_2a + db_2, \dots, h_ka + db_k)$$
其中：

• $b_1 = 1, b_{i+1} = s_i b_i + 1$，且 $s_i \ge s_{i-1}$（这保证了序列 $B=(b_i)$ 是有序序列 orderly sequence）。
• $h_i = u b_i + 1$。
• $d$ 可以是正整数或负整数（这是本文的一个重要创新点，允许 $d < 0$）。

2.3 贪心算法与有序序列

关键突破在于利用序列 $B$ 的有序性（Orderly）。对于有序序列，最小化问题 $\text{opt}_B(M) = \min \sum x_i$ s.t. $\sum b_i x_i = M$ 可以通过贪心算法直接求解。
作者证明了在特定条件下（$ua + d + k - 2 \ge \sum s_i$ 且 $s_i \le u+1$），阿佩里集中的元素 $N_{dr}$ 随着 $r$ 的变化具有单调性，从而可以将 $F(A)$ 和 $g(A)$ 的计算转化为对 $a-1$ 的贪心表示（Greedy Presentation）的求和。

3. 主要贡献与结果 (Key Contributions & Results)

3.1 通用公式 (Theorem 2.12 & 2.13)

对于 Collection GCNS，在满足特定不等式约束下，作者给出了 $F(A)$ 和 $g(A)$ 的闭式公式：

• 弗罗贝尼乌斯数：$F(A) = \left(\sum_{i=1}^k x_i\right) a + (a-1)(ua+d) - a$，其中 $(x_1, \dots, x_k)$ 是 $a-1$ 关于序列 $B$ 的贪心表示。
• 亏格：给出了基于贪心表示元素和的求和公式。
• 伪弗罗贝尼乌斯数 (PF)：在特定条件下，还给出了伪弗罗贝尼乌斯数集合 $PF(A)$和类型$t(A)$ 的公式。

3.2 对已知半群的统一与推广 (Collection CNS)

将上述通用公式应用于特殊情形 $b_i = \frac{b^i-1}{b-1}$，得到了 Collection CNS 的结果。这统一并推广了以下已知结果：

• Repunit 数值半群：$S(b, n)$。
• Mersenne 数值半群：$b=2$ 时的特例。
• Thabit 数值半群：$T_b,1(n)$。
• Proth 数值半群：部分解决了开放问题。

3.3 解决 Proth 数值半群的开放问题 (Section 5)

Proth 半群 $P_m(n)$ 由 $\{m 2^{n+i} + 1 \mid i \in \mathbb{N}\}$ 生成，其中 $m$ 为奇数且 $m < 2^n$。

• 开放问题：Srivastava 和 Thakkar 之前仅解决了 $m=2^r+1$ 的情况，未给出一般 $m$ 的弗罗贝尼乌斯数公式。
• 本文进展：
  • 将 $P_m(n)$ 映射到 Collection CNS 框架（此时 $d=-1$）。
  • 根据 $m$ 的不同形式（即 $m = 2^r + q$），分析了 $a-1$ 的贪心表示结构。
  • 给出了 $F(P_m(n))$ 的显式公式（见 Theorem 5.4 和 5.5），并提供了 $q < 50$ 时的具体贪心表示表（Table 1）。
  • 给出了 $g(P_m(n))$ 的计算公式。

3.4 新发现的半群类 (Section 6)

利用 Corollary 2.16，作者还处理了一类新的数值半群，其生成元形式为 $A = (a, 2a+d, 4a+3d, \dots, 2^ka+(2^k-1)d)$，其中 $a = m(2^k-1) + 2^{k-1}-1$。这扩展了文献中关于 $G_{b,d}(a)$ 的研究，放宽了参数限制。

4. 意义与影响 (Significance)

1. 统一框架：本文最大的贡献在于建立了一个统一的代数框架（Collection GCNS），将 Repunit、Mersenne、Thabit、Proth 等多种看似不同的数值半群纳入同一理论体系下处理。
2. 负参数处理：创新性地允许参数 $d$ 为负整数，这直接使得 Proth 半群（其生成元形式隐含负差值）能够被纳入该框架，从而解决了长期存在的开放问题。
3. 算法与公式结合：通过利用“有序序列”和“贪心算法”的性质，将复杂的组合优化问题转化为可计算的代数公式，避免了复杂的递归或动态规划。
4. 解决开放问题：部分解决了 Proth 数值半群中关于任意奇数 $m$ 的弗罗贝尼乌斯数计算问题，为后续研究提供了具体的计算路径和公式。
5. 伪弗罗贝尼乌斯数：不仅给出了 $F(A)$ 和 $g(A)$，还推导了伪弗罗贝尼乌斯数集合 $PF(A)$和半群类型$t(A)$，丰富了该半群类的结构信息。

总结

该论文通过引入广义生成元序列和有序序列的贪心性质，成功推导出了一类包含多种经典数值半群的弗罗贝尼乌斯数和亏格的统一闭式公式。特别是通过允许 $d$ 为负数，成功攻克了 Proth 数值半群的一般化问题，展示了该方法在数论和组合数学中的强大应用潜力。