The Frobenius Problem for the Proth Numbers

Pranjal Srivastava, Dhara ThakkarCALDAM 2024 · DOI

TL;DR

This paper introduces and solves the Frobenius problem for a new class of numerical semigroups called "Proth numerical semigroups." They provide a closed-form formula for the Frobenius number and demonstrate that these semigroups satisfy Wilf's conjecture, a significant open problem in the field.

What Problem Does This Paper Address?

The Frobenius problem, also known as the coin problem or the chicken McNugget theorem, asks for the largest integer that cannot be expressed as a non-negative integer linear combination of a given set of coprime positive integers. This problem has a rich history and connections to various fields, including number theory, graph theory, and computer science. While solutions exist for small numbers of integers (m=2, m=3), the general problem is NP-hard. Researchers have studied this problem for various special classes of integers, such as those forming arithmetic or geometric sequences. This paper extends this line of inquiry by introducing and analyzing the Frobenius problem for "Proth numerical semigroups," which are generated by sets of numbers related to Proth numbers (numbers of the form $k \cdot 2^n + 1$).

Methods

The authors employ standard techniques from numerical semigroup theory. They begin by defining the Proth numerical semigroup $P_k(n)$ and its generators. A key step is determining the minimal system of generators and the embedding dimension of these semigroups, which they establish as $n+r+1$ for a specific range of $k$. They then delve into the Apéry set, a crucial tool for understanding numerical semigroups. By explicitly describing the Apéry set of the Proth numerical semigroup, they are able to derive a closed-form formula for the Frobenius number. Finally, they leverage these results to prove that Proth numerical semigroups satisfy Wilf's conjecture.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Introduction of Proth Numerical Semigroups: The paper defines a novel class of numerical semigroups based on Proth numbers, opening up new avenues for research in this area.
  • Explicit Formula for Frobenius Number: A significant contribution is the derivation of a concrete formula for the Frobenius number of these semigroups, which is a challenging task for general cases.
  • Connection to Wilf's Conjecture: The paper demonstrates that Proth numerical semigroups satisfy Wilf's conjecture. This is noteworthy because Wilf's conjecture is an open problem, and proving it for specific classes of semigroups provides valuable insights.
  • Apéry Set as a Powerful Tool: The paper effectively utilizes the Apéry set to characterize the structure of Proth numerical semigroups and derive key results, highlighting its utility in solving Frobenius-related problems.

Key Results

  • The embedding dimension of the Proth numerical semigroup $P_k(n)$ is determined to be $n+r+1$, where $2^r < k < 2^{r+1}$.
  • A closed-form formula for the Frobenius number of the Proth numerical semigroup $P_{2^r+1}(n)$ is derived: $F(P_{2^r+1}(n)) = 2s_1 + s_n + s_{n+r} - s_0$, where $s_i = k \cdot 2^n + i + 1$.
  • The paper proves that Proth numerical semigroups satisfy Wilf's conjecture, meaning $F(S) + 1 \le e(S)v(S)$ for these semigroups.
  • The set of pseudo-Frobenius numbers and the type of the Proth numerical semigroup are characterized.

Limitations and Future Work

The paper focuses on Proth numerical semigroups where $k$ is an odd positive number and $k < 2^n$. The authors explicitly state that an open question is whether a formula can be found for the Frobenius number and other invariants of the Proth numerical semigroup $P_k(n)$ for arbitrary $k$. This suggests that the current results are specific to a particular range of $k$ and that a more general solution remains an area for future research.

Summary updated

BibTeX
@inproceedings{srivastava2024frobenius,
  author = {Pranjal Srivastava and Dhara Thakkar},
  title = {{The Frobenius Problem for the Proth Numbers}},
  booktitle = {CALDAM},
  year = {2024},
  doi = {10.1007/978-3-031-52213-0\_12},
}
Figure