ON A DIOPHANTINE PROBLEM OF FROBENIUS

SİNAN SERTÖZ AND ALİ E. ÖZLÜK

Communicated by C. Arf

Abstract. Frobenius problem is to find the largest integer g which cannot be expressed as a linear combination of some given natural numbers 1 < a_{1} < ⋯ < a_{n} with nonnegative integer coefficients, where a_{1}, …, a_{n} are relatively prime. We consider this problem as the investigation of the lattice points of the region {(x_{1}, …, x_{n}) ∈ ℝ^{n} | x_{1}, …, x_{n} > 0}. It can then be shown that g is the largest element of a finite set S, (lemma 1). Even though S is finite it is constructed using an infinite set H. Our main result (theorem 4) is to show that a finite subset E of H suffices to determine g. These methods also yield an upper bound for g, (lemmas 2 and 3).

1. Introduction

The Diophantine problem of Frobenius consists of finding the largest integer N which cannot be expressed as a linear combination of some given relatively prime integers with nonnegative coefficients. To be more precise let 1 < a_{1} < ⋯ < a_{n} be integers whose greatest common divisor is 1. For a given N ∈ ℕ we look at the existence of solutions of the equation N = a_{1}y_{1} +⋯+a_{n}y_{n} with (y_{1}, …, y_{n}) ∈ ℕ^{n}. It is known that for all N sufficiently large a solution vector (y_{1}, …, y_{n}) ∈ ℕ^{n} exists. Following [4] and [3] we denote by g(a_{1}, …, a_{n}) or simply by g the largest integer N for which no such solution vector exists. In this paper we describe a procedure for general n to find g +1 which consists of finding the maximal element of a certain restricted set. Such maximality procedures are common in the literature, see [2],

[8] and [6]. The method we use is to find g from a finite set which is formed by using an infinite set H, see lemma 1. Our main observation is theorem 4 where we show that a finite subset E of H can be used for the same purpose. Our method also gives an upper bound for g which is in some cases comparable to the bounds given in [3]. For an extensive bibliography of the literature see Selmer’s paper [7].

2. Cut-off point for the General Case

2.1. Let W be the semigroup generated by a_{1}, …, a_{n} with (a_{1}, …, a_{n}) = ν. We order the elements of W in increasing order

W = {i_{0} = 0, i_{1}, i_{2}, … }.

It is a folk theorem that all sufficiently large multiples of ν are elements of W.^{1} For completeness we record two interesting proofs here.

Appeared in the Bulletin of the Technical University of İstanbul, vol: 39 (1986), 41-51.

In this retyping all the known typos are corrected. All the footnotes are added during this retyping.

1We thank Richard A. Smith of Honolulu for sending in a correction in 2004.

Theorem: For r sufficiently large we have

i_{r+l} = i_{r} + lν, l ∈ ℕ.

Proof I: (Arf [A]) Let ν_{l} = (i_{1}, …, i_{l}), l = 1, 2, …, Since ν_{l} divides ν_{l−1} for all l > 1, there exists q such that

ν_{q} = ν_{q+1} = ⋯ = ν.

Write

ν = m_{1}i_{1} + ⋯ + m_{q}i_{q} with m_{1}, …, m_{q} ∈ ℤ

and let

m = max | m_{h}(\frac{i_{1}}{ν} − 1) |
1 ≤ h ≤ q.

Now it is claimed that all the multiples of ν that are greater than

i = mi_{1} + ⋯ + mi_{q}

are in W.

First observe that i itself is a multiple of ν. Multiples for ν larger than i are of the form i + lν for l ∈ ℕ. We look at three cases.

I) l = 0, 1, …, \frac{i_{1}}{ν} − 1.

i + lν = (m + lm_{1})i_{1} + ⋯ + (m + lm_{q})i_{q} = n_{1}i_{1} + ⋯ + n_{q}i_{q} where n_{h} ∈ ℕ since m ≥ |m_{h}l|. Hence i + lν ∈ W.

II) l = \frac{i_{1}}{ν}.

i + lν = i + i_{1} which is clearly in W.

III) l > \frac{i_{1}}{ν}. Then l = s\frac{i_{1}}{ν} + t, 0 ≤ t < \frac{i_{1}}{ν},

i + ν = i + si_{1} + tν, and this is also in W due to the considerations in I and II above.

Proof II: Write

ν = m_{1}a_{1} + ⋯ + m_{n}a_{n}  (∗)

and let

−N = sum of negative terms in (∗)
P = sum of positive terms in (∗)

ON A DIOPHANTINE PROBLEM OF FROBENIUS 3

Note N ≥ 0, P > 0. We thus have ν = −N + P, where each of N and P are non-negative linear combinations of a_{1}, a_{2}, …, a_{n}.

Let M = (a_{1} − 1)N.
Then M + ν = (a_{1} − 2)N + P
M + 2ν = (a_{1} − 3)N + 2P
⋯
M + (a_{1} − 1)ν = 0 + (a_{1} − 1)P.

Thus each of M, M + ν, M + 2ν, …, M + (a_{1} − 1)ν are non-negative linear combinations of a_{1}, a_{2}, …, a_{n} and therefore so is M + kν, for all integers k ≥ 0. 2.2. Upper Bound. We assume that the integers a_{1}, …, a_{n} satisfy the conditions

(a_{1}, …, a_{n}) = 1 and 1 < a_{1} < ⋯ < a_{n}.

Define the following sets:

H = {(x_{1}, …, x_{n}) ∈ ℤ^{n} | a_{1}x_{1} + ⋯ + a_{n}x_{n} = −1}
A = {(y_{1}, …, y_{n}) ∈ ℕ^{n} | ∀(x_{1}, …, x_{n}) ∈ H, ∃i s.t. y_{i} + x_{i} < 0}

and

S = {n ∈ ℕ | ∃(y_{1}, …, y_{n}) ∈ A s.t. n = a_{1}y_{1} + ⋯ + a_{n}y_{n}}

where ℤ is the set of integers and ℕ is the set of non-negative integers. Lemma 1:

g = (max_{n∈S} n) − 1.

Before giving a proof let us develop some notation which will be used throughout;

π_{N} is the plane defined by a_{1}x_{1} + ⋯ a_{n}x_{n} = N, i.e. π_{N} = {(X_{1}, …, X_{n}) ∈ ℝ^{n} | a_{1}X_{1} + ⋯ + a_{n}X_{n} = N}. L_{N} is the lattice on π_{N}, L_{N} = π_{N} ∩ ℤ^{n}, and L_{N}^{+} is the part that lies in the first quadrant, L_{N}^{+} = L_{N} ∩ ℕ^{n}.

Proof of Lemma: It is clear that A ⊂ ⋃_{N≥0} L_{N}^{+}. In fact A ∩ L_{N}^{+} ≠ ∅ iff L_{N}^{+} ≠ ∅ and L_{N−1}^{+} = ∅; If L_{N−1}^{+} ≠ ∅ then let q ∈ L_{N−1}^{+} and p ∈ A ∩ L_{N}^{+}. Then q − p ∈ H and p+(q −p) ∈ ℕ^{n} contradicting the fact that p ∈ A. Now g +1 ∈ S. If N > g +1 is also in S then L_{N−1}^{+} = ∅ contradicting the definition of g. Hence the lemma. Remark: An alternate description of H can be given for any fixed point p ∈ L_{N} for any N,

H = {q − p | q ∈ L_{N−1} }.

This alternate description disposes of the unpleasant possibility of having two different points p, p′ ∈ L_{N}^{+} such that p ∈ A but p′ ∉ A; If p′ ∉ A then ∃q′ ∈ L_{N−1}^{+},^{2} but x = q′ − p′ + (p′ − p) ∈ H and p + x ∈ L_{N−1}^{+} contrary to p ∈ A. In order to describe a procedure of employing the lemma in calculating g, we give a decomposition of H which will facilitate our work; Let

H = H_{1} ∪ ⋯ ∪ H_{n} ∪ H′

where H_{i} = {(x_{1}, …, x_{n}) ∈ H | x_{i} < 0 and x_{j} ≥ 0 for j ≠ i } for i = 1, …, n and H′ consists of those vectors of H which have at least two negative entries.

For i = 1, …, n, choose a vector (x_{i1}, …, x_{in}) ∈ H_{i} such that^{3}

−x_{ii} = min{ |x_{i}| | (x_{1}, …, x_{n}) ∈ H_{i} }.

Let (y_{1}, …, y_{n}) ∈ A be such that

g + 1 = a_{1}y_{1} + ⋯ + a_{n}y_{n}.

Then in particular we have

y_{1} + x_{11} < 0
⋮
y_{n} + x_{nn} < 0

This proves the following

Lemma 2: With (x_{11}, …, x_{1n}), …, (x_{n1}, …, x_{nn}) chosen as above, we have

g ≤ a_{1}(−x_{11} − 1) + ⋯ + a_{n}(−x_{nn} − 1) − 1.

Example A: a_{1} = 137, a_{2} = 251, a_{3} = 256.

(x_{11}, x_{12}, x_{13}) = (−11, 6, 0)
(x_{21}, x_{22}, x_{23}) = (20, −15, 4)
(x_{31}, x_{32}, x_{33}) = (6, 11, −14)
g + 1 ≤ 137(10) + 251(14) + 256(13) = 8212.

Erdös and Graham give the following bounds, see [3];

g ≤ (a_{1} − 1)(a_{n} − 1) − 1 = 34679
g ≤ a_{3}a_{1} + a_{3} \frac{(a_{1}, a_{2}, a_{3})}{(a_{1}, a_{2})} = 35328
g ≤ 2a_{n−1} [\frac{a_{n}}{n} ] − a_{n} = 42414.

2i.e. L_{N−1}^{+} ≠ ∅ so pick any q′ there.

3Note that only the i-th entry is negative in H_{i} and x_{ii} is the largest of the negative entries, hence |x_{ii}| = −x_{ii} is minimum.

2.3. Sufficiency. We now aim towards our main result that a certain subset of H suffices for the above computations. To be more specific we need the following subset of H;

E = {(x_{1}, …, x_{n}) ∈ H | |x_{i}| < a_{1}, i = 2, …, n }.

Similar to the decomposition of H we decompose E

E = E_{1} ∪ ⋯ E_{n} ∪ E′

where E′ = E ∩ H′, E_{i} = E ∩ H_{i}, i = 1, …, n.

The following lemma establishes the fact that the x_{ii}, defined through H_{i}, can be defined using only E_{i}, i = 1, …, n.

Lemma 3:^{4}

−x_{ii} = min{ |x_{i}| | (x_{1}, …, x_{n}) ∈ E_{i} }, i = 1, …, n.

Proof: Assume that (x_{i1}, …, x_{in}) ∉ E_{i}.^{5} We distinguish two cases according to i = 1 or not.

Case 1: i = 1, (x_{11}, …, x_{1n}) ∉ E_{1}, then x_{1j} ≥ a_{1} for some j > 1. Notice that x_{11} + a_{j} < 0 since

−1 = (a_{1}, …, a_{n})(x_{11}, …, x_{1n})
= (a_{1}, …, a_{n})(x_{11} + a_{j}, x_{12}, …, x_{1j} − a_{1}, …, x_{1n})

and the LHS being negative, all the entries on the right hand side cannot be nonnegative. hence x_{11} + a_{j} < 0. But then (x_{11} + a_{j}, x_{12}, …, x_{1j} − a_{1}, …, x_{1n}) ∈ H_{1} and the minimality of x_{11} is contradicted. Therefore (x_{11}, …, x_{1n}) ∈ E_{1}. Case 2: ^{6} Subcase 2.1: x_{ii} ≤ −a_{1}.^{7} Let (y_{1}, …, y_{n}) ∈ E_{i} with −y_{i} = min{|x_{i}| | (x_{1}, …, x_{n}) ∈ E_{i} }. Then clearly −a_{1} < y_{i} ≤ x_{ii} < 0. Hence this subcase is not possible. Subcase 2.2: x_{ij} ≥ a_{1} for some i ≠ j, j = 2, …, n. Let x_{ir} = K_{r}a_{1} + u_{r} where K_{r} ≥ 0, 0 ≤ u_{r} < a_{i}, i ≠ r, r = 2, …, n. If we denote

u_{1} = x_{i1} + K_{2}a_{2} + ⋯ + K_{i−1}a_{i−1} + K_{i+1}a_{i+1} + ⋯ + K_{n}a_{n}

then

(u_{1}, u_{2}, …, u_{i−1}, x_{ii}, u_{i+r}, …, u_{n}) ∈ E_{i}.

This shows that the vector (x_{11}, …, x_{nn}) which is defined using H_{1}, …, H_{n} can instead be defined using only E_{1}, …, E_{n}.^{8}

4The claim is that −x_{ii}, which was chosen by the same minimality condition in H_{i}, can also be found by restricting our attention to the smaller set E_{i}.

5We assume that (x_{i1}, …, x_{in}) is in H_{i} but not in E_{i}.

6Now we set i to a number larger than 1.

7i.e. |x_{ii}| ≥ a_{1}, which is one reason why the definition of a vector belonging to E_{i} may be violated.

8We have actually shown that even if the vector (x_{i1}, …, x_{ii}, …, x_{in}) is not in E_{i}, another vector such as (u_{1}, …, u_{i−1}, x_{ii}, u_{i+1}, …, u_{n}) which is constructed above can be shown to be in E_{i}. Hence the number x_{ii} can be obtained from the set E_{i}.

We have shown the sufficiency of E_{1}, …, E_{n} in the above computations. To show the sufficiency of E in computing g we define the following sets

A_{E} = {(y_{1}, …, y_{n}) ∈ ℕ^{n} | ∀(x_{1}, …, x_{n}) ∈ E, ∃i s.t y_{i} + x_{i} < 0 }

and

S_{E} = {n ∈ ℕ | n = y_{1}a_{1} + ⋯ + y_{n}a_{n} for some (y_{1}, …, y_{n}) ∈ A_{E} }.

Our main observation is the following theorem.

Theorem 4:

g = (max_{n∈S_{E}} n) − 1.

Proof: It suffices to show that A = A_{E}. That A ⊆ A_{E} is trivial. To show the converse let (y_{1}, …, y_{n}) ∈ A_{E}. Assume that (y_{1}, …, y_{n}) ∉ A, then there exists (x_{1}, …, x_{n}) ∈ H such that x_{i} + y_{i} ≥ 0, i = 1, …, n. Note that in the light of lemma 3 if (y_{1}, …, y_{n}) ∈ A_{E} then y_{i} < −x_{ii}, i = 1, …, n and in particular for i = 2, …, n, we have y_{i} < a_{1}. Hence if x_{r} < 0 for r = 2, …, n then x_{r} + y_{r} ≥ 0 implies that |x_{r}| < a_{1}. Define a vector (u_{1}, …, u_{n}) ∈ E as follows. If x_{i} < 0 then let u_{i} = x_{i}, i ≠ 1. If x_{i} ≥ 0 and i ≠ 1 define u_{i} as x_{i} mod a_{1}, i.e.

x_{i} = k_{i}a_{1} + u_{i}, k_{i} ≥ 0, 0 ≤ u_{i} < a_{1}.

And for i = 1, u_{1} = x_{1} + k_{i_{1}}a_{i_{1}} + ⋯ + k_{i_{r}}a_{i_{r}} where x_{i_{1}}, …, x_{i_{r}} are those x_{i}’s , i ≠ 1, which are nonnegative. Then (u_{1}, …, u_{n}) ∈ E and clearly u_{i} + y_{i} ≥ 0 for i = 2, …, n. For i = 1, observe that x_{1} ≤ u_{1}, and if y_{1} + x_{1} ≥ 0, then y_{1} + u_{1} ≥ 0. But this contradicts the fact that (y_{1}, …, y_{n}) ∈ A_{E}. Hence (y_{1}, …, y_{n}) ∈ A.

Example B: a_{1} = 137, a_{2} = 251, a_{3} = 256. Start with the vector (10, 14, 13) = (−x_{11} − 1, −x_{22} − 1, x_{33} − 1), see example A. The only vectors in E′ that gives a nonnegative entry when added to (10, 14, 13) are (13, −2, −5), (−4, −7, 9) and (37, −10, −10). Thus we modify (10, 14, 13) so that when added to (13, −2, −5) it gives a negative entry and its dot product with (137, 251, 256) is maximal with this property. This gives us two candidates

U = (10, 1, 13), V = (10, 14, 4).

We modify these vectors with respect to (−4, −7, 9); U already gives negative entries when added to (−4, −7, 9) so does not change whereas V gives rise to two other candidates.

Z = (3, 14, 4), and W = (10, 6, 4).

These three vectors, U, Z, W now satisfy the required condition, i.e. they are in A_{E}, and

g + 1 = max_{n∈S_{E}} n = max_{n∈S_{{U,Z,W }}} n = max_{n∈{3900,4949}} n = 4949.

Examples A and B are worked with the aid of a computer.^{9}

Remark 1: A few words are in order to explain what we mean by “modification” of a vector (c_{1}, c_{2}, c_{3}) by (b_{1}, b_{2}, b_{3}) where (b_{1}, b_{2}, b_{3}) ∈ H and c_{1}, c_{2}, c_{3} ∈ ℕ. This particular process consists of carrying out the following algorithm and choosing all vectors satisfying the stated conditions;

9A friend of us did these calculations for us on the computer but we did not trust the machine and went over these calculations by hand. Then was the age of innocence!

1) If there is an i such that c_{i} + b_{i} < 0, then (c_{1}, c_{2}, c_{3}) remains unaltered.

2) If all c_{i} + b_{i} ≥ 0, then a) choose (−b_{1} − 1, c_{2}, c_{3}) if b_{1} < 0 and c_{1} + b_{1} ≥ 0.

b) choose (c_{1}, −b_{2} − 1, c_{3}) if b_{2} < 0 and c_{2} + b_{2} ≥ 0.

c) choose (c_{1}, c_{2}, −b_{3} − 1) if b_{3} < 0 and c_{3} + b_{3} ≥ 0.

Remark 2: In order to obtain E it suffices to find a basis for the lattice

L = {(y_{1}, …, y_{n}) ∈ ℤ^{n} | a_{1}y_{1} + ⋯ + a_{n}y_{n} = 0}.

For this purpose the following method seems appropriate; Let

1 = ∑_{i=1}^{n} m_{0i}a_{i},  d_{1} = ∑_{i=2}^{n} m_{1i}a_{i},
⋯  ⋯
d_{n−2} = ∑_{i=n−1}^{n} m_{n−2 i}a_{i},  d_{n−1} = a_{n}

be the greatest common divisors of the sets

{a_{1}, …, a_{n}}, {a_{2}, …, a_{n}}, …, {a_{n−1}, a_{n}}, {a_{n}}

respectively, where m_{ij} ∈ ℤ. Using this data, define the vectors

A_{1} = (d_{1}, −a_{1}m_{12}, −a_{1}m_{13}, …, −a_{1}m_{1n−1}, −a_{1}m_{1n})
A_{2} = (0, \frac{d_{2}}{d_{1}} , −\frac{a_{2}}{d_{1}} m_{23}, …, −\frac{a_{2}}{d_{1}} m_{2n−1}, −\frac{a_{2}}{d_{1}} m_{2n})
· · · · · ·
A_{n−1} = (0, …, 0, \frac{d_{n−1}}{d_{n−2}} , −\frac{a_{n−1}}{d_{n−2}} ).

These vectors constitute a basis for L. This construction does not produce unique A_{i}’s, however a canonical procedure for choosing m_{ij}’s can be given.

It is comforting to see that our method agrees with the classical result in case n = 2.

Corollary 5: When n = 2, g + 1 = a_{1}a_{2} − a_{1} − a_{2} + 1.

Proof: In this case

E_{1} = {(x_{11}, x_{12})}, E_{2} = {(x_{21}, x_{22})}, E′ = ∅.

And according to our method (−x_{11} − 1, −x_{22} − 1) ∈ A_{E} will give the maximal value, i.e.

g + 1 = a_{1}(−x_{11} − 1) + a_{2}(−x_{22} − 1)
= −a_{1}x_{11} − a_{1} − a_{2}x_{22} − a_{2}
= −a_{1}x_{11} − a_{1} − a_{2}(x_{12} − a_{1}) − a_{2}
= −(a_{1}x_{11} + a_{2}x_{12}) − a_{1} + a_{1}a_{2} − a_{2}
= 1 − a_{1} + a_{1}a_{2} − a_{2} as required.

Our method can also be used to find g in the special case of (m, m + 1, …, m + n − 1), see [5].

Corollary 6: Let a_{i} = m + i − 1, i = 1, …, n; n < m. Then

g + 1 = m\{\frac{m − 1}{n − 1}\}

where for r ∈ ℝ, {r} = k ∈ ℤ such that k − 1 < r ≤ k (Note that when r ∉ ℤ then {r} = [r] + 1, and when r ∈ ℤ then {r} = r).

Proof: We have

(1, −1, 0, …, 0) ∈ E_{2}, …, (0, …, 0, 1, −1) ∈ E_{n},

therefore x_{22} = ⋯ = x_{nn} = −1. If (y_{1}, …, y_{n}) ∈ A_{E} then 0 ≤ y_{i} < −x_{ii}, i = 1, …, n. Hence

y_{2} = ⋯ = y_{n} = 0.

We now know that g +1 is a multiple of a_{1}. The semigroup generated by a_{2}, …, a_{n} consists of the intervals ⋃[k(m + 1), k(m + n − 1)]. To find x_{11} we find the smallest multiple of m that comes close to the end of one of these intervals within a unit, i.e. find the smallest k such that

k(m + n − 1) − (k + 1)m ≥ −1.

This gives k ≥ \frac{m − 1}{n − 1}.

Then x_{11} = −\{\frac{m − 1}{n − 1} + 1\} and y_{1} = \{\frac{m − 1}{n − 1}\} as required.

Acknowledgments We thank professors C. Arf and T.C. Brown for valuable discussions.

References

[1] Arf, C., Une interprétation algébrique de la suite des ordres de multiplicité d’une branche algébrique, Proc. London Math. Soc., (2), 50, 256-287, (1949).

[2] Brauer, A. & J. E. Shockley, On a Problem of Frobenius, J. reine Angew. Math., 211, 215-220, (1962).

[3] Erdös, P. & R. L. Graham, On a Linear Diophantine Problem of Frobenius, Acta Arithmetica, XXI, 399-408, (1972).

[4] Johnson, S. M., A Linear Diophantine Problem, Canad. J. Math., 12, 390-398, (1960).

[5] Nijenhuis, A. & H. S. Wilf, Representations of Integers by Linear Forms in Nonnegative Integers, Journal of Number Theory, 4, 98-108, (1972).

[6] Rödseth, Ö. J., On a Linear Diophantine Problem of Frobenius, J. reine Angew. Math., 301, 178-271, (1978).

[7] Selmer, S., On the Linear Diophantine Problem of Frobenius, J. reine Angew. Math., 393/394, 1-17 (1977).

[8] Selmer, S. & Ö. Beyer, On the Linear Diophantine Problem of Frobenius in Three Variables, J. reine Angew. Math., 301, 161-170, (1970).

Received February 2, 1986

TÜBİTAK Research Institute for Basic Sciences, Department of Mathematics, P.O. Box 74 Gebze, Kocaeli, Turkey

Current address: Bilkent University, Department of Mathematics, 06533 Ankara,Turkey

E-mail address: sertoz@@fen.bilkent.edu.tr

TÜBİTAK Research Institute for Basic Sciences, Department of Mathematics, P.O. Box 74 Gebze, Kocaeli, Turkey, & Bosphorus University, Istanbul, Turkey

Current address: University of Maine, Department of Mathematics and Statistics, 5752 Neville Hall, Orona, Maine 04469-5752, USA

E-mail address: ozluk@@gauss.umemat.maine.edu