\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 i~~s \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~~