The Frobenius Formula for $A=(a,ha+d,ha+b_2d,...,ha+b_kd)$

1. Problem Statement

The paper addresses the Frobenius Coin Problem (also known as the Change-Making Problem). Given a set of relatively prime positive integers $A = (a_1, a_2, \dots, a_n)$, the Frobenius number $g(A)$ is defined as the largest integer that cannot be expressed as a non-negative integer linear combination of the elements of $A$.

While closed-form solutions exist for $n=2$ (Sylvester's formula) and specific cases for $n=3$, no general closed-form formula exists for $n \geq 3$. The authors focus on a specific parametric family of sequences:
$$A(a) = (a, ha + d, ha + b_2d, \dots, ha + b_kd)$$
where:

• $a, h, d, b_i$ are positive integers.
• $\gcd(a, d) = 1$.
• $B = (1, b_2, \dots, b_k)$ is a fixed sequence of integers with $b_1=1$.
• The sequence is ordered such that $a < ha+d < \dots$.

The goal is to characterize $g(A(a))$ as a function of $a$ when $a$ is sufficiently large, extending previous work on square sequences ($B = (1, 2^2, \dots, k^2)$) to general sequences $B$.

2. Methodology

The authors employ a combinatorial approach utilizing generating functions and the properties of the Apéry set.

A. Apéry Set and Reduction

Using the theorem by Brauer and Shockley, the Frobenius number is related to the maximum element of the Apéry set of $A$ with respect to $a$:
$$g(A) = \max_{0 \leq r \leq a-1} \{N_{dr}\} - a$$
where $N_{dr} = \min \{ x \in \text{span}(A) \mid x \equiv dr \pmod a \}$.
The computation of $N_{dr}$ is reduced to a minimization problem involving the function $O_B(M)$, which represents the minimum number of elements from $B$ required to sum to $M$ (the change-making problem):
$$N_{dr} = \min_{m \in \mathbb{N}} \{ O_B(ma + r) \cdot ha + (ma + r)d \}$$

B. Generating Functions and the "Stable" Property

The authors define a generating function $f(t, q)$ where the coefficient of $t^k q^M$ corresponds to the existence of a representation of $M$ using $k$ elements of $B$. Specifically, $f(t, q) = \sum_{M \geq 0} t^{O_B(M)} q^M$.

The core theoretical contribution is the establishment of the "Stable" property for $O_B(M)$. They prove that for a fixed sequence $B$, there exists a threshold $M_0$ such that for all $M > M_0$:
$$O_B(M + b_k) = O_B(M) + 1$$
This implies that $O_B(M)$ behaves linearly (with slope $1/b_k$) modulo $b_k$ for large $M$. This stability allows the authors to compute $O_B(M)$ efficiently using polynomial-time algorithms relative to $b_k$.

C. Asymptotic Analysis

By analyzing the behavior of $N_{dr}$ for large $a$, the authors demonstrate that the maximum value in the Apéry set occurs within a specific window of residues near $a$. This leads to the conclusion that $g(A(a))$ is a "congruence class function" modulo $b_k$.

3. Key Contributions and Results

A. General Characterization (Theorem 3.3)

For a general sequence $B = (1, b_2, \dots, b_k)$, the authors prove that for sufficiently large $a$ (specifically $a \geq (u+c-1)b_k$, where $c$ and $u$ are constants derived from $B$), the Frobenius number is given by:
$$g(A(a)) = (w_j h - 1)a + r_j d + (ha + b_k d) \left( \left\lfloor \frac{a}{b_k} \right\rfloor - u - c + 1 \right)$$
where $a \equiv j \pmod{b_k}$.

• Structure: The formula is a quadratic polynomial in $a$ (due to the $\lfloor a/b_k \rfloor \cdot a$ term) with a leading coefficient of $h/b_k$.
• Periodicity: The coefficients $w_j$ and $r_j$ depend only on the residue class $j$ of $a$ modulo $b_k$.
• Algorithm: This provides a polynomial-time algorithm (in terms of $b_k$) to compute the exact Frobenius formula for any such sequence.

B. Orderly Sequences (Section 4)

The paper introduces the concept of Orderly Sequences, where the greedy algorithm for the change-making problem is always optimal ($O_B(M) = G_B(M)$).

• For orderly sequences, the bound for $a$ is significantly tighter: $a \geq (c-1)b_k$.
• The authors derive explicit formulas for several specific orderly sequences:
  • $B = (1, 2, b, b+1)$
  • $B = (1, 2, b, b+1, 2b)$
  • $B = (1, b, 2b-1)$
  • $B = (1, 2, \dots, k, K)$ (generalizing Selmer's results).

C. Extension to $b_1 > 1$ (Section 5)

The authors extend their methodology to cases where the first element of $B$ is not 1 (i.e., $b_1 > 1$). While the "Stable" property still holds, the calculation of the stability threshold becomes more complex, involving the Frobenius number of $B$ itself. They provide a corollary stating that the congruence class structure remains valid even in this generalized case.

D. Specific Examples

The paper provides explicit, piecewise-defined formulas for various $B$ sequences, demonstrating how the coefficients $w_j$ and $r_j$ change based on the residue of $a$. For instance, for $B=(1, 11, 14)$, the formula splits into 14 cases based on $a \pmod{14}$.

4. Significance

1. Unification: The work unifies previous isolated results (such as those for square sequences or arithmetic progressions) under a single framework of "congruence class functions."
2. Computational Efficiency: It establishes that computing the Frobenius number for this parametric family is feasible in polynomial time with respect to the largest element of the base sequence $B$, provided $a$ is large enough.
3. Structural Insight: It reveals that for large $a$, the Frobenius number is not a chaotic function but a structured, periodic quadratic polynomial. This deepens the understanding of the asymptotic behavior of numerical semigroups.
4. Generalization: By handling $b_1 > 1$ and various non-arithmetic sequences, the paper significantly broadens the scope of solvable Frobenius problems beyond the classical arithmetic progressions.

In summary, the paper provides a robust theoretical framework and practical algorithms for determining the Frobenius number of sequences of the form $(a, ha+dB)$, characterizing the solution as a periodic quadratic function of $a$ for sufficiently large $a$.