On Frobenius numbers in three variables
Except where reference is made to the work of others, the work described in this
dissertation is my own or was done in collaboration with my advisory committee. This
dissertation does not include proprietary or classified information.
Janet E. Trimm
Certificate of Approval:
Peter D. Johnson
Professor
Department of Mathematics and
Statistics
Overtoun Jenda, Chair
Professor
Department of Mathematics and
Statistics
Dean G. Hoffman
Professor
Department of Mathematics and
Statistics
Chris Rodger
Professor
Department of Mathematics and
Statistics
Stephen L. McFarland
Acting Dean
Graduate School
On Frobenius numbers in three variables
Janet E. Trimm
A Dissertation
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulfillment of the
Requirements for the
Degree of
Doctor of Philosophy
Auburn, Alabama
August 7, 2006
On Frobenius numbers in three variables
Janet E. Trimm
Permission is granted to Auburn University to make copies of this dissertation at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Dissertation Abstract
On Frobenius numbers in three variables
Janet E. Trimm
Doctor of Philosophy, August 7, 2006
(M.A.M, Auburn University, 2003)
(B.S., Rose-Hulman Institute of Technology, 2001)
49 Typed Pages
Directed by Overtoun M. G. Jenda
Given a set of relatively prime positive integers {a1,a2,...,an}, after some point all
positive integers are representable as a linear combination of the set with nonnegative
coefficients. Which integer is the last one not so representable is the Frobenius problem, or
the Frobenius stamp problem, and the number in question the Frobenius number of the set.
While the two-variable solution is widely known, and the general solution is NP-hard, there
have been several algorithmic solutions of the three-variable problem. Here we present a
new bound for the Frobenius number of most relatively prime triples.
iv
Acknowledgments
The author would like to thank her parents, Mickey and Greta Trimm, and her brother
Justin, for their support through this process as well as all the others she has gone through.
She would like to thank her fiance, Chris Dalzell, for his love and support as well.
Additionally, she would like to acknowledge the great inspiration and encouragement
that the faculty of the department of Mathematics and Statistics at Auburn has provided
throughout the years, particularly her committee.
The author would also like to thank Richard Russo for writing a computer program for
UNIX that efficiently computes Frobenius numbers, and Jennifer Clem for generating early
interesting patterns of these numbers. And it must be noted that the research experience
for undergraduates program run by Dr. Jenda and Dr. Johnson planted the seed for this
outcome.
v
Style manual or journal used Journal of Approximation Theory (together with the style
known as ?auphd?). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (specifically LATEX)
together with the departmental style-file auphd.sty.
vi
Table of Contents
1 Background 1
1.1 Sylvester and Frobenius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Algorithms for computing the Frobenius number in three variables . . . . . 2
1.2.1 R?odseth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Davison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 Kennedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 A preliminary result 9
3 Main Results 16
3.1 First Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.1 Part 1: n(ab?by) < ab?ax . . . . . . . . . . . . . . . . . . . . . . 18
3.1.2 Part 2: m(ab?ax) < ab?by . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Second Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1 Part 1: ab?ax < n(ab?by) . . . . . . . . . . . . . . . . . . . . . . 21
3.2.2 Part 2: ab?by < m(ab?ax) . . . . . . . . . . . . . . . . . . . . . . 23
4 Future Work 26
Bibliography 29
Appendices 30
A 11,30,k data set 31
B 28,57,k data set 34
C Notes on the style-file project 42
vii
Chapter 1
Background
Given a set of relatively prime positive numbers {a1,a2,...,an}, any integer after a
point is representable as a linear combination of the set using nonnegative integer coeffi-
cients. The last integer not representable as such a linear combination is called the Frobenius
number of the set and is denoted by g(a1,a2,...,an). The next number, the first of the
infinite sequence of representable integers, is called the conductor of the set and is denoted
?(a1,a2,...,an). That is, ?(a1,a2,...,an) = g(a1,a2,...,an) + 1.
The set of such linear combinations with nonnegative coefficients forms the monoid of
the set, sometimes also called the numeric semigroup of the set. Note that such a numeric
semigroup is generated by a1,a2,...,an and thus we will denote it by ?a1,a2,...,an?.
1.1 Sylvester and Frobenius
Given a pair of relatively prime integers a and b, what is the last integer not rep-
resentable in a and b? Two ready monetary applications have dubbed this problem the
?money-changing problem? or ?the stamp problem.? Given two values of coins or stamps a
and b, can we find a formula for computing the last number that is not representable as a
linear combination of a and b? In 1884, Sylvester [13] discovered a formula in for the case
of two relatively prime integers.
Theorem 1.1 Let a,b be relatively prime integers. Then the conductor of a and b is given
by ?(a,b) = (a?1)(b?1).
1
Finding formulas or algorithms for computing the conductor of a given set of n relatively
prime integers is often a difficult problem. Frobenius often referred to the general n-variable
problem in his lectures and it has since taken to be named after him.
The three-variable case is the next logical step to attempt to extend Sylvester?s result.
The following result of Johnson [8] shows that it suffices to consider variables that are
pairwise coprime.
Theorem 1.2 Let a,b,c be pairwise relatively prime and d be a positive common factor of
a and b. Then,
g(a,b,c) = d?gparenleftbigad, bd,cparenrightbig?c(d?1)
This result allows us to reduce all calculations to the pairwise coprime case. In addition,
one of the following algorithms [5] uses this result.
1.2 Algorithms for computing the Frobenius number in three variables
Through the years, there have been a number of algorithms developed that compute
the Frobenius number of three integers (see Johnson [8] Kennedy [9], Nijenhuis and Wilf
[10], R?odseth [11], Selmer and Beyer [12], and Wilf [14]). We now highlight a select number
of these.
1.2.1 R?odseth
Selmer and Beyer [12] used continuing fractions to formulate an algorithm for the Frobe-
nius number for three pairwise coprime positive integers. R?odseth [11] almost immediately
improved upon it as follows:
2
Step 1: Find s0 to satisfy the congruence
bs0 ? c (mod a), where 0 ? s0 < a.
Step 2: Use the Euclidean Algorithm in the form below:
a = q1s0 ?s1 0 ? s1 < s0
s0 = q2s1 ?s2 0 ? s2 < s1
... ...
sm?1 = qm+1sm ?sm+1 0 = sm+1 < sm
Step 3: Let P?1 = 0, P0 = 1, and
Pi+1 = qi+1Pi ?Pi?1 for i = 0,1,...,m.
Step 4: Let a = s?1, define s?1P?1 = ?, and find v, the unique integer satisfying
sv+1
Pv+1 ?
c
b <
sv
Pv.
Then,
g(a,b,c) = ?a + b(sv ?1) + c(Pv+1 ?1)?min{bsv+1,cPv}
Example: Let a = 11, b = 30, and c = 117.
Step 1: 30s0 ? 117 (mod 11) gives us s0 = 5.
Step 2:
11 =q1(5)?s1 q1 = 3 s1 = 4
5 =q2(4)?s2 q2 = 2 s2 = 3
4 =q3(3)?s3 q3 = 2 s3 = 2
3 =q4(2)?s4 q4 = 2 s4 = 1
2 =q5(1)?s5 q5 = 2 s5 = 0
3
Step 3: P?1 = 0, P0 = 1P1 = 3, P2 = 5, P3 = 7, P4 = 9, P5 = 11.
Step 4: s1P
1
= 43 < 11730 < 51 = s0P
0
, and so v = 0.
Then
g(11,30,117) = ?11 + 30(5?1) + 117(3?1)?min{30(4), 117(1)} = 226
1.2.2 Davison
The R?odseth [11] and Selmer-Beyer [12] algorithms were the word in the three-variable
problem for about ten years. Greenberg [7] found another algorithm in 1988, which was
rediscovered by Davison [5] in 1994. Davison?s algorithm finds a value f(a,b,c) such that
f(a,b,c) = g(a,b,c) + a + b + c as follows:
Step 0: Assume a < b < c. Find gcd(a,b,c). If gcd(a,b,c) negationslash= 1, then g(a,b,c) does not
exist.
Step 1: Find d12 = gcd(a,b), d13 = gcd(a,c), and d23 = gcd(b,c). Set aprime = ad12d13,
bprime = bd12d23, and cprime = cd13d23. f(a,b,c) = d12d13d23 ? f(aprime,bprime,cprime). Reorder and relabel aprime,bprime,cprime
to a < b < c.
Step 2: Solve bs ? c (mod a), where 0 < s < a.
Step 3: Perform the Euclidean algorithm on (s,a).
Step 4: Let r?1 = a, q?1 = 0, r0 = 1, and find k such that r2kq
2k
< cb < r2k?2q
2k?2
.
Step 5: Set ?(t) = r2k?2 ?tr2k?1q
2k?2 + tq2k?1
and find t? such that ?(t? < cb < ?(t? ? 1). The
bisection method is appropriate here, noting that ? is decreasing on [0,a].
Step 6: Set xprime = r2k?2 ?(t? ?1)r2k?1, yprime = q2k?2 +(t? ?1)q2k?1, xprimeprime = r2k?2 ?t?r2k?1,
and yprimeprime = q2k?2 + t?q2k?1. Then f(a,b,c) = max(bxprime + cq2k?1,br2k?1 + cyprimeprime).
4
Example: Using Davison?s algorithm on 11,30, and 117, we find the following:
Step 1: d12 = 1, d13 = 1, and d23 = 3. Thus aprime = 11, bprime = 10, and cprime = 39, and keeping in
mind d12d13d23 = 3, rename a = 10, b = 11, and c = 39.
Step 2: 11s ? 39 (mod 10) yields s = 9.
Step 3:
10 =q1(9) + r1 q1 = 1 r1 = 1
9 =q2(1)?r2 q2 = 9 r2 = 0
Step 4: bc = 3911 ? 3.55.
r0
q0 = 9, and
r2
q2 = 0, so k = 1.
Step 5: ?(t) = 9?t(1)1 + t . Using the bisection method, ?(2) = 7/3 and ?(1) = 4, so t? = 2.
Step 6: xprime = 9?(2?1)?1 = 8, xprimeprime = 9?2(1) = 7, yprime = 1+(2?1) = 2, and yprimeprime = 1+2(1) = 3.
So f(10,11,39) = max(11 ? 8 + 39 ? 1,11 ? 1 + 39 ? 3) = 128. Therefore f(11,30,117) =
3?f(10,11,39) = 384, and g(11,30,117) = f(11,30,117)?11?30?117 = 226.
1.2.3 Kennedy
Douglas Palmer Kennedy, in his masters? thesis [9], developed an algorithm for deter-
mining the Frobenius number of a triple {a,b,c}, where c = ab?ax?by, with a < b < c.
Step 1: For 0 ? i < a, find ?i and ?i such that ?(a,b) + i = ?ia + ?ib.
Step 2: Let ti range in the interval 0 ? ti ? ?(a,b)+ic , and find the integer kiti so that
riti??i+ti(b?x)
b ? kiti ?
?i?siti+tiy
a . riti and siti range as well.
Step 3: For each i and ti, find the maximal riti and siti satisfying the above inequality.
5
Step 4: Starting at i = 0, find the pair (r,s) such that ra + sb is maximal and exists
at all i.
Then ?(a,b,c) = ?(a,b)?ra?sb.
Example: Using Kennedy?s algorithm on 11,30, and 117, we let i range from 0 to 10.
The following values were obtained:
6
i ?i ?i ti kiti bound for (riti,siti)
0 10 6 0 0 (10,6)
1 1 (13,1)
1 21 2 0 0 (21,2)
2 2 9 0 0 (2,9)
1 1 (5,4)
3 13 5 0 0 (13,5)
1 1 (16,0)
4 24 1 0 0 (24,1)
2 1 (0,2)
5 5 6 0 0 (5,6)
1 1 (8,1)
6 16 4 0 0 (16,4)
7 27 0 0 0 (27,0)
1 0 (0,6)
2 1 (3,1)
8 8 7 0 0 (8,7)
1 1 (11,2)
9 19 3 0 0 (19,3)
10 0 10 0 0 (0,10)
1 1 (3,5)
2 2 (6,0)
7
The pair (r,s) that maximizes ra+sb at all i is (3,1). Thus ?(11,30,117) = 290?11?
3?30?1 = 227.
Since then, focus in the field has been concentrated on making algorithms faster, no-
tably Biehoffer et al. [4]. In addition, other algorithmic work has been done using generating
functions.
In spite of all these attempts, an explicit form for the Frobenius number for three
variables remains elusive. In the next chapter, we provide a formula for computing ?(a,b,c)
in terms of ?(a,b) for special sets of integers a,b,c.
8
Chapter 2
A preliminary result
In working with three variables, the obvious simplification is to refer to one variable in
terms of the other two.
This result from Brauer [1] makes that simplification possible:
Theorem 2.1 Given a relatively prime pair (a,b) and c not divisible by a or b , c is of
exactly one of the following forms: c = ax + by or c = ab?ax?by, with x,y > 0.
Proof: Let u be a solution of the congruence au ? c mod b so that 0 < u < b. Then
c = au + bv for some v ? Z, and v negationslash= 0. If v is positive, then c has the form ax + by with
x = u and y = v. If v is negative, then v = ?y for y > 0, and so
c =au + bv
=ab?a(b?u)?by
=ab?a(b?u)?by
So x = b?u, and c is of the form ab?ax?by.
c is not simultaneously representable in both forms. If it were, ab?ax?by = axprime+byprime,
where x,xprime,y,yprime > 0. So ab = a(x + xprime) + b(y + yprime). Therefore a|(y + yprime), which is not
possible, as (y + yprime) < a.
Starting with Brauer?s result we can show the following:
Lemma 2.2 Let a and b be relatively prime and c be a positive integer. If c = ab?ax?by
for some integers x,y > 0, c is not divisible by a or b.
9
Proof: First we note that since c > 0, ax < ab, so also is by < ab. Thus x < b and
y < a. If a|c, then ab ? ax ? by = ar for some integer r > 0. Therefore a(b ? x ? r) = by.
Since gcd(a,b) = 1, this means a|y. However, since a > y, this is a contradiction. Similarly,
if b|c, then ab ? ax ? by = sb for some integer s > 0, and so b(a ? y ? s) = ax. As a and b
are coprime, b|x, a contradiction since b > x. So c is not divisible by a or b.
This leads to our next conclusion:
Proposition 2.3 Let a and b be relatively prime and c be a positive integer. Then c /? ?a,b?
if and only if c = ab?ax?by for some integers x,y > 0.
Proof: If c /? ?a,b?, c is not divisible by a or b, so c = ab ? ax ? by for some integers
x,y > 0. If c = ab ? ax ? by for some integers x,y > 0, c is not divisible by a or b by the
above, and c negationslash= axprime + byprime by Theorem 2.1. So c /? ?a,b?.
The following two can be found in Kennedy:
Proposition 2.4 Let a and b be relatively prime and c be a positive integer. Then ?(a,b,c) =
?(a,b) if and only if c = ax + by for some x,y ? 0.
Proof: We first note that ?(a,b,c) ? ?(a,b). Now assume c = ax+by for some x,y ? 0.
Then ?(a,b)?1 = ua + vb + wc for some integers u,v,w ? 0. But then
?(a,b)?1 = ua + vb + wc
= ua + vb + w(ax + by)
= ra + sb
for some r,s ? 0, a contradiction. Hence ?(a,b,c) = ?(a,b). For the converse, suppose c
is not in the form ax + by for any x,y ? 0. Then by Proposition 2.3, c = ab ? ax ? by
10
for some x,y > 0. Furthermore ?(a,b) = ab ? a ? b + 1, so ?(a,b) ? 1 = ab ? a ? b =
ab ? ax ? by + ax ? a + by ? b = c + a(x ? 1) + b(y ? 1). But x ? 1,y ? 1 ? 0. So
?(a,b,c) ? ?(a,b)?1 < ?(a,b). Thus ?(a,b,c) negationslash= ?(a,b).
Proposition 2.5 Let a and b be relatively prime and c be a positive integer. Then ?(a,b,c) =
?(a,b)?ra?sb for some r,s ? 0.
Proof: We first note that ?(a,b,c)?1 /? ?a,b,c? and ?a,b? ? ?a,b,c?. So ?(a,b,c)?1 /? ?a,b?.
Therefore, ?(a,b,c)?1 = ab?ax?by for some x,y > 0, and so
?(a,b,c) = ab?ax?by + 1
= ?(a,b) + a + b?ax?by
= ?(a,b)?(x?1)a?(y ?1)b.
The last result is notably only an existence proof. The real problem is finding the
appropriate coefficients r and s so that ?(a,b,c) = ?(a,b)?ra?sb.
Looking at the Frobenius numbers of all triples {11,30,k}, where n is less than 330,
we noticed a pattern: for many triples, the difference in k was equal to the difference
in the Frobenius number of the triples. In fact, for some triples, ?(11,30,n + 11i) =
?(11,30,k)+11i, and for others, ?(11,30,n+30j) = ?(11,30,n)+30j. Further examination
led to the formulation of the following:
Theorem 2.6 Let a and b be relatively prime and c be any positive integer. Then
1. c ? ?a,b? if and only if ?(a,b,c) = ?(a,b)
2. c /? ?a,b? if and only if c = ab?ax?by for some x,y > 0. In this case,
11
(a) if ax < by and 0 < y ? floorlefta/2floorright, then ?(a,b,c) = ?(a,b)?ax
(b) if ax > by and 0 < x ? floorleftb/2floorright, then ?(a,b,c) = ?(a,b)?by.
Proof: (1) follows from Proposition 2.4 while the first part of (2) follows from Propo-
sition 2.3.
If c /? ?a,b?, then c = ab ? ax ? by by Brauer [1]. Conversely, if c = ab ? ax ? by and
a|c, then a|y since a and b are relatively prime, a contradiction since y < a. Similarly, c is
not divisible by b. So c /? ?a,b? again by Brauer [1].
We now assume the first part of (2) and argue that if ax < by and 0 < y ? floorlefta/2floorright then
?(a,b,c) = ?(a,b)?ax.
Suppose ?(a,b,c) < ?(a,b)?ax. Then ?(a,b)?ax?1 = ra+sb+t(ab?ax?by) for some
r,s,t ? 0 where c = ab?ax?by. Note that t > 0 since otherwise ?(a,b)?1 = (r+x)a+sb,
a contradiction.
Suppose t is even. Then ?(a,b) ? 1 = (r + x + t2(b ? 2x))a + (s + t2(a ? 2y))b. But
y ? a2 and so x ? b2 since ax < by. Thus ?(a,b)?1 ? ?a,b?, a contradiction.
Now suppose t is odd. Then
?(a,b)?1 = (r + x + t?12 (b?2x))a + (s + t?12 (a?2y))b + 12(b?2x)a + 12(a?2y)b
= (r + x + t?12 (b?2x))a + (s + t?12 (a?2y))b + c
Define u and v as follows:
u = r + x + t?12 (b?2x)
v = s + t?12 (a?2y)
12
So
c = ab?a?b?ua?vb
= ab?(u + 1)a?(v + 1)b
Therefore u + 1 = x since c = ab ? ax ? by uniquely. That is, r + t?12 (b ? 2x) + 1 = 0, a
contradiction since t > 0 and 2x ? b. Thus ?(a,b,c) ? ?(a,b)?ax.
Suppose now that ?(a,b,c) > ?(a,b)?ax. By Kennedy [9], ?(a,b,c) = ?(a,b)?ra?sb
for some r,s ? 0. So ?(a,b)?ra?sb > ?(a,b)?ax, and so ra+sb < ax. Thus r < x and
since ax < by, s < y.
We know that ?(a,b)?ra?sb?1 is not in ?a,b,c?. But
?(a,b)?ra?sb?1 = ab?a?b?ra?sb
= ab?ax?by + ax + by ?a?b?ra?sb
= c + (x?r ?1)a + (y ?s?1)b.
But x ? r ? 1 ? 0, and y ? s ? 1 ? 0, so c + (x ? r ? 1)a + (y ? s ? 1)b ? ?a,b,c?, a
contradiction. Thus ?(a,b,c) ? ?(a,b)?ax, and so ?(a,b,c) = ?(a,b)?ax.
Now we assume the second part of (2) and argue if ax > by and 0 < x ? floorleftb/2floorright, then
?(a,b,c) = ?(a,b)?by
Suppose ?(a,b,c) < ?(a,b)?by. Then ?(a,b)?by?1 = ra+sb+tc for some r,s,t ? 0.
Again, note that t > 0, because otherwise ?(a,b)?1 ? ?a,b?, a contradiction.
Suppose t is even. Then ?(a,b) ? 1 = (r + t2(b ? 2x))a + (s + y + t2(a ? 2y))b. Since
x ? b/2 and by < ax, then also y ? a/2, and ?(a,b)?1 ? ?a,b?, a contradiction.
13
Now suppose t is odd. Then
?(a,b)?1 = (r + t?12 (b?2x))a + (s + y + t?12 (a?2y))b + 12(b?2x)a + 12(a?2y)b
= (r + t?12 (b?2x))a + (s + y + t?12 (a?2y))b + c
Define u and v as follows:
u = r + t?12 (b?2x)
v = s + y + t?12 (a?2y)
So ?(a,b)?1 = ab?a?b = ua+vb+c, and so c = ab?a?b?ua?vb = ab?(u+1)a?(v+1)b.
But c = ab?ax?by uniquely by Brauer [1]. So v+1 = y, or equivalently,s+t?12 (a?2y)+1 =
0. As s ? 0, t > 0 and a > 2y, this is a contradiction. Thus ?(a,b,c) ? ?(a,b)?by.
Suppose now that ?(a,b,c) > ?(a,b) ? by. By 2.5, we know that ?(a,b,c) = ?(a,b) ?
ra?sb for some r,s ? 0, and so ?(a,b)?ra?sb > ?(a,b)?by. So ra+sb < by, so s < y,
and since by < ax, r < x. We know that ?(a,b)?ra?sb?1 is not in ?a,b,c?. But
?(a,b)?ra?sb?1 = ab?a?b?ra?sb
= ab?ax?by + ax + by ?a?b?ra?sb
= c + (x?r ?1)a + (y ?s?1)b.
Since x?r?1 ? 0 and y?s?1 ? 0, ?(a,b,c)?1 = c+(x?r?1)a+(y?s?1)b ? ?a,b,c?,
a contradiction. Thus ?(a,b,c) ? ?(a,b)?by, and so ?(a,b,c) = ?(a,b)?by.
14
Example: Let a = 11, b = 30 and c = 152. Then the solution to 30q = 152(mod 11)
is q = 8. But then bq > c and so c /? ?11,30?. Now ab ? c = 330 ? 152 = 178, and solving
30y = 178(mod 11) gives y = 3 and so x = 178?30(3)11 = 8. Thus, by = 90 > 88 = ax and
y = 3 < floorleft112 floorright. Hence, ?(11,30,152) = ?(a,b) ? ax = 29 ? 10 ? 11 ? 8 = 202 by the theorem
above.
The condition 0 < y ? floorlefta2floorright is necessary. For let c = 117 and a, b be as in the above.
Then 117 = 330?213 = 330?11?3?30?6 and so x = 3 and y = 6. We note that ax < by
and y = 6 > floorlefta2floorright. And ?(11,30) ? ax = 290 ? 33 = 257 negationslash= 227 = ?(11,30,117). In fact,
?(11,30,117) = ?(11,30)?11?3?30?1.
Remark 2.7 Let T = N? < a,b > and R = {c ? T : 0 < x ? floorleftb2floorright and 0 < y ? floorlefta2floorright}.
Then |R| ? (a?1)2 ? (b?1)2 = 14(a ? 1)(b ? 1). But |T| = 12?(a,b) by Sylvester 1.1. So
|R| ? 12|T|. That is, the formula above calculates ?(a,b,c) for at least half of the elements
in T. Moreover, if c ? T ?R and c < a or c < b, then ?(a,b,c) may be calculated using the
theorem above. Consequently the theorem calculates ?(a,b,c) for a much larger number
of elements c in T. For example, in the example above, let c = 6. Then 6 ? T ? R and
clearly 30 ?< 11,6 >. So ?(30,11,6) = ?(11,6) = 50 by the theorem. Similarly, let
c = 20. Then 20 ? T and 20 = 330 ? 30(3) ? 11(20) and so x = 3 and y = 20. But
y = 20 > floorlefta2floorright = 15 and so 20 ? T ? R. If we now let a = 11,b = 20 and c = 30,
then gcd(11,20) = 1 and 30 negationslash?< 11,20 >. Furthermore, 30 = 220 ? (11)(10) ? (20)(4)
and so x = 10 and y = 4. Thus ax = 110 > 80 = by and x = 10 ? floorleft202 floorright. Hence
?(30,11,20) = ?(11,20)?(20)(4) = 190?80 = 110 by the theorem.
15
Chapter 3
Main Results
Lemma 3.1 If n = ceilingleft ya?yceilingright and n(ab?by) < ab?ax, then y ? ann+1 and x ? bn+1.
Proof: By the definition of n, n ? ya?y. Further,
n(a?y) ? y
an?ny ? y
an ? (n + 1)y
an
n + 1 ? y
Because of this, and because n(ab?by) < ab?ax,
ax < ab?nab + nby
? ab?nab + nb ann + 1
ax ? abn + 1
x ? bn + 1
Lemma 3.2 If m = ceilingleft xb?xceilingright and m(ab?ax) < ab?by, then x ? bmm+1 and y ? am+1.
16
Proof: By the definition of m, m ? xb?x. Further,
m(b?x) ? x
mb?mx ? x
mb ? (m + 1)x
mb
m + 1 ? x
Because of this, and because m(ab?ax) < ab?by,
by < ab?mab + max
? ab?mab + mb bmm + 1
by ? abm + 1
y ? am + 1
3.1 First Result
Theorem 3.3 Let a,b,c be relatively prime and let c = ab ? ax ? by. If n = ceilingleft ya?yceilingright and
m = ceilingleft xb?xceilingright, then
?(a,b,c) ?
??
???
????
?(a,b)?nax, if n(ab?by) < ab?ax;
?(a,b)?mby, if m(ab?ax) < ab?by.
(3.1)
We will prove this in parts:
17
3.1.1 Part 1: n(ab?by) < ab?ax
We assume the condition in the first part, and argue that ?(a,b,c) = ?(a,b)?nax.
First we suppose not, and look for a contradiction. If given the above condition,
?(a,b,c) < ?(a,b)?nax, then ?(a,b)?nax?1 is in the monoid ?a,b,c?. So ?(a,b)?nax?1 =
ra + sb + tc for nonnegative r,s,t.
This can be rewritten ?(a,b)?1 = ra+nax+sb+tc. Since we know for certain that
the left-hand side of the last is not in the monoid ?a,b?, we know that t is positive.
Now there are multiple possibilities, based on the relationship between t and n.
If n+1 > t, then ?(a,b)?1 = ra+nax?tax+sb+tab?tby. This can be rewritten
as ?(a,b)?1 = a(r +x(n?t))+b(s+t(a?y)). Since (n?t) is nonnegative, as is (a?y),
this is a contradiction. So t ? n + 1.
So now we suppose that n + 1 divides t. This divisibility allows us to break up the
term tc as follows:
parenleftbigg t
n + 1
parenrightbigg
ab +
parenleftbigg nt
n + 1
parenrightbigg
ab?tax?tby.
This means that ?(a,b)?1 = ra + nax +
parenleftbigg t
n + 1
parenrightbigg
ab?tax + sb +
parenleftbigg nt
n + 1
parenrightbigg
ab?tby.
Grouping like terms gives us
?(a,b)?1 = a
parenleftbigg
r + nx +
parenleftbigg t
n + 1
parenrightbigg
(b?(n + 1)x)
parenrightbigg
+ b
parenleftbigg
s +
parenleftbigg t
n + 1
parenrightbigg
(na?(n + 1)y)
parenrightbigg
Since y < nan + 1 and x < bn + 1, by 3.1 this is a contradiction. So (n + 1) does not
divide t.
Since (n + 1) does not divide t, Euler says that t = (n + 1)q + p for some 0 < p ? n.
With this form, we know that (n + 1) does divide (t?p).
We then take the equation we had before, and regroup the terms thus: ?(a,b) ? 1 =
ra + nax + sb + (t?p)(ab?ax?by) + p(ab?ax?by).
18
And then dividing by (n + 1),
?(a,b)?1 = ra+nax+( t?pn+1)(ab?(n+1)ax)+sb+( t?pn+1)(nab?(n+1)by)+p(ab?ax?by)
If we let u := r + nx + ( t?pn+1)(b ? (n + 1)x), and v := s + ( t?pn+1)(na ? (n + 1)y), then
?(a,b)?1 = ua + vb + pc. By the same lemmas as above, u ? 0 and v ? 0.
Suppose a or b divides p. Then ?(a,b)?1 ? ?a,b?, a contradiction.
So, since ?(a,b) = ab?a?b+1, ab?a?b = ua+vb+pc, or pc = ab?(u+1)?(v+1).
And as neither a or b divides p, this is unique by Brauer.
However, pc = pab?pax?pby.
Rearranging this, pc = ab?pax?b(py ?(p?1)a).
We know that y > (n?1)an from the definition of n. As n ? p, y > p?1p a. The coefficient
on b is therefore nonnegative. This is also unique, therefore there must be equality:
ab?pax?b(py ?(p?1)a) = ab?(u + 1)a?(v + 1)b, and so u + 1 = px.
r + nx + ( t?pn+1)(b?(n + 1)x) + 1 = px. Rewrite to read as follows:
r+(n?p)x+( t?pn+1)(b?(n+1)x)+1 = 0. As the three terms added to 1 are nonnegative,
this is a contradiction.
No t exists such that ?(a,b)?nax?1 = ra + sb + tc, so ?(a,b,c) ? ?(a,b)?nax
3.1.2 Part 2: m(ab?ax) < ab?by
This follows similarly to Part 1. We assume m(ab?ax) < ab?by and argue ?(a,b,c) =
?(a,b)?mby.
First we assume not. Suppose ?(a,b,c) < ?(a,b) ? mby. Then ?(a,b) ? mby + 1 =
ra+sb+tc for some r,s,t ? 0. Note that t > 0 since otherwise ?(a,b)?1 = ra+sb+mby,
a contradiction, as ?(a,b)?1 /? ?a,b?.
19
The rest follows based on the relationship between m and t. Suppose m + 1 > t.
?(a,b)?1 = ra + sb + t(ab?ax?by) + mby
= ra + sb + ta(b?y) + by(m?t)
As b > y and m ? t, this implies ?(a,b)?1 ? ?a,b?, a contradiction. So t ? m + 1.
Suppose (m + 1)|t. Then ?(a,b) ? 1 = ra + sb + tm + 1(ab) + mtm + 1(ab) ? tax ? tby.
Rearranging, the following is evident:
?(a,b)?1 = a(r + tm+1(mb?x(m + 1))) + b(s + my + tm+1(a?y(m + 1)))
As m ? xb?x, and y ? am + 1 by 3.2 ?(a,b) ? 1 ? ?a,b?, a contradiction. So m + 1 does
not divide t.
So then t = (m+1)q+p for some positive q and 0 < p ? m. Therefore, (m+1)|(t?p).
Still, ?(a,b)?1 = ra + sb + mby + t(ab?ax?by). Using the above divisibility,
?(a,b)?1 = ra + sb + (t?p)c + pc
= a(r + t?pm + 1(mb?(m + 1)x)) + b(s + my + t?pm + 1(a?(m + 1)y)) + pc
For conciseness? sake, define
u = r + t?pm + 1(mb?(m + 1)x)
v = s + my + t?pm + 1(a?(m + 1)y)
So ?(a,b)?1 = ua+vb+pc. If a or b divides p, then ?(a,b)?1 ? ?a,b?, a contradiction. So
pc = ab?a?b?ua?vb, and by Brauer [1], this is unique. But also pc = pab?pax?pby,
20
which can be written pc = ab ? a(px ? (p ? 1)b) ? pby. Since m(ab ? ax) < ab ? by,
x > b(m?1)m > b(p?1)p , this is also unique, and so the two are equal, and so v + 1 = py.
So s + (m ? p)y + t?pm+1(a ? (m + 1)y) + 1 = 0. As y ? am+1, this is a contradiction. So
?(a,b,c) ? ?(a,b)?mby.
3.2 Second Result
Theorem 3.4 Let a,b,c be relatively prime and let c = ab ? ax ? by. If n = ceilingleft ya?yceilingright,
m = ceilingleft xb?xceilingright, then
?(a,b,c) ?
??
???
????
?(a,b)?(n?1)ax?(a?n(a?y))b, if ab?ax < n(ab?by) and x ? bn+1;
?(a,b)?(m?1)by ?(b?m(b?x)a, if ab?by < m(ab?ax) and y ? am+1.
(3.2)
3.2.1 Part 1: ab?ax < n(ab?by)
First we suppose not, and look for a contradiction. If given the above conditions,
?(a,b,c) < ?(a,b)?(n?1)ax?(a?n(a?y))b, then ?(a,b)?(n?1)ax?(a?n(a?y))b =
ra + sb + tc for some r,s ? 0, and t ? 1.
Thus ?(a,b)?1 = ra + (n?1)ax + sb + (a?n(a?y))b + t(ab?ax?by).
If t < n, then the above can be rewritten thus: ?(a,b) ? 1 = a(r + (n ? 1)x ? tx) +
b(s + (a?n(a?y)) + t(a?y)), a contradiction. So t ? n
The expression can be expanded thus: ?(a,b)?1 = ra+nax?ax+sb+ab?nab+nby+tc,
or ?(a,b)?1 = ra+ab?ax+sb+(t?n)c. If t = n, then ?(a,b)?1 = a(r+(b?x))+sb,
a contradiction. So t negationslash= n, and so t > n, or t ? n + 1.
21
Suppose (n+1)|t. Then ?(a,b)?1 = ra+(n?1)ax+
parenleftbigg t
n + 1
parenrightbigg
(b?(n+1)x)a+sb+
(a?n(a?y))b +
parenleftbigg t
n + 1
parenrightbigg
(na?(n + 1)y)b, a contradiction. So n + 1 does not divide t.
As t ? (n + 1) and n + 1 does not divide t, t = (n + 1)q + p for some p ? n, and so
(n + 1)|(t?p).
Therefore ?(a,b)?1 = ra+(n?1)ax+sb+(a?n(a?y))b+(t?p)(ab?ax?by)+pc.
As (n + 1)|(t ? p), this can be rewritten as ?(a,b) ? 1 = ra + (n ? 1)ax + sb + (a ? n(a ?
y))b +
parenleftbiggt?p
n + 1
parenrightbigg
a(b?(n + 1)x) +
parenleftbiggt?p
n + 1
parenrightbigg
b(na?(n + 1)y) + pc.
For conciseness, define u and v as follows:
u =
bracketleftbigg
r + (n?1)x +
parenleftbiggt?p
n + 1
parenrightbigg
(b?(n + 1)x)
bracketrightbigg
v =
bracketleftbigg
s + (a?n(a?y)) +
parenleftbiggt?p
n + 1
parenrightbigg
(na?(n + 1)y)
bracketrightbigg
This way ?(a,b) ? 1 = ab ? a ? b = ua + vb + pc. If a|p or b|p, this is a contradiction.
Otherwise, pc = ab?(u + 1)a?(v + 1)b, which is unique by Brauer.
But pc = p(ab?ax?by) = ab?pax?b(py?(p?1)a), which is also unique by Brauer. So
px = u+1 and py?(p?1)a = v+1. Therefore
bracketleftbigg
r + (n?1)x +
parenleftbiggt?p
n + 1
parenrightbigg
(b?(n + 1)x)
bracketrightbigg
+
1?px = 0, or,
bracketleftbigg
r + (n?1?p)x +
parenleftbiggt?p
n + 1
parenrightbigg
(b?(n + 1)x)
bracketrightbigg
+1 = 0. If p ? (n?1), this is
a contradiction.
If p = n, look at the b coefficients:
py ?(p?1)a =
bracketleftbigg
s + (a?n(a?y)) +
parenleftbiggt?p
n + 1
parenrightbigg
(na?(n + 1)y)
bracketrightbigg
+ 1
bracketleftbigg
s + (a?n(a?y)) +
parenleftbiggt?p
n + 1
parenrightbigg
(na?(n + 1)y)
bracketrightbigg
+ (p?1)a?py + 1 = 0
22
, or, since p = n,
s +
parenleftbiggt?p
n + 1
parenrightbigg
(na?(n + 1)y) + 1 =0.
As s and
parenleftBig
t?p
n?1
parenrightBig
(na?(n+1)y) are both nonnegative, this is a contradiction, and ?(a,b,c) ?
?(a,b)?(n?1)ax?(a?n(a?y))b.
3.2.2 Part 2: ab?by < m(ab?ax)
Suppose that ?(a,b,c) < ?(a,b) ? (m ? 1)by ? (b ? m(b ? x))a. Then ?(a,b) ? (m ?
1)by ? (b ? m(b ? x))a ? 1 = ra + sb + tc for some r,s ? 0 and t ? 1, as in the previous
cases. Rearranging, we get
?(a,b)?1 = [r + b?m(b?x)]a + [s + (m?1)y]b + t(ab?ax?by) (3.3)
If t < m, the above can be rewritten thus: ?(a,b)?1 = a[r+(b?m(b?x))+t(b?x)]+
b[s+(m?1)y ?ty], and the coefficients on a and b are both nonnegative, a contradiction.
So t ? m.
The above inequality 3.3 can be expanded like this:
?(a,b)?1 = ra + ab?mab + max + sb + mby ?by + tc
= ra + sb + (a?x)b + (t?m)c
If m = t, this is a contradiction. So t > m, or equivalently, t ? m + 1.
Suppose (m + 1)|t. Then inequality 3.3 can be written thus:
?(a,b)?1 = [r+(b?m(b?x))+ tm+1(mb?(m+1)x)]a+[s+(m?1)y+ tm+1(a?(m+1)y)]b
23
As each coefficient is a nonnegative integer, this is a contradiction. So (m + 1) does not
divide t.
So t = (m+1)q+p for some positive q and 0 < p ? m. Therefore (m+1)|(t?p). And
so ?(a,b)?1 = ra + (b?m(b?x))a + sb + (m?1)by + (t?p)(ab?ax?by) + pc
= a[r +(b?m(b?x))+ t?pm+1(mb?(m+1)x)]+b[s+(m?1)y + t?pm+1(a?(m+1)y)]+pc.
Assign u and v the following values:
u = r + (b?m(b?x)) + t?pm + 1(mb?(m + 1)x)
v = s + (m?1)y + t?pm + 1(a?(m + 1)y)
And so ?(a,b)?1 = ua + vb + pc. If a|p or b|p, this is a contradiction. By Theorem 1.1,
pc = ab?a?b?ua?vb = ab?(u + 1)a?(v + 1)b,
and by Theorem 2.1, this is unique.
But pc = p(ab ? ax ? by) = ab ? a(px ? (p ? 1)b) ? pby. As x ? (m?1)bm ? (p?1)bp , the
coefficients on a and b are positive integers, and so this also is unique. So the two can be
equated, v + 1 = py, or
s + (m?1)y + t?pm + 1(a?(m + 1)y) + 1 = py
s + (m?1)y ?py + t?pm + 1(a?(m + 1)y) + 1 = 0
s + (m?1?p)y + t?pm + 1(a?(m + 1)y) + 1 = 0
24
If p < m, each term added to 1 is nonnegative, so the above is a contradiction. If
p = m, look instead at u + 1 = px?(p?1)b.
r + (b?m(b?x)) + t?pm + 1(mb?(m + 1)x) + 1 = mx?(m?1)b
r + (b?m(b?x))?mx + (m?1)b + t?pm + 1(mb?(m + 1)x) + 1 = 0
r + t?pm + 1(mb?(m + 1)x) + 1 = 0
As each of the above terms is nonnegative, and one is positive, this also is a contradiction.
Therefore there is no t so that ?(a,b)?(m?1)by?(b?m(b?x))a?1 = ra+sb+tc, and
?(a,b)?(m?1)by ?(b?m(b?x))a ? ?(a,b,c).
One should note that when n = m = 1, the above results reduce to the preliminary
result in Chapter 2.
25
Chapter 4
Future Work
The obvious place to start with future work is the attempt to show the previous results
hold with equality. The examples in Appendices A and B, as well as several others not
included here, support this conjecture.
Previous attempts have involved trying to find some number of c to add to the con-
jectured conductor that will result in the same sort of contradiction that served us in this
case in our preliminary result.
Ideas for further attempts involve reevaluating the formulation of the inequality, or
perhaps working strictly with x and y, and not m and n.
The following result of Brauer and Seelbinder [3] suggests that the previous results may
have some corollary in more than three dimensions. First, define T as follows:
Let d1 = a1,d2 = gcd(a1,a2),...,dk = gcd(a1,a2,...ak). Then
T = T(a1,a2,...,ak)
= a2d1d
2
+ a3d2d
3
+ ... akdk?1d
k
Theorem 4.1 Let a1,a2,...,ak be relatively prime positive integers. Then every integer m
is representable in at least one of the forms
1. m = a1x1 + a2x2 + ... + akxk (x? > 0for? = 1,2,...,k)
2. m = T ?a1x1 ?a2x2 ?...?akxk (x? ? 0for? = 1,2,...,k)
In the pairwise relatively prime case with four variables, T = ab + c.
26
In particular, let k = 4. Then one can show that ?(a,b,c,d) = ?(a,b) ? ra ? sb ? tc
for some r,s,t ? 0. One then can develop an algorithm as in Kennedy [9] to find r,s,t for
given pairwise nonnegative integers a,b,c,d.
Note that if d = ax + by + cz for some x,y,z ? 0 , then the monoid generated by
?a,b,c,d? is the same as the one generated by ?a,b,c? and so ?(a,b,c,d) = ?(a,b,c) and so
r = s = t = 0.
Now suppose d is not in ?a,b,c?, then
d = T ?ax?by ?cz
= ab + c?ax?by ?cz
= ab?ax?by ?c(z ?1)
If i ? 0, then ?(a,b) + i = ?ia + ?ib for some nonnegative integers ?i,?i. So
?(a,b)?ra?sb?tc + i = ?ia + ?ib?ra?sb?tc?wi + wid
= ?ia + ?ib?ra?sb?tc?wi(ab?ax?by ?c(z ?1)) + wid
= [?i ?r + wi(x?b) + kib]a + [?i ?s + wiy ?kia]b + [?t + wi(z ?1)]c + wid
where ki,wi are nonnegative integers.
So, at each i,wi, we would find riwi,siwi,tiwi so that there is an integer kiwi such that
r ??i + wi(b?x)
b ? kiwi ?
?i ?siwi + wiy
a
and tiwi ? wi(z ?1).
27
Then we proceed as in Kennedy [9] to find values for r,s, and t. This approach has
been demonstrated to work in some examples.
Note that the case z = 0 needs to be considered separately.
28
Bibliography
[1] A. Brauer, On a problem of partitions, Amer. J. Math. 64 (1942), 299-312.
[2] A. Brauer and B. M. Seelbinder, On a problem of partitions II, Amer. J. Math. 76
(1954), 343-346.
[3] A. Brauer and J. E. Shockley, On a problem of Frobenius, J. Reine Angew. Math. 211
(1962), 215-220.
[4] D. Beihoffer, J. Hendry, A. Nijenhuis, and S. Wagon; Faster Algorithms for Frobenius
Numbers, Elec. J. of Combinatorics. 12 (2005), #R27.
[5] J. L. Davison, On the Linear Diophantine Problem of Frobenius, Journal of Number
Theory, 48 (1994), 353-363.
[6] P. Erd?os and R. L. Graham, On a linear diophantine problem of Frobenius, Acta
Arithmetica 21 (1975), 400-407.
[7] H. Greenberg, Solution to a Linear Diophantine Equation for Nonnegative Integers,
Journal of Algorithms, 9 (1988), 343-353.
[8] S. M. Johnson, A Linear Diophantine Problem, Canadian J. Math. 12 (1960), 390-398.
[9] D. P. Kennedy, On the conductors of submonoids of the natural numbers, M.Sc. Thesis,
Auburn University, 1992.
[10] A. Nijenhuis and H. S. Wilf, Representations of Integers by Linear Forms in Nonneg-
ative Integers, Journal of Number Theory. 4 (1972), 98- 106.
[11] O. J. Rodseth, On a Linear Diophantine Problem of Frobenius, J. Reine Angew. Math.
310 (1978), 171-178.
[12] E. S. Selmer and O. Beyer, On the Linear Diophantine Problem of Frobenius in three
variables, J. Reine Angew. Math. 301 (1978), 161-170.
[13] J. J. Sylvester, Mathematical Questions, with their solutions, Educational Times 41
(1884), 21.
[14] H. S. Wilf, A circle-of-lights algorithm for the ?Money-changing problem?, Amer. Math.
Monthly, 85 (1978), 562-565.
29
Appendices
30
Appendix A
11,30,k data set
Remembering that ?(a,b,c) = ?(a,b) ? ra ? sb, we break down the following data as
follows:
x k
g(11,30,k)
r,s
y
Note that g(11,30) = 289.
31
10 19 8
179 69
10,0 20,0
9 49 38 27 16 5
234 179 127 83 39
5,0 10,0 12,1 16,1 20,1
8 79 68 57 46 35 24 13 2
256 223 190 157 124 97 75 9
3,0 6,0 9,0 12,0 15,0 12,2 14,2 20,2
7 109 98 87 76 65 54 43 32 21 10
267 245 223 201 179 157 135 113 100 89
2,0 4,0 6,0 8,0 10,0 12,0 14,0 16,0 9,3 10,3
6 139 128 117 106 95 84 73 62 51 40 29
267 245 226 215 204 193 182 171 160 149 108
2,0 4,0 3,1 4,1 5,1 6,1 7,1 8,1 9,1 10,1 11,2
5 169 158 147 136 125 114 103 92 81 70 59
278 267 256 245 234 223 212 201 190 179 168
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 11,0
4 199 188 177 166 155 144 133 122 111 100 89
278 267 256 245 234 223 212 201 190 179 169
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 0,4
3 229 218 207 196 185 174 163 152 141 130 119
278 267 256 245 234 223 212 201 199 199 199
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 0,3 0,3 0,3
2 259 248 237 226 215 204 193 182 171 160 149
278 267 256 245 234 229 229 229 229 229 229
1,0 2,0 3,0 4,0 5,0 0,2 0,2 0,2 0,2 0,2 0,2
1 289 278 267 256 245 234 223 212 201 190 179
278 267 259 259 259 259 259 259 259 259 259
1,0 2,0 0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1
1 2 3 4 5 6 7 8 9 10 11
32
6 18 7
97 45
12,2 13,3
5 48 37 26 15 4
157 146 139 139 29
12,0 13,0 0,5 0,5 11,5
4 78 67 56 45 34 23 12 1
169 169 169 169 125 95 73 -1
0,4 0,4 0,4 0,4 4,4 4,5 6,5
3 108 97 86 75 64 53 42 31 20 9
199 199 199 199 177 155 133 111 109 46
0,3 0,3 0,3 0,3 2,3 4,3 6,3 8,3 0,6 3,7
2 138 127 116 105 94 83 72 61 50 39
229 229 229 229 207 185 169 169 169 136
0,2 0,2 0,2 0,2 2,2 4,2 0,4 0,4 0,4 3,4
1 168 157 146 135 124 113 102 91 80 69
259 259 259 259 237 229 229 229 229 199
0,1 0,1 0,1 0,1 2,1 0,2 0,2 0,2 0,2 0,3
12 13 14 14 15 16 17 18 19 20
2 28 17 6
109 87 49
0,6 2,6 0,8
1 58 47 36 25 14 3
199 177 169 139 137 19
0,3 2,3 0,4 0,5 2,6 0,9
21 22 23 24 25 26
33
Appendix B
28,57,k data set
Remembering that ?(a,b,c) = ?(a,b) ? ra ? sb, we break down the following data as
follows:
x k
g(28,57,k)
r,s
y
Note that g(28,57) = 1511.
34
27 29 1
755 -1
27,0
26 86 58 30 2
1147 783 419 55
13,0 26, 0 39,0 52,0
25 143 115 87 59 31 3
1259 1007 782 558 334 53
9,0 18,0 24,1 32,1 40,1 48,2
24 200 172 144 116 88 60 32 4
1343 1175 1007 839 671 503 335 167
6,0 12,0 18,0 24,0 30,0 36,0 42,0 48,0
23 257 229 201 173 145 117 89 61 33 5
1371 1231 1091 951 811 671 556 444 332 79
5,0 10,0 15,0 20,0 25,0 30,0 28,3 32,3 36,3 43,4
22 314 286 258 230 202 174 146 118 90 62 34
1399 1287 1175 1063 951 839 727 615 527 443 359
4,0 8,0 12,0 16,0 20,0 24,0 28,0 32,0 27,4 30,4 33,4
21 371 343 315 287 259 231 203 175 147 119 91
1427 1343 1259 1175 1091 1007 923 839 755 671 587
3,0 6,0 9,0 12,0 15,0 18,0 21,0 24,0 27,0 30,0 33,0
20 428 400 372 344 316 288 260 232 204 176 148
1427 1343 1259 1175 1091 1007 923 839 779 723 667
3,0 6,0 9,0 12,0 15,0 18,0 21,0 24,0 18,4 20,4 22,4
19 485 457 429 401 373 345 317 289 261 233 205
1427 1343 1286 1230 1174 1118 1062 1006 950 894 838
3,0 6,0 6,1 8,1 10,1 12,1 14,1 16,1 18,1 20,1 22,1
18 542 514 486 458 430 402 374 346 318 290 262
1455 1399 1343 1287 1231 1175 1119 1063 1007 951 895
2,0 4,0 6,0 8,0 10,0 12,0 14,0 16,0 18,0 20,0 22,0
17 599 571 543 515 487 459 431 403 375 347 319
1455 1399 1343 1287 1231 1175 1119 1063 1007 951 895
2,0 4,0 6,0 8,0 10,0 12,0 14,0 16,0 18,0 20,0 22,0
16 656 628 600 572 544 516 488 460 432 404 376
1455 1399 1343 1287 1231 1175 1119 1063 1031 1003 975
2,0 4,0 6,0 8,0 10,0 12,0 14,0 16,0 9,4 10,4 11,4
15 713 685 657 629 601 573 545 517 489 461 433
1455 1399 1343 1287 1257 1229 1201 1173 1145 1117 1089
2,0 4,0 6,0 8,0 5,2 6,2 7,2 8,2 9,2 10,2 11,2
14 770 742 714 686 658 630 602 574 546 518 490
1483 1455 1427 1399 1371 1343 1315 1287 1259 1231 1203
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 11,0
1 2 3 4 5 6 7 8 9 10 11
35
22 6
107
42,4
21 63 35 7
503 419 335
36,0 39,0 42,0
20 120 92 64 36 8
611 555 499 359 191
24,4 26,4 28,4 33,4 39,4
19 177 149 121 93 65 37 9
782 726 670 557 501 388 161
24,1 26,1 28,1 30,2 32,2 34,3 36,6
18 234 206 178 150 122 94 66 38 10
839 783 727 671 615 579 551 523 159
24,0 26,0 28,0 30,0 32,0 17,8 18,8 19,8 32,8
17 291 263 235 207 179 151 123 95 67 39 11
839 805 777 749 721 693 665 637 468 356 159
24,0 13,6 14,6 15,6 16,6 17,6 18,6 19,6 23,7 27,7 32,8
16 348 320 292 264 236 208 180 152 124 96 68
947 919 891 863 835 807 779 751 639 527 439
12,4 13,4 14,4 15,4 16,4 17,4 18,4 19,4 23,4 27,4 22,8
15 405 377 349 321 293 265 237 209 181 153 125
1061 1033 1005 977 949 921 893 865 753 695 667
12,2 13,2 14,2 15,2 16,2 17,2 18,2 19,2 23,3 21,4 22,4
14 462 434 406 378 350 322 294 266 238 210 182
1175 1147 1119 1091 1063 1035 1007 979 951 923 895
12,0 13,0 14,0 15,0 16,0 17,0 18,0 19,0 20,0 21,0 22,0
12 13 14 15 16 17 18 19 20 21 22
16 40 12
383 215
24,8 27,10
15 97 69 41 13
611 497 357 185
24,4 24,6 29,6 27,10
14 154 126 98 70 42 14
867 839 811 783 755 727
23,0 24,0 25,0 26,0 27,0 28,0
23 24 25 26 27 28
36
13 827 799 771 743 715 687 659 631 603 575 547
1483 1455 1427 1399 1371 1343 1315 1287 1259 1231 1203
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 11,0
12 884 856 828 800 772 744 716 688 660 632 604
1483 1455 1427 1399 1371 1343 1315 1287 1259 1231 1203
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 11,0
11 941 913 885 857 829 801 773 745 717 689 661
1483 1455 1427 1399 1371 1343 1315 1287 1259 1231 1203
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 11,0
10 998 970 942 914 886 858 830 802 774 746 718
1483 1455 1427 1399 1371 1343 1315 1287 1259 1231 1203
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 11,0
9 1055 1027 999 971 943 915 887 859 831 803 775
1483 1455 1427 1399 1371 1343 1315 1287 1259 1231 1203
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 11,0
8 1112 1084 1056 1028 1000 972 944 916 888 860 832
1483 1455 1427 1399 1371 1343 1315 1287 1259 1231 1203
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 11,0
7 1169 1141 1113 1085 1057 1029 1001 973 945 917 889
1483 1455 1427 1399 1371 1343 1315 1287 1259 1231 1203
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 11,0
6 1226 1198 1170 1142 1114 1086 1058 1030 1002 974 946
1483 1455 1427 1399 1371 1343 1315 1287 1259 1231 1203
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 11,0
5 1283 1255 1227 1199 1171 1143 1115 1087 1059 1031 1003
1483 1455 1427 1399 1371 1343 1315 1287 1259 1231 1226
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,0 10,0 0,5
4 1340 1312 1284 1256 1228 1200 1172 1144 1116 1088 1060
1483 1455 1427 1399 1371 1343 1315 1287 1283 1283 1283
1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 0,4 0,4 0,4
3 1397 1369 1341 1313 1285 1257 1229 1201 1173 1145 1117
1483 1455 1427 1399 1371 1343 1340 1340 1340 1340 1340
1,0 2,0 3,0 4,0 5,0 6,0 0,3 0,3 0,3 0,3 0,3
2 1454 1426 1398 1370 1342 1314 1286 1258 1230 1202 1174
1483 1455 1427 1399 1397 1397 1397 1397 1397 1397 1397
1,0 2,0 3,0 4,0 0,2 0,2 0,2 0,2 0,2 0,2 0,2
1 1511 1483 1455 1427 1399 1371 1343 1315 1287 1259 1231
1483 1455 1454 1454 1454 1454 1454 1454 1454 1454 1454
1,0 2,0 0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1
1 2 3 4 5 6 7 8 9 10 11
37
13 519 491 463 435 407 379 351 323 295 267 239
1175 1147 1119 1091 1063 1035 1007 979 951 923 895
12,0 13,0 14,0 15,0 16,0 17,0 18,0 19,0 20,0 21,0 22,0
12 576 548 520 492 464 436 408 380 352 324 296
1175 1147 1119 1091 1063 1035 1007 979 951 923 895
12,0 13,0 14,0 15,0 16,0 17,0 18,0 19,0 20,0 21,0 22,0
11 633 605 577 549 521 493 465 437 409 381 353
1175 1147 1119 1091 1063 1035 1007 979 951 923 895
12,0 13,0 14,0 15,0 16,0 17,0 18,0 19,0 20,0 21,0 22,0
10 690 662 634 606 578 550 522 494 466 438 410
1175 1147 1119 1091 1063 1035 1007 979 951 941 941
12,0 13,0 14,0 15,0 16,0 17,0 18,0 19,0 20,0 0,10 0,10
9 747 719 691 663 635 607 579 551 523 495 467
1175 1147 1119 1091 1063 1035 1007 998 998 998 998
12,0 13,0 14,0 15,0 16,0 17,0 18,0 0,9 0,9 0,9 0,9
8 804 776 748 720 692 664 636 608 580 552 524
1175 1147 1119 1091 1063 1055 1055 1055 1055 1055 1055
12,0 13,0 14,0 15,0 16,0 0,8 0,8 0,8 0,8 0,8 0,8
7 861 833 805 777 749 721 693 665 637 609 581
1175 1147 1119 1112 1112 1112 1112 1112 1112 1112 1112
12,0 13,0 14,0 0,7 0,7 0,7 0,7 0,7 0,7 0,7 0,7
6 918 890 862 834 806 778 750 722 694 666 638
1175 1169 1169 1169 1169 1169 1169 1169 1169 1169 1169
12,0 0,6 0,6 0,6 0,6 0,6 0,6 0,6 0,6 0,6 0,6
5 975 947 919 891 863 835 807 779 751 723 695
1226 1226 1226 1226 1226 1226 1226 1226 1226 1226 1226
0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5
4 1032 1004 976 948 920 892 864 836 808 780 752
1283 1283 1283 1283 1283 1283 1283 1283 1283 1283 1283
0,4 0,4 0,4 0,4 0,4 0,4 0,4 0,4 0,4 0,4 0,4
3 1089 1061 1033 1005 977 949 921 893 865 837 809
1340 1340 1340 1340 1340 1340 1340 1340 1340 1340 1340
0,3 0,3 0,3 0,3 0,3 0,3 0,3 0,3 0,3 0,3 0,3
2 1146 1118 1090 1062 1034 1006 978 950 922 894 866
1397 1397 1397 1397 1397 1397 1397 1397 1397 1397 1397
0,2 0,2 0,2 0,2 0,2 0,2 0,2 0,2 0,2 0,2 0,2
1 1203 1175 1147 1119 1091 1063 1035 1007 979 951 923
1454 1454 1454 1454 1454 1454 1454 1454 1454 1454 1454
0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1 0,1
12 13 14 15 16 17 18 19 20 21 22
38
13 211 183 155 127 99 71 43 15
867 839 811 783 770 770 574 209
23,0 24,0 25,0 26,0 0,13 0,13 7,13 18,14
12 268 240 212 184 156 128 100 72 44 16
867 839 827 827 827 827 743 575 407 239
23,0 24,0 0,12 0,12 0,12 0,12 3,12 9,12 15,12 21,12
11 325 297 269 241 213 185 157 129 101 73 45
884 884 884 884 884 884 828 716 604 492 380
0,11 0,11 0,11 0,11 0,11 0,11 2,11 6,11 10,11 14,11 18,11
10 382 354 326 298 270 242 214 186 158 130 102
941 941 941 941 941 941 885 773 687 631 575
0,10 0,10 0,10 0,10 0,10 0,10 2,10 6,10 5,12 7,12 9,12
9 439 411 383 355 327 299 271 243 215 187 159
998 998 998 998 998 998 970 914 858 802 746
0,9 0,9 0,9 0,9 0,9 0,9 1,9 3,9 5,9 7,9 9,9
8 496 468 440 412 384 356 328 300 272 244 216
1055 1055 1055 1055 1055 1055 1027 971 915 859 803
0,8 0,8 0,8 0,8 0,8 0,8 1,8 3,8 5,8 7,8 9,8
7 553 525 497 469 441 413 385 357 329 301 273
1112 1112 1112 1112 1112 1112 1084 1028 972 916 860
0,7 0,7 0,7 0,7 0,7 0,7 1,7 3,7 5,7 7,7 9,7
6 610 582 554 526 498 470 442 414 386 358 330
1169 1169 1169 1169 1169 1169 1141 1085 1029 973 917
0,6 0,6 0,6 0,6 0,6 0,6 1,6 3,6 5,6 7,6 9,6
5 667 639 611 583 555 527 499 471 443 415 387
1226 1226 1226 1226 1226 1226 1198 1142 1086 1030 974
0,5 0,5 0,5 0,5 0,5 0,5 1,5 3,5 5,5 7,5 9,5
4 724 696 668 640 612 584 556 528 500 472 444
1283 1283 1283 1283 1283 1283 1255 1199 1143 1087 1055
0,4 0,4 0,4 0,4 0,4 0,4 1,4 3,4 5,4 7,4 0,8
3 781 753 725 697 669 641 613 585 557 529 501
1340 1340 1340 1340 1340 1340 1312 1256 1200 1169 1169
0,3 0,3 0,3 0,3 0,3 0,3 1,3 3,3 5,3 0,6 0,6
2 838 810 782 754 726 698 670 642 614 586 558
1397 1397 1397 1397 1397 1397 1369 1313 1283 1283 1283
0,2 0,2 0,2 0,2 0,2 0,2 1,2 3,2 0,4 0,4 0,4
1 895 867 839 811 783 755 727 699 671 643 615
1454 1454 1454 1454 1454 1454 1426 1397 1397 1397 1397
0,1 0,1 0,1 0,1 0,1 0,1 1,1 0,2 0,2 0,2 0,2
23 24 25 26 27 28 29 30 31 32 33
39
11 17
291
11,16
10 74 46 18
519 351 209
11,12 17,12 18,14
9 131 103 75 47 19
690 634 578 522 485
11,9 13,9 15,9 17,9 0,18
8 188 160 132 104 76 48 20
747 691 635 599 599 431 263
11,8 13,8 15,8 0,16 0,16 6,16 12,16
7 245 217 189 161 133 105 77 49 21
804 748 713 713 713 629 545 461 377
11,7 13,7 0,14 0,14 0,14 3,14 6,14 9,14 12,14
6 302 274 246 218 190 162 134 106 78 50 22
861 827 827 827 827 743 659 575 491 429 231
11,6 0,12 0,12 0,12 0,12 3,12 6,12 9,12 12,12 2,18 5,20
5 359 331 303 275 247 219 191 163 135 107 79
941 941 941 941 941 857 773 689 656 628 516
0,10 0,10 0,10 0,10 0,10 3,10 6,10 9,10 0,15 1,15 5,15
4 416 388 360 332 304 276 248 220 192 164 136
1055 1055 1055 1055 1055 971 887 827 827 799 687
0,8 0,8 0,8 0,8 0,8 3,8 6,8 0,12 0,12 1,12 5,12
3 473 445 417 389 361 333 305 277 249 221 193
1169 1169 1169 1169 1169 1085 1001 998 998 970 858
0,6 0,6 0,6 0,6 0,6 3,6 6,6 0,9 0,9 1,9 5,9
2 530 502 474 446 418 390 362 334 306 278 250
1283 1283 1283 1283 1283 1199 1169 1169 1169 1141 1055
0,4 0,4 0,4 0,4 0,4 3,4 0,6 0,6 0,6 1,6 0,8
1 587 559 531 503 475 447 419 391 363 335 307
1397 1397 1397 1397 1397 1340 1340 1340 1340 1312 1283
0,2 0,2 0,2 0,2 0,2 0,3 0,3 0,3 0,3 1,3 0,4
34 35 36 37 38 39 40 41 42 43 44
40
5 51 23
404 259
9,15 4,20
4 108 80 52 24
599 543 403 287
0,16 2,16 7,16 3,20
3 165 137 109 81 53 25
827 771 656 572 403 286
0,12 2,12 0,15 3,15 1,18 1,21
2 222 194 166 138 110 82 54 26
1055 999 941 857 799 685 515 315
0,8 2,8 0,10 3,10 1,12 1,14 3,16 2,10
1 279 251 223 195 167 139 111 83 55 27
1283 1227 1226 1169 1141 1084 998 885 742 485
0,4 2,4 0,5 0,6 1,6 1,7 0,9 2,10 1,13 0,18
45 46 47 48 49 50 51 52 53 54
41
Appendix C
Notes on the style-file project
These style-files for use with LATEX are maintained by Darrel Hankerson1 and Ed
Slaminka2.
In 1990, department heads and other representatives met with Dean Doorenbos and
Judy Bush-Crofton (then responsible for manuscript approval). This meeting was prompted
by a memorandum3 from members of the mathematics departments concerning the Thesis
and Dissertation Guide and the approval process. There was wide agreement among the
participants (including Dean Doorenbos) to support the basic recommendations outlined in
the memorandum. The revised Guide reflected some (but not all) of the agreements of the
meeting.
Ms Bush-Crofton was supportive of the plan to obtain ?official approval? of these style
files.4 Unfortunately, Ms Bush-Crofton left the Graduate School before the process was
completed. In 1994, we find that we are returning to some of the same problems which were
resolved at the 1990 meeting.
In Summer 1994, I sent several memoranda to Ms. Ilga Trend of the Graduate School,
reminding her of the agreements made at the 1990 meeting. Professors A. Scottedward
Hodel and Stan Reeves provided additional support. In short, it is essential that the Grad-
uate School honor its commitments of the 1990 meeting. It should be emphasized that Dean
Doorenbos is to thank for the success of that meeting.
Maintaining these LATEX files has been more work than I expected. If the Graduate
School rejects your manuscript based on items controlled by the style-files, please contact
Darrel Hankerson or Ed Slaminka so that we can coordinate an appropriate response.
Finally, there have been several requests for additions to the package (mostly formatting
changes for figures, etc.). While such changes are not really part of the thesis-style package,
it could be beneficial to collect these options and distribute with the package (making
it easier on the next student). I?m especially interested in changes needed by various
departments.
1Mathematics and Statistics, 221 Parker Hall, 844-3641, hankedr@auburn.edu
2Mathematics and Statistics, 218 Parker, slamiee@auburn.edu
3Originally, the memorandum was presented to Professor Larry Wit. A copy is available on request.
4Followup memoranda gave a definition of ?official approval.? Copies will be sent on request.
42