# Proving Properties of $\varphi$-Representations with the Walnut Theorem-
Prover

Jeffrey Shallit
School of Computer Science
University of Waterloo
Waterloo, ON N2L 3G1
Canada
<EMAIL_ADDRESS>
###### Abstract

We revisit a classic theorem of Frougny and Sakarovitch concerning automata
for $\varphi$-representations, and show how to obtain it in a different and
more computationally direct way. Using it, we can find simple, induction-free
proofs of existing results in the literature about these representations, in a
uniform and straightforward manner. In particular, we can easily and
“automatically” recover many of the results of recent papers of Dekking and
Van Loon. We also obtain a number of new results on $\varphi$-representations.

In honor of the 80th birthday of George Bergman

##  1 Introduction

In 1957, George Bergman [2] observed that one can expand a non-negative real
number $z$ in base $\varphi=(1+\sqrt{5})/2$, in the sense that there exist
“digits” $a_{i}\in\\{0,1\\}$ such that

$z=\sum_{-\infty\leq i<r}a_{i}\varphi^{i}.$ (1)

In analogy with base-$b$ representation, we can write such a base-$\varphi$
representation as a string of digits $a_{r-1}\cdots
a_{0}\,.\,a_{1}a_{2}a_{3}\cdots$ where the non-negative and negative powers
are separated by the analogue of a “decimal point”. We call $a_{r-1}\cdots
a_{0}$ the left part and $.\,a_{1}a_{2}a_{3}\cdots$ the right part of the
$\varphi$-representation. The left part is always finite, while the right part
may be finite or infinite. These parts are analogous to the more familiar
integer and fractional parts of decimal representations of the positive reals.

If Eq. (1) holds, then we write

$z=[a_{r-1}\cdots a_{0}\,.\,a_{1}a_{2}a_{3}\cdots]_{\varphi}.$

For example, $2=[10.01]_{\varphi}=[1.11]_{\varphi}$ and
$\frac{1}{2}=[.010010010010\cdots]_{\varphi}$.

Furthermore, such a representation $x.y$ as a string of binary digits with a
decimal point is essentially unique111Throughout the paper, we adopt the
convention that in expansions of the form $[x.y]_{\varphi}$, we disregard
leading zeros in $x$ and trailing zeros in $y$. Thus $10.01$ and $010.0100$
are regarded as “essentially” the same. This convention is extremely useful,
as sometimes our automata will need to pad multiple inputs with zeros to
ensure they all have the same length. if one imposes the very natural
restriction that $a_{i}a_{i+1}\not=1$ for all $i$ (or, equivalently, if the
string $xy$ contains no occurrence of the block $11$), and furthermore that if
the expansion is infinite, it cannot end in $010101\cdots$.

We call a $\varphi$-representation obeying these rules canonical, and write it
as $(x)_{\varphi}$. Bergman [2] proved that the canonical
$\varphi$-representation of a natural number is finite, and Table 1 gives the
canonical expansions of the first few positive integers.

$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---|---
$(n)_{\varphi}$ | 1. | 10.01 | 100.01 | 101.01 | 1000.1001 | 1010.0001 | 10000.0001
Table 1: First few canonical expansions.

The left and right parts of the canonical $\varphi$-representation of $n$ can
be found in sequences A105424 and A341722 in the On-Line Encyclopedia of
Integer Sequences (OEIS) [35].

Bergman’s ideas were generalized to positive real numbers $\beta$ by Rényi
[29], who called such expansions $\beta$-expansions. Later, fundamental work
characterizing such expansions was done by Parry [28].

Several researchers, including Bertrand-Mathis and Frougny, have found deep
and interesting connections between these expansions and finite automata when
$\beta$ is an algebraic number. See, for example, [5, 16, 17, 18, 19, 20, 21,
1, 22].

In a very interesting article, Frougny and Sakarovitch [23] proved that the
canonical $\varphi$-representation of a non-negative integer can be computed
by a finite automaton $A$, in the following sense: $A$ takes three inputs in
parallel: $n$ represented in the Zeckendorf numeration system (see below), and
binary strings $x$ and $y$, and accepts if and only if
$(n)_{\varphi}=x.y^{R}$. Here $y^{R}$ denotes the reversal of the string
$y$.222This representation is called “folded”; it is useful in part because
the coefficients corresponding to small (in absolute value) powers of
$\varphi$ are grouped together when read by an automaton. However, their
article is rather challenging to read and they did not explicitly present this
automaton.

The first goal of this paper is to explain how the Frougny-Sakarovitch
automaton can be, rather easily, computed explicitly using existing software;
namely, the free software Walnut initially developed by Hamoon Mousavi [27].
This software can prove or disprove theorems about automatic sequences and
their generalizations, using a decision procedure for a certain extension of
Presburger arithmetic [33]. It suffices to express the desired assertions in
first-order logic. Furthermore, if the particular logical statement has free
variables, Walnut will compute a finite automaton accepting precisely those
values of the free variables making the statement true. Finally, if a formula
$F$ has two or more free variables, say $n$ and $x_{1},x_{2},\ldots x_{t}$,
Walnut can enumerate the number of $t$-tuples $(x_{1},\ldots,x_{t})$ such that
$F(n,x_{1},\ldots,x_{t})$ evaluates to TRUE.

Once we have this automaton, we can use it to easily reprove existing results
from the literature in a straightforward and uniform manner. For example, we
reprove some results recently considered by Dekking and Van Loon [14]. They
called a finite $\varphi$-representation (not necessarily canonical) of an
integer $n$ a Knott expansion if it does not end in $011$, and they developed
a rather complicated method for computing the number of different Knott
expansions of $n$. We will see that the Frougny-Sakarovitch automaton allows
us to enumerate Knott expansions, and thereby recover the results of Dekking
and Van Loon in a purely “automatic” fashion, without any tedious inductions.
Furthermore, by simply changing the conditions we impose on the form of the
expansion, we can easily and “automatically” enumerate other types of
expansions. The second goal of the paper is to illustrate these techniques and
obtain a number of new results.

The paper is organized as follows. In Section 2 we construct the Frougny-
Sakarovitch automaton. In Sections 3–LABEL:eight we prove a variety of old and
new results about $\varphi$-representations. In particular, in Theorem 6 we
prove a 2012 conjecture of Dale Gerdemann. In Section LABEL:three we discuss
Knott expansions; in Section LABEL:four we discuss a different type of
expansion, called a “natural expansion”, introduced by Dekking and Van Loon;
and in Section LABEL:fiveb we discuss DVL-expansions. Finally, in Section
LABEL:ten we discuss more general expansions for algebraic integers.

##  2 The Frougny-Sakarovitch automata

We will need two different representations of integers: the Zeckendorf system
and the negaFibonacci system.

Let the Fibonacci numbers be defined by the recurrence $F_{n}=F_{n-1}+F_{n-2}$
and initial conditions $F_{0}=0$ and $F_{1}=1$. Note that this uniquely
defines $F_{n}$ for all integers $n$ (even negative integers).

In the well-known Zeckendorf system [25, 37], we write a non-negative integer
$n$ as a sum $n=\sum_{2\leq i\leq t}a_{i}F_{i}$ with $a_{i}\in\\{0,1\\}$. We
abbreviate this by the expression $[x]_{F}$, where $x=a_{t}a_{t-1}\cdots
a_{2}$. This representation is unique if we impose the condition
$a_{i}a_{i+1}\not=1$; we let $(n)_{F}$ denote the canonical representation
obeying this condition. Thus $(43)_{F}=10010001$.

It will also be useful to be able to represent negative integers. In the
negaFibonacci system [7, 34], we write an integer $n$ (positive, negative, or
zero) as a sum $n=\sum_{1\leq i\leq t}a_{i}F_{-i}$, where again
$a_{i}\in\\{0,1\\}$. We abbreviate this by the expression $[x]_{-F}$, where
$x=a_{t}\cdots a_{1}$. Again, this representation is unique if we impose the
condition $a_{i}a_{i+1}\not=1$; we let $(n)_{-F}$ denote the canonical
representation obeying this condition. Thus $(43)_{-F}=101001010$.

We start by constructing the first Frougny-Sakarovitch automaton. It has three
inputs over $\\{0,1\\}$ that are read in parallel: $w,x,$ and $y$. Here

  * •

$w$ is the (canonical) Zeckendorf representation of some integer $n$,

  * •

$x$ is the left part of a $\varphi$-representation

  * •

$y^{R}$ is the right part of a $\varphi$-representation

and the automaton accepts if and only if $n=[x.y]_{\varphi}$. Notice that we
impose no other conditions on $x$ and $y$; they are simply arbitrary binary
strings. However, $w$ is assumed to contain no occurrence of $11$. All three
inputs are allowed to have any number of leading zeros, which permits the
inputs to be of the same length so they can be read simultaneously in
parallel.

The basic idea is very simple. As Bergman [2] noted (and easily proved by
induction), we have $\varphi^{k}=F_{k}\varphi+F_{k-1}$ for all integers $k$.
It now follows that

$\displaystyle\sum_{0\leq i<r}a_{i}\varphi^{i}$ $\displaystyle=\sum_{0\leq
i<r}a_{i}(F_{i}\varphi+F_{i-1})$ $\displaystyle=\left(\sum_{0\leq
i<r}a_{i}F_{i}\right)\varphi+\left(\sum_{0\leq i<r}a_{i}F_{i-1}\right)$
$\displaystyle=\left(a_{0}F_{0}+a_{1}F_{1}+\sum_{2\leq
i<r}a_{i}F_{i}\right)\varphi+a_{0}F_{-1}+a_{1}F_{0}+a_{2}F_{1}+\sum_{2\leq
j<r-1}a_{j+1}F_{j}$ $\displaystyle=(a_{1}+[a_{r}\cdots
a_{2}]_{F})\varphi+[a_{r}\cdots a_{3}]_{F}+a_{0}+a_{2}.$ (2)

Similarly,

$\displaystyle\sum_{1\leq i\leq s}b_{i}\varphi^{-i}$
$\displaystyle=\sum_{1\leq i\leq s}b_{i}(F_{-i}\varphi+F_{-i-1})$
$\displaystyle=\left(\sum_{1\leq i\leq s}b_{i}F_{-i}\right)\varphi+\sum_{1\leq
i\leq s}b_{i}F_{-i-1}$ $\displaystyle=[b_{s}\cdots
b_{1}]_{-F}\varphi+[b_{s}\cdots b_{1}0]_{-F}.$ (3)

Thus, the left part of a $\varphi$-representation is easily expressed as a
linear combination $c\varphi+d$, in terms of shifted Zeckendorf
representations, and the right part of a $\varphi$-representation is easily
expressed as a linear combination $c^{\prime}\varphi+d^{\prime}$, in terms of
shifted negaFibonacci representations. Then
$n=(c+c^{\prime})\varphi+d+d^{\prime}$ implies that $n=[a_{r-1}\cdots
a_{1}a_{0}.b_{1}b_{2}\cdots b_{s}]$ if and only if

$\displaystyle c^{\prime}$ $\displaystyle=-c$ (4) $\displaystyle n$
$\displaystyle=d+d^{\prime}$ (5)

both hold.

These are conditions that can be expressed in first-order logic, and hence we
can build an automaton to check them. In Walnut we can build this automaton
from smaller, easily-digestible pieces, as we now describe.

It may be helpful to have a short summary of Walnut syntax.

  * •

reg defines a regular expression

  * •

def defines an automaton based on a logical formula

  * •

eval evaluates a formula with no free variables and returns TRUE or FALSE

  * •

E represents the existential quantifier $\exists$; A represents the universal
quantifier $\forall$

  * •

& is logical AND, | is logical OR, => is logical implication; <=> is logical IFF; ~ is logical NOT

  * •

?msd_fib instructs Walnut that numbers should be expressed in Zeckendorf
representation; ?msd_neg_fib does the same thing for negaFibonacci
representation

###  2.1 Zeckendorf normalizer

We need a “normalizer” for Zeckendorf expansions; it takes $x$ and $y$ as
inputs, with $x$ an arbitrary binary string and $y$ a canonical Zeckendorf
expansion of some integer $n$, and accepts if and only if $n=[x]_{F}$. Such an
automaton can be found, for example, in [3, 32]. It has $5$ states (or $4$ if
one omits the dead state). We call it fibnorm.

Figure 1: The automaton fibnorm.

###  2.2 NegaFibonacci normalizer

We also need the analogous “normalizer” for negaFibonacci expansions; it takes
$x$ and $y$ as inputs, with $x$ an arbitrary binary string and $y$ a canonical
negaFibonacci expansion of some integer $n$, and accepts if and only if
$n=[x]_{-F}$. Such an automaton has $5$ states (or $4$ if one omits the dead
state). We call it negfibnorm.

Figure 2: The automaton negfibnorm.

###  2.3 Shifters

As we have seen in Eqs. (2) and (3), we need to shift some representations
left or right. We do this with the following automata:

  * •

shiftl takes arguments $x$ and $y$, and accepts if $y$ is $x$ shifted to the
left (and $0$ inserted at the right).

  * •

shiftr takes arguments $x$ and $y$, and accepts if $y$ equals the string $x$
shifted to the right (and the least significant digit disappears).

We can easily build these with regular expressions as follows:

    reg shiftl {0,1} {0,1} "([0,0]|[0,1][1,1]*[1,0])*":
    reg shiftr {0,1} {0,1} "([0,0]|[1,0][1,1]*[0,1])*(()|[1,0][1,1]*)":

###  2.4 Last bits

Again, as we have seen in Eqs. (2) and (3), we need the ability to extract the
last, second-to-last, or third-to-last bits of a string. These can easily be
specified with regular expressions. We create three: lstbit1, lstbit2, and
lstbit3. Here lstbit$n$ takes arguments $x$ and $y$, where $x\in\\{0,1\\}^{*}$
and $y$ is the representation of either $0$ or $1$, and accepts if $y$ is the
$n$’th-last bit of $x$ (or $0$ if $|x|<n$).

    reg lstbit1 {0,1} msd_fib "()|(([0,0]|[1,0])*([0,0]|[1,1]))":
    reg lstbit2 {0,1} msd_fib "()|[0,0]|[1,0]|(([0,0]|[1,0])*
    (([0,0]([0,0]|[1,0]))|([1,0]([0,1]|[1,1]))))":
    reg lstbit3 {0,1} msd_fib "()|[0,0]|[1,0]|(([0,0]|[1,0])
    ([0,0]|[1,0]))|(([0,0]|[1,0])*(([0,0]([0,0]|[1,0])
    ([0,0]|[1,0]))|([1,0]([0,0]|[1,0])([0,1]|[1,1]))))":

###  2.5 Converting from NegaFibonacci to Zeckendorf

Finally, we will need to be able to convert negaFibonacci representation to
Zeckendorf representation. We need two automata:

  * •

fibnegfib takes two arguments $x$ and $y$, where $x=(n)_{F}$ for some $n\geq
0$ and $y=(m)_{-F}$, and accepts if $n=m$. It has $12$ states.

  * •

fibnegfib2 takes two arguments $x$ and $y$, where $x=(n)_{F}$ for some $n\geq
0$ and $y=(m)_{-F}$, and accepts if $n=-m$. It has $9$ states.

###  2.6 Constructing the first Frougny-Sakarovitch automaton

We now have all the pieces we need to construct the first Frougny-Sakarovitch
automaton directly from the formulas (2) and (3). We do this with the
following Walnut code:

    def phipartleft "?msd_fib Er,s,y,b $shiftr(x,r) & $shiftr(r,s) &
       $fibnorm(s,y) & $lstbit2(x,b) & z=y+b":
    def intpartleft "?msd_fib Er,s,t,y,b,c $shiftr(x,r) & $shiftr(r,s) &
       $shiftr(s,t) & $fibnorm(t,y) & $lstbit1(x,b) & $lstbit3(x,c) &
       z=y+b+c":
    def phipartright "?msd_neg_fib $negfibnorm(x,z)":
    def intpartright "?msd_neg_fib Er $shiftl(x,r) & $negfibnorm(r,z)":

    def frougny1 "?msd_fib Et1,t2 $phipartleft(x,t1) &
       $phipartright(y,?msd_neg_fib t2) & $fibnegfib2(t1,t2)":
    # accepts if the phi part of inputs x and y sums to 0

    def frougny2 "?msd_fib Et1, t2, x2 $intpartleft(x,t1)
       & $intpartright(y,?msd_neg_fib t2) & (((?msd_neg_fib t2<0) &
       $fibnegfib2(x2,?msd_neg_fib t2) & ?msd_fib t1=n+x2)|
       (((?msd_neg_fib t2>=0) & $fibnegfib(x2,?msd_neg_fib t2) &
       ?msd_fib n=t1+x2)))":
    # accepts if the integer parts of inputs x and y sum to n

    def frougny3 "?msd_fib $frougny1(x,y) & $frougny2(n,x,y)":
    fixleadzero frougny frougny3:

Here phipartleft (resp., intpartleft) computes the coefficient of $\varphi$
(resp., the coefficient of $1$) in the expression (2). Similarly, phipartright
(resp., intpartright) does the same thing for (3).

Next, frougny1 checks the condition (4) and frougny2 checks the condition (5).
Finally, frougny checks the conjunction of the two conditions. The resulting
automaton frougny has 116 states.

If we want a simpler automaton, namely, where $x.y^{R}$ must be a canonical
representation (no $11$), we can intersect the automaton frougny with a simple
automaton imposing this condition on $x$ and $y$. This gives us a second
Frougny-Sakarovitch automaton saka with only $39$ states.

    def saka2 "?msd_fib $frougny(n,?msd_fib x,?msd_fib y) & $no11xy(x,y)":
    fixleadzero saka saka2:

With this automaton we can easily prove the following characterization of the
canonical $\varphi$-representation of $F_{n}$, which is the content of both
[23, Corollary 6] and [14, Proposition 3.1].

######  Proposition 1.

We have

  * •

$(F_{4i})_{\varphi}=100(0100)^{i-1}.(0100)^{i-1}1$, $i\geq 1$;

  * •

$(F_{4i+1})_{\varphi}=1000(1000)^{i-1}.(1000)^{i-1}1001$, $i\geq 1$;

  * •

$(F_{4i+2})_{\varphi}=1(0001)^{i}.(0001)^{i}$, $i\geq 0$;

  * •

$(F_{4i+3})_{\varphi}=10(0010)^{i}.(0010)^{i}01$, $i\geq 0$.

###### Proof.

We apply the automaton saka to the Fibonacci numbers $F_{n}$ for $n\geq 2$:

    reg isfib msd_fib "0*10*":
    def prop31a "?msd_fib $saka(n,x,y) & $isfib(n)":
    fixleadzero prop31 prop31a:

The resulting automaton is depicted in Figure 3.

Figure 3: Canonical $\varphi$-representation of $F_{n}$.

Inspection of the automaton shows that, ignoring leading zeros, there are
essentially four different acceptance paths:

  * •

$[1,1,0][0,0,1][0,0,0]([0,0,0][0,1,0][0,0,1][0,0,0])^{*}$.

  * •

$[1,1,1][0,0,0][0,0,0][0,0,1]([0,1,0][0,0,0][0,0,0][0,0,1])^{*}$;

  * •

$[1,1,0]([0,0,1][0,0,0][0,0,0][0,1,0])^{*}$;

  * •

$[1,1,1][0,0,0]([0,0,0][0,0,1][0,1,0][0,0,0])^{*}$;

These correspond to the cases $n\equiv 0,1,2,3$ (mod $4$), respectively, and
prove the result. ∎

We can also see from Figure 3 a partial explanation for the periodicity (mod
4) in the Frougny-Sakarovitch construction.

Exactly the same techniques can be used to prove a similar result for the
Lucas numbers, defined by $L_{0}=2$, $L_{1}=1$, and $L_{n}=L_{n-1}+L_{n-2}$.
We omit the details.

######  Theorem 2.

We have

  * •

$(L_{2i})_{\varphi}=10^{2i}.0^{2i-1}1$, $i\geq 1$;

  * •

$(L_{2i+1})_{\varphi}=(10)^{i}1.(01)^{i}$, $i\geq 0$.

One very useful feature of the automaton saka is we can use it to completely
characterize the folded representations of all natural numbers.

######  Theorem 3.

The string $a_{r-1}\cdots a_{1}a_{0}.a_{-1}a_{-2}\cdots a_{-r}$ is the
$\varphi$-representation of an integer $n\geq 0$ if and only if

$[a_{r-1},a_{-r}][a_{r-2},a_{1-r}]\cdots[a_{1},a_{-2}][a_{0},a_{-1}]$

is accepted by the automaton in Figure 4.

Figure 4: Automaton accepting the folded representations of all $n\geq 0$.

###### Proof.

We use the Walnut code

    def berg "?msd_fib En $saka(n,x,y)":

∎

Let us now turn to characterizing the right part of canonical
$\varphi$-representations. Dekking [12, Thm. 7.3] proved the following result:

######  Theorem 4.

If a binary string is of even length, ends in a $1$, and contains no $11$,
then it appears as the right part of the $\varphi$-representation of some
natural number $n$.

###### Proof.

To prove this, we make a Walnut regular expression for strings of even length
ending in a $1$. Some care is needed here, for two reasons: first, the
representation of the right part is “folded”, so we’re really talking about
beginning with a $1$ instead of ending. Second, our automata may have leading
zeros in the (reversed) representation of the right part, for the reasons
mentioned previously. Keeping these two points in mind, we use the following
Walnut code:

    reg has11 {0,1} "(0|1)*11(0|1)*":
    def rightp2 "?msd_fib En,x $saka(n,x,y)":
    fixleadzero rightp rightp2:
    reg evenl {0,1} "(0*)|(0*1(0|1)((0|1)(0|1))*)":
    eval thm73 "?msd_fib Ay $rightp(y) <=> ($evenl(y) & ~$has11(y))":

And Walnut returns TRUE. ∎

Similarly, we can prove a companion theorem for the left part of canonical
$\varphi$-representations. This appears to be new.

######  Theorem 5.

A binary string $x$ appears as the left part of a $\varphi$-representation of
some $n$ if and only if $x$ has no $11$ and does not have a suffix of the form
$1(00)^{i}1$.

###### Proof.

We use the following Walnut code:

    def leftp2 "?msd_fib En,y $saka(n,x,y)":
    fixleadzero leftp leftp2:
    reg suff {0,1} "(0|1)*1(00)*1":
    eval claim "?msd_fib Ax $leftp(x) <=> ((~$suff(x))&(~$has11(x)))":

And Walnut returns TRUE. ∎

It is easy to see that every positive integer has infinitely many (possibly
non-canonical) $\varphi$-representations; for example, we may write
$2=[10.01]_{\varphi}=[10.0011]_{\varphi}=[10.001011]_{\varphi}=\cdots$.
However, there can only be finitely many distinct left parts among all of
these. How many are there? We can use Walnut to “automatically” compute a
special kind of formula for this quantity, called a linear representation.

A linear representation for a function $f$ from $\Sigma^{*}$ to $\mathbb{N}$
is a triple $(v,\gamma,w)$, where $v$ is a $t$-element row vector, $\gamma$ is
a $t\times t$ matrix-valued morphism, and $w$ is a $t$-element column vector,
such that $f(x)=v\gamma(x)w$. For more information about linear
representations, see [4].

Let us find a linear representation for $p(n)$, the number of distinct left
parts of $\varphi$-representations for $n$. We can do this with the following
Walnut command:

    def numleft n "?msd_fib Ey $frougny(n,x,y)":

This gives us a linear representation of rank $112$ to compute $p(n)$, which
can be minimized to a linear representation of rank $28$. The first few terms
of this sequence are given in Table 2.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$p(n)$ | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 5 | 4 | 5 | 4 | 4 | 5 | 6 | 6 | 5 | 4 | 5 | 7
Table 2: First few values of $p(n)$.

This is sequence A362970 in the OEIS.

##  3 Base-$\varphi$ sum of digits

Dekking [11] studied the sum-of-digits function for base-$\varphi$
representations. If $n=\sum_{L\leq i\leq R}d_{i}\varphi^{i}$ is the canonical
base-$\varphi$ representation, then we define $s(n)=\sum_{L\leq i\leq
R}d_{i}$. The sequence $s(n)$ is sequence A055778 in the OEIS.

Let us compute a linear representation for $s(n)$. The idea is to define an
automaton with two binary inputs $x,y$ that accepts precisely if $y$ has a
single $1$ in a position matching a $1$ in $x$. Then the number of pairs
$(x,y)$ accepted corresponds to the number of $1$’s in $x$. We can then find
linear representations for the left and right parts of $(n)_{\varphi}$.

    reg match1 {0,1} {0,1} "([0,0]|[1,0])*[1,1]([0,0]|[1,0])*":
    def countl "?msd_fib Ex,y $saka(n,x,y) & $match1(x,t)":
    def countr "?msd_fib Ex,y $saka(n,x,y) & $match1(y,u)":
    def sl n "?msd_fib $countl(n,t)":
    def sr n "?msd_fib $countr(n,u)":

This gives a linear representation of rank $99$ for $s_{L}$ and one of rank
$82$ for $s_{R}$. When minimized, we get a representation of rank $19$ for
$s_{L}$ and one of rank $21$ for $s_{R}$. We can then find a linear
representation of rank $40$ for $s$ by summing these two linear
representations. This can be minimized to a linear representation for $s$ of
rank $21$; this allows efficient computation of $s(n)$.

We now show how to apply our automaton saka to solve an open problem due to
Dale Gerdemann in 2012, and stated in the text for sequence A055778 in the
OEIS. Once again, the proof is more or less purely computational, but here we
need some additional computational tools.

######  Theorem 6.

The sum of the digits for $n$ in Zeckendorf representation is always at most
the sum of the digits for $n$ in canonical base-$\varphi$ representation.

###### Proof.

Let $|x|_{a}$ denote the number of occurrences of the symbol $a$ in the string
$x$. It is easy, using the techniques above, to obtain a linear representation
of rank $23$ for the difference $|(n)_{\varphi}|_{1}-|(n)_{F}|_{1}$. However,
there is no algorithm for determining whether a given linear representation
computes a function that is always non-negative, so this linear representation
does not seem to be useful to solve the problem. Instead, we use a different
technique.

Recall that the automaton ${\tt saka}$ takes three inputs in parallel—$n$,
$x$, and $y$—and accepts if $x.y^{R}$ is the canonical
$\varphi$-representation for $n$. The transitions of this automaton are
therefore of the form $[a,b,c]$ where $a,b,c\in\\{0,1\\}$. Suppose an input
$a_{1}\cdots a_{t}$, $b_{1}\cdots b_{t}$, $c_{1}\cdots c_{t}$ is accepted.
Then $|(n)_{\varphi}|_{1}-|(n)_{F}|_{1}=\sum_{1\leq i\leq
t}(b_{i}+c_{i})-a_{i}$.

Therefore, we can take the automaton for ${\tt saka}$ and form a directed
graph $G$ from it by replacing the transition on the triple $[a,b,c]$ with a
weight labeled $b+c-a$. The assertion that $|(n)_{\varphi}|_{1}-|(n)_{F}|_{1}$
is always non-negative then follows from the stronger claim that

every path from the initial state to any state has a non-negative sum of
weights. (6)

But this is precisely the minimum-weight path problem solved by the Bellman-
Ford algorithm. We ran this algorithm on $G$ and verified that assertion (6)
holds. ∎

Next, one can consider those $n$ for which
$|(n)_{F}|_{1}=|(n)_{\varphi}|_{1}$. These correspond to the paths of weight
$0$ in the graph $G$ just discussed. One can easily verify, by explicit
enumeration, that all simple cycles of $G$ (i.e., no repeated vertices except
at the beginning and end of the cycle) have weight $\geq 0$, and furthermore
one can determine all those of weight $0$ (there are $26$ of them).

Let be $P$ be an accepting path of weight $0$. If $P$ contains a cycle $C$, by
above the weight of $C$ is non-negative, by removing $C$, we get an accepting
path of $P^{\prime}$ of weight $\leq 0$. But there are no negative-weight
accepting paths, so $C$ must also be of weight $0$ and hence so so is
$P^{\prime}$. We can then rule out possible cycles by considering the lowest-
weight path from the initial state to the first state of $C$ and similarly
from the first state of $C$ to a final state; these weights must sum to $0$.
Of the $26$ possible cycles, only three possibilities remain (up to choice of
the initial state of the cycle). By considering the possible cycles and how
they join up, we get the following automaton:

Figure 5: Automaton for weight-$0$ paths.

To get the accepted set of $n$, we project to the first coordinate and
determinize the resulting automaton. Thus we have proved the following result:

######  Theorem 7.

The following automaton accepts precisely those $n$ in Fibonacci
representation for which $|(n)_{F}|_{1}=|(n)_{\varphi}|_{1}$.

Figure 6: Automaton for weight-$0$ paths.

Similarly, one can study the sum of all the bits of the base-$\varphi$
representation, taken modulo $2$.

    reg sum2 {0,1} {0,1} "([0,0]|[1,1])*(([0,1]|[1,0])([0,0]|[1,1])*
    ([0,1]|[1,0])([0,0]|[1,1])*)*([0,1]|[1,0])([0,0]|[1,1])*":
    # sum of all the bits of x and y, mod 2

    def sdpr2 "?msd_fib Ex,y $saka(n,x,y) & $sum2(x,y)":
    # sum of digits of phi-rep mod 2 is 1

This gives a $73$-state automaton for this binary sequence. It is sequence
A330037 in the OEIS.

The automata frougny and saka that we have constructed make it very easy to
compute other quantities related to $\varphi$-representations. For example,
let us define $s_{L}(n)$ to be the sum of the bits of the left part of the
$\varphi$-representation of $n$. This is apparently a new sequence, never
before studied; it is sequence A362716 in the OEIS. (Dekking [9, 11] studied
the sum $s(n)$ of all the bits of the $\varphi$-representation.)

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$s_{L}(n)$ | 0 | 1 | 1 | 1 | 2 | 1 | 2 | 1 | 2 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 2 | 3 | 1 | 2
Table 3: First few values of $s_{L}(n)$.

We can easily find a linear representation for $s_{L}(n)$ as follows:

    reg match1 {0,1} {0,1} "([0,0]|[1,0])*[1,1]([0,0]|[1,0])*":
    def count1 "?msd_fib Ex,y $saka(n,x,y) & $match1(x,t)":
    def sl n "?msd_fib $count1(n,t)":

This gives us a linear representation of rank $99$. This linear representation
can be minimized using an algorithm of Schützenberger discussed in [4, Chap.
2]. We get the following linear representation: $(v,\gamma,w)$ of rank $19$,
as follows:

$v=\left[\hbox{}\,\vbox{\scriptsize\hbox{$\begin{array}[]{@{}ccccccccccccccccccc@{}}1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\end{array}$}}\,\hbox{}\right]
$$\begin{aligned} \gamma(0)&=\left[\hbox{}\,&\gamma(1) &= \left[\hbox{}\,&w &=
\left[ \hbox{}\, \par Similarly, one can study the sum-of-digits function
$s_{R}(n)$ for the right part of the canonical $\varphi$-representation. We
prove a new theorem about it: \begin{theorem}The difference
$d(n):=s_{R}(n+1)-s_{R}(n)$ is a Fibonacci-automatic sequence taking values in
$\\{-1,0,1\\}$ only. \end{theorem} \par\@proof We use the following {\tt
Walnut} code. \begin{verbatim} reg match1 {0,1} {0,1}
"([0,0]|[1,0])*[1,1]([0,0]|[1,0])*": def countr "?msd_fib Ex,y $saka(n,x,y) &
$match1(y,u)": def sr n "?msd_fib $countr(n,t)": def sr1 n "?msd_fib
$countr(n+1,t)": \end{verbatim} This produces linear representations for
$s_{R}(n)$ (rank $82$; minimizes to rank $21$) and $s_{R}(n+1)$ (rank $64$;
minimizes to rank $17$). From this we can produce a linear representation for
$d(n)=s_{R}(n+1)-s_{R}(n)$ of rank $38$, which minimizes to one of rank $17$.
We can then do the ``semigroup trick'' to show that the resulting sequence is
Fibonacci automatic. It is depicted in Figure~{}\ref{srd}. \begin{figure}[H]
\begin{center} \includegraphics[width=469.75499pt]{srdiff.pdf} \end{center}
\@@toccaption{{\lx@tag[ ]{{7}}{Fibonacci automaton for
$d(n)$.}}}\@@caption{{\lx@tag[: ]{{Figure 7}}{Fibonacci automaton for
$d(n)$.}}} \end{figure} \qed\end@proof
\par\par\par\@@numbered@section{section}{toc}{Length of base-$\varphi$
representations} \par Similarly, one can study the length $\ell(n)$ of the
left part of $(n)_{\varphi}$ (or, alternatively, one more than the exponent of
the highest power of $\varphi$ appearing in $(n)_{\varphi}$). This is sequence
\href https://oeis.org/A362692 in the OEIS. \begin{table}[H] \begin{center}
\begin{tabular}[]{c|ccccccccccccccccccccc}$n$&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\\\
\hline\cr$\ell(n)$&0&1&2&3&3&4&4&5&5&5&5&5&6&6&6&6&6&6&7&7\end{tabular}
\end{center} \@@toccaption{{\lx@tag[ ]{{4}}{First few values of
$\ell(n)$.}}}\@@caption{{\lx@tag[: ]{{Table 4}}{First few values of
$\ell(n)$.}}}\end{table} \par Here the idea is to create a simple automaton,
{\tt onepos}, that accepts binary strings $x$ and $t$ if and only if $t$
contains a single $1$ and it occurs at or to the right of the first $1$ in
$x$. Then we simply count the number of such $t$: \begin{verbatim} def
intlength "?msd_fib Ex,y $saka(n,x,y) & $onepos(x,t)": def intl n "?msd_fib
$intlength(n,t)": \end{verbatim} The resulting linear representation can be
minimized to the following linear representation of rank $9$:
\end{aligned}{\\\ }
\centerline{\hbox{\url{https://cs.uwaterloo.ca/~shallit/walnut.html} \ .}} For
the definitions of {\tt Walnut} automata that we did not give explicitly, see
{\\\ } \centerline{\hbox{\url{https://cs.uwaterloo.ca/~shallit/papers.html} \
.}} \par Most of the other results of
\cite[cite]{[\@@bibref{}{Dekking&van.Loon:2023}{}{}]} can be proved using the
analogous techniques. \par In principle, everything we have said in this paper
can be applied to $\beta$-expansions, where $\beta$ is a quadratic Pisot
number. The choice $\beta=\varphi$ was particularly easy in the current
version of {\tt Walnut}, because it already has Fibonacci and negaFibonacci
numbers implemented, and adders for integers represented in these forms.
\par\par\@@unnumbered@section{section}{}{Acknowledgments} \par I thank Anna
Lubiw, George Bergman, Jacques Sakarovitch, Michel Dekking, and Daniel Berend
for helpful comments and insights. \par
\thebibliography\lx@bibitem{Berend&Frougny:1994} D.~{}Berend and C.~{}Frougny.
\lx@bibnewblock Computability by finite automata and {Pisot} bases.
\lx@bibnewblock{\em Math. Systems Theory} {\bf 27} (1994), 275--282.
\par\lx@bibitem{Bergman:1957} G.~{}Bergman. \lx@bibnewblock A number system
with an irrational base. \lx@bibnewblock{\em Math. Mag.} {\bf 31} (1957), 98--
110. \par\lx@bibitem{Berstel:2001} J.~{}Berstel. \lx@bibnewblock An exercise
on {Fibonacci} representations. \lx@bibnewblock{\em RAIRO Inform. Th\'{e}or.
App.} {\bf 35} (2001), 491--498. \par\lx@bibitem{Berstel&Reutenauer:2011}
J.~{}Berstel and C.~{}Reutenauer. \lx@bibnewblock{\em Noncommutative Rational
Series With Applications}, Vol. 137 of {\em Encyclopedia of Mathematics and
Its Applications}. \lx@bibnewblock Cambridge University Press, 2011.
\par\lx@bibitem{Bertrand-Mathis:1989} A.~{}Bertrand-Mathis. \lx@bibnewblock
Comment \'{e}crire les nombres entiers dans une base qui n'est pas
enti\\`{e}re. \lx@bibnewblock{\em Acta Math. Hung.} {\bf 54} (1989), 237--241.
\par\lx@bibitem{Brown:1969} J.~{}L. Brown, Jr. \lx@bibnewblock Unique
representation of integers as sums of distinct {Lucas} numbers.
\lx@bibnewblock{\em Fibonacci Quart.} {\bf 7} (1969), 243--252.
\par\lx@bibitem{Bunder:1992} M.~{}W. Bunder. \lx@bibnewblock Zeckendorf
representations using negative {Fibonacci} numbers. \lx@bibnewblock{\em
Fibonacci Quart.} {\bf 30} (1992), 111--115.
\par\lx@bibitem{Chu&Luo&Miller:2022} H.~{}V. Chu, D.~{}C. Luo, and S.~{}J.
Miller. \lx@bibnewblock On {Zeckendorf} related partitions using the {Lucas}
sequence. \lx@bibnewblock{\em Fibonacci Quart.} {\bf 60} (2022), 111--119.
\par\lx@bibitem{Dekking:2020} F.~{}M. Dekking. \lx@bibnewblock The sum of
digits function of the base phi expansion of the natural numbers.
\lx@bibnewblock{\em INTEGERS} {\bf 20} (2020), \\#A45 (electronic).
\par\lx@bibitem{Dekking:2020b} F.~{}M. Dekking. \lx@bibnewblock Base phi
representations and golden mean beta-expansions. \lx@bibnewblock{\em Fibonacci
Quart.} {\bf 58} (2020), 38--48. \par\lx@bibitem{Dekking:2021} F.~{}M.
Dekking. \lx@bibnewblock The sum of digits functions of the {Zeckendorf} and
the base phi expansions. \lx@bibnewblock{\em Theoret. Comput. Sci.} {\bf 859}
(2021), 70--79. \par\lx@bibitem{Dekking:2023} F.~{}M. Dekking. \lx@bibnewblock
The structure of base phi expansions. \lx@bibnewblock Arxiv preprint
arXiv:2305.08349 [math.NT], May 15 2023. Available at
\url{https://arxiv.org/abs/2305.08349}. \par\lx@bibitem{Dekking&van.Loon:2021}
M.~{}Dekking and A.~{}van Loon. \lx@bibnewblock On the representation of the
natural numbers by powers of the golden mean. \lx@bibnewblock Arxiv preprint
arXiv:2111.07544 [math.NT], November 15 2021. Available at
\url{https://arxiv.org/abs/2111.07544}. \par\lx@bibitem{Dekking&van.Loon:2023}
M.~{}Dekking and A.~{}van Loon. \lx@bibnewblock Counting base phi
representations. \lx@bibnewblock Arxiv preprint arXiv:2304.11387 [math.NT],
April 22 2023. Available at \url{https://arxiv.org/abs/2304.11387}.
\par\lx@bibitem{Fleischer&Shallit:2021} L.~{}Fleischer and J.~{}O. Shallit.
\lx@bibnewblock Automata, palindromes, and reversed subwords.
\lx@bibnewblock{\em J. Automata, Languages, and Combinatorics} {\bf 26}
(2021), 221--253. \par\lx@bibitem{Frougny:1989} C.~{}Frougny. \lx@bibnewblock
Linear numeration systems, $\theta$-developments and finite automata.
\lx@bibnewblock In B.~{}Monien and R.~{}Cori, editors, {\em STACS 89}, Vol.
349 of {\em Lecture Notes in Computer Science}, pp. 144--155. Springer-Verlag,
1989. \par\lx@bibitem{Frougny:1991a} C.~{}Frougny. \lx@bibnewblock
Representation of numbers in non-classical numeration systems. \lx@bibnewblock
In P.~{}Kornerup and D.~{}W. Matula, editors, {\em Proc. 10th IEEE Symp.
Computer Arithmetic}, pp. 17--21. IEEE Press, 1991.
\par\lx@bibitem{Frougny:1992a} C.~{}Frougny. \lx@bibnewblock Representations
of numbers and finite automata. \lx@bibnewblock{\em Math. Systems Theory} {\bf
25} ({}1992), 37--60. \par\lx@bibitem{Frougny:1992b} C.~{}Frougny.
\lx@bibnewblock{Syst\\`{e}mes} de {num\'{e}ration} {lin\'{e}aires} et
$\theta$-repr\'{e}sentations. \lx@bibnewblock{\em Theoret. Comput. Sci.} {\bf
94} ({}1992), 223--236. \par\lx@bibitem{Frougny:1992c} C.~{}Frougny.
\lx@bibnewblock Confluent linear numeration systems. \lx@bibnewblock{\em
Theoret. Comput. Sci.} {\bf 106} (1992), 183--219.
\par\lx@bibitem{Frougny:1992d} C.~{}Frougny. \lx@bibnewblock How to write
integers in non-integer base. \lx@bibnewblock In I.~{}Simon, editor, {\em 1st
Latin American Symposium on Theoretical Informatics (LATIN '92)}, Lecture
Notes in Computer Science, pp. 154--164. Springer-Verlag, {}1992.
\par\lx@bibitem{Frougny:2003} C.~{}Frougny. \lx@bibnewblock On-line digit set
conversion in real base. \lx@bibnewblock{\em Theoret. Comput. Sci.} {\bf 292}
(2003), 221--235. \par\lx@bibitem{Frougny&Sakarovitch:1999} C.~{}Frougny and
J.~{}Sakarovitch. \lx@bibnewblock Automatic conversion from {Fibonacci}
representation to representation in base $\varphi$, and a generalization.
\lx@bibnewblock{\em Internat. J. Algebra Comput.} {\bf 9} (1999), 351--384.
\par\lx@bibitem{Hart&Sanchis:1999} E.~{}Hart and L.~{}Sanchis. \lx@bibnewblock
On the occurrence of {$F_{n}$} in the {Zeckendorf} decomposition of
{$nF_{n}$}. \lx@bibnewblock{\em Fibonacci Quart.} {\bf 37} (1999), 21--33.
\par\lx@bibitem{Lekkerkerker:1952} C.~{}G. Lekkerkerker. \lx@bibnewblock
Voorstelling van natuurlijke getallen door een som van getallen van
{Fibonacci}. \lx@bibnewblock{\em Simon Stevin} {\bf 29} (1952), 190--195.
\par\lx@bibitem{Lothaire:2002} M.~{}Lothaire. \lx@bibnewblock{\em Algebraic
Combinatorics on Words}, Vol.~{}90 of {\em Encyclopedia of Mathematics and Its
Applications}. \lx@bibnewblock Cambridge University Press, 2002.
\par\lx@bibitem{Mousavi:2021} H.~{}Mousavi. \lx@bibnewblock Automatic theorem
proving in {{\tt Walnut}}. \lx@bibnewblock Arxiv preprint, arXiv:1603.06017
[cs.FL], May 25 2021. Available at \url{http://arxiv.org/abs/1603.06017}.
\par\lx@bibitem{Parry:1960} W.~{}Parry. \lx@bibnewblock On the
$\beta$-expansions of real numbers. \lx@bibnewblock{\em Acta Math. Acad. Sci.
Hung.} {\bf 11} (1960), 401--416. \par\lx@bibitem{Renyi:1957}
A.~{}{R\'{e}nyi}. \lx@bibnewblock Representations for real numbers and their
ergodic properties. \lx@bibnewblock{\em Acta Math. Acad. Sci. Hung.} {\bf 8}
(1957), 477--493. \par\lx@bibitem{Rousseau:1995} C.~{}Rousseau.
\lx@bibnewblock The phi number system revisited. \lx@bibnewblock{\em Math.
Mag.} {\bf 68} (1995), 283--284. \par\lx@bibitem{Sanchis&Sanchis:2001} G.~{}R.
Sanchis and L.~{}A. Sanchis. \lx@bibnewblock On the frequency of occurrence of
$\alpha^{i}$ in the $\alpha$-expansions of the positive integers.
\lx@bibnewblock{\em Fibonacci Quart.} {\bf 39} (2001), 123--137.
\par\lx@bibitem{Shallit:2021} J.~{}Shallit. \lx@bibnewblock Robbins and
{Ardila} meet {Berstel}. \lx@bibnewblock{\em Inform. Process. Lett.} {\bf 167}
(2021), 106081. \par\lx@bibitem{Shallit:2022} J.~{}Shallit.
\lx@bibnewblock{\em The Logical Approach To Automatic Sequences: Exploring
Combinatorics on Words with {\tt Walnut}}, Vol. 482 of {\em London Math. Soc.
Lecture Note Series}. \lx@bibnewblock Cambridge University Press, 2022.
\par\lx@bibitem{Shallit&Shan&Yang:2023} J.~{}Shallit, S.~{}L. Shan, and K.-H.
Yang. \lx@bibnewblock Automatic sequences in negative bases and proofs of some
conjectures of {Shevelev}. \lx@bibnewblock{\em RAIRO Inform. Th\'{e}or. App.}
{\bf 57} (2023), 4. \par\lx@bibitem{Sloane:2023} N.~{}J.~{}A. Sloane et~{}al.
\lx@bibnewblock The on-line encyclopedia of integer sequences. \lx@bibnewblock
Electronic resource, available at \url{https://oeis.org}, 2023.
\par\lx@bibitem{Stewart&Tall:1979} I.~{}N. Stewart and D.~{}O. Tall.
\lx@bibnewblock{\em Algebraic Number Theory}. \lx@bibnewblock Chapman and
Hall, 1979. \par\lx@bibitem{Zeckendorf:1972} E.~{}Zeckendorf.
\lx@bibnewblock{Repr\'{e}sentation} des nombres naturels par une somme de
nombres de {Fibonacci} ou de nombres de {Lucas}. \lx@bibnewblock{\em Bull.
Soc. Roy. {Li\\`{e}ge}} {\bf 41} (1972), 179--182. \par\endthebibliography
\par\@add@PDF@RDFa@triples\par\end{document}$