#  ON A FAMILY OF $2$-AUTOMATIC SEQUENCES GENERATING ALGEBRAIC CONTINUED
FRACTIONS IN characteristic $2$

Yining Hu  School of Mathematics and Statistics, Huazhong University of
Science and Technology, Wuhan, PR China<EMAIL_ADDRESS>
###### Abstract.

We present family of automatic sequences that define algebraic continued
fractions in characteristic $2$. This family is constructed from ultimately
period words and contains the period-doubling sequence.

###### Key words and phrases:

algebraicity, automatic sequence, continued fraction, period-doubling sequence

###### 2010 Mathematics Subject Classification:

11B85, 11J70, 11B50, 11Y65, 05A15, 11T55

This work is supported by the National Science Foundation of China grant
12001216.

##  1\. Introduction

Ultimately periodic sequences are the simplest of all sequences. In this
article we study a family $\mathcal{S}$ of automatic sequences generated by
ultimately periodic sequences and the continued fractions defined by them.

Each sequence $\bf{s}$ in $\mathcal{S}$ is built from an ultimately periodic
sequence $(\varepsilon_{n})_{n}=p_{0}\ldots p_{l-1}(e_{0}\ldots
e_{d-1})^{\infty}$ in the following way. Starting from the empty word $W_{0}$,
we consider the sequence of words $(W_{n})_{n\geq 0}$ such that
$W_{n+1}=W_{n},\varepsilon_{n},W_{n}$ (note the comma is for concatenation and
it will be omitted when it is suitable). Hence, we have
$W_{1}=\varepsilon_{0}$,
$W_{2}=\varepsilon_{0},\varepsilon_{1},\varepsilon_{0}$, etc. Note that, for
all $n\geq 1$, $W_{n}$ is a palindrome, centred in $\varepsilon_{n}$, of
length $2^{n}-1$.

By construction, the word $W_{n+1}$ starts by $W_{n}$ and and we define
$\mathbf{s}(\boldsymbol{\varepsilon})$ to be the limit of $(W_{n})$. Hence, we
have

$\mathbf{s}(\boldsymbol{\varepsilon})=\varepsilon_{0},\varepsilon_{1},\varepsilon_{0},\varepsilon_{2},\varepsilon_{0},\varepsilon_{1},\varepsilon_{0},\varepsilon_{3},\varepsilon_{0},\varepsilon_{1},\varepsilon_{0},\varepsilon_{2},....$

We illustrate the construction of $\mathbf{s}(\boldsymbol{\varepsilon})$ with
two basic cases.

1) $\boldsymbol{\varepsilon}=a,b,(c)^{\infty}$ then

$\mathbf{s}(\boldsymbol{\varepsilon})=a,b,a,c,a,b,a,c,....=(a,b,a,c)^{\infty}.$

Here $\boldsymbol{\varepsilon}$ is ultimately constant and
$\mathbf{s}(\boldsymbol{\varepsilon})$ is periodic. Consequently a basic
property on continued fractions shows that
$\operatorname{CF}(\mathbf{s}(\boldsymbol{\varepsilon}))$ is quadratic over
$\mathbb{F}_{2}(t)$.

2) $\boldsymbol{\varepsilon}=(a,b)^{\infty}$ then

$\mathbf{s}(\boldsymbol{\varepsilon})=a,b,a,a,a,b,a,b,a,b,...$

Here $\mathbf{s}(\boldsymbol{\varepsilon})$ is the celebrated period-doubling
sequence. It has been proved that
$\operatorname{CF}(s(\boldsymbol{\varepsilon}))$ satisfies an algebraic
equation of degree $4$ (see [7, 8]).

Each sequence in $\mathcal{S}$ is $2$-automatic. The definition and relevant
results about automatic sequences are briefly recalled in Section 1.3.

Continued fractions defined by two classical example of automatic sequences in
characteristic $2$ were studied in [7, 5, 8], where it was established that
the Thue-Morse and period-doubling sequences both define algebraic continued
fractions of degree $4$. On the other hand, both sequences define quadratic
formal power series. The situation is different from the real case: Bugeaud
[4] proved in 2013 that the continued fraction expansion of an algebraic real
number of degree at least $3$ is not automatic.

Our family $\mathcal{S}$ is a natural generalization of the period-doubling
sequence. We prove in this article that every sequence from this family
defines an algebraic continued fraction in characteristic $2$.

In Section 1.1 we give the notation necessary for stating our main result in
1.2. In Section 2 we prove the main theorem, and in Section 3 we give three
examples. Finally, in Section 4 we make a comment on the link between
continued fractions and Riccati differential equations.

###  1.1. Continued Fractions in Power Series Rings

Let $A=\\{a_{0},\ldots,a_{k}\\}$ be a finite alphabet. We treat $a_{j}$ as
formal variables and define

$\displaystyle\mathbb{F}_{2}[A]:=\mathbb{F}_{2}[a_{0},\ldots,a_{k}]$
$\displaystyle\mathbb{F}_{2}(A):=\mathbb{F}_{2}(a_{0},\ldots,a_{k})$
$\displaystyle\mathbb{F}_{2}((A)):=\mathbb{F}_{2}((\frac{1}{a_{0}},\ldots,\frac{1}{a_{k}})).$

Here $\mathbb{F}_{2}((\frac{1}{a_{0}},\ldots,\frac{1}{a_{k}}))$ denotes the
ring of power series of the form

(1.1) $\sum_{n_{0},\ldots,n_{k}\geq
N}c_{n_{0},n_{1},\ldots,n_{k}}a_{0}^{-n_{0}}\cdots{a_{k}}^{-n_{k}},$

where $N$ is an integer and $c_{n_{0},n_{1},\ldots,n_{k}}\in\mathbb{F}_{2}$.

Let $(u_{n})_{n\geq 0}$ be a sequence taking values in $A$. It defines a
formal power series $\sum_{n\geq 0}u_{n}z^{n}$ in $\mathbb{F}_{2}[A][[z]]$.

We define a norm on $\mathbb{F}_{2}((A))$ by assigning a series of the form
(1.1) the number $2^{-m}$, where $m=\min\\{n_{0}+n_{1}\cdots+n_{k}\mid\
c_{n_{0},n_{1},\ldots,n_{k}}\neq 0\\}$ with the convention that
$\min\emptyset=\infty$. This norm makes $\mathbb{F}_{2}((A))$ an ultrametric
space.

The continued fraction $\operatorname{CF}(\mathbf{u})=[u_{0},u_{1},\ldots]$ is
defined as the limit of the sequence $([u_{0},u_{1},\ldots,u_{n}])_{n}$:

$\displaystyle[u_{0}]$ $\displaystyle=u_{0},$
$\displaystyle[u_{0},u_{1},\ldots,u_{n}]$
$\displaystyle=u_{0}+\frac{1}{[u_{1},\ldots,u_{n}]}\in\mathbb{F}_{2}((A)),$

for $n\geq 1$. For example,

$\displaystyle[u_{0},u_{1},u_{2}]$
$\displaystyle=u_{0}+\cfrac{1}{u_{1}+\frac{1}{u_{2}}}$
$\displaystyle=u_{0}+\frac{u_{1}^{-1}}{1+(u_{1}u_{2})^{-1}}$
$\displaystyle=u_{0}+u_{1}^{-1}+u_{1}^{-2}u_{2}^{-1}+u_{1}^{-3}u_{2}^{-2}+\cdots$

The convergence of this sequence is proved in the same way as in the case of
classical contineud fraction for real numbers.

We may also choose to specialize the letters in $A$ to non-constant
polynomials in $\mathbb{F}_{2}[z]$ (this gives a continuous map from
$\mathbb{F}_{2}((A))$ to $\mathbb{F}_{2}((1/z))$), and then
$\operatorname{CF}({\mathbf{u}})$ can be seen as formal power series in
$\mathbb{F}_{2}((1/z))$. For basic information on continued fractions,
particularly in power series rings, the reader is refered to [9].

###  1.2. Main result

We prove the following theorem.

######  Theorem 1.1.

Let $\boldsymbol{\varepsilon}=p_{0}\ldots p_{l-1}(e_{0}\ldots
e_{d-1})^{\infty}$ be an ultimately periodic sequence over the alphabet $A$.

(i) The continued fraction
$\operatorname{CF}(\operatorname{\mathbf{s}(\boldsymbol{\varepsilon})})$ is
algebraic of degree at most $2^{d}$ over $\mathbb{F}_{2}(A)$. It is of degree
$2^{d}$ if $e_{0}$ is different from the other letters.

(ii) The formal power series

$F:=\sum_{j\geq 0}s_{j}z^{j}\in\mathbb{F}_{2}(A)[[z]].$

is algebraic of degree at most $2^{d-1}$ over $\mathbb{F}_{2}(A)(z)$. It is of
degree $2^{d-1}$ if $e_{0}$ is different from the other letters.

######  Remark 1.

For the formal power series in in Theorem 1.1 and in the examples, we chose to
keep the letters of an automatic sequence as formal variables instead of
mapping them to elements in $\mathbb{F}_{p}$, because in the latter case, the
formal power series and consequently its minimal polynomial depend on the
mapping. For an automatic sequence $\bf{u}$ taking values
$a_{1},\ldots,a_{k}$, it is always possible treat the letters as formal
variables and get a minimal polynomial in
$\mathbb{F}_{p}[a_{1},\ldots,a_{k},x][y]$. This is because $F$ can be
decomposed into a finite sum $\sum a_{n}F_{n}$, where each $F_{n}$ is
algebraic over $\mathbb{F}_{p}(x)$. Therefore each $a_{n}F_{n}$ is algebraic
over $\mathbb{F}_{p}(a_{1},\ldots,a_{k})(x)$ and so is $F$.

###  1.3. Automatic sequences and algebraicity

Here we recall briefly the definition and properties of automatic sequences.
We refer the readers to [2] for a comprehensive exposition on the subject. A
sequence $(u_{n})_{n}$ is said to be $k$-automatic if it can be generated by a
finite $k$-automaton. In this article we will use an equivalent definition.
The $k$-kernel of a sequence $(u_{n})_{n}$ is defined as the smallest set
containing $(u_{n})_{n}$ and stable under the operations
$(v_{n})_{n}\mapsto(v_{kn+r})_{n}$ for $r=0,1,\ldots,k-1$. The sequence
$\bf{u}$ is said to be $k$-automatic if its $k$-kernel is finite.

The well-known Theorem of Christol, Kamae, Mendès France and Rauzy [6] states
that a formal power series in $\mathbb{F}_{p}[[x]]$ is algebraic over
$\mathbb{F}_{p}(x)$ if and only if the sequence of its coefficients is
$p$-automatic. This theorem is generalized by Salon [10] to multivariate
cases: We define the $k$-kernel of a multi-dimensional sequence
$\mathbf{u}=(u_{n_{1},\ldots,n_{d}})_{n_{1},\ldots,n_{d}}$ to be the smallest
set containing $\bf{u}$ and stable under the operations

$(v_{n_{1},\ldots,n_{d}})_{n_{1},\ldots,n_{d}}\mapsto(v_{k\cdot
n_{1}+r_{1},\ldots,k\cdot n_{d}+r_{d}})_{n_{1},\ldots,n_{d}}$

for $0\leq r_{1},\ldots,r_{d}<k$. The sequence $\bf{u}$ is said to be
$k$-automatic if its $k$-kernel is finite. When $\bf{u}$ takes values in
$\mathbb{F}_{p}$, then the formal power series $\sum
u_{n_{1},\ldots,n_{d}}x_{1}^{n_{1}}\cdot x_{d}^{n_{d}}$ is algebraic over
$\mathbb{F}_{p}(x_{1},\ldots,x_{d})$ if and only if $\bf{u}$ is $k$-automatic.

For $r=0,1,\ldots,p-1$, the Cartier operators $\Lambda_{r}$ are defined as

$\displaystyle\Lambda_{r}:\mathbb{F}_{p}[[x]]$
$\displaystyle\rightarrow\mathbb{F}_{p}[[x]]$
$\displaystyle\sum_{n=0}^{\infty}u_{n}x^{n}$
$\displaystyle\mapsto\sum_{n=0}^{\infty}u_{pn+r}x^{n}.$

Thus for $f\in\mathbb{F}_{p}[[x]]$, we have

$f=\sum_{r=0}^{p-1}x^{r}(\Lambda_{r}f)^{p}.$

In the multivariate case, the Cartier operators are

$\displaystyle\Lambda_{r_{1},\ldots,r_{d}}:\mathbb{F}_{p}[[x_{1},\ldots,x_{d}]]$
$\displaystyle\rightarrow\mathbb{F}_{p}[[x_{1},\ldots,x_{d}]]$
$\displaystyle\sum u_{n_{1},\ldots,n_{d}}x_{1}^{n_{1}}\cdots x_{d}^{n_{d}}$
$\displaystyle\mapsto\sum
u_{pn_{1}+r_{1},\ldots,pn_{d}+r_{d}}x_{1}^{n_{1}}\cdots x_{d}^{n_{d}}.$

For $f\in\mathbb{F}_{p}[[x_{1},\ldots,x_{d}]]$, we have

$f=\sum_{r_{1},\ldots,r_{d}=0}^{p-1}x_{1}^{r_{1}}\cdots
x_{d}^{r_{d}}(\Lambda_{r_{1},\ldots,r_{d}}f)^{p}.$

The following lemma will be used in the proof of theorem 1.1:

######  Lemma 1.2.

Let $\mathbf{u}=(u_{n_{1},\ldots,n_{d}})_{n_{1},\ldots,n_{d}}$ be a
$p$-automatic sequence taking value in $\mathbb{F}_{p}$. Let $\bf{v}$ be an
element from the $p$-kernel of $\bf{u}$, then the degree of algebraicity of
$\sum v_{n_{1},\ldots,n_{d}}x_{1}^{n_{1}}\cdot x_{d}^{n_{d}}$ is less than or
equal to that of $\sum u_{n_{1},\ldots,n_{d}}x_{1}^{n_{1}}\cdot
x_{d}^{n_{d}}$.

###### Proof.

Let $f=\sum u_{n_{1},\ldots,n_{d}}x_{1}^{n_{1}}\cdot x_{d}^{n_{d}}$. We only
need to prove that for all $(r_{1},\ldots,r_{d})\in\\{0,1,\ldots,p-1\\}^{d}$,
for $\Lambda:=\Lambda_{r_{1},\ldots,r_{d}}$, the degree of algebraicity of
$\Lambda f$ is less than or equal to that of $f$. From the proof of Christol’s
theorem we know that there exists $n\geq 0$ and $a_{1},a_{2},\ldots
a_{n}\in\mathbb{F}_{p}(x_{1},\ldots,x_{d})$ such that

$f=a_{1}f^{p^{1}}+a_{2}f^{p^{2}}+\cdots+a_{n}f^{p^{n}}.$

We make use of the following property of $\Lambda$: for two power series $g$
and $h$, we have

$\Lambda(g\cdot h^{p})=\Lambda(g)\cdot h,$

and

$\Lambda\frac{g}{h}=\Lambda\frac{g\cdot h^{p-1}}{h^{p}}=\frac{\Lambda{(g\cdot
h^{p-1}})}{h}.$

Therefore

$\Lambda
f=\Lambda(a_{1})f+\Lambda(a_{2})f^{p}+\cdots+\Lambda(a_{n})f^{p^{n-1}}\in\mathbb{F}_{p}(x_{1},\ldots,x_{d})[f].$

We conclude that the degree of $\Lambda f$ is less than or equal to that of
$f$. ∎

##  2\. Proof of Theorem 1.1

To prove of the first part of theorem 1.1, we consider the truncation
$[s_{0},...,s_{2^{n}-2}]$ of the continued fraction
$\operatorname{CF}(\operatorname{\mathbf{s}(\boldsymbol{\varepsilon})})$ for
$n\geq 1$. This corresponds to the palindrome $W_{n}$. For $n\geq 1$, we set
$u_{n}/v_{n}=[s_{0},...,s_{2^{n}-2}]$. We have $(u_{1},v_{1})=(s_{0},1)$ and
$(u_{2},v_{2})=(s_{0}s_{1}s_{2}+s_{0}+s_{2},s_{1}s_{2}+1)$, etc. The first
step of the proof was introduced in the author’s previous work with Lasjaunias
concerning the particular case of the period-doubling sequence. In Lemma 3.2
from [8], using basic properties of continuants, we proved that the pair
$(u_{n},v_{n})$ satisfies a simple recurrence relation. Indeed, for $n\geq 1$,
we have

(R) $u_{n+1}=\varepsilon_{n}u_{n}^{2}\mbox{ and
}v_{n+1}=\varepsilon_{n}u_{n}v_{n}+1.$

From (R) we get immediately

$\frac{v_{n+1}}{u_{n+1}}=\frac{v_{n}}{u_{n}}+\frac{1}{u_{n}}$

and therefore we obtain

$\frac{v_{n}}{u_{n}}=\sum_{1\leq k\leq n}\frac{1}{u_{k}}$

for $n\geq 1$. Consequently

($\star$)
$\frac{1}{\operatorname{CF}({\mathbf{s(\boldsymbol{\varepsilon})}})}=\lim_{n\rightarrow\infty}\frac{v_{n}}{u_{n}}=\sum_{n\geq
1}\frac{1}{u_{n}}.$

It is easier to work with the following series which differs by a rational
fractional from
$1/\operatorname{CF}(\operatorname{\mathbf{s}(\boldsymbol{\varepsilon})})$:

$G:=\sum_{n>l}\frac{1}{u_{n}}.$

By regrouping every $d$ terms and using (R), we decompose $G$ as follows

(2.1) $G=\sum_{n=0}^{d-1}\frac{G_{n}^{2}}{e_{n}},$

where

$G_{n}=\sum_{k=0}^{\infty}\frac{1}{u_{l+n+kd}}$

for $n=0,1,\ldots,d-1$. It follows from their definition and (R) that
$\\{G_{n}\\}$ satisfy the following relations

(2.2) $G_{0}=\frac{1}{u_{l}}+\frac{G_{d-1}^{2}}{e_{d-1}}$

and

(2.3) $G_{n}=\frac{G_{n-1}^{2}}{e_{n-1}}$

for $n=1,2,\ldots,d-1$, with the convention $u_{0}=1$, from which we deduce

(2.4) $G_{0}=\frac{1}{u_{l}}+\frac{G_{0}^{2^{d}}}{e_{d-1}e_{d-2}^{2}\cdots
e_{0}^{2^{d-1}}}.$

Using (2.1), (2.3) and (2.4), we can express $G$ in terms of $G_{0}$

$G=\frac{1}{u_{l}}+G_{0}+\frac{G_{0}^{2}}{e_{0}}+\frac{G_{0}^{4}}{e_{0}^{2}e_{1}}+\cdots+\frac{G_{0}^{2^{d-1}}}{e_{0}^{2^{d-2}}e_{1}^{2^{d-3}}\cdots
e_{d-2}}.$

This means that the degree algebraicity of $G$ (and that of
$\operatorname{CF}(\operatorname{\mathbf{s}(\boldsymbol{\varepsilon})})$) is
at most that of $G_{0}$. This proves that the degree of algebraicity of
$\operatorname{CF}(\operatorname{\mathbf{s}(\boldsymbol{\varepsilon})})$ is at
most $2^{d}$.

When $e_{0}$ is different from all other letters, $G_{0}$ is in the $2$-kernel
of $G$, so that by lemma 1.2, the degree of $G$ is at least that of $G_{0}$.
To show that degree of algebraicity of $G_{0}$ is at least $2^{d}$, consider
the series

$g=\sum_{k=0}^{\infty}\frac{1}{e_{0}^{2^{k\cdot d}}}$

that satisfies

$e_{0}\cdot g^{2^{d}}+e_{0}\cdot g+1=0.$

This is an irreducible polynomial by Eisenstein’s criterion. If we project all
the letters in $G_{0}$ to $e_{0}$, then we get the series
$e_{0}\cdot\sum_{k=l}^{\infty}\frac{1}{e_{0}^{2^{k\cdot d}}}$, which has the
same degree of algebraicity as $g$. Since projection cannot increase degree,
we conclude that in this case, the degree of algebraicity of $G_{0}$, and
therefore that of
$\operatorname{CF}(\operatorname{\mathbf{s}(\boldsymbol{\varepsilon})})$ is
$2^{d}$.

To prove the second part of the theorem, we need the following lemma

######  Lemma 2.1.

Suppose that the letters $e_{j}\;(0\leq j<d)$ are all distinct and that they
are different from the letters $p_{j}\;(0\leq j<l)$. For $j=0,1,\ldots,d-1$,
define

$P_{j}:=\\{k\mid s_{k}=e_{j}\\}.$

Then

(2.5) $P_{j+1}=\\{2k+1\mid k\in P_{j}\\}\quad\mbox{ for }j=0,1,\ldots,d-2$

and

(2.6) $P_{0}=\\{2k+1\mid k\in P_{d-1}\\}\cup\\{(2k+1)\cdot 2^{l}-1\mid
k=1,2,\ldots\\}.$

###### Proof.

To simplify notation, we write $e_{n}$ instead of $e_{n\pmod{d}}$ when $n\geq
d$. By definition, $\operatorname{\mathbf{s}(\boldsymbol{\varepsilon})}$ can
be written in two ways:

(2.7)
$W_{l}e_{0}W_{l}e_{1}W_{l}e_{0}W_{l}e_{2}W_{l}e_{0}W_{l}e_{1}W_{l}e_{0}W_{l}\ldots$

and

(2.8)
$W_{l+1}e_{1}W_{l+1}e_{2}W_{l+1}e_{1}W_{l+1}e_{3}W_{l+1}e_{1}W_{l+1}e_{2}W_{l+1}e_{1}W_{l+1}\ldots$

Letter $e_{0}$ appears at the same places in (2.7) as $e_{1}$ in (2.8), except
that the length of the block $W_{l}$ is $2^{l}-1$, while that of $W_{l+1}$ is
$2^{l+1}-1$. By the assumption on $(e_{j})$ and $(p_{j})$, the letter $e_{j}$
does not appear in $W_{l+j}$ $(0\leq j<d)$. The above observation allows us to
conclude that

$P_{1}=\\{2k+1\mid k\in P_{0}\\}.$

Similar argument shows that

$P_{j+1}=\\{2k+1\mid k\in P_{j}\\}\quad\mbox{ for }j=1,\ldots,d-2.$

To prove (2.6), we also write
$\operatorname{\mathbf{s}(\boldsymbol{\varepsilon})}$ in two ways:

(2.9)
$W_{l+d-1}e_{d-1}W_{l+d-1}e_{0}W_{l+d-1}e_{d-1}W_{l+d-1}e_{1}W_{l+d-1}e_{d-1}W_{l+d-1}e_{0}\ldots$

and

(2.10)
$W_{l+d}e_{0}W_{l+d}e_{1}W_{l+d}e_{0}W_{l+d}e_{2}W_{l+d}e_{0}W_{l+d}e_{1}W_{l+d}e_{0}W_{l+d}\ldots$

As with previous cases, the letter $e_{0}$ appears at the same places in
(2.10) as $e_{d-1}$ in (2.9), except that the length of the block $W_{l+d}$ is
$2^{l+d}-1$, while that of $W_{l+d-1}$ is $2^{l+d-1}-1$. Unlike previous
cases, the letter $e_{0}$ also occurs in $W_{l+d}$ at indices $(2k+1)\cdot
2^{l}-1$ for $k=1,2,\ldots$ That’s how we get the additional term in (2.6). ∎

We consider another sequence
$\boldsymbol{\varepsilon}^{\prime}=p_{0}^{\prime}\ldots
p_{l-1}^{\prime}(e_{0}^{\prime}\ldots e_{d-1}^{\prime})^{\infty}$. where the
letters $p_{j}^{\prime}$ $(0\leq j<l)$ and $e_{j}^{\prime}$ $(0\leq j<d)$ are
all distinct, so that we can apply lemma 2.1 to obtain the sets $P_{j}$ for
$j=0,1,\ldots,d-1$ corresponding to the sequence
$\mathbf{s}(\boldsymbol{\varepsilon}^{\prime})$.

We decompose the series $F$ as follows

(2.11) $F=R+e_{0}F_{0}+\cdots+e_{d-1}F_{d-1},$

where

$R=\frac{\sum_{k=0}^{2^{l}-2}s_{k}z^{k}}{1+z^{2^{l}}}$

is a rational function which accounts for the preperiodic part of
$\boldsymbol{\varepsilon}$ and

$F_{n}=\sum_{j\in P_{n}}z^{j}$

for $n=0,1,\ldots,d-1$.

From lemma 2.1 we deduce the relations

(2.12) $F_{n}=zF_{n-1}^{2}$

for $n=1,\ldots,d-1$. On the other hand, since the supports of $R$ and
$F_{0},\ldots,F_{d-1}$ form a partition of $\mathbb{N}$, we have

(2.13)
$F_{0}=\frac{1}{1+z}-\frac{\sum_{k=0}^{2^{l}-2}z^{k}}{1+z^{2^{l}}}-\sum_{n=1}^{d-1}F_{n}=\frac{z^{2^{l}-1}}{1+z^{2^{l}}}-\sum_{n=1}^{d-1}F_{n}.$

From (2.12) and (2.13) we deduce

(2.14)
$F_{0}=\frac{z^{2^{l}-1}}{1+z^{2^{l}}}-\sum_{n=1}^{d-1}z^{2^{n}-1}F_{0}^{2^{n}}.$

Using (2.11) and (2.12) we can express $F$ using $F_{1}$

(2.15) $F=R+\sum_{n=0}^{d-1}e_{n}z^{2^{n}-1}F_{0}^{2^{n}}.$

This shows that the degree of $F$ is at most that of $F_{0}$.

The degree of $F_{0}$ is $2^{d-1}$: if $l$ were $0$, in place of $F_{0}$, by
2.11, we would have a series $f$ that satisfies

$f=\frac{1}{1+z}-\sum_{n=1}^{d-1}z^{2^{n}-1}f^{2^{n}}.$

Therefore the series $h:=zf$ satisfy

$(1+z)\cdot\sum_{n=0}^{d-1}h^{2^{n}}+z=0,$

which is an irreducible polynomial in $h$ by Eisenstein’s criterion.

The support of $f$ is the positions of $e_{0}$ in

$\mathbf{s}((e_{0}e_{1}\ldots
e_{d-1})^{\infty})=W_{0}e_{0}W_{0}e_{1}W_{0}e_{0}W_{0}e_{2}W_{0}e_{0}W_{0}e_{1}W_{0}e_{0}W_{0}\ldots$

Comparing the above expression with (2.7) we obtain

$F_{0}=z^{2^{l}-1}f^{2^{l}}.$

Therefore $f$ is in the $2$-kernel of $F_{0}$. By lemma 1.2 the degree of
$F_{0}$ is at least that of $f$.

When $e_{0}$ is different from the other letters, we can obtain $F_{0}$ from
$F$ mapping $e_{0}$ to $1$ and the other letters to $0$. This show that in
this case the degree of $F$ is at least that of $F_{0}$.

##  3\. Examples

######  Example 1.

Let $\boldsymbol{\varepsilon}=(ab)^{\infty}$. Then
$\bf{s(\boldsymbol{\varepsilon})}$ is the period-doubling sequence. We have

$\displaystyle\frac{1}{\operatorname{CF}(\mathbf{s})}=G$
$\displaystyle=\frac{1}{a}+\frac{1}{a^{2}b}+\frac{1}{a^{4}b^{2}a}+\frac{1}{a^{8}b^{4}a^{2}b}+\frac{1}{a^{16}b^{8}a^{4}b^{2}a}\cdots$
$\displaystyle=\frac{G_{0}^{2}}{a}+\frac{G_{1}^{2}}{b},$

with

$\displaystyle G_{0}$
$\displaystyle=1+\frac{1}{a^{2}b}+\frac{1}{a^{8}b^{4}a^{2}b}+\cdots$
$\displaystyle G_{1}$
$\displaystyle=\frac{1}{a}+\frac{1}{a^{4}b^{2}a}+\frac{1}{a^{16}b^{8}a^{4}b^{2}a}\cdots.$

The series $G_{0}$ and $\operatorname{CF}(\mathbf{s})$ satisfy

$G_{0}=1+\frac{G_{0}^{4}}{a^{2}b},$

and

$\frac{1}{\operatorname{CF}(\mathbf{s})}=G=1+G_{0}+\frac{G_{0}^{2}}{a}.$

We get as expected (see [8])

$(ab+b^{2}+1)+(a^{2}b+ab^{2})\cdot G+ab\cdot G^{2}+G^{4}=0$

The formal power series defined by $\bf{s(\boldsymbol{\varepsilon})}$ is

$F=a+bz+az^{2}+az^{3}+az^{4}+bz^{5}+az^{6}+\cdots=aF_{0}+bF_{1}.$

The series $F_{0}$ and $F$ satisfy

$F_{0}=\frac{1}{1+z}-zF_{0}^{2},$ $F=aF_{0}+bzF_{0}^{2}.$

We deduce

$(z^{3}+z)\cdot F^{2}+(az^{2}+bz^{2}+a+b)\cdot
F+(a^{2}z+abz+b^{2}z+a^{2}+ab)=0.$

######  Remark 2.

Here we have a simple example of an algebraic formal power series whose
continued fraction has unbounded partial quotients. If we let $a=b=x$ in
$G_{0}$, we get a series

$g=1+\frac{1}{x}+\frac{1}{x^{5}}+\frac{1}{x^{21}}+\cdots,$

which satisfies the algebraic equation

$\frac{g^{4}}{x}+g+1=0.$

It can be shown that

$g=[1,x,x^{3},x,x^{11},x,x^{3},x,x^{43},\ldots]=[1,x^{c_{0}},x^{c_{1}},x^{c_{2}},\ldots],$

where $c_{2n}=1$ and $c_{2n+1}=4c_{n}-1$ for all $n\geq 0$. The exponents of
partial quotients are not bounded, but they form nontheless a $2$-regular
sequence (see [1]).

######  Example 2.

Let $\boldsymbol{\varepsilon}=a(bc)^{\infty}$. Then
$\mathbf{s(\boldsymbol{\varepsilon})}=abacabababacabacabac\cdots$ We have

$\frac{1}{\operatorname{CF}(\mathbf{s})}=\frac{1}{a}+G,$

where

$\displaystyle G$
$\displaystyle=\frac{1}{a^{2}b}+\frac{1}{a^{4}b^{2}c}+\frac{1}{a^{8}b^{4}c^{2}b}+\frac{1}{a^{16}b^{8}c^{4}b^{2}c}+\frac{1}{a^{32}b^{16}c^{8}b^{4}c^{2}b}+\cdots$
$\displaystyle=\frac{G_{0}^{2}}{b}+\frac{G_{1}^{2}}{c},$

with

$\displaystyle G_{0}$
$\displaystyle=\frac{1}{a}+\frac{1}{a^{4}b^{2}c}+\frac{1}{a^{16}b^{8}c^{4}b^{2}c}+\cdots$
$\displaystyle G_{1}$
$\displaystyle=\frac{1}{a^{2}b}+\frac{1}{a^{8}b^{4}c^{2}b}+\frac{1}{a^{32}b^{16}c^{8}b^{4}c^{2}b}+\cdots$

The series $G_{0}$, and
$\operatorname{CF}(\mathbf{s(\boldsymbol{\varepsilon})})$ satisfy

(3.1) $\displaystyle G_{0}$
$\displaystyle=\frac{1}{a}+\frac{G_{0}^{4}}{b^{2}c},$ (3.2)
$\displaystyle\frac{1}{\operatorname{CF}(\mathbf{s(\boldsymbol{\varepsilon})})}$
$\displaystyle=G_{0}+\frac{G_{0}^{2}}{b}.$

We deduce from (3.1) and (3.2) that the minimal polynomial of
$\operatorname{CF}(\mathbf{s})$ is

(3.3)
$(ab^{2}c+abc^{2}+c^{2})x^{4}+(a^{2}b^{2}c+a^{2}bc^{2})x^{3}+a^{2}bcx^{2}+a^{2}.$

The formal power series defined by $\bf{s(\boldsymbol{\varepsilon})}$ is

$\displaystyle F$
$\displaystyle=a+bz+az^{2}+cz^{3}+az^{4}+bz^{5}+az^{6}+bz^{7}+az^{8}+bz^{9}+az^{10}+\cdots$
$\displaystyle=\frac{a}{1+z^{2}}+bF_{0}+cF_{1}.$

The series $F_{0}$ and $F$ satisfy

$F_{0}=\frac{z}{1+z^{2}}-zF_{0}^{2},$
$F=\frac{a}{1+z^{2}}+bF_{0}+czF_{0}^{2}.$

From these we deduce that the minimal polynomial for $F$ is

$Ax^{2}+Bx+C=0,$

where

$\displaystyle A$ $\displaystyle=z^{5}+z,$ $\displaystyle B$
$\displaystyle=bz^{4}+cz^{4}+b+c,$ $\displaystyle C$
$\displaystyle=b^{2}z^{3}+bcz^{3}+c^{2}z^{3}+abz^{2}+acz^{2}+a^{2}z+b^{2}z+bcz+ab+ac.$

######  Example 3.

Let $\boldsymbol{\varepsilon}=(aabb)^{\infty}$. Then
$\mathbf{s(\boldsymbol{\varepsilon})}=aaabaaabaaabaaaaaaab\ldots$. We have

$\frac{1}{\operatorname{CF}(\mathbf{s(\boldsymbol{\varepsilon})})}=G=\frac{1}{a}+\frac{1}{a^{2}a}+\frac{1}{a^{4}a^{2}b}+\frac{1}{a^{8}a^{4}b^{2}b}+\frac{1}{a^{16}a^{8}b^{4}b^{2}a}+\frac{1}{a^{32}a^{16}b^{8}b^{4}a^{2}a}+\cdots$

and

$G=\frac{G_{0}^{2}}{a}+\frac{G_{1}^{2}}{a}+\frac{G_{2}^{2}}{b}+\frac{G_{3}^{2}}{b}.$

with

$\displaystyle G_{0}$ $\displaystyle=1+\frac{1}{a^{8}a^{4}b^{2}b}+\cdots$
$\displaystyle G_{1}$
$\displaystyle=\frac{1}{a}+\frac{1}{a^{16}a^{8}b^{4}b^{2}a}+\cdots$
$\displaystyle G_{2}$
$\displaystyle=\frac{1}{a^{2}a}+\frac{1}{a^{32}a^{16}b^{8}b^{4}a^{2}a}\cdots$
$\displaystyle G_{3}$
$\displaystyle=\frac{1}{a^{4}a^{2}b}+\frac{1}{a^{64}a^{32}b^{16}b^{8}a^{4}a^{2}b}\cdots$

The series $G$ and $G_{0}$ satisfy

$\displaystyle G_{0}$ $\displaystyle=1+\frac{G_{0}^{16}}{a^{12}b^{3}}$
$\displaystyle G$
$\displaystyle=1+G_{0}+\frac{G_{0}^{2}}{a}+\frac{G_{0}^{4}}{a^{3}}+\frac{G_{0}^{8}}{a^{6}b}.$

We deduce

$G^{16}+c_{8}G^{8}+c_{2}G^{2}+c_{1}G+c_{0}=0.$

where

$\displaystyle c_{0}$
$\displaystyle=a^{11}b^{3}+a^{10}b^{4}+a^{3}b^{11}+a^{2}b^{12}+a^{6}b^{6}+a^{4}b^{8}+a^{2}b^{10}+b^{12}+a^{6}b^{2}+$
$\displaystyle\quad a^{4}b^{4}+a^{2}b^{6}+b^{8}+1,$ $\displaystyle c_{1}$
$\displaystyle=a^{12}b^{3}+a^{11}b^{4}+a^{4}b^{11}+a^{3}b^{12},$
$\displaystyle c_{2}$
$\displaystyle=a^{11}b^{3}+a^{10}b^{4}+a^{8}b^{6}+a^{6}b^{8}+a^{4}b^{10}+a^{3}b^{11},$
$\displaystyle c_{8}$ $\displaystyle=a^{6}b^{2}+a^{4}b^{4}+a^{2}b^{6},$

This polynomial is irreducible.

The formal power series defined by $\mathbf{s(\boldsymbol{\varepsilon})}$ is

$\displaystyle F$ $\displaystyle=a(F_{0}+F_{1})+a(F_{2}+F_{3}),$

where

$\displaystyle F_{0}$
$\displaystyle=1+z^{2}+z^{4}+z^{6}+z^{8}+z^{10}+z^{12}+z^{14}+z^{15}+z^{16}+z^{18}+\cdots$
$\displaystyle F_{1}$
$\displaystyle=z+z^{5}+z^{9}+z^{13}+z^{17}+z^{21}+z^{25}+z^{29}+z^{31}+z^{33}+z^{37}+\cdots$
$\displaystyle F_{2}$
$\displaystyle=z^{3}+z^{11}+z^{19}+z^{27}+z^{35}+z^{43}+z^{51}+z^{59}+z^{63}+z^{67}+\cdots$
$\displaystyle F_{3}$
$\displaystyle=z^{7}+z^{23}+z^{39}+z^{55}+z^{71}+z^{87}+z^{103}+z^{119}+z^{127}+z^{135}+\cdots$

The series $F_{0}$ and $F$ satisfy

(3.4) $\displaystyle F_{0}$
$\displaystyle=\frac{1}{1+z}+zF_{0}^{2}+z^{3}F_{0}^{4}+z^{7}F_{0}^{8},$ (3.5)
$\displaystyle F$
$\displaystyle=aF_{0}+azF_{0}^{2}+bz^{3}F_{0}^{4}+bz^{7}F_{0}^{8}.$

Here $F$ is not of degree $8$, but $4$, because we can write (3.4) and (3.5)
as

(3.6) $\frac{1}{1+z}+(F_{0}+zF_{0}^{2})+z^{3}(F_{0}+zF_{0}^{2})^{4}=0$ (3.7)
$F=a(F_{0}+zF_{0}^{2})+bz^{3}(F_{0}+zF_{0}^{2})^{4}.$

From (3.6) and (3.7) we find minimal polynomial of $F$ to be

$c_{4}x^{4}+c_{1}x+c_{0}=0,$

where

$\displaystyle c_{0}$
$\displaystyle=a^{4}z^{3}+a^{3}bz^{3}+a^{2}b^{2}z^{3}+ab^{3}z^{3}+b^{4}z^{3}+a^{4}z^{2}+a^{3}bz^{2}+a^{2}b^{2}z^{2}+$
$\displaystyle\quad
ab^{3}z^{2}+a^{4}z+a^{3}bz+a^{2}b^{2}z+ab^{3}z+a^{4}+a^{3}b+a^{2}b^{2}+ab^{3}$
$\displaystyle c_{1}$
$\displaystyle=a^{3}z^{4}+a^{2}bz^{4}+ab^{2}z^{4}+b^{3}z^{4}+a^{3}+a^{2}b+ab^{2}+b^{3}$
$\displaystyle c_{4}$ $\displaystyle=z^{7}+z^{3}$

This example shows that the degree of the continued fraction is not always
twice that of the formal power series.

##  4\. Continued Fractions and Riccati Differential Equations

In 1977, Baum and Sweet [3] considered considered the subset $D$ of irrational
continued fractions $\alpha$ in $\mathbb{F}_{2}((1/t))$ such that

$\alpha=[0,a_{1},a_{2},\ldots,a_{n},\ldots]$

where $\deg(a_{i})=1$ (i.e., $a_{i}=t$ or $t+1$) for $i\geq 1$. Consider the
subset $P$ of $\mathbb{F}_{2}((1/t))$

$P:=\\{\alpha\in\mathbb{F}_{2}((1/t))\mid\alpha=\sum_{i<0}a_{i}t^{i}\\}.$

Hence $P$ contains $D$. They proved the following theorem:

######  Theorem 4.1.

[Baum-Sweet, 1977] An element $\alpha\in P$ is in $D$ if and only if $\alpha$
satisfies

$\alpha^{2}+t\alpha+1=(1+t)\beta^{2}$

for some $\beta\in P$.

This theorem has the following equivalent formulation (see [8] for a proof):

######  Theorem 4.1′.

An element $\alpha\in P$ is in $D$ if and only if $\alpha$ satisfies

$(\alpha\cdot t(t+1))^{\prime}=\alpha^{2}+1.$

In [5] and [8], it was proved that the Thue-Morse and period-doubling
continued fraction both satisfy the Riccati differential equation

$(ab(a+b)f)^{\prime}=(ab)^{\prime}(1+f^{2}).$

We prove that these are in fact particular cases of a more general result:

######  Proposition 4.2.

Let $\bf{u}$ be a sequence taking value in $\\{a,b,a+b\\}$, where $a$, $b$ and
$a+b$ (if it is in the image of $\bf{u}$) are non-constant polynomials in
$\mathbb{F}_{2}[t]$, then the continued fraction

$f=[u_{0},u_{1},\ldots]\in\mathbb{F}_{2}((1/t))$

satisfies the Riccati differential equation

$(ab(a+b)f)^{\prime}=(ab)^{\prime}(1+f^{2}).$

###### Proof of Proposition 4.2.

Let $P_{n}/Q_{n}$ $(n\geq-1)$ be the convergents of $f$. Recall that

$(P_{0},Q_{0})=(u_{0},1),\quad(P_{-1},Q_{-1})=(1,0)$

and

(4.1) $P_{n}=u_{n}P_{n-1}+P_{n-2},\quad Q_{n}=u_{n}Q_{n-1}+Q_{n-2}\quad\mbox{
for }n\geq 1.$

Then we only have to prove that

$\lim_{n}(ab(a+b)f_{n})^{\prime}-(ab)^{\prime}(1+f_{n}^{2})=0,$

where $f_{n}=\frac{P_{n}}{Q_{n}}.$

Define

$F_{n}:=ab(a+b)P_{n}Q_{n}+ab(P_{n}^{2}+Q_{n}^{2}),$

then

$(ab(a+b)f_{n})^{\prime}-(ab)^{\prime}(1+f_{n}^{2})=\frac{F_{n}^{\prime}}{Q_{n}^{2}}.$

We prove by induction that for all $n\geq 0$,

(4.2) $F_{n}=ab+g_{n}^{2}$

for some $g_{n}\in\mathbb{F}_{2}[a,b]$.

It is easy to check that the claim is true for $n=-1,0$. Suppose now $n>1$ and
that the claim holds for $n-1$ and $n-2$. From the recurrence relations (4.1)
we deduce

$\displaystyle
F_{n}=u_{n}^{2}F_{n-1}+F_{n-2}+u_{n}ab(a+b)(P_{n-1}Q_{n-2}+P_{n-2}Q_{n-1}).$

Notice that $P_{n-1}Q_{n-2}+P_{n-2}Q_{n-1}=1$ by a basic property of
convergents, and if $u_{n}=a$ or $u_{n}=b$,
$u_{n}ab(a+b)=a^{2}b^{2}+u_{n}^{2}ab$, if $u_{n}=a+b$,
$u_{n}ab(a+b)=u_{n}^{2}ab$. We have

$F_{n}=ab+u_{n}^{2}g_{n-1}^{2}+g_{n-2}^{2}+a^{2}b^{2}$

if $u_{n}=a$ or $u_{n}=b$, and

$F_{n}=ab+u_{n}^{2}g_{n-1}^{2}+g_{n-2}^{2}$

if $u_{n}=a+b$. Thus we have proven (4.2).

Therefore

$\frac{F_{n}^{\prime}}{Q_{n}^{2}}=\frac{a^{\prime}b+b^{\prime}a}{Q_{n}^{2}}.$

Since the valuation of $1/Q_{n}$ in $1/t$ is at least $n$, the above term
converges to $0$ in $\mathbb{F}_{2}((1/t))$ as $n$ goes to infinity. ∎

##  5\. Acknowledgement

I would like to thank Alain Lasjaunias (who has written a partial presentation
on this subject intended for a private public) for valuable discussions. I
would also like to thank Jean-Paul Allouche for his help.

## References

  * [1] Jean-Paul Allouche and Jeffrey Shallit.  The ring of k-regular sequences.  Theoretical Computer Science, 98(2):163–197, 1992.
  * [2] Jean-Paul Allouche and Jeffrey Shallit.  Automatic sequences. Theory, Applications, Generalizations.  Cambridge University Press, Cambridge, 2003.
  * [3] Leonard E. Baum and Melvin M. Sweet.  Badly approximable power series in characteristic $2$.  Ann. of Math. (2), 105(3):573–580, 1977.
  * [4] Yann Bugeaud.  Automatic continued fractions are transcendental or quadratic.  Ann. Sci. Éc. Norm. Supér. (4), 46(6):1005–1022, 2013.
  * [5] Yann Bugeaud and Guo-Niu Han.  The Thue-Morse continued fractions in characteristic $2$ are algebraic.  Acta Arith., 2022+.
  * [6] Gilles Christol, Teturo Kamae, Michel Mendès France, and Gérard Rauzy.  Suites algébriques, automates et substitutions.  Bull. Soc. Math. France, 108(4):401–419, 1980.
  * [7] Yining Hu and Guo-Niu Han.  On the algebraicity of Thue-Morse and period-doubling continued fractions.  Acta Arith., 203(4):353–381, 2022.
  * [8] Yining Hu and Alain Lasjaunias.  Period-doubling continued fractions are algebraic in characteristic $2$.  Ann. Inst. Fourier (Grenoble), forthcoming.
  * [9] Alain Lasjaunias.  Continued fractions.  arXiv preprint arXiv:1711.11276, 2017.
  * [10] Olivier Salon.  Suites automatiques à multi-indices.  Séminaire de théorie des nombres de Bordeaux, pages 1–36A, 1986.