On a Generalization of the Coin Exchange Problem for Three Variables

Amitabha Tripathi Department of Mathematics Indian Institute of Technology Hauz Khas New Delhi - 110016 India

               atripath@maths.iitd.ac.in

Sujith Vijay^{1} Department of Mathematics Rutgers University – New Brunswick Piscataway, NJ 08854 USA

                sujith@math.rutgers.edu

Abstract

Given relatively prime and positive integers a_{1}, a_{2}, …, a_{k}, let Γ denote the set of nonnegative integers representable by the form a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{k}x_{k}, and let Γ^{⋆} denote the positive integers in Γ. Let S^{⋆}(a_{1}, a_{2}, …, a_{k}) denote the set of all positive integers n not in Γ for which n + Γ^{⋆} is contained in Γ^{⋆}. The purpose of this article is to determine an algorithm which can be used to obtain the set S^{⋆} in the three variable case. In particular, we show that the set S^{⋆}(a_{1}, a_{2}, a_{3}) has at most two elements. We also obtain a formula for g(a_{1}, a_{2}, a_{3}), the largest integer not representable by the form a_{1}x_{1} + a_{2}x_{2} + a_{3}x_{3} with the x_{i}’s nonnegative integers.

1This work was done while the second author was at the Department of Mathematics, Indian Institute of Technology, Delhi.

1 Introduction

Given relatively prime and positive integers a_{1}, a_{2}, …, a_{k} and a positive integer N, consider the equation

a_{1}x_{1} + a_{2}x_{2} + … + a_{k}x_{k} = N  (1)

If each x_{i} is a nonnegative integer, it is well known and easy to show that (1) has a solution for all sufficiently large N. Hence, if we denote by Γ the set {a_{1}x_{1}+a_{2}x_{2}+⋯+a_{k}x_{k} : x_{j} ≥ 0}, then Γ^{c} := ℕ \ Γ is a finite set. A natural problem that then arises is finding the largest N such that (1) has no solution in nonnegative integers, or in other words, of the largest element in Γ^{c}. This problem was first posed by Frobenius, who is believed to have been the first person to show that a_{1}a_{2} − a_{1} − a_{2} is the largest element in Γ^{c} in the two variable case. Frobenius was also responsible in introducing the notation g(a_{1}, a_{2}, …, a_{k}) to denote the largest number in Γ^{c}. It is for this reason that the problem is also known as the linear Diophantine problem of Frobenius. The coin exchange problem derives its name from the obvious interpretation of this problem in terms of exchanging coins of arbitrary denomination with an infinite supply of coins of certain fixed denominations. The number of elements in Γ^{c}, denoted by n(a_{1}, a_{2}, …, a_{k}), was later introduced by Sylvester [25], and it was shown that n(a_{1}, a_{2}) = \frac{1}{2}(a_{1} − 1)(a_{2} − 1). Another related function is s(a_{1}, a_{2}, …, a_{k}), which stands for the sum of elements in Γ^{c}, introduced by Brown and Shiue [6], wherein it was shown that s(a_{1}, a_{2}) = \frac{1}{12}(a_{1} − 1)(a_{2} − 1)(2a_{1}a_{2} − a_{1} − a_{2} − 1).

An explicit solution for the functions g and n in more than two variables has met with little success over the years except in special cases. There is a simple formula for each of these functions when the a_{j}’s are in arithmetic progression [2, 9, 19, 27], but results obtained in other cases usually give upper bounds, deal with a special case or give an algorithmic solution [3, 4, 5, 11, 12, 13, 15, 20, 21, 22, 23, 24]. We refer to the book [18] where a complete account of the Frobenius problem can be found.

A variation of the coin exchange problem which also leads to its generalization was introduced by Tripathi [28]. We employ the notation used in [28], and denote by S^{⋆}(a_{1}, a_{2}, …, a_{k}) the set of all n ∈ Γ^{c} such that

n + Γ^{⋆} ⊆ Γ^{⋆},

where Γ^{⋆} = Γ\{0}. Let g^{⋆}(a_{1}, a_{2}, …, a_{k}) (respectively, n^{⋆}(a_{1}, a_{2}, …, a_{k}) and s^{⋆}(a_{1}, a_{2}, …, a_{k})) denote the least (respectively, the number and sum of) elements in S^{⋆}. It is apparent that g(a_{1}, a_{2}, …, a_{k}) is the largest element in S^{⋆}, so that

g^{⋆}(a_{1}, a_{2}, …, a_{k}) ≤ g(a_{1}, a_{2}, …, a_{k}),

and n^{⋆}(a_{1}, a_{2}, …, a_{k}) ≥ 1, with equality if and only if g^{⋆} = g. It is interesting to note that this problem also arises from looking at the generators for the derivation modules of certain monomial curves [16, 17] and also in comparing numerical semigroups [8], and has been extensively studied in a more algebraic setting.

For each j, 1 ≤ j ≤ a_{1} − 1, let m_{j} denote the least number in Γ congruent to j mod a_{1}. Then m_{j} − a_{1} is the largest number in Γ^{c} congruent to j mod a_{1}, and no number less than this in this residue class can be in S^{⋆}, for they would differ by a multiple of a_{1}, an element in Γ^{⋆}. Therefore

S^{⋆}(a_{1}, a_{2}, …, a_{k}) ⊆ {m_{j} − a_{1} : 1 ≤ j ≤ a_{1} − 1},  (2)

g^{⋆}(a_{1}, a_{2}, …, a_{k}) ≤ ( max_{1≤j≤a_{1}−1} m_{j}) − a_{1} = g(a_{1}, a_{2}, …, a_{k}),  (3)
n^{⋆}(a_{1}, a_{2}, …, a_{k}) ≤ a_{1} − 1,  (4)

and

s^{⋆}(a_{1}, a_{2}, …, a_{k}) ≤ ∑_{j=1}^{a_{1}−1} m_{j} − a_{1}(a_{1} − 1).  (5)

More precisely,

m_{j} − a_{1} ∈ S^{⋆}(a_{1}, a_{2}, …, a_{k}) ⟺ (m_{j} − a_{1}) + m_{i} ≥ m_{j+i}  (6)

for 1 ≤ i ≤ a_{1} − 1. The expression for g(a_{1}, a_{2}, …, a_{k}) in (3) is due to Brauer & Shockley [5]. It is known [1] that if the semigroup Γ is symmetric then S^{⋆} = {g(a_{1}, a_{2}, …, a_{k})}.

The purpose of this article is to determine the set S^{⋆} together with the related functions in the three variable case. We shall use the variables a, b, c, and assume that a, b, c are coprime.

Given a, b, c, we define the matrix M by

M := ( \begin{matrix}x_{a} & y_{a} & z_{a} \\ x_{b} & y_{b} & z_{b} \\ x_{c} & y_{c} & z_{c} \end{matrix} ) ,

where the entries are nonnegative integers. Let x_{a}, y_{b}, z_{c} be the least positive integers such that

ax_{a} = by_{a} + cz_{a} for some integers y_{a} ≥ 0, z_{a} ≥ 0;  (7)
by_{b} = ax_{b} + cz_{b} for some integers x_{b} ≥ 1, z_{b} ≥ 0;  (8)
cz_{c} = ax_{c} + by_{c} for some integers x_{c} ≥ 1, y_{c} ≥ 0.  (9)

The matrix M, with the entries at x_{b} and x_{c} allowed to be 0, was used in [7, 10] in order to give an expression for g(a, b, c); see also [Proposition 4.7.1, [18]]. For the sake of completeness, we state the proposition below.

Proposition 1. Let x_{a}, y_{b}, z_{c} be the least positive integers such that there exist integers x_{b}, x_{c}, y_{a}, y_{c}, z_{a}, z_{b} ≥ 0 with

ax_{a} = by_{a} + cz_{a}, by_{b} = ax_{b} + cz_{b}, cz_{c} = ax_{c} + by_{c}.

(a) If x_{b}, x_{c}, y_{a}, y_{c}, z_{a}, z_{b} are all greater than 0, then

x_{a} = x_{b} + x_{c}, y_{b} = y_{a} + y_{c}, z_{c} = z_{a} + z_{b}.

(b) (i) If x_{b} = 0 or x_{c} = 0, then by_{b} = cz_{c} and ax_{a} = by_{a} + cz_{a} with y_{a}, z_{a} > 0.

(ii) If y_{a} = 0 or y_{c} = 0, then ax_{a} = cz_{c} and by_{b} = ax_{b} + cz_{b} with x_{b}, z_{b} > 0.

(iii) If z_{a} = 0 or z_{c} = 0, then ax_{a} = by_{b} and cz_{c} = ax_{c} + by_{c} with x_{c}, y_{c} > 0.

We now state and prove our main result where we determine the set S^{⋆}(a, b, c) in terms of the entries of the matrix M.

Theorem 1. Let a < b < c with gcd(a, b, c) = 1. With the entries of the matrix M as defined in (7), (8), (9),

S^{⋆}(a, b, c) = \{ \begin{matrix}\{b(y_{b} − 1) + c(z_{a} − 1) − a, b(y_{a} − 1) + c(z_{c} − 1) − a\}, \\ if y_{a}, z_{a} ≥ 1; \\ \{b(y_{b} − 1) + c(z_{a} − 1) − a\}, if y_{a} = 0; \\ \{b(y_{a} − 1) + c(z_{c} − 1) − a\}, if z_{a} = 0. \end{matrix}

Proof. For any integer j, with 1 ≤ j ≤ a − 1, let m_{j} = by + cz, where y, z are nonnegative integers. Recall that m_{j} is the smallest integer in Γ congruent to j mod a. Now y ≤ y_{b} − 1, since otherwise b(y − y_{b}) + c(z + z_{b}) ≡ j mod a and, by equation (8), it is less than m_{j}. Similarly, by using equation (9), we have z ≤ z_{c} − 1.

If y_{a} > y_{b}, then a(x_{a} − x_{b}) = b(y_{a} − y_{b}) + c(z_{a} + z_{b}) > 0, contradicting the minimality of x_{a}. Thus, y_{a} ≤ y_{b}, and similarly z_{a} ≤ z_{c}. Note that these inequalities follow immediately from the above Proposition, and that the former inequality is strict if z_{a} > 0 and the latter if y_{a} > 0.

If y ≥ y_{a} and z ≥ z_{a}, then m_{j} − (by_{a} + cz_{a}) would be a positive integer less than m_{j} and congruent to j mod a. Therefore, at least one of

0 ≤ y ≤ y_{a} − 1 and 0 ≤ z ≤ z_{c} − 1  (10)

or

0 ≤ y ≤ y_{b} − 1 and 0 ≤ z ≤ z_{a} − 1  (11)

holds. Case I: (y_{a}, z_{a} ≥ 1) We claim that m_{i}^{⋆} := b(y_{a} − 1) + c(z_{c} − 1) = m_{i} and m_{j}^{⋆} := b(y_{b} − 1) + c(z_{a} − 1) = m_{j}, with y_{a} < y_{b} and z_{a} < z_{c}. If m_{i}^{⋆} > m_{i} = by + cz, then b(y_{a} − y − 1) + c(z_{c} − z − 1) = (b(y_{a} − 1) + c(z_{c} − 1)) − (by + cz) ∈ aℕ. Since 0 ≤ z ≤ z_{c} − 1, we have 0 ≤ z_{c} − z − 1 < z_{c}, so that from the definition of z_{c} we conclude y_{a} − y − 1 ≥ 1. Hence, b(y_{a} − y − 1) + c(z_{c} − z − 1) = (by_{a} + cz_{a}) + ma for some m ∈ ℕ. But then ma + b(y + 1) = c(z_{c} − z_{a} − z − 1), which contradicts the minimality of z_{c}. This contradiction proves that m_{i}^{⋆} = m_{i}, and we have y_{a} < y_{b} since z_{a} > 0 by an earlier argument in this proof. A similar argument shows that m_{j}^{⋆} = m_{j}, with z_{a} < z_{c}.

We now claim that if m_{k} = by + cz ≠ b(y_{a} − 1) + c(z_{c} − 1), b(y_{b} − 1) + c(z_{a} − 1), then m_{k} − a ∉ S^{⋆}. To prove this, we exhibit m′_{k} ∈ Γ^{⋆} such that (m_{k} − a) + m′_{k} ∉ Γ^{⋆}. If 0 ≤ y ≤ y_{a} −1 and 0 ≤ z ≤ z_{c} −1, set m′_{k} := b(y_{a} −y −1)+c(z_{c} −z −1); and if 0 ≤ y ≤ y_{b} −1 and 0 ≤ z ≤ z_{a} − 1, set m′_{k} := b(y_{b} − y − 1) + c(z_{a} − z − 1). In the first case, (m_{k} − a) + m′_{k} equals m_{i}^{⋆} −a, and in the second case, it equals m_{j}^{⋆} −a. So, in both cases, (m_{k} −a)+m′_{k} ∉ Γ^{⋆}. This proves that S^{⋆} ⊆ {b(y_{a} − 1) + c(z_{c} − 1) − a, b(y_{b} − 1) + c(z_{a} − 1) − a}.

To complete the first case of our proof, it remains to show that each of the two numbers m_{i}^{⋆} − a, m_{j}^{⋆} − a belong to S^{⋆}. We show this for m_{i}^{⋆} − a; a similar argument shows that m_{j}^{⋆} − a ∈ S^{⋆}. Consider N = (b(y_{a} − 1) + c(z_{c} − 1) − a) + n, where n = ax_{0} + by_{0} + cz_{0} with x_{0}, y_{0}, z_{0} nonnegative, not all zero. Observe that y_{a} − 1 ≥ 0 by assumption, and that z_{c} − 1 ≥ 0 by definition. If x_{0} ≥ 1, then it is clear that N ∈ Γ^{⋆}. If y_{0} ≥ 1, then N = a(x_{a} − 1 + x_{0}) + b(y_{0} − 1) + c(z_{c} − z_{a} − 1 + z_{0}) ∈ Γ^{⋆}. If z_{0} ≥ 1, then N = a(x_{c} − 1 + x_{0}) + b(y_{a} + y_{c} − 1 + y_{0}) + c(z_{0} − 1) ∈ Γ^{⋆}. This proves m_{i}^{⋆} − a ∈ S^{⋆}, and completes Case I. Case II: (y_{a} = 0 or z_{a} = 0) If z_{a} = 0, equation (10) must hold. We show that m_{i}^{⋆} − a = b(y_{a} −1)+c(z_{c} −1)−a is the only element in S^{⋆} in this case. Indeed, the argument in Case I shows that m_{i}^{⋆} = m_{i}, that m_{i}^{⋆} − a ∈ S^{⋆}, and that S^{⋆} has at most two elements. Thus, it only remains to show that m_{j}^{⋆}−a = b(y_{b}−1)−c−a ∉ S^{⋆}. In fact, m_{j}^{⋆} = b(y_{b}−1)−c = by+cz = m_{j} implies b(y_{b} − y − 1) = am + c(z + 1) for some m ∈ ℕ. Since this contradicts the minimality of y_{b}, m_{j}^{⋆} > m_{j} and so m_{j}^{⋆} − a = b(y_{b} − 1) − c − a ∉ S^{⋆}. In case y_{a} = 0, equation (11) must hold, and a similar argument will show that b(y_{b} − 1) + c(z_{a} − 1) − a is the only element in S^{⋆} in this case. This completes the proof of our theorem.

Corollary 1. Let a < b < c with gcd(a, b, c) = 1. With the notation of Theorem 1,

g(a, b, c) = \{ \begin{matrix}max \{b(y_{b} − 1) + c(z_{a} − 1) − a, b(y_{a} − 1) + c(z_{c} − 1) − a\}, \\ if y_{a}, z_{a} ≥ 1; \\ b(y_{b} − 1) + c(z_{a} − 1) − a, if y_{a} = 0; \\ b(y_{a} − 1) + c(z_{c} − 1) − a, if z_{a} = 0. \end{matrix}

Remark 1. A variation of Corollary 1 is due to Johnson [12]. In [12], the variables a, b, c are assumed to be pairwise coprime, so that x_{b}, y_{b}, z_{b} and x_{c}, y_{c}, z_{c} are defined analogously to x_{a}, y_{a}, z_{a}, and therefore taken as nonnegative. In the case of Theorem 1 we only assume that a, b, c are coprime, and need the positivity of x_{b}, y_{b}, z_{b} and x_{c}, y_{c}, z_{c}. If we assume that a, b, c are pairwise coprime, y_{a} > 0 and z_{a} > 0, so that only the first case in Theorem 1 holds; see also [Theorem 2.2.3, [18]]:

Let a < b < c with a, b, c pairwise coprime. With the notation of Theorem 1,

g(a, b, c) = max {b(y_{b} − 1) + c(z_{a} − 1) − a, b(y_{a} − 1) + c(z_{c} − 1) − a}

Corollary 2. Let a < b < c be such that gcd(a, b, c) = 1 and a|(b + c). Then

S^{⋆}(a, b, c) = \{b ⌊\frac{ac}{b + c}⌋ − a, c ⌊\frac{ab}{b + c}⌋ − a\} .

Proof. Observe that a|(bx−cy) if and only if a|(x+y) since a|(b+c) and gcd(a, b, c) = 1 forces gcd(a, b) = 1 = gcd(a, c). If we write y = ma−x, then bx > cy reduces to x > \frac{mac}{b+c}. The least such x is clearly y_{b} = ⌈\frac{ac}{b+c}⌉. Similarly, z_{c} = ⌈\frac{ab}{b+c}⌉, and it is easy to see that (y_{a}, z_{a}) = (1, 1). Observe that b+c cannot divide either ab or ac since gcd(b, c) = 1. Therefore, y_{b} −1 = ⌊\frac{ac}{b+c}⌋ and z_{c} − 1 = ⌊\frac{ab}{b+c}⌋, and the result now follows from Theorem 1.

Remark 2. Corollary 2 implies that

g(a, b, c) = max \{b ⌊\frac{ac}{b + c}⌋ − a, c ⌊\frac{ab}{b + c}⌋ − a\}

when a|(b + c). This result is well-known and due to Brauer & Shockley; see [5, 26].

Corollary 3. If gcd(a, d) = 1, then

S^{⋆}(a, a + d, a + 2d) = \{ \begin{matrix}\{\frac{1}{2}a(a − 2) + d(a − 1)\} , if a is even; \\ \{\frac{1}{2}a(a − 3) + d(a − 1), \frac{1}{2}a(a − 3) + d(a − 2)\} , \\ if a is odd. \end{matrix}

Proof. Observe that a|{(a+d)x+(a+2d)y} if and only if a|(x+2y). Therefore, (y_{a}, z_{a}) equals (0, \frac{1}{2}a) if a is even and (1, \frac{1}{2}(a − 1)) if a is odd. If a is even, it is easy to see that y_{b} = 2, and the only element in the set is (a+d)+ \frac{1}{2}(a+2d)(a−2)−a = d(a−1)+ \frac{1}{2}a(a−2). If a is odd, the required conditions to determine z_{c} reduce to minimizing y such that (a+2d)y > (a+d)x and 2y ≡ x mod a. This gives z_{c} = \frac{1}{2}(a + 1) and the set thus consists of the two elements (a+d)+ \frac{1}{2}(a+2d)(a−3)−a = d(a−2)+ \frac{1}{2}a(a−3) and \frac{1}{2}(a+2d)(a−1)−a = d(a−1)+ \frac{1}{2}a(a−3). This completes the proof.

Remark 3. Corollary 3 is the three variable version of the main result of [28]. Determination of g(a, a + d, a + 2d) is an immediate consequence of Corollary 3 and is also a special case of a more general result when there is no restriction on the number of variables in arithmetic progression, and is due to Roberts; see [2, 19, 27]. Corollary 3 implies

g(a, a + d, a + 2d) = a ⌊\frac{a − 2}{2}⌋ + d(a − 1).

A description of the set S^{⋆}(a, b, c), and hence of the several related functions, including g(a, b, c) and g^{⋆}(a, b, c), involves at least a partial knowledge of the matrix M. The description of M is a known result due to Morales [14], and is described in [Claim 8.4.3, [18]].

2 Acknowledgement

The authors wish to thank the referee for several suggestions and references that have helped improve an earlier version of their paper.

References

[1] V. Barucci, D. E. Dobbs and M. Fontana, Maximality properties of one-dimensional analytically irreducible local domains, Memoires Amer. Math. Soc., 125/598, 1997.

[2] P. T. Bateman, Remark on a recent note on linear forms, Amer. Math. Monthly, 65 (1958), 517–518.

[3] A. Brauer, On a problem of partitions – I, Amer. J. Math., 64 (1942), 299–312.

[4] A. Brauer and B. M. Seelbinder, On a problem of partitions – II, Amer. J. Math., 76 (1954), 343–346.

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

[6] T. C. Brown and P. J. Shiue, A remark related to the Frobenius problem, Fibonacci Quart., 31 (1993), 31–36.

[7] G. Denham, Short generating functions for some semigroup algebras, The Electronic Journal of Combinatorics, 10, Research paper 36 (2003), 7 pages.

[8] D. E. Dobbs and G. L. Matthews, On comparing two chains of numerical semigroups and detecting Arf semigroups, Semigroup Forum, 63, #2 (2001), 237–246.

[9] D. D. Grant, On linear forms whose coefficients are in arithmetic progression, Israel J. Math., 15 (1973), 204–209.

[10] J. Herzog, Generators and relations of abelian semigroups and semigroup rings, Manuscripta Math., 3 (1970), 175–193.

[11] G. R. Hofmeister, Zu einem Problem von Frobenius, Norske Videnskabers Selskabs Skrifter, 5 (1966), 1–37.

[12] S. M. Johnson, A linear diophantine problem, Canad. J. Math. 12 (1960), 390–398.

[13] R. J. Levit, A minimum solution for a diophantine equation, Amer. Math. Monthly, 63 (1956), 646–651.

[14] M. Morales, Syzygies of monomial curves and a linear diophantine problem of Frobenius, Internal Report, Max Planck Institut für Mathematik, Bonn, 1987.

[15] A. Nijenhuis and H. S. Wilf, Representations of integers by linear forms in non negative integers, J. Number Theory, 4 (1972), 98–106.

[16] D. P. Patil and Balwant Singh, Generators for the derivation modules and the relation ideals of certain curves, Manuscripta Math., 68 (1990), 327–335.

[17] D. P. Patil and I. Sengupta, Minimal set of generators for the derivation modules of certain monomial curves, Comm. Algebra, 27 (1999), 5619–5631.

[18] J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Oxford Lecture Series in Mathematics and its Applications, 30, Oxford Univerity Press, 2005.

[19] J. B. Roberts, Note on linear forms, Proc. Amer. Math. Soc., 7 (1956), 465–469.

[20] J. B. Roberts, On a diophantine problem, Canad. J. Math., 9 (1957), 219–222.

[21] Ö. J. Rödseth, On a linear diophantine problem of Frobenius, J. reine Angew. Math., 301 (1978), 171–178.

[22] Ö. J. Rödseth, On a linear diophantine problem of Frobenius II, J. reine Angew. Math., 307/308 (1979), 431–440.

[23] E. S. Selmer and Ö. Beyer, On the linear diophantine problem of Frobenius in three variables, J. reine Angew. Math., 301 (1978), 161–170.

[24] E. S. Selmer, On the linear diophantine problem of Frobenius, J. reine Angew. Math., 293/294 (1977), 1–17.

[25] J. J. Sylvester, Mathematical questions with their solutions, The Educational Times, 41 (1884), 21.

[26] A. Tripathi, Topics in Number Theory, Ph. D. Thesis, Department of Mathematics, State University of New York, Buffalo, 1989.

[27] A. Tripathi, The coin exchange problem for arithmetic progressions, Amer. Math. Monthly, 101, (1994), 779–781.

[28] A. Tripathi, On a variation of the coin exchange problem for arithmetic progressions, Integers, 3, #A01 (2003), 1–5.

2000 Mathematics Subject Classification: Primary 11D04. Keywords: coin exchange problem, linear diophantine problem of Frobenius.

Received December 20 2005; revised version received September 12 2006. Published in Journal of Integer Sequences, September 12 2006.

Return to Journal of Integer Sequences home page.