# Synchronisation of running sums of automatic sequences

Rob Burns

###### Abstract

We investigate the running sums of some well-known automatic sequences to
determine whether they are synchronised.

##  1 Introduction

Synchronised sequences were introduced by Carpi and Maggi [4] in 2001.These
sequences, or functions over $\mathbb{N}$, lie between automatic and regular
sequences. Roughly speaking, a function $f$ is called synchronised if there is
an automaton which takes as input a pair of integers $(n,s)$, written in some
number system(s), and accepts the pair if and only if $f(n)=s$. If both $n$
and $s$ are written in base $k$, then the function is called $k$-synchronised.
If $n$ is written in base $k$ and $s$ is written in base-$l$, then the
function is called $(k,l)$-synchronised. If $n$ and $s$ are written in
Fibonacci representation, then the function is called Fibonacci-synchronised.

The running sum of a sequence of positive integers $a=(a_{i})_{i=0}^{\infty}$
is defined to be

$f_{a}(n):=\sum_{i=0}^{n}a_{i}.$

Unless the sequence $a$ is trivial, $f_{a}$ is unbounded and therefore not
automatic. On the other hand, if $a$ is automatic, then $f_{a}$ is regular.

This paper examines some standard automatic sequences to determine whether
their running sums are synchronised. In his book The Logical Approach to
Automatic Sequences[8], Jeffrey Shallit provides a Fibonacci-synchronising
automaton for the running sum of the Fibonacci word (section 10.11) and a
$2$-synchronising automaton for the running sum of the ternary Thue-Morse
sequence (section 10.15).

##  2 Preliminaries

The Fibonacci numbers $0,1,1,2,3,5,8,\dots$ are defined by the recursive
relations

$F_{0}=0,\,\,\,F_{1}=1\,\,\,\text{ and }\,\,\,F_{n}=F_{n-1}+F_{n-2}\text{ for
}\,\,\,n\geq 2.$

The golden ratio is defined by $\phi:=(1+\sqrt{5})/2$. The conjugate of $\phi$
is defined by $\psi:=(1-\sqrt{5})/2=-1/\phi$. $\phi$ and $\psi$ are roots of
the polynomial $x^{2}-x-1$. The Fibonacci numbers satisfy Binet’s formula:

$F_{n}=(\phi^{n}-\psi^{n})/\sqrt{5}.$ (1)

We will sometimes use regular expressions to represent integers. The regular
expression for an integer depends on the base in which it is being
represented. For example, in base $2$, non-zero even numbers are represented
by the regular expression

$0^{*}1(1|0)^{*}0.$

Note that the regular expression above has been padded with $0$’s at the most
significant digit end of its representation. This will generally be the case.
We will use exponentiation when the regular expression contains a repeated
word. For example, in base $3$, the base $10$ integer $30$ is represented by
the expression $(10)^{2}=1010$. Sequences defined by regular expressions can
also be defined by an automaton and vice versa.

There is a connection between an extension of Presburger arithmetic and
automatic sequences as described in theorem 6.6.1 of [8]. As a result, two or
more automatic sequences (or synchronised sequences) can be combined using
operations from first-order logic to create new automata (or synchronised
sequences). If $f$ is a synchronised function and $s$ is an automatic
sequence, then we can create another synchronised function $f^{\prime}$ by

$f^{\prime}(n)=\begin{cases}f(n),&\text{if }\,\,n\in s\\\ 0,&\text{if
}\,\,n\not\in s.\end{cases}$

We will use this fact in section 5.

The automata in this paper will read integers starting with the most
significant digit (msd).

We have used Shallit’s book [8] as the source for information about automatic
sequences and the software package Walnut. We used Walnut to handle automata.
Hamoon Mousavi, who wrote the program, has provided an introductory article
[6]. Further resources and a list of papers that have used Walnut can be found
at Jeffrey Shallit’s page.

The free open-source mathematics software system SageMath [9] was used to
perform the matrix algebra and polynomial factorisation.

We will need the following theorem from [7], which establishes some closure
properties of synchronised sequences. Here, $\lfloor.\rfloor$ is the floor
function.

######  Theorem 2.1.

Suppose $(a(n))_{n\geq 0}$ and $(b(n))_{n\geq 0}$ are $(k,l)$-synchronised
sequences. Then so are the sequences

  1. (a)

$(a(n)+b(n))_{n\geq 0}$;

  2. (b)

$(a(n)\dotdiv b(n))_{n\geq 0}$,  where  $x\dotdiv y$ is the "monus" function,
defined by $\max(x-y,0)$;

  3. (c)

$(\lfloor a(n)-b(n)\rfloor)_{n\geq 0}$;

  4. (d)

$(\lfloor\alpha a(n)\rfloor)_{n\geq 0}$,  where  $\alpha$ is a non-negative
rational number.

We will also need the following growth bounds on synchronised sequences. See
[8], theorem 10.6.1.

######  Theorem 2.2.

Let $k,l\geq 2$ be integers. Let $(f(n))_{n\geq 0}$ be a $(k,l)$-synchronised
sequence, and define $\beta=(\log l)/(\log k)$. Then

  1. (a)

$f(n)=\mathcal{O}(n^{\beta})$;

  2. (b)

if
$f(n)=\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{{$\scriptscriptstyle\mathcal{O}$}}(n^{\beta})$,
then $f(n)=\mathcal{O}(1)$.

######  Remark.

The bounds of theorem 2.2 also hold for Fibonacci-synchronised sequences (with
$\beta=1$) (See the comment on p. 284 of [8]).

######  Remark.

An example of how theorem 2.2 can be used to show a sequence is not
synchronised is provided by the characteristic sequence of the powers of $2$.
The running sum of this sequence is unbounded but has growth rate
$\mathcal{O}(\log(n))=\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{{$\scriptscriptstyle\mathcal{O}$}}(n)$
and so cannot be $2$-synchronised.

##  3 The running sum and the index function

Let $s$ be an automatic binary sequence. Define $\bm{\mathrm{sum_{s}}}$ to be
the running sum of $s$. Define $\bm{\mathrm{ind_{s}}}$ to be the sequence of
indices at which the binary digit $1$ appears in $s$. For example, for the
Thue-Morse sequence $\bm{\mbox{T}}=(0,1,1,0,1,0,0,1,1,0,0,1,0.\dots)$, we have

$\bm{\mathrm{sum_{T}}}=(0,1,2,2,3,3,3,4,5,5,\dots)\,\,\,\text{ and
}\,\,\,\bm{\mathrm{ind_{T}}}=(1,2,4,7,8,11,13,14,16,\dots).$

######  Theorem 3.1.

If $s$ is an automatic binary sequence, then the sequence
$\bm{\mathrm{sum_{s}}}$ is synchronised if and only if the sequence
$\bm{\mathrm{ind_{s}}}$ is synchronised.

###### Proof.

If $B$ is a synchronising automaton for $\bm{\mathrm{sum_{s}}}$, then $B$
accepts the pair $(k,n)$ if and only if $\bm{\mathrm{sum_{s}}}$$(k)=n$. Define
the automaton $A$ by the logical formula

$A(n,k):=B(k,n)\land s(k)=1$

Then, $A$ is a synchronising automaton for $\bm{\mathrm{ind_{s}}}$.
Conversely, suppose $A$ is a synchronising automaton for
$\bm{\mathrm{ind_{s}}}$. So, $A$ accepts the pair $(n,k)$ if and only if the
$n$’th $1$ in $s$ appears at index $k$, i.e. $\bm{\mathrm{ind_{s}}}$$(n)=k$.
Define the automaton $B$ by the first order logical expression

$B(k,n):=\exists r(r\leq k):A(n,r)\land(\forall i:r+1\leq i\leq
k\,\,\,s(i)=0).$

Then, $B$ is a synchronising automaton for $\bm{\mathrm{sum_{s}}}$. ∎

##  4 Synchronised sequences

We will now examine some automatic sequences for which the running sums are
synchronised. Our method is to first guess the synchronising automaton using
the Myhill-Nerode theorem and then verify the guess with Walnut.

The running sum of the Thue-Morse sequence is known to be $2$-synchronised.
The automaton representing the running sum, which we call tmsum, is given at
figure 1. The proof that this is the correct automaton uses an inductive
argument. Firstly, the automaton gives the correct answer for $n=0,1$. Next,
for each $n$, we can show that there is a unique $s$ such that the automaton
accepts the pair $(n,s)$. Finally, we can show that if the automaton accepts
the pair $(n,s)$, then it also accepts the pair $(n+1,s+\bm{\mbox{T}}(n+1))$
where T is the Thue-Morse sequence. These claims are established by the
following Walnut commands.

Figure 1: Automaton tmsum for the running sum of the Thue-Morse sequence.

    eval testtmsum "?msd_2 An,s,t $tmsum(n,s) & $tmsum(n,t) => s=t":
    eval testtmsum "?msd_2 An Es $tmsum(n,s)":
    eval testtmsum "?msd_2 An,s,u ($tmsum(n,s) & T[n+1]=u)
            => $tmsum(n+1, s+u)":

Walnut returns the value TRUE for each of the four statements. The first and
second commands show that for each $n$, there is a unique $s$ such that tmsum
accepts the pair $(n,s)$. The third command shows that tmsum does the right
thing as $n$ increases.

Next is the Cantor sequence, which is the characteristic sequence of the
Cantor integers. An integer is a Canton integer if its base $3$ representation
only contains the integers $0$ and $2$. The running sum of the Cantor sequence
is $(3,2)$-synchronised and a synchronising automaton, called cansum, is given
at figure 2. The correctness of the automaton can again be established using
Walnut. The commands are given below. CA is Walnut’s name for the Cantor
sequence.

Figure 2: Automaton cansum for the running sum of the Cantor sequence.

    eval testcs1 "An Es $cansum(?msd_3 n,s)":
    eval testcs2 "An,s,t $cansum(?msd_3 n,s) & $cansum(?msd_3 n,t) => s=t":
    eval testcs3 "?msd_2 An,s,u ($cansum(?msd_3 n,s) & CA[?msd_3 n+1]=u)
            => $cansum(?msd_3 n+1, s+u)":

The second-bit sequence sb is defined by:

$\bm{\mbox{sb}}(n)=a_{2}\text{ where }n=a_{1}a_{2}\dots\text{ is the base 2
representation of n in msd form.}$

The running sum of the second-bit sequence is $2$-synchronised and the
synchronising automaton, called sbsum, appears at figure 3. The correctness of
the automaton can be established using Walnut in the same way as for the
earlier sequences.

Figure 3: Automaton sbsum for the running sum of the second-bit sequence.

The next sequence in this section is the twisted Thue-Morse sequence, ttm. For
an integer $n\geq 0$, $\bm{\mbox{ttm}}(n)$ is the number of $0$’s, modulo $2$,
in the base $2$ representation of $n$, with $\bm{\mbox{ttm}}(0)$ defined to be
$0$. The running sum of the twisted Thue-Morse sequence is $2$-synchronised
and the synchronising automaton, called ttmsum, appears at figure 4. Again,
Walnut will verify the correctness of the automaton.

Figure 4: Automaton ttmsum for the running sum of the twisted Thue-Morse
sequence.

Finally, we examine the sequence $\gamma$, the $n$’th value of which is the
highest power of $2$ dividing $n!$. The sequence is of interest when
considering the values of $n$ for which $n!$ can be written as a sum of three
squares.[2][3] The sequence itself is not synchronised because, according to
Legendre’s formula, $\gamma_{n}=n-\sum_{k\geq 0}a_{k}$ when $n$ has binary
representation $\sum_{k\geq 0}a_{k}2^{k}$. Hence, if $\gamma$ were
synchronised, the sequence which maps $n$ to the sum of its binary digits
would also be synchronised by theorem 2.1. However, that sequence is bounded
by $\mathcal{O}(\log
n)=\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{{$\scriptscriptstyle\mathcal{O}$}}(n)$,
contradicting theorem 2.2. Instead, we consider the sequence
$\bar{\gamma}=\gamma\pmod{2}$, which is a $2$-automatic sequence. The running
sum of $\bar{\gamma}$ is $2$-synchronised. An automaton for $\bar{\gamma}$ is
shown in figure 5 and a synchronising automaton for
$\mathbf{sum_{\bar{\gamma}}}$ is shown in figure 6. Both automata take
integers in least significant digit first order.

Figure 5: Automaton for the sequence $\bar{\gamma}$.

Figure 6: Synchronising automaton for the running sum of the sequence
$\bar{\gamma}$.

##  5 Unsynchronised sequences

This section examines automatic sequences for which the running sum is not
synchronised. We rely heavily on linear representations for the running sums.
A linear representation of a function $f$ defined over an alphabet
$\\{0,1,\dots,b-1\\}$ consists of vectors $v$ and $w$ and matrices
$M_{0},M_{1},\dots,M_{b-1}$ such that, if $n_{k}n_{k-1}\dots n_{0}$ is the
base $b$ representation of n in msd form, then
$f(n)=v*M_{n_{k}}*M_{n_{k-1}}*\dots*M_{n_{0}}*w$. Given an automatic sequence,
Walnut will provide the linear representation for the running sum of the
sequence. For example, the Walnut command

    eval tmsumrep n "?msd_2 (j>=0) & (j<=n) & T[j]=@1":

produces a linear representation for the running sum of the Thue-Morse
sequence. In this case $v$, $w$, $M_{0}$ and $M_{1}$ are given by:

$\displaystyle v=\begin{pmatrix}1,0,0,0\end{pmatrix}\,\,\text{ and
}\,\,w=\begin{pmatrix}0,0,1,1\end{pmatrix}$ (2) $\displaystyle
M_{0}=\begin{pmatrix}1,0,0,0\\\ 0,1,0,1\\\ 0,0,1,0\\\
0,1,0,1\end{pmatrix}\,\,\text{ and }\,\,M_{1}=\begin{pmatrix}0,1,1,0\\\
0,1,0,1\\\ 1,0,0,1\\\ 0,1,0,1\end{pmatrix}.$ (3)

For most sequences in this section, the linear representation of the running
sum will be used to calculate the growth rate of a sub-sequence determined by
a regular expression. We will then use theorem 2.1 to construct a new sequence
with growth rate that conflicts with theorem 2.2. As a result, we deduce that
the original sequence cannot have been synchronised. A suitable subsequence
can be found by looking for a product of the matrices
$\\{M_{0},\dots,M_{b-1}\\}$ for which the minimal polynomial has a repeated
non-zero root.

###  5.1 Period-doubling sequence

The period-doubling sequence $\bm{\mbox{pd }}=d_{0}d_{1}d_{2}\dots$ satisfies
the relations

$d_{2n}=1,\,\,\,d_{4n+1}=0,\,\,\,d_{4n+3}=d_{n}.$

In order to show that $\bf sum_{pd}$, the running sum of the period-doubling
sequence, is not 2-synchronised, we will first calculate the value of
$\mathbf{sum_{pd}}$$(n)$ when $n=(4^{r+1}-1)/3$ for $r\in\mathbb{N}$. The base
2 representation of $(4^{r+1}-1)/3$ is $0*(10)^{r}1$.

######  Lemma 5.1.

$\mathbf{sum_{pd}}$$((4^{r+1}-1)/3)=(2*4^{r+1}+3r+1)/9$.

###### Proof.

We can use the linear representation of $\mathbf{sum_{pd}}$ provided by
Walnut, and the base 2 representation of $(4^{r+1}-1)/3$, to calculate
$\mathbf{sum_{pd}}$$(4^{r+1}-1)/3)$. The linear representation is determined
by the vectors $v$ and $w$ and matrices $M_{0}$ and $M_{1}$ below:

$\displaystyle v=\begin{pmatrix}1,0,0,0\end{pmatrix}\,\,\text{ and
}\,\,w=\begin{pmatrix}1,1,0,0\end{pmatrix}$ (4) $\displaystyle
M_{0}=\begin{pmatrix}1,0,0,0\\\ 0,1,0,1\\\ 1,0,0,0\\\
0,2,0,0\end{pmatrix}\,\,\text{ and }\,\,M_{1}=\begin{pmatrix}0,1,1,0\\\
0,1,0,1\\\ 1,1,0,0\\\ 0,2,0,0\end{pmatrix}.$ (5)

The matrix $M_{1}*M_{0}$ has minimal polynomial

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

The theory of linear recurrences says there are constants $a$, $b$ and $c$
such that

$\mathbf{sum_{pd}}((4^{r+1}-1)/3)=v*(M_{1}*M_{0})^{r}*M1*w=a+br+c4^{r}.$

We then use specific values of $\bf sum_{pd}$ $(n)$ to deduce that $a=1/9$,
$b=3/9$ and $c=8/9$ as required. ∎

######  Corollary 5.2.

The running sum of the period-doubling sequence is not 2-synchronised.

###### Proof.

The function $\lfloor 2n/3\rfloor$ is synchronised by theorem 2.1 We define
the function $g$ by

$g(n)=\begin{cases}\mathbf{sum_{pd}}(n)\dotdiv\lfloor 2n/3\rfloor,&\text{if
}\,\,n=(4^{r+1}-1)/3\\\ 0&\text{otherwise}\end{cases}$

If $\mathbf{sum_{pd}}$ $(n)$ is synchronised, then so is $\bf sum_{pd}$
$(n)\dotdiv\lfloor(2n+1)/3\rfloor$ by theorem 2.1. Hence, $g$ is also
synchronised since the set $\\{(4^{r+1}-1)/3:r\in\mathbb{N}\\}$ comes from a
regular expression. When $n=(4^{r+1}-1)/3$,

$\displaystyle g(n)$
$\displaystyle=(2*4^{r+1}+3r+1)/9\dotdiv\lfloor(2*4^{r+1}-2)/9\rfloor$
$\displaystyle=\lfloor(r+1)/3\rfloor.$

Since $g(n)=\mathcal{O}(\log
n)=\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{{$\scriptscriptstyle\mathcal{O}$}}(n)$
and is unbounded, it cannot be a synchronised function by theorem 2.2. Hence,
$\bf sum_{pd}$ is not $2$-synchronised. ∎

###  5.2 Mephisto Waltz sequence

The Mephisto Waltz sequence $\bm{\mbox{mw }}=m_{0},m_{1},\dots$ is a
$3$-automatic sequence in which the value of $m_{n}$ is given by the number of
$2$’s modulo $2$ in the base $3$ representation of $n$. The running sum of mw,
$\mathbf{sum_{mw}}$ , has a linear representation given by the vectors $v$ and
$w$ and matrices $M_{0},M_{1}$ and $M_{2}$ below:

$\displaystyle v=\begin{pmatrix}1,0,0,0\end{pmatrix}\,\,\text{ and
}\,\,w=\begin{pmatrix}0,0,1,1\end{pmatrix}$ (6) $\displaystyle
M_{0}=\begin{pmatrix}1,0,0,0\\\ 0,2,0,1\\\ 0,0,1,0\\\
0,1,0,2\end{pmatrix}\,\,\,\,M_{1}=\begin{pmatrix}1,1,0,0\\\ 0,2,0,1\\\
0,0,1,1\\\ 0,1,0,2\end{pmatrix}\,\,\text{ and
}\,\,M_{2}=\begin{pmatrix}0,2,1,0\\\ 0,2,0,1\\\ 1,0,0,2\\\
0,1,0,2\end{pmatrix}$ (7)

######  Lemma 5.3.

When $n=(3^{2r}-1)/2$, $\mathbf{sum_{mw}}$$(n)=n/2-r$.

###### Proof.

The matrix $M_{1}^{2}$ has minimal polynomial

$x^{3}-11x^{2}+19x-9=(x-9)(x-1)^{2}$

Hence, there are constants $a$, $b$ and $c$ such that

$\mathbf{sum_{mw}}((3^{2r}-1)/2)=v*(M_{1})^{2r}*w=a+br+c3^{2r}.$

We then use specific values of $\mathbf{sum_{mw}}$$(n)$ to deduce that
$a=-1/4$, $b=-1$ and $c=1/4$. Therefore, when $n=(3^{2r}-1)/2$,

$\displaystyle\mathbf{sum_{mw}}(n)$
$\displaystyle=-1/4-r+3^{2r}/4=(3^{2r}-1)/4-r$ $\displaystyle=n/2-r$

∎

######  Corollary 5.4.

The running sum of the Mephisto Waltz sequence is not $3$-synchronised.

###### Proof.

We consider the function

$g(n)=\begin{cases}n/2\dotdiv\mathbf{sum_{mw}}(n),&\text{if
}\,\,n=(3^{2r}-1)/2\\\ 0&\text{otherwise.}\end{cases}$

Then $g(n)=\mathcal{O}(\log
n)=\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{{$\scriptscriptstyle\mathcal{O}$}}(n)$
and is unbounded, and so cannot be a synchronised function by theorem 2.2.
Hence, $\mathbf{sum_{mw}}$ is not $3$-synchronised. ∎

###  5.3 Paper-folding sequence

The regular paper-folding sequence $\bm{\mbox{pf }}=f_{0}f_{1}f_{2}\dots$
satisfies the relations

$f_{2n+1}=f_{n},\,\,\,f_{4n}=0,\,\,\,f_{4n+2}=1.$

The argument to show that $\mathbf{sum_{pf}}$, the running sum of the paper-
folding sequence, is not $2$-synchronised, is similar to that used for the
period-doubling sequence. We examine $\mathbf{sum_{pf}}$ when $n$ has the
binary representation given by the regular expression $(10)^{r}1$. Such an
$n=(4^{r+1}-1)/3$. A linear representation for $\mathbf{sum_{pf}}$ is given by
the vectors $v$ and $w$ and matrices $M_{0}$ and $M_{1}$ below:

$\displaystyle v=\begin{pmatrix}1,0,0,0,0,0,0,0\end{pmatrix}\,\,\text{ and
}\,\,w=\begin{pmatrix}0,0,0,0,1,1,1,1\end{pmatrix}$ (8) $\displaystyle
M_{0}=\begin{pmatrix}1,0,0,0,0,0,0,0\\\ 0,1,0,1,0,0,0,0\\\ 0,0,0,0,1,0,0,0\\\
0,0,0,1,0,1,0,0\\\ 1,0,0,0,0,0,0,0\\\ 0,1,0,0,0,0,0,1\\\ 0,0,0,0,1,0,0,0\\\
0,0,0,0,0,1,0,1\end{pmatrix}\,\,\text{ and
}\,\,M_{1}=\begin{pmatrix}0,1,1,0,0,0,0,0\\\ 0,1,0,1,0,0,0,0\\\
0,0,1,0,0,1,0,0\\\ 0,0,0,1,0,1,0,0\\\ 0,1,0,0,0,0,1,0\\\ 0,1,0,0,0,0,0,1\\\
0,0,0,0,0,1,1,0\\\ 0,0,0,0,0,1,0,1\end{pmatrix}$ (9)

######  Lemma 5.5.

When $n=(4^{r+1}-1)/3$, $\mathbf{sum_{pf}}$$(n)=(n+1)/2-r$.

###### Proof.

The matrix $M_{1}*M_{0}$ has minimal polynomial

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

There are constants $a$, $b$ and $c$ such that

$\mathbf{sum_{pf}}((4^{r+1}-1)/3)=v*(M_{1}*M_{0})^{r}*M1*w=a+br+c4^{r}.$

We then use specific values of $\mathbf{sum_{pf}}$$(n)$ to deduce that
$a=1/3$, $b=-1$ and $c=2/3$. Therefore, when $n=(4^{r+1}-1)/3$,

$\displaystyle\mathbf{sum_{pf}}(n)$
$\displaystyle=1/3-r+2*4^{r}/3=(2*4^{r}+1)/3-r$ $\displaystyle=(n+1)/2-r$

∎

######  Corollary 5.6.

The running sum of the paper-folding sequence is not 2-synchronised.

###### Proof.

We use the same argument as corollary 5.2. This time we consider the function

$g(n)=\begin{cases}(n+1)/2\dotdiv\mathbf{sum_{pf}}(n),&\text{if
}\,\,n=(4^{r+1}-1)/3\\\ 0&\text{otherwise.}\end{cases}$

Again, $g(n)=\mathcal{O}(\log
n)=\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{{$\scriptscriptstyle\mathcal{O}$}}(n)$
and is unbounded, and so cannot be a synchronised function by theorem 2.2.
Hence, $\mathbf{sum_{pf}}$ is not $2$-synchronised. ∎

###  5.4 Leech’s word

Leech’s word le is a 13-automatic sequence defined over the alphabet
$\\{0,1,2\\}$. It is the fixed point of the 13-uniform morphism, starting from
$0$:

$\displaystyle 0\rightarrow\,\,$ $\displaystyle 0,1,2,1,0,2,1,2,0,1,2,1,0$
$\displaystyle 1\rightarrow\,\,$ $\displaystyle 1,2,0,2,1,0,2,0,1,2,0,2,1$
$\displaystyle 2\rightarrow\,\,$ $\displaystyle 2,0,1,0,2,1,0,1,2,0,1,0,2$

and appears as sequence A337005 in the OEIS.[1] The running sum of le,
$\mathbf{sum_{le}}$, is given by

$\mathbf{sum_{le}}=\mathbf{sum_{le1}}+2*\mathbf{sum_{le2}}$

where $\mathbf{sum_{le1}}$ is the running sum of the number of $1$’s appearing
in $\mathbf{le}$ and $\mathbf{sum_{le2}}$ is the running sum of the number of
$2$’s appearing in $\mathbf{le}$. We can obtain linear representations for
$\mathbf{sum_{le1}}$ and $\mathbf{sum_{le2}}$ with the Walnut commands

    eval lesum1 n "?msd_13  (j>=0) & (j<=n) & LE[j]=@1":
    eval lesum2 n "?msd_13  (j>=0) & (j<=n) & LE[j]=@2":

LE is Walnut’s name for Leech’s word. Each of these commands produces vectors
$v$ and $w$ and matrices $M_{0},M_{1},\dots,M_{12}$. In each case the vectors
$v$ and the matrices are identical. The vectors $w$ differ and will be denoted
by $w_{1}$ and $w_{2}$. We will calculate $\mathbf{sum_{le}}$$(n)$ when $n$
has the base 13 representation $(111)^{r}$, and so we will only need the
matrix $M_{1}$. $v$, $w_{1}$, $w_{2}$ and $M_{1}$ are given below:

$\displaystyle v=\begin{pmatrix}1,0,0,0,0,0\end{pmatrix}\,\,\text{,
}\,\,w_{1}=\begin{pmatrix}0,0,1,1,0,0\end{pmatrix}\,\,\text{ and
}\,\,w_{2}=\begin{pmatrix}0,0,0,0,1,1\end{pmatrix}$ $\displaystyle
M_{1}=\begin{pmatrix}0,1,1,0,0,0\\\ 0,4,0,5,0,4\\\ 0,0,0,1,1,0\\\
0,4,0,4,0,5\\\ 1,0,0,0,0,1\\\ 0,5,0,4,0,4\end{pmatrix}$

A linear representation for $\mathbf{sum_{le}}$ is determined by the matrices
$M_{0},M_{1},\dots,M_{12}$ and the vectors $v$ and $w_{1}+2w_{2}$.

######  Lemma 5.7.

For $n=(13^{3r}-1)/12$, where $r\in\mathbb{N}$, $\mathbf{sum_{le}}$$(n)=n+3r$.

###### Proof.

The matrix $M_{1}$ has minimal polynomial

$x^{6}-12x^{5}-12x^{4}-14x^{3}+12x^{2}+12x+13=(x-13)(x-1)(x-\theta)^{2}(x+\theta+1)^{2}$

where $\theta=(-1+\sqrt{-3})/2$. There are constants $a$, $b$ and $c$, $d$,
$e$ and $f$ such that

$\mathbf{sum_{le}}((13^{r}-1)/12)=v*M_{1}^{r}*(w_{1}+2*w_{2})=a+b\,13^{r}+(c+dr)\theta^{r}+(e+fr)(-1-\theta)^{r}.$

We use the specific values

$\displaystyle\mathbf{sum_{le}}((13^{1}-1)/12)$
$\displaystyle=1,\,\,\,\mathbf{sum_{le}}((13^{2}-1)/12)=16$
$\displaystyle\mathbf{sum_{le}}((13^{3}-1)/12)$
$\displaystyle=186,\,\,\,\mathbf{sum_{le}}((13^{4}-1)/12)=2377$
$\displaystyle\mathbf{sum_{le}}((13^{5}-1)/12)$
$\displaystyle=30943,\,\,\,\mathbf{sum_{le}}((13^{6}-1)/12)=402240$

to deduce that

$a=11/12,b=1/12,c=(\theta-1)/3,d=(\theta+2)/3,e=(-\theta-2)/3,f=(-\theta+1)/3.$

Therefore, when $n=(13^{3r}-1)/12$,

$\displaystyle\mathbf{sum_{le}}(n)=$
$\displaystyle(13^{3r}+11)/12+(\theta-1+3r\theta+6r)\theta^{3r}/3+(-\theta-2-3r\theta+3r)(-1-\theta)^{3r}/3$
$\displaystyle=$
$\displaystyle(13^{3r}+11)/12+(\theta-1+3r\theta+6r-\theta-2-3r\theta+3r)/3$
$\displaystyle=$ $\displaystyle(13^{3r}-1)/12+3r$ $\displaystyle=$
$\displaystyle n+3r$

where we have used the fact that $\theta^{3}=(-1-\theta)^{3}=1$. ∎

######  Corollary 5.8.

The running sum of Leech’s word is not $13$-synchronised.

###### Proof.

We define the function $g$ by

$g(n)=\begin{cases}\mathbf{sum_{le}}(n)\dotdiv n,&\text{if }\,\,n\text{ has
base 13 representation }\,\,(111)^{*}\\\ 0,&\text{otherwise}\end{cases}$

If $\mathbf{sum_{le}}$ is synchronised, then so is $g$ by theorem 2.1. But
from lemma 5.7, $g=\mathcal{O}(\log
n)=\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{{$\scriptscriptstyle\mathcal{O}$}}(n)$
and is unbounded, and so it cannot be a synchronised function by theorem 2.2.
Hence, $\mathbf{sum_{le}}$ is not $13$-synchronised. ∎

###  5.5 Baum-Sweet sequence

The Baum-Sweet sequence, bs, satisfies

$\bm{\mbox{bs}}(n)=\begin{cases}0,&\text{if the base 2 representation of
}\,\,n\,\,\text{has a block of zeros of odd length}\\\ 1,&\text{otherwise
}\end{cases}$

The running sum of bs, $\mathbf{sum_{bs}}$ , has a linear representation given
by the vectors $v$ and $w$ and matrices $M_{0}$ and $M_{1}$ below:

$\displaystyle v=\begin{pmatrix}1,0,0,0,0,0\end{pmatrix}\,\,\text{ and
}\,\,w=\begin{pmatrix}1,1,1,1,0,0\end{pmatrix}$ (10) $\displaystyle
M_{0}=\begin{pmatrix}1,0,0,0,0,0\\\ 0,1,0,1,0,0\\\ 0,0,0,0,1,0\\\
0,0,0,1,0,1\\\ 0,0,1,0,0,0\\\ 0,0,0,1,0,0\end{pmatrix}\,\,\text{ and
}\,\,M_{1}=\begin{pmatrix}0,1,1,0,0,0\\\ 0,1,0,1,0,0\\\ 0,0,1,0,0,1\\\
0,0,0,1,0,1\\\ 0,0,0,1,0,0\\\ 0,0,0,1,0,0\end{pmatrix}$ (11)

$M_{0}$ has minimal polynomial
$x^{4}-x^{3}-2x^{2}+x+1=(x-\phi)(x-1)(x-\psi)(x+1)$ where $\phi$ is the golden
ration and $\psi$ is its conjugate.

######  Theorem 5.9.

The running sum of $\bf bs$ is not 2-synchronised.

###### Proof.

The linear representation above shows that, for $k\in\mathbb{N}$, there are
constants $a,b,c,d$ such that
$\mathbf{sum_{bs}}$$(2^{k})=a+b(-1)^{k}+c\phi^{k}+d\psi^{k}$. The values of
$(a,b,c,d)$ can be calculated, giving

$\mathbf{sum_{bs}}(2^{k})=1/2+(-1)^{k}/2+(3\sqrt{5}/10+1/2)\phi^{k}+(-3\sqrt{5}/10+1/2)\psi^{k}.$

Since $\mathbf{sum_{bs}}$ is unbounded and
$\mathbf{sum_{bs}}$$(2^{k})\sim\phi^{k}=\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{{$\scriptscriptstyle\mathcal{O}$}}(2^{k})$,
$\mathbf{sum_{bs}}$ cannot be a 2-synchronised function by theorem 2.2. ∎

###  5.6 Stewart’s choral sequence

Stewart choral sequence, $\bm{\mbox{sc}}=s_{0}s_{1}s_{2}\dots$, is a
$3$-automatic sequence satisfying the recurrence relation

$s_{3n}=0,\,\,\,s_{3n-1}=1,\,\,\,s_{3n+1}=s_{n}.$

The running sum of sc, $\mathbf{sum_{sc}}$, has a linear representation
determined by vectors $v$ and $w$ and matrices $M_{0}$, $M_{1}$ and $M_{2}$.
$v$, $w$ and $M_{1}$ are given below:

$\displaystyle v=\begin{pmatrix}1,0,0,0\end{pmatrix}\,\,\text{ and
}\,\,w=\begin{pmatrix}0,0,1,1\end{pmatrix}$ (12) $\displaystyle
M_{1}=\begin{pmatrix}1,1,0,0\\\ 0,2,0,1\\\ 0,1,1,0\\\ 0,1,0,2\end{pmatrix}.$
(13)

######  Lemma 5.10.

Let $r\in\mathbb{N}$. When $n=(3^{r}-1)/2$,
$\mathbf{sum_{sc}}$$(n)=(3^{r}-2r-1)/4$.

###### Proof.

The matrix $M_{1}$ has minimal polynomial

$x^{3}-5x^{2}+7x-3=(x-3)(x-1)^{2}.$

There are constants $a$, $b$ and $c$ such that

$\mathbf{sum_{sc}}((3^{r}-1)/2)=v*M_{1}^{r}*w=a+br+c3^{r}.$

We then use specific values of $\mathbf{sum_{sc}}$$(n)$ to deduce that
$a=-1/4$, $b=-1/2$ and $c=1/4$. Therefore,

$\mathbf{sum_{sc}}((3^{r}-1)/2)=-1/4-r/2+3^{r}/4=(3^{r}-2r-1)/4.$

∎

######  Corollary 5.11.

The running sum of Stewart’s choral sequence is not 3-synchronised.

###### Proof.

Use the same argument as for corollaries 5.6, 5.2 and theorem 5.9. ∎

###  5.7 Rudin-Shapiro sequence

The Rudin-Shapiro sequence, rs, is a $2$-automatic sequence satisfying

rs $\displaystyle(0)=\bm{\mbox{rs}}(1)=0$ rs
$\displaystyle(2n)=\bm{\mbox{rs}}(n)$ rs
$\displaystyle(4n+1)=\bm{\mbox{rs}}(n)$ rs
$\displaystyle(4n+3)=1-\bm{\mbox{rs}}(2n+1).$

######  Theorem 5.12.

The running sum of rs, $\mathbf{sum_{rs}}$, is not $2$-synchronised.

###### Proof.

Walnut provides the following linear representation for $\mathbf{sum_{rs}}$:

$\displaystyle v=\begin{pmatrix}1,0,0,0,0,0,0,0\end{pmatrix}\,\,\text{ and
}\,\,w=\begin{pmatrix}0,0,0,0,1,1,1,1\end{pmatrix}$ (14) $\displaystyle
M_{0}=\begin{pmatrix}1,0,0,0,0,0,0,0\\\ 0,1,0,1,0,0,0,0\\\ 1,0,0,0,0,0,0,0\\\
0,1,0,0,0,1,0,0\\\ 0,0,0,0,0,0,1,0\\\ 0,0,0,1,0,0,0,1\\\ 0,0,0,0,0,0,1,0\\\
0,0,0,0,0,1,0,1\end{pmatrix}\,\,\text{ and
}\,\,M_{1}=\begin{pmatrix}0,1,1,0,0,0,0,0\\\ 0,1,0,1,0,0,0,0\\\
0,1,0,0,1,0,0,0\\\ 0,1,0,0,0,1,0,0\\\ 0,0,1,0,0,0,0,1\\\ 0,0,0,1,0,0,0,1\\\
0,0,0,0,1,0,0,1\\\ 0,0,0,0,0,1,0,1\end{pmatrix}$ (15)

The minimal polynomial for $M_{1}$ is

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

Therefore, there are constants $a,b,c,d,e$ such that

$\mathbf{sum_{rs}}(2^{k}-1)=v*M_{1}^{k}*w=a+b(-1)^{k}+c2^{k}+d(\sqrt{2})^{k}+e(-\sqrt{2})^{k}.$

The constants $(a,b,c,d,e)=(0,0,1/2,-(\sqrt{2}+1)/4,(\sqrt{2}-1)/4)$, so

$\mathbf{sum_{rs}}(2^{k}-1)=\begin{cases}2^{k-1}-2^{k/2-1},&\text{if k is
even}\\\ 2^{k-1}-2^{(k-1)/2},&\text{if k is odd.}\end{cases}$ (16)

From equation (16), the base $2$ representation of
$\mathbf{sum_{rs}}$$(2^{k}-1)$ is given by $1^{k/2}0^{k/2-1}$ when $k$ is even
and by $1^{(k-1)/2}0^{(k-1)/2}$ when $k$ is odd. The pumping lemma then says
that an automaton which accepts pairs $(2^{k}-1,\mathbf{sum_{rs}}(2^{k}-1))$,
for $k$ large enough, must also accept base $2$ formatted pairs
$(1^{k+m},1^{m+k/2}0^{k/2-1})$ or $(1^{k+m},1^{m+(k-1)/2}0^{(k-1)/2})$ where m
is some non-zero integer. This contradicts the value of
$\mathbf{sum_{rs}}$$(2^{k+m}-1)$ given in equation (16) and so the running sum
of the Rudin-Shapiro sequence is not $2$-synchronised. ∎

###  5.8 Fibonacci-Thue-Morse sequence

The Fibonacci-Thue-Morse sequence, ftm, satisfies

$\bm{\mbox{ftm}}(n)=\begin{cases}0&\text{if the Fibonacci representation of
}\,\,n\,\,\text{has an even number of 1's}\\\ 1&\text{if the Fibonacci
representation of }\,\,n\,\,\text{has an odd number of 1's.}\end{cases}$

In order to show that the running sum of ftm, $\mathbf{sum_{ftm}}$, is not
Fibonacci-synchronised, we look at the values of $\mathbf{sum_{ftm}}$$(n)$
when $n=n(r)$ has the Fibonacci representation $(100100)^{r}=(100)^{2r}$.
Walnut provides the following linear representation for $\mathbf{sum_{ftm}}$:

$\displaystyle v=\begin{pmatrix}1,0,0,0,0,0,0,0,0,0,0,0\end{pmatrix}\,\,\text{
and }\,\,w=\begin{pmatrix}0,0,1,0,1,1,1,1,1,0,0,0\end{pmatrix}$ (17)
$\displaystyle M_{0}=\begin{pmatrix}1,0,0,0,0,0,0,0,0,0,0,0\\\
0,0,0,1,1,0,0,0,0,0,0,0\\\ 0,0,0,0,0,1,0,0,0,0,0,0\\\
0,0,0,1,1,0,0,0,0,0,0,0\\\ 0,0,0,0,0,0,0,1,0,0,0,0\\\
0,0,0,0,0,1,0,0,0,0,0,0\\\ 0,0,0,0,0,0,0,1,0,0,0,0\\\
0,0,0,0,0,0,0,1,0,0,1,0\\\ 0,0,0,0,0,0,0,1,0,0,1,0\\\
1,0,0,0,0,0,0,0,0,0,0,0\\\ 0,0,0,1,0,0,0,0,0,0,0,0\\\
0,0,0,1,0,0,0,0,0,0,0,0\end{pmatrix}\,\,\text{ and
}\,\,M_{1}=\begin{pmatrix}0,1,1,0,0,0,0,0,0,0,0,0\\\
0,0,0,0,0,0,0,0,0,0,0,0\\\ 0,0,0,0,0,0,0,0,0,0,0,0\\\
0,1,0,0,0,0,1,0,0,0,0,0\\\ 0,0,0,0,0,0,0,0,1,0,0,0\\\
0,0,0,0,0,0,0,0,1,1,0,0\\\ 0,0,0,0,0,0,0,0,0,0,0,0\\\
0,0,0,0,0,0,0,0,1,0,0,1\\\ 0,0,0,0,0,0,0,0,0,0,0,0\\\
0,0,0,0,0,0,0,0,0,0,0,0\\\ 0,1,0,0,0,0,0,0,0,0,0,0\\\
0,0,0,0,0,0,0,0,0,0,0,0\end{pmatrix}$ (18)

######  Lemma 5.13.

  1. (i)

$F_{6r+14}-18F_{6r+8}+F_{6r+2}=0$ for all $r\in\mathbb{N}$.

  2. (ii)

$F_{6r+14}-6F_{6r+8}-16F_{6r+7}-16F_{6r+4}+5F_{6r+2}=0$ for all
$r\in\mathbb{N}$.

###### Proof.

The first statement follows from Binet’s formula (1) and the fact that the
polynomial $x^{2}-x-1$ is a factor of $x^{12}-18x^{6}+1$. The second statement
follows from Binet’s formula and the fact that $x^{2}-x-1$ is a factor of
$x^{12}-6x^{6}-16x^{5}-16x^{2}+5$. ∎

######  Lemma 5.14.

Let $n=n(r)$ have Fibonacci representation $(100100)^{r}$. Then,

$\mathbf{sum_{ftm}}$$(n)=a(r)+b(r)$, where $a(r)=(F_{6r+2}-1)/4$ and

$b(r)=(F_{6r+8}-13F_{6r+2}-32r-8)/32$.

###### Proof.

Let $A=M_{1}*M_{0}*M_{0}$. Then,

$\displaystyle A^{2}=\begin{pmatrix}1,0,0,5,2,0,0,5,0,0,4,0\\\
0,0,0,0,0,0,0,0,0,0,0,0\\\ 0,0,0,0,0,0,0,0,0,0,0,0\\\
0,0,0,7,4,0,0,6,0,0,4,0\\\ 0,0,0,4,3,0,0,4,0,0,2,0\\\
0,0,0,5,4,1,0,5,0,0,2,0\\\ 0,0,0,0,0,0,0,0,0,0,0,0\\\
0,0,0,6,4,0,0,7,0,0,4,0\\\ 0,0,0,0,0,0,0,0,0,0,0,0\\\
0,0,0,0,0,0,0,0,0,0,0,0\\\ 0,0,0,4,2,0,0,4,0,0,3,0\\\
0,0,0,0,0,0,0,0,0,0,0,0\end{pmatrix}$ (19)

Using the linear representation for $\mathbf{sum_{ftm}}$, we prove by
induction that

$v*(A^{2r})=(1,0,0,a(r),b(r),0,0,a(r),0,0,b(r)+2r,0)$

where the functions $a(r)$ and $b(r)$ are given in the statement of the lemma.
We have

$\displaystyle v*(A^{2r+2})=(1,0,0,a(r),b(r),0,0,a(r),0,0,b(r)+2r,0)*A^{2}$
$\displaystyle=(1,0,0,5+7a(r)+4b(r)+6a(r)+4b(r)+8r,2+4a(r)+3b(r)+4a(r)+2b(r)+4r,$
$\displaystyle
0,0,5+6a(r)+4b(r)+7a(r)+4b(r)+8r,0,0,4+4a(r)+2b(r)+4a(r)+3b(r)+6r)$
$\displaystyle=(1,0,0,5+13a(r)+8b(r)+8r,2+8a(r)+5b(r)+4r,0,0,5+13a(r)+8b(r)+8r,$
$\displaystyle 0,0,4+8a(r)+5b(r)+6r)$

From the definitions of $a(r)$ and $b(r)$, we have:

$\displaystyle 5+13a(r)$ $\displaystyle+8b(r)+8r$
$\displaystyle=5+13((F_{6r+2}-1)/4)+(F_{6r+8}-13F_{6r+2}-32r-8)/4+8r$
$\displaystyle=(F_{6r+8}-1)/4$ $\displaystyle=a(r+1).$

Again using the definitions of $a(r)$ and $b(r)$, we have:

$\displaystyle 8a(r)+$ $\displaystyle 5b(r)+4r+2$
$\displaystyle=(5F_{6r+8}-F_{6r+2}-32r-40)/32$
$\displaystyle=(F_{6r+14}-13F_{6r+8}-32r-40)/32$ $\displaystyle=b(r+1)$

where the second last step follows from lemma 5.13. This concludes the
inductive proof. ∎

######  Lemma 5.15.

Let $n=n(r)$ have Fibonacci representation $(100100)^{r}$. Then,

$\lfloor n/2\rfloor=a(r)+b(r)+r$, where $a(r)=(F_{6r+2}-1)/4$ and

$b(r)=(F_{6r+8}-13F_{6r+2}-32r-8)/32$.

###### Proof.

We first note that $a(r)+b(r)+r=(F_{6r+8}-5F_{6r+2}-16)/32$. We use induction
to show that, $n(r)=2a(r)+2b(r)+2r$. The inductive step is:

$\displaystyle n(r+1)$ $\displaystyle=(100100)^{r+1}=n(r)+F_{6r+4}+F_{6r+7}$
$\displaystyle=2a(r)+2b(r)+2r+F_{6r+4}+F_{6r+7}$
$\displaystyle=(F_{6r+8}+16F_{6r+7}+16F_{6r+4}-5F_{6r+2}-16)/16$
$\displaystyle=(F_{6r+8}+F_{6r+14}-6F_{6r+8}-16)/16$
$\displaystyle=(F_{6r+14}-5F_{6r+8}-16)/16$
$\displaystyle=2a(r+1)+2b(r+1)+2(r+1)$

where we have used lemma 5.13 and the definition of $a(r)$ and $b(r)$. This
completes the induction. ∎

Figure 7: Fibonacci-synchronising automaton for the function $\lfloor
n/2\rfloor$.

######  Corollary 5.16.

The running sum of the Fibonacci-Thue-Morse sequence is not Fibonacci-
synchronised.

###### Proof.

The sequence $\lfloor n/2\rfloor$ is Fibonacci-synchronised. A synchronising
automaton, taken from the paper [5], is shown at figure 7. Define the function
$g$ by

$g(n)=\begin{cases}\lfloor n/2\rfloor\dotdiv\mathbf{sum_{ftm}}(n),&\text{if
}\,\,n\,\,\text{has Fibonacci representation }\,\,(100100)^{r}\\\
0&\text{otherwise}\end{cases}$

If $\mathbf{sum_{ftm}}$$(n)$ is Fibonacci-synchronised, then so is $\lfloor
n/2\rfloor\dotdiv\mathbf{sum_{ftm}}(n)$ by theorem 2.1, which also applies to
Fibonacci representations. Hence, $g$ is also Fibonacci-synchronised since the
set of numbers having Fibonacci representation of the form $(100100)^{r}$ is
defined by a regular expression. If the Fibonacci-representation of $n$ has
the form $(100100)^{r}$, then $g(n)=r$ by lemmas 5.14 and 5.15. Since
$g(n)=\mathcal{O}(\log
n)=\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{{$\scriptscriptstyle\mathcal{O}$}}(n)$
and is unbounded, it cannot be a Fibonacci-synchronised function by theorem
2.2. Hence, $\mathbf{sum_{ftm}}$ is not Fibonacci-synchronised. ∎

## References

  * [1] OEIS Foundation Inc. (2024).  The On-Line Encyclopedia of Integer Sequences.
  * [2] Rob Burns.  Factorials and legendre’s three-square theorem.  01 2021.
  * [3] Rob Burns.  Factorials and legendre’s three-square theorem: Ii.  03 2022.
  * [4] Arturo Carpi and Cristiano Maggi.  On synchronized sequences and their separators.  RAIRO - Theoretical Informatics and Applications, 35(6):513 – 524, November 2001.
  * [5] Benoit Cloitre and Jeffrey Shallit.  Some fibonacci-related sequences.  12 2023.
  * [6] Hamoon Mousavi.  Automatic theorem proving in Walnut.  arXiv, 2016.
  * [7] Jeffrey Shallit.  Synchronized sequences.  In T. Lecroq and S. Puzynina, editors, Combinatorics on Words, pages 1–19. Springer International Publishing, 2021.
  * [8] Jeffrey Shallit.  The Logical Approach to Automatic Sequences.  Cambridge University Press, Sep 2022.
  * [9] The Sage Developers.  SageMath, the Sage Mathematics Software System (Version 8.2), 2018.  https://www.sagemath.org.