\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\usepackage{pgf,tikz}
\usetikzlibrary{arrows, automata, shapes, positioning}
\usetikzlibrary{decorations}
\usetikzlibrary{snakes}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\DeclareMathOperator{\val}{val}
\DeclareMathOperator{\rep}{rep}
\DeclareMathOperator{\lex}{lex}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{problem}[theorem]{Problem}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
The Formal Inverse of the \\
\vskip .12in
Period-Doubling Sequence
}
\vskip 1cm
\large
Narad Rampersad\footnote{The author is supported by NSERC Discovery
Grant 418646-2012.}\\
Department of Mathematics and Statistics\\
University of Winnipeg\\
515 Portage Avenue\\
Winnipeg, Manitoba R3B 2E9 \\
Canada\\
\href{mailto:n.rampersad@uwinnipeg.ca}{\tt n.rampersad@uwinnipeg.ca} \\
\ \\
Manon Stipulanti\footnote{The author is supported by FRIA Grant 1.E030.16.}\\
D\'epartement de Math\'ematique \\
University of Li\`ege\\
All\'ee de la D\'ecouverte 12 (B37) \\
4000 Li\`ege \\
Belgium \\
\href{mailto:m.stipulanti@uliege.be}{\tt m.stipulanti@uliege.be}
\end{center}
\vskip .2 in
\begin{abstract}
If $p$ is a prime number, consider a $p$-automatic sequence $(u_n)_{n\ge 0}$, and let $U(X) = \sum_{n\ge 0} u_n X^n \in \mathbb{F}_p[[X]]$ be its generating function.
Assume that there exists a formal power series $V(X) = \sum_{n\ge 0} v_n X^n \in \mathbb{F}_p[[X]]$ which is the compositional inverse of $U$, i.e., $U(V(X))=X=V(U(X))$.
The problem investigated in this paper is to study the properties of the sequence $(v_n)_{n\ge 0}$.
The work was first initiated for the Thue-Morse sequence, and more recently the case of other sequences (variations of the Baum-Sweet sequence, variations of the Rudin-Shapiro sequence and generalized Thue-Morse sequences) has been treated.
In this paper, we deal with the case of the period-doubling sequence.
We first show that the sequence of indices at which the period-doubling sequence takes the value $0$ (resp., $1$) is not $k$-regular for any $k\ge 2$.
Secondly, we give recurrence relations for its formal inverse, then we show that it is $2$-automatic, and we also provide an automaton that generates it.
Thirdly, we study the sequence of indices at which this formal inverse takes the value $1$, and we show that it is not $k$-regular for any $k\ge 2$ by connecting it to the characteristic sequence of Fibonacci numbers.
We leave as an open problem the case of the sequence of indices at which this formal inverse takes the value $0$.
\end{abstract}
\section{Introduction}
Let us consider the following problem.
Let $p$ be a prime number.
Let $\boldsymbol{u}=(u_n)_{n\ge 0}$ be a $p$-automatic sequence and let $U(X) = \sum_{n\ge 0} u_n X^n \in \mathbb{F}_p[[X]]$ be its generating function.
Assume that there exists a formal power series $V(X) = \sum_{n\ge 0} v_n X^n \in \mathbb{F}_p[[X]]$ which is the compositional inverse of $U$, i.e., $U(V(X))=X=V(U(X))$.
What can be said about properties of the sequence $\boldsymbol{v}=(v_n)_{n\ge 0}$?
Gawron and Ulas~\cite{GU16} initiated work on this problem,
and they consider the case where $\boldsymbol{u}=\boldsymbol{t}$ is the well-known Prouhet-Thue-Morse sequence.
More precisely, they studied the sequence $\boldsymbol{c}=(c_n)_{n\ge 0}$, which is the sequence of coefficients of the compositional inverse of the generating function of the sequence $\boldsymbol{t}$.
They called this sequence $\boldsymbol{c}$ the \textit{inverse Prouhet-Thue-Morse sequence}.
The $2$-automaticity of $\boldsymbol{c}$ is easily deduced using Christol's theorem~\cite{CKMFR80}, but they also exhibited some recurrence relations satisfied by $\boldsymbol{c}$ and provided an automaton that generates $\boldsymbol{c}$.
They studied two increasing sequences $\boldsymbol{a} = (a_n)_{n\ge 0}$ and $\boldsymbol{d} = (d_n)_{n\ge 0}$ respectively defined by
\[
\{a_n \mid n\in \mathbb{N}\} = \{m \in \mathbb{N} \mid c_m= 1\},
\]
and
\[
\{d_n \mid n\in \mathbb{N}\} =\{m \in \mathbb{N} \mid c_m= 0\}.
\]
In particular, they proved that $\boldsymbol{a}$ is $2$-regular,
but that $\boldsymbol{d}$ is not $k$-regular for any $k\ge 2$.
More recently, this work has been extended to other sequences~\cite{Merta18,Merta18bis}.
The author first obtains results similar to~\cite{GU16} for two variations of the Baum-Sweet sequence, and secondly for generalized Thue-Morse sequences (two specific cases) and two variations of the Rudin-Shapiro sequence.
In this paper, we consider the case where $\boldsymbol{u}=\boldsymbol{d}$ is the period-doubling sequence.
This sequence is defined by $d_n := \nu_2 (n + 1) \bmod{2}$, where the function $\nu_2$ is the exponent of the highest power of $2$ dividing its argument.
\section{Background}
In this section, we recall the necessary background for this paper; see, for instance, \cite{AS03, Rigo1, Rigo2} for more details.
\subsection{Combinatorics on words}
Let $A$ be a finite \emph{alphabet}, i.e., a finite set consisting of \emph{letters}.
A \emph{(finite) word} $w$ over $A$ is a finite sequence of letters belonging to $A$.
If $w=w_n w_{n-1} \cdots w_0 \in A^*$ with $n\ge 0$ and $w_i \in A$ for all $i\in\{0,\ldots,n\}$, then the \emph{length $|w|$} of $w$ is $n+1$, i.e., it is the number of letters that $w$ contains.
We let $\varepsilon$ denote the empty word.
This special word is the neutral element for concatenation of words, and its length is set to be $0$.
The set of all finite words over $A$ is denoted by $A^*$, and we let $A^+=A^*\setminus\{\varepsilon\}$ denote the set of non-empty finite words over $A$. For any $n\ge 0$, we let $A^n$ denote the set of length-$n$ words in $A^*$.
A finite word $w\in A^*$ is a \emph{prefix} of another finite word $z\in A^*$ if there exists $u\in A^*$ such that $z=wu$.
If $A$ is ordered by $<$, the \emph{lexicographic order} on $A^*$, which we denote by $<_{\lex}$, is a total order on $A^*$ induced by the order $<$ on the letters and defined as follows: $u <_{\lex} v$ either if $u$ is a strict prefix of $v$ or if there exist $a,b\in A$ and $p\in A^*$ such that $a**1$ are \emph{multiplicatively independent} if the only integers $k,\ell$ such that $\alpha^k = \beta^\ell$ are $k=\ell=0$.
Otherwise, $\alpha$ and $\beta$ are \emph{multiplicatively dependent}.
The following result can be found in~\cite{Dur11}.
\begin{theorem}[Cobham-Durand]\label{thm:Cobham-Durand-2011}
Let $\alpha, \beta >1$ be two multiplicatively independent real numbers.
Let $\boldsymbol{u}$ (resp., $\boldsymbol{v}$) be a pure $\alpha$-substitutive (resp., pure $\beta$-substitutive) word.
Let $g$ and $g'$ be two non-erasing morphisms.
If $\boldsymbol{w} = g(\boldsymbol{u}) = g'(\boldsymbol{v})$, then $\boldsymbol{w}$ is ultimately periodic.
In particular, if an infinite word is $\alpha$-substitutive and $\beta$-substitutive, i.e., in the special case where $g$ and $g'$ are codings, then it is ultimately periodic.
\end{theorem}
\subsection{Abstract numeration systems, automatic sequences and regular sequences}
An \emph{abstract numeration system} (ANS) is a triple $S = (L,A,<)$ where $L$ is an infinite regular language over a totally ordered alphabet $(A,<)$.
The map $\rep_S : \mathbb{N} \to L$ is the one-to-one correspondence mapping $n \in \mathbb{N}$ onto the $(n+1)$st word in the genealogically ordered language $L$, which is called the \emph{$S$-representation} of $n$.
The $S$-representation of $0$ is the first word in $L$.
The inverse map is denoted by $\val_S : L \to \mathbb{N}$.
If $w$ is a word in $L$, $\val_S(w)$ is its \emph{$S$-numerical value}.
For instance, the base-$k$ numeration system is an ANS; the Zeckendorff numeration system based on the Fibonacci numbers (with initial conditions $1$ and $2$) is also an ANS.
A \emph{deterministic finite automaton with output} (DFAO) is a
$6$-tuple $\mathcal{A}=(Q,q_0,A, \delta , B,\mu)$, where $Q$ is a finite set of \emph{states}, $q_0 \in Q$ is the \emph{initial state}, $A$ is a finite \emph{input alphabet},
$\delta : Q \times A \to Q$ is the \emph{transition function}, $B$ is a finite \emph{output alphabet}, and $\mu : Q \to B$ is the \emph{output function}.
If $S = (L, A, <)$ is an ANS, we say that an infinite word $\boldsymbol{w} = w_0 w_1 w_2 \cdots \in B^\mathbb{N}$ is \emph{$S$-automatic} if there exists a DFAO $\mathcal{A}=(Q,q_0,A, \delta , B,\mu)$ such that $x_n = \mu(\delta(q_0, \rep_S (n)))$ for all $n \ge 0$.
The automaton $\mathcal{A}$ is called a \emph{$S$-DFAO}.
When the $ANS$ is the base-$k$ numeration system with $k\ge 2$,
we have the following theorem of Cobham~\cite{Cobham72}.
\begin{theorem}[Cobham's theorem on automatic sequences]\label{thm:Cobham-1972}
An infinite word $\boldsymbol{w} \in B^\mathbb{N}$ is $k$-automatic if and only if there exist a $k$-uniform morphism $f : A^* \to A^*$ prolongable on a letter $a\in A$ and a coding $g : A^* \to B^*$ such that $\boldsymbol{w} = g( f^\omega (a) )$.
\end{theorem}
Let $\boldsymbol{u} = (u_n)_{n\ge 0}$ be an infinite sequence and let $k\ge 2$ be an integer.
We define the \emph{$k$-kernel} of $\boldsymbol{u}$ to be the set of subsequences
\[
\mathcal{K}_k(\boldsymbol{u})=\{ (u_{k^i\cdot n+r})_{n\ge 0} \mid i \ge 0 \text{ and } 0\le r < k^i \}.
\]
We say that a sequence $\boldsymbol{u}$ is \emph{$k$-regular} if there exists a finite set $S$ of sequences such that every sequence in $\mathcal{K}_k(\boldsymbol{u})$ is a $\mathbb{Z}$-linear combination of sequences of $S$.
The following properties can be found in~\cite{AS03,Schaeffer13}.
\begin{proposition}\label{pro:prop-aut-reg}
Let $k\ge 2$ be an integer.
\begin{itemize}
\item[$(1)$] If a sequence differs only in finitely many terms from a $k$-automatic sequence, then it is $k$-automatic.
\item[$(2)$] For all $m \ge 1$, a sequence is $k$-automatic if and only if it is $k^m$-automatic.
\item[$(2)$] If the integer sequence $(u_n)_{n\ge 0}$ is $k$-regular, then for all integers $m \ge 1$, the sequence $(u_n \bmod{m})_{n\ge 0}$ is $k$-automatic.
\item[$(3)$] A sequence is $k$-regular and takes only finitely many values if and only if it is $k$-automatic.
\item[$(4)$] Let $(u_n)_{n\ge 0}$ be a $k$-regular sequence. Then for $a\ge 1$ and $b\ge 0$, the sequence $(u_{an+b})_{n\ge 0}$ is $k$-regular.
\item[$(5)$] Let $\boldsymbol{u}=(u_n)_{n\ge 0}$ be a sequence, and let $\boldsymbol{v}=(u_{n+1}-u_n)_{n\ge 0}$ be the first difference of $\boldsymbol{u}$.
Then $\boldsymbol{u}$ is $k$-regular if and only if $\boldsymbol{v}$ is $k$-regular.
\end{itemize}
\end{proposition}
\subsection{Formal power series}
Let $k\ge 2$.
The \emph{ring $\mathbb{F}_k[[X]]$ of formal power series with coefficients in the field $\mathbb{F}_k = \{0,1, \ldots, k-1\}$} is defined by
\[
\mathbb{F}_k[[X]] = \left\{ \sum_{n\ge 0} a_n X^n \mid a_n \in \mathbb{F}_k \right\}.
\]
We let $\mathbb{F}_k(X)$ denote the \emph{the field of rational functions}.
We say that a formal series $A(X)=\sum_{n\ge 0} a_n X^n$
is \emph{algebraic (over $\mathbb{F}_k(X)$)} if there exist an integer $d \ge 1$ and polynomials $P_0(X)$, $P_1(X)$, $\ldots$, $P_d(X)$, with coefficients in $\mathbb{F}_k$ and not all zero, such that
\[
P_0+P_1 A+P_2 A^ 2+ \cdots + P_d A^d =0.
\]
With an infinite sequence $\boldsymbol{w}=(w_n)_{n \in \mathbb{N}}$ over $\{0,1,\ldots,k-1\}$, we can associate a formal series $W(X) = \sum_{n\ge 0} w_n X^n$ over $\mathbb{F}_k[[X]]$, which is called the \emph{generating function} of $\boldsymbol{w}$.
In the case where $k=p$ is a prime number, and if $w_0=0$ and $w_1$ is invertible in $\mathbb{F}_p$, then the series $W(X)$ is \emph{invertible} in $\mathbb{F}_p[[X]]$, i.e., there exists a series
$U(X) \in \mathbb{F}_p[[X]]$ such that $W(U(X)) = X = U(W(X))$.
The formal series $U(X)$ is called the \emph{(formal) inverse} of $W(X)$.
\section{The period-doubling sequence}
The following definition can be found in~\cite{AS03}.
\begin{definition}
Consider the period-doubling sequence (indexed by \texttt{A096268} in \cite{Sloane})
$$
\boldsymbol{d} = (d_n)_{n\ge 0} =0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 \cdots .
$$
This sequence is defined by $d_n := \nu_2 (n + 1) \bmod{2}$, where the function $\nu_2$ is the exponent of the highest power of $2$ dividing its argument.
Alternatively, we have $\boldsymbol{d} = h^{\omega}(0)$, where $h(0) = 01$ and $h(1) = 00$.
Since $h$ is a $2$-uniform morphism, then the period doubling sequence $\boldsymbol{d}$ is $2$-automatic.
The $2$-DFAO drawn in Figure~\ref{fig:aut-pd} generates the period-doubling sequence $\boldsymbol{d}$.
Note that this automaton reads its input from most significant digit to least significant digit.
\begin{figure}
\begin{center}
\begin{tikzpicture}
\tikzstyle{every node}=[shape=circle,fill=none,draw=black,minimum size=20pt,inner sep=2pt]
\node[](a) at (0,0) {$0$};
\node[](b) at (2,0) {$1$};
\tikzstyle{every node}=[shape=circle,fill=none,draw=none,minimum size=10pt,inner sep=2pt]
\node(a0) at (-1.5,0) {};
\tikzstyle{every path}=[color =black, line width = 0.5 pt, > = triangle 45]
\tikzstyle{every node}=[shape=circle,minimum size=5pt,inner sep=2pt]
\draw [->] (a0) to [] node [] {} (a);
\draw [->] (a) to [loop above] node [above] {$0$} (a);
\draw [->] (a) to [bend left] node [above] {$1$} (b);
\draw [->] (b) to [bend left] node [below] {$0,1$} (a);
;
\end{tikzpicture}
\caption{The $2$-DFAO generating the period-doubling sequence $\boldsymbol{d}$.}
\label{fig:aut-pd}
\end{center}
\end{figure}
\end{definition}
Let us define two increasing sequences $\boldsymbol{o} = (o_n)_{n\ge 0}$ and $\boldsymbol{z} = (z_n)_{n\ge 0}$ respectively satisfying $\{o_n \mid n\in N\}=\{m\in N \mid d_m =1\}$ and $\{z_n \mid n\in N\}=\{m\in N \mid d_m =0\}$.
We have
\begin{align*}
\boldsymbol{o}&=
1, 5, 7, 9, 13, 17, 21, 23, 25, 29, 31, 33, 37, 39, 41, 45, 49, 53, 55, 57, 61, 65, 69, 71, 73, 77, \ldots, \\
\boldsymbol{z}&=
0, 2, 3, 4, 6, 8, 10, 11, 12, 14, 15, 16, 18, 19, 20, 22, 24, 26, 27, 28, 30, 32, 34, 35, 36, 38, 40, \ldots.
\end{align*}
Those two sequences are indexed by \texttt{A079523} and \texttt{A121539} in~\cite{Sloane}.
Observe that the binary expansions of the terms of $\boldsymbol{o}$ (resp., $\boldsymbol{z}$) end with an odd (resp., even) number of $1$'s.
This can be seen if one considers the language accepted by the $2$-DFAO in Figure~\ref{fig:aut-pd} where the final state is the one outputting $1$ (resp., $0$).
In the following, we study the regularity of the sequences $\boldsymbol{o}$ and $\boldsymbol{z}$.
\begin{proposition}\label{pro:pd-0-not-k-reg}
The sequence $\boldsymbol{z}=(z_n)_{n\ge 0}$ is not $k$-regular for any $k \in \mathbb{N}_{\ge 2}$.
\end{proposition}
\begin{proof}
Let $\boldsymbol{\bar{d}}$ be the image of $\boldsymbol{d}$ under the exchange morphism $E: \{0,1\}^* \to \{0,1\}^*: 0\mapsto 1, 1\mapsto 0$.
In particular, $\boldsymbol{\bar{d}}$ is the fixed point of the morphism $h'(0) = 11$ and $h'(1) = 10$ starting with $1$.
We also have
\[
\boldsymbol{z} = \{m \in \mathbb{N} \mid d_m=0\} = \{m \in \mathbb{N} \mid \bar{d}_m=1\}.
\]
The sequence $\boldsymbol{\bar{d}}$ is related to the Thue-Morse sequence in the following way.
Let $\boldsymbol{t}=(t_n)_{n\ge 0}$ be the Thue-Morse sequence, i.e., the fixed point of the morphism $\tau : \{0,1\}^* \to \{0,1\}^* : 0 \mapsto 01, 1 \mapsto 10$ which starts with $0$.
In fact, the sequence $\boldsymbol{\bar{d}}$ is the first difference modulo $2$ of the Thue-Morse sequence $\boldsymbol{t}$~\cite{AS99}, i.e., $\boldsymbol{\bar{d}}=(t_{n+1}- t_n \bmod{2})_{n\ge 0}$.
In other words, the sequence $\boldsymbol{z}$ of positions of $1$'s in $\boldsymbol{\bar{d}}$ is exactly the sequence of positions in the Thue-Morse sequence $\boldsymbol{t}$ where the letters $0$ and $1$ alternate.
Consequently, the first difference of $\boldsymbol{z}$, which is the first difference between the positions of $1$'s in $\boldsymbol{\bar{d}}$, gives the length of the blocks of consecutive identical letters in $\boldsymbol{t}$, i.e., it is the sequence of run lengths of $\boldsymbol{t}$.
However, the sequence of run lengths of $\boldsymbol{t}$ is the sequence $\boldsymbol{p}=(p_n)_{n\ge 0}$ which is the fixed point of the morphism $f : \{1,2\}^* \to \{1,2\}^* : 1 \mapsto 121, 2 \mapsto 12221$ which starts with $1$~\cite{Aetal95}.
This sequence $\boldsymbol{p}$ is not $2$-automatic~\cite{AAS}, and by Proposition~\ref{pro:prop-aut-reg}, $\boldsymbol{p}$ is not $2^m$-automatic for any $m\ge 1$.
Let us show that $\boldsymbol{p}$ is not $k$-automatic for any integer $k\ge 2$.
Suppose that $\boldsymbol{p}$ is $k$-automatic for some integer $k\ge 2$ which is not a power of $2$.
Then, by Theorem~\ref{thm:Cobham-1972}, $\boldsymbol{p}$ is the image under a coding of the fixed point of a $k$-uniform morphism whose Perron-Frobenius eigenvalue is $k$.
Since the Perron-Frobenius eigenvalue of $f$ is $2$, then by
Theorem~\ref{thm:Cobham-Durand-2011}, $\boldsymbol{p}$ is ultimately periodic, which is impossible.
Now since $\boldsymbol{p}$ takes only two different values, $\boldsymbol{p}$ is not $k$-regular for any $k\ge 2$ by Proposition~\ref{pro:prop-aut-reg}.
Since $\boldsymbol{p}$ is the first difference of $\boldsymbol{z}$, then $\boldsymbol{z}$ is not $k$-regular for any $k\ge 2$ again by Proposition~\ref{pro:prop-aut-reg}.
\end{proof}
The next lemma gives two other morphisms that generate the period-doubling sequence $\boldsymbol{d}$.
Those morphisms are helpful to locate the positions of $1$'s in $\boldsymbol{d}$.
\begin{lemma}\label{lem:pd-fixed-point}
Let $f : \{2,4\}^* \to \{2,4\}^* : 2 \mapsto 242, 4 \mapsto 24442$ and $g : \{2,4\}^* \to \{0,1\}^* : 2 \mapsto 01, 4 \mapsto 0001$.
For all $n\ge 1$, we have $h^{2n+1}(0)=g(f^n(2))$ and $h^{2n+1}(10)=g(f^n(4))$.
In particular, $\boldsymbol{d}=h^\omega(0) = g(f^\omega(2))$.
\end{lemma}
\begin{proof}
We proceed by induction on $n\ge 1$.
The case $n=1$ can easily be checked by hand.
Now assume that $n\ge 1$ and suppose that the result holds for all $m\le n$.
We have
\[
h^{2(n+1)+1}(0)
=h^{2n+1}(0100)
=h^{2n+1}(0)h^{2n+1}(10)h^{2n+1}(0).
\]
Now, by induction hypothesis, we find
\[
h^{2(n+1)+1}(0)
=g(f^n(2))g(f^n(4))g(f^n(2))
=g(f^n(242))
=g(f^{n+1}(2)),
\]
as expected.
Similarly, we have
\[
h^{2(n+1)+1}(10)
=h^{2n+1}(01010100)
=h^{2n+1}(0)h^{2n+1}(10)h^{2n+1}(10)h^{2n+1}(10)h^{2n+1}(0),
\]
and by induction hypothesis, we get
\[
h^{2(n+1)+1}(0)
=g(f^n(2))g(f^n(4))g(f^n(4))g(f^n(4))g(f^n(2))
=g(f^n(24442))
=g(f^{n+1}(4)).
\]
The particular case can be deduced from the first equality of the statement.
\end{proof}
\begin{proposition}\label{pro:pd-1-not-k-reg}
The sequence $\boldsymbol{o}=(o_n)_{n\ge 0}$ is not $k$-regular for any $k \in \mathbb{N}_{\ge 2}$.
\end{proposition}
\begin{proof}
By Lemma~\ref{lem:pd-fixed-point}, we know that $\boldsymbol{d}= g(f^\omega(2))$ with $f : \{2,4\}^* \to \{2,4\}^* : 2 \mapsto 242, 4 \mapsto 24442$ and $g : \{2,4\}^* \to \{0,1\}^* : 2 \mapsto 01, 4 \mapsto 0001$.
Observe that $|g(2)|=2$ and $|g(4)|=4$, and the letter $1$ occurs only once at the end of $g(2)$ (resp., $g(4)$).
Consequently, the first difference of the positions of $1$'s in $\boldsymbol{d}$ --- which is the first difference of $\boldsymbol{o}$ --- is given by the shift of the sequence $f^\omega(2)$, i.e., we drop the first term.
By the proof of Proposition~\ref{pro:pd-0-not-k-reg}, we know that $f^\omega(2)$ is not $k$-regular for any $k\ge 2$.
By Proposition~\ref{pro:prop-aut-reg}, $\boldsymbol{o}$ is not $k$-regular for any $k\ge 2$.
\end{proof}
\begin{remark}
Using an argument similar to the one of the proof of Proposition~\ref{pro:pd-1-not-k-reg}, one can also get another way of proving Proposition~\ref{pro:pd-0-not-k-reg}.
\end{remark}
\section{The formal inverse of the period-doubling word}
Let $D(X) = \sum_{n\ge 0} d_n X^n$ be the generating function of the period-doubling sequence $\boldsymbol{d}$.
Since $d_0=0$ and $d_1=1$ is invertible in $\mathbb{F}_2$, then the series $D(X)$ is invertible in $\mathbb{F}_2[[X]]$, i.e., there exists a series
$$
U(X) = \sum_{n\ge 0} u_n X^n \in \mathbb{F}_2[[X]]
$$
such that $D(U(X)) = X = U(D(X))$.
We want to describe the sequence $\boldsymbol{u}=(u_n)_{n\ge 0}$.
Mimicking~\cite{GU16}, the first step is to get recurrence relations for the coefficients $(u_n)_{n\ge 0}$ of the series $U(X)$.
To that aim, recall the following result; see~\cite[p.~412]{CKMFR80}.
\begin{lemma}\label{lem:period-doubling-inverse}
The generating function $D(X) = \sum_{n\ge 0} d_n X^n$ of the period-doubling sequence $\boldsymbol{d}$ satisfies
\[
X (1 + X^2) D(X)^2 + (1 + X^2) D(X) + X =0
\]
over $\mathbb{F}_2[[X]]$.
\end{lemma}
\begin{proof}
Observe that, since $\boldsymbol{d}=h^\omega(0)$, we have $d_{2n} = 0$ and $d_{2n+1} = 1 - d_n$ for all $n\ge 0$.
Thus we have
\[
D(X)
= \sum_{n\ge 0} d_n X^n
= \sum_{n\ge 0} d_{2n} X^{2n} + \sum_{n\ge 0} d_{2n+1} X^{2n+1}
= X \sum_{n\ge 0} X^{2n} - X \sum_{n\ge 0} d_n X^{2n}.
\]
Now recall that, for any prime $p$ and for any series $F(X)$ in $\mathbb{F}_p[[X]]$, we have $1/(1-X) = \sum_{n\ge 0} X^n$.
Consequently,
\[
D(X)
= \frac{X}{1 - X^2} - X D(X^2).
\]
Now working over $\mathbb{F}_2[[X]]$, we have
$$
X (1 + X^2) D(X^2) + (1 + X^2) D(X) + X =0,
$$
and since for any prime $p$ and for any series $F(X)$ in $\mathbb{F}_p[[X]]$, we have $F(X)^p = F(X^p)$, we find
\[
X (1 + X^2) D(X)^2 + (1 + X^2) D(X) + X =0,
\]
as desired.
\end{proof}
To prove the next result, we follow the method from~\cite{GU16}.
\begin{proposition}\label{pro:pol-and-rec-u}
The series $U(X)=\sum_{n\ge 0} u_n X^n$ satisfies each of the following polynomial equations
\begin{align*}
& X^2 U(X)^3 + X U(X)^2 + (X^2 +1) U(X) + X =0,\\
&X^3 U(X)^4 + X^3 U(X)^2 + U(X) + X =0
\end{align*}
over $\mathbb{F}_2[[X]]$.
In particular, the sequence $\boldsymbol{u}=(u_n)_{n\ge 0}$ verifies $u_0 = 0$, $u_1=1$, and over $\mathbb{F}_2$
\[
\begin{cases}
u_{2n} = 0 \quad \forall \, n \ge 0, \\
u_{4n+1} = u_{2n-1} \quad \forall \, n \ge 1, \\
u_{4n+3} = u_n \quad \forall \, n \ge 0. \\
\end{cases}
\]
\end{proposition}
\begin{proof}
First, let us rewrite the equation from Lemma~\ref{lem:period-doubling-inverse} in terms of $X$.
We get
\[
D(X)^2 X^3 + D(X) X^2 + (D(X)^2 +1) X + D(X) =0.
\]
In this new equation, replace $X$ by $U(X)$ to obtain
\[
D(U(X))^2 U(X)^3 + D(U(X)) U(X)^2 + (D(U(X))^2 +1) U(X) + D(U(X)) =0.
\]
Since $U(X)$ is the formal inverse of $D(X)$, we actually have
\begin{equation}\label{eq:period-doubling-inverse-5}
X^2 U(X)^3 + X U(X)^2 + (X^2 +1) U(X) + X =0,
\end{equation}
which is the first equation of the statement.
This in turn implies that, over $\mathbb{F}_2[[X]]$,
\begin{equation}\label{eq:period-doubling-inverse-6}
U(X)^3 = \frac{X U(X)^2 + (X^2 +1) U(X) + X}{X^2}.
\end{equation}
Now multiply~\eqref{eq:period-doubling-inverse-5} by $U(X)$ and replace $U(X)^3$ by its value~\eqref{eq:period-doubling-inverse-6}.
We obtain first
\[
X^2 U(X)^4 + X U(X)^3 + (X^2 +1) U(X)^2 + X U(X) =0,
\]
and so
\begin{align*}
&X^2 U(X)^4 + X \left( \frac{X U(X)^2 + (X^2 +1) U(X) + X}{X^2} \right) + (X^2 +1) U(X)^2 + X U(X) =0 \\
&\Rightarrow X^3 U(X)^4 + X U(X)^2 + (X^2 +1) U(X) + X + (X^3 +X) U(X)^2 + X^2 U(X) =0\\
&\Rightarrow X^3 U(X)^4 + (X^3 +2X) U(X)^2 + (2X^2 +1) U(X) + X =0.
\end{align*}
Working over $\mathbb{F}_2[[X]]$, this equality becomes
\[
X^3 U(X)^4 + X^3 U(X)^2 + U(X) + X =0
\Leftrightarrow X^3 U(X^4) + X^3 U(X^2) + U(X) + X =0,
\]
which is the second equation of the statement.
Let us now prove that the recurrence relations for the sequence $\boldsymbol{u}$ hold.
Writing $U(X)=\sum_{n\ge 0} u_n X^{n}$ in the second equation proven above, we find
\begin{align*}
&X^3 \sum_{n\ge 0} u_n X^{4n} + X^3 \sum_{n\ge 0} u_n X^{2n} + \sum_{n\ge 0} u_n X^{n} + X =0 \\
\Leftrightarrow &\sum_{n\ge 0} u_n X^{4n+3} + \sum_{n\ge 0} u_n X^{2n+3} + \sum_{n\ge 0} u_n X^{n} + X =0.
\end{align*}
Let us inspect the coefficients in the last equality.
We immediately have $u_0=0$ and $u_1=1$ over $\mathbb{F}_2$.
Since the exponents $4n+3$ and $2n+3$ are odd for all $n\ge 0$, we also get that, over $\mathbb{F}_2$,
$$
u_{2n} = 0 \quad \forall \, n \ge 0.
$$
Looking at the coefficient of $X^{4n+3}$, we obtain
$$
u_n + u_{2n} + u_{4n+3} = 0 \quad \forall \, n \ge 0,
$$
which implies that $u_{4n+3} = u_n$ over $\mathbb{F}_2$ for all $n\ge 0$.
Let us now find the coefficient of $X^{4n+1}$ for $n\ge 1$.
We have
$$
u_{2n-1} + u_{4n+1} = 0 \quad \forall \, n \ge 1,
$$
giving $u_{4n+1} = u_{2n-1}$ over $\mathbb{F}_2$ for all $n\ge 1$.
As a consequence, the sequence $\boldsymbol{u}=(u_n)_{n\ge 0}$ verifies $u_0 = 0$, $u_1=1$, and satisfies the following recurrence relations over $\mathbb{F}_2$
\[
\left\{
\begin{array}{l}
u_{2n} = 0 \quad \forall \, n \ge 0, \\
u_{4n+1} = u_{2n-1} \quad \forall \, n \ge 1, \\
u_{4n+3} = u_n \quad \forall \, n \ge 0. \\
\end{array}
\right.
\]
\end{proof}
From now on, the sequence $\boldsymbol{u}=(u_n)_{n\ge 0}$ will be referred to as the \emph{inverse period-doubling sequence}, iPD sequence for short (sequence \texttt{A317542} in \cite{Sloane}).
We have
\[
\boldsymbol{u}=(u_n)_{n\ge 0} =
0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 \cdots.
\]
\begin{remark}
We have $d_n = u_n$ for all $n\le 8$, but observe that
$$
1 = d_{4\cdot 2 + 1} = d_9 \neq u_9 = u_{4\cdot 2 + 1}u= u_{2 \cdot 2 - 1} = u_3 = 0.
$$
\end{remark}
In the following, we show that $\boldsymbol{u}$ is $2$-automatic, and we also provide an automaton that generates $\boldsymbol{u}$, which is deduced from the recurrence relations in Lemma~\ref{lem:recurrences}.
\begin{corollary}
The sequence $\boldsymbol{u}=(u_n)_{n\ge 0}$ is $2$-automatic.
\end{corollary}
\begin{proof}
From Proposition~\ref{pro:pol-and-rec-u}, it follows that the formal power series $U(X)$ is algebraic over $\mathbb{F}_2(X)$.
By Christol's theorem, the sequence $\boldsymbol{u}$ is thus $2$-automatic.
\end{proof}
\begin{lemma}\label{lem:recurrences}
For all $n\ge 0$, $r_1\in\{0, 2\}$, $r_2\in\{0, 2,4,6\}$ and $r_3\in\{0, 2, 4, 6, 8, 10, 12, 14\}$, we have
\begin{align}
u_n &= u_{4n+3} = u_{16n+15}, \label{eq:u-rec-1} \\
u_{2n} &= u_{4n+r_1} = u_{8n+r_2} = u_{8n+3} = u_{16n+r_3} = u_{16n+3} = u_{16n+9} = u_{16n+11} = 0, \label{eq:u-rec-2} \\
u_{2n+1} &= u_{8n+7}, \label{eq:u-rec-3} \\
u_{4n+1} &= u_{8n+5} = u_{16n+1} = u_{16n+7} = u_{16n+13}, \label{eq:u-rec-4} \\
u_{8n+1} &= u_{16n+5}. \label{eq:u-rec-5}
\end{align}
\end{lemma}
\begin{proof}
We make an extensive use of the recurrence relations from Proposition~\ref{pro:pol-and-rec-u}.
We show that the $2$-kernel $\mathcal{K}_2(\boldsymbol{u})$ is finitely generated by the sequences $(u_n)_{n\ge 0}$, $(u_{2n})_{n\ge 0}$, $(u_{2n+1})_{n\ge 0}$, $(u_{4n+1})_{n\ge 0}$ and $(u_{8n+1})_{n\ge 0}$.
The first equality in~\eqref{eq:u-rec-1} is directly given by Proposition~\ref{pro:pol-and-rec-u}.
For all $n\ge 0$, we have
$$
u_{16n+15} = u_{4(4n+3)+3} = u_{4n+3} = u_n
$$
using Proposition~\ref{pro:pol-and-rec-u} twice since $n, 4n+3\ge 0$.
Let us show~\eqref{eq:u-rec-2}.
From Proposition~\ref{pro:pol-and-rec-u}, it is clear that for all $n\ge 0$,
$$
u_{2n} = 0 = u_{4n+r_1} = u_{8n+r_2} = u_{16n+r_3}.
$$
Now for all $n\ge 0$, we have
$$
u_{8n+3} = u_{4(2n)+3} = u_{2n} = 0,
$$
$$
u_{16n+3} = u_{4(4n)+3} = u_{4n} = u_{2n} = 0,
$$
and
$$
u_{16n+11} = u_{4(4n+2)+3} = u_{4n+2} = u_{2n} = 0,
$$
using Proposition~\ref{pro:pol-and-rec-u} since $2n, 4n, 4n+2 \ge 0$.
Similarly, for all $n\ge 0$, we have $4n+2\ge 1$, thus Proposition~\ref{pro:pol-and-rec-u} gives
$$
u_{16n+9} = u_{4(4n+2)+1} = u_{2(4n+2)-1} = u_{8n+3} = u_{2n} = 0,
$$
where the next-to-last equality comes from~\eqref{eq:u-rec-2} above.
Let us prove~\eqref{eq:u-rec-3}.
For all $n\ge 0$, we have
$$
u_{8n+7} = u_{4(2n+1)+3} = u_{2n+1},
$$
using Proposition~\ref{pro:pol-and-rec-u} since $2n+1 \ge 0$.
Let us show that~\eqref{eq:u-rec-4} holds.
For all $n\ge 0$, we have
$$
u_{8n+5} = u_{4(2n+1)+1} = u_{2(2n+1)-1} = u_{4n+1},
$$
$$
u_{16n+7} = u_{4(4n+1)+3} = u_{4n+1},
$$
and
$$
u_{16n+13} = u_{4(4n+3)+1} = u_{2(4n+3)-1} = u_{8n+5} = u_{4n+1},
$$
using Proposition~\ref{pro:pol-and-rec-u} since $2n+1, 4n+3 \ge 1$ and $4n+1 \ge 0$.
Now we prove that $u_{16n+1}=u_{4n+1}$ for all $n\ge 0$.
The result is trivial when $n=0$ for we have $u_{16n+1}=u_1=u_{4n+1}$.
Now suppose that $n\ge 1$.
We first obtain from Proposition~\ref{pro:pol-and-rec-u} that
$$
u_{16n+1} = u_{4(4n)n+1} = u_{2(4n)-1} = u_{8n-1}.
$$
Writing $n=m+1$ with $m\ge 0$, we then get
$$
u_{16n+1} = u_{8n-1} = u_{8m+7} = u_{2m+1}
$$
where the last equality comes from~\eqref{eq:u-rec-3} since $m\ge 0$.
Consequently,
$$
u_{16n+1} = u_{2m+1} = u_{2(m+1)-1} = u_{2n-1} = u_{4n+1}
$$
using Proposition~\ref{pro:pol-and-rec-u} for the last equality since $n\ge 1$.
This gives the expected recurrence relation.
Finally, for all $n\ge 0$, we have $4n+1 \ge 0$, so Proposition~\ref{pro:pol-and-rec-u} implies that
$$
u_{16n+5} = u_{4(4n+1)+1} = u_{2(4n+1)-1} = u_{8n+1},
$$
which proves~\eqref{eq:u-rec-5}.
\end{proof}
Using the recurrence relations from Lemma~\ref{lem:recurrences}, we build the $2$-DFAO in Figure~\ref{fig:aut-inverse-pd}, which generates the iPD sequence $\boldsymbol{u}$.
Note that this automaton reads its input from least significant digit to most significant digit.
\begin{figure}
\begin{center}
\begin{tikzpicture}
\tikzstyle{every node}=[shape=circle,fill=none,draw=black,minimum size=20pt,inner sep=2pt]
\node[](a) at (0,0) {$0$};
\node[](b) at (2,2) {$0$};
\node[](c) at (2,-2) {$1$};
\node[](d) at (4,-1.2) {$1$};
\node[](e) at (4,1.2) {$1$};
\tikzstyle{every node}=[shape=circle,fill=none,draw=none,minimum size=10pt,inner sep=2pt]
\node(a0) at (-1.5,0) {};
\tikzstyle{every path}=[color =black, line width = 0.5 pt, > = triangle 45]
\tikzstyle{every node}=[shape=circle,minimum size=5pt,inner sep=2pt]
\draw [->] (a0) to [] node [] {} (a);
\draw [->] (a) to [] node [above] {$0$} (b);
\draw [->] (a) to [bend left] node [right] {$1$} (c);
\draw [->] (b) to [loop above] node [above] {$0,1$} (b);
\draw [->] (c) to [bend left] node [left] {$1$} (a);
\draw [->] (c) to [] node [above] {$0$} (d);
\draw [->] (d) to [bend left] node [left] {$0$} (e);
\draw [->] (d) to [loop below] node [below] {$1$} (d);
\draw [->] (e) to [bend left] node [right] {$0$} (d);
\draw [->] (e) to [] node [above] {$1$} (b);
;
\end{tikzpicture}
\caption{The $2$-DFAO generating the inverse period-doubling sequence $\boldsymbol{u}$.}
\label{fig:aut-inverse-pd}
\end{center}
\end{figure}
Since the iPD sequence $\boldsymbol{u}$ takes the values $0$ and $1$, it can also be considered as a sequence of complex numbers.
We now obtain the transcendence of its generating function.
\begin{proposition}
The formal power series $U(X) = \sum_{n\ge 0} u_n X^n \in \mathbb{C}[[X]]$ is transcendental over $\mathbb{C}(X)$.
\end{proposition}
\begin{proof}
A classical result of Fatou states that a power series whose coefficients take only finitely many values is either rational or transcendental~\cite{Fatou}.
However, if the rational power series $A(X)=\sum_{n\ge 0} a_n X^n$ has bounded integer coefficients, then the sequence $(a_n)_{n\ge 0}$ must be ultimately periodic.
Since the iPD sequence $\boldsymbol{u}$ is not ultimately periodic, we deduce that $U(X) = \sum_{n\ge 0} u_n X^n \in \mathbb{C}[[X]]$ is transcendental over $\mathbb{C}(X)$.
\end{proof}
\section{Characteristic sequence of 1's in the iPD sequence $\boldsymbol{u}$}
In this section, we study the characteristic sequence of $1$'s in the iPD sequence $\boldsymbol{u}$.
The main result is that this sequence is not $k$-regular for any $k\ge 2$.
Surprisingly, it is related to the characteristic sequence of Fibonacci numbers.
\begin{definition}
Let us define an increasing sequence $\boldsymbol{a} = (a_n)_{n\ge 0}$ satisfying $\{a_n \mid n\in N\}=\{m\in N \mid u_m =1\}$ (sequence \texttt{A317543} in \cite{Sloane}).
We have
\[
\boldsymbol{a}=1, 5, 7, 13, 17, 23, 29, 31, 37, 49, 55, 61, 65, 71, 77, 95, 101, 113, 119, 125, 127, 133, 145, \ldots.
\]
From Proposition~\ref{pro:pol-and-rec-u}, we already know that $\boldsymbol{a}$ only contains odd integers.
In the $2$-DFAO in Figure~\ref{fig:aut-inverse-pd}, if the states outputting $1$ are considered to be final, then the binary expansions of the terms of $\boldsymbol{a}$ is the language
\[
L_a= \{ \rep_2(a_n) \mid n\ge 0 \} = \{11\}^* 1 \cup 1 \{1,00\}^* 0 \{11\}^* 1.
\]
For instance, $\rep_2(a_0)=1$, $\rep_2(a_1)=101$, $\rep_2(a_2)=111$, $\rep_2(a_3)=1101$.
\end{definition}
In the following, we obtain the complexity function of the language $L_a$.
To that aim, we define the sequence $(F(n))_{n\ge 0}$ of the Fibonacci numbers with initial conditions equal to $0$ and $1$, i.e., $F(0)=0$, $F(1)=1$ and, for all $n\ge 2$, let $F(n)=F(n-1)+F(n-2)$.
\begin{proposition}\label{pro:complexity-L-a}
The complexity function $\rho_{L_a} : \mathbb{N} \to \mathbb{N}$ of the language $L_a$ satisfies $\rho_{L_a}(0)=0$, $\rho_{L_a}(2n)=F(2n-1)-1$ for all $n\ge 1$, and $\rho_{L_a}(2n+1)=F(2n)+1$ for all $n\ge 0$.
\end{proposition}
\begin{proof}
Start with the $2$-DFAO in Figure~\ref{fig:aut-inverse-pd}.
If the states outputting $1$ are final, then it accepts the language $L_a$ if words are read starting with the least significant digit.
Let us reverse this $2$-DFAO to obtain the non-deterministic automaton in Figure~\ref{fig:aut-La}.
It accepts $L_a$ if words are read starting with the most significant digit.
\begin{figure}
\begin{center}
\begin{tikzpicture}
\tikzstyle{every node}=[shape=circle,fill=none,draw=black,minimum size=20pt,inner sep=2pt]
\node[accepting](a) at (0,0) {$0$};
\node[](b) at (2,2) {$0$};
\node[](c) at (2,-2) {$1$};
\node[](d) at (4,-1.2) {$1$};
\node[](e) at (4,1.2) {$1$};
\tikzstyle{every node}=[shape=circle,fill=none,draw=none,minimum size=10pt,inner sep=2pt]
\node(a0) at (2,-3.5) {};
\node(b0) at (5.2,-2) {};
\node(c0) at (5.5,1.2) {};
\tikzstyle{every path}=[color =black, line width = 0.5 pt, > = triangle 45]
\tikzstyle{every node}=[shape=circle,minimum size=5pt,inner sep=2pt]
\draw [->] (a0) to [] node [] {} (c);
\draw [->] (b0) to [] node [] {} (d);
\draw [->] (c0) to [] node [] {} (e);
\draw [->] (b) to [] node [above] {$0$} (a);
\draw [->] (c) to [bend left] node [left] {$1$} (a);
\draw [->] (b) to [loop above] node [above] {$0,1$} (b);
\draw [->] (a) to [bend left] node [right] {$1$} (c);
\draw [->] (d) to [] node [above] {$0$} (c);
\draw [->] (e) to [bend left] node [right] {$0$} (d);
\draw [->] (d) to [loop below] node [below] {$1$} (d);
\draw [->] (d) to [bend left] node [left] {$0$} (e);
\draw [->] (b) to [] node [above] {$1$} (e);
;
\end{tikzpicture}
\caption{A non-deterministic automaton accepting the language $L_a$.}
\label{fig:aut-La}
\end{center}
\end{figure}
Determinizing it leads to an automaton $\mathcal{A}_{L_a}$ whose state set is $\{1,\ldots,8\}$, with $1$ as initial state, with $2,6$ as final states, and whose transition table is given in Table~\ref{tab:tran-det-aut-La}.
\begin{table}[h!]
\begin{center}
\begin{tabular}{c|cc}
& 0 & 1 \\
\hline
1 & 8 & 2 \\
2 & 3 & 4 \\
3 & 5 & 6 \\
4 & 3 & 2 \\
5 & 3 & 5 \\
6 & 8 & 7 \\
7 & 8 & 6 \\
8 & 8 & 8
\end{tabular}
\end{center}
\caption{The transition table of a deterministic automaton accepting $L_a$.}
\label{tab:tran-det-aut-La}
\end{table}
Observe that this automaton accepts $L_a$, and has $8$ as a sink state.
Now let $M$ denote the adjacency matrix of $\mathcal{A}_{L_a}$ without considering the sink state $8$, and let
\[
u = (1,0,0,0,0,0,0) \; \text{ and } \; v = (0,1,0,0,0,1,0)^\top.
\]
Note that $v$ codes the final states of $\mathcal{A}_{L_a}$.
For all $n\ge 0$, $u M^n v$ is the number of length-$n$ words in $L_a$.
An easy induction shows that
\[
M^{2n} v
=(F(2n-1)-1,F(2n)+1,F(2n-1)-1, F(2n), F(2n), 1, 0)^\top \quad \forall \, n\ge 1,
\]
and
\[
M^{2n+1} v
=(F(2n)+1,F(2n+1)-1,F(2n)+1, F(2n+1), F(2n+1)-1, 0, 1)^\top \quad \forall \, n\ge 0.
\]
The conclusion follows.
\end{proof}
The sequence $(a_n \bmod{3})_{n\ge 0}$ shows a particularly unexpected behavior as explained in the next two results.
\begin{lemma}\label{lem:a-n-mod-3}
Let $n\ge 0$. Then $a_n \bmod{3} \equiv r$ with $r\in \{1,2\}$.
More precisely, let $w_n := \rep_2(a_n)$, and define $L_{a,1} = \{11\}^* 1$ and $L_{a,2} = 1 \{1,00\}^* 0 \{11\}^* 1$.
If $w_n \in L_{a,1}$, or if $w_n \in L_{a,2}$ and $|w_n|$ is even, then $a_n \bmod{3} \equiv 1$; if $w_n \in L_{a,2}$ and $|w_n|$ is odd, then $a_n \bmod{3} \equiv 2$.
\end{lemma}
\begin{proof}
First, we have
\begin{align}\label{eq:PowersOf2Mod3}
(2^n \bmod{3})_{n \ge 0} = (1, -1, 1, -1, 1, -1,\ldots).
\end{align}
Now let $n\ge 0$ and set $w_n := \rep_2(a_n)$.
If $w_n \in L_{a,1}$, then from~\eqref{eq:PowersOf2Mod3} we deduce that $a_n \bmod{3} \equiv 1$.
Assume that $w_n \in L_{a,2}$ and write $w_n=p_ns_n$ with $p_n \in 1\{1,00\}^*$ and $s_n \in 0\{11\}^*1$.
Since $|s_n|$ is even, then~\eqref{eq:PowersOf2Mod3} shows that $\val_2(s_n) \bmod{3} \equiv 1$.
As a first case, suppose that $|w_n|$ is odd.
Then $|p_n|$ is also odd, and so $p_n$ contains an odd number of $1$'s separated by even-length blocks of $0$'s.
Because the $0$'s blocks have even length, the contributions of successive $1$'s in $p_n$ alternate in value between $+1 \bmod{3}$ and $-1 \bmod{3}$.
Since $|s_n|$ is even, after reading $s_n$ then reading $p_n$ gives an additional $+1 \bmod{3}$.
Consequently, both $p_n$ and $s_n$ together give $2 \bmod{3}$, i.e., $a_n \bmod{3} \equiv \val_2(p_ns_n) \bmod{3} \equiv 2$.
As a second case, assume that $|w_n|$ is even.
Then $|p_n|$ is even, and so $p_n$ contains an even number of $1$'s separated by even-length blocks of $0$'s.
Again the $1$'s in $p_n$ contribute alternating $+1 \bmod{3}$ and $-1 \bmod{3}$, and since there is an even number of them, the $1$'s in $p_n$ contribute $0 \bmod{3}$ in total.
Thus, in this case, $a_n \bmod{3} \equiv \val_2(p_ns_n) \bmod{3} \equiv 1$.
\end{proof}
\begin{proposition}\label{pro:a-n-mod-3-Fib}
The sequence $(a_n \bmod{3})_{n\ge 0}$ is given by the infinite word
\[
1^{F(1)} 2^{F(2)} 1^{F(3)} 2^{F(4)} 1^{F(5)} 2^{F(6)} \cdots.
\]
In particular, the sequence of run lengths of $(a_n \bmod{3})_{n\ge 0}$ is the sequence of Fibonacci numbers $(F(n))_{n\ge 1}$ .
\end{proposition}
\begin{proof}
Recall that $L_a^n = L_a \cap \{0,1\}^n$ denotes the set of length-$n$ words in $L_a$.
We can order the words of $L_a^n$ by lexicographic order, i.e.,
\[
L_a^n = \{ w_{n,1} <_{\lex} w_{n,2} <_{\lex} \cdots <_{\lex} w_{n,\#L_a^n} \}.
\]
By Proposition~\ref{pro:complexity-L-a}, $\# L_a^0=0=\# L_a^2$,
$\# L_a^{2n} = F(2n-1)-1$ for all $n\ge 1$, and $\# L_a^{2n+1} = F(2n)+1$ for all $n\ge 0$.
Let us first consider $L_a^{2n}$ for $n\ge 2$.
From Lemma~\ref{lem:a-n-mod-3},
we know that $\val_2(w_{2n,i}) \bmod{3} \equiv 1$ for all $i\in\{1,2,\ldots, F(2n-1)-1\}$.
In other terms, we get
\[
(\val_2(w_{2n,i}) \bmod{3})_{1 \le i \le F(2n-1)-1} = 1^{F(2n-1)-1}.
\]
Let us now study $L_a^{2n+1}$ for $n\ge 0$.
In the case where $n=0$, then $L_a^{1}=\{w_{1,1}\}$ with $w_{1,1}=1$, which of course gives $\val_2(w_{1,1}) \bmod{3}=1^{F(1)}$.
Assume that $n\ge 1$.
Since the words of $L_a^{2n+1}$ are ordered lexicographically, we know that $w_{2n+1,i} \in L_{a,2}$ for all $i\in\{1,2,\ldots, F(2n)\}$, and $w_{2n+1,F(2n)+1}=1^{2n+1} \in L_{a,1}$.
From Lemma~\ref{lem:a-n-mod-3},
we obtain that $\val_2(w_{2n+1,i}) \bmod{3} \equiv 2$ for all $i\in\{1,2,\ldots, F(2n)\}$, and $\val_2(w_{2n+1,F(2n)+1}) \bmod{3} \equiv 1$.
In fact, we obtain
\[
(\val_2(w_{2n+1,i}) \bmod{3})_{1 \le i \le F(2n)+1} = 2^{F(2n)}1.
\]
Observe that, for any $n\ge 1$, concatenating the sequences $(\val_2(w_{2n+1,i}) \bmod{3})_{1 \le i \le F(2n)+1}$ and $(\val_2(w_{2n+2,i}) \bmod{3})_{1 \le i \le F(2n+1)-1}$ gives
$(2^{F(2n)}1) \cdot (1^{F(2n+1)-1}) = 2^{F(2n)} 1^{F(2n+1)}.$
Now putting everything together, we find
\begin{align*}
(a_n \bmod{3})_{n\ge 0}
&= 1^{F(1)} \cdot 2^{F(2)}1 \cdot 1^{F(3)-1} \cdot 2^{F(4)}1 \cdot 1^{F(5)-1} \cdot 2^{F(6)}1 \cdots \\
&= 1^{F(1)} 2^{F(2)} 1^{F(3)} 2^{F(4)} 1^{F(5)} 2^{F(6)} \cdots,
\end{align*}
as expected.
\end{proof}
To show that $\boldsymbol{a}$ is not $k$-regular for any $k\ge 2$, the idea is to study the sequence of consecutive differences in $(a_n \bmod{3})_{n\ge 0}$.
Let us define the sequence $\boldsymbol{\delta}=(\delta_n)_{n\ge 0}$ by
\[
\delta_n =
\left\{
\begin{array}{ll}
1, & \text{if } (a_{n+1} - a_n) \bmod{3}\neq 0; \\
0, & \text{otherwise}.
\end{array}
\right.
\]
From Proposition~\ref{pro:a-n-mod-3-Fib}, we know that $\delta_n = 1$ if and only if there exists $n=F(m)-2$ for some $m\ge 0$.
If we let $\boldsymbol{x}$ denote the characteristic sequence of Fibonacci numbers, i.e., $x_n$ equals $1$ if $n$ is a Fibonacci number, $0$ otherwise, then $\boldsymbol{\delta}=(x_n)_{n\ge 2}$ since for all $n\ge 0$
\[
\delta_n = 1
\Leftrightarrow n= F(m) - 2 \text{ for some } m\ge 0
\Leftrightarrow n +2 = F(m) \text{ for some } m\ge 0
\Leftrightarrow x_{n+2} =1.
\]
The goal is now to show that $\boldsymbol{x}$ is not $k$-automatic for any $k\ge 2$; then the non-$k$-automaticity of $\boldsymbol{\delta}$ can easily be deduced.
What follows is widely inspired by~\cite{Rigo1,Rigo2}.
In our context, we consider the ANS $(L_F,\{0,1\},<)$ where $L_F=\{\varepsilon\} \cup 1\{0,01\}^*$ is the language of Fibonacci representations of nonnegative integers with $0 < 1$.
Observe that the DFA $\mathcal{A}$ in Figure~\ref{fig:FibonacciLanguage} accepts the regular language $L_F$.
\begin{figure}
\begin{center}
\begin{tikzpicture}
\tikzstyle{every node}=[shape=circle,fill=none,draw=black,minimum size=20pt,inner sep=2pt]
\node[accepting](a) at (0,0) {$A$};
\node[accepting](b) at (2,0) {$B$};
\node[accepting](c) at (4,0) {$C$};
\node[accepting](d) at (6,0) {$D$};
\node[](e) at (8,0) {$E$};
\tikzstyle{every node}=[shape=circle,fill=none,draw=none,minimum size=10pt,inner sep=2pt]
\node(a0) at (-1,0) {};
\tikzstyle{every path}=[color =black, line width = 0.5 pt, > = triangle 45]
\tikzstyle{every node}=[shape=circle,minimum size=5pt,inner sep=2pt]
\draw [->] (a0) to [] node [] {} (a);
\draw [->] (a) to [bend left=60] node [above] {$0$} (e);
\draw [->] (a) to [] node [above] {$1$} (b);
\draw [->] (b) to [bend left=50] node [above] {$1$} (e);
\draw [->] (b) to [] node [above] {$0$} (c);
\draw [->] (c) to [loop above] node [] {$0$} (c);
\draw [->] (c) to [bend left] node [above] {$1$} (d);
\draw [->] (d) to [bend left] node [below] {$0$} (c);
\draw [->] (d) to [] node [above] {$1$} (e);
\draw [->] (e) to [loop right] node [] {$0,1$} (c);
;
\end{tikzpicture}
\caption{The DFA $\mathcal{A}$ accepting the language $\{\varepsilon\} \cup 1\{0,01\}^*$.}
\label{fig:FibonacciLanguage}
\end{center}
\end{figure}
\begin{lemma}\label{lem:Fib-automatic}
The characteristic sequence of Fibonacci numbers $\boldsymbol{x}$ is Fibonacci-automatic.
\end{lemma}
\begin{proof}
The Fibonacci-DFAO $\mathcal{B}$ in Figure~\ref{fig:FibonacciNumbers} generates the sequence $\boldsymbol{x}$ in the Zeckendorff numeration system.
In particular, this shows that $\boldsymbol{x}$ is Fibonacci-automatic.
\begin{figure}
\begin{center}
\begin{tikzpicture}
\tikzstyle{every node}=[shape=circle,fill=none,draw=black,minimum size=20pt,inner sep=2pt]
\node[](a) at (0,0) {$0_0$};
\node[](b) at (2,0) {$1$};
\node[](c) at (4,0) {$0_1$};
\tikzstyle{every node}=[shape=circle,fill=none,draw=none,minimum size=10pt,inner sep=2pt]
\node(a0) at (-1,0) {};
\tikzstyle{every path}=[color =black, line width = 0.5 pt, > = triangle 45]
\tikzstyle{every node}=[shape=circle,minimum size=5pt,inner sep=2pt]
\draw [->] (a0) to [] node [] {} (a);
\draw [->] (a) to [loop above] node [above] {$0$} (a);
\draw [->] (a) to [] node [above] {$1$} (b);
\draw [->] (b) to [loop above] node [above] {$0$} (b);
\draw [->] (b) to [] node [above] {$1$} (c);
\draw [->] (c) to [loop above] node [] {$0,1$} (c);
;
\end{tikzpicture}
\caption{The Fibonacci-DFAO $\mathcal{B}$ generating $\boldsymbol{x}$.}
\label{fig:FibonacciNumbers}
\end{center}
\end{figure}
\end{proof}
When a word is $S$-automatic for some ANS $S$, then it is in fact
morphic~\cite{Rigo2}.
\begin{theorem}\label{thm:morphic-automatic-ANS}
An infinite word $\boldsymbol{w}$ is morphic if and only if $\boldsymbol{w}$ is $S$-automatic for some ANS $S$.
\end{theorem}
From Lemma~\ref{lem:Fib-automatic} and Theorem~\ref{thm:morphic-automatic-ANS}, we easily deduce that $\boldsymbol{x}$ is morphic.
More precisely, we want to build the morphisms that generate $\boldsymbol{x}$.
We follow the constructive proof of Theorem~\ref{thm:morphic-automatic-ANS} (we refer the reader to~\cite[Chapter 2]{Rigo2} for more details).
\begin{lemma}\label{lem:Fib-morphic-1}
Let $f : \{z,a_0,a_1,\ldots,a_7\}^* \to \{z,a_0,a_1,\ldots,a_7\}^*$ be the morphism defined by $f(z)=za_0$ and
\[
\begin{array}{c|cccccccc}
i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
f(a_i) & a_1a_2 & a_1 a_4 & a_3 a_7 & a_3a_6 & a_4 a_7 & a_5 a_6 & a_5 a_7 & a_7 a_7
\end{array}.
\]
We also define the morphism $g : \{z,a_0,a_1,\ldots,a_7\}^* \to \{0,1\}^*$ by $g(z)=g(a_1)=g(a_4)=g(a_7)=\varepsilon$, $g(a_0)=g(a_5)=g(a_6)=0$ and $g(a_2)=g(a_3)=1$.
Then $\boldsymbol{x} = g( f^\omega(z) )$.
In particular, the word $\boldsymbol{x}$ is morphic.
\end{lemma}
\begin{proof}
First recall that the DFA $\mathcal{A}$ in Figure~\ref{fig:FibonacciLanguage} accepts the language $L_F=\{\varepsilon\} \cup 1\{0,01\}^*$, and the Fibonacci-DFAO $\mathcal{B}$ in Figure~\ref{fig:FibonacciNumbers} generates the sequence $\boldsymbol{x}$.
Then, the product automaton $\mathcal{P}=\mathcal{A}\times \mathcal{B}$ is drawn in Figure~\ref{fig:Product}.
\begin{figure}
\begin{center}
\begin{tikzpicture}
\tikzstyle{every node}=[shape=circle,fill=none,draw=black,minimum size=20pt,inner sep=2pt]
\node[](a) at (0,0) {$(A,0_0)$};
\node[](b) at (2.5,0) {$(B,1)$};
\node[](c) at (5,0) {$(C,1)$};
\node[](d) at (7.5,0) {$(D,0_1)$};
\node[](e) at (7.5,-2.5) {$(C,0_1)$};
\node[](f) at (5,2.5) {$(E,0_0)$};
\node[](g) at (7.5,2.5) {$(E,1)$};
\node[](h) at (10,0) {$(E,0_1)$};
\tikzstyle{every node}=[shape=circle,fill=none,draw=none,minimum size=10pt,inner sep=2pt]
\node(a0) at (-2,0) {};
\tikzstyle{every path}=[color =black, line width = 0.5 pt, > = triangle 45]
\tikzstyle{every node}=[shape=circle,minimum size=5pt,inner sep=2pt]
\draw [->] (a0) to [] node [] {} (a);
\draw [->] (a) to [] node [above] {$0$} (f);
\draw [->] (a) to [] node [above] {$1$} (b);
\draw [->] (b) to [] node [above] {$0$} (c);
\draw [->] (b) to [bend left] node [above] {$1$} (h);
\draw [->] (c) to [loop below] node [below] {$0$} (c);
\draw [->] (c) to [] node [above] {$1$} (d);
\draw [->] (d) to [] node [above] {$1$} (h);
\draw [->] (d) to [bend right] node [left] {$0$} (e);
\draw [->] (e) to [loop left] node [left] {$0$} (e);
\draw [->] (e) to [bend right] node [right] {$1$} (d);
\draw [->] (f) to [loop above] node [above] {$0$} (f);
\draw [->] (f) to [] node [above] {$1$} (g);
\draw [->] (g) to [loop above] node [above] {$0$} (g);
\draw [->] (g) to [] node [above] {$1$} (h);
\draw [->] (h) to [loop right] node [right] {$0,1$} (h);
;
\end{tikzpicture}
\caption{The DFA $\mathcal{P}$ which is the product of $\mathcal{A}$ and $\mathcal{B}$.}
\label{fig:Product}
\end{center}
\end{figure}
If we set
\begin{align*}
&a_0:=(A,0_0), a_1:=(E,0_0), a_2:=(B,1), a_3:=(C,1), \\
&a_4:=(E,1), a_5:=(C,0_1), a_6:=(D,0_1), a_7:=(E,0_1),
\end{align*}
then we can associate a morphism $\psi_\mathcal{P} : \{z,a_0,a_1,\ldots,a_7\}^* \to \{z,a_0,a_1,\ldots,a_7\}^*$ with $\mathcal{P}$ as follows.
It is defined by $\psi_\mathcal{P}(z)=za_0$ and
\[
\begin{array}{c|cccccccc}
i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\hline
\psi_\mathcal{P}(a_i) = \delta_{\mathcal{P}}(a_i,0)\delta_{\mathcal{P}}(a_i,1) & a_1a_2 & a_1 a_4 & a_3 a_7 & a_3a_6 & a_4 a_7 & a_5 a_6 & a_5 a_7 & a_7 a_7
\end{array}
\]
where $\delta_\mathcal{P}$ is the transition function of $\mathcal{P}$.
Notice that $\psi_\mathcal{P} = f$.
We also define the morphism
\[
g : \{z,a_0,a_1,\ldots,a_7\}^* \to \{0,1\}^* :
z,a_1,a_4,a_7 \mapsto\varepsilon; a_0,a_5,a_6 \mapsto 0; a_2,a_3 \mapsto 1.
\]
It is well known that $\boldsymbol{x} = g( f^\omega(z) )$, which shows that $\boldsymbol{x}$ is morphic.
\end{proof}
Observe that the morphism $g$ in Lemma~\ref{lem:Fib-morphic-1} is erasing, i.e., the image of some letter is the empty word.
In the following lemma (see~\cite[Chapter 3]{Rigo1}), we get rid of the erasure and we later obtain two new non-erasing morphisms that generate $\boldsymbol{x}$.
\begin{lemma}\label{lem:getting-rid-of-erasing-morphism}
Let $\boldsymbol{w} = g(f^\omega(a))$ be a morphic word where $g : B^* \to A^*$ is a (possibly erasing) morphism and $f : B^* \to B^*$ is a non-erasing morphism.
Let $C$ be a subalphabet of $\{b \in B \mid g(b)=\varepsilon \}$ such that $f_C$ is a submorphism of $f$.
Let $\lambda_C : B^* \to B^*$ be the morphism defined by $\lambda_C (b)=\varepsilon$ if $b\in C$, and $\lambda_C (b) = b$ otherwise.
The morphisms $f_\varepsilon := (\lambda_C \circ f) |_{ (B \setminus C)^*}$ and $g_\varepsilon := g |_{ (B \setminus C)^*}$ are such that $\boldsymbol{w} = g_\varepsilon(f_\varepsilon^\omega(a))$.
\end{lemma}
\begin{proposition}\label{pro:Fib-morphic-2}
Let $\phi:\{a,b,c,d,e\}^*\to \{a,b,c,d,e\}^*$ be the morphism defined by
\[
\phi:\{a,b,c,d,e\}^*\to \{a,b,c,d,e\}^*:
\left\{
\begin{array}{ccc}
a & \mapsto & ab, \\
b & \mapsto & c, \\
c & \mapsto & ce, \\
d & \mapsto & de, \\
e & \mapsto & d
\end{array}
\right.
\]
and let $\mu:\{a,b,c,d,e\}^*\to \{0,1\}^*: a,d,e \mapsto 0; b,c \mapsto 1$ be a coding.
Then $\boldsymbol{x} = \mu ( \phi^\omega( a ) )$.
\end{proposition}
\begin{proof}
We make use of Lemmas~\ref{lem:Fib-morphic-1} and~\ref{lem:getting-rid-of-erasing-morphism}.
First, we have
\[
\{ b \in \{z,a_0,a_1,\ldots,a_7\} \mid g(b)=\varepsilon\} = \{z,a_1,a_4,a_7\},
\]
so we choose $C=\{a_1,a_4,a_7\}$ for $f_C$ is a submorphism of $f$.
Then the morphism
\[
f_\varepsilon : \{z,a_0,a_2,a_3,a_5,a_6\}^* \to \{z,a_0,a_2,a_3,a_5,a_6\}^*
\]
is defined by $f_\varepsilon(z)=za_0$, $f_\varepsilon(a_0)=a_2$, $f_\varepsilon(a_2)=a_3$, $f_\varepsilon(a_3)=a_3 a_6$, $f_\varepsilon(a_5)=a_5 a_6$ and $f_\varepsilon(a_6)=a_5$, while the morphism $g_\varepsilon : \{z,a_0,a_2,a_3,a_5,a_6\}^* \to \{0,1\}^*$ is given by $g_\varepsilon(z)=\varepsilon$, $g_\varepsilon(a_0)=g_\varepsilon(a_5)=g_\varepsilon(a_6)=0$ and $g_\varepsilon(a_2)=g_\varepsilon(a_3)=1$.
We also have $\boldsymbol{x} = g_\varepsilon(f_\varepsilon^\omega(z))$.
Note that $f_\varepsilon|_{\{a_2,a_3,a_5,a_6\}^*}$ is a submorphism of $f_\varepsilon$.
Let us define the morphism $f'_\varepsilon : \{a_0,a_2,a_3,a_5,a_6\}^* \to \{a_0,a_2,a_3,a_5,a_6\}^* $
by $f'_\varepsilon(a_0)=a_0a_2$, and $f'_\varepsilon = f_\varepsilon|_{\{a_2,a_3,a_5,a_6\}^*}$.
From that definition, $f'_\varepsilon$ is prolongable on $a_0$.
Also consider the morphism $g'_\varepsilon : \{a_0,a_2,a_3,a_5,a_6\}^* \to \{0,1\}^*$ given by $g'_\varepsilon=g_\varepsilon|_{\{a_0,a_2,a_3,a_5,a_6\}^*}$.
We have
\begin{align*}
f_\varepsilon^\omega(z)
&= z a_0 f_\varepsilon(a_0) f_\varepsilon^2(a_0) f_\varepsilon^3(a_0) f_\varepsilon^4(a_0) \cdots \\
&= z a_0 f_\varepsilon(a_0) f_\varepsilon(f_\varepsilon(a_0)) f_\varepsilon^2(f_\varepsilon(a_0)) f_\varepsilon^3(f_\varepsilon(a_0)) \cdots \\
&= z a_0 a_2 f_\varepsilon(a_2) f_\varepsilon^2(a_2) f_\varepsilon^3(a_2) \cdots \\
&= z a_0 a_2 f'_\varepsilon(a_2) (f'_\varepsilon(a_2))^2 (f'_\varepsilon(a_2))^3 \cdots,
\end{align*}
thus we get
\begin{align*}
\boldsymbol{x}
&= g_\varepsilon( f_\varepsilon^\omega(z) ) \\
&= g_\varepsilon(z) g_\varepsilon(a_0) g_\varepsilon(a_2) g_\varepsilon(f'_\varepsilon(a_2)) g_\varepsilon((f'_\varepsilon(a_2))^2) g_\varepsilon( (f'_\varepsilon(a_2))^3 ) \cdots \\
&= \varepsilon g'_\varepsilon(a_0) g'_\varepsilon(a_2) g'_\varepsilon(f'_\varepsilon(a_2)) g'_\varepsilon((f'_\varepsilon(a_2))^2) g'_\varepsilon( (f'_\varepsilon(a_2))^3 ) \cdots \\
&= g'_\varepsilon ( a_0 a_2 f'_\varepsilon(a_2) (f'_\varepsilon(a_2))^2 (f'_\varepsilon(a_2))^3 \cdots ) \\
&= g'_\varepsilon ( (f'_\varepsilon)^\omega(a_0) ).
\end{align*}
Up to a renaming of the letters, we have proven the claim.
\end{proof}
\begin{corollary}
Let $\varphi = \frac{1}{2} ( \sqrt{5} +1 )$ be the golden ratio.
The word $\boldsymbol{x}$ is $\varphi$-substitutive.
\end{corollary}
\begin{proof}
Let
\[
M_\phi
=
\left(
\begin{array}{ccccc}
1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 & 0 \\
\end{array}
\right)
\]
be the matrix associated with the morphism $\phi$.
The Perron-Frobenius eigenvalue of $M_\phi$ is $\varphi = \frac{1}{2} ( \sqrt{5} +1 )$.
Since all the letters of $\{a,b,c,d,e\}$ occur in $\phi^{\omega}(a)$, then $\boldsymbol{x}$ is $\varphi$-substitutive by Proposition~\ref{pro:Fib-morphic-2}.
\end{proof}
\begin{proposition}\label{prop:not-k-automatic}
The sequence $\boldsymbol{x}$ is not $k$-automatic for any $k \in \mathbb{N}_{\ge 2}$.
\end{proposition}
\begin{proof}
Proceed by contradiction and suppose that there exists an integer $k \ge 2$ such that $\boldsymbol{x}$ is $k$-automatic.
Then, by Theorem~\ref{thm:Cobham-1972}, $\boldsymbol{x}$ is also $k$-substitutive.
Indeed, it is not difficult to see that the Perron-Frobenius eigenvalue of the matrix associated with a $k$-uniform morphism is the integer $k$.
Clearly, $k$ and $\varphi$ are two multiplicatively independent real numbers.
Thus, by Theorem~\ref{thm:Cobham-Durand-2011}, $\boldsymbol{x}$ is ultimately periodic.
This is impossible.
\end{proof}
\begin{corollary}\label{cor:notReg}
The sequence $(a_n)_{n\ge 0}$ is not $k$-regular for any $k \in \mathbb{N}_{\ge 2}$.
\end{corollary}
\begin{proof}
Suppose that the sequence $(a_n)_{n\ge 0}$ is $k$-regular for some $k \ge 2$.
Then by Proposition~\ref{pro:prop-aut-reg}, the sequence $(a_n \bmod{3})_{n\ge 0}$ is $k$-automatic, and so is $\boldsymbol{x}$.
This contradicts Proposition~\ref{prop:not-k-automatic}.
\end{proof}
We end this section with the following open problem.
\begin{problem}
Let us define an increasing sequence $\boldsymbol{b} = (b_n)_{n\ge 0}$ satisfying $\{b_n \mid n\in N\}=\{m\in N \mid u_m =0\}$ (sequence \texttt{A317544} in
\cite{Sloane}).
This is the characteristic sequence of $0$'s in the iPD sequence $\boldsymbol{u}$.
We have
\[
\boldsymbol{b}=
0, 2, 3, 4, 6, 8, 9, 10, 11, 12, 14, 15, 16, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, \ldots.
\]
Is the sequence $\boldsymbol{b}$ $k$-regular for some $k\ge 2$?
\end{problem}
\begin{remark}
After submission of the present paper for publication, \L{}. Merta contacted us with a different proof of Corollary~\ref{cor:notReg} that uses his work on the Baum-Sweet sequence~\cite{Merta18}.
In this note, we only sketch this other proof.
We let $\boldsymbol{bs}=(bs_n)_{n\ge 0}$ denote the Baum-Sweet sequence (indexed by \texttt{A086747} in \cite{Sloane}).
First, using Proposition~\ref{pro:pol-and-rec-u} and recurrence relations satisfied by $\boldsymbol{bs}$, one can prove that $u_{2n+1}=bs_{n+1}$ for all $n\ge 0$.
Then, if $\boldsymbol{\ell} = (\ell_n)_{n\ge 0}$ is the characteristic sequence of $1$'s in the Baum-Sweet sequence $\boldsymbol{bs}$, we deduce that $a_n = 2 \ell_{n+1}-1$ for all $n\ge 0$.
From the stability properties of $k$-regular sequences (see \cite{AS03}), if $\boldsymbol{a}$ was $k$-regular for some $k\ge 2$, then $\boldsymbol{\ell}$ would
also be, which contradicts \cite[Theorem 2.6]{Merta18}.
\end{remark}
\section{Acknowledgment}
We thank \L{}. Merta for pointing out the connection between the iPD sequence $\boldsymbol{u}$ and the Baum-Sweet sequence $\boldsymbol{bs}$, giving yet another way to prove that the characteristic sequence of $1$'s in $\boldsymbol{u}$ is not $k$-regular for any $k\ge 2$.
We also thank the anonymous referee for suggesting the simplified proof of Proposition~\ref{pro:complexity-L-a}.
\begin{thebibliography}{99}
\bibitem{AAS} G. Allouche, J.-P. Allouche and J. Shallit, Kolam indiens,
dessins sur le sable aux \^{i}les Vanuatu, courbe de Sierpi\'nski
et morphismes de mono\"{i}de, \emph{Ann. Inst. Fourier} (Grenoble)
\textbf{56} (2006), 2115--2130.
\bibitem{Aetal95} J.-P. Allouche, A. Andr\'e, J. Berstel, S. Brlek,
W. Jockusch, S. Plouffe and B. E. Sagan, A relative of the Thue-Morse
sequence, \emph{Discrete Math.} \textbf{139} (1995), 455--461.
\bibitem{AS99} J.-P. Allouche and J. Shallit, The ubiquitous
Prouhet-Thue-Morse sequence, in \emph{Sequences and Their Applications},
Springer Ser. Discrete Math. Theor. Comput. Sci., Springer,
1999, pp.~1--16.
\bibitem{AS03}
J.-P. Allouche and J. Shallit, \textit{Automatic Sequences: Theory, Applications, Generalizations}, Cambridge University Press, 2003.
\bibitem{CKMFR80} G . Christol, T. Kamae, M. Mend\`es France and G. Rauzy, Suite alg\'ebriques, automates et substitutions, \emph{Bull. Soc. Math. France} \textbf{108} (1980), 401--419.
\bibitem{Cobham72} A. Cobham, Uniform tag sequences, \emph{Math. Systems Theory} \textbf{6} (1972), 164--192.
\bibitem{Dur11} F. Durand, Cobham's theorem for substitutions, \emph{J. Eur. Math. Soc.} \textbf{13} (2011), 1799--1814.
\bibitem{Fatou} P. Fatou, S\'eries trigonom\'etriques et s\'eries de Taylor, \emph{Acta Math.} \textbf{30} (1906), 335--400.
\bibitem{GU16}
M. Gawron and M. Ulas, On formal inverse of the Prouhet-Thue-Morse sequence, \emph{Discrete Math.} \textbf{339} (2016), 1459--1470.
\bibitem{Merta18} \L{}. Merta, Composition inverses of the variations of the Baum-Sweet sequence, 2018. Preprint available at
\url{https://arxiv.org/abs/1803.00292}.
\bibitem{Merta18bis} \L{}. Merta, Formal inverses of the generalized
Thue-Morse sequences and variations of the Rudin-Shapiro sequence,
2018. Preprint available at
\url{https://arxiv.org/abs/1810.03533}.
\bibitem{Rigo1} M. Rigo, \textit{Formal Languages, Automata and Numeration
Systems. 1. Introduction to Combinatorics on Words}, Networks and
Telecommunications Series, John Wiley \& Sons,
2014.
\bibitem{Rigo2} M. Rigo, \textit{Formal Languages, Automata and Numeration
Systems. 2. Applications to Recognizability and Decidability},
Networks and Telecommunications Series, John Wiley \& Sons, 2014.
\bibitem{Schaeffer13} L. Schaeffer, Deciding Properties of Automatic
Sequences, Master's Thesis, University of Waterloo, Waterloo, Ontario,
2013.
\bibitem{Sloane} N. J. A. Sloane, \emph{The On-Line Encyclopedia of Integer Sequences}, \url{https://oeis.org}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 68R15.
\noindent \emph{Keywords: } formal inverse, period-doubling sequence, Fibonacci sequence, automatic sequence, $k$-regular sequence, Christol's theorem.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A079523},
\seqnum{A086747},
\seqnum{A096268},
\seqnum{A121539},
\seqnum{A317542},
\seqnum{A317543}, and
\seqnum{A317544}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received September 10 2018;
revised versions received December 5 2018.
Published in {\it Journal of Integer Sequences}, December 5 2018.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
**