Characterizing Frobenius Semigroups by Filtration

Inga Johnson, Sean Powers, Colin Starr, Charles Trevelyan and Craig Webster Department of Mathematics Willamette University Salem, OR 97301 USA

                    ijohnson@willamette.edu
                     cstarr@willamette.edu

Abstract

For a given base a, and for all integers k, we consider the sets

G_{a}(k) = {a^{k}, a^{k} + a^{k−1}, …, a^{k} + a^{k−1} + ⋯ + a^{1} + a^{0}},

and for each G_{a}(k) the corresponding “Frobenius set”

F_{a}(k) = {n ∈ ℕ | n is not a sum of elements of G_{a}(k)}.

The sets F_{a}(k) are nested and their union is ℕ. Given an integer n, we find the smallest k such that n ∈ F_{a}(k).

1 Introduction and statement of result

The Frobenius problem for a given set A = {a_{1}, a_{2}, …, a_{n}} of positive relatively prime integers is the problem of finding the largest integer that cannot be expressed as a sum of (possibly repeated) elements of A. This largest such number is the Frobenius number of the set A, denoted by g(A).

Finding the Frobenius number for sets A has been a widely studied problem since the early 1900’s, when Frobenius was reported to have posed the question frequently in lectures. Sylvester [12] is widely credited with showing that for relatively prime integers a and b, g({a, b}) = ab − (a + b), but he actually addressed a slightly different problem. In 1990, Curtis showed that for an arbitrary relatively prime set A the Frobenius number cannot be expressed in terms of a finite set of polynomials [2], although Greenberg and later Davison found algorithms that are reasonably quick in practice in the n = 3 case [3, 4]. In 1996, Ramírez-Alfonsín proved that the Frobenius problem for sets A of three or more elements is NP-hard [9]. However, R. Kannan has shown that for every fixed n, there is a method that solves the Frobenius problem in polynomial time (although the degree of the polynomial grows rapidly with n) [6].

In this paper we study a family of sets G_{a}(k), defined below, and for each such set we study not only the Frobenius number but the set of all numbers which are not sums of elements of G_{a}(k). More precisely, let the base a ∈ ℕ be fixed. For each k ∈ ℕ, we define

G_{a}(k) = {a^{k}, a^{k} + a^{k−1}, a^{k} + a^{k−1} + a^{k−2}, …, a^{k} + a^{k−1} + ⋯ + a^{1} + a^{0}}.

Note that the rightmost (and largest) element listed in the set above is a geometric series equal to \frac{a^{k+1}−1}{a−1}, and henceforth we will write it as such without further comment. For the sets G_{a}(k) we study the Frobenius sets

F_{a}(k) = {n ∈ ℕ | n is not a sum of the elements of G_{a}(k)}.

A straightforward calculation shows that the sets F_{a}(k) are nested (i.e., F_{a}(k − 1) ⊆ F_{a}(k)), and the union of the sets F_{a}(k) over all k is ℕ. This paper investigates the following question: for arbitrary n ∈ ℕ, what is the least integer k such that n ∈ F_{a}(k)? We denote this least positive integer as f_{a}(n) := min{k | n ∈ F_{a}(k)} and call it the Frobenius level of n with respect to the sets G_{a}(k).

Example 1. With a = 2 and k ≤ 3, we have

G_{2}(1) = {2, 3}  F_{2}(1) = {1}
G_{2}(2) = {4, 6, 7}  F_{2}(2) = {1, 2, 3, 5, 9}
G_{2}(3) = {8, 12, 14, 15}  F_{2}(3) = {1, 2, 3, 4, 5, 6, 7, 9, 10,
11, 13, 17, 19, 25, 33}

The sets G_{2}(k), for k = 1, 2, … form the sequence A023758 of Sloane’s Encyclopedia.

We see that f_{2}(9) = 2 and f_{2}(19) = 3; however, there is not enough information given in Example 1 to determine f_{2}(30). I. Johnson and J. L. Merzel [5] determined the Frobenius level of an integer n with respect to the sets G_{2}(k) while studying factorizations in the Steenrod algebra at the prime 2. Their paper serves as motivation for studying these more general sets G_{a}(k) for arbitrary a and the solution presented in this paper is a generalization of their results. It is believed that the results presented here will have implications in the Steenrod algebra for odd primes analogous to those found at the prime 2 by Johnson and Merzel. For a discussion of the Steenrod algebra and its role in the field of algebraic topology, see [7, 10, 11, 13].

Our solution of this Frobenius level problem relies on careful study of base a arithmetic, and the following definitions and notations are required to state our result. For a positive integer n, let [n] denote a base a expansion of n. This means if w_{i} ∈ {0, 1, …, a − 1} for all i and

n = w_{k}a^{k} + w_{k−1}a^{k−1} + ⋯ + w_{2}a^{2} + w_{1}a^{1} + w_{0}a^{0},

then [n] = w_{k}w_{k−1} … w_{1}w_{0}. We note that this expansion is unique up to leading zeros. For example, in base 3 (ternary) we may view [41] as 1112 or 0001112. We call an ordered string of digits b_{k}b_{k−1}b_{k−2} … b_{2}b_{1}b_{0} with each digit b_{i} in {0, 1, …, a − 1} a base a string, and given integers i, j such that k ≥ i + j ≥ i ≥ 0 the base a string b_{i+j} … b_{i+1}b_{i} is called a substring of b_{k}b_{k−1}b_{k−2} … b_{2}b_{1}b_{0}. We will use roman characters to denote integers and Greek letters to denote strings and substrings.

For a given base-a string β, let |β| denote the integer with expansion β in base a. The length of the string β will be denoted by len(β). Of course, the length is only defined for a given base a string. Expressions such as len([n]) are not well-defined and will not be used.

Let β = b_{i+j}b_{i+j−1} … b_{i} be a substring of b_{k} … b_{2}b_{1}b_{0}. Then β is a non-increasing substring if and only if b_{m} ≤ b_{m−1} for i < m ≤ i+j. That is, we will read from right to left to determine whether a string is increasing, and of course constant strings are non-increasing. (For our purposes, “constant string” refers to a string of length at least two in which all digits are equal.) For an arbitrary base-a string b_{k} … b_{2}b_{1}b_{0} we say that a drop occurs at b_{m} provided b_{m+1} < b_{m}. A non-increasing substring b_{i+j} … b_{i+1}b_{i} of b_{k} … b_{2}b_{1}b_{0} is said to follow a drop provided i ≠ 0 and a drop occurs at b_{i−1}. Given a base a string β = b_{k} … b_{m} … b_{1}b_{0}, the digit b_{m} is said to contribute to β if b_{m} is itself a digit in a non-increasing substring of β that follows a drop. In examples and diagrams we will underline contributing digits. We remark that a digit b_{m} contributes to a string β if and only if (1) a drop occurs at b_{m−1}, or (2) b_{m−1} contributes and b_{m} ≤ b_{m−1}. Thus whether or not a digit contributes is completely determined by the behavior of the digit to its immediate right.

Example 2. Here is an example of a string, γ = 201120100121, with drops indicated by arrows and contributing digits underlined.

\xymatrix{γ : & 2 & \underline{0} & \underline{1} & \underline{1} & 2 \ar[l]_{drop} & \underline{0} & 1 \ar[l]_{drop} & \underline{0} & \underline{0} & \underline{1} & 2 \ar[l]_{drop} & 1}

Note that we have not indicated drops within contributing substrings since the important characteristic is whether a digit contributes.

Definition 3. For a given base-a string β, define z(β) to be the number of digits in β that contribute to β.

For instance, in ternary, z(\underline{01}2\underline{0}21000) = 3 and z(1\underline{01}2\underline{11}2) = 4. The contributing digits have been underlined.

The function z exhibits a “quasi-linear” property in the sense of the following lemma.

Lemma 4. Let β be a base-a string, β = b_{k} ⋯ b_{j} ⋯ b_{2}b_{1}b_{0}, where b_{j} is not a digit in a constant substring that follows a drop. Then

z(β) = z(b_{k} ⋯ b_{j}) + z(b_{j} ⋯ b_{1}b_{0}).

Proof. If j = k or j = 0 the result is clear. Suppose k > j > 0. The assumption on b_{j} implies that either b_{j} does not contribute to β, or it does contribute and b_{j} ≠ b_{j+1} and b_{j} ≠ b_{j−1}. The result is clear in the case that b_{j} does not contribute to β, so suppose b_{j} does contribute to β. Then we have the following two cases:

(i) b_{j+1} < b_{j} < b_{j−1} (ii) b_{j+1} > b_{j} and b_{j} < b_{j−1}.

It suffices to prove that each digit of β that contributes to β also contributes to the sum z(b_{k} ⋯ b_{j}) + z(b_{j} ⋯ b_{0}) once and only once. In case (i), b_{j} contributes to b_{j}b_{j−1} … b_{1}b_{0}; however, it cannot contribute to b_{k} ⋯ b_{j+1}b_{j} as it cannot follow a drop. Thus the digit b_{j} contributes once to the sum. The digits in the substring b_{j}b_{j−1} … b_{1} are contributing if and only if they contribute to β. Since b_{j+1} contributes to β, the digits of the substring b_{k} ⋯ b_{j+1} contribute to b_{k} ⋯ b_{j+1}b_{j} if and only if they contribute to β. The proof for case (ii) is analogous except that b_{j+1} does not contribute to β and does not contribute to b_{k} ⋯ b_{j+1}b_{j}, but all contributions from the left of b_{j+1} are the same in both strings.

Given strings α and β, their concatenation will be denoted by αβ. Lastly, we define the “star” notation.

Definition 5. For nonempty strings α and β, we define the relation ∗ by

α ∗ β ⇔ |α| < z(β)

Example 6. Consider the ternary string 1211111201. If α = 12 and β = 11111201, then z(β) = 6 and |α| = 5. In this case, 12 ∗ 11111201 holds; note that len(β) = 8 = 7 + 1. However, 121 ∗ 1111201 does not hold as 16 ≮ 5.

The following theorem is one of the main results of this paper. In Section 3 we give an algorithmic description of this theorem and briefly discuss its complexity.

Theorem 7. Let n ∈ ℕ. Then the Frobenius level of n, f_{a}(n), is the smallest k for which we can write n = |αβ| with len(β) = k + 1 and α ∗ β.

The previous example shows that the Frobenius level of n = 36091 = |1211111201| is f_{3}(36091) = 7.

Theorem 7 reduces to the results of Johnson and Merzel when a = 2. In the Johnson and Merzel paper z(β) is defined as the number of non-trailing zeros in β and our definition of z(β) reduces to the Johnson-Merzel definition in the case a = 2.

2 Proof of Theorem 1

The proof of Theorem 7 is organized as follows: Lemma 8 gives a particularly useful way to represent integers that are not in F_{a}(k). Lemmas 9 and 10 show that the sets F_{a}(k) can be described recursively. Lemmas 13 and 14 set up technical details to assist in the proof of Theorem 15 by induction. Theorem 7 is then a corollary of Theorem 15. Along the way, Theorem 11 gives an explicit formula for the Frobenius number of G_{a}(k) which corresponds to the well-known results of Nijenhuis and Wilf [8].

Lemma 8. If n ∉ F_{a}(k), then there exist c_{1} ∈ ℤ_{≥0}, c_{2}, …, c_{k+1} ∈ {0, …, a − 1} such that n = c_{1}a^{k} + c_{2}(a^{k} + a^{k−1}) + ⋯ + c_{k+1}(a^{k} + a^{k−1} + ⋯ + a + 1).

Proof. Suppose n ∉ F_{a}(k). Then there exist coefficients w_{i}, 1 ≤ i ≤ k + 1, such that

n = w_{1}a^{k} + w_{2}(a^{k} + a^{k−1}) + ⋯ + w_{k+1}(a^{k} + a^{k−1} + ⋯ + a^{1} + a^{0}).

If the coefficients w_{i} satisfy the conditions of the lemma then we are done; otherwise, let j be the largest subscript for which w_{j} ≥ a. Using the division algorithm, write w_{j} = aq + c_{j}, where 0 ≤ c_{j} < a. Substitution gives

w_{j}(a^{k} + a^{k−1} + ⋯ + a^{k−j+1}) = (aq + c_{j})(a^{k} + a^{k−1} + ⋯ + a^{k−j+1})
= aq(a^{k} + a^{k−1} + ⋯ + a^{k−j+1})
+c_{j}(a^{k} + ⋯ + a^{k−j+1})
= aq(a^{k}) + q(a^{k} + a^{k−1} + ⋯ + a^{k−j+2})
+c_{j}(a^{k} + ⋯ + a^{k−j+1}).

Next, define c_{m} := w_{m} for all j < m ≤ k + 1. Thus n can be written as

n = (w_{1} + aq)a^{k} + w_{2}(a^{k} + a^{k−1}) + ⋯ + w_{j−2}(a^{k} + a^{k−1} + ⋯ + a^{k−j+3})
+(w_{j−1} + q)(a^{k} + a^{k−1} + ⋯ + a^{k−j+2}) + c_{j}(a^{k} + a^{k−1} + ⋯ + a^{k−j+1})
+c_{j+1}(a^{k} + a^{k−1} + ⋯ + a^{k−j}) + ⋯ + c_{k+1}(a^{k} + a^{k−1} + ⋯ + a^{1} + a^{0}).

Now c_{j}, c_{j+1}, ..., c_{k+1} ∈ {0, 1, 2, …, a − 1}, and repeating the procedure above at most j − 2 times gives the coefficients c_{i} in the desired range for i = 2, 3, ..., k + 1.

Lemma 9. Let n ∈ ℕ, and let q and r be the unique integers such that n = aq + r, where 0 ≤ r < a. Let R = r\frac{a^{k+1}−1}{a−1}. Then n ∈ F_{a}(k) if and only if n < R or \frac{n−R}{a} ∈ F_{a}(k − 1).

Proof. We prove that n ∉ F_{a}(k) if and only if n ≥ R and \frac{n − R}{a} ∉ F_{a}(k − 1).

Suppose n ≥ R and \frac{n−R}{a} ∉ F_{a}(k − 1). Then \frac{n − R}{a} is a nonnegative-integral combination of the elements of G_{a}(k − 1); thus

\frac{n − R}{a} = c_{1}a^{k−1} + c_{2}(a^{k−1} + a^{k−2}) + ⋯ + c_{k}(a^{k−1} + a^{k−2} + ⋯ + 1)

for some c_{1}, …, c_{k} ∈ ℤ_{≥0}. Therefore

n = c_{1}a^{k} + c_{2}(a^{k} + a^{k−1}) + ⋯ + c_{k}(a^{k} + a^{k−1} + ⋯ + a) + R,

where c_{1}, c_{2}, ..., c_{k} ∈ ℤ_{≥0}. Because R = r (\frac{a^{k+1}−1}{a−1}) = r (a^{k} + a^{k−1} + ⋯ + a + 1), n ∉ F_{a}(k).

Conversely, suppose n ∉ F_{a}(k). By Lemma 8, there exist c_{1} ∈ ℤ_{≥0} and c_{2}, c_{3}, …, c_{k+1} ∈ {0, …, a − 1} such that

\begin{aligned}n & = & c_{1}a^{k} + c_{2}(a^{k} + a^{k−1}) + ⋯ + c_{k+1}(a^{k} + ⋯ + a + 1) \\ & = & a(c_{1}a^{k−1} + c_{2}(a^{k} + a^{k−1}) + ⋯ + c_{k+1}(a^{k−1} + ⋯ + 1)) + c_{k+1}. \end{aligned}

Since r is unique and 0 ≤ c_{k+1} < a, we see from the equation above that c_{k+1} = r. Therefore,

\frac{n − R}{a} = c_{1}a^{k−1} + c_{2}(a^{k−1} + a^{k−2}) + ⋯ + c_{k}(a^{k−1} + a^{k−2} + ⋯ + 1).

Thus, \frac{n−R}{a} ∉ S_{a}(k − 1). Since n − R ≥ 0, n ≥ R.

Lemma 10. Let n ≢ 0 (mod a). Then n ∈ F_{a}(k) if and only if n − \frac{a^{k+1}−1}{a−1} ∈ F_{a}(k).

Proof. Let n − \frac{a^{k+1}−1}{a−1} ∉ F_{a}(k). Then n ∉ F_{a}(k) follows immediately.

Suppose n ∉ F_{a}(k). Write

n = c_{1}a^{k} + c_{2}(a^{k} + a^{k−1}) + ⋯ + c_{k+1}(a^{k} + a^{k−1} + ⋯ + a + 1),

where c_{1} ∈ ℤ^{+} and c_{2}, c_{3}, …, c_{k+1} ∈ {0, 1, … a − 1}. Note that c_{k+1} ≥ 1 since n ≢ 0 (mod a). Then

n − \frac{a^{k+1} − 1}{a − 1} = c_{1}a^{k} + c_{2}(a^{k} + a^{k−1}) + ⋯ + (c_{k+1} − 1)\frac{a^{k+1} − 1}{a − 1},

which implies that n − \frac{a^{k+1}−1}{a−1} ∉ F_{a}(k).

We notice that the Frobenius number for the sets G_{a}(k) is the largest element of F_{a}(k), and since the sets F_{a}(k) can be described recursively we present an easy to prove formula for g(G_{a}(k)) in Theorem 11. We note that the sets G_{a}(k) are part of a well studied class known as sequentially redundant sets. Recall that a sequentially redundant set of positive integers is a set A = {a_{1}, a_{2}, …, a_{n}} such that for j = 2, 3, …, n, there exist non-negative integers t_{ij} such that

\frac{a_{j}}{d_{j}} = \frac{1}{d_{j−1}} ∑_{i=1}^{j−1} t_{ij}a_{i},

where d_{i} = gcd{a_{1}, a_{2}, …, a_{i}} for each 1 ≤ i ≤ n. The Frobenius number of a sequentially redundant set is well-known [8]; thus the result below is not new.

Theorem 11. The Frobenius number of the set G_{a}(k) is

g(\{a^{k}, a^{k} + a^{k−1}, …, a^{k} + a^{k−1} + ⋯ + a^{0}\}) = \frac{1 − a^{k+1}k − a^{k+1} + a^{k+2}k}{a − 1}

Proof. We proceed by induction on k. G_{a}(1) = {a, a + 1}, so using Sylvester’s formula we have g({a, a + 1}) = a(a + 1) − (2a + 1) = (a − 1)(a + 1) − a as desired. Next we assume the formula holds for G_{a}(k − 1). Then the largest number in S_{a}(k − 1) is

g(G_{a}(k − 1)) = (a − 1) (∑_{i=1}^{k−1}(a^{k−1} + a^{k−2} + ⋯ + a^{k−1−i})) − a^{k−1}.

Lemma 9 implies that if w is the largest element of F_{a}(k − 1), then for maximal R aw + R is the largest element of F_{a}(k). The largest possible R occurs for r = a − 1; thus R = a^{k+1} − 1.

Therefore

g(G_{a}(k)) = a ((a − 1) (∑_{i=1}^{k−1}(a^{k−1} + a^{k−2} + ⋯ + a^{k−1−i})) − a^{k−1})
+a^{k+1} − 1
= (a − 1) (∑_{i=1}^{k}(a^{k} + a^{k−1} + ⋯ + a^{k−i})) − a^{k}

= \frac{1 − a^{k+1}k − a^{k+1} + a^{k+2}k}{a − 1} .

The next two lemmas describe the behavior of the function z when a base-a string of ones is subtracted from a base a string with a specific form. We precede these lemmas with the following motivating example.

Example 12. Let a = 3 and consider the ternary string

γ = 21101000100121.

Let δ = 111 ⋯ 1 be a constant ternary string of ones with len(δ) = 14. We first calculate γ − δ and add a leading zero so len(γ − δ) remains 14; γ − δ = 02212111212010. Next we compare z(γ) and z(γ − δ). Contributing digits are underlined below.

[figure: γ :; 2; 1; 1; \underline{0}; 1; \underline{0}; \underline{0}; \underline{0}; 1; \underline{0}; \underline{0}; \underline{1}; 2; 1; γ − δ :; \underline{0}; 2; 2; \underline{1}; 2; \underline{1}; \underline{1}; \underline{1}; 2; \underline{1}; 2; \underline{0}; 1; 0]

Thus z(γ) = 7 = z(γ − δ). The key observation to make in this example is that all contributing digits in γ are paired with contributing digits in the same position in γ − δ except for the rightmost contributing zero in γ, which is paired with the leading contributing digit in γ − δ.

Lemma 13. Suppose a base-a string γ = h_{n}h_{n−1} ⋯ h_{l+1}h_{l}h_{l−1} ⋯ h_{1}h_{0} satisfies the following conditions:

(i) for 0 ≤ i ≤ l − 1, h_{i} > 0,

(ii) h_{l} = 0 [note: it is possible that l = 1],

(iii) for l + 1 ≤ i ≤ n − 1, h_{i} = 0 or 1 (possibly empty), and

(iv) h_{n} > 1.

Suppose δ is a base-a string of 1’s with length n + 1. Then z(γ − δ) = z(γ), where γ − δ has the same length as γ (by appending a leading zero if necessary).

Proof. Firstly, note that a > 2 is forced by the given conditions. Now, to compute γ − δ, we “borrow” from each digit to the left of h_{l}. The result is

γ − δ = [h_{n} − 2][h_{n−1} + a − 2] ⋯ [h_{l+1} + a − 2][h_{l} + a − 1][h_{l−1} − 1] ⋯ [h_{1} − 1][h_{0} − 1].

Since 2 ≤ h_{n} ≤ a−1, h_{n}−2 < a−2. Also, h_{n−1} is either a 0 or 1 in γ. Thus, the n−1 digit in γ − δ is a − 2 more than the n − 1 digit of γ: it increases by a due to borrowing from h_{n}, loses one because the n−2 digit borrows from it, and loses one more from subtracting δ. The value of the n − 1 digit of γ − δ is thus either a − 2 or a − 1. Therefore, h_{n} − 2 < h_{n−1} + a − 2, and the n digit will be a drop in γ − δ. However, in γ, h_{n} > h_{n−1}, so there is a drop in γ − δ that is not in γ.

In γ − δ, the l + 1 through n − 1 digits are each a − 2 more than h_{i} (since γ − δ requires borrowing throughout these digits), and therefore this section yields the same digit-by-digit contribution to γ − δ as to γ.

Note that h_{l} = 0, so the l-digit of γ−δ is a−1. (Since h_{l} is the first zero appearing in γ, no borrowing is necessary to the right of h_{l}.) If h_{l+1} = 0 (and is hence part of a non-increasing sequence to the left of a drop) in γ, then the l + 1 digit in γ − δ is a − 2 and is therefore a drop and counted as it was for z(γ). If h_{l+1} = 1, then the l + 1 digit in γ − δ has value a − 1 and thus is not part of a non-increasing sequence following a drop; it is again counted as it was for z(γ). Thus, in either case, the contribution to γ − δ from the l + 1 digit is the same as it is in γ.

Since h_{l−1} − 1 is less than a − 1 and h_{l} + a − 1 = a − 1, the l digit in γ − δ is not a drop. However, the digit at position l in γ is a drop since it is the first zero appearing in γ. Thus, γ − δ loses a drop that γ had.

For l − 1 > i ≥ 1, each digit h_{i} > 0, and therefore no borrowing is required for corresponding digits in γ − δ. Thus these digits make the same contribution to γ − δ as to γ.

The net result of these considerations is that the contribution in γ that occurs at h_{l} is moved to the leading digit in γ − δ, but all other contributions remain the same. Therefore z(γ − δ) = z(γ), as desired.

Before continuing with the next lemma, we pause to recall the relation ∗: if α and β are nonempty base-a strings, then α ∗ β ⟺ |α| < z(β).

Lemma 14. Let β = b_{k}b_{k−1} ⋯ b_{2}b_{1}b_{0} and α be strings in base a. Let δ = 1 ⋯ 1 be a string of k + 1 ones in base a.

Suppose

(a) β ≢ 0 (mod a),

(b) z(β) > 0, and

(c) |α| > 0.

Then

(i) for |β| > |δ|, α ∗ β ⇔ α ∗ (β − δ), and

(ii) for |β| < |δ|, α ∗ β ⇔ [|α| − 1] ∗ ([1]β − δ), where 1 and β are concatenated to create [1]β > δ.

Proof. Case (i): Suppose |β| > |δ|. Then either β is zero-free or it contains a zero. If β is zero-free, then β − δ requires no borrowing, so z(β) = z(β − δ) and α does not change. (Note: this also implies that in Case (i), the hypotheses |α| > 0 is unnecessary.) Thus α ∗ β ⟺ α ∗ (β − δ).

Now suppose that β contains at least one zero. Write β = b_{k}b_{k−1} ⋯ b_{1}b_{0}. Inductively define substrings β_{i}, i = 1, 2, … m, for m < k + 1, as follows:

β_{1} = b_{j_{1}} ⋯ b_{l_{1}} ⋯ b_{1}b_{0},

where l_{1} is the smallest subscript in β such that b_{l_{1}} = 0, and j_{1} > l_{1} is the smallest subscript in β such that b_{j_{1}} > 1. Note that this subscript exists since |β| > |δ|. If b_{w} = 0 for some w > j_{1}, then define β_{2} = b_{j_{2}} ⋯ b_{l_{2}} ⋯ b_{j_{1}}, where l_{2} > j_{1} is the smallest subscript such that b_{l_{2}} = 0, and j_{2} > l_{2} is the smallest subscript such that b_{j_{2}} > 1. A diagram of the basic structure of each β_{i} is included below.

\overbrace{\underbrace{b_{j_{i}}}_{>1} \underbrace{…}_{≤1} \underbrace{b_{l_{i}}}_{=0} \underbrace{… b_{j_{i−1}}}_{≠0}}^{β_{i}}

Create successively β_{1}, β_{2}, β_{3}, …, β_{m} as above, where either b_{k} appears in β_{m} or b_{w} > 0 for all w > j_{m}. In the former case, define β_{m+1} to be the empty string; in the latter case, define β_{m+1} = b_{k}b_{k−1} ⋯ b_{j_{m}}. The following diagram gives a picture of β and the β_{i} substrings.

[figure: β :; b_{k}; β_{m+1}; …; b_{j_{m}}; β_{m}; …; \underline{b_{l_{m}}}; …; b_{j_{m−1}}; …; b_{j_{1}}; β_{1}; …; \underline{b_{l_{1}}}; …; b_{0}; β − δ :; \underline{b_{j_{m}} − 2}; \underline{b_{j_{1}} − 2}]

The β_{i} satisfy the hypotheses of Lemma 13 and of quasi-linearity. Thus each b_{l_{i}} is contributing in β and is paired with the contributing digit b_{j_{i}} − 2 in β − δ.

Let δ_{i} denote a string of ones of length len(β_{i}) for i = 1, …, m + 1. We compute:

z(β) = ∑_{i=1}^{m+1} z(β_{i}) by quasi-linearity

= ∑_{i=1}^{m+1} z(β_{i} − δ_{i}) by Lemma 13.

It remains to show that ∑_{i=1}^{m+1} z(β_{i} − δ_{i}) = z(β − δ). Notice that quasi-linearity does not apply to the strings β_{i} − δ_{i} as the leading digit of β_{i} − δ_{i} is one less than the last digit of β_{i+1} − δ_{i+1}. However, we can piece these strings together to form β − δ by deleting the last digit of each β_{i} − δ_{i} for i = 2, …, m + 1 and concatenating appropriately. Recall that these last digits are not contributing digits to β_{i} − δ_{i} so none of them are underlined. In addition, every digit in each β_{i} − δ_{i} has the same right neighbor after forming β − δ (by deletion and concatenation) except b_{j_{i−1}+1} − 1, so we must only show that b_{j_{i−1}+1} − 1, for i = 2, …, m + 1, contributes to β_{i} − δ_{i} if and only if it contributes to β − δ. (That is, we must show that the deletion-concatenation procedure does not disturb any underlining.)

Now

b_{j_{i−1}+1} − 1 contributes to β_{i} − δ_{i} ⟺ b_{j_{i−1}+1} − 1 < b_{j_{i−1}} − 1
⟺ b_{j_{i−1}+1} − 1 ≤ b_{j_{i−1}} − 2.

We know from the proof of Lemma 13 that b_{j_{i}−1} − 2 contributes to β_{i−1} − δ_{i−1}, and hence to β −δ. This implies that b_{j_{i−1}+1} −1 ≤ b_{j_{i−1}} −2 if and only if b_{j_{i−1}+1} −1 contributes to β −δ.

Thus each contribution to β_{i} − δ_{i} is counted once and only once in β − δ, so ∑_{i=1}^{m+1} z(β_{i} − δ_{i}) = z(β − δ).

Case (ii): Now consider |β| < |δ|. If β has no digits larger than 1, then form β̃ as below (with t = −1). If β has a digit larger than 1, let t be the largest integer such that b_{t} > 1. Apply case (i) to β′ = b_{t} … b_{1}b_{0} and δ′ = 1 … 1, a string of t+1 ones. Then z(β′) = z(β′−δ′).

Consider β̃ = [1]b_{k}b_{k−1} … b_{t+1} = [a + b_{k}]b_{k−1} … b_{t+1} where b_{t+1}, …, b_{k} ∈ {0, 1}. Let s ≥ t + 1 be the least integer such that b_{s} = 0. Note that such a b_{s} exists since |β| < |δ|. Let δ̃ = 1 … 1 be a string of k − t ones. For i from t + 1 through k, the digits c_{i} of β̃ − δ̃ are as follows:

c_{i} = 0,  if t + 1 ≤ i < s;
c_{s} = a − 1;
c_{i} = a − 1, if i > s and b_{i} = 1;
c_{i} = a − 2, if i > s and b_{i} = 0.

If t ≥ 0, then the digits labelled t + 1 through s − 1 of β̃ are all 1, and the corresponding digits of β̃ − δ̃ are all 0. Since the t + 1 digit is a drop in either case, both strings contribute the same. If t = −1, then digits t + 1 = 0 through s − 1 of β̃ are all 1 (since β ≢ 0 (mod a)) and the corresponding digits of β̃ − δ̃ are all 0, and none of these contribute. Note that the string of digits from t + 1 to s − 1 could be empty.

Now b_{s} = 0 contributes to β̃ since it is a drop from the preceding digit, but the sth digit of β̃ − δ̃ does not contribute since it equals a − 1. Thus, the contributions in β up through the sth digit are z(β′) + (s − t − 1) + 1, and the contributions in [1]β − δ up through the sth digit are z(β′) + (s − t − 1).

From the table above, we see that the s + 1 through k digits contribute in β if and only if they contribute in [1]β − δ since 0 ↔ a − 2 and 1 ↔ a − 1. For b_{s} becomes a − 1 in β̃ − δ̃. Therefore, if b_{s+1} = 0 (and therefore contributes to β), then the s + 1 digit of β̃ − δ̃ is a − 2, which contributes to β̃ − δ̃. If b_{s+1} = 1 (and therefore does not contribute to β), then the s + 1 digit of β̃− δ̃ is a − 1, which does not contribute to β̃− δ̃. The remaining digits of β̃− δ̃ may be considered in the same way.

Thus, overall, we have z([1]β−δ) = z(β)−1 since only the sth digit contributes differently in β and β̃ − δ̃.

Theorem 15. For nonempty strings α and β with |αβ| ≠ 0,

α ∗ β ⇔ |αβ| ∈ F_{a}(len(β) − 1).

Proof. We proceed by induction on n := |αβ|. Set k := len(β) − 1, so the theorem asserts α ∗ β ⇔ n ∈ F_{a}(k).

If n = 1, then |α| = 0, |β| = 1, β = \underbrace{0 ⋯ 01}_{k+1 digits} and z(β) = k, so α ∗ β ⇔ |α| < z(β) ⇔ 0 <

k ⇔ 1 ∈ F_{a}(k), where the last equivalence follows from the definition of F_{a}(k) and the fact that 1 ∈ F_{a}(k) exactly when k > 0.

Now assume that n > 1 and that the theorem holds for all smaller positive integers.

(i) Suppose n ≡ 0 (mod a).

Write β = β′0, and note len(β′) = k and z(β) = z(β′) since appending a zero to the right of β′ cannot introduce a drop. Then

α ∗ β ⇔ α ∗ β′ ⇔ \frac{n}{a} = |αβ′| ∈ F_{a}(k − 1) ⇔ n ∈ F_{a}(k),

where the second equivalence follows by induction and the last from Lemma 9 since R = 0.

(ii) Suppose n ≢ 0 (mod a). Note that this implies that in base a, the last digit of β is nonzero. There are three cases:

(a) Suppose z(β) = 0. Then β has no drops and thus can be written as a sum of the elements in G_{a}(k). Then |β| = c_{1}a^{k} + ⋯ + c_{k+1}(a^{k} + ⋯ + a + 1), and n = |α| · a^{k+1} + c_{1}a^{k} + ⋯ + c_{k+1}(a^{k} + ⋯ + a + 1) ∉ F_{a}(k). In this case, α ∗ β and n ∈ F_{a}(k) are both false.

(b) Suppose z(β) > 0 and |α| = 0. Certainly n = |β| ≤ a^{k+1} − 1. In fact, since β has a drop, we have n < a^{k+1} − 1. (The base-a digits of β cannot all equal a − 1 since β has a drop.) There are two cases.

(1) If |β| < a^{k}+⋯+a+1, then n < R (n ≢ 0 (mod a) ⟹ R ≥ a^{k}+…+a^{1}+a^{0}). Thus, by Lemma 9, n ∈ F_{a}(k), and therefore α ∗ β and n ∈ F_{a}(k) are both true.

(2) Again let δ be a string of k+1 ones in base a, and assume that a^{k}+⋯+a+1 ≤ |β| < a^{k+1} − 1. Since |α| = 0, we may apply Lemma 9 to obtain

α ∗ β ⇔ α ∗ (β − δ) ⇔ |αβ| − |δ| = n − (a^{k} + … + a + 1) ∈ F_{a}(k) ⇔ n ∈ F_{a}(k),

where it is understood that len(β − δ) = len(β). The first equivalence follows from Lemma 14 (recall that the hypothesis |α| > 0 was unnecessary for Case (i)), the second from the induction hypothesis, and the last from Lemma 10.

(c) Suppose z(β) > 0 and |α| > 0; then by Lemma 14

α ∗ β ⇔ α ∗ (β − δ) or [|α| − 1] ∗ ([1]β − δ)
⇔ n − (a^{k} + ⋯ + a + 1) ∈ F_{a}(k)
⇔ n ∈ F_{a}(k),

where the first equivalence follows from Lemma 14, the second from the induction hypothesis, and the last from Lemma 10.

Theorem 7 is actually a corollary of Theorem 15. One can easily compute f_{a}(n) from Theorem 7. Here are a few example calculations. Notice that to apply Theorem 7 it may be necessary to write a string with leading zeros.

Corollary 16. Let n ∈ ℤ^{+}. Then n ∈ F_{a}(k) if and only if there exist base-a strings α and β such that

1. |αβ| = n,

2. α ∗ β, and

3. k = len(β) − 1.

Proof. If such strings α and β exist, then n = αβ ∈ F_{a}(k) by Theorem 15. Conversely, if n ∈ F_{a}(k), then let β be the last k + 1 digits of a base-a representation of n, and let α be the remaining digits, setting α = 0 if otherwise α would be empty. This gives |αβ| = n and k = len(β) − 1 directly. Furthermore, since |αβ| = n ∈ F_{a}(k), α ∗ β by Theorem 15.

Example 17.

1. For n = 24 = |11000| = |0011000| with base a = 2, let α = 0 and β = 011000; then |αβ| = 24 and 0 = |α| < z(β) = 1. We see that f_{2}(24) = len(β) − 1 = 5 since for no shorter β will we have a drop.

2. In ternary, for n = 50_{10} = |1212_{3}|, let α = 0 and β = 1212; then |αβ| = 50 and 0 = |α| < z(β) = 2. Thus f_{3}(50) = len(β) − 1 = 3.

3. In base 7, for n = 22413_{10} = |122226_{7}|, let α = 1 and β = 22226; then |αβ| = 22413 and 1 = |α| < z(β) = 4. Therefore f_{7}(22413) = 4.

We note that Theorem 15 and Corollary 16 completely characterize the Frobenius sets, F_{a}(k). In addition, if n ∉ F_{a}(k − 1) there is a simple algorithm giving n as a non-negative linear combination of the elements of G_{a}(k − 1).

Representation Algorithm: Assuming n ∉ F_{a}(k − 1) the following algorithm gives t_{i} ≥ 0 such that

n = t_{0}a^{k−1} + t_{1}(a^{k−1} + a^{k−2}) + t_{2}(a^{k−1} + a^{k−2} + a^{k−3}) + ⋯ + t_{k}(a^{k−1} + ⋯ + a^{1} + a^{0}).

1. Write n in base a as n = c_{r} ⋯ c_{1}c_{0}.

2. Let t_{k} := c_{0} and Remain := n − t_{k}(a^{k−1} + ⋯ + a^{1} + a^{0}).

3. If Remain = 0, put t_{k−1} = t_{k−2} = ⋯ = t_{0} := 0, then STOP.

4. Let m := 1.

5. Write Remain in base a as c_{mr} … c_{m2}c_{mm} \overbrace{00 … 0}^{m zeros} .

6. Let t_{k−m} := c_{mm} and put Remain := Remain − t_{k−m}(a^{k−1} + a^{k−2} + ⋯ + a^{m}).

7. If Remain = 0, put t_{k−m−1} = t_{k−m−2} ⋯ = t_{0} := 0, then STOP.

8. If Remain > 0, put m := m + 1. If m < k GOTO step (5).

9. If Remain > 0 and m = k, put t_{0} = \frac{Remain}{a^{k}}. STOP. Here is an example using the Representation Algorithm.

Example 18. Suppose a = 3. Let n = 1541 = 2·3^{6}+3^{4}+2. The ternary representation of 1541 is 2010002. Since 2∗010002 holds but 20∗10002 is false, 1541 ∈ F_{3}(5) but 1541 ∉ F_{3}(4) by Corollary 16. Recall that G_{3}(4) = {81, 108, 117, 120, 121}. We begin by writing the elements of G_{3}(4) in base a = 3: [G_{3}(4)]_{3} = {10000, 11000, 11100, 11110, 11111}. We will find non-negative coefficients t_{i} such that

2010002 = t_{0}(10000) + t_{1}(11000) + t_{2}(11100) + t_{3}(11110) + t_{4}(11111) The ternary representation of 1541 implies t_{4} = 2. The next few steps outlined below

involve subtracting the appropriate multiple of the elements of G_{3}(4). The quantity Remain is changed by each subtraction and each new Remain amount gives another t_{i}.

Step 1  Step 2
n = 2010002 1210010
\underline{−22222}  \underline{−11110}
Remain : 1210010 1121200
⟹ t_{3} = 1  ⟹ t_{2} = 2
Step 3  Step 4
n = 1121200 1022000
\underline{−22200}  \underline{−22000}
Remain : 1022000 1000000
⟹ t_{1} = 2  ⟹ t_{0} = 9

3 Theorem 15 as an Algorithm

Fix the integer a ≥ 2. In this section we present the algorithm for determining, given n ∈ ℤ^{+}, the least k such that n ∈ F_{a}(k). We then briefly discuss the computational complexity of our algorithm. Algorithm:

1. Write n in base a : n = c_{k} ⋯ c_{1}c_{0}.

2. Let α_{0} := c_{k} ⋯ c_{1} and β_{0} := c_{0}.

3. If α_{0} ∗ β_{0}, then n ∈ F_{a}(0). STOP.

4. If not α_{0} ∗ β_{0}, let l := 1.

5. Let α_{l} := c_{k} ⋯ c_{l+1} and β_{l} := c_{l} ⋯ c_{0}.

6. If α_{l} ∗ β_{l}, then n ∈ F_{a}(l). STOP.

7. If l < k − 1, then put l := l + 1. GOTO step 5.

8. Let α_{k} := 0 and β_{k} := c_{k} ⋯ c_{0}.

9. If α ∗ β, then n ∈ F_{a}(k). STOP.

10. Let α_{k+1} := 0 and β_{k+1} = 0c_{k} ⋯ c_{0}. Then |α| = 0 and z(β_{k+1}) = 1, so α ∗ β and n ∈ F_{a}(k + 1). STOP.

It is clear that the above algorithm terminates. Furthermore, since the algorithm checks membership in F_{a}(k) for each value of k sequentially beginning with k = 0, it must determine the least value of k such that n ∈ F_{a}(k), as desired.

In the worst case, steps 5 through 7 are repeated at most log_{a}(n − 1) + 1 times. Each iteration requires about log_{a}(n) operations (mostly from computation of z(β)). Steps outside of this loop require minimal computation, so the algorithm is O(log_{a}^{2}(n)). Note that this algorithm can be improved to O(log(n)) by repeated bisection of the base-a representation of n.

We note in closing that a working group at Willamette University has studied a similar Frobenius-level problem for the following related G-sets. For positive integers a, b, c, d such that gcd(a, b) = gcd(c, d) = 1 and a < b, define G(0) = {a, b}, G(1) = {ac, bc, bc + d}, and for k ≥ 2

G(k) = {ac^{k}, bc^{k}, bc^{k} + dc^{k−1}, bc^{k} + dc^{k−1} + dc^{k−2}, …, bc^{k} + dc^{k} + ⋯ + dc^{0}}.

They have found necessary and sufficient conditions for nested corresponding Frobenius-sets. They are working to solve the Frobenius-level problem for these more general sequentially redundant sets [1].

References

[1] P. Cudworth, T. Dailey, M. Flink, G. Houser, I. Johnson, B. Kehr, P. Le, J. Petersen, and C. Starr, Characterizing a generalized infinite family of Frobenius semigroups by filtration, in preparation.

[2] F. Curtis, On formulas for the Frobenius number of a numerical semigroup, Math. Scand. 67 (1990), 190–192.

[3] J. L. Davison, On the linear Diophantine problem of Frobenius, J. Number Theory 48 (1994), 353–363.

[4] H. Greenberg, Solution to a linear Diophantine equation for nonnegative integers, J. Algorithms 9 (1988), 343–353.

[5] I. Johnson and J. L. Merzel, A class of left ideals of the Steenrod algebra, Homology, Homotopy Appl. 9 (2007), 185–191.

[6] R. Kannan, Lattice translates of a polytope and the Frobenius problem, Combinatorica 12 (1992), 161–177.

[7] R. E. Mosher and M. C. Tangora, Cohomology Operations and Applications in Homotopy Theory, Harper & Row, 1968.

[8] Albert Nijenhaus and Herbert S. Wilf, Representations of integers by linear forms in nonnegative integers, J. Number Theory 4 (1972), 98–106.

[9] J. L. Ramírez-Alfonsín, Complexity of the Frobenius problem, Combinatorica, 16 (1996), 143–147.

[10] D. C. Ravenel, Complex Cobordism and Stable Homotopy Groups of Spheres, Academic Press, 1986.

[11] N. E. Steenrod and D. B. A. Epstein, Cohomology Operations, Princeton University Press, 1962.

[12] J. J. Sylvester, Problem 7382, Math. Quest. Sol. Educational Times 41 (1884), ix, 21.

[13] R. M. W. Wood, Problems in the Steenrod algebra, Bull. London Math. Soc. 30 (1998), 449–517.

2000 Mathematics Subject Classification: Primary 11B37. Keywords: Frobenius problem, Frobenius level, sequentially redundant, Frobenius semigroup.

(Concerned with sequence \underline{A023758}.)

Received August 1 2006; revised versions received August 31 2007; September 13 2008; October 20 2008. Published in Journal of Integer Sequences, December 14 2008.

Return to Journal of Integer Sequences home page.