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

1. Problem Statement

The paper addresses the Frobenius Problem for specific families of numerical semigroups. Given a set of relatively prime positive integers $A = (a_1, a_2, \dots, a_n)$, the problem seeks to determine:

• The Frobenius Number $F(A)$: The largest integer that cannot be expressed as a non-negative integer linear combination of elements in $A$.
• The Genus $g(A)$: The count of positive integers that cannot be expressed as such a combination.
• Pseudo-Frobenius Numbers and Type: The set of maximal elements in the complement of the semigroup under the partial order induced by the semigroup, and the cardinality of this set (the type).

While formulas exist for $n=2$ (Sylvester's formula) and specific sequences (arithmetic progressions, geometric sequences), finding closed-form solutions for $n \geq 3$ is generally NP-hard. The authors focus on a generalized collection of semigroups that unifies and extends several known families, including Repunit, Mersenne, Thabit, and Proth numerical semigroups.

2. Methodology

The authors employ a unified approach based on the Apéry set and greedy algorithms for change-making problems.

A. Generalized Collection (GCNS)

The paper defines a general collection of numerical semigroups, denoted as Collection GCNS, generated by:
$$A = (a, h_1a + db_1, h_2a + db_2, \dots, h_ka + db_k)$$
where:

• $a, k \in \mathbb{P}$ (positive integers), $a, k \geq 2$.
• $d \in \mathbb{Z} \setminus \{0\}$ (can be positive or negative, a key innovation).
• $\gcd(a, d) = 1$.
• The sequences $B = (b_1, \dots, b_k)$ and $H = (h_1, \dots, h_k)$ follow recursive structures:
  • $b_1 = 1$, $b_{i+1} = s_i b_i + 1$ with $s_i \geq s_{i-1}$.
  • $h_i = u b_i + 1$ for some $u \in \mathbb{P}$.

B. The Apéry Set and Minimization

The core of the methodology relies on computing the Apéry set of $a$ in $\langle A \rangle$, denoted $\text{Ap}(\langle A \rangle, a)$. The elements of this set, $N_r$ (the smallest element in the semigroup congruent to $r \pmod a$), are derived from a minimization problem:
$$OH_B(M) = \min \left\{ \sum_{i=1}^k h_i x_i \;\middle|\; \sum_{i=1}^k b_i x_i = M, \; x_i \in \mathbb{N} \right\}$$
The authors prove that for their specific sequence $B$, the greedy algorithm yields the optimal solution for this minimization problem (i.e., the sequence $B$ is "orderly"). This allows for the explicit construction of the greedy presentation of any integer $M$.

C. Monotonicity Conditions

A critical technical contribution is establishing conditions under which the function $N_{dr}(m)$ (representing the Apéry set element for a specific residue class) is monotonically increasing with respect to the quotient $m$.

• They derive a sufficient condition: $ua + d + k - 2 \geq \sum_{i=1}^{k-1} s_i$.
• Under this condition, the maximum element in the Apéry set (which determines the Frobenius number) occurs at the largest residue $r = a-1$.

3. Key Contributions and Results

A. Unified Formulas for Collection GCNS

The paper provides closed-form formulas for $F(A)$ and $g(A)$ for the general Collection GCNS under specific constraints (Theorem 2.12 and 2.13):

• Frobenius Number:
  $$F(A) = \left( \sum_{i=1}^k x_i \right) a + (a-1)(ua + d) - a$$
  where $(x_1, \dots, x_k)$ is the greedy presentation of $a-1$.
• Genus:
  $$g(A) = \frac{1}{a} \sum_{r=1}^{a-1} \left( \sum_{i=1}^k x_i^{(r)} \right) + \frac{(a-1)(ua + d - 1)}{2}$$
  where $x_i^{(r)}$ are the coefficients of the greedy presentation of $r$.

B. Generalization of Repunit Semigroups (Collection CNS)

The authors specialize the GCNS results to Collection CNS, where $b_i = \frac{b^i-1}{b-1}$ and $h_i = b^i$. This covers:

• Repunit Semigroups: $S(b, n)$.
• Mersenne Semigroups: The case $b=2$.
• Thabit Semigroups: Specific parameter choices.
• Proth Semigroups: A partial solution to an open problem.

For these cases, they derive explicit polynomial formulas for $F(A)$ and $g(A)$ that depend on the parameters $a, b, d, n$.

C. Partial Solution to the Proth Numerical Semigroup Open Problem

The paper addresses Open Problem 1.3 from Srivastava and Thakkar regarding Proth numerical semigroups $P_m(n)$ generated by $\{m2^{n+i} + 1\}$.

• Challenge: Previous work only solved the case where $m = 2^r + 1$. The general case for arbitrary odd $m$ was open.
• Result: The authors provide a method to calculate $F(P_m(n))$ and $g(P_m(n))$ by analyzing the greedy presentation of $(2^r + q)2^n$ (where $m = 2^r + q$).
• Outcome: They provide explicit formulas for specific ranges of $q$ (odd numbers) and generate a table (Table 1) detailing the greedy presentations and corresponding theorems for $q < 50$. This constitutes a significant partial solution to the open problem.

D. Negative $d$ Innovation

A notable feature of the paper is the allowance of negative integers for $d$. This extends the applicability of the formulas to semigroups where the generators are not strictly increasing in the standard arithmetic sense, broadening the scope of the Frobenius problem solutions.

4. Significance

1. Unification: The paper successfully unifies the study of several distinct families of numerical semigroups (Repunit, Mersenne, Thabit, Proth) under a single theoretical framework (Collection GCNS).
2. Algorithmic Efficiency: By proving that the underlying sequences are "orderly," the authors reduce the complex Frobenius problem to a simple greedy algorithm, enabling the derivation of closed-form formulas rather than relying on computational enumeration.
3. Advancement on Open Problems: The work makes tangible progress on the Proth numerical semigroup problem, moving beyond the specific case of $m=2^r+1$ to a broader class of odd integers $m$.
4. Generalization: The methodology extends to cases with negative $d$, offering new insights into the structure of numerical semigroups that were previously difficult to analyze.

In summary, this paper provides a powerful, unified algebraic toolset for solving the Frobenius problem for a wide class of numerical semigroups, offering explicit formulas for invariants that were previously unknown or only computable for specific sub-cases.