# Representations of integers as quotients of sums of distinct powers of three

Katie Anders  University of Texas at Tyler<EMAIL_ADDRESS>,  Madeline
Locus Dawsey  University of Texas at Tyler<EMAIL_ADDRESS>,  Bruce
Reznick  University of Illinois at Urbana-Champaign<EMAIL_ADDRESS>and
Simone Sisneros-Thiry  California State University- East Bay
<EMAIL_ADDRESS>
###### Abstract.

Which integers can be written as a quotient of sums of distinct powers of
three? We outline our first steps toward an answer to this question, beginning
with a necessary and almost sufficient condition. Then we discuss an algorithm
that indicates whether it is possible to represent a given integer as a
quotient of sums of distinct powers of three. When the given integer is
representable, this same algorithm generates all possible representations. We
develop a categorization of representations based on their connections to
$0,1$-polynomials and give a complete description of the types of
representations for all integers up to 364. Finally, we discuss in detail the
representations of 7, 22, 34, 64, and 100, as well as some infinite families
of integers.

###### Key words and phrases:

digital representations, ternary representations, Newman polynomials

###### 2010 Mathematics Subject Classification:

11A63

##  1\. Introduction

We investigate which integers can be written as a quotient of sums of distinct
powers of 3. Such an integer $m$ is of the form

(1.1)
$m=\frac{3^{a_{1}}+\cdots+3^{a_{\ell-1}}+3^{a_{\ell}}}{3^{b_{1}}+\cdots+3^{b_{n-1}}+3^{b_{n}}}=3^{a_{\ell}-b_{n}}\cdot\frac{3^{a_{1}-a_{\ell}}+\cdots+3^{a_{\ell-1}-a_{\ell}}+3^{0}}{3^{b_{1}-b_{n}}+\cdots+3^{b_{n-1}-b_{n}}+3^{0}},$

where $a_{1},a_{2},\ldots,a_{\ell}$ and $b_{1},b_{2},\ldots,b_{n}$ are non-
negative integers with $a_{1}>a_{2}>\cdots>a_{\ell}$,
$b_{1}>b_{2}>\cdots>b_{n}$, and $a_{\ell}-b_{n}\geq 0$. We can restrict our
attention to integers $m$ congruent to $1\bmod 3$. Why? Since the numerator
and denominator of the right side of (1.1) are congruent to $1\bmod 3$, we
have $m\equiv 1\pmod{3}$ if $a_{\ell}-b_{n}=0$ and $m\equiv 0\pmod{3}$ if
$a_{\ell}-b_{n}>0$. If $m\equiv 0\pmod{3}$, then we can write $m=3^{k}m_{1}$,
where $m_{1}\equiv 1\pmod{3}$. Consequently, we will only consider integers
congruent to $1\bmod 3$.

A straightforward estimate, given below as Theorem 1.2, shows that any integer
written as a quotient of sums of distinct powers of three must be contained in

(1.2) $\bigcup_{r=0}^{\infty}\bigl{(}\tfrac{2}{3}\cdot 3^{r},\tfrac{3}{2}\cdot
3^{r}\bigr{)}.$

Can every integer congruent to $1\bmod 3$ belonging to the union
$\eqref{feasible}$ be written as a quotient of sums of distinct powers of 3?
No, this necessary condition is nearly sufficient but not quite. The smallest
integers $m\equiv 1\pmod{3}$ that belong to the union of intervals in (1.2)
but have no representation of the form (1.1) are $m=529$, $m=592$, $m=601$,
and $m=616$, and there are only ten exceptions less than $6.2\times 10^{6}$.

A very preliminary version of some of the material in this paper was presented
by the third author in 2015 [9], and this presentation included the next
smallest counterexample, 5368, which was found by his student Sakulbuth
Ekvittayaniphon. Independently, a few years later, Jeffrey Shallit and his
student Sajed Haque [5] found a total of eleven exceptions less than 107
million. See also A339636 in [8], in which it is stated that “A simple
automaton-based (or breadth-first search) algorithm can establish in $O(n)$
time whether $n$ is …,” in our terms, representable. These exceptions are also
discussed in [3, p,4]; the distinction of local and universal representations
does not arise. See also the thesis of the fourth author [10, pp.128-130].

###  1.1. Definitions, Notation, and Background Material

For $r\geq 1$, let

$\mathcal{A}_{r}=\left\\{1+\sum_{k=1}^{r-1}\epsilon_{k}3^{k}+3^{r}\ \bigg{|}\
\epsilon_{k}\in\\{0,1\\}\right\\}\quad\text{ and
}\quad\mathcal{A}=\\{1\\}\cup\bigcup_{r=1}^{\infty}\mathcal{A}_{r}.$

Returning to (1.1), we see that in the rightmost fraction, both the numerator
and denominator are elements of $\mathcal{A}$. We use the following notation
for the set of 0,1-polynomials with constant term 1, also known as Newman
polynomials, which are investigated more thoroughly in [7]:

$\mathcal{P}_{r}=\left\\{1+\sum_{k=1}^{r-1}\epsilon_{k}x^{k}+x^{r}\ \bigg{|}\
\epsilon_{k}\in\\{0,1\\}\right\\}\quad\text{ and
}\quad\mathcal{P}=\\{1\\}\cup\bigcup_{r=1}^{\infty}\mathcal{P}_{r}.$

Note that $m\in\mathcal{A}_{r}$ if and only if there exists a polynomial
$p(x)\in\mathcal{P}_{r}$ such that $m=p(3)$. With this notation, the subject
of our investigation is $\mathcal{A}/\mathcal{A}$, defined as the set of
integers congruent to $1\bmod 3$ that can be written as a quotient of two
elements of $\mathcal{A}$. Since $1\in\mathcal{A}$, we see that 1 can be the
denominator of such a quotient, and it follows that
$\mathcal{A}\subseteq\mathcal{A}/\mathcal{A}$. There are, however, elements of
$\mathcal{A}/\mathcal{A}$ that do not belong to $\mathcal{A}$. One such
example is 7, which we shall consider shortly.

We use the notation
$w=[\epsilon_{r}\;\epsilon_{r-1}\;\dots\;\epsilon_{1}\;\epsilon_{0}]_{3}$ to
indicate the standard base 3 representation of the integer $w$, where the
digits $\epsilon_{r},\dots,\epsilon_{0}\in\\{0,1,2\\}$. For example, the
standard base 3 representation of the integer 7 is $7=[21]_{3}$. We see from
this standard base 3 representation that 7 does not belong to $\mathcal{A}$;
because

(1.3)
$7=\frac{28}{4}=\frac{[1001]_{3}}{[11]_{3}}=\frac{3^{3}+1}{3+1}=\frac{p(3)}{q(3)},$

where $p(x)=x^{3}+1\in\mathcal{P}_{3}$ and $q(x)=x+1\in\mathcal{P}_{1}$, we
have that $7\in\mathcal{A}/\mathcal{A}$.

Throughout this document, we say an integer is representable if it can be
written as a quotient of sums of distinct powers of 3 using any of the types
of formats illustrated in (1.3). In the example of the integer 7, we notice
that $\frac{p(x)}{q(x)}=x^{2}-x+1$, which, when evaluated at any integer $x$,
will yield an integer. We call such a representation universal. Not every
representation is universal; those that are not we call _local_ , and the
smallest example of a local representation in base 3 is

$22=\frac{22\cdot
37}{37}=\frac{814}{37}=\frac{3^{6}+3^{4}+3+1}{3^{3}+3^{2}+1}=\frac{p(3)}{q(3)},$

where $p(x)=x^{6}+x^{4}+x+1\in\mathcal{P}_{6}$ and
$q(x)=x^{3}+x^{2}+1\in\mathcal{P}_{3}$. Note that $q(x)$ does not divide
$p(x)$ in this example, and so in general the quotient $\frac{p(b)}{q(b)}$
need not be an integer when evaluated at an integer $b\neq 3$. As an example,
$\frac{p(1)}{q(1)}=\frac{4}{3}$. Note also that $22=3^{3}-3^{2}+3+1$, and it
is not surprising that

$x^{6}+x^{4}+x+1=(x^{3}+x^{2}+1)(x^{3}-x^{2}+x+1)+x^{3}(x-3),$

since the polynomials involved in the representation of $22$ indicate that the
remainder from polynomial division must be divisible by $x-3$. We now state
the definitions of universal representation and local representation more
formally.

######  Definition 1.1.

Let $m$ be an integer such that $m\equiv 1\pmod{3}$ and $m=\frac{p(3)}{q(3)}$,
where $p(x),q(x)\in\mathcal{P}$. If $q(x)\mid p(x)$, then the representation
of $m$ as $\frac{p(3)}{q(3)}$ is universal. If $q(x)\nmid p(x)$, then this
representation of $m$ is local.

Notice that any integer $m\equiv 1\pmod{3}$ which can be written as a sum of
distinct powers of 3 has a universal representation $m=\frac{p(3)}{q(3)}$ with
$q(x)=1$. Throughout, we refer to a universal representation for which
$q(x)=1$ as a _trivial_ universal representation.

Next we prove the aforementioned theorem that states that an integer written
as a quotient of sums of distinct powers of 3 must belong to the union given
in (1.2).

######  Theorem 1.2.

For any integer $r$, let $\mathcal{I}_{r}=\left(\frac{2}{3}\cdot
3^{r},\frac{3}{2}\cdot 3^{r}\right)$. If $m\in\mathcal{A}/\mathcal{A}$, then
$m\in\mathcal{I}_{r}$ for some $r$. Moreover, if $m=\frac{p(3)}{q(3)}$ for
some $p(x),q(x)\in\mathcal{P}$, then there exists an integer $e$ such that
$p(x)\in\mathcal{P}_{e+r}$ and $q(x)\in\mathcal{P}_{e}$.

###### Proof.

Suppose $p(x)\in\mathcal{P}_{d}$. Then

$3^{d}<1+3^{d}\leq p(3)\leq 1+\sum_{k=1}^{d-1}3^{k}+3^{d}=\frac{3\cdot
3^{d}-1}{3-1}<\frac{3}{2}\cdot 3^{d}.$

Accordingly, if $q(x)\in\mathcal{P}_{e}$, then $3^{e}<q(3)<\frac{3}{2}\cdot
3^{e}$, so

$\frac{2}{3}\cdot 3^{d-e}=\frac{3^{d}}{\frac{3}{2}\cdot
3^{e}}<\frac{p(3)}{q(3)}<\frac{\frac{3}{2}\cdot 3^{d}}{3^{e}}=\frac{3}{2}\cdot
3^{d-e},$

and thus $\frac{p(3)}{q(3)}\in\mathcal{I}_{d-e}$. This inequality holds
regardless of whether $\frac{p(3)}{q(3)}$ is an integer. If
$m=\frac{p(3)}{q(3)}$, then $m\in\mathcal{I}_{d-e}$, establishing the
necessary condition; if $m\in\mathcal{I}_{r}$, then $d=e+r$. ∎

What do the intervals in Theorem 1.2 remind us of? This question led to our
initial interest in these representations of integers. In 2019, Athreya,
Tyson, and the third author studied the standard Cantor set,

$C=\left\\{\sum_{k=1}^{\infty}\frac{\alpha_{k}}{3^{k}}\ \bigg{|}\
\alpha_{k}\in\\{0,2\\}\right\\},$

and they proved in [2, Theorem 1] that

(1.4) $\left\\{\frac{u}{v}\ \bigg{|}\ u,v\in C,v\neq
0\right\\}=\bigcup_{r=-\infty}^{\infty}\left[\frac{2}{3}\cdot
3^{r},\frac{3}{2}\cdot 3^{r}\right].$

Note the similarity between this union and that given in $\eqref{feasible}$.
We also highlight and explain some of the differences. Since we are only
considering integers in our work, the union in (1.2) is over $r\geq 0$.
Another difference is that we only consider integers congruent to $1\bmod 3$,
while in (1.4), there is no restriction regarding the congruence class of the
integer mod 3. For example, $\frac{1}{3},\frac{2}{3}\in C$, so
$\frac{2/3}{1/3}=2$ is a quotient of elements of the Cantor set, but of course
$2\equiv 2\pmod{3}$ cannot be represented as a quotient of sums of distinct
powers of 3, as we have discussed.

The usual construction of the Cantor set involves a sequence of sets $C_{n}$
consisting of $2^{n}$ closed intervals, each of length $3^{-n}$. Consider the
set of quotients of left endpoints of these intervals:

$\displaystyle\left\\{\frac{\sum_{k=1}^{d}\frac{\alpha_{k}}{3^{k}}}{\sum_{j=1}^{e}\frac{\beta_{j}}{3^{j}}}\
\bigg{|}\ \alpha_{k},\beta_{j}\in\\{0,2\\}\right\\}$
$\displaystyle=\left\\{\frac{2\cdot
3^{-d}\sum_{k=1}^{d}\frac{1}{2}\alpha_{k}\cdot 3^{d-k}}{2\cdot
3^{-e}\sum_{j=1}^{e}\frac{1}{2}\beta_{j}\cdot 3^{e-j}}\ \bigg{|}\
\alpha_{k},\beta_{j}\in\\{0,2\\}\right\\}$
$\displaystyle=\left\\{\frac{3^{e-d}\cdot\sum_{k=1}^{d}\frac{1}{2}\alpha_{k}\cdot
3^{d-k}}{\sum_{j=1}^{e}\frac{1}{2}\beta_{j}\cdot 3^{e-j}}\ \bigg{|}\
\alpha_{k},\beta_{j}\in\\{0,2\\}\right\\}.$

Each element of this set is a quotient of two elements of $\mathcal{P}$,
evaluated at $x=3$, multiplied by a power of $3$.

The question of which polynomials are quotients of two elements of
$\mathcal{P}$ seems to be both open and hard. One observation is that if
$r(x)=\frac{p(x)}{q(x)}$, then the zeros of $r(x)$ are a subset of the zeros
of $p(x)$. Determining the zeros of polynomials in $\mathcal{P}$ also seems to
be a very hard question; see [7].

In 1987, John Loxton and Alf van der Poorten wrote a paper entitled “An awful
problem about integers in base four” [6], which was dedicated to proving that
every odd integer can be written as a quotient of sums and differences of
powers of 4. What was “awful” was only that there was not an elegant top-down
solution. Their paper reports that Selfridge and LaCampagne asked a similar
question for 3, and the authors mentioned that if differences are removed, as
in the case we are investigating, “There is some difficulty in describing
which integers can occur.”

We concur with this quote, and in this paper we report our findings and early
progress in determining which integers congruent to $1\bmod 3$ can be written
as quotients of sums of distinct powers of 3. In Section 2, we exhibit several
families of integers having only universal representations, and then we
consider $100$, the smallest integer having only universal representations but
not belonging to any of these families. In contrast to the integers discussed
in Section 2, some integers have only local representations. We investigate
two such examples, $22$ and $34$, in Section 3.1. Then, in Section 3.2, we
present $64$ as an example of an integer having both nontrivial universal
representations and local representations. In Section 4, we provide a table
that indicates for each integer $m\equiv 1\pmod{3}$ contained in the union
(1.2) up to $m=364$ whether $m$ has a universal representation and whether $m$
has a local representation. Finally, we outline further directions to explore
in Section 5.

The following examples illustrate a few of the possible combinations of types
of representations that can exist for a single integer $m\equiv 1\pmod{3}$.

######  Example 1.3.

The integer $31=3^{3}+3+1$ has a trivial universal representation with
$p(x)=x^{3}+x+1$ and $q(x)=1$. It is also the case that if
$g(x)=x^{5}-x^{3}+1$ and $h(x)=x^{2}-x+1$, then
$\frac{g(3)}{h(3)}=\frac{217}{7}=31$, and $h(x)\nmid g(x)$. Since neither
$g(x)$ nor $h(x)$ is in $\mathcal{P}$, we know that $\frac{g(3)}{h(3)}$ is not
a universal representation of $31$. However, with a suitable common multiplier
for $g(x)$ and $h(x)$, we can obtain polynomials in $\mathcal{P}$ and see that
$31$ has a local representation in addition to its trivial universal
representation. In fact, $31$ actually has many local representations, and the
algorithm in Section 1.2 describes how to find them. As a specific example of
such a local representation, observe that

$\frac{x^{5}-x^{3}+1}{x^{2}-x+1}=\frac{(x^{5}-x^{3}+1)(x^{4}+x^{3}+x^{2}+x+1)}{(x^{2}-x+1)(x^{4}+x^{3}+x^{2}+x+1)}=\frac{x^{9}+x^{8}+x^{2}+x+1}{x^{6}+x^{4}+x^{3}+x^{2}+1}.$

######  Example 1.4.

As another example of an integer that has both a trivial universal
representation and a local representation, consider $37=3^{3}+3^{2}+1$. We can
also write

$37=\frac{3^{6}-3^{3}+1}{3^{3}-3^{2}+1}.$

The polynomials $x^{6}-x^{3}+1$ and $x^{3}-x^{2}+1$ are not in $\mathcal{P}$,
but if we multiply each by $x^{5}+x^{4}+x^{3}+x^{2}+x+1$, we obtain
polynomials that do belong to $\mathcal{P}$, and we have
$37=\frac{p(3)}{q(3)}$, where $p(x)=x^{11}+x^{10}+x^{9}+x^{2}+x+1$ and
$q(x)=x^{8}+x^{5}+x^{4}+x^{3}+x+1$. To conclude that this is a local
representation, we must have that $q(x)\nmid p(x)$. We could show this with
polynomial long division, or we can consider evaluating the quotient
$\frac{p(x)}{q(x)}$ at $x=2$, for example. This yields $\frac{3591}{315}$,
which is not an integer and tells us the representation of $37$ as
$\frac{p(3)}{q(3)}$ must be local.

######  Example 1.5.

It is also possible for an integer to have two universal representations with
different polynomial quotients. For example, $841=3^{6}+3^{4}+3^{3}+3+1$ is a
trivial universal representation of $841$ with the polynomial quotient being
$x^{6}+x^{4}+x^{3}+x+1$. In addition, $841$ has a nontrivial universal
representation with polynomial quotient $x^{6}+x^{5}-x^{4}-2x^{3}+x+1$, since
$841=3^{6}+3^{5}-3^{4}-2\cdot 3^{3}+3+1=\frac{p(3)}{q(3)}$ with
$p(x)=x^{15}+x^{14}+x^{11}+x^{5}+x^{4}+x^{2}+x+1$ and
$q(x)=x^{9}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1$.

For a given integer $m$, we have developed an algorithm for determining
whether $m$ is an element of $\mathcal{A}/\mathcal{A}$. This algorithm is a
refinement of a multiplication transducer, which we shall discuss in more
detail in Section 1.2. As noted previously, we need only consider the integers
$m\equiv 1\pmod{3}$ belonging to an interval of the form given in Theorem 1.2.
For such $m$, this algorithm explores all possibilities for multiples of $m$
by $q$, a sum of distinct powers of 3, such that $mq=p$ is also a sum of
distinct powers of 3. This can be done manually or through the construction of
a directed graph that represents all possible multiplications. The algorithm
leverages intuition similar to more familiar multiplication algorithms in base
10, performing multiplication in steps, starting with the ones digit, and
“carrying” powers of 3. However, our algorithm does not require the summation
of partial products.

Rather than using our algorithm to compute the product $p$ of given integers
$m$ and $q$, we instead start with a given integer $m\equiv 1\pmod{3}$ and
construct both $p$ and $q$ simultaneously to ensure that they are elements of
$\mathcal{A}$, choosing only paths forward that preserve this necessary
condition. Thus, we begin with $3^{0}=1$ copy of $m$, and then for each
positive power $i$ of 3, we need to choose whether or not to include $3^{i}$
additional copies of $m$ in $q$, building the base 3 representation of $q$ as
we move through the algorithm.

###  1.2. The Algorithm, Digraphs, and Multiplication Transducers

We begin with a familiar example, using the algorithm to construct the
quotient given in (1.3) for $m=7$. Denote this quotient by
$7=\frac{p}{q}\in\mathcal{A}/\mathcal{A}$. The procedure of constructing this
quotient involves iterating through steps, where each step “records” the $i$th
digit of the product $7\cdot q=p$ in base 3, as well as the $i$th digit of
$q$. Since $p,q\in\mathcal{A}$, it is necessary to record a digit of 1 in the
$3^{0}$ place of the base 3 expansions of both $p$ and $q$. Write the base 3
expansion of $7$ as $7=(2\cdot 3^{1}+1)\cdot 3^{0}$. After recording 1 into
the $3^{0}$ place of $p$, the remaining unrecorded value is $(2\cdot
3^{1})\cdot 3^{0}=2\cdot 3^{1}$ to “carry” into the next step, which is the
$3^{1}$ step. Note that the number of copies of $3^{1}$ in this unrecorded
value that we must carry into the next step is $2$, which is congruent to
$2\bmod{3}$. In order to record either $0$ or $1$ into the $3^{1}$ place of
$p=7\cdot q$, we need to first add more copies of $3^{1}$ to $q$. Hence we add
$m=7$ to the carried value of $2$, which gives us $(m+2)\cdot 3^{1}=(7+2)\cdot
3^{1}=9\cdot 3^{1}$. To account for this addition of $m\cdot 3^{1}=7\cdot
3^{1}$ into $7\cdot q=p$, we must record a digit of 1 in the $3^{1}$ place of
$q$. Now, we observe that $9\cdot 3^{1}=3\cdot 3^{2}$, so $3$ is the value
which we must carry at the $3^{2}$ step. Since 3 is a sum of distinct powers
of 3, we can stop iterating and complete the construction. In fact, we have
that $3\cdot 3^{2}=3^{3}$, so we record a digit of 0 in the $3^{2}$ place of
$p$ and a digit of 1 in the $3^{3}$ place of $p$. The result of the algorithm
is therefore $7\cdot q=p$, which is given by the equation
$7\cdot(3^{1}+3^{0})=3^{3}+3^{0}$. It follows that
$7=\frac{p}{q}=\frac{[1001]_{3}}{[11]_{3}}$, the representation from (1.3). A
complete description of all possible representations of 7 is given by Theorem
2.4 Part (3) with $r=k=1$.

In general, we can perform the algorithm iteratively by following the steps
below, and in the case that $m=\frac{p}{q}\in\mathcal{A}/\mathcal{A}$, each
step $i$ produces the digit of the $i$th power of 3 in the base 3 expansions
of both $q$ and $p$. We record either $0\cdot 3^{i}$ or $1\cdot 3^{i}$ into
the base 3 expansions of $q$ and $p$ in the $i$th step, depending on the
result of the previous step, and then we consider the remaining unrecorded
value as carrying multiples of $3^{i+1}$ into the next step. We refer to the
number of copies of $3^{i+1}$ which are carried into the next step as the
carry value. As described in the following procedure, we use an initial carry
value of 0 in Step 0. The general algorithm is that for Step $i$, where $i\geq
1$:

  1. (1)

Determine the number of copies of $3^{i}$ recorded into the base 3 expansions
of $p$ and $q$ in Step $i$ by following the bullet point below which
corresponds to the carry value at the end of Step $i-1$.

     * •

If the carry value is congruent to $1\bmod 3$: record $0\cdot 3^{i}$ into $q$,
record $1\cdot 3^{i}$ into $p$, and subtract $1$ from the carry value.

     * •

If the carry value is congruent to $2\bmod 3$: add $m$ to the carry value,
record $1\cdot 3^{i}$ into $q$, and record $0\cdot 3^{i}$ into $p$.

     * •

If the carry value is congruent to $0\bmod 3$, we have a choice: either

       * –

add $m$ to the carry value, record $1\cdot 3^{i}$ into $q$, record $1\cdot
3^{i}$ into $p$, and subtract $1$ from the carry value (note: we always make
this choice at Step $0$), or

       * –

record $0\cdot 3^{i}$ into $q$, and record $0\cdot 3^{i}$ into $p$.

  2. (2)

After recording $0\cdot 3^{i}$ or $1\cdot 3^{i}$ into $p$ and $q$ according to
the conditions above and subtracting 1 from the carry value if necessary, the
result will be divisible by $3^{i+1}$. Factor out $3^{i+1}$ from this result,
and what remains is the new carry value at the end of Step $i$.

  3. (3)

Move to Step $i+1$ using this new carry value.

The algorithm terminates when either (i) the carry value is $w$, a sum of
distinct powers of 3, or (ii) all possible destinations from a given Step $i$
have already been visited without arriving at a sum of distinct powers of 3.

In Case (i), the base 3 expansion of the integer $q$ is complete when the
algorithm terminates, and the base 3 expansion of the integer $p$ is completed
by appending the base 3 representation of $w$ to the left of the values
already recorded for $p$. In our example $m=7$, the algorithm terminated when
we arrived at a carry value of 3 from $9*3^{1}=3*3^{2}$. The algorithm
terminated because the carry value $w=3$ is a sum of distinct powers of 3. We
then completed $p$ by appending $[{\bf 10}]_{3}$, the base 3 expansion of $3$,
to arrive at $7=\frac{[{\bf 10}01]_{3}}{[11]_{3}}$.

In Case (ii), the integer $m$ is not representable, because the algorithm
enters an infinite loop and never arrives at a finite quotient. This is
precisely what happens with $m=529$, $m=592$, $m=601$, $m=616$, and the other
integers that are congruent to $1\bmod 3$ and belong to the union given in
(1.2) but cannot be represented as quotients of sums of distinct powers of 3.

The remarks below provide additional justification as to why the algorithm
builds a representation of $m$ as $\frac{p}{q}$, where $p,q\in\mathcal{A}$.

  * •

The procedure builds the base 3 expansions of $q$ and $p$ one digit at a time
based on the powers of 3 required to obtain $mq=p$, where $p$ and $q$ are both
sums of distinct powers of 3. Since $p$ and $q$ cannot have any digits of 2 in
their base 3 expansions, we must add $m$ to any carry values congruent to
$2\bmod 3$ in order to record either $0\cdot 3^{i}$ or $1\cdot 3^{i}$ for $p$
in Step $i$. This addition corresponds to adding $1\cdot 3^{i}$ to $q$, since
then we will have added $m\cdot 3^{i}$ to the product $mq=p$. After adding
$m\equiv 1\pmod{3}$ to such a carry value in Part (1) of the algorithm, the
result will be divisible by $3^{i+1}$, so we may move to Part (2) of the
algorithm.

  * •

The carry value is the part of the remaining unrecorded value, after recording
$0\cdot 3^{i}$ or $1\cdot 3^{i}$ into $p$ in Step $i$, which carries multiples
of $3^{i+1}$ into the next step. For this reason, we must subtract $1$ from
the carry value every time we record $1\cdot 3^{i}$ into $p$, so that what
remains is the part of the carry value which was unrecorded in Step $i$.

  * •

When a carry value is congruent to $0\bmod 3$, the two choices in Part (1) of
the algorithm correspond to the two different ways of arriving at a multiple
of $3^{i+1}$ to be carried from Step $i$ into Step $i+1$. The first way is to
add $m$ to the carry value and correspondingly record $1\cdot 3^{i}$ into $q$,
then subtract $1\cdot 3^{i}$ from the carry value after recording a digit of
$1$ into the $3^{i}$ place of $p$, and move to Part (2) of the algorithm with
the resulting multiple of $3^{i+1}$. The second way is to simply factor out
another 3 from the carry value, which is divisible by 3 in this case, to get a
multiple of $3^{i+1}$.

The algorithm can be illustrated through a directed graph with the carry
values as vertices. We present the graph for $m=22$ in Figure 1. In Example
1.6, we discuss how to use the directed graph to obtain representations of
$22$ as a quotient.

######  Example 1.6.

Let’s consider the algorithm for $m=22$. We will use Figure 1 to keep track of
what happens in each step.

072810$\displaystyle\mathbf{\frac{1}{1}}$$\displaystyle\frac{\mathbf{1}{\color[rgb]{0.5,0.5,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0.5,0.5}1}}{\mathbf{0}{\color[rgb]{0.5,0.5,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0.5,0.5}1}}$$\displaystyle\frac{\mathbf{0}{\color[rgb]{0.5,0.5,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0.5,0.5}11}}{\mathbf{1}{\color[rgb]{0.5,0.5,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0.5,0.5}01}}$$\displaystyle\frac{\mathbf{0}{\color[rgb]{0.5,0.5,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0.5,0.5}011}}{\mathbf{1}{\color[rgb]{0.5,0.5,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0.5,0.5}101}}$
Figure 1. Directed graph of the steps of the algorithm for $m=22$.

  * •

Step $0$: As always, we start with a carry value of 0, which is congruent to
$0\bmod 3$, and we choose to add $m=22$ to the carry value, record $1\cdot
3^{0}$ into $q$ and into $p$, subtract 1 from the carry value accordingly, and
move to Step $1$. The remaining unrecorded value is $(22-1)\cdot 3^{0}=21\cdot
3^{0}=7\cdot 3^{1}$, which yields a carry value of $7$. Note that in Figure 1,
Step 0 corresponds to the edge from the vertex 0 to the vertex 7, which is the
new carry value, and the label on the edge denotes the $3^{0}$ digits of the
base 3 expansions of $p$ (in the numerator) and $q$ (in the denominator).

  * •

Step $1$: The carry value is $7\equiv 1\pmod{3}$. We record $0\cdot 3^{1}$
into $q$ and $1\cdot 3^{1}$ into $p$, and we subtract 1 from the carry value
accordingly. The remaining unrecorded value is now $(7-1)\cdot 3^{1}=6\cdot
3^{1}=2\cdot 3^{2}$, which yields a carry value of $2$. In Figure 1, Step 1
corresponds to the edge from the vertex 7 to the vertex 2, the new carry
value, and the new recorded digits in the edge label, $p$ in the numerator and
$q$ in the denominator, are the $3^{1}$ digits.

  * •

Step $2$: The carry value is $2\equiv 2\bmod 3$. We add $m=22$ to the carry
value, record $1\cdot 3^{2}$ into $q$, and record $0\cdot 3^{2}$ into $p$. The
remaining unrecorded value at this step is $(2+22)\cdot 3^{2}=24\cdot
3^{2}=8\cdot 3^{3}$, which yields a carry value of $8$. Step 2 corresponds to
the edge from the vertex 2 to the vertex 8 with the $3^{2}$ digits of $p$ and
$q$ recorded.

  * •

Step $3$: The carry value is $8\equiv 2\pmod{3}$, so we again add $m=22$ to
the carry value, record $1\cdot 3^{3}$ into $q$, and record $0\cdot 3^{3}$
into $p$. The remaining unrecorded value is $(8+22)\cdot 3^{3}=30\cdot
3^{3}=10\cdot 3^{4}$, which yields a carry value of $10$. Step 3 corresponds
to the edge from the vertex 8 to the vertex 10 with the $3^{3}$ digits of $p$
and $q$ recorded.

  * •

Step $4$: The carry value is $10=3^{2}+3^{0}$, which is a sum of distinct
powers of 3, so the algorithm terminates.

At this point, we append the base 3 representation of $10$, $[101]_{3}$, to
the left of the digits for $p$, and we arrive at the final quotient
$22=\frac{[1010011]_{3}}{[1101]_{3}}$.

In the example $m=22$, for vertices congruent to $0\bmod 3$, we make the first
choice in the description of the algorithm (adding $m$) only in the first
step, as the second option would loop back to the vertex 0 and keep us from
moving toward our goal of obtaining a representation of $m$. If we continued
beyond the carry value of 10 to draw edges for all possible paths originating
at the vertex 0, we would have the extended graph in Figure 2. Such an
extended graph shows all representations of an integer $m$. The particular
representation of $m=22$ constructed above by stopping after the carry value
of 10 is the same representation we obtain from following the path
$0\rightarrow 7\rightarrow 2\rightarrow 8\rightarrow 10\rightarrow
3\rightarrow 1\rightarrow 0$ in Figure 2, since the subpath $10\rightarrow
3\rightarrow 1\rightarrow 0$ appends the same digits to $p$ as the digits in
the base 3 representation of 10. We see this by observing that the subpath
$10\rightarrow 3\rightarrow 1\rightarrow 0$ contributes no digits to $q$ while
contributing to $p$ the digits 101.

07281031 Figure 2. The subgraph of the multiplication transducer for $m=22$ in
base 3 that encodes all representations of $22$ as a quotient of sums of
distinct powers of 3.

In general, the algorithm serves two main purposes for this paper. First, if
the algorithm terminates for a given integer $m\equiv 1\pmod{3}$, as in Step 4
of Example 1.6, then the algorithm proves that $m$ is representable. Second,
if all possible paths back to $0$ are included in the graph produced by the
algorithm for a given $m$, then the algorithm provides an explicit
construction of all representations of $m$. The directed graph involves two
branches corresponding to the two choices in the algorithm. Next we will
discuss the additional information about an integer $m$ and its
representations that can be gleaned from an extended graph.

The graph in Figure 1 is a subgraph of the graph in Figure 2, while the graph
in Figure 2 can be generated as a subgraph of a multiplication transducer. A
multiplication transducer, as described in [4], is a finite state automaton
which performs the operation of multiplication by $m$ in base $b$ for any
given positive integers $m$ and $b$. The multiplication transducer that
performs multiplication by $m$ in base 3 can multiply $m\cdot q=p$ for any
positive integer $q$ as follows: by reading the digits of the base 3
representation of $q$ from right to left, following the directed edges of the
graph, and recording the digits of $p$ after each step. This process continues
until all digits have been read and the value carried over from the previous
step is 0. As noted, the graph in Figure 2 is a subgraph of the multiplication
transducer that multiplies by $m=22$ in base 3, and this subgraph can be
generated from the transducer as follows: by restricting edges to those that
generate $q,p\in\mathcal{A}$ and subsequently restricting vertices to the
carry values that are possible steps in the computation $m\cdot q=22\cdot q=p$
for $q,p\in\mathcal{A}$.

When exploring the representations of an integer $m$ through an expanded graph
that includes the path back to the vertex 0, such as Figure 2, we can generate
all possible representations of $m$ as a quotient of sums of distinct powers
of 3. Each representation corresponds to a specific closed walk through the
vertices of the digraph, starting and ending at the vertex 0. We note that a
closed walk must include at least one step away from the vertex 0 in order to
correspond to a valid representation, and by restricting our attention to
elements of $\mathcal{A}$, we ensure that the initial step away from the
vertex 0 will never be from the vertex 0 to itself. In the example above, we
outlined the representation
$22=\frac{[1010011]_{3}}{[1101]_{3}}=\frac{814}{37}$, but taking a different
closed walk, stepping up from the vertex 3 to the vertex 8 before returning to
the vertex 0 in Figure 2, would give the representation
$22=\frac{[1010110011]_{3}}{[1101101]_{3}}=\frac{22198}{1009}$.

######  Definition 1.7.

An indecomposable walk is a closed walk through the graph that contains the
vertex 0 as the initial point and terminal point but not as an interior point,
and an indecomposable representation is a representation corresponding to such
a walk. A decomposable walk is a closed walk through the graph that contains
the vertex 0 not only as the initial point and terminal point but also as an
interior point, and a decomposable representation is a representation
corresponding to a decomposable walk.

In the example of $m=22$, the representations given in the paragraph above
Definition 1.7 are indecomposable representations, while
$22=\frac{[1010011\underline{1010011}]_{3}}{[1101\underline{0001101}]_{3}}$ is
an example of a decomposable representation. In general, a decomposable
representation can be thought of as the concatenation of multiple
indecomposable representations written in base 3. Before concatenating, we
append copies of the digit 0 to the denominator of each indecomposable
representation to make the lengths of the numerator and denominator match. To
create the decomposable representation we gave for $m=22$, we concatenated two
copies of $\frac{[1010011]_{3}}{[1101]_{3}}$, appending three digits of 0 as
placeholders in the denominator of the first (underlined) copy. This can also
be thought of in base 10 as creating the representation $22=\frac{3^{7}\cdot
814+814}{3^{7}\cdot 37+37}$. In other words, a decomposable representation can
be written as $\frac{3^{k}p_{1}+p_{2}}{3^{k}q_{1}+q_{2}}$ for two
representations $m=\frac{p_{1}}{q_{1}}$ and $m=\frac{p_{2}}{q_{2}}$, where $k$
is at least the length of the base 3 representation of $p_{2}$.

##  2\. Integers with only universal representations

In our exploration of representations of integers as quotients of sums of
distinct powers of 3, we have encountered many integers $m\equiv 1\pmod{3}$
which have only universal representations. We devote this section to such
integers. We begin in Section 2.1 by describing how to build new universal
representations from a given universal representation. In Section 2.2, we
prove that four infinite families of integers have only universal
representations. Finally, we investigate the representations of integers of
the form $m=3^{n}-2$ in Section 2.3 and of $m=100$ in Section 2.4.

###  2.1. Tools for Building New Representations

Given a representation of an integer $m$ as a quotient of sums of distinct
powers of 3, there are several ways we can generate new representations. Some
aspects of this study can be handled quickly, using only properties of the set
$\mathcal{P}$. Before proceeding, it will be helpful to adopt an alternative
description of Newman polynomials and to establish two lemmas. Write

$p(x)=1+\sum_{k=1}^{r-1}\epsilon_{k}x^{k}+x^{r}=\sum_{j=0}^{m}x^{a_{j}},$

where $0=a_{0}<a_{1}<\cdots<a_{m}=r$, and let $\Delta(p):=\\{a_{i}-a_{j}:0\leq
j<i\leq m\\}$. The following lemma identifies exactly when a product of Newman
polynomials is itself a Newman polynomial.

######  Lemma 2.1.

Suppose $s(x),t(x)\in\mathcal{P}$. Then $(st)(x)\in\mathcal{P}$ if and only if
$\Delta(s)\cap\Delta(t)=\emptyset$.

###### Proof.

If $s(x)=\sum\limits_{k=0}^{m}x^{a_{k}}$ and
$t(x)=\sum\limits_{\ell=0}^{n}x^{b_{\ell}}$, then
$(st)(x)=\sum\limits_{k=0}^{m}\sum\limits_{\ell=0}^{n}x^{a_{k}+b_{\ell}}$. The
coefficient of $x^{j}$ in $(st)(x)$ is the number of times that
$a_{k}+b_{\ell}=j$, which is always non-negative and is in $\\{0,1\\}$ if and
only if $a_{k}+b_{\ell}=a_{k^{\prime}}+b_{\ell^{\prime}}$ implies
$k=k^{\prime}$ and $\ell=\ell^{\prime}$. This happens if and only if
$a_{k}-a_{k^{\prime}}=b_{\ell^{\prime}}-b_{\ell}$ is equivalent to
$k=k^{\prime}$ and $\ell=\ell^{\prime}$, which happens if and only if
$\Delta(s)\cap\Delta(t)=\emptyset$. ∎

We remark here that one simple way to avoid common exponent gaps between two
Newman polynomials $s(x),t(x)$ is to require that all exponent gaps in $s(x)$
are greater than the degree of $t(x)$, or vice versa. This is a recurring idea
in this paper and will be referenced several times in the remainder of this
subsection as well as in the proof of Theorem 2.6.

We now present a different version of Lemma 2.1 which can be used to view
exponent gaps within Newman polynomials more generally from the perspective of
universal representations. This lemma can be proved by a direct computation,
which is omitted.

######  Lemma 2.2.

Suppose $p_{j}(x),q_{j}(x)\in\mathcal{P}$ for all $1\leq j\leq w$ and
$p(x)=\sum_{j}x^{n_{j}}p_{j}(x),q(x)=\sum_{j}x^{n_{j}}q_{j}(x)\in\mathcal{P}$,
with no other conditions on the non-negative integers $n_{j}$. Suppose further
that $\frac{p_{j}(x)}{q_{j}(x)}=t(x)$ for all $j$. Then
$\frac{p(x)}{q(x)}=t(x)$ as well. Similarly, if
$\frac{p_{j}(3)}{q_{j}(3)}=t(3)=m$ for all $j$, then $\frac{p(3)}{q(3)}=m$.

Note that if we impose the additional condition that
$n_{j}>\deg\left(\sum_{i<j}x^{n_{i}}p_{i}(x)\right)$ for each $j$, then we
obtain a special case of Lemma 2.2 that will be applied in the proof of
Theorem 2.6 to prove the universality of some representations of $100$.

Equipped with these lemmas, we now discuss two ways to build new
representations from a given representation. First, we can generate additional
representations of the same integer $m$. Every integer having one
representation in fact has infinitely many representations. Suppose
$m=\frac{p(3)}{q(3)}$, where $p(x),q(x)\in\mathcal{P}$ and $\deg p(x),\deg
q(x)\leq T$. If $f(x)$ is any polynomial in $\mathcal{A}$ for which the gaps
in exponents are greater than $T$, then the exponent gaps in $f(x)$ ensure
that there are no possible cross-terms in the products $(fp)(x)$ and
$(fq)(x)$. By Lemma 2.1, we have that $(fp)(x),(fq)(x)\in\mathcal{A}$, and so
$m=\frac{(fp)(3)}{(fq)(3)}$, giving a new representation of the same integer
$m$, and this new representation is decomposable.

Secondly, we can work with a given representation of $m$ to obtain
representations of other integers. Suppose
$m=\frac{p(3)}{q(3)}\in\mathcal{A}/\mathcal{A}$ and $f(x)\in\mathcal{P}$ is
any polynomial for which $\Delta(f)\cap\Delta(p)=\emptyset$. Then
$(fp)(x)\in\mathcal{P}$ by Lemma 2.1, so, multiplying $m$ by $f(x)$ and
evaluating at $x=3$, we have that $f(3)\cdot m=\frac{(fp)(3)}{q(3)}$ is in
$\mathcal{A}/\mathcal{A}$ and is a representation not of $m$ but of $f(3)\cdot
m$. A particular type of polynomial $f(x)$ that will yield such a
representation of a new integer is a polynomial $f(x)$ with exponent gaps
larger than the degree of $p(x)$. More explicitly, if $\deg p(x)=r$ and
$f(x)\in\mathcal{P}$ such that $\min\Delta(f)>r$, then $(fp)(x)\in\mathcal{P}$
and thus $f(3)\cdot m\in\mathcal{A}/\mathcal{A}$.

###  2.2. Special families

This section is dedicated to proving that several infinite families of
integers $m\equiv 1\pmod{3}$ have only universal representations and,
moreover, that those universal representations must have a specific form.
There are certain values of $m$ for which the representation
$m=\frac{p(3)}{q(3)}\in\mathcal{A}/\mathcal{A}$ gives very strong conditions
on $p(x)$ and $q(x)$, and the following lemma will be useful as we prove these
conditions.

######  Lemma 2.3.

Let $\mathcal{C},\mathcal{D}$ be sets of integers, and suppose one of the
following two cases holds:

  * •

Case 1: $\mathcal{C}=\mathcal{D}=\\{n,n+1,n+2\\}$, where $n\in\mathbb{Z}$;

  * •

Case 2: $\mathcal{C}=\\{0,1\\}\ \text{and}\ \mathcal{D}=\\{-1,0,1,2\\}$.

Let $a(x)=\sum_{i}a_{i}x^{i}$ and $b(x)=\sum_{i}b_{i}x^{i}$, where
$a_{i}\in\mathcal{C}$ and $b_{i}\in\mathcal{D}$. If $a(3)=b(3)$, then
$a_{i}=b_{i}$ for all $i$, so $a(x)=b(x)$.

###### Proof.

We prove the result by induction on $\operatorname{max}\\{\deg a(x),\deg
b(x)\\}$; the assertion is clear when this maximum is 0. Since $a(3)=b(3)$, we
know $\sum_{i}a_{i}3^{i}=\sum_{i}b_{i}3^{i}$, and this gives $a_{0}\equiv
b_{0}\pmod{3}$. In the first case, this means that $a_{0}=b_{0}$; we may write
$a(x)=a_{0}+x\tilde{a}(x)$ and $b(x)=b_{0}+x\tilde{b}(x)$ and apply the
inductive argument to $\tilde{a},\tilde{b}$. In the second case, we first note
that $b_{0}\notin\\{-1,2\\}$ and, again, $a_{0}=b_{0}$ and repeat the
argument. ∎

These results allow us to make explicit statements about representations of
certain special families of integers congruent to $1\bmod 3$. If $m$ belongs
to one of the families described below in Theorem 2.4, then $m$ has only
universal representations, and they must be of a particular kind.

######  Theorem 2.4.

Let $p(x),q(x)\in\mathcal{P}$.

  1. (1)

If $3^{r}+1=\frac{p(3)}{q(3)}$, then $p(x)=(x^{r}+1)q(x)$.

  2. (2)

If $3^{rk}+3^{(r-1)k}+\dots+3^{k}+1=\frac{p(3)}{q(3)}$, then

$p(x)=(x^{rk}+x^{(r-1)k}+\dots+x^{k}+1)q(x)=\frac{x^{(r+1)k}-1}{x^{k}-1}q(x).$

  3. (3)

If $3^{2rk}-3^{(2r-1)k}+\dots-3^{k}+1=\frac{p(3)}{q(3)}$, then

$p(x)=(x^{2rk}-x^{(2r-1)k}+\dots-x^{k}+1)q(x)=\frac{x^{(2r+1)k}+1}{x^{k}+1}q(x).$

  4. (4)

If $r>s>0$ and $3^{r}-3^{s}+1=\frac{p(3)}{q(3)}$, then

$p(x)=(x^{r}-x^{s}+1)q(x).$

In each of these four cases, there exist $p(x),q(x)\in\mathcal{P}$ which
satisfy the particular condition.

###### Proof.

The proofs of the various parts of this theorem are similar and begin by
letting $p(x),q(x)\in\mathcal{P}.$

For Part 1, assume $3^{r}+1=\frac{p(3)}{q(3)}$, and consider the polynomials
$p(x)$ and $(x^{r}+1)q(x)$. Observe that the coefficients of $p(x)$ are in
$\\{0,1\\}$ and the coefficients of $(x^{r}+1)q(x)$ are in $\\{0,1,2\\}$.
Since $p(3)=(3^{r}+1)q(3)$, we know from Lemma 2.3 that $p(x)=(x^{r}+1)q(x)$.
A simple example with $p(x),q(x)\in\mathcal{P}$ comes from taking $q(x)=1$.

Similarly, in Part 2, assume
$3^{rk}+3^{(r-1)k}+\dots+3^{k}+1=\frac{p(3)}{q(3)}$, and consider the
polynomials $(x^{k}-1)p(x)$ and $(x^{(r+1)k}-1)q(x)$. Since
$p(x),q(x)\in\mathcal{P}$, it follows that both $(x^{k}-1)p(x)$ and
$(x^{(r+1)k}-1)q(x)$ have coefficients in $\\{-1,0,1\\}$. We take their
quotient at $x=3$ and use the hypothesis regarding $\frac{p(3)}{q(3)}$ to
obtain

$\frac{(3^{(r+1)k}-1)q(3)}{(3^{k}-1)p(3)}=\frac{(3^{(r+1)k}-1)}{(3^{k}-1)}\left(\frac{p(3)}{q(3)}\right)^{-1}=\frac{3^{(r+1)k}-1}{3^{(r+1)k}-1}=1.$

Thus $(3^{k}-1)p(3)=(3^{(r+1)k}-1)q(3)$, and it follows from Lemma 2.3 that
$(x^{k}-1)p(x)=(x^{(r+1)k}-1)q(x)$. Again, a simple example with
$p(x),q(x)\in\mathcal{P}$ comes from taking $q(x)=1$.

In Part 3, assume $3^{2rk}-3^{(2r-1)k}+\dots-3^{k}+1=\frac{p(3)}{q(3)}$, and
consider the polynomials $(x^{k}+1)p(x)$ and $(x^{(2r+1)k}+1)q(x)$. The
coefficients of these products are in $\\{0,1,2\\}$. As in the proof of Part
2, we take the quotient of these two polynomials at $x=3$ and use the
hypothesis regarding $\frac{p(3)}{q(3)}$ to obtain

$(3^{k}+1)p(3)=(3^{(2r+1)k}+1)q(3).$

Again by Lemma 2.3, it follows that $(x^{k}+1)p(x)=(x^{(2r+1)k}+1)q(x)$. As an
example, take $q(x)=x^{k}+1$. Then $p(x)=x^{(2r+1)k}+1$, and we can see that
$p(x),q(x)\in\mathcal{P}$, and
$\frac{p(x)}{q(x)}=x^{2rk}-x^{(2r-1)k}+\dots-x^{k}+1$.

Lastly, in Part 4, assume $3^{r}-3^{s}+1=\frac{p(3)}{q(3)}$, and consider the
polynomials $p(x)$ and $(x^{r}-x^{s}+1)q(x)$. By hypothesis
$p(x),q(x)\in\mathcal{P}$, so we can write
$q(x)=\sum\limits_{j=0}^{v}x^{b_{j}}$, and

$(x^{r}-x^{s}+1)q(x)=(x^{r}+1)\left(\sum_{j=0}^{v}x^{b_{j}}\right)-x^{s}\left(\sum_{j=0}^{v}x^{b_{j}}\right).$

We see that $(x^{r}-x^{s}+1)q(x)$ is the difference of a polynomial with
coefficients in $\\{0,1,2\\}$ and a polynomial with coefficients in
$\\{0,1\\}$, so the coefficients of $(x^{r}-x^{s}+1)q(x)$ are in
$\\{-1,0,1,2\\}$. Since $p(3)=(3^{r}-3^{s}+1)q(3)$, we can use Lemma 2.3 one
final time to conclude that $p(x)=(x^{r}-x^{s}+1)q(x)$. Finally, an example
comes from taking $q(x)=x^{r-1}+\cdots+x+1$, and then
$p(x)=x^{2r-1}+\cdots+x^{r+s}+x^{s-1}+\cdots+x+1$. ∎

Among the integers congruent to $1\bmod 3$ and less than or equal to $121$,
the following are covered by one or more of the parts of Theorem 2.4 and thus
have only universal representations: 4, 7, 10, 13, 19, 25, 28, 40, 55, 61, 73,
79, 82, 91, 121. The integers in intervals excluded by Theorem 1.2 are 16, 43,
46, 49, 52. This leaves open 22, 31, 34, 37, 58, 64, 67, 70, 76, 85, 88, 94,
97, 103, 106, 109, 112, 115, 118. The first open two have quite different
behavior; as we shall see in Section 3.1, 22 has only local representations,
but we already know from Example 1.3 that 31 can go either way!

###  2.3. Integers of the form $3^{n}-2$

Here we describe the representations of integers of the form $m=3^{n}-2$,
where $n\geq 3$. First note that any integer of this form is covered by
Theorem 2.4 Part 4, since $3^{n}-2=3^{n}-3+1$. Hence we know that all
representations of such an integer must be universal. We now describe all
possible representations for $m=3^{n}-2$ and give the specific polynomials
$p(x)$ and $q(x)$ such that $m=\frac{p(3)}{q(3)}$.

Suppose that $m=3^{n}-2=\frac{p(3)}{q(3)}$, where
$p(x)=1+\sum\limits_{i=1}^{w-1}c_{i}x^{i}+x^{w}$ and
$q(x)=1+\sum\limits_{i=1}^{s-1}d_{i}x^{i}+x^{s}$ with
$c_{i},d_{i}\in\\{0,1\\}$. Let $g(x):=\frac{p(x)}{q(x)}\in\mathbb{Z}[x]$. Then
by Theorem 1.2, we know

$\frac{2}{3}\cdot 3^{w-s}<3^{n}-2<\frac{3}{2}\cdot 3^{w-s},$

so $n=w-s=\deg g(x)$.

Since the constant terms and the coefficients of $x^{w}$ in $p(x)$ and $x^{s}$
in $q(x)$ are 1, we may then write
$g(x)=1+\sum\limits_{i=1}^{n-1}e_{i}x^{i}+x^{n}$. Equating coefficients of
powers of $x$ in $p(x)=g(x)q(x)$ now gives the system of equations

$c_{i}=\begin{cases}d_{i}+e_{i}&\mbox{if }i=1,\\\
d_{i}+\sum\limits_{j=1}^{i-1}d_{i-j}e_{j}+e_{i}&\mbox{if }1<i<n,\\\
d_{i}+\sum\limits_{j=1}^{i-1}d_{i-j}e_{j}+1&\mbox{if }i=n,\\\
d_{i}+\sum\limits_{j=1}^{n-1}d_{i-j}e_{j}+d_{i-n}&\mbox{if }n<i\leq
w.\end{cases}$

We now use this system of equations to determine the coefficients
$c_{i},d_{i}$, and $e_{i}$ in the polynomials $p(x),q(x)$, and $g(x)$. We will
approach this in sections:

  * •

We first consider the coefficients corresponding to $i=1$ and then $2\leq
i\leq n-1$.

  * •

Next, we consider the coefficients corresponding to $i=n$.

  * •

After dealing with $i=n$, we reach a point where we can choose either to
continue toward the end of the algorithm or to carry the value $\frac{m-1}{2}$
repeatedly before continuing. We consider the choice of carrying
$\frac{m-1}{2}$ repeatedly $k$ times, for $n+1\leq i\leq n+k$.

  * •

We then consider the remaining coefficients, when $n+k<i$.

We begin by considering $g(3)$. Since

$\displaystyle 3^{n}-2=g(3)$
$\displaystyle=1+3e_{1}+9e_{2}+27e_{3}+\cdots+3^{n-1}e_{n-1}+3^{n},$
$\displaystyle-3$ $\displaystyle=3e_{1}+9e_{2}+27e_{3}+\cdots+3^{n-1}e_{n-1},$
$\displaystyle-1$ $\displaystyle=e_{1}+3e_{2}+9e_{3}+\cdots+3^{n-2}e_{n-1},$

so $e_{1}\equiv 2\pmod{3}$. Since $e_{1}=c_{1}-d_{1}$, we see
$c_{1}=0,d_{1}=1$, and $e_{1}=-1$. Next observe that $3e_{2}\equiv 0\pmod{9}$,
so $e_{2}\equiv 0\pmod{3}$. The second equation in our system is
$c_{2}=d_{2}-1+e_{2}$. Since $c_{2},d_{2}\in\\{0,1\\}$, we must have
$c_{2}=0,d_{2}=1$, and $e_{2}=0$.

Suppose that $2\leq i\leq n-1$ and that for all $j$ with $2\leq j<i$, we have
$c_{j}=0,d_{j}=1$, and $e_{j}=0$. Consider the $i$-th equation

$c_{i}=d_{i}+d_{i-1}e_{1}+d_{i-2}e_{2}+\cdots+d_{2}e_{i-2}+d_{1}e_{i-1}+e_{i}.$

This is

$c_{i}=d_{i}+1(-1)+1(0)+\cdots+1(0)+1(0)+e_{i},$

or, more simply, $c_{i}=d_{i}-1+e_{i}$. We know $3^{i-1}e_{i}\equiv
0\pmod{3^{i}}$, so $e_{i}\equiv 0\pmod{3}$. Then $c_{i}=0,d_{i}=1$, and
$e_{i}=0$. Thus we have $c_{1}=0,d_{1}=1$, and $e_{1}=-1$; and
$c_{2}=\cdots=c_{n-1}=0,d_{2}=\cdots=d_{n-1}=1$, and $e_{2}=\cdots=e_{n-1}=0$.

Now consider the $n$-th equation

$c_{n}=d_{n}+d_{n-1}e_{1}+d_{n-2}e_{2}+\cdots+d_{2}e_{n-2}+d_{1}e_{n-1}+1.$

This is

$c_{n}=d_{n}+1(-1)+0+\cdots+0+0+1,$

so $c_{n}=d_{n}$. We have
$g(x)=1+\sum\limits_{i=1}^{n-1}e_{i}x^{i}+x^{n}=1-x+x^{n}$.

As we complete the description of representations of $3^{n}-2$, we will refer
to the digraph in Figure 3. Choosing $c_{n}=d_{n}=0$ uniquely determines a
universal representation for $3^{n}-2$, and it is the same representation that
comes from choosing to carry $\frac{m-1}{6}$ at the first possible opportunity
after carrying $\frac{m-1}{2}$ (without ever taking the loop at the vertex
$\frac{m-1}{2}$ in Figure 3). It is straightforward to prove by induction that
$\frac{m-1}{6}$ is a sum of distinct powers of 3 when $m=3^{n}-2$, and
therefore choosing to carry $\frac{m-1}{6}$ without taking the loop leads to
the immediate termination of the algorithm.

01$\displaystyle\frac{m-3}{2}$$\displaystyle\frac{m-1}{2}$$\displaystyle\frac{m-1}{3}$4$\displaystyle\frac{m-1}{6}$……
Figure 3. The subgraph of the multiplication transducer for $m=3^{n}-2$ with
$n\geq 3$ in base $3$ that encodes all representations of $m$ as a quotient of
sums of distinct powers of 3.

We now show that choosing to take the loop $k$ times for any positive integer
$k$ will still result in a universal representation. Suppose we choose
$c_{n}=d_{n}=1$. Then the $(n+1)$-th equation in our system is

$c_{n+1}=d_{n+1}+d_{n}e_{1}+d_{n-1}e_{2}+\cdots+d_{2}e_{n-1}+d_{1},$

which is

$c_{n+1}=d_{n+1}+1(-1)+0\cdots+0+1,$

so $c_{n+1}=d_{n+1}$. Choose $c_{n+1}=d_{n+1}=1$. The $(n+2)$-th equation is

$c_{n+2}=d_{n+2}+d_{n+1}e_{1}+d_{n}e_{2}+\cdots+d_{3}e_{n-1}+d_{2},$

which is

$c_{n+2}=d_{n+2}+1(-1)+0+\cdots+0+1,$

so $c_{n+2}=d_{n+2}$. In general, suppose that $i\geq 1$ and for all $1\leq
j<i$, we have chosen $c_{n+j}=d_{n+j}=1$. Then the $(n+i)$-th equation is

$c_{n+i}=d_{n+i}+d_{n+i-1}e_{1}+d_{n+i-2}e_{2}+\cdots+d_{i+1}e_{n-1}+d_{i},$

which is

$c_{n+i}=d_{n+i}+1(-1)+0+\cdots+0+1,$

so $c_{n+i}=d_{n+i}$. Suppose that for all $i$ with $1\leq i\leq k-1$, we
choose $c_{n+i}=d_{n+i}=1$. Then we have $c_{1}=0,d_{1}=1$, and $e_{1}=-1$;
and
$c_{2}=\cdots=c_{n-1}=0,c_{n}=\cdots=c_{n+k-1}=1,d_{2}=\cdots=d_{n-1}=1,d_{n}=\cdots=d_{n+k-1}=1$,
and $e_{2}=\cdots=e_{n-1}=0$. Then the $(n+k)$-th equation is

$c_{n+k}=d_{n+k}+d_{n+k-1}e_{1}+d_{n+k-2}e_{2}+\cdots+d_{k+1}e_{n-1}+d_{k},$

which is

$c_{n+k}=d_{n+k}+1(-1)+0+\cdots+0+1,$

so $c_{n+k}=d_{n+k}$. We have now taken the loop from the vertex
$\frac{m-1}{2}$ to itself $k$ times. We choose $c_{n+k}=d_{n+k}=0$ to stop
taking the loop and allow the algorithm to terminate. Similar arguments to
those outlined above show that $c_{n+k+1}=\cdots=c_{n+k+(n-1)}=1$ and
$d_{n+k+1}=\cdots=d_{n+k+(n-1)}=0$. Then we use the values we found for the
coefficients $c_{i}$ and $d_{i}$ to write down the polynomials involved in the
representation of $3^{n}-2$ that corresponds to taking the loop $k$ times.
These polynomials are
$p_{k}(x)=1+x^{n}+\cdots+x^{n+k-1}+x^{n+k+1}+\cdots+x^{n+k+(n-1)}$ and
$q_{k}(x)=1+x+\cdots+x^{n+k-1}$. We have $3^{n}-2=\frac{p_{k}(3)}{q_{k}(3)}$,
and $x^{n}-2=\frac{p_{k}(x)}{q_{k}(x)}$, giving a universal representation for
$3^{n}-2$, and we note that we can obtain such a representation for any
positive integer k.

###  2.4. Representations of 100

Now let us consider $m=100$, which is not covered by any of the theorems
previously established in this section. In fact, $m=100$ is the smallest
integer that has only universal representations but is not covered by these
theorems.

Following the algorithm for $m=100$, we note that at the end of Step 1 we have
a carry value of $33$. As stated in Section 1.2, whenever the carry value is a
multiple of 3, we have a choice of two directions. Here, in Step $2$, we have
a choice to move forward carrying either $44$ or $11$. We will refer to these
choices in general as a step up and a step down from the current carry value,
where the step up corresponds to the choice to add $m$ to the carry value and
record $1\cdot 3^{i}$ into $q$ and into $p$, while the step down corresponds
to the choice to record $0\cdot 3^{i}$ into $q$ and into $p$. Returning to the
algorithm for $100$, we see in Figure 4 that if we choose to step up from 33
and move forward carrying $44$, this will never lead us back to 0. Thus, in an
effort to continue our search for representations of $100$, we step down from
$33$ to $11$.

033113712414448164953545153846 Figure 4. The subgraph of the multiplication
transducer for $m=100$ that encodes all representations of $100$ as a quotient
of sums of distinct powers of 3.

Continuing with the algorithm, our next carry value is $37=3^{3}+3^{2}+3^{0}$,
a sum of distinct powers of 3. According to the algorithm, we now record
$100=\frac{[{\bf 1101}001]_{3}}{\hskip 12.67pt[101]_{3}}$, where the rightmost
three digits in both the numerator and denominator come from the three steps
carrying 0, then $33$, then $11$, and the remaining bold digits in the
numerator come from appending $[1101]_{3}$, the base 3 expansion of 37, to
$p$. We have $100=\frac{3^{6}+3^{5}+3^{3}+1}{3^{2}+1}$, and with
$p(x)=x^{6}+x^{5}+x^{3}+1$ and $q(x)=x^{2}+1$, this is
$100=\frac{p(3)}{q(3)}$. Is this a universal representation or a local
representation? Since $p(x)=(x^{4}+x^{3}-x^{2}+1)q(x)$, this representation is
universal.

As soon as we reach a carry value that is a sum of distinct powers of 3, in
this case the carry value 37, the algorithm takes the shortest possible path
back to 0 by always choosing to step down when the carry value is congruent to
$0\bmod 3$. We could obtain other indecomposable representations of $100$ by
deviating from the algorithm and instead choosing to step up from 12, possibly
repeatedly, and each step up from $12$ would create a two-step loop in the
journey back to 0. In fact, we could obtain infinitely many indecomposable
representations in this fashion. Would they be all universal, all local, or
some of each?

######  Theorem 2.5.

Every indecomposable representation of $100$ is universal. Moreover, for any
indecomposable representation of $100$ as $\frac{p(3)}{q(3)}$, the quotient
$\frac{p(x)}{q(x)}$ is $x^{4}+x^{3}-x^{2}+1$.

###### Proof.

As noted above, taking a step up from $33$ does not lead to a representation
of $100$. Also noted above, if we step down the first time we encounter a
carry value of $12$, we obtain a universal representation. Instead, suppose
that when we first encounter a carry value of $12$, we step up from $12$ to
$37$, follow the two-step loop exactly once, and then continue as usual. This
yields the recorded quotient

$100=\frac{[{110}\underline{11}1001]_{3}}{\hskip
15.00002pt[\underline{01}0101]_{3}}=\frac{3^{8}+3^{7}+3^{5}+3^{4}+3^{3}+1}{3^{4}+3^{2}+1}.$

If we step up from $12$ to $37$ exactly twice and then continue, we record

$100=\frac{[{110}\underline{1111}1001]_{3}}{\hskip
15.00002pt[\underline{0101}0101]_{3}}=\frac{3^{10}+3^{9}+3^{7}+3^{6}+3^{5}+3^{4}+3^{3}+1}{3^{6}+3^{4}+3^{2}+1}.$

To generalize, after stepping up from 12 to $37$ exactly $j$ times, which
means taking the two-step loop in Figure 4 exactly $j$ times, we have

$100=\frac{3^{4+2j+2}+3^{4+2j+1}+\displaystyle\sum_{k=4}^{4+2j-1}3^{k}+3^{3}+1}{\displaystyle\sum_{i=1}^{j}3^{2+2i}+3^{2}+1}.$

For any $j\geq 0$, let
$p_{j}(x)=x^{4+2j+2}+x^{4+2j+1}+\sum\limits_{k=4}^{4+2j-1}x^{k}+x^{3}+1$ and
$q_{j}(x)=\sum\limits_{i=1}^{j}x^{2+2i}+x^{2}+1$. We will show by induction
that $p_{j}(x)=(x^{4}+x^{3}-x^{2}+1)q_{j}(x)$ for any $j\geq 0$. For the base
case, note that when $j=0$, we have $p_{0}(x)=x^{6}+x^{5}+x^{3}+1$ and
$q_{0}(x)=x^{2}+1$, so $p_{0}(x)=(x^{4}+x^{3}-x^{2}+1)q_{0}(x)$. Suppose that
$t$ is a non-negative integer with $p_{t}(x)=(x^{4}+x^{3}-x^{2}+1)q_{t}(x)$.
We will show that $p_{t+1}(x)=(x^{4}+x^{3}-x^{2}+1)q_{t+1}(x)$ to complete the
proof. First note that

$\displaystyle(x^{4}+x^{3}-x^{2}+1)q_{t+1}(x)$
$\displaystyle=(x^{4}+x^{3}-x^{2}+1)\left(\displaystyle\sum_{i=1}^{t+1}x^{2+2i}+x^{2}+1\right)$
$\displaystyle=(x^{4}+x^{3}-x^{2}+1)\left(x^{2+2(t+1)}+\displaystyle\sum_{i=1}^{t}x^{2+2i}+x^{2}+1\right)$
$\displaystyle=(x^{4}+x^{3}-x^{2}+1)(x^{2+2t+2})+p_{t}(x).$

Now observe that
$p_{t}(x)=x^{4+2t+2}+x^{4+2t+1}+\sum\limits_{k=4}^{4+2t-1}x^{k}+x^{3}+1$,
while

$\displaystyle p_{t+1}(x)$
$\displaystyle=x^{4+2(t+1)+2}+x^{4+2(t+1)+1}+\displaystyle\sum_{k=4}^{4+2(t+1)-1}x^{k}+x^{3}+1$
$\displaystyle=x^{4+2t+4}+x^{4+2t+3}+x^{4+2t+1}+x^{4+2t}+\displaystyle\sum_{k=4}^{4+2t-1}x^{k}+x^{3}+1$
$\displaystyle=x^{4+2t+4}+x^{4+2t+3}+x^{4+2t+1}+x^{4+2t}+\displaystyle\sum_{k=4}^{4+2t-1}x^{k}+x^{3}+1+(x^{4+2t+2}-x^{4+2t+2})$
$\displaystyle=x^{4+2t+4}+x^{4+2t+3}-x^{4+2t+2}+x^{4+2t}+p_{t}(x)$
$\displaystyle=x^{4+2t}(x^{4}+x^{3}-x^{2}+1)+p_{t}(x).$

Thus $p_{t+1}(x)=(x^{4}+x^{3}-x^{2}+1)q_{t+1}(x)$, and our proof by induction
is complete.

Since we have considered all indecomposable representations of $100$, we
conclude that every indecomposable representation of $100$ is universal. ∎

######  Theorem 2.6.

Every representation of $100$ is universal. Moreover, for any representation
of $100$ as $\frac{p(3)}{q(3)}$, the quotient $\frac{p(x)}{q(x)}$ is
$x^{4}+x^{3}-x^{2}+1$. This includes both indecomposable and decomposable
representations.

###### Proof.

We have addressed the indecomposable representations of $100$ in Theorem 2.5,
so it remains to consider the decomposable representations of $100$. Suppose
we have a representation of $100$ resulting from the concatenation of two
indecomposable walks through the digraph with no loops at 0 occurring between
the two walks. On the first indecomposable walk, we step up from $12$ to $37$
exactly $j$ times, and on the second indecomposable walk, we step up from $12$
to $37$ exactly $k$ times.

The contributions to $p(x)$ and $q(x)$ coming from this first indecomposable
walk are $p_{j}(x)$ and $q_{j}(x)$, as defined in the proof of Theorem 2.5,
while the contributions coming from the second indecomposable walk are
$x^{2j+7}p_{k}(x)$ and $x^{2j+7}q_{k}(x)$. Note that there are a total of
$2j+7$ steps in the first indecomposable walk, so the second indecomposable
walk begins recording powers of 3 starting with $3^{2j+7}$. Thus, for the
representation of $100$ resulting from two indecomposable walks, we have
$p(x)=x^{2j+7}p_{k}(x)+p_{j}(x)$ and $q(x)=x^{2j+7}q_{k}(x)+q_{j}(x)$.

Note that

$\displaystyle(x^{4}+x^{3}-x^{2}+1)q(x)$
$\displaystyle=(x^{4}+x^{3}-x^{2}+1)\left(x^{2j+7}q_{k}(x)+q_{j}(x)\right)$
$\displaystyle=x^{2j+7}(x^{4}+x^{3}-x^{2}+1)q_{k}(x)+(x^{4}+x^{3}-x^{2}+1)q_{j}(x)$
$\displaystyle=x^{2j+7}p_{k}(x)+p_{j}(x)$ $\displaystyle=p(x).$

Thus $q(x)\mid p(x)$, and this representation of $100$ must be universal.

What if a representation results from concatenating not just two
indecomposable walks through the digraph but $n$ indecomposable walks with no
loops at 0 between any two walks? Let $i_{1},i_{2},\ldots i_{n}$ be the non-
negative integers such that $i_{h}$ is the number of times we step up from
$12$ to $37$ on the $h$th indecomposable walk through the digraph. Then we
have

$\displaystyle p(x)$
$\displaystyle=x^{2(i_{1}+i_{2}+\cdots+i_{n-1})+7(n-1)}p_{i_{n}}(x)+x^{2(i_{1}+i_{2}+\cdots+i_{n-2})+7(n-2)}p_{i_{n-1}}(x)+\cdots$
$\displaystyle\qquad+x^{2(i_{1}+i_{2})+7(2)}p_{i_{3}}(x)+x^{2i_{1}+7}p_{i_{2}}(x)+p_{i_{1}}(x)$
$\displaystyle=\displaystyle\sum_{j=1}^{n}x^{2a_{j}+7(j-1)}p_{i_{j}}(x),$

where $a_{j}=\sum\limits_{k=1}^{j-1}i_{k}$, and

$\displaystyle q(x)$
$\displaystyle=x^{2(i_{1}+i_{2}+\cdots+i_{n-1})+7(n-1)}q_{i_{n}}(x)+x^{2(i_{1}+i_{2}+\cdots+i_{n-2})+7(n-2)}q_{i_{n-1}}(x)+\cdots$
$\displaystyle\qquad+x^{2(i_{1}+i_{2})+7(2)}q_{i_{3}}(x)+x^{2i_{1}+7}q_{i_{2}}(x)+q_{i_{1}}(x)$
$\displaystyle=\displaystyle\sum_{j=1}^{n}x^{2a_{j}+7(j-1)}q_{i_{j}}(x).$

Each pair of polynomials $p_{i_{h}}(x)$ and $q_{i_{h}}(x)$ gives an
indecomposable representation of $100$ as
$100=\frac{p_{i_{h}}(3)}{q_{i_{h}}(3)}$, so from Theorem 2.5, we have
$p_{i_{h}}(x)=(x^{4}+x^{3}-x^{2}+1)q_{i_{h}}(x)$ for each $i_{h}$. Then we see
that

$\displaystyle(x^{4}+x^{3}-x^{2}+1)q(x)$
$\displaystyle=(x^{4}+x^{3}-x^{2}+1)\displaystyle\sum_{j=1}^{n}x^{2a_{j}+7(j-1)}q_{i_{j}}(x)$
$\displaystyle=\displaystyle\sum_{j=1}^{n}x^{2a_{j}+7(j-1)}(x^{4}+x^{3}-x^{2}+1)q_{i_{j}}(x)$
$\displaystyle=\displaystyle\sum_{j=1}^{n}x^{2a_{j}+7(j-1)}p_{i_{j}}(x)$
$\displaystyle=p(x).$

Thus $q(x)\mid p(x)$, and this representation of $100$ must be universal.

We conclude by proving that adding loops at 0 between any two indecomposable
walks results in new representations of 100 which are also universal. Consider
$p(x)=\sum_{h}x^{b_{h}}p_{i_{h}}(x)$ and $q(x)=\sum_{h}x^{b_{h}}q_{i_{h}}(x)$,
where $i_{1},i_{2},\ldots i_{n}$ are as above and $b_{1},b_{2},\ldots b_{n}$
are non-negative integers. Then by Lemma 2.2, we see that
$p(x)=(x^{4}+x^{3}-x^{2}+1)q(x)$ as well. Therefore, since adding loops at 0
changes only the powers $b_{h}$ of $x$ in $p(x)$ and $q(x)$, we see that
representations of 100 including loops at 0 are still universal. As an
example, if we take $\ell$ loops at 0 between walk $i_{d}$ and walk $i_{d+1}$,
the resulting polynomials $p(x)$ and $q(x)$ yield

$\displaystyle(x^{4}+x^{3}-x^{2}+1)q(x)$
$\displaystyle=(x^{4}+x^{3}-x^{2}+1)\left[\displaystyle\sum_{j=1}^{d}x^{2a_{j}+7(j-1)}q_{i_{j}}(x)+\displaystyle\sum_{j=d+1}^{n}x^{2a_{j}+7(j-1)+\ell}q_{i_{j}}(x)\right]$
$\displaystyle=\displaystyle\sum_{j=1}^{d}x^{2a_{j}+7(j-1)}(x^{4}+x^{3}-x^{2}+1)q_{i_{j}}(x)$
$\displaystyle\qquad+\displaystyle\sum_{j=d+1}^{n}x^{2a_{j}+7(j-1)+\ell}(x^{4}+x^{3}-x^{2}+1)q_{i_{j}}(x)$
$\displaystyle=\displaystyle\sum_{j=1}^{d}x^{2a_{j}+7(j-1)}p_{i_{j}}(x)+\displaystyle\sum_{j=d+1}^{n}x^{2a_{j}+7(j-1)+\ell}p_{i_{j}}(x)$
$\displaystyle=p(x).$

Hence all representations of $100$ are universal. ∎

##  3\. Integers with local representations

As we have seen in Examples 1.3 and 1.4, some integers $m\equiv 1\pmod{3}$
have local representations in addition to a trivial universal representation.
In this section, we identify several other examples of integers with local
representations. Specifically, in Section 3.1, we restrict our attention to
integers $m$ with only local representations, and in Section 3.2, we show that
$m=64$ has both local representations and nontrivial universal
representations.

###  3.1. Integers with only local representations

Some integers $m\equiv 1\pmod{3}$ have only local representations. Here we
prove that all representations of $m=22$ and $m=34$ are local, and we list
many more integers $m$ whose representations are all local.

######  Theorem 3.1.

There do not exist $p(x),q(x)\in\mathcal{P}$ with $q(x)\ |\ p(x)$ such that
$22=\frac{p(3)}{q(3)}$; that is, all representations of $22$ are local,
including both decomposable and indecomposable representations.

###### Proof.

Suppose to the contrary that $22=\frac{p(3)}{q(3)}$, where
$p(x),q(x)\in\mathcal{P}$ and $g(x):=\frac{p(x)}{q(x)}\in\mathbb{Z}[x]$. Let
$r=\deg p(x)$ and $s=\deg q(x)$. By Theorem 1.2,

$\frac{2}{3}\cdot 3^{r-s}<22<\frac{3}{2}\cdot 3^{r-s},$

which implies $r-s=\deg g(x)=3$. Since the constant terms and the coefficients
of $x^{r}$ in $p(x)$ and $x^{s}$ in $q(x)$ are 1, we may then write
$g(x)=1+e_{1}x+e_{2}x^{2}+x^{3}$. It is now convenient to take
$p(x)=1+\sum\limits_{i=1}^{r-1}c_{i}x^{i}+x^{r}$ and
$q(x)=1+\sum\limits_{i=1}^{s-1}d_{i}x^{i}+x^{s}$, where
$c_{i},d_{i}\in\\{0,1\\}$. The equation $p(x)=g(x)q(x)$ thus implies that

$\displaystyle c_{1}$ $\displaystyle=d_{1}+e_{1},$ $\displaystyle c_{2}$
$\displaystyle=d_{2}+d_{1}e_{1}+e_{2},$ $\displaystyle c_{3}$
$\displaystyle=d_{3}+d_{2}e_{1}+d_{1}e_{2}+1.$

Since $22=g(3)=1+3e_{1}+9e_{2}+27$, we have $e_{1}+3e_{2}=-2$, and so
$e_{1}\equiv 1\pmod{3}$. But $e_{1}=c_{1}-d_{1}$ and
$c_{1},d_{1}\in\\{0,1\\}$, so we must have that $c_{1}=1,d_{1}=0,$ and
$e_{1}=1$. Thus $3e_{2}=-3$, so $e_{2}=-1$ and $g(x)=x^{3}-x^{2}+x+1$. Note
that $g(3)=22$. The remaining two equations become

$\displaystyle c_{2}$ $\displaystyle=d_{2}+0\cdot 1+(-1)=d_{2}-1,$
$\displaystyle c_{3}$ $\displaystyle=d_{3}+d_{2}\cdot
1+0\cdot(-1)+1=d_{3}+d_{2}+1.$

It follows from the first of these two equations that $c_{2}=0$ and $d_{2}=1$.
It then follows from the second equation that $c_{3}=d_{3}+2$, which is
impossible. ∎

We can implement the same approach to prove that all representations of $34$
are local, or we can instead use Theorem 3.1 and prove the result regarding
$34$ as a corollary. Here we implement the latter approach.

######  Corollary 3.2.

There do not exist $p(x),q(x)\in\mathcal{P}$ with $q(x)\ |\ p(x)$ such that
$34=\frac{p(3)}{q(3)}$; that is, all representations of $34$ are local,
including both decomposable and indecomposable representations.

###### Proof.

Let $p(x),q(x),r$, and $s$ be as in the proof of Theorem 3.1, and let
$h(x):=\frac{p(x)}{q(x)}\in\mathbb{Z}[x]$. Again,

$\frac{2}{3}\cdot 3^{r-s}<34<\frac{3}{2}\cdot 3^{r-s},$

which implies $r-s=\deg h(x)=3$, and we will continue following the same
procedure as in the proof of Theorem 3.1. Now $34=h(3)=1+3e_{1}+9e_{2}+27$, so
$e_{1}+3e_{2}=2$ and $e_{1}\equiv 2\pmod{3}$. But $e_{1}=c_{1}-d_{1}$ and
$c_{1},d_{1}\in\\{0,1\\}$, so we have that $c_{1}=0$, $d_{1}=1$, and
$e_{1}=-1$. Thus $e_{2}=1$ and $h(x)=x^{3}+x^{2}-x+1$.

At this point, our argument diverges from that in the proof of Theorem 3.1.
Write $p(x)=\sum\limits_{k=0}^{m}x^{a_{k}}$ and
$q(x)=\sum\limits_{\ell=0}^{n}x^{b_{\ell}}$. We have
$q(x)(x^{3}+x^{2}-x+1)=p(x)$. Now reverse the polynomials by taking $x\mapsto
1/x$ and multiplying $q(x)$ by $x^{s}$, $h(x)$ by $x^{3}$, and $p(x)$ by
$x^{r}$ to obtain

(3.1)
$\left(\sum_{\ell=0}^{n}x^{s-b_{\ell}}\right)(x^{3}-x^{2}+x+1)=\sum_{k=0}^{m}x^{r-a_{k}}.$

Note that $x^{3}h\left(\frac{1}{x}\right)=g(x)$, where $g(x)$ is as in the
proof of Theorem 3.1. Since the polynomials $x^{s}q\left(\frac{1}{x}\right)$
and $x^{r}p\left(\frac{1}{x}\right)$ are still in $\mathcal{P}$, we have
already seen in the proof of Theorem 3.1 that Equation (3.1) cannot be
satisfied, and we have a contradiction. ∎

The same type of proof by contradiction that we used to prove Theorem 3.1 by
examining the coefficients of $p(x)$ and $q(x)$ can also be used to show that
the following numbers have only local representations: 34, 58, 67, 97, 103,
106, 115, 175, 178, 184, 193, 199, 202, 205, 208, 214, 229, 232, 238, 259,
265, 277, 286, 295, 298, 304, 307, 310, 313, 331, 340. Additionally, the
procedure can be applied to test larger integers, but the computations become
increasingly tedious.

###  3.2. Integers with both nontrivial universal representations and local
representations

Here we consider $m=64$ as an example of an integer that has both nontrivial
universal representations and local representations. See the digraph for
$m=64$ in Figure 5 for reference.

021289312482972223110 Figure 5. The subgraph of the multiplication transducer
for $m=64$ that encodes all representations of $64$ as a quotient of sums of
distinct powers of 3.

We begin by applying the algorithm as usual, stepping down from 9, and this
yields $64=\frac{3^{5}+3^{2}+3+1}{3+1}$. Letting $p(x)=x^{5}+x^{2}+x+1$ and
$q(x)=x+1$, we have $64=\frac{p(3)}{q(3)}$. Since
$p(x)=\left(x^{4}-x^{3}+x^{2}+1\right)q(x)$, this is a universal
representation of $64$. Since $q(x)\neq 1$, this universal representation is
nontrivial.

Suppose we continued with the algorithm beyond $28$, the first carry value
that is a sum of distinct powers of 3. Would we get local representations or
universal representations? The first choice to be made occurs when the carry
value is 9. We will show that any representation of $64$ that takes a step up
from carrying 9 to carrying 24 upon first arriving at the carry value 9 must
be a local representation. This is true for both decomposable and
indecomposable representations, and we prove it using the same approach as in
the proof of Theorem 3.1.

######  Theorem 3.3.

Any representation of $64$ that steps up upon first arriving at the carry
value 9 is a local representation. This holds for both decomposable and
indecomposable representations.

###### Proof.

Suppose to the contrary that $64=\frac{p(3)}{q(3)}$ for some
$p(x),q(x)\in\mathcal{P}$, $g(x):=\frac{p(x)}{q(x)}\in\mathbb{Z}[x]$, and the
representation $\frac{p(3)}{q(3)}$ results from stepping up upon first
arriving at the carry value 9. Let $r=\deg p(x)$ and $s=\deg q(x)$. By Theorem
1.2,

$\frac{2}{3}\cdot 3^{r-s}<64<\frac{3}{2}\cdot 3^{r-s},$

which implies $r-s=\deg g(x)=4$. Since the constant terms and the coefficients
of $x^{r}$ in $p(x)$ and $x^{s}$ in $q(x)$ are 1, we may then write
$g(x)=x^{4}+e_{3}x^{3}+e_{2}x^{2}+e_{1}x+1$. It is now convenient to take
$p(x)=1+\sum\limits_{i=1}^{r}c_{i}x^{i}$ and
$q(x)=1+\sum\limits_{i=1}^{s}d_{i}x^{i}$, where $c_{i},d_{i}\in\\{0,1\\}$.

Since $64=g(3)=81+27e_{3}+9e_{2}+3e_{1}+1$, we have $-6=9e_{3}+3e_{2}+e_{1}$,
and $e_{1}\equiv 0\pmod{3}$. Since $e_{1}=c_{1}-d_{1}$, we see $c_{1}=d_{1}$
and $e_{1}=0$. After the first step of the algorithm, we have a carry value of
$21\equiv 0\pmod{3}$ and thus must make a choice. As in the case of $m=100$,
one step, the step from $21$ down to 7, does not lead to any representations.
Thus, to have a chance at actually obtaining a representation of $64$, we must
step up from $21$ to $28$, and this corresponds to taking $c_{1}=d_{1}=1$.
Note that $e_{1}=0$ gives $-6=9e_{3}+3e_{2}$, so $-2=3e_{3}+e_{2}$, and
$e_{2}\equiv 1\pmod{3}$. Since $e_{2}=c_{2}-d_{2}-d_{1}e_{1}=c_{2}-d_{2}$, we
see $c_{2}=1,d_{2}=0$, and $e_{2}=1$. Then $-3=3e_{3}$, so $e_{3}=-1$. Then
$c_{3}=d_{3}+d_{2}e_{1}+d_{1}e_{2}+e_{3}$ is $c_{3}=d_{3}$. Since we are
interested in representations that step up from 9 to 24, we take
$c_{3}=d_{3}=1$. Then, substituting the values we have already determined,
$c_{4}=d_{4}+d_{3}e_{1}+d_{2}e_{2}+d_{1}e_{3}+1$ becomes $c_{4}=d_{4}$.

Suppose $c_{4}=d_{4}=0$. Then
$c_{5}=d_{5}+d_{4}e_{1}+d_{3}e_{2}+d_{2}e_{3}+d_{1}$ is $c_{5}=d_{5}+2$, which
is a contradiction to $c_{5},d_{5}\in\\{0,1\\}$.

Now suppose $c_{4}=d_{4}=1$. Then
$c_{5}=d_{5}+d_{4}e_{1}+d_{3}e_{2}+d_{2}e_{3}+d_{1}$ is $c_{5}=d_{5}+2$, which
is a contradiction to $c_{5},d_{5}\in\\{0,1\\}$.

Since in all cases we arrive at a contradiction, we may conclude that
$q(x)\nmid p(x)$, and thus all representations of $64$ that choose the step up
when first carrying 9 are local. ∎

We conclude this section by discussing a specific example of a local
representation of 64, one that steps up upon first arriving at the carry value
$9$.

######  Example 3.4.

Suppose that $m=64=\frac{p}{q}\in\mathcal{A}/\mathcal{A}$. As usual, we start
with a carry value of 0, and we choose to add $m=64$ to the carry value,
record $1\cdot 3^{0}$ into $q$ and into $p$, then subtract 1 from the carry
value, and move on to Step 1. The remaining unrecorded value is $(64-1)\cdot
3^{0}=63\cdot 3^{0}=21\cdot 3^{1}$, so the carry value at the end of Step 1 is
now $21\equiv 0\pmod{3}$. As in the case of $m=100$, we must make a choice.
One choice, the step from $21$ down to 7, does not lead to any
representations. Thus, to have a chance at actually obtaining a representation
of $64$, we must step up from $21$ to $28$. To implement this choice, we add
$m=64$ to the carry value again, record $1\cdot 3^{1}$ into $q$ and into $p$,
and then subtract 1 from the carry value. The remaining unrecorded value is
$(21+64-1)\cdot 3^{1}=84\cdot 3^{1}=28\cdot 3^{2}$, so the new carry value at
the end of Step 2 is 28. Since $28=3^{3}+3^{0}$ is a sum of distinct powers of
3, the algorithm would terminate here, and we would append the digits of the
base 3 representation $28=[1001]_{3}$ to the left of $p$ to get the nontrivial
universal representation
$64=\frac{[100111]_{3}}{[11]_{3}}=\frac{3^{5}+3^{2}+3+1}{3+1}=\frac{256}{4}$
discussed above.

At present, we seek to characterize representations of $64$ that step up upon
first arriving at the carry value $9$. To obtain such a representation of 64,
we must continue the algorithm instead of allowing the algorithm to terminate
in Step 2, when our carry value is $28\equiv 1\pmod{3}$. To continue, we
record $1\cdot 3^{2}$ into $p$, subtract 1 from the carry value, and arrive at
the unrecorded value $(28-1)\cdot 3^{2}=27\cdot 3^{2}=9\cdot 3^{3}$. The new
carry value at the end of Step 3 is 9. Because we are exploring
representations of $64$ that step up upon first arriving at the carry value
$9$, we choose to add $m=64$ to the carry value and record $1\cdot 3^{3}$ into
$q$ and into $p$. Then, after subtracting 1 from the carry value, the
remaining unrecorded value is $(9+64-1)\cdot 3^{3}=72\cdot 3^{3}=24\cdot
3^{4}$, so our carry value at the end of Step 4 is 24. We choose again to add
$m=64$ to the carry value and record $1\cdot 3^{4}$ into $q$ and into $p$.
After subtracting 1 from the carry value, we have the remaining unrecorded
value $(24+64-1)\cdot 3^{4}=87\cdot 3^{4}=29\cdot 3^{5}$, so we are left with
a new carry value of 29 at the end of Step 5. Since $29\equiv 2\pmod{3}$, we
must add $m=64$ to the carry value and correspondingly record $1\cdot 3^{5}$
into $q$. Then the remaining unrecorded value is $(29+64)\cdot 3^{5}=93\cdot
3^{5}=31\cdot 3^{6}$, so our carry value at the end of Step 6 is $31$. Since
$31=3^{3}+3^{1}+3^{0}$ is a sum of distinct powers of 3, we can terminate this
extension of the algorithm by appending the digits of the base 3
representation $31=[1011]_{3}$ to the left of $p$. This yields the local
representation

$64=\frac{[1011011111]_{3}}{[111011]_{3}}=\frac{3^{9}+3^{7}+3^{6}+3^{4}+3^{3}+3^{2}+3+1}{3^{5}+3^{4}+3^{3}+3+1}=\frac{22720}{355}.$

Notice that this representation is $64=\frac{p(3)}{q(3)}$ where
$p(x)=x^{9}+x^{7}+x^{6}+x^{4}+x^{3}+x^{2}+x+1$ and
$q(x)=x^{5}+x^{4}+x^{3}+x+1$, and that $q(x)\nmid p(x)$.

##  4\. Catalog of knowledge

This table classifies all indecomposable representations of integers $m\equiv
1\pmod{3}$ in the intervals given in 1.2 up to $\frac{3}{2}\cdot 3^{5}$. For
some integers, such as 22, 34, and 229, information is also known about
decomposable representations, as discussed for $22$ in Theorem 3.1 and for
$34$ in Corollary 3.2. In the table, $\bigstar$ indicates that $m$ has
representations of that type, an empty cell indicates $m$ does not have
representations of that type, and $?$ indicates that it is not known whether
$m$ has representations of that type. The only $?$ appears for local
representations of $289$.

In addition to the techniques already discussed in this paper, another
approach we employed to find representations of an integer $m$ utilized
Mathematica as follows. For all Newman polynomials $p(x)$ up to a fixed
degree, construct a table of the values $p(3)$. It was computationally
feasible for us to do this up to degree $18$. Search for those values $p(3)$
which are multiples of $m$. If $p(3)=m\cdot t$, then see if the ternary
expansion of $t$ uses only the digits 0 and 1. If so, then $t=q(3)$ for a
Newman polynomial $q(x)$. Finally, check if $q(x)\mid p(x)$.

m | universal | local
---|---|---
1 | $\bigstar$ |
4 | $\bigstar$ |
7 | $\bigstar$ |
10 | $\bigstar$ |
13 | $\bigstar$ |
19 | $\bigstar$ |
22 |  | $\bigstar$
25 | $\bigstar$ |
28 | $\bigstar$ |
31 | $\bigstar$ | $\bigstar$
34 |  | $\bigstar$
37 | $\bigstar$ | $\bigstar$
40 | $\bigstar$ |
55 | $\bigstar$ |
58 |  | $\bigstar$
61 | $\bigstar$ |
64 | $\bigstar$ | $\bigstar$
67 |  | $\bigstar$
70 | $\bigstar$ | $\bigstar$
73 | $\bigstar$ |
76 | $\bigstar$ | $\bigstar$
79 | $\bigstar$ |
82 | $\bigstar$ |
85 | $\bigstar$ | $\bigstar$
88 | $\bigstar$ | $\bigstar$
91 | $\bigstar$ |
94 | $\bigstar$ | $\bigstar$
97 |  | $\bigstar$
100 | $\bigstar$ |
103 |  | $\bigstar$
106 |  | $\bigstar$
109 | $\bigstar$ | $\bigstar$
112 | $\bigstar$ | $\bigstar$
115 |  | $\bigstar$
118 | $\bigstar$ | $\bigstar$
121 | $\bigstar$ |
m | universal | local
---|---|---
163 | $\bigstar$ |
166 |  | $\bigstar$
169 | $\bigstar$ | $\bigstar$
172 |  | $\bigstar$
175 |  | $\bigstar$
178 |  | $\bigstar$
181 | $\bigstar$ |
184 |  | $\bigstar$
187 | $\bigstar$ | $\bigstar$
190 | $\bigstar$ | $\bigstar$
193 |  | $\bigstar$
196 | $\bigstar$ | $\bigstar$
199 |  | $\bigstar$
202 |  | $\bigstar$
205 |  | $\bigstar$
208 |  | $\bigstar$
211 | $\bigstar$ | $\bigstar$
214 |  | $\bigstar$
217 | $\bigstar$ |
220 | $\bigstar$ | $\bigstar$
223 | $\bigstar$ | $\bigstar$
226 |  | $\bigstar$
229 |  | $\bigstar$
232 |  | $\bigstar$
235 | $\bigstar$ |
238 |  | $\bigstar$
241 | $\bigstar$ |
244 | $\bigstar$ |
247 | $\bigstar$ | $\bigstar$
250 | $\bigstar$ | $\bigstar$
253 | $\bigstar$ | $\bigstar$
256 | $\bigstar$ | $\bigstar$
259 |  | $\bigstar$
262 |  | $\bigstar$
265 |  | $\bigstar$
268 |  | $\bigstar$
271 | $\bigstar$ | $\bigstar$
274 | $\bigstar$ | $\bigstar$
277 |  | $\bigstar$
280 | $\bigstar$ | $\bigstar$
283 | $\bigstar$ | $\bigstar$
286 |  | $\bigstar$
289 | $\bigstar$ | $?$
292 | $\bigstar$ | $\bigstar$
295 |  | $\bigstar$
298 |  | $\bigstar$
m | universal | local
---|---|---
301 | $\bigstar$ | $\bigstar$
304 |  | $\bigstar$
307 |  | $\bigstar$
310 |  | $\bigstar$
313 |  | $\bigstar$
316 | $\bigstar$ | $\bigstar$
319 | $\bigstar$ | $\bigstar$
322 |  | $\bigstar$
325 | $\bigstar$ | $\bigstar$
328 | $\bigstar$ | $\bigstar$
331 |  | $\bigstar$
334 | $\bigstar$ | $\bigstar$
337 | $\bigstar$ | $\bigstar$
340 |  | $\bigstar$
343 |  | $\bigstar$
346 |  | $\bigstar$
349 |  | $\bigstar$
352 | $\bigstar$ | $\bigstar$
355 | $\bigstar$ | $\bigstar$
358 |  | $\bigstar$
361 | $\bigstar$ | $\bigstar$
364 | $\bigstar$ |

##  5\. Further directions

Ultimately, we want to know which integers can be written as a quotient of
sums of distinct powers of 3. An additional long-term goal is to find a
complete classification of the types of representations integers can have as
quotients of sums of distinct powers of 3. For example, we seek a complete
description of the integers congruent to 1 mod 3 in (1.2) which do not lie in
$\mathcal{A}/\mathcal{A}$. This paper makes progress toward this goal and also
provides a launching point for several related questions and directions.

###  5.1. Properties of the Directed Graphs

In Figure 2 in Section 1.2, we introduce an example of an expanded digraph
generated as a subgraph of the multiplication transducer that performs
multiplication by $m$ in base 3. These digraphs are worthy of study in their
own right, beyond the information they encode regarding representations of
integers as quotients of sums of distinct powers of 3. For any positive
integer $m=3t+1$, define the digraph $D_{m}$ as follows: The vertices of
$D_{m}$ are a subset of $\\{0,\dots,\lfloor m/2\rfloor\\}$. There are four
kinds of directed edges in $D_{m}$. What kind of edge we see originating at a
given vertex depends on the congruence class of the given vertex modulo 3. The
four kinds of edges are

$\\{3k\rightarrow k,\quad 3k\rightarrow k+t,\quad 3k+1\rightarrow k,\quad
3k+2\rightarrow k+t+1\\}.$

If $i$ is in the vertex set of $D_{m}$ and $i\rightarrow j$ is in the set of
possible edges above, then $j$ must also belong to the vertex set of $D_{m}$.

This digraph $D_{m}$ is the digraph produced by applying the algorithm of
Section 1.2 to $m$, as done in Figure 2 for $m=22$, in Figure 4 for $m=100$,
and in Figure 5 for $m=64$, and the four kinds of edges correspond to the four
possible ways to move from Step $i$ to Step $i+1$ in the algorithm. Every
representation of $m$ as $\frac{p(3)}{q(3)}$ with $p(x),q(x)\in\mathcal{P}$
can be read off from the vertices in a walk from the vertex 0 to itself. When
no such walk exists, as in the case $m=529$, there is no such representation.
More information about these digraphs and various related topics will appear
in [1].

###  5.2. Extending to different bases

It is natural to ask the questions of this paper for digital bases $b\neq 3$.
If $b=2$, then the standard binary representation for $n$,
$n=\sum_{i}a_{i}2^{i}$ with $a_{i}\in\\{0,1\\}$, gives $n=p(2)$, where
$p(x)=\sum_{i}a_{i}x^{i}\in\mathcal{P}$.

For any $b\geq 2$, local representations still exist: if
$p(x),q(x)\in\mathcal{P}$ and $p(x)=q(x)t(x)$ for $t(x)\in\mathbb{Z}[x]$, then
$t(b)=\frac{p(b)}{q(b)}$ will be a quotient of sums of distinct powers of $b$.
For example,

$b^{2}-b+1=[(b-1)\,1]_{b}=\frac{b^{3}+1}{b+1}.$

On the other hand, $b^{2}\equiv 1\pmod{b+1}$, and

(5.1) $\frac{b^{2b}+\cdots+b^{4}+b^{2}+1}{b+1}\in\mathbb{Z}.$

Further, $(x+1)\nmid\left(x^{2b}+\cdots+x^{4}+x^{2}+1\right)$, because $x=-1$
is not a root of the polynomial on the right. Thus, for every base $b$, there
are local representations of quotients of distinct sums of powers of $b$; for
$b=3$, (5.1) is a local representation of $\frac{729+81+9+1}{3+1}=205$.

The phrase “quotients of sums of distinct powers of $b$” may be rewritten as
“quotients of integers with base $b$ representations using only digits from
$\\{0,1\\}$.” Written this way, we can extend our work to ask similar
questions for different sets of digits when $b\geq 3$. The fourth-named author
studied generalizations of this problem in her dissertation [10], exploring
quotients of integers which, when written in base $b$, have a restricted digit
set.

##  6\. Acknowledgments

The second author was supported by an AMS-Simons Travel Grant. The third and
fourth authors wish to acknowledge the warm hospitality of the Department of
Mathematics of the University of Texas at Tyler during a visit in June 2022.

## References

  * [1] K. Anders, M. Dawsey, B. Reznick, and S. Sisneros-Thiry, _Digraphs for representations of integers as quotients of sums of distinct powers of three_ , in preparation.
  * [2] J. Athreya, B. Reznick, and J. Tyson, _Cantor set arithmetic_ , American Mathematical Monthly, 126 (2019), 4–17 (MR3904605, arXiv:1711.08791).
  * [3] J. H. Bai, J. Meleshko, S. Riasat, and J. Shallit, _Quotients of Palindromic and Antipalindromic Numbers_ , arXiv:22021.13694v1.
  * [4] F. Blanchard, J. M. Dumont, and A. Thomas, _Generic sequences, transducers and multiplication of normal numbers_ , Israel Journal of Mathematics, 80(3) (1992), 257–287.
  * [5] S. Haque, email to the third and fourth authors, May 26, 2017.
  * [6] J. Loxton and A. van der Poorten, _An awful problem about integers in base four_ , Acta Arith., 49 (1987), 193–203. MR0928637 (89m:11004).
  * [7] A. Odlyzko and B. Poonen, _Zeros of polynomials with 0,1 coefficients_ , Enseign. Math. (2) 39 (1993), no. 3-4, 317–348, MR1252071 (95b:11026).
  * [8] Online Encyclopedia of Integer Sequences, https://oeis.org/ consulted August 11, 2023.
  * [9] B. Reznick, _Quotients of sums of distinct powers of three_ , presentation at AMS Central Sectional Meeting, Loyola-Chicago, October 3, 2015, https://faculty.math.illinois.edu/reznick/loyola-10315Fc.pdf.
  * [10] S. Sisneros-Thiry, _Combinatorial number theory through diagramming and gesture_ , Thesis (Ph.D.) University of Illinois at Urbana-Champaign. 2020.