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

この論文「ON THE FROBENIUS NUMBER AND GENUS OF A COLLECTION OF SEMIGROUPS GENERALIZING REPUNIT NUMERICAL SEMIGROUPS（レピュニット数値半群を一般化する半群の集合におけるフロベニウス数と種数について）」は、数論的半群（Numerical Semigroups）の理論、特にフロベニウス数（Frobenius number）と種数（Genus）の計算問題に焦点を当てた研究です。

以下に、論文の技術的な要約を問題設定、手法、主要な貢献、結果、および意義に分けて日本語で詳述します。

1. 問題設定 (Problem)

数論的半群 $\langle A \rangle$ は、互いに素な正整数の列 $A = (a_1, a_2, \dots, a_n)$ によって生成される自然数の部分集合です。

• フロベニウス数 $F(A)$: $\langle A \rangle$ に属さない最大の整数。
• 種数 $g(A)$: $\langle A \rangle$ に属さない正整数の個数。

$n \ge 3$ の場合、$F(A)$ と $g(A)$ を一般的な閉じた式（closed formula）で表すことは Curtis の定理により不可能ですが、特定の数列構造を持つ半群については公式が求められています。
既存の研究では、レピュニット数（repunit numbers）、メルセンヌ数（Mersenne numbers）、タビット数（Thabit numbers）、プロス数（Proth numbers）などに関連する半群が個別に研究されてきました。しかし、これらを統一的に扱う一般的な枠組みや、負の整数を含むパラメータを許容する拡張系における公式は未解決でした。

この論文の目的は、以下の形式を持つ半群の集合に対するフロベニウス問題（$F(A)$ と $g(A)$ の決定）を解決することです：
$$A = (a, h_1 a + d b_1, h_2 a + d b_2, \dots, h_k a + d b_k)$$
ここで、$d$ は負の整数であってもよいという点が重要な革新です。

2. 手法とアプローチ (Methodology)

著者らは、以下の新しいアプローチを導入しました。

2.1. 一般化された半群の集合 (Collection GCNS)

半群の生成元を以下のように定義された「Collection GCNS」に一般化しました。

• $b_1 = 1, b_{i+1} = s_i b_i + 1$ （$s_i \ge s_{i-1}$）
• $h_i = u b_i + 1$ （$u \in \mathbb{P}$）
• $A = (a, h_1 a + d b_1, \dots, h_k a + d b_k)$

この構造は、レピュニット、タビット、プロス数などの半群を特殊ケースとして含みます。

2.2. 最小化問題と貪欲法 (Greedy Algorithm)

フロベニウス数を計算するために、以下の最小化問題 $O^H_B(M)$ を導入しました。
$$O^H_B(M) = \min \left\{ \sum_{i=1}^k h_i x_i \mid \sum_{i=1}^k b_i x_i = M, x_i \in \mathbb{N} \right\}$$
ここで、数列 $B = (1, b_2, \dots, b_k)$ が**「整然な数列（orderly sequence）」**であることが鍵となります。整然な数列とは、任意の $M$ に対して、貪欲法（greedy algorithm）が常に最適解を与える数列のことです。
著者らは、$b_{i+1} = s_i b_i + 1$ かつ $s_i \ge s_{i-1}$ という条件を満たす数列は整然であることを示し（Lemma 2.6）、これにより $O^H_B(M)$ が貪欲法で効率的に計算可能であることを証明しました。

2.3. Apéry 集合の構造解析

$A$ の Apéry 集合（$\langle A \rangle$ における $a$ に関する Apéry 集合）の要素 $N_r$ を、貪欲法による表現（greedy presentation）を用いて記述しました。

• $N_r = \min \{ \text{weight}(X) \cdot a + r \cdot d \mid X \text{ is greedy presentation of } r \}$
• 特定の条件下（$u a + d + k - 2 \ge \sum s_i$ など）において、$N_r$ が $r$ に関して単調増加または特定の順序関係を持つことを示し、最大値（フロベニウス数）を特定しました。

3. 主要な貢献と結果 (Key Contributions and Results)

3.1. 一般公式の導出 (Theorem 2.12, 2.13)

Collection GCNS に属する半群 $A$ に対して、以下の条件（$s_i < u+1$ など）の下で、フロベニウス数 $F(A)$ と種数 $g(A)$ の閉じた式を導出しました。

• フロベニウス数: $a-1$ の貪欲表現 $X(a-1) = (x_1, \dots, x_k)$ を用いて、
  $$F(A) = \sum_{i=1}^k x_i a + (a-1)(ua+d) - a$$
• 種数: 貪欲表現の要素和を用いた総和の式として導出。

3.2. 既存の半群への適用と一般化

この一般公式を適用することで、以下の既存の半群族に対する公式を簡潔に導出・再確認しました。

• レピュニット数値半群 (Repunit): $S(b, n)$ に対する公式（Corollary 3.2）。
• メルセンヌ数値半群 (Mersenne): $b=2$ の場合（Corollary 3.3）。
• タビット数値半群 (Thabit): 一般化されたタビット半群に対する公式（Theorem 4.1, 4.4）。
• プロス数値半群 (Proth): 未解決問題であった任意の奇数 $m$ に対するフロベニウス数の部分解決（Section 5）。

3.3. プロス数値半群の未解決問題への挑戦 (Open Problem 1.3)

Srivastava と Thakkar が提起した「任意の奇数 $m$ に対するプロス半群 $P_m(n)$ のフロベニウス数と種数の公式」に対して、部分的な解決を行いました。

• $m = 2r + q$ （$q$ は奇数）と置いた場合、$a-1$ の貪欲表現の最初の成分 $x_1$ の値（0 か 1, 2 か）に応じて、$F(P_m(n))$ の異なる公式を導出しました（Theorem 5.4, 5.5）。
• $q < 50$ の具体的なケースについて、貪欲表現のパターンを分類し、明示的な公式を提供する表（Table 1）を作成しました。

3.4. 負の整数 $d$ の扱い

$d$ が負の整数であっても、生成元の条件（$h_i a + d b_i > 1$）を満たせば、同様の手法が適用可能であることを示しました。これにより、Proth 半群（$d=-1$）など、従来の正の定数差を持つ数列では扱えなかったケースを統一的に扱えるようになりました。

4. 意義 (Significance)

1. 統一的な枠組みの提供: レピュニット、メルセンヌ、タビット、プロスなど、これまで個別に研究されていた多様な数値半群を、単一の一般化された構造（Collection GCNS）の中に位置づけ、統一的な手法で解析可能にしました。
2. 負のパラメータの許容: $d$ が負の整数である場合でも公式が成立することを示し、Proth 半群のような重要なクラスの解析を可能にしました。
3. アルゴリズム的効率性: 貪欲法が最適解を与える「整然な数列」の性質を利用することで、複雑な最小化問題を簡素化し、閉じた式（closed formula）の導出を可能にしました。
4. 未解決問題への進展: プロス半群のフロベニウス数に関する長年の未解決問題に対し、$m$ の特定の条件（$x_1 \neq 0$ など）の下で完全な公式を、それ以外の場合でも具体的なパターンに基づく部分解を提供しました。

結論

この論文は、数論的半群のフロベニウス問題において、生成元の構造を一般化し、貪欲法の性質を巧みに利用することで、広範な半群族に対する明示的な公式を導出することに成功しました。特に、負の定数項を含むケースやプロス半群への適用は、この分野における重要な進展であり、今後の研究の基礎となるものです。