%%%% 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, ¶¡ÏãÔ°AV, 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