%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-30/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}
%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}
\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}
%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
\gdef\@thm@name{#3}%
\@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
\edef\@currentlabel{\@thm@name}%
\label{#1}\endgroup
}
\makeatother
% end lift
\newtheoremstyle{namedthrm}
{}{}{}{}{}{}{ } % This last space needs to be there
{\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack
%% Document start
\date{}
\begin{document}
%% Content start
\title{A Remark Related to the Frobenius Problem}
\author{
Tom C. Brown\footnote{Department of Mathematics and Statistics, Simon Fraser University, Burnaby, British Columbia, V5A 1S6, Canada. \texttt{tbrown@sfu.ca}} and
Peter Jau-shyong Shiue\footnote{Department of Mathematical Sciences, University of Nevada, Las Vegas, NV, USA 89154-4020. \texttt{shiue@nevada.edu}}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown} and P.J.-S. {Shiue}, \emph{A remark related to the {Frobenius}
problem}, Fib. Quart. \textbf{31} (1993), 32--36.}\bigskip\end{center}
The Frobenius problem \cite{brauer1942,frobenius1912} is to find, for a given
set $a_1,\ldots,a_m$ of relatively prime integers, the largest number which is
\emph{not} a linear combination of $a_1,\ldots,a_m$ with nonnegative integer
coefficients.
Given a set $a_1,\ldots,a_m$ of relatively prime positive integers, let us
agree to call a number \emph{representable} if it is a linear combination
of $a_1,\ldots,a_m$ with nonnegative integer coefficients; otherwise we
call it \emph{nonrepresentable}.
The fact that every sufficiently large positive integer is representable
(given relatively prime $a_1,\ldots,a_m$) has been rediscovered many times,
and makes a good exercise in a course in elementary number theory.
The Frobenius probelm has a long history. (See \cite{selmer1977} for
a list of references.) In 1884, J. J. Sylvester \cite{sylvester1884}
completely solved the problem for $m=2$. He found that if $a$ and $b$
are positive integers such that $(a,b) = 1$, then every $n\geq(a-1)(b-1)$
can be expressed in the form $n = xa + by$ where $x,y$ are nonnegative
integers, and $ab - a - b$ cannot be so expressed. That is, the largest
nonrepresentable number in this case is $ab - a - b$. Sylvester also
found that among the $(a-1)(b-1)$ numbers $0,1,2,\ldots,ab-a-b$,
exactly half are representable and half are nonrepresentable.
When $m = 3$, no closed-form expression for the largest nonrepresentable
number is known (except in some special cases), although there do exist
algorithms for calculating it.
In the general case, various upper bounds are known for the largest
nonrepresentable number, and closed-form expressions are known in a few
special cases, for example, in the case that $a_1,\ldots,a_m$ are in
arithmetic progression \cite{bateman1958,roberts1957}.
In this note we consider an aspect of the case $m=2$ which seems not
to have been examined previously. We start by defining two notations.
For given $a,b$ with $(a,b) = 1$, let $\NR(a,b)$ denote the \emph{set}
of numbers nonrepresentable in terms of $a,b$. Thus, $\NR(a,b)$ is the
set of all those nonnegative integers $n$ which \emph{cannot} be
expressed in the form $n = ax + by$, where $x,y$ are nonnegative
integers. Let
\[ S(a,b) = \sum\{n:n\in \NR(a,b) \} \]
equal the \emph{sum} of the numbers nonrepresentable in terms of $a$
and $b$.
Although Sylvester showed that exactly $\frac12(a-1)(b-1)$ of the numbers
$0,1,2,\ldots,ab-a-b$ are nonrepresentable, that is that
\[ |\NR(a,b)| = \frac12(a-1)(b-1), \]
additional information about the nonrepresentable would be provided by an
estimate of their sum $S(a,b) = \sum\{n:n\in \NR(a,b) \}$.
A crude upper bound for $S(a,b)$ is obtained by taking the sum of the
$\frac12(a-1)(b-1)$ largest integers in the interval $[0,ab-a-b]$.
Similarly, a crude lower bound is obtained by taking the sum of the
$\frac12(a-1)(b-1)$ smallest integers in the interval $[0,ab-a-b]$.
This gives
\[ \frac18(a-1)^2(b-1)^2 - \frac14(a-1)(b-1) \leq S(a,b) \leq \frac38(a-1)^2(b-1)^2 - \frac14(a-1)(b-1), \]
an upper bound of order $\frac38(ab)^2$ and a lower bound of order
$\frac18(ab)^2$.
C. W. Ho, J. L. Parish, \& P. J. Shiue \cite{ho+parish+shiue1991}
found that if $A$ is any finite set of nonnegative integers such
that the complement of $A$ (in the set of nonnegative integers)
is closed under addition, then $\sum\{n:n\in A\}\leq|A|^2$. Since
the sum of two representable numbers is certainly a representable
number, we can take $\NR(a,b)$ in the place of $A$, and obtain
\[ S(a,b) = \sum\{n:n\in \NR(a,b) \} \leq |\NR(a,b)|^2 = \frac14(a-1)^2(b-1)^2 \]
an upper bound for $S(a,b)$ of order $\frac14(ab)^2$, which considerably
improves the previous upper bound.
In this note we find that, in fact,
\[ S(a,b) = \frac1{12}(a-1)(b-1)(2ab - a - b - 1), \]
so that the exact order of $S(a,b)$ is $\frac16(ab)^2$.
For example, when $a = 4$, $b = 7$, the nonrepresentable numbers are 1, 2, 3,
5, 6, 9, 10, 13, and 17, which sum to
\[ S(4,7) = 66 = \frac1{12}(4-1)(7-1)(56-4-7-1). \]
For the remainder of the paper, $a$, $b$ are fixed positive integers with
$(a,b) = 1$.
To calculate $S(a,b)$, we use the following idea:
For each $n\geq0$, let $r(n)$ be the \emph{number} of representations of $n$
in the form $n = sa + tb$, where $s,t$ are nonnegative integers. That is, $r(n)$
is the number of ordered pairs $(s,t)$ such that $n = sa + tb$.
For example, $r(ab) = 2$, since if $ab = sa + tb$, then $(a,b)=1$ implies
that $a$ divides $t$ and $b$ divides $s$, so that the only possibilities
for $(s,t)$ are $(b,0)$ and $(0,a)$.
It is not hard to see that if $0\leq n \leq ab - 1$, then either $r(n) = 0$
or $r(n) = 1$. For suppose that $r(n)\geq2$ and that $n = s_1a + t_1b = s_2a
+ t_2b$ where (without loss of generality) $s_1>s_2$. Then $0 = (s_1-s_2)a
+ (t_1-t_2)b$. Therefore, $b$ divides $s_1-s_2$, so $s_1\geq b$ and $n\geq ab$.
Now, we define
\[ f(x) = \sum_{n=0}^{ab-a-b}[1 - r(n)]x^n. \]
Using the fact that $r(n) = 0$ or $r(n) = 1$ for $0\leq n\leq ab-1$, we obtain
\begin{align*}
f'(1)
&= \sum_{n=1}^{ab-a-b}n[1 - r(n)] = \sum\{n:1\leq n\leq ab-a-b\text{ and }r(n) = 0\} \\
&= \sum \{n: n\in \NR(a,b)\} = S(a,b).
\end{align*}
Thus, the problem of finding $S(a,b)$ has been reduced to calculating $f'(1)$.
It will turn out that
\[ f(x) = \frac{P(x) - 1}{x-1}, \text{ where } P(x) = \frac{(x^{ab}-1)(x-1)}{(x^a-1)(x^b-1)}. \]
This remarkably simple formula for $f(x)$ was discovered by Ali Ozluk, and
appears in a more general setting (using $a_1,\ldots,a_m$ instead of $a,b$)
in a paper by Ozluk \& Sertoz \cite{sertoz+ozluk1986}. For our case of $m=2$,
the calculations can be done as follows.
Let
\[ A(x) = 1/(1-x^a)(1 - x^b) = \left(\sum_{n=0}^\infty x^{an}\right)\left(\sum_{n=0}^\infty x^{bn}\right) = \sum_{n=0}^\infty r(n)x^n. \]
Now, since $(a,b) = 1$, it follows that
\[ P(x) = \frac{(x^{ab}-1)(x-1)}{(x^a-1)(x^b-1)} \]
is a polynomial, with leading coefficient 1. (This can be seen by factoring
both the numerator and denominator into complex linear factors. Since $(a,b)=1$,
there are integers $s$, $t$ such that $as + bt = 1$. Let $\zeta$ be any complex
number such that both $\zeta^a = 1$ and $\zeta^b = 1$; then $\zeta = \zeta^1
= \zeta^{as + bt} = (\zeta^a)^s(\zeta^b)^t = 1$. In other words, no linear
factor [except for $(x-1)$] appears twice in the denominator of $P(x)$;
hence, every factor in the denominator cancels against a linear factor in the
numerator.)
Since $P(1) = 1$ by l'Hospital's rule, we have that $\frac{P(x)-1}{x-1}$ is
also a polynomial, of degree $ab-a-b$, with leading coefficient 1.
Now we write,
\begin{align*}
\frac{P(x) - 1}{x-1}
&= \frac{P(x)}{x-1} + \frac1{1-x} = (x^{ab} - 1)A(x) + \frac1{1-x} \\
&= \sum_{n=0}^\infty r(n)x^{ab+n} + \sum_{n=0}^\infty[1-r(n)]x^n \\
&= \sum_{n=ab}^\infty[r(n-ab) + 1 - r(n)]x^n + \sum_{n=0}^{ab-1}[1-r(n)]x^n.
\end{align*}
Since we know that this power series is really a polynomial of degree $ab-a-b$
with leading coefficient 1, we can deduce that the power series coefficient
of the $(ab-a-b)$th term is 1, and all later power series coefficients are
zero. [Therefore, in particular, $r(ab-a-b) = 0$, $r(n) = 1$ for $ab-a-b