On a Generalization of the Frobenius Number

Alexander Brown, Eleanor Dannenberg, Jennifer Fox, Joshua Hanna, Katherine Keck, Alexander Moore, Zachary Robbins, Brandon Samples,

and James Stankewicz Department of Mathematics University of Georgia Athens, GA 30602 USA

                     stankewicz@gmail.com

Abstract

We consider a generalization of the Frobenius problem, where the object of interest is the greatest integer having exactly j representations by a collection of positive relatively prime integers. We prove an analogue of a theorem of Brauer and Shockley and show how it can be used for computation.

1 Introduction

The linear diophantine problem of Frobenius has long been a celebrated problem in number theory. Most simply put, the problem is to find the Frobenius number of k positive relatively prime integers (a_{1}, …, a_{k}), i.e., the greatest integer M for which there is no way to express M as the non-negative integral linear combination of the given a_{i}.

A generalization, which has drawn interest both from classical study of the Frobenius problem ([1, Problem A.2.6]) and from the perspective of partition functions and integer points in polytopes (as in Beck and Robins [2]), is to ask for the greatest integer M that can be expressed in exactly j different ways. We make this precise with the following definitions:

A representation of M by a k-tuple (a_{1}, …, a_{k}) of non-negative, relatively prime integers is a solution (x_{1}, …, x_{k}) ∈ ℕ^{k} to the equation M = ∑_{i=1}^{k} a_{i}x_{i}.

We define the j-Frobenius number of a k-tuple (a_{1}, …, a_{k}) of relatively prime positive integers to be the greatest integer M with exactly j representations of M by (a_{1}, …, a_{k}) if such a positive integer exists and zero otherwise. We refer to this quantity as g_{j}(a_{1}, …, a_{k}).

Finally, we define f_{j}(a_{1}, …, a_{k}) exactly as we defined g_{j}(a_{1}, …, a_{k}), except that we consider only positive representations (x_{1}, …, x_{k}) ∈ ℤ_{>0}^{k}.

Note that the 0-Frobenius number of (a_{1}, …, a_{k}) is just the classical Frobenius number. The purpose of this paper is to prove a generalization of a result of Brauer and Shockley [3] on the classical Frobenius number.

2 The Main Results

Our main result is the following:

Theorem 1. If d = gcd(a_{2}, …, a_{k}) and j ≥ 0, then either

g_{j}(a_{1}, a_{2}, …, a_{k}) = d · g_{j}(a_{1}, \frac{a_{2}}{d} , …, \frac{a_{k}}{d}) + (d − 1)a_{1}

or g_{j}(a_{1}, a_{2}, …, a_{k}) = g_{j}(a_{1}, \frac{a_{2}}{d} , …, \frac{a_{k}}{d}) = 0.

Lemma 2. If f_{j}(a_{1}, …, a_{k}) is nonzero, there exist integers x_{2}, …, x_{k} > 0 such that

f_{j}(a_{1}, …, a_{k}) = ∑_{i=2}^{k} a_{i}x_{i}.

Proof. Let f_{j} := f_{j}(a_{1}, …, a_{k}). By the definition of f_{j}, we can write f_{j} = ∑_{i=1}^{k} a_{i}x_{i,ℓ} with

x_{i,ℓ} > 0 for 1 ≤ ℓ ≤ j. Since

f_{j} + a_{1} = ∑_{i=1}^{k} a_{i}x_{i,ℓ} + a_{1} = a_{1}(x_{1,ℓ} + 1) + ∑_{i=2}^{k} a_{i}x_{i,ℓ},

we obtain at least j positive representations of f_{j} + a_{1}. As f_{j} is the largest number with exactly j positive representations, there must be at least j + 1 distinct ways to represent

f_{j} + a_{1}. Specifically, we have f_{j} + a_{1} = ∑_{i=1}^{k} a_{i}x′_{i,ℓ} with x′_{i,ℓ} > 0 for all 1 ≤ ℓ ≤ j + 1. Subtract

a_{1} from both sides of these j + 1 equations to obtain f_{j} = (x′_{1,ℓ} − 1)a_{1} + ∑_{i=2}^{k} a_{i}x′_{i,ℓ}. Evidently,

there exists some ℓ_{0} ∈ [1, j + 1] for which x′_{1,ℓ_{0}} − 1 = 0 because f_{j} cannot have j + 1 positive

representations. Therefore, f_{j}(a_{1}, …, a_{k}) = ∑_{i=2}^{k} a_{i}x′_{i,ℓ_{0}}.

Theorem 3. If gcd(a_{2}, …, a_{k}) = d, then

f_{j}(a_{1}, a_{2}, …, a_{k}) = d · f_{j}(a_{1}, \frac{a_{2}}{d} , …, \frac{a_{k}}{d}).

Proof. Let a_{i} = da′_{i} for i = 2, …, k and N = f_{j}(a_{1}, …, a_{k}). Assuming N > 0, we know by Lemma 2 that

N = ∑_{i=2}^{k} a_{i}x_{i} = d ∑_{i=2}^{k} a′_{i}x_{i}

with x_{i} > 0. Let N′ = ∑_{i=2}^{k} a′_{i}x_{i}. We want to show that N′ = f_{j}(a_{1}, a′_{2}, …, a′_{k}) and will do this in three steps.

Step 1: First, we know that N′ does not have j + 1 or more positive representations by a_{1}, a′_{2}, …, a′_{k}. If N′ could be so represented, then for 1 ≤ l ≤ j + 1 we would have

N′ = a_{1}y_{1,ℓ} + ∑_{i=2}^{k} a′_{i}y_{i,ℓ}.

Multiplying this equation by d immediately produces too many representations of N and thus a contradiction.

Step 2: Next, we know that

f_{j}(a_{1}, …, a_{k}) = N = a_{1}x_{1,ℓ} + ∑_{i=2}^{k} a_{i}x_{i,ℓ}

for 1 ≤ l ≤ j and x_{i} > 0, so

\frac{N}{d} = \frac{a_{1}x_{1,ℓ}}{d} + ∑_{i=2}^{k} \frac{a_{i}x_{i,ℓ}}{d} .

Since d|N and d|a_{i} for i ≥ 2, we must have d|a_{1}x_{1,ℓ} for 1 ≤ ℓ ≤ j. In addition, gcd(a_{1}, d) = 1 so we must have d|x_{1,ℓ} for 1 ≤ ℓ ≤ j. So

N′ = a_{1} \frac{x_{1,ℓ}}{d} + ∑_{i=2}^{k} a′_{i}x_{i,ℓ},

hence N′ has at least j distinct positive representations. But we have already shown that N′ cannot have j + 1 or more positive representations, thus N′ has exactly j positive representations.

Step 3: Finally we will show that N′ is the largest number with exactly j positive representations by a_{1}, a′_{2}, …, a′_{k}. Consider any n > N′. Since dn > dN′ = N, we know that dn can be represented as a linear combination of a_{1}, …, a_{k} in exactly X ways with X ≠ j. Thus, for 1 ≤ l ≤ X and X ≠ j we have

dn = a_{1}x_{1,ℓ} + ∑_{i=2}^{k} a_{i}x_{i,ℓ}

and as in Step 2,

n = a_{1}(\frac{x_{1,ℓ}}{d}) + ∑_{i=2}^{k} a′_{i}x_{i,ℓ}.

If X > j then we certainly do not have exactly j representations, so assume X < j. Assume now that we can write n = a_{1}y_{1} + ∑_{i=2}^{k} a′_{i}y_{i} where y_{i} ≠ x_{i,ℓ} for any such ℓ. By multiplying by d we get a new representation for dn, which is a contradiction because dn is represented in exactly X ≠ j ways.

Therefore N′ is the greatest number with exactly j positive representations and so

N′ = f_{j}(a_{1}, a′_{2}, …, a′_{k}).

Thus

f_{j}(a_{1}, a_{2}, …, a_{k}) = d · f_{j}(a_{1}, \frac{a_{2}}{d} , …, \frac{a_{k}}{d}).

Having established our results about f_{j}(a_{1}, …, a_{k}), we show that we can translate these results to results about the j-Frobenius numbers.

Lemma 4. Either f_{j}(a_{1}, …, a_{k}) = g_{j}(a_{1}, …, a_{k}) = 0 or,

f_{j}(a_{1}, …, a_{k}) = g_{j}(a_{1}, …, a_{k}) + ∑_{i=1}^{k} a_{i}.

Proof. For ease, write f_{j} for f_{j}(a_{1}, …, a_{k}), g_{j} for g_{j}(a_{1}, …, a_{k}), and K = ∑_{i=1}^{k} a_{i}.

Any representation (y_{1}, …, y_{k}) of M gives a representation (y_{1} + 1, …, y_{k} + 1) of M + K. Moreover, adding or subtracting K preserves the distinctness of representations because it adjusts every coefficient y_{i} by 1. Therefore if M has j representations, M + K has at least j positive representations. Likewise, every positive representation of M + K gives a representation of M. Thus f_{j} = 0 if and only if g_{j} = 0. Assume now that f_{j} and g_{j} are both nonzero.

Suppose that f_{j} < g_{j} + K. By definition, we can find exactly j representations (y_{1}, …, y_{k}) for g_{j} and g_{j} has exactly j representations if and only if g_{j} + K has exactly j positive representations (x_{1}, …, x_{k}). However, by assumption g_{j} + K > f_{j} and g_{j} + K has exactly j positive representations. This contradicts the definition of f_{j}, hence f_{j} ≥ g_{j} + K.

Suppose that f_{j} > g_{j} + K. By definition, we can find exactly j positive representations (x_{1}, …, x_{k}) for f_{j}. The same argument as above shows that f_{j} − K has exactly j representations in contradiction to the definition of g_{j}. Thus f_{j} ≤ g_{j} + K.

Proof of Theorem 1: Combine Theorem 3 with Lemma 4.

Corollary 5. Let a_{1}, a_{2} be coprime positive integers and let m be a positive integer. Suppose that g_{j} = g_{j}(a_{1}, a_{2}, ma_{1}a_{2}) ≠ 0. Then

• g_{j} = (j + 1)a_{1}a_{2} − a_{1} − a_{2} for j < m + 1

• g_{m+1} = 0 and

• g_{m+2} = (m + 2)a_{1}a_{2} − a_{1} − a_{2}.

Proof. Theorem 1 tells us that if g_{j}(1, 1, m) ≠ 0 then

g_{j}(a_{1}, a_{2}, ma_{1}a_{2}) = a_{2}(g_{j}(a_{1}, 1, ma_{1})) + (a_{2} − 1)a_{1}
= a_{2} (a_{1}g_{j}(1, 1, m) + (a_{1} − 1)1) + (a_{2} − 1)a_{1}
= a_{1}a_{2}(g_{j}(1, 1, m) + 2) − a_{1} − a_{2}.

Following Beck and Robins in their proof of [2, Proposition 1], we can use the values of the restricted partition function p_{1,1,m}(k) to determine g_{j}(1, 1, m). Furthermore we can determine the relevant values with the Taylor series \frac{1}{(1−t)^{2}(1−t^{m})} = ∑_{k=0}^{∞} p_{1,1,m}(k)t^{k}. Now recall that for k < m, p_{1,1,m}(k) = p_{1,1}(k) = k + 1 but p_{1,1,m}(m) = m + 2 and for all k > m, p_{1,1,m}(k) > m + 2. Note that no number is represented m + 1 times. Thus g_{m+1}(1, 1, m) = 0, g_{j}(1, 1, m) = j − 1 for j < m and g_{m+2}(1, 1, m) = m.

Remark 6. It is a consequence of the asymptotics in Nathanson [4] that for a given tuple, there may be many j for which g_{j} = 0, so the ordering g_{0} < g_{1} < ⋯ may not hold. In the process of discovering the theorems of this paper, we noted the somewhat stranger occurrence of tuples where 0 < g_{j+1} < g_{j}.

Take, for instance, the 3-tuple (3, 5, 8). The order g_{0} < g_{1} < ⋯ holds until g_{14} = 52 and g_{15} = 51. As should also be the case, the 3-tuple increased by a factor of d = 2 creates the new “dependent” 3-tuple (3, 10, 16), which fails to hold order in the same position with g_{14} = 107 and g_{15} = 105. A few independent examples are as follows:

g_{17}(2, 5, 7) = 43 and g_{18}(2, 5, 7) = 42,

g_{38}(2, 5, 17) = 103 and g_{39}(2, 5, 17) = 102,

g_{35}(4, 7, 19) = 181 and g_{36}(4, 7, 19) = 180, and

g_{38}(9, 11, 20) = 376 and g_{39}(9, 11, 20) = 369.

We do not as of yet know a lower bound on j for the above to occur. Indeed, in every case we have computed, if g_{0}, g_{1} > 0 then g_{1} > g_{0}, but to date neither a proof or a counterexample has presented itself.

3 Acknowledgments

The research done in this note was completed as part of the undergraduate number theory VIGRE research seminar directed by Professor Dino Lorenzini and assisted by graduate students Brandon Samples and James Stankewicz at the University of Georgia in Fall 2008. Brandon Samples and James Stankewicz were partially supported by NSF VIGRE grant DMS-0738586. Support for the seminar was provided by the Mathematics Department’s NSF VIGRE grant.

References

[1] J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Oxford University Press, 2005.

[2] M. Beck and S. Robins, A formula related to the Frobenius Problem in two dimensions, in Number Theory (New York 2003), Springer, New York, 2004, pp. 17–23.

[3] A. Brauer and J. E. Shockley, On a problem of Frobenius, J. Reine Angew. Math. 211 (1962) 215–220.

[4] M. Nathanson, Partitions with parts in a finite set, Proc. Amer. Math. Soc. 128 (2000) 1269–1273.

2000 Mathematics Subject Classification: Primary 11D45, Secondary 45A05. Keywords: Frobenius problem, counting solutions of Diophantine equations, linear integral equations.

2000 Mathematics Subject Classification: Primary 11D45; Secondary 45A05. Keywords: Frobenius problem, counting solutions of Diophantine equations, linear integral equations.

Received April 29 2009; revised version received January 7 2010. Published in Journal of Integer Sequences, January 8 2010.

Return to Journal of Integer Sequences home page.