\documentclass[12pt,reqno]{article} \usepackage[all]{xy} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Characterizing Frobenius Semigroups by \\ \vskip .11in Filtration } \vskip 1cm \large Inga Johnson, Sean Powers, Colin Starr, Charles Trevelyan and \\ Craig Webster\\ Department of Mathematics\\ Willamette University\\ Salem, OR 97301\\ USA\\ \href{mailto:ijohnson@willamette.edu}{\tt ijohnson@willamette.edu}\\ \href{mailto:cstarr@willamette.edu}{\tt cstarr@willamette.edu} \end{center} \vskip .2 in \begin{abstract} For a given base $a$, and for all integers $k$, we consider the sets $$G_{a}(k)=\{a^{k},a^{k}+a^{k-1},\ldots,a^{k}+a^{k-1}+\dots+a^{1}+a^{0}\},$$ and for each $G_a(k)$ the corresponding ``Frobenius set'' $$F_a(k)=\{n \in\mathbb{N} \ |\ n \text{ is not a sum of elements of }G_{a}(k) \}.$$ The sets $F_a(k)$ are nested and their union is $\mathbb{N}$. Given an integer $n$, we find the smallest $k$ such that $n \in F_a(k)$. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}} \newtheorem{examp}[theorem]{Example} \newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}} \newtheorem{rema}[theorem]{Remark} \newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}} %% User definitions: \newcommand{\len}{\mbox{len}} \newcommand{\bal}[1]{\begin{align*}#1\end{align*}} \newcommand{\f}[2]{\displaystyle \frac{#1}{#2}} \newcommand{\bt}{\begin{thm}} \newcommand{\et}{\end{thm}} \newcommand{\bp}{\begin{proof}} \newcommand{\ep}{\end{proof}} \newcommand{\bprop}{\begin{prop}} \newcommand{\eprop}{\end{prop}} \newcommand{\bl}{\begin{lemma}} \newcommand{\el}{\end{lemma}} \newcommand{\bc}{\begin{corollary}} \newcommand{\ec}{\end{corollary}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\be}{\begin{enumerate}} \newcommand{\ee}{\end{enumerate}} \section{Introduction and statement of result} The {\bf Frobenius problem} for a given set $A=\{a_1, a_2, \dots, a_n\}$ of positive relatively prime integers is the problem of finding the largest integer that cannot be expressed as a sum of (possibly repeated) elements of $A$. This largest such number is the {\it Frobenius number} of the set $A$, denoted by $g(A)$. Finding the Frobenius number for sets $A$ has been a widely studied problem since the early 1900's, when Frobenius was reported to have posed the question frequently in lectures. Sylvester \cite{Syl} is widely credited with showing that for relatively prime integers $a$ and $b$, $g(\{a, b\}) = ab-(a+b)$, but he actually addressed a slightly different problem. In 1990, Curtis showed that for an arbitrary relatively prime set $A$ the Frobenius number cannot be expressed in terms of a finite set of polynomials \cite{Cu}, although Greenberg and later Davison found algorithms that are reasonably quick in practice in the $n=3$ case \cite{D,G}. In 1996, Ram\'{i}rez-Alfons\'{i}n proved that the Frobenius problem for sets $A$ of three or more elements is NP-hard \cite{RA}. However, R. Kannan has shown that for every fixed $n$, there is a method that solves the Frobenius problem in polynomial time (although the degree of the polynomial grows rapidly with $n$) \cite{Kannan}. In this paper we study a family of sets $G_a(k)$, defined below, and for each such set we study not only the Frobenius number but the set of all numbers which are not sums of elements of $G_a(k)$. More precisely, let the base $a\in \mathbb{N}$ be fixed. For each $k \in \mathbb{N}$, we define $$G_{a}(k)=\{a^{k},a^{k}+a^{k-1}, a^{k}+a^{k-1}+a^{k-2}, \ldots,a^{k}+a^{k-1}+\dots+a^{1}+a^{0}\}.$$ Note that the rightmost (and largest) element listed in the set above is a geometric series equal to $\frac{a^{k+1}-1}{a-1}$, and henceforth we will write it as such without further comment. For the sets $G_a(k)$ we study the Frobenius sets $$F_{a}(k)=\{n \in\mathbb{N}\ |\ n \text{ is not a sum of the elements of }G_{a}(k) \}.$$ A straightforward calculation shows that the sets $F_a(k)$ are nested (i.e., $F_a(k-1) \subseteq F_a(k)$), and the union of the sets $F_a(k)$ over all $k$ is $\mathbb{N}$. This paper investigates the following question: for arbitrary $n\in \mathbb{N},$ what is the least integer $k$ such that $n\in F_a(k)$? We denote this least positive integer as $f_{a}(n):=\text{min}\{k\ |\ n\in F_a(k)\}$ and call it the {\it Frobenius level} of $n$ with respect to the sets $G_a(k)$. \begin{example}\label{base2} With $a=2$ and $k \leq 3$, we have \[ \begin{array}{ccc} G_2(1) = \{2, 3\} & \hspace{.5in} & F_2(1) =\{ 1 \} \\ G_2(2) = \{ 4, 6, 7 \} & & F_2(2) = \{1, 2, 3, 5, 9 \} \\ G_2(3) = \{8, 12, 14, 15\} & & F_2(3) = \{1, 2, 3, 4, 5, 6, 7, 9, 10, \\ && 11, 13, 17, 19, 25, 33\} \end{array} \] The sets $G_2(k)$, for $k=1, 2, \dots$ form the sequence A023758 of Sloane's Encyclopedia. \end{example} We see that $f_2(9)=2$ and $f_2(19)=3$; however, there is not enough information given in Example~\ref{base2} to determine $f_2(30)$. I. Johnson and J. L. Merzel \cite{JM} determined the Frobenius level of an integer $n$ with respect to the sets $G_2(k)$ while studying factorizations in the Steenrod algebra at the prime 2. Their paper serves as motivation for studying these more general sets $G_a(k)$ for arbitrary $a$ and the solution presented in this paper is a generalization of their results. It is believed that the results presented here will have implications in the Steenrod algebra for odd primes analogous to those found at the prime 2 by Johnson and Merzel. For a discussion of the Steenrod algebra and its role in the field of algebraic topology, see \cite{MT,Rav,Steen,Wood}. Our solution of this Frobenius level problem relies on careful study of base $a$ arithmetic, and the following definitions and notations are required to state our result. For a positive integer $n$, let $[n]$ denote a base $a$ expansion of $n$. This means if $w_i \in \{0, 1, \dots, a-1\}$ for all $i$ and $$n = w_k a^k + w_{k-1} a^{k-1} + \dots + w_2 a^2 + w_1 a^1 + w_0 a^0,$$ then $[n] = w_k w_{k-1}\dots w_1 w_0$. We note that this expansion is unique up to leading zeros. For example, in base 3 (ternary) we may view [41] as 1112 or 0001112. We call an ordered string of digits $b_k b_{k-1} b_{k-2} \dots b_2 b_1b_0$ with each digit $b_i$ in $\{0, 1, \dots, a-1\}$ a {\it base $a$ string}, and given integers $i, j$ such that $k \geq i+j \geq i \geq 0$ the base $a$ string $b_{i+j} \dots b_{i+1} b_i$ is called a {\it substring} of $b_k b_{k-1} b_{k-2} \dots b_2 b_1b_0$. We will use roman characters to denote integers and Greek letters to denote strings and substrings. For a given base-$a$ string $\beta $, let $\left\vert \beta \right\vert $ denote the integer with expansion $\beta$ in base $a$. The length of the string $\beta$ will be denoted by $\len(\beta)$. Of course, the length is only defined for a given base $a$ string. Expressions such as $\len([n])$ are not well-defined and will not be used. Let $\beta=b_{i+j}b_{i+j-1}\dots b_{i}$ be a substring of $b_k \dots b_2 b_1b_0$. Then $\beta$ is a {\it non-increasing substring} if and only if $ b_{m}\leq b_{m-1}$ for $ij>0$. The assumption on $b_j$ implies that either $b_j$ does not contribute to $\beta$, or it does contribute and $b_j \neq b_{j+1}$ and $b_{j}\neq b_{j-1}$. The result is clear in the case that $b_j$ does not contribute to $\beta$, so suppose $b_j$ does contribute to $\beta$. Then we have the following two cases: (i) $b_{j+1} < b_j < b_{j-1}$ \hfill (ii) $b_{j+1}>b_j$ and $b_j < b_{j-1}$. \hfill {} It suffices to prove that each digit of $\beta$ that contributes to $\beta$ also contributes to the sum $z(b_k \cdots b_j) + z(b_{j} \cdots b_{0})$ once and only once. In case (i), $b_j$ contributes to $b_jb_{j-1} \dots b_1b_0$; however, it cannot contribute to $b_k \cdots b_{j+1} b_j$ as it cannot follow a drop. Thus the digit $b_j$ contributes once to the sum. The digits in the substring $b_jb_{j-1} \dots b_1$ are contributing if and only if they contribute to $\beta$. Since $b_{j+1}$ contributes to $\beta$, the digits of the substring $b_k \cdots b_{j+1} $ contribute to $b_k \cdots b_{j+1} b_j$ if and only if they contribute to $\beta$. The proof for case (ii) is analogous except that $b_{j+1}$ does not contribute to $\beta$ and does not contribute to $b_k \cdots b_{j+1} b_j$, but all contributions from the left of $b_{j+1}$ are the same in both strings. \end{proof} Given strings $\alpha $ and $\beta $, their concatenation will be denoted by $\alpha \beta $. Lastly, we define the ``star" notation. \begin{definition} For nonempty strings $\alpha $ and $\beta ,$ we define the relation $*$ by \begin{equation*} %\label {star} \alpha * \beta \Leftrightarrow \left\vert \alpha \right\vert 0$, \item[(ii)] $h_l=0$ [note: it is possible that $l=1$], \item[(iii)] for $l+1 \leq i \leq n-1,$ $h_i = 0$ or 1 (possibly empty), and \item[(iv)] $h_n>1$. \end{enumerate} \noindent Suppose $\delta$ is a base-$a$ string of 1's with length $n+1$. Then $z(\gamma-\delta)=z(\gamma)$, where $\gamma-\delta$ has the same length as $\gamma$ (by appending a leading zero if necessary). \end{lemma} \begin{proof} Firstly, note that $a>2$ is forced by the given conditions. Now, to compute $\gamma-\delta,$ we ``borrow'' from each digit to the left of $h_l.$ The result is $$\gamma - \delta = [h_n-2][h_{n-1}+a-2]\cdots[h_{l+1}+a-2][h_{l}+a-1][h_{l-1}-1]\cdots[h_{1}-1][h_0-1].$$ Since $2 \leq h_n \leq a-1,$ $h_n - 2 < a-2.$ Also, $h_{n-1}$ is either a 0 or 1 in $\gamma$. Thus, the $n-1$ digit in $\gamma-\delta$ is $a-2$ more than the $n-1$ digit of $\gamma$: it increases by $a$ due to borrowing from $h_n,$ loses one because the $n-2$ digit borrows from it, and loses one more from subtracting $\delta$. The value of the $n-1$ digit of $\gamma-\delta$ is thus either $a-2$ or $a-1$. Therefore, $h_{n}-2< h_{n-1}+a-2$, and the $n$ digit will be a drop in $\gamma -\delta$. However, in $\gamma$, $h_n > h_{n-1},$ so there is a drop in $\gamma - \delta$ that is not in $\gamma$. In $\gamma-\delta,$ the $l+1$ through $n-1$ digits are each $a-2$ more than $h_i$ (since $\gamma-\delta$ requires borrowing throughout these digits), and therefore this section yields the same digit-by-digit contribution to $\gamma-\delta$ as to $\gamma$. Note that $h_l=0,$ so the $l$-digit of $\gamma-\delta$ is $a-1.$ (Since $h_l$ is the first zero appearing in $\gamma,$ no borrowing is necessary to the right of $h_l.$) If $h_{l+1}=0$ (and is hence part of a non-increasing sequence to the left of a drop) in $\gamma$, then the $l+1$ digit in $\gamma - \delta$ is $a-2$ and is therefore a drop and counted as it was for $z(\gamma)$. If $h_{l+1}=1$, then the $l+1$ digit in $\gamma - \delta$ has value $a-1$ and thus is not part of a non-increasing sequence following a drop; it is again counted as it was for $z(\gamma)$. Thus, in either case, the contribution to $\gamma-\delta$ from the $l+1$ digit is the same as it is in $\gamma$. Since $h_{l-1}-1$ is less than $a-1$ and $h_{l}+a-1=a-1,$ the $l$ digit in $\gamma-\delta$ is not a drop. However, the digit at position $l$ in $\gamma$ is a drop since it is the first zero appearing in $\gamma.$ Thus, $\gamma-\delta$ loses a drop that $\gamma$ had. For $l-1>i\geq 1$, each digit $h_i>0$, and therefore no borrowing is required for corresponding digits in $\gamma - \delta$. Thus these digits make the same contribution to $\gamma-\delta$ as to $\gamma.$ The net result of these considerations is that the contribution in $\gamma$ that occurs at $h_l$ is moved to the leading digit in $\gamma-\delta,$ but all other contributions remain the same. Therefore $z(\gamma-\delta)=z(\gamma),$ as desired. \end{proof} Before continuing with the next lemma, we pause to recall the relation $*$: if $\alpha$ and $\beta$ are nonempty base-$a$ strings, then $\alpha *\beta \iff |\alpha|0$, and \item[(c)] $|\alpha| > 0$. \end{enumerate} Then \begin{enumerate} \item[(i)] for $|\beta|>|\delta|$, $\alpha *\beta \Leftrightarrow \alpha * (\beta - \delta)$, and \item [(ii)] for $|\beta|<|\delta|$, $\alpha*\beta \Leftrightarrow [|\alpha | -1] * ([1]\beta -\delta)$, where $1$ and $\beta$ are concatenated to create $[1]\beta>\delta$. \end{enumerate} \end{lemma} \begin{proof} {\bf Case (i):} Suppose $|\beta|>|\delta|$. Then either $\beta$ is zero-free or it contains a zero. If $\beta$ is zero-free, then $\beta - \delta$ requires no borrowing, so $z(\beta)=z(\beta-\delta)$ and $\alpha$ does not change. (Note: this also implies that in Case (i), the hypotheses $|\alpha|>0$ is unnecessary.) Thus $ \alpha * \beta \iff \alpha* (\beta - \delta)$. Now suppose that $\beta$ contains at least one zero. Write $\beta=b_{k}b_{k-1} \cdots b_1 b_0$. Inductively define substrings $\beta_i$, $i=1,2,\dots m$, for $ml_1$ is the smallest subscript in $\beta$ such that $b_{j_1}>1$. Note that this subscript exists since $|\beta|>|\delta|.$ If $b_w=0$ for some $w>j_1$, then define $\beta_2=b_{j_2}\cdots b_{l_2}\cdots b_{j_1}$, where $l_2>j_1$ is the smallest subscript such that $b_{l_2}=0$, and $j_2>l_2$ is the smallest subscript such that $b_{j_2}>1$. A diagram of the basic structure of each $\beta_i$ is included below. $$\overbrace{\underbrace{b_{j_i}}_{>1} \underbrace{\dots \hspace{.05in}_{ \hspace{.01in}_{ \hspace{.01in} }} }_{\leq 1} \underbrace{b_{l_i}}_{=0} \underbrace{\dots b_{j_{i-1}}}_{\neq0} }^{\beta_i}$$ Create successively $\beta_1, \beta_2, \beta_3, \ldots, \beta_m$ as above, where either $b_{k}$ appears in $\beta_m$ or $b_w>0$ for all $w>j_m$. In the former case, define $\beta_{m+1}$ to be the empty string; in the latter case, define $\beta_{m+1}=b_{k} b_{k-1} \cdots b_{j_m}$. The following diagram gives a picture of $\beta$ and the $\beta_i$ substrings. \ \xymatrix@C=4pt@M=0pt{ \beta: &&b_k \ar@{-}@/^1pc/ [rr]|{\beta_{m+1}} & \dots & b_{j_m} \ar@{-}@/^1pc/ [rrrr]|{\beta_{m}} & \dots &\underline{b_{l_m}} \ar `d[l] `^d[ll] [lld] & \dots &b_{j_{m-1}} & % b_{j_2} \ar@{-}@/^1pc/ [rrrr]|{\beta_{2}} & \dots & \underline{b_{l_2}} %\ar `d[l] `^d[ll] [lld] & \dots & b_{j_1} \ar@{-}@/^1pc/ [rrrr]|{\beta_{1}} & \dots& \underline{b_{l_1}} \ar `d[l] `^d[ll] [lld] & \dots & b_0 \\ \beta - \delta: && &{} &\underline{b_{j_m }- 2} &{}&{}&{}&{}&{} %&\underline{b_{j_2} - 2} & &&\underline{b_{j_1} -2} & } \ The $\beta_i$ satisfy the hypotheses of Lemma \ref{subtraction1} and of quasi-linearity. Thus each $b_{l_i}$ is contributing in $\beta$ and is paired with the contributing digit $b_{j_i}-2$ in $\beta-\delta$. Let $\delta_i$ denote a string of ones of length $\len(\beta_i)$ for $i=1,\dots , m+1$. We compute: \begin{eqnarray*} z(\beta) & = & \sum_{i=1}^{m+1} z(\beta_i) \hspace{.1in} \textrm{by quasi-linearity}\\ &=& \sum_{i=1}^{m+1} z(\beta_i-\delta_i) \hspace{.1in} \textrm{by Lemma~\ref{subtraction1}.} \end{eqnarray*} It remains to show that $ \sum_{i=1}^{m+1} z(\beta_i-\delta_i) = z(\beta -\delta)$. Notice that quasi-linearity does not apply to the strings $\beta_i-\delta_i$ as the leading digit of $\beta_i -\delta_i$ is one less than the last digit of $\beta_{i+1} - \delta_{i+1}$. However, we can piece these strings together to form $\beta-\delta$ by deleting the last digit of each $\beta_{i}-\delta_{i}$ for $i=2,\dots,m+1$ and concatenating appropriately. Recall that these last digits are not contributing digits to $\beta_i -\delta_i$ so none of them are underlined. In addition, every digit in each $\beta_{i} - \delta_{i}$ has the same right neighbor after forming $\beta-\delta$ (by deletion and concatenation) except $b_{j_{i-1}+1}-1$, so we must only show that $b_{j_{i-1}+1}-1$, for $i = 2, \dots , m+1$, contributes to $\beta_{i} - \delta_{i}$ if and only if it contributes to $\beta - \delta$. (That is, we must show that the deletion-concatenation procedure does not disturb any underlining.) Now \begin{eqnarray*} b_{j_{i-1}+1} -1 \textrm{ contributes to } \beta_i - \delta_i & \iff & b_{j_{i-1}+1} -1 < b_{j_{i-1}} -1 \\ & \iff & b_{j_{i-1}+1} -1 \leq b_{j_{i-1}} -2. \end{eqnarray*} We know from the proof of Lemma \ref{subtraction1} that $b_{j_i-1}-2$ contributes to $\beta_{i-1}-\delta_{i-1},$ and hence to $\beta-\delta.$ This implies that $b_{j_{i-1}+1} -1\leq b_{j_{i-1}}-2$ if and only if $b_{j_{i-1}+1}-1$ contributes to $\beta-\delta.$ Thus each contribution to $\beta_i-\delta_i$ is counted once and only once in $\beta-\delta,$ so $\sum_{i=1}^{m+1}z(\beta_i-\delta_i)= z(\beta-\delta).$ {\bf Case (ii):} Now consider $|\beta|<|\delta|$. If $\beta$ has no digits larger than 1, then form $\tilde{\beta}$ as below (with $t=-1$). If $\beta$ has a digit larger than 1, let $t$ be the largest integer such that $b_t>1$. Apply case (i) to $\beta' = b_t \dots b_1 b_0$ and $\delta' = 1 \dots 1$, a string of $t+1$ ones. Then $z(\beta') = z(\beta'-\delta')$. Consider $\tilde\beta =[1]b_kb_{k-1}\dots b_{t+1}= [a+b_k] b_{k-1} \dots b_{t+1}$ where $b_{t+1}, \dots, b_k \in \{0, 1\}$. Let $s \geq t+1$ be the least integer such that $b_s=0$. Note that such a $b_s$ exists since $|\beta| <|\delta|$. Let $\tilde\delta = 1\dots 1$ be a string of $k-t$ ones. For $i$ from $t+1$ through $k$, the digits $c_i$ of $\tilde\beta - \tilde\delta$ are as follows: \[ \left\{ \begin{array}{cl} c_i = 0, & \textrm{ if }t+1\leq is \textrm{ and } b_i=1; \\ c_i = a-2, & \textrm{ if } i>s \textrm{ and } b_i = 0. \end{array} \right. \] If $t\ge 0,$ then the digits labelled $t+1$ through $s-1$ of $\tilde\beta$ are all 1, and the corresponding digits of $\tilde\beta-\tilde\delta$ are all 0. Since the $t+1$ digit is a drop in either case, both strings contribute the same. If $t=-1,$ then digits $t+1=0$ through $s-1$ of $\tilde\beta$ are all 1 (since $\beta\not\equiv 0$ (mod $a$)) and the corresponding digits of $\tilde\beta-\tilde\delta$ are all 0, and none of these contribute. Note that the string of digits from $t+1$ to $s-1$ could be empty. Now $b_s=0$ contributes to $\tilde\beta$ since it is a drop from the preceding digit, but the $s$th digit of $\tilde\beta-\tilde\delta$ does not contribute since it equals $a-1.$ Thus, the contributions in $\beta$ up through the $s$th digit are $z(\beta')+(s-t-1)+1,$ and the contributions in $[1]\beta-\delta$ up through the $s$th digit are $z(\beta')+(s-t-1).$ From the table above, we see that the $s+1$ through $k$ digits contribute in $\beta$ if and only if they contribute in $[1]\beta -\delta$ since $0\leftrightarrow a-2$ and $1 \leftrightarrow a-1$. For $b_s$ becomes $a-1$ in $\tilde\beta-\tilde\delta.$ Therefore, if $b_{s+1}=0$ (and therefore contributes to $\beta),$ then the $s+1$ digit of $\tilde\beta-\tilde\delta$ is $a-2,$ which contributes to $\tilde\beta-\tilde\delta.$ If $b_{s+1}=1$ (and therefore does not contribute to $\beta),$ then the $s+1$ digit of $\tilde\beta-\tilde\delta$ is $a-1,$ which does not contribute to $\tilde\beta-\tilde\delta.$ The remaining digits of $\tilde\beta-\tilde\delta$ may be considered in the same way. Thus, overall, we have $z([1]\beta - \delta) =z(\beta) -1$ since only the $s$th digit contributes differently in $\beta$ and $\tilde\beta-\tilde\delta.$ \end{proof} \begin{theorem}\label{starthrm} For nonempty strings $\alpha$ and $\beta$ with $\left\vert \alpha \beta \right\vert \neq 0,$ $$\alpha * \beta \Leftrightarrow \left\vert \alpha \beta \right\vert \in F_{a}(len(\beta )-1).$$ \end{theorem} \begin{proof} We proceed by induction on $n:=|\alpha \beta|$. Set $k:=len(\beta )-1$, so the theorem asserts $\alpha * \beta \Leftrightarrow n\in F_a(k)$. If $n=1$, then $\left\vert \alpha \right\vert =0, |\beta|=1,$ $\beta=\underbrace{0\cdots 01}_{k+1\mbox{ digits}}$ and $z(\beta)=k$, so $\alpha \ast \beta \Leftrightarrow |\alpha|0.$ Now assume that $n>1$ and that the theorem holds for all smaller positive integers. \begin{enumerate} \item[(i)] \ Suppose $n\equiv 0$ (mod $a$). \ Write $\beta =\beta ^{\prime }0$, and note $\len(\beta ^{\prime})=k$ and $z(\beta )=z(\beta ^{\prime })$ since appending a zero to the right of $\beta'$ cannot introduce a drop. Then \begin{equation*} \alpha * \beta \Leftrightarrow \alpha \ast \beta ^{\prime }\Leftrightarrow \frac{n}{a}=\left\vert \alpha \beta ^{\prime }\right\vert \in F_a(k-1)\Leftrightarrow n\in F_a(k), \end{equation*} where the second equivalence follows by induction and the last from Lemma~\ref{recursive1} since $R=0.$ \item[(ii)] \ Suppose $n\not\equiv 0$ (mod $a$). Note that this implies that in base $a,$ the last digit of $\beta$ is nonzero. There are three cases: \begin{enumerate} \item[(a)] Suppose $z(\beta )=0$. Then $\beta$ has no drops and thus can be written as a sum of the elements in $G_{a}(k)$. Then $\left\vert \beta \right\vert =c_{1}a^{k}+\dots+c_{k+1}(a^k+\dots +a+1)$, and $n=\left\vert \alpha \right\vert \cdot a^{k+1}+c_{1}a^{k}+\dots+c_{k+1}(a^k+\dots +a+1)\notin F_a(k)$. \ In this case, $\alpha \ast \beta $ and $n\in F_a(k)$ are both false. \item[(b)] Suppose $z(\beta )>0$ and $\left\vert \alpha \right\vert =0$. \ Certainly $n=\left\vert \beta \right\vert \le a^{k+1}-1$. In fact, since $\beta$ has a drop, we have $n 0$ was unnecessary for Case (i)), the second from the induction hypothesis, and the last from Lemma~\ref{recursive2}. \end{enumerate} \item[(c)] Suppose $z(\beta )>0$ and $\left\vert \alpha \right\vert >0$; then by Lemma \ref{subtraction2} \bal{\alpha \ast \beta &\Leftrightarrow \alpha * (\beta - \delta) \mbox{ or } \left [ \left\vert\alpha\right\vert -1 \right ] \ \ast ([1]\beta - \delta)\\ &\Leftrightarrow n-(a^k+\dots +a+1)\in F_a(k)\\ &\Leftrightarrow n\in F_a(k),} where the first equivalence follows from Lemma~\ref{subtraction2}, the second from the induction hypothesis, and the last from Lemma~\ref{recursive2}. \end{enumerate} \end{enumerate} \end{proof} Theorem \ref{mainthrm} is actually a corollary of Theorem~\ref{starthrm}. One can easily compute $f_{a}(n)$ from Theorem~ \ref{mainthrm}. Here are a few example calculations. Notice that to apply Theorem~\ref{mainthrm} it may be necessary to write a string with leading zeros. \bc\label{cor} Let $n\in \Z^+.$ Then $n\in F_a(k)$ if and only if there exist base-$a$ strings $\alpha$ and $\beta$ such that \be \item $|\alpha\beta|=n$, \item $\alpha *\beta,$ and \item $k=\len(\beta)-1.$ \ee \ec \bp If such strings $\alpha$ and $\beta$ exist, then $n=\alpha\beta\in F_a(k)$ by Theorem \ref{starthrm}. Conversely, if $n\in F_a(k),$ then let $\beta$ be the last $k+1$ digits of a base-$a$ representation of $n$, and let $\alpha$ be the remaining digits, setting $\alpha=0$ if otherwise $\alpha$ would be empty. This gives $|\alpha\beta|=n$ and $k=\len(\beta)-1$ directly. Furthermore, since $|\alpha\beta|=n\in F_a(k), \alpha *\beta$ by Theorem \ref{starthrm}. \ep \begin{example} \begin{enumerate} \item For $n=24=|11000|=|0011000|$ with base $a=2,$ let $\alpha=0$ and $\beta=011000$; then $|\alpha \beta|= 24$ and $0=|\alpha| < z(\beta)=1$. We see that $f_{2}(24)=\len(\beta)-1=5$ since for no shorter $\beta$ will we have a drop. \item In ternary, for $n=50_{10} = |1212_3|$, let $\alpha=0$ and $\beta=1212$; then $|\alpha \beta|= 50$ and $0=|\alpha| < z(\beta)=2$. Thus $f_{3}(50)=\len(\beta)-1=3$. \item In base 7, for $n=22413_{10}=|122226_7|$, let $\alpha=1$ and $\beta=22226$; then $|\alpha\beta|=22413$ and $1=|\alpha| < z(\beta)=4$. Therefore $f_{7}(22413)=4$. \end{enumerate} \end{example} We note that Theorem~\ref{starthrm} and Corollary~\ref{cor} completely characterize the Frobenius sets, $F_a(k)$. In addition, if $n \not\in F_a(k-1)$ there is a simple algorithm giving $n$ as a non-negative linear combination of the elements of $G_a(k-1)$. \ {\bf Representation Algorithm:} Assuming $n \not\in F_a(k-1)$ the following algorithm gives $t_i \geq 0$ such that $$n=t_0 a^{k-1}+t_1 (a^{k-1}+a^{k-2}) +t_2(a^{k-1}+a^{k-2}+a^{k-3})+ \dots +t_k(a^{k-1}+\dots+a^1+a^0).$$ \be \item Write $n$ in base $a$ as $n=c_r\cdots c_1c_0.$ \item Let $t_k := c_0$ and $Remain:=n-t_k(a^{k-1}+\dots+a^1+a^0)$. \item If $Remain=0$, put $t_{k-1} = t_{k-2} = \dots = t_0:=0$, then STOP. \item Let $m:=1$. \item Write $Remain$ in base $a$ as $c_{mr}\dots c_{m2} c_{mm} \overbrace{00\dots0}^{m \hspace{.1in}\textrm{zeros}}.$ \item Let $t_{k-m} := c_{mm}$ and put $Remain:= Remain - t_{k-m}(a^{k-1}+a^{k-2}+\dots +a^m)$. \item If $Remain=0$, put $t_{k-m-1} =t_{k-m-2} \dots =t_0:=0$, then STOP. \item If $Remain > 0$, put $m:=m+1$. If $m 0$ and $m=k$, put $t_0 = \frac{Remain}{a^k}$. STOP. \ee Here is an example using the Representation Algorithm. \begin{example} Suppose $a=3$. Let $n=1541=2\cdot 3^6+3^4+2$. The ternary representation of $1541$ is $2010002$. Since $2*010002$ holds but $20*10002$ is false, $1541 \in F_3(5)$ but $1541 \not\in F_3(4)$ by Corollary~\ref{cor}. Recall that $G_3(4) = \{81, 108, 117, 120, 121\}$. We begin by writing the elements of $G_3(4)$ in base $a=3$: $[G_3(4)]_3 = \{ 10000, 11000, 11100, 11110, 11111\}$. We will find non-negative coefficients $t_i$ such that $$2010002=t_0(10000)+t_1(11000)+t_2(11100)+t_3(11110)+t_4(11111)$$ The ternary representation of $1541$ implies $t_4 = 2$. The next few steps outlined below involve subtracting the appropriate multiple of the elements of $G_3(4)$. The quantity $Remain$ is changed by each subtraction and each new $Remain$ amount gives another $t_i$. \[ \begin{array}{crcrcrcr} & \textrm{Step }1&&\textrm{Step } 2&\\ n=&2010002 & \hspace{.2in} & 1210010 & \hspace{.2in} &\\ &\underline{- 22222 } & & \underline{- 11110} &&\\ Remain: & 1210010 & & 1121200 && \\ & \implies t_3=1&& \implies t_2=2&& \end{array} \] \[ \begin{array}{crcrcrcr} & \textrm{Step }3&&\textrm{Step } 4\\ n=&1121200 & \hspace{.2in} &1022000 \\ & \underline{-22200}&& \underline{-22000}\\ Remain: & 1022000 && 1000000\\ & \implies t_1=2&& \implies t_0= 9 \end{array} \] %%Check: 9(81)+2(108)+2(117)+1(120)+2(121) = 1541. \end{example} \section{Theorem~\ref{starthrm} as an Algorithm} Fix the integer $a\geq 2$. In this section we present the algorithm for determining, given $n\in \Z^+$, the least $k$ such that $n\in F_a(k).$ We then briefly discuss the computational complexity of our algorithm. \noindent {\bf Algorithm:} \be \item Write $n$ in base $a:$ $n=c_k\cdots c_1c_0.$ \item Let $\alpha_0:=c_k\cdots c_1$ and $\beta_0:=c_0.$ \item If $\alpha_0*\beta_0,$ then $n\in F_a(0).$ STOP. \item If not $\alpha_0*\beta_0,$ let $l:=1.$ \item Let $\alpha_l:=c_k\cdots c_{l+1}$ and $\beta_l:=c_l\cdots c_0.$ \item If $\alpha_l*\beta_l,$ then $n\in F_a(l).$ STOP. \item If $l