# A General Approach to Proving Properties of Fibonacci Representations via
Automata Theory

Jeffrey Shallit111Research funded by a grant from NSERC, 2018-04118. and Sonja
Linghui Shan School of Computer Science, University of Waterloo, Waterloo, ON
N2L 3G1, Canada<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We provide a method, based on automata theory, to mechanically prove the
correctness of many numeration systems based on Fibonacci numbers. With it,
long case-based and induction-based proofs of correctness can be replaced by
simply constructing a regular expression (or finite automaton) specifying the
rules for valid representations, followed by a short computation. Examples of
the systems that can be handled using our technique include Brown’s lazy
representation (1965), the far-difference representation developed by Alpert
(2009), and three representations proposed by Hajnal (2023). We also provide
three additional systems and prove their validity.

##  1 Introduction

Given an increasing sequence $(s_{n})_{n\geq 0}$ of positive integers, a
numeration system is a way of expressing natural numbers as a linear
combination of the $s_{n}$. Many different numeration systems, such as
representation in base $k$, or the more exotic systems based on the Fibonacci
numbers, have been proposed. For example, recall that the Fibonacci numbers,
sequence A000045 in the On-Line Encyclopedia of Integer Sequences (OEIS), are
defined by the recurrence $F_{n}=F_{n-1}+F_{n-2}$ for $n\geq 2$ and the
initial values $F_{0}=0$, $F_{1}=1$. Consider writing a non-negative integer
$n$ as a sum of distinct Fibonacci numbers $F_{i}$ for $i\geq 2$. Some
numbers, such as $12$, have only one such representation
$(12=8+3+1=F_{6}+F_{4}+F_{2})$, while others have many:
$8=F_{6}=F_{5}+F_{4}=F_{5}+F_{3}+F_{2}$.

There are two very desirable characteristics of a numeration system. First,
completeness: every natural number should have a representation. Second,
unambiguity: no natural number should have two or more different
representations. These two goals are typically achieved by restricting the
types of representations that are considered valid within the system. If a
system achieves both goals, we say it is perfect. For Fibonacci
representations, various perfect systems have been proposed.

Among all possible perfect systems based on Fibonacci numbers, one is
particularly useful: the Zeckendorf or greedy representation. This
representation can be computed as follows: first, choose the largest index $i$
such that $F_{i}\leq n$. Then the representation for $n$ is $F_{i}$ plus the
(recursively-computed) representation for $n-F_{i}$. The representation for
$0$ is the empty sum of $0$ Fibonacci numbers. A simple induction now shows
that the greedy algorithm produces a representation for every natural number,
which is evidently unique.

This representation was originally noted by Zeckendorf, but was first
published by Lekkerkerker [13] and only later by Zeckendorf himself [21]. It
was also anticipated, in much more general form, by Ostrowski [16].

An alternative (but equivalent) definition of Zeckendorf representation is to
impose a condition that valid representations must obey. For example, we could
require that a representation be valid if and only if no two consecutive
Fibonacci numbers appear in the sum.

It is convenient to express arbitrary sums of distinct Fibonacci numbers as
strings of digits over a finite alphabet (in analogy with base-$k$
representation). Let $x=a_{1}\cdots a_{t}$ be a string (or word) made up of
integer digits. We define its value as a Fibonacci representation as follows:

$[x]_{F}:=\sum_{1\leq i\leq t}a_{i}F_{t+2-i}.$ (1)

Note that these strings are in “most-significant-digit” first format. For
example, $[2101]_{F}=2F_{5}+F_{4}+F_{2}=14$.

It is also useful to define a (partial) inverse to $[x]_{F}$. By $(n)_{F}$ we
mean the binary string $x$ such that $x$ is the Zeckendorf representation of
$n$; alternatively, such that $[x]_{F}=n$ and $x$ contains no occurrence of
the block $11$. In what follows, we adopt this string-based point of view
almost exclusively. We can think of the condition “no occurrence of the block
$11$” as a rule, specifying which representations are valid, adopted precisely
to guarantee both completeness and unambiguity.

In formal language theory, a language $L$ is a (finite or infinite) collection
of strings. A rule is then encoded by the language or set of strings that obey
the rule. Completeness then becomes the assertion that for all $n$ there
exists a string $x\in L$ such that $[x]_{F}=n$, while unambiguity becomes the
assertion that there do not exist distinct strings $x,y\in L$ such that
$[x]_{F}=[y]_{F}$. 222We adopt the convention that two strings are considered
to be the same if they differ only in the number of leading zeros. Thus, for
example, $[100]_{F}=[0100]_{F}=3$ are the same representation.

Let us look at another example involving the Fibonacci numbers, one that is
much less well known: the so-called lazy representation [4]. In this system,
representation as a sum of Fibonacci numbers corresponds (via Eq. (1)) to a
binary string having no occurrence of the block $00$ (where leading zeros are
not even considered). Once again, this rule provides a numeration system that
is both complete and unambiguous [4]. Table 1 gives both greedy (Zeckendorf)
and lazy representations for the first few natural numbers.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
---|---|---|---|---|---|---|---|---|---|---|---|---
greedy | $\epsilon$ | 1 | 10 | 100 | 101 | 1000 | 1001 | 1010 | 10000 | 10001 | 10010 | 10100
lazy | $\epsilon$ | 1 | 10 | 11 | 101 | 110 | 111 | 1010 | 1011 | 1101 | 1110 | 1111
Table 1: Greedy and lazy Fibonacci representations.

The greedy and lazy representations are certainly not the only possible
perfect numeration systems based on the Fibonacci numbers. In fact, there are
uncountably many such systems! These result from making a choice, for all $n$
having at least two different representations as sums of distinct Fibonacci
numbers, about which particular representation is chosen to be valid. (By a
result of Robbins [18], “most” numbers have more than one representation as a
sum of distinct Fibonacci numbers.)

If we demand that the set of valid representations forms a regular
language—that is, accepted by a finite automaton; see Section 2—there are
still infinitely many different systems (although only countably many). For
example, consider choosing the $t$’th largest possible representation for $n$
in lexicographic order (if there are at least $t$), and otherwise the
lexicographically first. It will follow from results below that, for each
$t\geq 0$, this choice gives a regular language $L_{t}$ of valid
representations.

Some natural questions then arise: given a language $L$ encoding the “rule” a
representation must obey (such as no occurrence of the block $11$, or no
occurrence of the block $00$), how can we determine if the corresponding set
of Fibonacci representations is complete and unambiguous? And if it is
complete, how can we efficiently find a representation for a given number $n$?
Up to now, each new system proposed required a new proof, often a rather
tedious case-based proof by induction. In this paper we provide a general
framework for answering these questions “automatically”, via an algorithm, in
the case where the language of valid representations is regular.

These ideas are capable of generalization. For example, we can also consider
representations for all integers $\mathbb{Z}$, instead of just the natural
numbers $\mathbb{N}$. This can be achieved in two distinct ways:

  * •

By allowing a larger digit set, say, $\\{-1,0,1\\}$;

  * •

By using the so-called negaFibonacci system, based on the Fibonacci numbers of
negative index $F_{-n}$ for $n\geq 1$.

Once again, we would like a choice of valid representations that is complete
and unambiguous.

In this paper we show how to decide these properties, provided that the set of
valid representations forms a regular language (which is indeed the case for
all the proposed systems in the literature).

Here is an outline of the paper. In Section 2, we explain the basics of
automata theory needed to understand the rest of the paper. In Section 3, we
discuss how to test completeness and ambiguity for systems using digits $0$
and $1$ only. In Section 4 we discuss systems using digits $-1,0,1$ only. In
Section 5 we discuss representations for all integers, not just the natural
numbers. In Section 6 we discuss an entirely new type of Fibonacci
representation based on dictionary order. Finally, in Section 7 we describe a
few of the new Fibonacci representations we found through exhaustive search of
small automata.

##  2 The decision procedure and Walnut

We assume the reader is familiar with the basics of automata theory as
discussed, for example, in [11].

The following particular case of a theorem of Büchi [7] (as later corrected by
Bruyère et al. [6] is our principal tool in the paper.

######  Theorem 1.

There is a decision procedure that, given a first-order logical formula $F$
involving natural numbers, comparisons, automata, and addition, and no free
variables, will decide the truth or falsity of $F$. Furthermore, if $F$ has
free variables, the procedure constructs a DFA accepting those values of the
free variables (in Fibonacci representation) that make $F$ evaluate to TRUE.

For more information about the specific case of the decision procedure for
Fibonacci representation, see [15].

We should explain how automata can process pairs, triples, and generally
$k$-tuples of inputs. This is done by replacing the input alphabet $\Sigma$
with the alphabet
$\overbrace{\,\Sigma\times\Sigma\times\cdots\times\Sigma\,}^{k\rm\ times}$. In
other words, inputs are $k$-tuples of alphabet symbols. The $i$’th input then
corresponds to the concatenation of the $i$’th components of all the
$k$-tuples. Of course, this means that all $k$ inputs have to have the same
length; this is achieved by padding shorter inputs, if necessary, with leading
zeros.

The decision procedure of Theorem 1 has been implemented in free software
called Walnut, originally created by Hamoon Mousavi [14]; also see the book
[20]. We recall some of the basics of Walnut syntax:

  * •

eval evaluates a formula with no free variables and returns TRUE or FALSE; def
defines an automaton for future use; reg defines a regular expression.

  * •

In a regular expression, the period is an abbreviation for the entire
alphabet.

  * •

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

  * •

A denotes $\forall$ (for all); E denotes $\exists$ (there exists).

  * •

?msd_fib tells Walnut to evaluate an arithmetic expression using Fibonacci
representation.

We use Walnut to do the computations needed to verify that a given system is
complete and unambiguous. For much more about Walnut, including a link to
download it, visit

https://cs.uwaterloo.ca/~shallit/walnut.html .

##  3 Representation of natural numbers using digits 0 and 1 only

In this section we consider representations of the natural numbers by
Fibonacci numbers using digits $0$ and $1$ only.

The first step is to find an automaton that can convert from an arbitrary
Fibonacci representation to the greedy or Zeckendorf representation. To do
this we use the following simple observation:

######  Proposition 2.

We can convert a binary string $x$ to a Zeckendorf representation $y$ for the
same number using the following algorithm: first append a 0 on the front, if
necessary. Then scan the string from left to right, replacing each occurrence
of “ $011$” successively with “ $100$”.

###### Proof.

Clearly each such replacement does not change the value of $[x]_{F}$. The
algorithm terminates because each replacement lowers the total number of $1$’s
by $1$. Finally, the algorithm clearly cannot result in two consecutive $1$’s,
because it introduces two consecutive $0$’s, only the second of which can
later change to a $1$. ∎

We can implement this idea as a DFA $C$ that takes two inputs in parallel, $x$
and $y$, and accepts if and only if both $[x]_{F}=[y]_{F}$ and $y$ is a valid
Zeckendorf representation; that is, it contains no two consecutive $1$’s. It
suffices to keep track of $[x^{\prime}]_{F}-[y^{\prime}]_{F}$ for the prefix
$x^{\prime}$ of $x$ seen so far, and similarly for the prefix $y^{\prime}$ of
$y$ seen so far. Note that we assume that $x$ and $y$ have the same length,
with the shorter of the two prefixed by leading zeros, if necessary. We can
think of this as a “converter” or “normalizer” that allows us to turn
arbitrary Fibonacci representations into Zeckendorf representations. It is
depicted in Figure 1.

Figure 1: DFA $C$ for conversion to the Zeckendorf representation.

This automaton was given by Berstel [3] in a slightly different form. Also see
[19].

As an example, consider the input $[0,1][1,0][1,0][1,1][0,0]$ to $C$, whose
first components spell out $x=01110$ and whose second components spell out
$y=10010$. Starting in state $0$, the automaton visits, successively, states
$1,2,0,3,0$, and hence accepts—as it should, since $[x]_{F}=[y]_{F}$.

We now state one of our main results.

######  Theorem 3.

There is an algorithm that, given rules that specify which representations are
valid (in the form of a regular language $L$ of all valid representations),
will decide if the corresponding numeration system based on the Fibonacci
numbers is complete and unambiguous for $\mathbb{N}$.

###### Proof.

Using Theorem 1, it suffices to express the properties of completeness and
unambiguity as a first-order logic formula $F$. Once this is done, the
decision algorithm can determine if $F$ is true or false.

Completeness says every integer has a representation in $L$. We can express
this as follows:

$\forall n\ \exists x\ x\in L\ \wedge\ [x]_{F}=n,$ (2)

Unambiguity says that no integer has two distinct representations in $L$. We
can express this as follows:

$\neg\exists x,y\in L\ (\neg\operatorname{equal}(x,y))\ \wedge\
[x]_{F}=[y]_{F}.$ (3)

Here $\operatorname{equal}$ means that $x$ and $y$ are the same, up to leading
zeros. ∎

Furthermore, if $L$ is a regular language that provides a system that is
complete, we can find a representation in $L$ for $n$ efficiently. The first
step is to represent $n$ in Fibonacci representation, say using the greedy
algorithm. Construct a new automaton from fcanon by using two intersections.
The first intersection is with an automaton with a first component that
belongs to $L$, while the second component is arbitrary. The second
intersection is with an automaton where the first component is arbitrary, and
the second is of the form $0^{*}(n)_{F}$. This gives a new automaton of
$O(\log n)$ states, and it now suffices to find any accepting path (a path
from the initial state to the final state). This can be done in linear time in
the number of states using depth-first or breadth-first search. This gives us
an $O(\log n)$ algorithm to find a representation. Thus we have proved:

######  Theorem 4.

Suppose $L$ is a regular language. If $L$ is complete, we can find a
representation for an integer $n$ in $O(\log n)$ time.

######  Remark 5.

Here we use the convention of the so-called “word RAM” model, where we assume
that $n$ fits in a single machine word, or more generally that we can perform
basic operations on integers with $O(\log n)$ bits in unit time.

All this can be carried out mechanically with Walnut. Here all we have to do
is define the language $L$ of valid representations (say, with a regular
expression) and type in the Walnut commands corresponding to the two logical
assertions (2) and (3). We illustrate this with two examples.

The first is the lazy representation mentioned previously, and discussed first
by Brown [4]. The first step is to give a regular expression defining a valid
representation in Brown’s system:

    reg lazyExclude {0,1} "0*1(0|1)*00(0|1)*":
    def lazy "~$lazyExclude(s)":

This gives a $4$-state automaton testing the lazy criterion that is depicted
in Figure 2.

Figure 2: DFA for Brown’s lazy representation.

We test the completeness and unambiguity for Brown’s system as follows.

    reg equal {0,1} {0,1} "([0,0]|[1,1])*":
    eval brown1 "?msd_fib An Es $fcanon(s,n) & $lazy(s)":
    eval brown2 "?msd_fib ~En,s,t $lazy(s) & $lazy(t) & (~$equal(s,t))
        & $fcanon(s,n) & $fcanon(t,n) ":

Both return TRUE. Given these results, we have now proven that the lazy
representation is complete and unambiguous.

For a second example, see the Appendix.

##  4 Representation using digits $-1$, $0$, and $1$

We now turn to representations using digits $-1$, $0$, and $1$ in the
Fibonacci system.

Recently, Hajnal [10] described three Fibonacci representations using Eq. (1)
to associate a string $x=e_{t}e_{t-1}\cdots e_{2}\in\\{-1,0,1\\}^{*}$ with a
natural number $n$: alternating, even, and odd. Using induction and a case-
based argument, he proved that each of these three representations is complete
and unambiguous.

Using automata, we can replace his rather long arguments with our general
approach. We first describe each of his systems, and show that the set of
valid representations for all natural numbers is a regular language.

The alternating representation requires a representation to fulfill four
conditions:

  1. 1.

the most significant nonzero term is positive,

  2. 2.

two adjacent nonzero terms cannot be of the same sign,

  3. 3.

two adjacent nonzero terms have at least one zero in between, and

  4. 4.

if there are two or more nonzero terms, then there has to be at least two
zeros between the last and the second last nonzero terms.

We denote a number $n$ in this representation as $[n]_{A}$. For example,
$[9]_{A}=10\bar{1}001$, where $\bar{1}$ is used for $-1$.

For the alternating representation, we can use the following Walnut code:

    reg altInclude1 {-1,0,1} "(0*|0*1.*)":
    reg altExclude1 {-1,0,1} ".*(10*1|[-1]0*[-1]).*":
    reg altExclude2 {-1,0,1} ".*(1[-1]|[-1]1).*":
    reg altInclude2 {-1,0,1} "(0*|0*10*|.*(100+[-1]|[-1]00+1)0*)":
    def alt "~$altExclude1(s) & ~$altExclude2(s) & $altInclude1(s) & $altInclude2(s)":

The result is an automaton of 12 states that checks whether an input over the
alphabet $\\{-1,0,1\\}$ is alternating, and is illustrated in Figure 3.

Figure 3: DFA for the alternating condition.

The even representation requires three conditions:

  1. 1.

the most significant nonzero term is positive,

  2. 2.

only positions indexed with even numbers, such as $e_{2}$, can have nonzero
terms, and

  3. 3.

two adjacent nonzero terms cannot both be $-1$.

We denote a number $n$ in this representation as $[n]_{E}$. For example,
$[14]_{E}=10\bar{1}0001$.

    reg evenInclude {-1,0,1} "(0*|0*1(0[-1]|01|00)*)":
    reg evenExclude {-1,0,1} ".*[-1]0*[-1].*":
    def even "$evenInclude(s) & ~$evenExclude(s)":

This gives us a 5-state automaton to check the even condition, which is
illustrated in Figure 4.

Figure 4: DFA for the even condition.

The odd representation adds an epsilon term to the sum in Eq. (1), therefore
associating a string $e_{t}e_{t-1}\cdots e_{2}\epsilon$, where
$\epsilon\in\\{-1,0\\}$, with a number $n$. The odd representation requires
the string to meet three conditions:

  1. 1.

the most significant nonzero term is positive,

  2. 2.

only positions indexed with odd numbers (such as $e_{3}$) and the epsilon term
are allowed to be nonzero, and

  3. 3.

two adjacent nonzero terms cannot both be $-1$.

We denote a number $n$ in this representation as $[n]_{O}$. For example,
$[14]_{O}=100010\bar{1}$, where $\bar{1}$ is used for $\epsilon=-1$.

We express the odd representation conditions in Walnut as follows. Notice we
relax the third condition (required in [10]) slightly by limiting its
application to only the string $e_{t}e_{t-1}\cdots e_{2}$ without the
$\epsilon$ term.

    reg oddInclude {-1,0,1} "(0*|0*10([-1]0|10|00)*)":
    reg oddExclude {-1,0,1} ".*[-1]0*[-1].*":
    def odd "$oddInclude(s) & ~$oddExclude(s)":

This gives us a 5-state automaton to check the odd condition, which is
illustrated in Figure 5.

Figure 5: DFA for the odd condition.

It now remains to use our technique to show that these representations are all
complete and unambiguous. In order to do this, we need a “converter” automaton
that can compare representations using digits $-1,0,1$ to ordinary Zeckendorf
representation. We can construct such an automaton based on fcanon as follows.
The idea is to use one automaton to “select” the positive digits of a
representation, another one to “select” the negative digits, and then do an
(implicit) subtraction to obtain the value of the representation.

    reg posdigits {-1,0,1} {0,1} "([1,1]|[-1,0]|[0,0])*":
    reg negdigits {-1,0,1} {0,1} "([-1,1]|[1,0]|[0,0])*":
    def fcanon2 "?msd_fib Et,u,w,s $negdigits(x,t) & $posdigits(x,u) &
       $fcanon(t,w) & $fcanon(u,s) & z+w=s":

This gives a 24-state automaton fcanon2, the analogue of fcanon, for doing the
conversion.

Let us now check that the alternating representation of Hajnal is both
complete and unambiguous.

    reg same {-1,0,1} {-1,0,1} "([-1,-1]|[0,0]|[1,1])*":
    eval altRep1 "?msd_fib An Es $fcanon2(s,n) & $alt(s)":
    # evaluates to TRUE, 4 ms
    eval altRep2 "?msd_fib ~En,s,t $alt(s) & $alt(t) & (~$same(s,t))
        & $fcanon2(s,n) & $fcanon2(t,n)":
    # evaluates to TRUE, 31 ms

Similarly, we can check the even and odd representations, as follows:

    eval evenRep1 "?msd_fib An Es $fcanon2(s,n) & $even(s)":
    # evaluates to TRUE, 1 ms
    eval evenRep2 "?msd_fib ~En,s,t $even(s) & $even(t) & (~$same(s,t))
        & $fcanon2(s,n) & $fcanon2(t,n)":
    # evaluates to TRUE, 4 ms
    eval oddRep1 "?msd_fib An (Es $fcanon2(s,n) & $odd(s)) |
       (Et $fcanon2(t,n+1) & $odd(t))":
    # evaluates to TRUE, 7 ms
    eval oddRep2 "~En,s,t $odd(s) & $odd(t) & (~$same(s,t))
        & $fcanon2(s,n) & $fcanon2(t,n)":
    # evaluates to TRUE, 4 ms

This completes our proof that all three systems of Hajnal are complete and
unambiguous.

######  Remark 6.

We noticed, by testing the following, that this representation is also
complete if $\epsilon\in\\{1,0\\}$ instead of $\epsilon\in\\{-1,0\\}$ as
required in [10].

    eval oddRep3 "?msd_fib An
        (Es $fcanon2(s,n) & $odd(s)) | (Et $fcanon2(t,n-1) & $odd(t))":
    # evaluates to TRUE, 4 ms

##  5 Representations for all integers

In this section we investigate two different ways to represent all integers
(not just the natural numbers) using Fibonacci representations.

Alpert [2] described a far-difference representation for Fibonacci numbers
that writes every integer (not just the natural numbers), with a Fibonacci
numeration system using the digits $-1,0,1$. In Alpert’s system, the far-
difference representation requires the string to have

  1. 1.

at least three zeros between any two nonzero terms of the same sign, and

  2. 2.

at least two zeros between any two nonzero terms of different signs.

We use $[n]_{A}$ to denote a natural number in this representation: for
example, $[-38]_{A}=\bar{1}000\bar{1}001$. One nice feature of Alpert’s system
is that it is very easy to negate an integer: all we have to do is change the
sign of each digit.333The three systems proposed by Hajnal also exhibit this
property. Therefore, if we exclude the condition stating ”the most significant
nonzero term is positive” from the three systems, they can be perfect
representations for all integers.

We express the far-difference representation conditions in Walnut as follows.

    reg exclude1 {-1, 0, 1} ".*([-1][-1]|[-1]0[-1]|[-1]00[-1]|11|101|1001).*":
    reg exclude2 {-1, 0, 1} ".*([-1]1|1[-1]|10[-1]|[-1]01).*":
    def alpert "~$exclude1(s) & ~$exclude2(s)":

This gives a $7$-state automaton that checks the Alpert condition, as
illustrated in Figure 6.

Figure 6: DFA for the Alpert conditions.

To check completeness and ambiguity, we have to check positive and negative
integers separately. In addition to fcanon2, we need an automaton fcanon2_neg
that takes a string $x$ over the alphabet $\\{-1,0,1\\}$ and a natural number
$n\geq 0$ as input and accepts if $[x]_{F}=-n$.

    def fcanon2_neg "?msd_fib Et,u,w,s $negdigits(x,t) & $posdigits(x,u) &
       $fcanon(t,w) & $fcanon(u,s) & z+s=w":

We can then prove the completeness and unambiguity of this system as follows.

    eval farDiff1_pos "?msd_fib An Es $fcanon2(s,n) & $alpert(s)":
    eval farDiff1_neg "?msd_fib An Es $fcanon2_neg(s,n) & $alpert(s)":
    # both evaluate to TRUE, 3 ms
    eval farDiff2_pos "?msd_fib ~En,s,t $alpert(s) & $alpert(t)
        & (~$same(s,t)) & $fcanon2(s,n) & $fcanon2(t,n)":
    eval farDiff2_neg "?msd_fib ~En,s,t $alpert(s) & $alpert(t)
        & (~$same(s,t)) & $fcanon2_neg(s,n) & $fcanon2_neg(t,n)":
    # both evaluate to TRUE, 9 ms

Thus we have easily verified the correctness of Alpert’s conditions.

Bunder [8] invented a different numeration system for all integers, called the
negaFibonacci system. In this system, we write integers as a sum of distinct
Fibonacci numbers with negative indices, subject to the condition that no two
consecutive Fibonacci numbers can be used. Since $F_{-n}=(-1)^{n+1}F_{n}$ for
$n\geq 1$, this is the same as enforcing the requirement in a Fibonacci
representation $a_{t}F_{t}+\cdots+a_{2}F_{2}+a_{1}F_{1}$ with digits
$a_{i}\in\\{-1,0,1\\}$, (a) only the terms with odd indices are allowed to be
positive and only the terms with even indices are allowed to be negative and
(b) no two consecutive nonzero digits can appear. We can enforce this
condition as follows:

    reg bunder1 {-1,0,1} ".*1.(..)*":
    reg bunder2 {-1,0,1} ".*[-1](..)*":
    reg bunder3 {-1,0,1} ".*((1[-1])|([-1]1)).*":
    def bunder "~$bunder1(x) & ~$bunder2(x) & ~$bunder3(x)":

which gives the automaton in Figure 7.

Figure 7: DFA for the Bunder conditions.

We can then check completeness and unambiguity much as we did for Alpert’s
system, but there is a new wrinkle: representations have an extra digit at the
end, corresponding to the term $a_{1}F_{1}$, that must be taken care of. To do
this we introduce a “shifter” automaton that shifts a representation to the
right, and a “lastbit” that determines if the last bit of a representation is
$1$ or $0$. The shifter is called rshiftfib and is displayed in Figure 8.

Figure 8: Shifter automaton.

Then Bunder’s representation can be verified to be complete and unambiguous,
as follows:

    reg lastbit {-1,0,1} {0,1} "([0,0]|[1,0]|[-1,0])*([1,1]|[0,0])":
    def fcanon3 "?msd_fib Et,u,m $rshiftfib(x,t) &
       $lastbit(x,u) & $fcanon2(t,m) & z=m+u":
    def fcanon3_neg "?msd_fib Et,u,m $rshiftfib(x,t) &
       $lastbit(x,u) & $fcanon2_neg(t,m) & z=m-u":
    eval bunder1_pos "?msd_fib An Es $fcanon3(s,n) & $bunder(s)":
    eval bunder1_neg "?msd_fib An Es $fcanon3_neg(s,n) & $bunder(s)":
    # both evaluate to TRUE, 1 ms
    eval bunder2_pos "?msd_fib ~En,s,t $bunder(s) & $bunder(t)
        & (~$same(s,t)) & $fcanon3(s,n) & $fcanon3(t,n)":
    eval bunder2_neg "?msd_fib ~En,s,t $bunder(s) & $bunder(t)
        & (~$same(s,t)) & $fcanon3_neg(s,n) & $fcanon3_neg(t,n)":
    # both evaluate to TRUE, 12 ms

##  6 Maximum dictionary order representation

In this section we consider an entirely new Fibonacci representation based on
dictionary order. We first introduce how strings are compared in dictionary
order. Let $s=s_{1}s_{2}\cdots s_{m}$ and $t=t_{1}t_{2}\cdots t_{n}$ where
$m\leq n$ be two strings. Let $i$ such that $1\leq i\leq m$ be the first
position where $s_{i}\neq t_{i}$. If $s_{i}<t_{i}$, then $s<t$ in dictionary
order; otherwise $s>t$. For example, $1\underline{0}11<1\underline{1}00$, but
$10\underline{1}1>10\underline{0}1$. If there is no such position $i$, then
either $s=t$ or $s$ is a proper prefix of $t$. In this latter case we say
$s<t$. For example, $110=110$ and $110<1100$.

Consider a representation of natural numbers by always choosing the largest
string representation in dictionary order for every number. Since every number
has a Fibonacci-based representation, the representation is complete. Since we
choose only one Fibonacci-based representation for each number, the
representation is unambiguous. Representations of the first few numbers are
given in Table 2.

$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
---|---|---|---|---|---|---|---|---|---|---|---
$(n)_{D}$ | 1 | 10 | 11 | 101 | 110 | 111 | 1010 | 1100 | 1101 | 1110 | 1111
Table 2: Representations for the first few numbers.

We now show that

######  Theorem 7.

The set of largest Fibonacci representations in dictionary order forms a
regular language.

###### Proof.

The idea is to construct a comparator DFA $C_{D}$ that can take two
representations in parallel and decide if one is greater than the other, in
dictionary order.

In order to take two representations in parallel, they would have to be the
same length, and therefore the shorter one would have to be padded with
leading zeros to make it the same length as the longer one. In this case, it
is not hard to see that no automaton can do the needed comparison.

However, in our case, we can take advantage of the following fact: two
Fibonacci representations for the same number cannot be of wildly different
lengths.

######  Lemma 8.

The lengths of two Fibonacci-based representation strings for the same natural
number differ by one at most (not counting leading zeros).

###### Proof.

Let $s$ and $t$ be two Fibonacci representations for a natural number $m$.
Without loss of generality, assume that $s$ is longer. Suppose the leading $1$
digit of $s$ corresponds to $F_{i}$. If $s$ and $t$ differ in length by more
than one, then $t$ is a sum of some $F_{j}$’s where $j\leq i-2$. Now a classic
identity on Fibonacci numbers states that $\sum_{0\leq j\leq
n}F_{j}=F_{n+2}-1$. Using this relation, we conclude that
$\sum_{j=2}^{i-2}F_{j}=F_{i}-2<F_{i}$. Therefore $s$ and $t$ do not represent
the same number. ∎

Using this fact, it is indeed possible to compare two strings in dictionary
order with an automaton.

Figure 9: DFA $C_{D}$ for comparing strings in dictionary order.

It is shown in Fig. 9 and takes two inputs in parallel, $s^{\prime}$ and
$t^{\prime}$. Let $s$ and $t$ be $s^{\prime}$ and $t^{\prime}$ without leading
zeros. The DFA $C_{D}$ accepts if and only if $s$ is greater than $t$ in
dictionary order. We have three cases to consider: $|s|>|t|$, $|s|<|t|$, and
$|s|=|t|$. We now discuss how the $8$ states of $C_{D}$ relate to these $3$
cases.

  * •

State $0$ is the initial state.

  * •

State $1$ is reached if $|s|>|t|$; that is, if $s^{\prime}$ starts with $1$
and $t^{\prime}$ starts with $01$.

  * •

State $2$ is reached when $|s|>|t|$, $s$ ends in $1$, and based on the inputs
so far, $t$ is a proper prefix of $s$ therefore $s>t$.

  * •

State $3$ is reached when $|s|>|t|$, $s$ ends in $0$, and based on the inputs
so far, $t$ is a proper prefix of $s$ therefore $s>t$.

  * •

State $4$ is reached when $|s|<|t|$ and $t$ ends in $1$, and based on the
inputs so far, $s$ is a proper prefix of $t$ therefore $s<t$.

  * •

State $5$ is reached when $|s|<|t|$ and $t$ ends in $0$, and based on the
inputs so far, $s$ is a proper prefix of $t$ therefore $s<t$.

  * •

State $6$ is reached when $|s|=|t|$ and, based on the inputs so far, we have
$s=t$.

  * •

State $7$ is one of the accepting states. It is reached when we can identify a
position $i$ such that $s_{i}>t_{i}$ . Additional symbols read, starting from
this state, cannot change the comparison result.

It is now easy to verify that the transitions maintain the invariants
corresponding to each state, and we leave this to the reader. ∎

Using the comparator automaton, we can build a DFA $D$ that finds the maximum
dictionary order representation for each natural number. The automaton $D$
takes two inputs in parallel: a number $n$ in Zeckendorf representation and a
string $s\in\\{0,1\\}^{*}$; and it only accepts if, out of all Fibonacci-based
representations of $n$, the string $s$ is the greatest based on dictionary
order. We implement $D$ in Walnut as follows.

    def dictOrder "$fcanon(s,n) & (At $fcanon(t,n) => ($dGreater(s,t)|$equal(s,t)))":

Here dictOrder implements the automaton $D$; fcanon, the automaton $C$; and
dGreater, the automaton $C_{D}$. The resulting automaton has $7$ states and is
depicted in Figure 10.

Figure 10: DFA $D$ for converting to dictionary order representation.

##  7 Finding new perfect systems of small complexity via exhaustive search

We see that a Fibonacci-based representation of natural numbers can be
represented by a language over the binary alphabet $\\{0,1\\}$. If the
language is regular, we can express it with a DFA and test its completeness
and unambiguity in Walnut. For example, the Zeckendorf representation can be
expressed as a $3$-state DFA and the Brown one, a $4$-state DFA. Therefore we
were curious about whether there exist other DFAs with a small number of
states that can qualify as complete and unambiguous representations. We
conducted an exhaustive search to find such automata and found a surprising
number of them. If we allow up to $7$ states, we found more than $28$ new
complete and unambiguous representations.444There could be more as the
heuristics we used to trim our search tree can sometimes exclude eligible
representations if, for two numbers $m,n$ where $m<n$, the representation of
$m$ is longer than that of $n$. We present two interesting examples out of the
seven new $6$-state representations.

######  Theorem 9.

Let $L=0^{*}(\epsilon|1|10(\epsilon|0|1)1^{*}(01^{+})^{*}(\epsilon|0))$. Then
$L$ is complete and unambiguous.

###### Proof.

We use the following Walnut code:

    reg one0sq {0,1} "0*(()|1|10(()|0|1)1*(01+)*(()|0))":
    eval one0sqTestC "?msd_fib An Ex $one0sq(x) & $fcanon(x,n)":
    eval one0sqTestU "?msd_fib ~En,x,y $one0sq(x) & $one0sq(y)
        & (~$equal(x,y)) & $fcanon(x,n) & $fcanon(y,n)":

Both returned TRUE. Here one0sq tests membership in $L$. ∎

Notice this representation allows $100$ at the very beginning but no other
consecutive $0$’s are allowed. This restriction on $00$ blocks is very similar
to Brown’s. In fact, Brown’s can be expressed, in the form of a regular
expression, as

$0^{*}(\epsilon|11^{*}(01^{+})^{*}(\epsilon|0))=0^{*}(\epsilon|1$$|10(\epsilon|0|1)$$1^{*}(01^{+})^{*}(\epsilon|0))$.

We can imagine that a new representation could be generated for allowing a
block of $00$ after the second $1$, or the third, or after both the first and
third $1$, or the first and fourth, etc. This offers another construction of
infinitely many perfect representations.

######  Theorem 10.

Let $L$ be the language accepted by the DFA $Z$. Then $L$ is complete and
unambiguous.

Figure 11: The DFA $Z$.

###### Proof.

We use the following Walnut code:

    eval azTestC "?msd_fib An Ex $az(x) & $fcanon(x,n)":
    eval azTestU "?msd_fib ~En,x,y $az(x) & $az(y) & (~$equal(x,y))
        & $fcanon(x,n) & $fcanon(y,n)":

Both returned TRUE. Here az tests membership in $L$. ∎

The strings in $L$ can end with a single $1$ or the block $11$ or an odd
number of $0$’s, but not an even number of $0$’s. Additionally, the strings
cannot contain the block “$11$” anywhere but the end. This restriction on
“$11$” is reminiscent of the Zeckendorf representation.

##  8 Final remarks

The ideas in this paper can be extended in many different ways. For example,
we could consider representations in terms of Fibonacci numbers of both
positive and negative index with various constraints [17], or representations
in terms of sums of the Lucas numbers [5], or other linear recurrences, such
as the Pell numbers [12] or Tribonacci numbers [9]. The automaton-based
approach can be used in all of these cases.

## References

  * [1]
  * [2] H. Alpert (2009): _Differences of multiple Fibonacci numbers_.  INTEGERS 9, 10.1515/INTEG.2009.061.  Paper #A57.
  * [3] J. Berstel (2001): _An exercise on Fibonacci representations_.  RAIRO Inform. Théor. App. 35, pp. 491–498, 10.1051/ita:2001127.
  * [4] J. L. Brown, Jr. (1965): _A new characterization of the Fibonacci numbers_.  Fibonacci Quart. 3(1), pp. 1–8.
  * [5] J. L. Brown, Jr. (1969): _Unique representation of integers as sums of distinct Lucas numbers_.  Fibonacci Quart. 7, pp. 243–252.
  * [6] V. Bruyère, G. Hansel, C. Michaux & R. Villemaire (1994): _Logic and $p$-recognizable sets of integers_.  Bull. Belgian Math. Soc. 1, pp. 191–238, 10.36045/bbms/1103408547.  Corrigendum, Bull. Belg. Math. Soc. 1 (1994), p. 577.
  * [7] J. R. Büchi (1960): _Weak second-order arithmetic and finite automata_.  Zeitschrift für mathematische Logik und Grundlagen der Mathematik 6, pp. 66–92, 10.1002/malq.19600060105.  Reprinted in S. Mac Lane and D. Siefkes, eds., The Collected Works of J. Richard Büchi, Springer-Verlag, 1990, pp. 398–424.
  * [8] M. W. Bunder (1992): _Zeckendorf representations using negative Fibonacci numbers_.  Fibonacci Quart. 30, pp. 111–115.
  * [9] L. Carlitz, R. Scoville & V.E. Hoggatt, Jr. (1972): _Fibonacci representations of higher order_.  Fibonacci Quart. 10, pp. 43–69, 94.
  * [10] P. Hajnal (2023): _A short note on numeration systems with negative digits allowed_.  Bull. Inst. Combin. Appl. 97, pp. 54–66.
  * [11] J. E. Hopcroft & J. D. Ullman (1979): _Introduction to Automata Theory, Languages, and Computation_.  Addison-Wesley.
  * [12] A. F. Horadam (1993): _Zeckendorf representations of positive and negative integers by Pell numbers_.  In G. E. Bergum, A. N. Philippou & A. F. Horadam, editors: Applications of Fibonacci Numbers, 5, Kluwer, pp. 305–316, 10.1007/978-94-011-2058-6_29.
  * [13] C. G. Lekkerkerker (1952): _Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci_.  Simon Stevin 29, pp. 190–195.
  * [14] H. Mousavi (2016): _Automatic theorem proving in Walnut_.  Arxiv preprint arXiv:1603.06017 [cs.FL], available at http://arxiv.org/abs/1603.06017.
  * [15] H. Mousavi, L. Schaeffer & J. Shallit (2016): _Decision Algorithms for Fibonacci-Automatic Words, I: Basic Results_.  RAIRO Inform. Théor. App. 50, pp. 39–66, 10.1051/ita/2016010.
  * [16] A. Ostrowski (1922): _Bemerkungen zur Theorie der Diophantischen Approximationen_.  Abh. Math. Sem. Hamburg 1, pp. 77–98,250–251, 10.1007/BF02940595.  Reprinted in Collected Mathematical Papers, Vol. 3, pp. 57–80.
  * [17] H. Park, B. Cho, D. Cho, Y. D. Cho & J. Park (2020): _Representations of integers as sums of Fibonacci numbers_.  Symmetry 12(10), 10.3390/sym12101625.  Paper 1625.
  * [18] N. Robbins (1996): _Fibonacci partitions_.  Fibonacci Quart. 34, pp. 306–313.
  * [19] J. Shallit (2021): _Robbins and Ardila meet Berstel_.  Inform. Process. Lett. 167, 10.1016/j.ipl.2020.106081.  Paper 106081.
  * [20] J. Shallit (2022): _The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut_.  London Math. Soc. Lecture Notes Series 482, Cambridge University Press, 10.1017/9781108775267.
  * [21] E. Zeckendorf (1972): _Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas_.  Bull. Soc. Roy. Liège 41, pp. 179–182.


DClust86 |  HAH $J045159.3+000645.9$ |  |  MACS $J0451.9+0006$ |  | $2449900135$ | $66$ |  |  |
DClust87 |  HAH $J051537.3-432514.2$ |  |  |  | $4139400014$ | $36$ |  |  |
DClust88 |  HAH $J051856.3-431439.1$ |  |  |  | $4114300083$ | $60$ |  |  |
DClust89 |  HAH $J051856.4-431444.4$ |  |  |  | $4114300083$ | $60$ |  |  |
DClust90 |  HAH $J052116.2-510409.5$ |  |  SPT-CL $J0521-5104$ |  | $4368600053$ | $42$ |  |  |
DClust91 |  HAH $J052214.2-362408.4$ |  |  |  | $3909700155$ | $34$ |  |  |
DClust92 |  HAH $J065327.1-574306.1$ |  |  SPT-CL $J0653-5744$ |  |  |  |  |  |
DClust93 |  HAH $J071718.8+374842.3$ |  |  MACS $J071718+374841$ |  |  |  |  |  |
DClust94 |  HAH $J071731.9+374449.9$ |  |  |  | $942200072$ | $56$ |  |  |
DClust95 |  HAH $J074704.6+693824.0$ |  |  |  | $154800014$ | $33$ |  |  |
DClust96 |  HAH $J080911.4+064341.9$ |  |  |  | $2171900062$ | $158$ |  |  |
DClust97 |  HAH $J084349.0+411635.4$ |  |  |  | $841300099$ | $63$ |  |  |
DClust98 |  HAH $J084959.8+360340.6$ |  |  |  | $995000060$ | $103$ |  |  RM $J085007.9+360413.7$ | $103$
DClust99 |  HAH $J091023.7+021049.2$ |  |  |  | $2377800058$ | $84$ |  |  |
DClust100 |  HAH $J091044.5+424945.8$ |  |  |  | $790800062$ | $36$ |  |  |
DClust101 |  HAH $J092141.2-062241.6$ |  |  |  | $2736400046$ | $119$ |  |  |
DClust102 |  HAH $J094058.7+074541.1$ |  |  MACS $J0940$ ACS |  | $2122300012$ | $118$ |  |  RM $J094053.7+074425.4$ | $107$
DClust103 |  HAH $J100050.2+013251.5$ |  |  |  | $2378700125$ | $131$ |  |  |
DClust104 |  HAH $J100142.8+015448.1$ |  |  |  | $2378700108$ | $99$ |  |  |
DClust105 |  HAH $J111554.8+013015.5$ |  |  MACS $J1115.8+0129$ |  | $2380000092$ | $49$ |  |  |
DClust106 |  HAH $J113305.2+500840.9$ |  |  MACS $J1133.2+5008$ |  | $561400014$ | $31$ |  |  RM $J113313.2+500840.5$ | $76$
DClust107 |  HAH $J115054.9-280548.7$ |  |  PLCK ESZ $G287.0+32.9$ |  |  |  |  |  |
DClust108 |  HAH $J130154.4+275347.0$ |  |  |  | $1306700027$ | $105$ |  |  |
DClust109 |  HAH $J130236.3+141055.0$ |  |  |  | $1869900048$ | $112$ |  |  |
DClust110 |  HAH $J133422.4+503133.0$ |  |  RX $J1334.5+5030$ POS1 |  | $563100033$ | $34$ |  |  |
DClust111 |  HAH $J134711.8-114157.8$ |  |  RX $J1347-1145$ ACS |  |  |  |  |  |
DClust112 |  HAH $J142952.3+554752.8$ |  |  |  | $425100125$ | $106$ |  |  |
DClust113 |  HAH $J143808.8+341940.3$ |  |  |  | $1078000014$ | $143$ |  |  |
DClust114 |  HAH $J144727.3+083001.9$ |  |  MACS $J1447.4+0827$ |  | $2102100021$ | $88$ |  |  RM $J144726.0+082825.1$ | $99$
DClust115 |  HAH $J151832.6-813031.8$ |  |  PLCK ESZ $G308.3-20.2$ |  |  |  |  |  |
DClust116 |  HAH $J161543.8-060959.7$ |  |  Abell $2163$ |  |  |  |  |  |
DClust117 |  HAH $J173142.8+225101.0$ |  |  MACS $J1731.6+2252$ |  | $1516300115$ | $87$ |  |  |
DClust118 |  HAH $J173647.0+461847.1$ |  |  |  | $678200065$ | $0$ |  |  |
DClust119 |  HAH $J175151.7+443859.0$ |  |  MACS $J1752.0+4440$ |  | $750100068$ | $78$ |  |  |
DClust120 |  HAH $J221450.1-140049.7$ |  |  MACS $J2214-1359$ |  | $3057300114$ | $117$ |  |  |
DClust121 |  HAH $J224154.3+173336.5$ |  |  MACS $J2241.8+1732$ |  | $1726600046$ | $86$ |  |  RM $J224158.1+173303.7$ | $63$
DClust122 |  HAH $J224901.9-443103.9$ |  |  |  | $4206000045$ | $167$ |  |  |
DClust123 |  HAH $J230104.7+300726.4$ |  |  |  | $1240500156$ | $73$ |  |  |
DClust124 |  HAH $J234232.8-541329.7$ |  |  SPT-CL $J2342-5411$ |  |  |  |  |  |
Rediscovery group |  |  |  |  |  |  |  |  |
RClust125 |  HAH $J001426.3-302255.3$ |  |  |  | $3673800147$ | $109$ |  |  |
RClust126 |  HAH $J015242.4-135618.2$ |  |  |  | $3035600098$ | $64$ |  |  |
RClust127 |  HAH $J032940.8-021318.5$ |  |  |  | $2550900117$ | $118$ |  |  |
RClust128 |  HAH $J033304.4-065144.3$ |  |  |  | $2730200015$ | $38$ |  |  |
RClust129 |  HAH $J041604.1-240522.2$ |  |  |  | $3473300094$ | $120$ |  |  |
RClust130 |  HAH $J045400.6-030833.8$ |  |  |  | $2578000063$ | $118$ |  |  |
RClust131 |  HAH $J045413.1+025733.8$ |  |  Abell $520$ P1 |  |  |  |  |  |
RClust132 |  HAH $J074450.9+392736.0$ |  |  |  | $891500113$ | $54$ |  |  |
RClust133 |  HAH $J091617.5-002405.9$ |  |  MACS $J0916.1-0023$ |  | $2480300042$ | $110$ |  |  RM $J091617.6-002405.7$ | $0$
RClust134 |  HAH $J100012.6+022015.8$ |  |  |  | $2353000151$ | $104$ |  |  |
RClust135 |  HAH $J100018.5+023845.6$ |  |  |  | $2353000132$ | $98$ |  |  |
RClust136 |  HAH $J100133.7+022135.3$ |  |  |  | $2353000126$ | $140$ |  |  |
RClust137 |  HAH $J133241.0+503346.3$ |  |  |  | $563100075$ | $87$ |  |  RM $J133238.4+503336.0$ | $26$
RClust138 |  HAH $J135409.1+771557.2$ |  |  MACS $J1354.6+7715$ |  |  |  |  |  |
RClust139 |  HAH $J135409.2+771549.9$ |  |  MACS $J1354.6+7715$ |  | $58300091$ | $50$ |  |  |
RClust140 |  HAH $J145250.0+580135.3$ |  |  MACS $J1452.9+5802$ |  | $371800109$ | $112$ |  |  |
RClust141 |  HAH $J152745.2+065220.8$ |  |  |  | $2179700063$ | $16$ |  |  RM $J152745.8+065233.6$ | $16$
RClust142 |  HAH $J213512.7-010143.9$ |  |  |  | $2519000027$ | $169$ |  |  RM $J213512.2-010255.8$ | $72$
RClust143 |  HAH $J221142.0-035052.4$ |  |  |  | $2622000023$ | $115$ |  |  RM $J221145.9-034944.5$ | $90$
RClust144 |  HAH $J224851.7-443105.1$ |  |  |  | $4206000045$ | $58$ |  |  |
RClust145 |  HAH $J001423.0-302109.7$ |  |  |  | $3673800147$ | $109$ |  |  |
RClust146 |  HAH $J095939.1+023044.1$ |  |  |  | $2353000051$ | $48$ |  |  |
RClust147 |  HAH $J100013.9+022249.8$ |  |  |  | $2353000156$ | $124$ |  |  |
RClust148 |  HAH $J100047.7+015023.3$ |  |  |  | $2378700136$ | $94$ |  |  |
RClust149 |  HAH $J100055.7+013821.1$ |  |  |  | $2378700129$ | $169$ |  |  |
RClust150 |  HAH $J130042.7+280523.6$ |  |  |  | $1306700012$ | $111$ |  |  |
RClust151 |  HAH $J230824.7-021213.3$ |  |  |  | $2571800113$ | $28$ |  |  RM $J230822.2-021131.8$ | $56$
RClust152 |  HAH $J013152.3-133658.3$ |  |  |  | $3009600047$ | $58$ |  |  |
RClust153 |  HAH $J071815.0+374200.3$ |  |  |  | $942200005$ | $24$ |  |  |
RClust154 |  HAH $J114934.3+222440.5$ |  |  |  | $1510200105$ | $63$ |  |  RM $J114935.7+222354.6$ | $50$
RClust155 |  HAH $J173217.5+193250.3$ |  |  |  | $1644300126$ | $114$ |  |  |
RClust156 |  HAH $J203146.3-403705.4$ |  |  |  | $4079500042$ | $96$ |  |  |

Table 4: continued.

Notes. Candidate clusters from Tables LABEL:tab:unpublished and
LABEL:tab:rediscoveries. As the presence of nearby clusters could provoke
excess lensing substructures, we report the confirmed and targeted clusters
from the HST observations, as well as candidate clusters identified by cross-
matching within a 3′radius with DESI (Zou et al. 2021) and redMaPPer on SDSS
(Rykoff et al. 2014, 2016) catalogues.

##  Appendix B GALFIT modelling of light profiles of lenses

Figure 11: Postage stamps showing the lens galaxy fitting with GALFIT for the
newly-discovered HAH grade A candidates. We present three lens candidates per
line, where each HAH lens is indicated by the sequence part of the name. Each
postage stamp is composed by (1) the original image used for the fit, using
the HST instruments and filters indicated in Tables LABEL:tab:unpublished and
LABEL:tab:rediscoveries, (2) the fitted model using chi-square minimisation in
GALFIT, (3) the residuals obtained by subtracting the fitted model from the
original image. The arcs and background galaxies were masked using SExtractor
during the fitting process, such that only the light of the lens was fitted.
The postage stamps show the default orientation of the HST images, which can
be different from the one shown in Figure 2. Figure 12: continued. Figure 13:
Left: Boxplots representing the distributions of the magnitudes measured with
Galfit and the Auto and ISO magnitudes measured with SExtractor. For each
boxplot, the middle line in the box represent the median of the distribution.
The box itself extends from the lower quartile to the upper quartile, covering
the interquartile range. The points which fall outside the whiskers situated
on each side of the box are considered to be extreme values. Right: Comparison
between the magnitudes measured with Galfit (abscissa) against the ’ISO’ and
’Auto’ magnitudes (ordinates) from SExtractor. The grey dotted line is a 45°
guide line. These two plots do not show systematic differences in the
photometry of the foreground lens galaxies between the different measurements.

##  Appendix C Additional lens candidates

After the end of the Hubble Asteroid Hunter citizen science project, we found
twelve serendipitous non-targeted lens candidates from recent imaging
observations released in the HST archives after June 2020 (Table 5 and Fig.
14). These candidates were identified by citizen scientist Claude Cornen, by
inspecting the ’Daily Data Reports’999https://archive.stsci.edu/hst/daily/,
while discarding calibrations as well as observations of asteroids, comets,
stars or clusters.

Figure 14: Serendipitous, non-targeted lens candidates identified after the
end of the Hubble Asteroid Hunter citizen science project, not included in the
main analysis of the paper. The HAH lenses from the mosaics are indicated
using only the sequence part of their name. Table 5: New strong lens
candidates identified after the end of the Hubble Asteroid Hunter citizen
science project.

Candidate (IAU name) | Obs. id | Obs. date | Instrument | Apertures | Filters | Proposal id | Grade
---|---|---|---|---|---|---|---
HAH J005556.9-270453.7 | ie6jy6010 | 2020-06-01 | WFC3 | IR | F140W | 15347 | B
HAH J022433.88-032332.24 | jeco01010 | 2021-09-15 | ACS | WFC | F475W | 16300 | C
HAH J024528.7-530146.0 | iepl29020 | 2022-02-04 | WFC3 | UVIS | F606W | 16729 | C
HAH J024533.7-530203.5 | iepl29020 | 2022-02-04 | WFC3 | UVIS | F606W | 16729 | A
HAH J075532.64+235351.49 | jece46020 | 2021-03-12 | ACS | WFC | F814W | 16257 | B
HAH J085709.37-005916.69 | jea302010 | 2021-04-07 | ACS | WFC | F814W | 16186 | A
HAH J115805.07-104747.39 | jeh903010 | 2021-04-08 | ACS | WFC | F814W | 16429 | A
HAH J120540.24+310338.7 | jdrz1h010 | 2021-05-26 | ACS | WFC | F606W | 15446 | A
HAH J121647.87-120907.76 | jc8h07020 | 2014-06-05 | ACS | WFC | F814W | 13393 | C
HAH J124253.68+021447.94 | jece02010 | 2021-04-12 | ACS | WFC | F606W | 16257 | B
HAH J125708.26+715432.28 | ieer07010 | 2021-01-02 | WFC3 | IR | F110W | 16243 | B
HAH J141114.51-051221.3 | jece78020 | 2021-04-18 | ACS | WFC | F814W | 16257 | C

Notes. IAU names, observing programs, HST instruments and filters
corresponding to new strong lens candidates identified after the end of the
Hubble Asteroid Hunter citizen science project, from data released in the HST
archives after June 2020.