# Factor Complexity of $S$-adic sequences generated by the Arnoux-Rauzy-
Poincaré Algorithm

V. Berthé and S. Labbé

LIAFA, Université Paris Diderot - Paris 7,
Case 7014, 75205 Paris Cedex 13, France
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
(Mathematics Subject Classifications: 68R15, 37B10.)

###### Abstract

The Arnoux-Rauzy-Poincaré multidimensional continued fraction algorithm is
obtained by combining the Arnoux-Rauzy and Poincaré algorithms. It is a
generalized Euclidean algorithm. Its three-dimensional linear version consists
in subtracting the sum of the two smallest entries to the largest if possible
(Arnoux-Rauzy step), and otherwise, in subtracting the smallest entry to the
median and the median to the largest (the Poincaré step), and by performing
when possible Arnoux-Rauzy steps in priority. After renormalization it
provides a piecewise fractional map of the standard $2$-simplex. We study here
the factor complexity of its associated symbolic dynamical system, defined as
an $S$-adic system. It is made of infinite words generated by the composition
of sequences of finitely many substitutions, together with some restrictions
concerning the allowed sequences of substitutions expressed in terms of a
regular language. Here, the substitutions are provided by the matrices of the
linear version of the algorithm. We give an upper bound for the linear growth
of the factor complexity. We then deduce the convergence of the associated
algorithm by unique ergodicity.

##  1 Introduction

Multidimensional continued fraction algorithms aim at providing good rational
approximations of a given vector. There exist many different types of
continued fraction algorithms. Among them, piecewise fractional ones in the
sense of [Bre81, Sch00] have been widely studied whereas for their arithmetic
or for their ergodic properties. The viewpoint we take here on these
algorithms is issued from word combinatorics and symbolic dynamics. It is
indeed possible to generate with such algorithms infinite words with
prescribed letter frequencies: the letter frequency vector is indeed the
vector on which the algorithm is applied. We recall that a substitution is a
morphism of the free monoid that replaces letters by finite words. A piecewise
fractional continued fraction algorithm produces (unimodular) matrices with
non-negative entries that we consider as incidence matrices of substitutions.
We then iterate these substitutions in an $S$-adic way, that is, as the
(inverse) limit of an infinite product of substitutions (see e.g. [BD14, CN10,
DLR13, Ler12]). We thus obtain an infinite word $\mathbf{u}$ of the form

$\mathbf{u}=\lim_{n\to\infty}\sigma_{0}\circ\sigma_{1}\circ\cdots\circ\sigma_{n}(a^{\infty}).$

As an illustration consider the generation of Sturmian words with the
classical continued fraction algorithm (see [Lot02, Fog02] for more details).

The Diophantine approximation properties of the underlying continued fraction
algorithm are reflected in the generic behaviour of the balance function of
the generated word $\mathbf{u}$, where the balance function counts, for each
given letter, the difference between the numbers of occurrences of this letter
in any two words of the same length that occur in $\mathbf{u}$. It is also
closely related to the notion of symbolic discrepancy such as considered in
[Ada03]. We also would like the combinatorics of the generated infinite word
$\mathbf{u}$ to be “simple” in the sense that the factor complexity of
$\mathbf{u}$ is expected to be of linear growth, were the factor complexity
counts the number of factors of a given length.

Observe that there exist several methods for producing infinite words with
prescribed letter frequencies having a linear factor complexity $p(n)$ and/or
a bounded balance. The Sturmian words form a well-known family of infinite
balanced words over a two-letter alphabet having a linear factor complexity
($p(n)=n+1$ for all $n$). Nevertheless the situation is more contrasted for
words defined on alphabets having at least three letters concerning the
possibility of having simultaneously prescribed letter frequencies, a linear
factor complexity and a bounded balance. Typical generalizations of Sturmian
words are natural codings of interval exchanges and the billiard words in the
$d$-dimensional cube. However, billiard words have quadratic factor complexity
[Bar95, Bed03] and codings of interval exchanges are not balanced [Zor97].
Other approaches were considered in digital geometry where arithmetic
definitions of $3$D discrete lines were proposed. The standard model of
[And03] is one of them and can be encoded as a word on a three-letter
alphabet. It turns out that this model corresponds to the one of billiard
words [Lab12], thus also having a quadratic factor complexity in general.

The experimentations described in [BL11, Lab12] indicate that some
multidimensional continued fraction algorithms generate $S$-adic words having
a linear factor complexity and a bounded balance for almost every letter
frequencies vector. In particular, Brun multidimensional continued fraction
algorithm as well as the Arnoux-Rauzy-Poincaré algorithm seem to be the two
best choices in terms of balance properties. In this article, we focus on the
Arnoux-Rauzy-Poincaré algorithm which performs experimentally a bit better
than does Brun algorithm. This algorithm (under its linear form) consists in
subtracting the sum of the two smallest entries to the largest if possible and
otherwise, in subtracting the smallest entry to the median and the median to
the largest. In order to generate infinite words, we introduce an
$\mathcal{S}$-adic system associated with the nine possible matrices of the
algorithm that thus provide a set $\mathcal{S}$ of nine substitutions. Three
of them are substitutions known under the name of Arnoux-Rauzy substitutions
[AR91], and the other six are named Poincaré substitutions after Poincaré
algorithm [Nog95]. Moreover, the execution of the Arnoux-Rauzy-Poincaré
algorithm yields restrictions to the allowed infinite sequences of
substitutions, expressed in terms of a regular language. We then have a
bijection (up to a set of zero measure) between the infinite words in the
corresponding $\mathcal{S}$-adic system and the standard $2$-simplex
$\Delta=\\{(x_{1},x_{2},x_{3})\in\mathbb{R}^{3}_{+}\mid
x_{1}+x_{2}+x_{3}=1\\}$ (the vectors of letter frequencies). The main result
of the present paper is that these words have a linear factor complexity
$p(n)$.

######  Theorem 1 (Factor Complexity).

Let $\mathbf{u}$ be an $\mathcal{S}$-adic word generated by the Arnoux-Rauzy-
Poincaré algorithm applied to a totally irrational vector
$\mathbf{x}\in\Delta$. Then the factor complexity of $\mathbf{u}$ is such that
$p(n+1)-p(n)\in\\{2,3\\}$ and $2n+1\leq p(n)\leq\frac{5}{2}n+1$ for all $n\geq
0$.

The proof relies on a careful study of bispecial factors of $\mathbf{u}$, that
is, of factors having several left and right extensions in $\mathbf{u}$. We
prove that weak and strong bispecial factors are alternating in the sequence
(ordered by increasing length) of non-neutral bispecial factors. The
restriction for the directive sequences of the $\mathcal{S}$-adic words to the
regular language provided by the Arnoux-Rauzy-Poincaré algorithm is clearly
important; indeed quadratic factor complexity can be reached otherwise (see
Section 4.5).

Then, by using a result of Boshernitzan [Bos85], we deduce unique ergodicity
and thus, the existence of (uniform) frequency of any factor, and in
particular of the letters. This also provides a combinatorial proof of
convergence for this multidimensional continued fraction algorithm.

######  Theorem 2 (Frequencies and Convergence).

Let $\mathbf{u}$ be an $\mathcal{S}$-adic word generated by the Arnoux-Rauzy-
Poincaré algorithm applied to a totally irrational vector
$\mathbf{x}\in\Delta$. Then the symbolic dynamical system generated by
$\mathbf{u}$ is uniquely ergodic. As a consequence, the frequencies of factors
and letters exist in $\mathbf{u}$, the latter being equal to the coordinates
of $\mathbf{x}$.

Furthermore, the Arnoux-Rauzy-Poincaré algorithm is a weakly convergent
algorithm, that is, for Lebesgue almost every $\mathbf{x}\in\Delta$, if
$(M_{n})_{n}$ stands for the sequence of matrices produced by the Arnoux-
Rauzy-Poincaré algorithm, then one has $\cap_{n}M_{0}\cdots
M_{n}({\mathbb{R}}_{+}^{3})={\mathbb{R}}_{+}\mathbf{x}.$

Let us sketch the content of the present paper. The Arnoux-Rauzy-Poincaré
multidimensional continued fraction algorithm is introduced in Section 2. We
also define the associated Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic system
based on its nine substitutions (provided by its linear version) together with
a rational restriction on the directive sequences of substitutions that are
iterated. In Section 3, we introduce the basic notions used to compute the
factor complexity, namely languages, bispecial factors and extension types. In
Section 4, we study the life of bispecial factors under Arnoux-Rauzy and
Poincaré substitutions (with no restriction on the order of application of
substitutions). In Section 5, we prove the upper bound on the factor
complexity stated in Theorem 1. The convergence of the algorithm together with
unique ergodicity is lastly considered in Section 6.

This article is an extended version of [BL13]. The present paper provides the
upper bound $p(n)\leq\frac{5}{2}n+1$, whereas the upper bound in [BL13] was
$p(n)\leq 3n+1$.

Acknowledgements We are thankful to Pierre Arnoux, Srecko Brlek, Julien
Cassaigne, Julien Leroy and Thierry Monteil for many fruitful discussions on
the subject. This work was supported by Agence Nationale de la Recherche and
the Austrian Science Fund through project Fractals and Numeration
ANR-12-IS01-0002 and project Dyna3S ANR-13-BS02-0003. The second author is
supported by NSERC (Canada).

##  2 The Arnoux-Rauzy-Poincaré Algorithm

###  2.1 The algorithm

The Arnoux-Rauzy-Poincaré (ARP) is a multidimensional continued fraction
algorithm in the sense of [Bre81, Sch00], defined by piecewise fractional maps
acting on the standard $2$-simplex
$\Delta=\\{(x_{1},x_{2},x_{3})\in\mathbb{R}^{3}_{+}:x_{1}+x_{2}+x_{3}=1\\}$.
It is a fusion algorithm such as introduced in [BL11, Lab12] which combines
the two classical algorithms that are Poincaré (P) algorithm and Arnoux-Rauzy
(AR) algorithm, which are respectively defined (under their linear form) in
dimension 3 as follows: Poincaré algorithm acts on a triple of non-negative
entries by subtracting the smallest entry to the median and the median to the
largest, whereas Arnoux-Rauzy algorithm acts by subtracting the sum of the two
smallest entries to the largest, when possible. Our algorithm privilegiates an
Arnoux-Rauzy step if possible, otherwise it perfoms a Poincaré step.

The simplex $\Delta$ admits as vertices the vectors
$\mathbf{e}_{1}=(1,0,0)^{\top}$, $\mathbf{e}_{2}=(0,1,0)^{\top}$ and
$\mathbf{e}_{3}=(0,0,1)^{\top}$. In order to partition $\Delta$, we consider
the following fifteen matrices, namely

$\footnotesize\begin{array}[]{lllll}A_{1}=\left(\begin{array}[]{rrr}1&1&1\\\
0&1&0\\\ 0&0&1\end{array}\right),&P_{21}=\left(\begin{array}[]{rrr}1&1&1\\\
0&1&1\\\ 0&0&1\end{array}\right),&P_{31}=\left(\begin{array}[]{rrr}1&1&1\\\
0&1&0\\\ 0&1&1\end{array}\right),&H_{21}=\left(\begin{array}[]{rrr}1&0&0\\\
0&1&0\\\ 1&0&1\end{array}\right),&H_{31}=\left(\begin{array}[]{rrr}1&0&0\\\
1&1&0\\\ 0&0&1\end{array}\right),\\\ A_{2}=\left(\begin{array}[]{rrr}1&0&0\\\
1&1&1\\\ 0&0&1\end{array}\right),&P_{12}=\left(\begin{array}[]{rrr}1&0&1\\\
1&1&1\\\ 0&0&1\end{array}\right),&P_{32}=\left(\begin{array}[]{rrr}1&0&0\\\
1&1&1\\\ 1&0&1\end{array}\right),&H_{12}=\left(\begin{array}[]{rrr}1&0&0\\\
0&1&0\\\ 0&1&1\end{array}\right),&H_{32}=\left(\begin{array}[]{rrr}1&1&0\\\
0&1&0\\\ 0&0&1\end{array}\right),\\\ A_{3}=\left(\begin{array}[]{rrr}1&0&0\\\
0&1&0\\\ 1&1&1\end{array}\right),&P_{13}=\left(\begin{array}[]{rrr}1&1&0\\\
0&1&0\\\ 1&1&1\end{array}\right),&P_{23}=\left(\begin{array}[]{rrr}1&0&0\\\
1&1&0\\\ 1&1&1\end{array}\right),&H_{13}=\left(\begin{array}[]{rrr}1&0&0\\\
0&1&1\\\ 0&0&1\end{array}\right),&H_{23}=\left(\begin{array}[]{rrr}1&0&1\\\
0&1&0\\\ 0&0&1\end{array}\right),\end{array}$

whose column vectors define partitions by triangles of the simplex such as
illustrated at Figure 1 (left).

Figure 1: Left: the partition provided by three Arnoux-Rauzy matrices, the six
Poincaré matrices and the six half triangles. Right: the partition of Arnoux-
Rauzy-Poincaré algorithm.

Then, the column vectors of $A_{1}$, $A_{2}$, $A_{3}$, $P_{31}H_{31}$,
$P_{13}H_{13}$, $P_{23}H_{23}$, $P_{32}H_{32}$, $P_{12}H_{12}$ and
$P_{21}H_{21}$ describe a partition of $\Delta$ depicted in Figure 1 (right).
Partitions are considered here up to a set of zero measure. This partition
allows one to associate with almost every point of $\Delta$ a matrix as
follows:

$\begin{array}[]{rcl}M:\Delta&\to&GL(3,\mathbb{Z})\\\
\mathbf{x}&\mapsto&\begin{cases}A_{k}&\text{ if }\mathbf{x}\in A_{k}\Delta,\\\
P_{jk}&\text{ else if }\mathbf{x}\in
P_{jk}H_{jk}\Delta.\end{cases}\end{array}$

We say that $\mathbf{x}=(x_{1},x_{2},x_{3})\in\Delta$ is _totally irrational_
if $x_{1}$, $x_{2}$, $x_{3}$ are linearly independent over $\mathbb{Q}$. When
$\mathbf{x}$ is not a totally irrational vector, there might be more than one
choice for the matrix $M(\mathbf{x})$ in the previous definition.
Nevertheless, the matrix $M(\mathbf{x})$ is uniquely defined for a totally
irrational vector.

Then, the Arnoux-Rauzy-Poincaré algorithm is defined (by renormalizing with
respect to the simplex $\Delta$) the linear map $M$:

$\begin{array}[]{rcl}T:\Delta&\to&\Delta\\\
\mathbf{x}&\mapsto&\displaystyle\frac{M(\mathbf{x})^{-1}\cdot\mathbf{x}}{\left\|M(\mathbf{x})^{-1}\cdot\mathbf{x}\right\|_{1}}\,\cdot\end{array}$

Each totally irrational vector $\mathbf{x}\in\Delta$ defines an orbit under
the map $T$ and a sequence of matrices
$(M_{n}(\mathbf{x}))_{n\in{\mathbb{N}}}$:

$M_{0}(\mathbf{x})=\mathrm{Id},\quad M_{n}(\mathbf{x})=M(T^{n-1}(\mathbf{x}))\
\mbox{ for all }n.$

######  Example 3.

Consider $\mathbf{x}=(1,\pi,\sqrt{2})$. The first $5$ points of the orbit of
$\mathbf{x}$ under the map $T$ are

$\mathbf{x}\in A_{2}\Delta,\quad T(\mathbf{x})\in P_{13}H_{13}\Delta,\quad
T^{2}(\mathbf{x})\in A_{2}\Delta,\quad T^{3}(\mathbf{x})\in A_{3}\Delta,\quad
T^{4}(\mathbf{x})\in A_{1}\Delta,\cdots$

One has $M_{0}(\mathbf{x})=\mathrm{Id}$, $M_{1}(\mathbf{x})=A_{2}$,
$M_{2}(\mathbf{x})=P_{13}$, $M_{3}(\mathbf{x})=A_{2}$,
$M_{4}(\mathbf{x})=A_{3}$ and $M_{5}(\mathbf{x})=A_{1}$.

###  2.2  Arnoux-Rauzy-Poincaré $S$-adic words

We now associate with the Arnoux-Rauzy-Poincaré algorithm a finite set
$\mathcal{S}$ of substitutions as well as $\mathcal{S}$-adic words.

We first start with some terminology. We consider a finite set of letters
${\cal A}$, called alphabet. Here ${\mathcal{A}}=\\{1,2,3\\}$. A (finite) word
is an element of the free monoid ${\cal A}^{*}$ generated by ${\cal A}$. The
unique word of length $0$ is the _empty word_ and we let it be denoted as
$\varepsilon$. We let the set of all (finite) words over $\mathcal{A}$ be
denoted by $\mathcal{A}^{*}$. With the concatenation of words as product
operation, ${\mathcal{A}}^{*}$ is the free monoid with $\varepsilon$ as
identity element. A substitution on the alphabet ${\mathcal{A}}$ is a non-
erasing morphism of the free monoid wich replaces letters by words. Let
$\sigma$ be a substitution. Its incidence matrix (also called abelianized
matrix) $M_{\sigma}=\left(m_{i,j}\right)_{1\leq i,j\leq d}$ is defined as the
square matrix whose entry of index $(i,j)$ is equal to the number of
occurrences of the letter $i$ in $\sigma(j)$. If a word $u$ can be factorized
as $pvs$, with $p,v,s\in\mathcal{A}^{*}$, then we say that $p$ is a _prefix_ ,
$v$ is a _factor_ and $s$ is a _suffix_ of $u$. The factor $v$ is said
_proper_ if $p$ and $s$ are non-empty. This notion extends to any infinite
word $\mathbf{u}$. The set ${\mathcal{A}}^{\mathbb{N}}$ is equipped with the
product topology of the discrete topology on each copy of ${\mathcal{A}}$;
this topology is induced by the following distance: for two distinct infinite
words ${\bf u}$ and ${\bf v}$ in ${\mathcal{A}}^{\mathbb{N}}$,
$\operatorname{d}({\bf u},{\bf v})=2^{-\min\\{n\in{\mathbb{N}}\ \mid\
u_{n}\neq v_{n}\\}}$.

The infinite word $\mathbf{u}\in{\mathcal{A}}^{\mathbb{N}}$ is said to admit
an $S$-adic representation if there exist a finite set $S$ of substitutions
defined on the alphabet $\mathcal{A}$, a sequence
$s=(\sigma_{n})_{n\in\mathbb{N}}\in S^{\mathbb{N}}$ of substitutions that all
belong to $S$, and $(a_{n})_{n\in\mathbb{N}}$ a sequence of letters in
${\mathcal{A}}$ such that

$\mathbf{u}=\lim_{n\to\infty}\sigma_{0}\sigma_{1}\cdots\sigma_{n}(a_{n}^{\infty}),$

with the notation $a_{n}^{\infty}$ standing for the infinite constant word
taking the value $a_{n}$. The word $\mathbf{u}$ is said to be $S$-adic, and
the sequence $s$ is called the _directive sequence_. We will use the following
notation: for all $m\in{\mathbb{N}}$

$\mathbf{u}^{(m)}=\lim_{n\to\infty}\sigma_{m}\sigma_{m+1}\cdots\sigma_{n}(a_{n}^{\infty}).$

An $S$-adic expansion with directive sequence
$(\sigma_{n})_{n\in{\mathbb{N}}}$ is said _weakly primitive_ if, for each $n$,
there exists $r$ such that the substitution $\sigma_{n}\cdots\sigma_{{n+r}}$
is positive, that is, its incidence matrix has only positive entries. If an
infinite word $\mathbf{u}$ admits a weakly primitive $S$-adic representation,
then it is _uniformly recurrent_ , that is, all its factors occur infinitely
often and with bounded gaps [Dur03]. An infinite word $\mathbf{u}$ is said
_recurrent_ if all its factors occur infinitely often in $\mathbf{u}$. For
more on $S$-adic words, see [BD14, CN10, DLR13, Ler12].

We now associate substitutions with the matrices defining the Arnoux-Rauzy-
Poincaré algorithm. Let $i,j,k$ be such that $\\{i,j,k\\}=\\{1,2,3\\}$. A
Poincaré substitution is a substitution of the form $\pi_{jk}:i\mapsto
ijk,j\mapsto jk,k\mapsto k$. An Arnoux-Rauzy substitution is given by
$\alpha_{k}:i\mapsto ik,j\mapsto jk,k\mapsto k$. For each
$\\{i,j,k\\}=\\{1,2,3\\}$, $P_{jk}$ is the incidence matrix of the
substitution $\pi_{jk}$ and $A_{k}$ is the incidence matrix of $\alpha_{k}$.
There are thus 6 Poincaré and 3 distinct Arnoux-Rauzy substitutions:

$\begin{array}[]{lll}\pi_{23}=\left\\{\begin{array}[]{l}1\mapsto 123\\\
2\mapsto 23\\\ 3\mapsto 3\\\
\end{array}\right.,&\pi_{13}=\left\\{\begin{array}[]{l}1\mapsto 13\\\ 2\mapsto
213\\\ 3\mapsto 3\\\
\end{array}\right.,&\alpha_{3}=\left\\{\begin{array}[]{l}1\mapsto 13\\\
2\mapsto 23\\\ 3\mapsto 3\\\ \end{array}\right.,\\\
\pi_{12}=\left\\{\begin{array}[]{l}1\mapsto 12\\\ 2\mapsto 2\\\ 3\mapsto
312\\\ \end{array}\right.,&\pi_{32}=\left\\{\begin{array}[]{l}1\mapsto 132\\\
2\mapsto 2\\\ 3\mapsto 32\\\
\end{array}\right.,&\alpha_{2}=\left\\{\begin{array}[]{l}1\mapsto 12\\\
2\mapsto 2\\\ 3\mapsto 32\\\ \end{array}\right.,\\\
\pi_{31}=\left\\{\begin{array}[]{l}1\mapsto 1\\\ 2\mapsto 231\\\ 3\mapsto
31\\\ \end{array}\right.,&\pi_{21}=\left\\{\begin{array}[]{l}1\mapsto 1\\\
2\mapsto 21\\\ 3\mapsto 321\\\
\end{array}\right.,&\alpha_{1}=\left\\{\begin{array}[]{l}1\mapsto 1\\\
2\mapsto 21\\\ 3\mapsto 31\\\ \end{array}\right..\end{array}$

Let

$\mathcal{S}:=\\{\alpha_{1},\alpha_{2},\alpha_{3},\pi_{12},\pi_{13},\pi_{21},\pi_{23},\pi_{31},\pi_{32}\\}.$

We also denote by $\mathcal{S}_{\alpha}$, $\mathcal{S}_{\pi}$, respectively,
the following sets of substitutions:

$\mathcal{S}_{\alpha}=\\{\alpha_{1},\alpha_{2},\alpha_{3}\\},\
\mathcal{S}_{\pi}=\\{\pi_{12},\pi_{13},\pi_{23},\pi_{21},\pi_{31},\pi_{32}\\},\mbox{
with }\mathcal{S}=\mathcal{S}_{\alpha}\cup\mathcal{S}_{\pi}.$

The substitutions in $\mathcal{S}$ are such that for any letter
$i\in\\{1,2,3\\}$, $\sigma(i)$ admits $i$ as a prefix. This yields the
convergence of any $\mathcal{S}$-adic representation in
${\mathcal{A}}^{\mathbb{N}}$ if the sequence of letters $(a_{n})_{n}$ is
constant. More precisely, for any sequence of substitutions $(\sigma_{n})_{n}$
with values in $\mathcal{S}$ and for every letter $a\in\\{1,2,3\\}$ then the
following limit exists

$\lim_{n\to\infty}\sigma_{0}\sigma_{1}\cdots\sigma_{n}(a^{\infty}).$

######  Definition 4 (Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic word).

An _Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic word_ is an infinite word of the
form

$\mathbf{u}=\lim_{n\to\infty}\sigma_{0}\sigma_{1}\cdots\sigma_{n}(a^{\infty}),$

where $a\in\mathcal{A}$ and $\sigma_{n}\in\mathcal{S}$ for all $n\geq 0$. Its
directive sequence is the sequence $s=(\sigma_{n})_{n}$.

###  2.3 The Arnoux-Rauzy-Poincaré $S$-adic system

The aim of this section is to associate with the Arnoux-Rauzy-Poincaré
algorithm an $\mathcal{S}$-adic symbolic dynamical system by taking into
account the restrictions provided by the algorithm which is not complete but
Markovian. We first recall the definition of an $S$-adic system. An $S$-adic
system is obtained by adding restrictions on the set of allowed directive
sequences: it is given by a finite directed strongly connected graph
$\mathcal{G}$ labeled by the substitutions, with each infinite path giving
rise to a directive sequence [BD14].

The partition of $\Delta$ allows to associate with almost any point of
$\Delta$ a substitution of $\mathcal{S}$:

$\begin{array}[]{rcl}\sigma:\Delta&\to&\mathcal{S}\\\
\mathbf{x}&\mapsto&\begin{cases}\alpha_{k}&\text{ if }\mathbf{x}\in
A_{k}\Delta,\\\ \pi_{jk}&\text{ else if }\mathbf{x}\in
P_{jk}H_{jk}\Delta,\end{cases}\end{array}$

and a directive sequence $s=(\sigma_{n})_{n}$ with
$\sigma_{n}=\sigma(T^{n}(\mathbf{x}))$ for all $n$. Observe that the
substitution $\sigma(\mathbf{x})$ has for incidence matrix $M(\mathbf{x})$
such as defined in Section 2.1.

######  Definition 5.

An _$\mathcal{S}$ -adic word $\mathbf{u}$ generated by the Arnoux-Rauzy-
Poincaré algorithm applied to the totally irrational vector
$\mathbf{x}\in\Delta$_ is an infinite word of the form

$\mathbf{u}=\lim_{n\to\infty}\left(\sigma(\mathbf{x})\cdot\sigma(T(\mathbf{x}))\cdot\sigma(T^{2}(\mathbf{x}))\cdot\ldots\cdot\sigma(T^{n-1}(\mathbf{x}))\right)(a^{\infty})$

where $a\in\\{1,2,3\\}$. Its directive sequence is the sequence
$s=(\sigma_{n})_{n}$ with $\sigma_{n}=\sigma(T^{n}(\mathbf{x}))$ for all $n$.

Let us show that the factors of the directive sequences produced by the
Arnoux-Rauzy-Poincaré algorithm belong to a rational language strictly
included in $\mathcal{S}^{*}$. We consider the automaton
$\mathcal{G}=(Q,\mathcal{S},\delta,I,F)$ defined by the states

$Q=\\{\Delta,H_{12},H_{13},\\\ H_{21},H_{23},H_{31},H_{32}\\},$

the alphabet $\mathcal{S}$, with the transitions $\delta\subset
Q\times\mathcal{S}\times Q$ being defined by

$\displaystyle\delta=\bigcup_{\\{i,j,k\\}=\\{1,2,3\\}}\\{(\Delta,\alpha_{k},\Delta),$
$\displaystyle(\Delta,\pi_{jk},H_{jk}),(H_{jk},\alpha_{j},H_{jk}),$
$\displaystyle(H_{jk},\alpha_{i},\Delta),(H_{jk},\pi_{ij},H_{ij}),(H_{jk},\pi_{ki},H_{ki}),(H_{jk},\pi_{ji},H_{ji})\\},$

and with initial state $I=\\{\Delta\\}$ and final state $F=Q$ (see Figure 2).
We consider the $\mathcal{S}$-adic system associated with the regular language
$\mathcal{L}(\mathcal{G})$.

Figure 2: The deterministic automaton $\mathcal{G}$. To avoid crossing arrows,
the initial state $\Delta$ is drawn at three places. The indices of $\pi$
transitions are not written since they are determined by the indices of the
arrival state: $\xrightarrow{\pi}H_{jk}$ means $\xrightarrow{\pi_{jk}}H_{jk}$.

This language corresponds to directive sequences for which the sequence of
incidence matrices is generated by the execution of the Arnoux-Rauzy-Poincaré
algorithm.

######  Proposition 6 (ARP regular language).

The set of directive sequences produced by the Arnoux-Rauzy-Poincaré algorithm
is included in the set of labeled infinite paths in the automaton
$\mathcal{G}$.

The proof of the proposition is provided in the appendix.

######  Remark 7.

We can even prove that the closure of the set of directive sequences produced
by the Arnoux-Rauzy-Poincaré algorithm is equal to the set $X_{\mathcal{G}}$
of labeled infinite paths starting in the automaton $\mathcal{G}$, as a
consequence of the convergence of the algorithm proved in Section 6. Let
$\Sigma\colon\Delta\rightarrow X_{\mathcal{G}}$ be the map that associates
with a (totally irrational vector) $\mathbf{x}$ the directive sequence
$(\sigma_{n})_{n}$ where $\sigma_{n}=\sigma(T^{n}(\mathbf{x}))$ for all $n$.
One has the following diagram and measure-theoretical isomorphism, where
$\Sigma$ is a.e. one-to-one and where the shift associates with the label of
an infinite path the label of the path deprived of its first edge:

$\begin{array}[]{ccc}\Delta&\stackrel{{\scriptstyle
T}}{{\longrightarrow}}&\Delta\\\
\Big{\downarrow}\scriptstyle{\Sigma}&&\Big{\downarrow}\scriptstyle{\Sigma}\\\
\
X_{\mathcal{G}}&\underset{\mathrm{shift}}{\longrightarrow}&X_{\mathcal{G}}\end{array}$

We now can define the Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic system from the
multidimensional continued fraction algorithm.

######  Definition 8 (Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic system).

The _Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic system_ is the set of
$\mathcal{S}$-adic words

$\mathbf{u}=\lim_{n\to\infty}\sigma_{0}\sigma_{1}\cdots\sigma_{n}(a^{\infty}),$

whose directive sequence $(\sigma_{n})_{n}$ is an infinite path in
$\mathcal{G}$. We distinguish three types of directive sequences together with
some restrictions on the chosen letter $a$:

  1. 1.

if $(\sigma)_{n}\in\mathcal{S}^{*}\\{\alpha_{k}\\}^{\mathbb{N}}$, for
$k\in\\{1,2,3\\}$, then $a=k$ (Type 1);

  2. 2.

else if
$(\sigma)_{n}\in\mathcal{S}^{*}\\{\alpha_{k},\alpha_{j}\\}^{\mathbb{N}}$, then
$a\in\\{j,k\\}$, for some $\\{i,j,k\\}=\\{1,2,3\\}$ (Type 2);

  3. 3.

otherwise, take any $a\in\\{1,2,3\\}$ (Type 3).

The requirements in this definition concerning the choice of the letter $a$
will be clearer with Proposition 13 below: they aim at working with recurrent
words which will be used in the computation of the factor complexity function.
According to Proposition 6, any $\mathcal{S}$-adic word $\mathbf{u}$ generated
by the Arnoux-Rauzy-Poincaré algorithm applied to a totally irrational vector
$\mathbf{x}\in\Delta$, according to Definition 5, belongs to the Arnoux-Rauzy-
Poincaré $\mathcal{S}$-adic system. Furthermore, they correspond to Type 3 in
Definition 8.

######  Remark 9.

We stress the following terminology: by Arnoux-Rauzy-Poincaré
$\mathcal{S}$-adic word, we mean an $\mathcal{S}$-adic word with no other
restriction on the directive sequence that the fact that it belongs to
$\mathcal{S}^{\mathbb{N}}$ (see Definition 4), whereas for a word in the
Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic system, the restrictions of
Proposition 6 are taken into account.

######  Example 10.

We continue Example 3. The word generated by the Arnoux-Rauzy-Poincaré
algorithm applied to $\mathbf{x}=(1,\pi,\sqrt{2})$ is:

$\displaystyle\mathbf{u}$
$\displaystyle=\alpha_{2}\pi_{13}\alpha_{2}\alpha_{3}\alpha_{1}\pi_{31}\pi_{23}\pi_{31}\pi_{12}(\alpha_{3})^{8}\alpha_{1}(\alpha_{2})^{6}\pi_{21}\alpha_{3}\alpha_{3}\alpha_{1}\pi_{32}\cdots(1)$
$\displaystyle=1232212323221232212323221232123221232322123232212321232212323\cdots$

Note that the substitutions shown on the above line determine the prefix of
$\mathbf{u}$ of length $1453060$. The first prefixes are

$\alpha_{2}(1)=12,\quad\alpha_{2}\pi_{13}(1)=1232,\quad\alpha_{2}\pi_{13}\alpha_{2}(1)=123221232,\quad\alpha_{2}\pi_{13}\alpha_{2}\alpha_{3}(1)=1232212323221232.$

Observe that due to its $S$-adic construction, the infinite word $\mathbf{u}$
can be decomposed on three-block codes (that is, on codes consisting of three
finite words) in many ways:

$\displaystyle 12322|1232322|12322|1232322|1232|12322|1232322|1232322|\cdots$
$\displaystyle 12|32|2|12|32|32|2|12|32|2|12|32|32|2|12|32|12|\cdots$
$\displaystyle 123|22123|23|22123|22123|23|22123|2123|22123|23|22123|\cdots$

The blocks are in each case respectively $\\{12322,1232322,1232\\}$,
$\\{12,2,32\\}$ and $\\{23,22123,2123\\}$ (they are obtained as
$\sigma_{1}\cdots\sigma_{n}(i)$, for $i=1,2,3$, or else, as return words on
the letter $1$ in $\mathbf{u}$, where a return word on $1$ is a finite word
$v$ that does not contain the letter $1$, but that is such that $v1$ is a
factor of $\mathbf{u}$). For comparison, the billiard word of direction
$(1,\pi,\sqrt{2})$ starting at $(0,0,0)$ is:

$2321232212322312232123221322231223212322321223212322132232123\cdots$

It has quadratic factor complexity. It cannot be decomposed on a three-factor
code (its has too much return words on each letter).

###  2.4 Totally irrational vectors and weak primitivity

The next lemma provides a characterization of weakly primitive
$\mathcal{S}$-adic expansions. Indeed weak primitivity fails if and only if
the directive sequence $(\sigma_{n})_{n\in{\mathbb{N}}}$ contains finitely
many Poincaré substitutions and takes ultimately at most two values (that thus
are Arnoux-Rauzy substitutions).

######  Lemma 11.

Let
$\mathbf{u}=\lim_{n\to\infty}\sigma_{0}\sigma_{1}\cdots\sigma_{n}(a_{n}^{\infty})$
be an $\mathcal{S}$-adic word generated by the Arnoux-Rauzy-Poincaré algorithm
applied to the vector $\mathbf{x}=(x_{1},x_{2},x_{3})\in\Delta$. Its
associated $\mathcal{S}$-adic expansion is weakly primitive if and only if

$(\sigma_{n})_{n\in{\mathbb{N}}}\not\in\mathcal{S}^{*}\cdot\left(\\{\alpha_{1},\alpha_{2}\\}^{\mathbb{N}}\cup\\{\alpha_{1},\alpha_{3}\\}^{\mathbb{N}}\cup\\{\alpha_{2},\alpha_{3}\\}^{\mathbb{N}}\cup\\{\alpha_{1}\\}^{\mathbb{N}}\cup\\{\alpha_{2}\\}^{\mathbb{N}}\cup\\{\alpha_{3}\\}^{\mathbb{N}}\right).$

###### Proof.

If
$(\sigma_{n})_{n\in{\mathbb{N}}}\in\mathcal{S}^{*}\cdot\left(\\{\alpha_{1},\alpha_{2}\\}^{\mathbb{N}}\cup\\{\alpha_{1},\alpha_{3}\\}^{\mathbb{N}}\cup\\{\alpha_{2},\alpha_{3}\\}^{\mathbb{N}}\cup\\{\alpha_{1}\\}^{\mathbb{N}}\cup\\{\alpha_{2}\\}^{\mathbb{N}}\cup\\{\alpha_{3}\\}^{\mathbb{N}}\right)$,
then it is easily seen that $(\sigma_{n})_{n\in{\mathbb{N}}}$ is not weakly
primitive.

Now, let $(\sigma_{n})_{n\in{\mathbb{N}}}$ be the directive sequence of an
$\mathcal{S}$-adic expansion which is not weakly primitive in the Arnoux-
Rauzy-Poincaré $\mathcal{S}$-adic system. Being not weakly primitive means
that there exists $m$ such that for all $p$ with $m\leq p$ the substitution
$\sigma_{m}\cdots\sigma_{{p}}$ is not positive, that is, one of the entries of
its incidence matrix is zero. Moreover, for all $p$ and $r$ such that $m\leq
p\leq r$ the incidence matrix of the substitution
$\sigma_{p}\cdots\sigma_{{r}}$ is not positive.

Note that since the incidence matrix of every substitution in $\mathcal{S}$
has entries $1$ on the diagonal, the positivity of entries is preserved by
left and right multiplication. Therefore, if
$\sigma_{1}\sigma_{2}\cdots\sigma_{n}\in\mathcal{S}^{*}$ is positive, then
$\varphi$ is positive for every
$\varphi\in\mathcal{S}^{*}\sigma_{1}\mathcal{S}^{*}\sigma_{2}\mathcal{S}^{*}\cdots\mathcal{S}^{*}\sigma_{n}\mathcal{S}^{*}$.

Assume first that $(\sigma_{n})_{n\geq m}$ contains no Poincaré substitution.
If $(\sigma_{n})_{n\geq m}$ contains three distinct Arnoux-Rauzy
substitutions, there are some values of $p$ and $r$ with $m\leq p\leq r$ such
that $\sigma_{p}\cdots\sigma_{{r}}$ contains three distinct Arnoux-Rauzy
substitutions. One verifies that $\alpha_{i}\alpha_{j}\alpha_{k}$ is positive
for all possible values of $i$, $j$, $k$ with $\\{i,j,k\\}=\\{1,2,3\\}$. Then
$\sigma_{p}\cdots\sigma_{{r}}$ is positive which is a contradiction.
Therefore, we conclude that
$(\sigma_{n})_{n\in{\mathbb{N}}}\in\mathcal{S}^{*}\cdot\left(\\{\alpha_{1},\alpha_{2}\\}^{\mathbb{N}}\cup\\{\alpha_{1},\alpha_{3}\\}^{\mathbb{N}}\cup\\{\alpha_{2},\alpha_{3}\\}^{\mathbb{N}}\right)$.

Assume $(\sigma_{n})_{n\geq m}$ contains at least one Poincaré substitution.
We may suppose that $(\sigma_{n})_{n\geq p}$ starts with a Poincaré
substitution $\sigma_{p}=\pi_{jk}$ for $p\geq m$. Since $(\sigma_{n})_{n\geq
p}\in\mathcal{L}(\mathcal{G})$, then

$(\sigma_{n})_{n\geq
p}\in\left(\pi_{jk}\alpha_{j}^{\infty}\right)\cup\left(\pi_{jk}\alpha_{j}^{t}\\{\alpha_{i},\pi_{ki},\pi_{ji}\\}\mathcal{S}^{\mathbb{N}}\right)\cup\left(\pi_{jk}\alpha_{j}^{t}\pi_{ij}\alpha_{i}^{\infty}\right)\cup\left(\pi_{jk}\alpha_{j}^{t}\pi_{ij}\alpha_{i}^{s}\\{\alpha_{k},\pi_{jk},\pi_{ik},\pi_{ki}\\}\mathcal{S}^{\mathbb{N}}\right),$

for some non-negative integers $s$ and $t$ and $\\{i,j,k\\}=\\{1,2,3\\}$. But
$\pi_{jk}\alpha_{i}$, $\pi_{jk}\pi_{ki}$ and $\pi_{jk}\pi_{ji}$ are positive.
Also $\pi_{jk}\pi_{ij}\alpha_{k}$, $\pi_{jk}\pi_{ij}\pi_{jk}$,
$\pi_{jk}\pi_{ij}\pi_{ik}$ and $\pi_{jk}\pi_{ij}\pi_{ki}$ are positive.
Therefore,

$(\sigma_{n})_{n\geq
p}\in\left(\pi_{jk}\alpha_{j}^{\infty}\right)\cup\left(\pi_{jk}\alpha_{j}^{t}\pi_{ij}\alpha_{i}^{\infty}\right)$

and we have shown that
$(\sigma_{n})_{n\in{\mathbb{N}}}\in\mathcal{S}^{*}\cdot\left(\\{\alpha_{1}\\}^{\mathbb{N}}\cup\\{\alpha_{2}\\}^{\mathbb{N}}\cup\\{\alpha_{3}\\}^{\mathbb{N}}\right)$.
∎

######  Proposition 12.

Let $\mathbf{u}$ be an $\mathcal{S}$-adic word generated by the Arnoux-Rauzy-
Poincaré algorithm applied to the totally irrational vector
$\mathbf{x}\in\Delta$. Then the associated $S$-adic expansion is weakly
primitive. In particular, $\mathbf{u}^{(m)}$ is of Type $3$, uniformly
recurrent and proper, for all $m$.

###### Proof.

The conclusion follows from Lemma 11 by noticing that if

$(\sigma_{n})_{n\in{\mathbb{N}}}\in\mathcal{S}^{*}\cdot\left(\\{\alpha_{1},\alpha_{2}\\}^{\mathbb{N}}\cup\\{\alpha_{1},\alpha_{3}\\}^{\mathbb{N}}\cup\\{\alpha_{2},\alpha_{3}\\}^{\mathbb{N}}\cup\\{\alpha_{1}\\}^{\mathbb{N}}\cup\\{\alpha_{2}\\}^{\mathbb{N}}\cup\\{\alpha_{3}\\}^{\mathbb{N}}\right)$

then $\mathbf{x}$ cannot be totally irrational. ∎

Observe that not every word of the Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic
system is uniformly recurrent. Nevertheless, one easily checks that words of
this system are all recurrent.

######  Proposition 13.

Any infinite word ${\bf u}$ in the Arnoux-Rauzy-Poincaré system is recurrent
as well as $\mathbf{u}^{(m)}$ for any $m$.

######  Example 14.

The infinite word $\alpha_{1}^{\infty}(2^{\infty})=21^{\infty}$ is not
recurrent whereas $\alpha_{1}^{\infty}(1^{\infty})=1^{\infty}$ is recurrent.

The restriction of the infinite words under study to the case where each
letter always appears as proper factor will also be useful to prove the main
result of this article.

######  Definition 15 (Proper word ).

A word $\mathbf{u}\in\\{1,2,3\\}^{\mathbb{N}}$ is said _proper_ if each letter
$i\in\\{1,2,3\\}$ is a proper factor of $\mathbf{u}$, or equivalently, for
each letter $i\in\\{1,2,3\\}$, there exists a letter $e$ such that $ei$ is a
factor of $\mathbf{u}$.

##  3 Factor complexity

In this section, we define the terminology relative to languages, bispecial
factors, extension types and factor complexity. We adopt the notation of
[CN10].

###  3.1 Language and complexity function $p(n)$

Let $\mathcal{A}=\\{1,2,\ldots,d\\}$ be an alphabet. The length of a word
$u\in\mathcal{A}^{n}$ is denoted by $|u|$ and is equal to $n$, whereas the
notation $|u|_{i}$ stands for the number of occurrences of the letter $i$ in
$u$. A _language_ is a subset of the free monoid $\mathcal{A}^{*}$. A language
$L$ is _factorial_ if for any $w\in L$, then any factor $u$ of $w$ belongs to
$L$. The abelianized of a finite word $w\in\mathcal{A}^{*}$ is the vector

$\overrightarrow{w}=(|w|_{1},|w|_{2},\ldots,|w|_{d})\in\mathbb{N}^{d}.$

We consider an infinite word
$\mathbf{u}=u_{0}u_{1}u_{2}u_{3}\cdots\in\mathcal{A}^{\mathbb{N}}$. For each
$n\in\mathbb{N}$, $\mathcal{L}_{n}(\mathbf{u})$ is the set of factors of
length $n$ in $\mathbf{u}$, while $\mathcal{L}(\mathbf{u})$ is the set of all
factors in $\mathbf{u}$, and is called the _language of $\mathbf{u}$_. The
language of $\mathbf{u}$ is factorial. For each $n\in\mathbb{N}$, let
$p_{\mathbf{u}}(n)$ be the cardinality of $\mathcal{L}_{n}(\mathbf{u})$. Then
$p_{\mathbf{u}}:\mathbb{N}\to\mathbb{N}$ is a function called the _factor
complexity function_ of $\mathbf{u}$. When no confusion is possible, we omit
$\mathbf{u}$ and just write $p$.

###  3.2 Bispecial Factors and Extension Types

Let $w$ be a factor of either a recurrent infinite word or of a finite word
$\mathbf{u}$. We let $E^{+}(w)=\\{x\in\mathcal{A}\mid
wx\in\mathcal{L}(\mathbf{u})\\}$ denote the set of right extensions of $w$ in
$\mathbf{u}$. The _right valence_ $d^{+}(w)=\mathrm{Card}\,E^{+}(w)$ of $w$
(in $\mathbf{u}$) is defined as the number of distinct right extensions of
$w$. _Left extensions_ $E^{-}(w)$ and _left valence_ $d^{-}(w)$ are defined in
a a similar way. A factor whose right valence is at least $2$ is called _right
special_. A factor whose left valence is at least $2$ is called _left
special_. A factor which is both left and right special is called _bispecial_.
The _extension type_ $E_{\mathbf{u}}(w)$ of a factor $w$ of $\mathbf{u}$ is
the set of pairs $(a,b)$ of $\mathcal{A}\times\mathcal{A}$ such that $w$ can
be extended in both directions as $awb$:

$E_{\mathbf{u}}(w)=\\{(a,b)\in\mathcal{A}\times\mathcal{A}\mid
awb\in\mathcal{L}(\mathbf{u})\\}.$

We also use the notation $E_{\mathbf{u}}(w)$ by $E(w)$ when the context is
clear. The _bilateral multiplicity_ of a factor $w$ is the number

$m(w)=\mathrm{Card}\,E(w)-d^{-}(w)-d^{+}(w)+1.$

We have the following fact (see e.g. [CN10, Proposition 4.5.1]) which links
bilateral multiplicity to the notion of bispecial factor: let $w$ be a factor
of a recurrent infinite word such that $m(w)\neq 0$; then, $w$ is bispecial. A
bispecial factor is said _strong_ if $m(w)>0$, _weak_ if $m(w)<0$ and
_neutral_ if $m(w)=0$. A bispecial factor is _ordinary_ if there exist letters
$a,b\in\mathcal{A}$ such that

$\\{(a,b)\\}\subseteq
E(w)\subseteq\left(\\{a\\}\times\mathcal{A}\right)\cup\left(\mathcal{A}\times\\{b\\}\right).$
(1)

An ordinary bispecial factor is neutral, but the converse is not true for
$|\mathcal{A}|>2$. We will use this notion in particular in Section 4.4.

######  Lemma 16.

If a bispecial factor is ordinary, then it is neutral.

###### Proof.

If $w$ is ordinary, then

$\mathrm{Card}\,E(w)=\mathrm{Card}\,E^{-}(w)+\mathrm{Card}\,E^{+}(w)-1$

because $(a,b)\in E(w)$. Thus, we have
$m(w)=\mathrm{Card}\,E(w)-d^{-}(w)-d^{+}(w)+1=0$. ∎

It is convenient to represent the extension type $E(w)$ of a bispecial factor
$w$ in a graphical way. It is often represented as a bipartite graph, but we
choose here a table representation: a cross ($\times$) is drawn at the
intersection of row $a$ and column $b$ if and only if $(a,b)\in E(w)$ (see
Figure 3).

| 1 | 2 | 3
---|---|---|---
1 |  | $\times$ |
2 |  | $\times$ |
3 | $\times$ | $\times$ | $\times$

$m(w)=0$

neutral and ordinary

| 1 | 2 | 3
---|---|---|---
1 |  | $\times$ |
2 |  |  | $\times$
3 | $\times$ | $\times$ | $\times$

$m(w)=0$

neutral but not ordinary

| 1 | 2 | 3
---|---|---|---
1 |  | $\times$ |
2 |  |  |
3 |  |  | $\times$

$m(w)=-1$

weak

| 1 | 2 | 3
---|---|---|---
1 |  |  |
2 |  | $\times$ | $\times$
3 | $\times$ | $\times$ | $\times$

$m(w)=1$

strong

Figure 3: Examples of tables representing the extension type $E(w)$ of a
bispecial factor $w$.

######  Definition 17 (Left equivalence).

Let $w$ and $w^{\prime}$ be two bispecial factors defined on the alphabet
$\mathcal{A}$. We say that their extension types are _left equivalent_ if
there exists a permutation $\tau$ acting on $\mathcal{A}$ such that
$E(w^{\prime})=\\{(\tau(a),b)\mid(a,b)\in E(w)\\}$.

Right equivalence is defined similarly. Left equivalence can be interpreted on
the table representation of the extension type as follows. Indeed one
representation can be obtained from the other by a permutation of the rows:

$\scriptsize E(w)=\begin{array}[]{c|ccc}&1&2&3\\\ \hline\cr 1&&&\times\\\
2&&&\\\ 3&\times&\times&\times\end{array}\quad\quad\quad\text{\normalsize
and}\quad\quad\quad E(w^{\prime})=\begin{array}[]{c|ccc}&1&2&3\\\ \hline\cr
1&\times&\times&\times\\\ 2&&&\times\\\ 3&&&\end{array}$

Substitutions considered in this article preserve the first letter and thus
preserve the right extensions. Then, the notion of left equivalence is
sufficient for our need. But in general, we have the following definition. Of
course if the extension type of $w$ and $w^{\prime}$ are left or right
equivalent, then they are also equivalent. When the extension type of two
words are equivalent, they share common properties. In particular, being
ordinary, strong or weak is preserved under equivalence.

######  Lemma 18.

Let $w$ and $w^{\prime}$ be two bispecial factors such that the extension type
of $w$ and $w^{\prime}$ are equivalent, then

  1. •

$w$ is ordinary (neutral, strong, weak resp.) if and only if $w^{\prime}$ is
ordinary (neutral, strong, weak resp.),

  2. •

$\mathrm{Card}E(w)=\mathrm{Card}E(w^{\prime})$, $d^{-}(w)=d^{-}(w^{\prime})$,
$d^{+}(w)=d^{+}(w^{\prime})$, $m(w)=m(w^{\prime})$,

  3. •

if the extension type of $w$ and $w^{\prime}$ are left equivalent, then
$E^{+}(w)=E^{+}(w^{\prime})$,

  4. •

if the extension type of $w$ and $w^{\prime}$ are right equivalent, then
$E^{-}(w)=E^{-}(w^{\prime})$.

###  3.3 Factor Complexity

Let $p(n)$ be the factor complexity function of the infinite word
$\mathbf{u}$. Two other functions derived from the factor complexity are
useful, namely the sequences of _finite differences of order $1$ and $2$_
respectively of $p(n)$:

$\displaystyle s(n)$ $\displaystyle=$ $\displaystyle p(n+1)-p(n),$ (2)
$\displaystyle b(n)$ $\displaystyle=$ $\displaystyle s(n+1)-s(n).$ (3)

Of course, we have

$\displaystyle p(n)$ $\displaystyle=$ $\displaystyle
p(0)+\sum_{\ell=0}^{n-1}s(\ell),$ (4) $\displaystyle s(n)$ $\displaystyle=$
$\displaystyle s(0)+\sum_{\ell=0}^{n-1}b(\ell).$ (5)

These equations are very useful to compute the complexity function $p(n)$ when
its growth is slow (for example in the case of a linear growth), since in this
case functions $s$ and $b$ take small values. For example, we have $p(n)=n+1$
for all $n$ ($\mathbf{u}$ is thus a Sturmian word) if and only if $s(n)$ is
always equal to $1$, which is also equivalent to the fact that exactly two
letters occur ($p(1)=2$, $s(0)=1$) and that $b(n)$ always takes the value $0$.

In this article, one of our main results is to show that some infinite words
on a three-letter alphabet have complexity $p(n)<3n$. In order to achieve
this, we use the next lemma.

######  Lemma 19.

Suppose $|\mathcal{A}|=3$. Then, $p(n+1)-p(n)\in\\{2,3\\}$ if and only if
$\sum_{\ell=0}^{n-1}b(\ell)\in\\{0,1\\}$. Furthermore, if the sequence of
finite differences of order $2$ is such that

$(b(\ell))_{\ell}=0,\ldots,0,1,0,\ldots,0,-1,0,\ldots,0,1,0,\ldots,0,-1,\ldots$

then $\sum_{\ell=0}^{n-1}b(\ell)\in\\{0,1\\}$.

###### Proof.

Since $|\mathcal{A}|=3$, then $p(1)=3$ and $s(0)=p(1)-p(0)=3-1=2$. We have

$p(n+1)-p(n)=s(n)=s(0)+\sum_{\ell=0}^{n-1}b(\ell)=2+\sum_{\ell=0}^{n-1}b(\ell),$

which yields the proof of the first statement.

The proof of the second one comes from the fact that the first non-zero term
of the sequence $(b(\ell))_{\ell}$ is $+1$. ∎

The finite differences of order $1$ and $2$ of $p(n)$ are related to special
and bispecial factors as explained in [Cas97a]. We state a weaker form (for
recurrent words) of a result of [CN10]. Indeed, as we are interested in the
factor complexity of some recurrent words, we do not need to consider
unioccurrent or exceptional prefixes.

######  Theorem 20.

[CN10, Theorem 4.5.4] Let $\mathbf{u}\in\mathcal{A}^{\mathbb{N}}$ be an
infinite recurrent word. Then, for all $n\in\mathbb{N}$:

$\displaystyle s(n)$ $\displaystyle=$
$\displaystyle\sum_{w\in{\mathcal{L}}_{n}(u)}(d^{+}(w)-1)=\sum_{w\in{\mathcal{L}}_{n}(u)}(d^{-}(w)-1)$
(6) $\displaystyle b(n)$ $\displaystyle=$
$\displaystyle\sum_{w\in{\mathcal{L}}_{n}(u)}m(w).$ (7)

##  4 Bispecial Factors under Arnoux-Rauzy and Poincaré Substitutions

The goal of the next sections is to describe factors of Arnoux-Rauzy-Poincaré
$\mathcal{S}$-adic words. The key ingredient is a synchronization lemma that
allows the desubstitution with respect to the substitutions in $\mathcal{S}$
(Section 4.1). As a consequence for bispecial factors, antecedents (they are
uniquely defined and always bispecial) and bispecial images together with
their possible extensions are described in details in Section 4.2 and 4.3,
respectively. We then can consider the notion of life of a bispecial factor
produced by an $\mathcal{S}$-adic expansion (Section 4.4). So far we still do
not use the restrictions of Proposition 6 on the possible directive sequences
in $\mathcal{S}^{\mathbb{N}}$ (they will be considered only in Section 5).
Section 4.5 illustrates the fact that a quadratic factor complexity can be
reached without these restrictions. We end this section with the introduction
of notions of order on vectors allowing the comparison of abelianized vectors
under the application of substitutions in $\mathcal{S}$ (Section 4.6).

We recall that a Poincaré substitution is of the form $\pi_{jk}:i\mapsto
ijk,j\mapsto jk,k\mapsto k$. An Arnoux-Rauzy substitution is given by
$\alpha_{k}:i\mapsto ik,j\mapsto jk,k\mapsto k$.

###  4.1 Synchronization lemma

From now on, the alphabet is set to $\mathcal{A}=\\{1,2,3\\}$. The next lemma
describes the preimage of a factor under Arnoux-Rauzy (AR) and Poincaré (P)
substitutions. Such statements are classical tools when computing the factor
complexity of fixed points of substitutions.

######  Lemma 21 (Synchronization).

Let $u\in\mathcal{A}^{*}$ and $w$ be a factor of $\alpha_{k}(u)$ for some
$\\{i,j,k\\}=\\{1,2,3\\}$.

  1. (i)

If $w$ is empty or if the first letter of $w$ is $i$ or $j$, then there exist
a unique $v\in\mathcal{A}^{*}$ and a unique $s\in\\{\varepsilon,i,j\\}$ such
that $w=\alpha_{k}(v)\cdot s$.

  2. (ii)

If the first letter of $w$ is $k$, then there exist a unique
$v\in\mathcal{A}^{*}$ and a unique $s\in\\{\varepsilon,i,j\\}$ such that
$w=k\cdot\alpha_{k}(v)\cdot s.$

Let $u\in\mathcal{A}^{*}$ and $w$ be a factor of $\pi_{jk}(u)$ for some
$\\{i,j,k\\}=\\{1,2,3\\}$.

  1. (iii)

If $w$ is empty or if the first letter of $w$ is $i$, then there exist a
unique $v\in\mathcal{A}^{*}$ and a unique $s\in\\{\varepsilon,i,j,ij\\}$ such
that $w=\pi_{jk}(v)\cdot s$.

  2. (iv)

If $w=j$, then there exist a unique $v(=\varepsilon)$ such that
$w=j\cdot\pi_{jk}(v)$.

  3. (v)

If the first letter of $w$ is $j$ and $|w|>1$, then there exist a unique
$v\in\mathcal{A}^{*}$ and a unique $s\in\\{\varepsilon,i,j,ij\\}$ such that
$w=jk\cdot\pi_{jk}(v)\cdot s$.

  4. (vi)

If the first letter of $w$ is $k$, then there exist a unique
$v\in\mathcal{A}^{*}$ and a unique $s\in\\{\varepsilon,i,j,ij\\}$ such that
$w=k\cdot\pi_{jk}(v)\cdot s$.

###### Proof.

The sets $\\{ik,jk,k\\}$ and $\\{ijk,jk,k\\}$ form a prefix code. ∎

######  Definition 22 (Antecedent, extended image).

Let $\sigma=\alpha_{k}$ or $\sigma=\pi_{jk}$, $u\in\mathcal{A}^{*}$ and $w$ be
a factor of $\sigma(u)$. We say that the _antecedent of $w$ under $\sigma$_ is
the unique word $v$ as defined by Lemma 21. If $v$ is the antecedent of a word
$w$, then we say that the word $w$ is an _extended image_ of $v$.

Note that the antecedent is unique, but that a word $v$ may have more than one
extended image. Consider for instance $w_{1}=23\pi_{23}(11)1=231231231$ and
$w_{2}=3\pi_{23}(11)2=31231232$ which are two distinct extended images of
$v=11$. This is why the situation becomes here quite intricate especiallly for
bispecial factors. In fact, it happens that strong and weak bispecial words
appear in pairs: the image of a neutral bispecial factor $v$ can have two
extended images that are bipsecial, with one of them being strong, and the
other one being weak. For more details, see Lemma 36 and Remark 37 below.

We now consider images and antecedents of bispecial factors.

######  Definition 23 (Bispecial extended image).

Let $u\in\mathcal{A}^{*}\cup\mathcal{A}^{\mathbb{N}}$ and $v$ be a factor of
$u$. We shall say that a _bispecial extended image_ $w$ of $v$ under $\sigma$
is a bispecial word of $\sigma(u)$ which is an extended image of $v$ under
$\sigma$.

For example, let $v$ be a bispecial factor and suppose
$E(v)=\\{(1,2),(2,3),(3,1),(3,2),(3,3)\\}$. Then $w=3\pi_{23}(v)$ and
$w^{\prime}=23\pi_{23}(v)$ are both bispecial extended images of $v$ under
$\pi_{23}$. Indeed, we have

$\pi_{23}\left(\\{1v2,2v3,3v1,3v2,3v3\\}\right)=\\{123\pi_{23}(v)23,23\pi_{23}(v)3,3\pi_{23}(v)123,3\pi_{23}(v)23,3\pi_{23}(v)3\\}$

and the extension types are $E(w)=\\{(2,2),(2,3),(3,1),(3,2),(3,3)\\}$ and
$E(w^{\prime})=\\{(1,2),(3,3)\\}$.

The next lemma allows one to relate every bispecial factor to a shorter one
and eventually to the empty word.

######  Lemma 24 (Bispecial extended image growth).

Let $\sigma=\alpha_{k}$ or $\sigma=\pi_{jk}$ and $w\neq\varepsilon$ be a non-
empty bispecial extended image of $v$ under $\sigma$. Then, $|v|<|w|$.

###### Proof.

Suppose that $\sigma=\alpha_{k}$ for some $k\in\\{1,2,3\\}$. Since $w$ is non-
empty, $w$ starts and ends with letter $k$ and from Lemma 21 (ii), the unique
antecedent $v$ of $w$ is such that $w=k\alpha_{k}(v)$. We conclude that
$|v|<|w|$.

Suppose that $\sigma=\pi_{jk}$ for some $\\{i,j,k\\}=\\{1,2,3\\}$. Since $w$
is non-empty, $w$ starts with letter $j$ or $k$ and ends with letter $k$. From
Lemma 21 (iv) and (v), the unique antecedent $v$ of $w$ is such that
$w=k\pi_{jk}(v)$ or $w=jk\pi_{jk}(v)$. In both cases, $|v|<|w|$. ∎

###  4.2 Arnoux-Rauzy substitutions

The case of Arnoux-Rauzy substitutions is particularly convenient to handle,
both for bispecial extended images or for antecedents of bispecial factors.

######  Lemma 25 (AR - Bispecial extended image).

Let $u\in\mathcal{A}^{*}$ and let $v$ be a bispecial factor of $u$. There is a
unique bispecial extended image $w=k\alpha_{k}(v)$ of $v$ in $\alpha_{k}(u)$.

###### Proof.

Let $w$ and $w^{\prime}$ be two extended images of $v$ under $\alpha_{k}$.
Since they are bispecial factors, one deduces from Lemma 21 that both $w$ and
$w^{\prime}$ start and end with letter $k$. Hence
$w=k\alpha_{k}(v)=w^{\prime}$. ∎

######  Lemma 26 (AR - Antecedent of a bispecial).

Let $u\in\\{1,2,3\\}^{*}$ and $w\neq\varepsilon$ be a bispecial factor of
$\alpha_{k}(u)$. Let $v$ be the unique antecedent of $w$ under $\alpha_{k}$.
One has $w=k\alpha_{k}(v)$. Furthermore, $v$ is bispecial and it has the same
extension type $E_{\alpha_{k}(u)}(w)=E_{u}(v)$ and same multiplicity
$m(w)=m(v)$ as $w$.

Figure 4: The preimage of the bispecial word $w$ under $\alpha_{k}$.

###### Proof.

One checks that $(a,b)\in E(v)$ if and only if $(a,b)\in E(k\alpha_{k}(v))$
(see Figure 4). Then $E(k\alpha_{k}(v))=E(v)$. We deduce that
$E^{+}(k\alpha_{k}(v))=E^{+}(v)$ and $E^{-}(k\alpha_{k}(v))=E^{-}(v)$. From
this we conclude that $m(k\alpha_{k}(v))=m(v)$. ∎

###  4.3 Poincaré substitutions

The case of Poincaré substitutions is more delicate to handle as already
illustrated by the following result. We loose here unicity for the bispecial
extended images.

######  Lemma 27 (P - Bispecial extended images).

Let $i,j,k$ such that $\\{i,j,k\\}=\\{1,2,3\\}$. Let $u\in\\{1,2,3\\}^{*}$ and
let $v$ be a bispecial factor of $u$. There are at most two distinct bispecial
extended images of $v$ under $\pi_{jk}$. They are either $k\pi_{jk}(v)$ or
$jk\pi_{jk}(v)$.

###### Proof.

Let $w$ be a bispecial extended image of $v$ under $\pi_{jk}$. Since $w$ is a
bispecial factor, it must start with letter $j$ or $k$ and end with letter
$k$. From Lemma 21, one gets $w\in\\{jk\pi_{jk}(v),k\pi_{jk}(v)\\}$. ∎

The “at most two" of Lemma 27 will be made more precise later in Lemma 30
where conditions will be given for when a bispecial factor has one or two
bispecial extended images under a Poincaré substitution.

In order to get a similar result concerning the antecedent of a bispecial
factor under Poincaré substitutions (see Lemma 29 below), we first need the
following result stated for factors in general which is also used for proving
Lemma 30 and 36.

######  Lemma 28 (P - Extensions).

Let $i,j,k$ such that $\\{i,j,k\\}=\\{1,2,3\\}$. Let $u\in\\{1,2,3\\}^{*}$ and
$v$ be a factor of $u$. We assume that for all $(a,b)\in E(v)$, there exists a
letter $e$ such that $eavb$ is also a factor of $u$. The extensions of $v$ in
$u$ are related to the extensions of $k\pi_{jk}(v)$ and $jk\pi_{jk}(v)$
considered as factors of $\pi_{jk}(u)$:

$\begin{array}[]{l}(i,b)\in E(v)\iff(j,b)\in
E(k\pi_{jk}(v))\quad\text{and}\quad(i,b)\in E(jk\pi_{jk}(v)),\\\ (j,b)\in
E(v)\iff(j,b)\in E(k\pi_{jk}(v))\quad\text{and}\quad(k,b)\in
E(jk\pi_{jk}(v)),\\\ (k,b)\in E(v)\iff(k,b)\in E(k\pi_{jk}(v)).\end{array}$

###### Proof.

First note that $i\notin E^{-}(k\pi_{jk}(v))$ and $j\notin
E^{-}(jk\pi_{jk}(v))$. Note also that the right extensions are preserved by
$\pi_{jk}$ because $\pi_{jk}$ preserves the first letter of words. Let
$(a_{0},b)\in E(v)$, $(a_{1},b)\in E(k\pi_{jk}(v))$ and $(a_{2},b)\in
E(jk\pi_{jk}(v))$ and let us consider each case $a_{0}=i$, $a_{0}=j$ and
$a_{0}=k$ separately (see Figure 5).

Figure 5: The preimage of $k\pi_{jk}(v)$ and $jk\pi_{jk}(v)$ under $\pi_{jk}$.

According to the assumption made on $v$, one checks that if $a_{0}=i$, then
$a_{1}=j$ and $a_{2}=i$; if $a_{0}=j$, then $a_{1}=j$ and $a_{2}=k$; if
$a_{0}=k$, then $a_{1}=k$. The reciprocals are also verified. ∎

In the next lemma, we show that bispecial factors are preserved under
desubstitution by the Poincaré substitution.

######  Lemma 29 (P - Antecedent of a bispecial).

Let $u\in\\{1,2,3\\}^{*}$ and $w\neq\varepsilon$ be a bispecial factor of
$\pi_{jk}(u)$. Let $v$ be the unique antecedent of $w$ under $\pi_{jk}$. One
has either $w=k\pi_{jk}(v)$, or $w=jk\pi_{jk}(v)$. Furthermore, $v$ is a
bispecial factor of $u$.

###### Proof.

The result is a direct consequence of Lemma 28. Since right extensions are
preserved by $\pi_{jk}$, we only need to check that if $w$ has at least two
left extensions then so does $v$.

Suppose that $w=k\pi_{jk}(v)$. Remark that $i\notin E^{-}(w)$. Thus $j,k\in
E^{-}(w)$ since $w$ is bispecial. From Lemma 28, $k\in E^{-}(w)$ implies $k\in
E^{-}(v)$. Also, $j\in E^{-}(w)$ implies that $i\in E^{-}(v)$ or $j\in
E^{-}(v)$. Thus $v$ is bispecial.

Suppose that $w=jk\pi_{jk}(v)$. Since $j\notin E^{-}(w)$, then $i,k\in
E^{-}(w)$. Or course, the existence of $w$ implicitly suppose $j\in
E^{-}(k\pi_{jk}(v))$. Then, $i,j\in E^{-}(v)$. We conclude that $v$ is
bispecial. ∎

Now we want to describe more precisely under which conditions a bispecial word
$v$ has a unique bispecial extended image and provide its extension type as we
were able to do in Lemma 26 for Arnoux-Rauzy substitutions. In general (see
Table 1 and 2), this depends on its left extensions $E^{-}(v)$. However, if
the left valence satisfies $d^{-}(v)=2$, we deduce the unicity of the
bispecial extended image as well as important information on the extension
type of the extended image. Recall that the notion of left equivalence for
extension types was defined in Section 3.2 in Definition 17.

######  Lemma 30 (P - Bispecial extended images in details).

Let $i,j,k$ such that $\\{i,j,k\\}=\\{1,2,3\\}$. Let $u\in\\{1,2,3\\}^{*}$ and
let $v$ be a bispecial factor of $u$. We assume that for all $(a,b)\in E(v)$,
there exists a letter $e$ such that $eavb$ is also a factor of $u$.

  1. (i)

If $d^{-}(v)=2$, $v$ admits a unique bispecial extended image
$w\in\\{k\pi_{jk}(v),jk\pi_{jk}(v)\\}$ under $\pi_{jk}$ and $d^{-}(w)=2$.
Moreover, the extension types $E(v)$ and $E(w)$ (in $\pi_{jk}(u)$) are left
equivalent and are related according to Table 1.

  2. (ii)

If $d^{-}(v)=3$, then $v$ admits either one, or two bispecial extended images
$w\in\\{k\pi_{jk}(v),jk\pi_{jk}(v)\\}$ under $\pi_{jk}$. In any case,
$d^{-}(w)=2$ and the two non-empty rows of $E(w)$ are obtained by projection
of rows of $E(v)$. Furthermore, they are related according to Table 2.

###### Proof.

For each $a\in\\{1,2,3\\}$, let $R_{a}\subseteq\\{1,2,3\\}$ be such that

$E(v)=\bigcup_{a\in\\{1,2,3\\}}\\{a\\}\times R_{a}.$

The set $R_{a}$ denotes the right extensions associated with the left
extension $a\in E^{-}(v)$.
(i) If $d^{-}(v)=2$, then $E^{-}(v)$ is equal to either $\\{i,j\\}$,
$\\{i,k\\}$ or $\\{j,k\\}$. We proceed case by case. If $E^{-}(v)=\\{i,j\\}$,
then $k\pi_{jk}(v)$ is not left special and $jk\pi_{jk}(v)$ is the unique
bispecial extended image of $v$. If $E^{-}(v)=\\{i,k\\}$ or $\\{j,k\\}$, then
$jk\pi_{jk}(v)$ is not left special and $k\pi_{jk}(v)$ is the unique bispecial
extended image of $v$. This is summarized in Table 1 where the information
follows from Lemma 28.

$\begin{array}[]{c|c|c}E(v)&E(k\pi_{jk}(v))&E(jk\pi_{jk}(v))\\\
\hline\cr(\\{i\\}\times R_{i})\cup(\\{j\\}\times
R_{j})&\\{j\\}\times(R_{i}\cup R_{j})&(\\{i\\}\times R_{i})\cup(\\{k\\}\times
R_{j})\\\ (\\{i\\}\times R_{i})\cup(\\{k\\}\times R_{k})&(\\{j\\}\times
R_{i})\cup(\\{k\\}\times R_{k})&\\{i\\}\times R_{i}\\\ (\\{j\\}\times
R_{j})\cup(\\{k\\}\times R_{k})&(\\{j\\}\times R_{j})\cup(\\{k\\}\times
R_{k})&\\{k\\}\times R_{j}\end{array}$ Table 1: If $d^{-}(v)=2$, then exactly
one extended image of $v$ amongst $k\pi_{jk}(v)$ and $jk\pi_{jk}(v)$ is
bispecial. This only depends on the left extensions as the right extensions
are preserved.

In each case, the extension type $E(v)$ is left equivalent to the extension
type of the unique bispecial extended image $w$ of $v$. Moreover $d^{-}(w)=2$.

(ii) If $d^{-}(v)=3$, i.e., $E^{-}(v)=\\{i,j,k\\}$, then
$E^{-}(k\pi_{jk}(v))=\\{j,k\\}$ and $E^{-}(jk\pi_{jk}(v))=\\{i,k\\}$. Thus,
both extended images can be bispecial but their left valence is at most $2$.
This is summarized in Table 2.

$\begin{array}[]{c|c|c}E(v)&E(k\pi_{jk}(v))&E(jk\pi_{jk}(v))\\\
\hline\cr(\\{i\\}\times R_{i})\cup(\\{j\\}\times R_{j})\cup(\\{k\\}\times
R_{k})&(\\{j\\}\times R_{i}\cup R_{j})\cup(\\{k\\}\times R_{k})&(\\{i\\}\times
R_{i})\cup(\\{k\\}\times R_{j})\end{array}$
Table 2: If $d^{-}(v)=3$, then one or both extended images of $v$ amongst
$k\pi_{jk}(v)$ and $jk\pi_{jk}(v)$ are bispecial. In each case, their left
valence is $2$.

∎

Note that Table 1 and 2 provide much more information than does the statement
of Lemma 30 and they will be used to prove a more general result in Lemma 36.
For example, in Table 2, if $v$ is a bispecial factor such that $d^{-}(v)=3$,
$R_{i}=R_{j}$ and $|R_{i}|=|R_{j}|=1$, then $jk\pi_{jk}(v)$ is a left special
factor but not a right special factor, it is thus not bispecial.

###  4.4 Life of a bispecial factor under ARP substitutions

In this section, the life of a bispecial factor is analyzed more precisely
under the application of Arnoux-Rauzy and Poincaré substitutions in the spirit
of [Cas97a, Section 4.2.2] where bispecial factors are described under the
image of circular morphisms. To achieve this, we need to understand exactly
the left extensions which will give information about the multiplicity of the
bispecial factors.

Let $\mathcal{S}=\mathcal{S}_{\alpha}\cup\mathcal{S}_{\pi}.$ Let $w$ be a
factor of an infinite word Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic word. Let
$w_{0}=w$ and $w_{i+1}$ be the unique antecedent of $w_{i}$ under $\sigma_{i}$
for $i\geq 0$. In particular, $w_{1}$ is the antecedent of $w_{0}$ under
$\sigma_{0}$ and $w_{2}$ is the antecedent of $w_{1}$ under $\sigma_{1}$. If
$|w_{i}|>0$, then $|w_{i+1}|<|w_{i}|$ by Lemma 24. There thus exists $n$ such
that $w_{n}=\varepsilon$.

######  Definition 31 (Age, History, Life).

Let $w$ be a factor of an Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic word. Let
$w_{0}=w$ and $w_{i+1}$ be the unique antecedent of $w_{i}$ under $\sigma_{i}$
for $i\geq 0$. The smallest of the integers $n$ for which $w_{n}=\varepsilon$
is called the _age_ of $w$ and is denoted as $\mathrm{age}(w)$. Furthermore,
we say that the finite sequence $\sigma_{0}\sigma_{1}\cdots\sigma_{n}$ is the
_history_ and the sequence $(w_{i})_{0\leq i\leq n}$ is the _life_ of the word
$w$.

Figure 6: Life and history of a factor $w$.

The above definition is illustrated in Figure 6. According to Lemma 26 and 29,
all the words $w_{i}$ of the history of $w$ are bispecial factors when $w$ is
bispecial. We will consider from now on recurrent Arnoux-Rauzy-Poincaré
$\mathcal{S}$-adic words $\mathbf{u}$, with $\mathbf{u}^{(m)}$ being also
recurrent, in order to apply the assumptions of Lemma 28 and 30. According to
Proposition 13, note that this assumption applies in particular to all the
words of the Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic system.

######  Lemma 32.

Let ${\bf u}$ be a recurrent Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic word
such that $\mathbf{u}^{(m)}$ is also recurrent for all $m$. Let $n\geq 0$ be
an integer. Let $B_{n}$ be the set of all bispecial factors of age $n$ in
$\mathbf{u}$. Then $\mathrm{Card}\,B_{n}\leq 2$.

###### Proof.

Let $w\in B_{n}$, $\sigma_{0}\sigma_{1}\cdots\sigma_{n}$ be its history, and
let $(w_{i})_{0\leq i\leq n}$ be its life.

Suppose first that
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}_{\alpha}^{*}\mathcal{S}$,
that is, the substitutions of the history of $w$ are all Arnoux-Rauzy
substitutions except possibly $\sigma_{n}$ which may be a Poincaré
substitution. From Lemma 25, $w_{i}$ is the unique extended image of $w_{i+1}$
for all $0\leq i\leq n-1$. Then $\mathrm{Card}B_{n}=1$.

Suppose now that
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\mathcal{S}$.
Let $\ell$ be the largest index smaller than $n$ of occurrence of $\pi_{jk}$,
that is,

$\sigma_{0}\sigma_{1}\cdots\sigma_{\ell}\in\mathcal{S}^{*}\,\pi_{jk}\quad\text{
and
}\quad\sigma_{\ell+1}\sigma_{\ell+2}\cdots\sigma_{n}\in\mathcal{S}_{\alpha}^{*}\mathcal{S}.$

Then, from Lemma 25, $w_{i}$ is the unique extended image of $w_{i+1}$ for all
$\ell+1\leq i\leq n-1$. Also, from Lemma 30, $w_{\ell+1}$ has at most two
extended images $w_{\ell}$ and $w^{\prime}_{\ell}$ in
$\\{k\pi_{jk}(w_{\ell+1}),jk\pi_{jk}(w_{\ell+1})\\}$. But then,
$d^{-}(w^{\prime}_{\ell})=d^{-}(w_{\ell})=2$ (still by Lemma 30). Therefore
both $w^{\prime}_{\ell}$ has a unique extended image $w^{\prime}_{\ell-1}$ and
$w_{\ell}$ has a unique extended image $w_{\ell-1}$ (by Lemma 30 (i)).
Recursively, we get $d^{-}(w^{\prime}_{i})=d^{-}(w_{i})=2$ for all $0\leq
i\leq\ell$, $w^{\prime}_{i}$ has a unique extended image $w_{i-1}$, and
$w_{i}$ has a unique extended image $w_{i-1}$ for all $1\leq i\leq\ell$. We
thus get $\mathrm{Card}B_{n}\leq 2$. ∎

The life $(w_{i})_{0\leq i\leq n}$ of bispecial factors “starts” (when read
backwards with decreasing indices) as the empty word $\varepsilon$ at $i=n$.
The word $w_{i}$ for $i<n$ is then obtained as the concatenation of one or two
letters concatenated with $\sigma_{i}(w_{i+1})$. These letters depend on the
extension type $E(w_{i+1})$ and recursively on the extension type $E(w_{n})$
of $w_{n}=\varepsilon$. Furthermore, $w_{n}$ is the antecedent of $w_{n-1}$
under $\sigma_{n-1}$ and the extension type $E(w_{n})$ of $w_{n}=\varepsilon$
depends on $\sigma_{n}$. Thus, it is important to understand properly what are
the possible extension types of the empty word under the application of
Arnoux-Rauzy and Poincaré substitutions. Below, the extension type
$E(\varepsilon)$ of the empty word considered as a bispecial factor in the
language of $\sigma(u)$ is denoted by $E_{\sigma(u)}(\varepsilon)$.

######  Lemma 33.

Let $\mathbf{u}\in\mathcal{A}^{*}\cup\mathcal{A}^{\mathbb{N}}$ be a proper
word. Considered as a bispecial factor of the language of the word
$\alpha_{k}(\mathbf{u})$, the empty word $\varepsilon$ is ordinary. Considered
as a bispecial factor of the language of the word $\pi_{jk}(\mathbf{u})$, the
empty word $\varepsilon$ is neutral but not ordinary:

$\scriptsize
E_{\alpha_{k}(\mathbf{u})}(\varepsilon)=\begin{array}[]{c|ccc}&i&j&k\\\
\hline\cr i&&&\times\\\ j&&&\times\\\
k&\times&\times&\times\end{array}\quad\quad\text{\normalsize and}\quad\quad
E_{\pi_{jk}(\mathbf{u})}(\varepsilon)=\begin{array}[]{c|ccc}&i&j&k\\\
\hline\cr i&&\times&\\\ j&&&\times\\\ k&\times&\times&\times\end{array}.$

###### Proof.

We need to consider the set of pairs of consecutive letters appearing in the
language $\alpha_{k}(u)$. These can be consecutive letters inside
$\alpha_{k}(1)$, $\alpha_{k}(2)$ or $\alpha_{k}(3)$, i.e., $\\{ik,jk\\}$.
Alternatively, it may be the last letter of a word $\alpha_{k}(a)$ with the
first letter of a word $\alpha_{k}(b)$: $\\{ki,kj,kk\\}$.

Similarly for the language $\pi_{jk}(u)$, consecutive letters inside
$\pi_{jk}(i)$, $\pi_{jk}(j)$ and $\pi_{jk}(k)$ are $\\{ij,jk\\}$ and pairs
made of the last letter of a word $\pi_{jk}(a)$ with the first letter of a
word $\pi_{jk}(b)$ are $\\{ki,kj,kk\\}$. ∎

From now on, we assume that the Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic words
$\mathbf{u}^{(m)}$ are all proper for all $m$ in order to apply Lemma 33 for
the bispecial factors of all ages. Note that being recurrent does not imply
the fact of being proper: indeed an infinite word can be recurrent on the
alphabet $\\{1,2\\}$ while each letter of the alphabet $\\{1,2,3\\}$ must
appear for this word to be proper.

######  Lemma 34.

Let ${\bf u}$ be an Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic word such that
$\mathbf{u}^{(m)}$ is proper and recurrent for all $m$. Let $w$ be a bispecial
factor of ${\bf u}$. Then $|E(w)|\leq 5$.

###### Proof.

Let $n=\mathrm{age}(w)$ and $(w_{i})_{i}$ be the life of $w$. From Lemmas 26,
30 and 33, we have

$|E(w_{0})|\leq|E(w_{1})|\leq|E(w_{2})|\leq\cdots\leq|E(w_{n})|\leq 5.\qed$

The following lemma shows that the histories of bispecial factors in a same
infinite word ${\bf u}$ are related.

######  Lemma 35.

Let ${\bf u}$ be an Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic word such that
$\mathbf{u}^{(m)}$ is proper and recurrent for all $m$. Let $w$ and $z$ be two
bispecial factors of ${\bf u}$.

  1. (i)

If $\mathrm{age}(w)<\mathrm{age}(z)$, then the history of $w$ is a prefix of
the one of $z$.

  2. (ii)

If $\mathrm{age}(w)=\mathrm{age}(z)$, then $w$ and $z$ have the same history.

###### Proof.

Statement (i) follows from the definition and statement (ii) follows from (i).
∎

In the next lemma, we describe exactly what are the bispecial factors
associated with each possible history. We recall that there are at most two
bispecial factors of the same age for a given history according to Lemma 32.
It has the same history as $w$ according to Lemma 35.

######  Lemma 36.

Let $\mathbf{u}$ be an Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic word such that
$\mathbf{u}^{(m)}$ is proper and recurrent for all $m$. Let $w$ be a bispecial
factor of $\mathbf{u}$ and let $n=\mathrm{age}(w)$. Let $w^{\prime}$ be the
other bispecial factor of the same age as $w$ if it exists. Then the common
history $\sigma_{0}\sigma_{1}\cdots\sigma_{n}$ of $w$ and $w^{\prime}$
determines the left valence, the multiplicity and the extension type of both
$w$ and $w^{\prime}$. More precisely, the multiplicity and the extension type
are described in Table 3, whereas extension types are provided in Figures 7,
8, 9 and 10.

$\begin{array}[]{l|ccc|ccc}\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in&d^{-}(w)&m(w)&\text{ordinary}&d^{-}(w^{\prime})&m(w^{\prime})&\text{ordinary}\\\
\hline\cr\mathcal{S}_{\alpha}^{*}\mathcal{S}_{\alpha}&3&0&\mathrm{yes}\\\
\mathcal{S}_{\alpha}^{*}\mathcal{S}_{\pi}&3&0&\mathrm{no}\\\
\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\alpha_{k}\\}&2&0&\mathrm{yes}\\\
\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\alpha_{i},\alpha_{j}\\}&2&0&\mathrm{yes}&2&0&\mathrm{yes}\\\
\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\pi_{ji},\pi_{ki},\pi_{ij},\pi_{kj}\\}&2&0&\mathrm{yes}&2&0&\mathrm{yes}\\\
\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\pi_{jk},\pi_{ik}\\}&2&+1&\mathrm{no}&2&-1&\mathrm{no}\\\
\end{array}$ Table 3:  Left valence and multiplicity for the (at most two)
bispecial factors of the same age.

######  Remark 37.

Recall that the occurrence of strong and weak bispecial factors has an impact
on the factor complexity. According to Lemma 36, strong and weak bispecial
words appear in pairs under the application of Poincaré substitutions each
time $\pi_{jk}$ is followed by either $\pi_{jk}$ or $\pi_{ik}$ for
$\\{i,j,k\\}=\\{1,2,3\\}$ with possibly some Arnoux-Rauzy substitutions
$\alpha_{k}$, $k\in\\{1,2,3\\}$, in between.

###### Proof.

In the following proof, elements $(j,k)$ of $E(w)$ are noted $jk$ for short.
We refer below to the lines of Table 3.

Line 1. Assume
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}_{\alpha}^{*}\mathcal{S}_{\alpha}$.
According to Lemma 26, the extension type is preserved by Arnoux-Rauzy
substitutions, which yields $E(w)=E_{\sigma_{n}}(\varepsilon)$, so that
$d^{-}(w)=3$. Moreover, since $\sigma_{n}\in\mathcal{S}_{\alpha}$, then
$E_{\sigma_{n}}(\varepsilon)$ is ordinary and the multiplicity is $m(w)=0$ (by
Lemma 33). Also, the bispecial extended images are unique under the
application of each substitution $\sigma_{i}\in\mathcal{S}_{\alpha}$, by Lemma
25.

Line 2. Assume
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}_{\alpha}^{*}\mathcal{S}_{\pi}$.
The proof is the same as for Line 1 except that the extension type of the
empty word $E_{\sigma_{n}}(\varepsilon)$ is not ordinary because
$\sigma_{n}\in\mathcal{S}_{\pi}$ (by Lemma 33).

Line 3-6. We assume
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\mathcal{S}$.
Let $\ell$ be the largest index of occurrence smaller than $n$ of $\pi_{jk}$,
that is,

$\sigma_{0}\sigma_{1}\cdots\sigma_{\ell}\in\mathcal{S}^{*}\,\pi_{jk}\quad\text{
and
}\quad\sigma_{\ell+1}\sigma_{\ell+2}\cdots\sigma_{n}\in\mathcal{S}_{\alpha}^{*}\mathcal{S}.$

The bispecial antecedent of $w$ under the substitution
$\sigma_{0}\sigma_{1}\cdots\sigma_{\ell-1}\in\mathcal{S}^{*}$ is $w_{\ell}$,
and $w_{\ell+1}$ is the bispecial antecedent of $w_{\ell}$ under the
substitution $\sigma_{\ell}=\pi_{jk}$. Since
$\sigma_{\ell+1}\sigma_{\ell+2}\cdots\sigma_{n}\in\mathcal{S}_{\alpha}^{*}\mathcal{S}$,
then $d^{-}(w_{\ell+1})=3$ and $w_{\ell+1}$ has two extended images under
$\sigma_{\ell}=\pi_{jk}$. Moreover, let $w^{\prime}_{\ell}$, with
$w^{\prime}_{\ell}\neq w_{\ell}$, be the other extended image of $w_{\ell+1}$.
One has $w_{\ell},w^{\prime}_{\ell}\in\\{k\pi_{jk}(w_{\ell+1}),\
jk\pi_{jk}(w_{\ell+1})\\}$. Note that the factor $w^{\prime}_{\ell}$ may be
bispecial or not (see e.g. the proof of the case of Line 3 below). The end of
the proof for lines 3-6 follows the same pattern. In fact, the first part
$\sigma_{0}\sigma_{1}\cdots\sigma_{\ell-1}\in\mathcal{S}^{*}$ is always
applied on a bispecial factor $w_{\ell}$ or $w^{\prime}_{\ell}$ with left
valence satisfying $d^{-}(w_{\ell})=d^{-}(w^{\prime}_{\ell})=2$. Therefore,
from Lemma 30 (i) the extension types of $w=w_{0}$ and $w_{\ell}$ are left-
equivalent. Similarly, the extension types of $w^{\prime}=w^{\prime}_{0}$ and
$w^{\prime}_{\ell}$ are left-equivalent (where the $w^{\prime}_{i}$ are
inductively defined as extended images). From Lemma 18, the multiplicity, the
left valence and the fact of being strong, weak or ordinary is preserved by
left-equivalence. Below, we suppose $w_{\ell}=k\pi_{jk}(w_{\ell+1})$ and
$w^{\prime}_{\ell}=jk\pi_{jk}(w_{\ell+1})$.

Figure 7: Life of a bispecial word if
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\alpha_{k}\\}$.

Line 3. We assume
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\alpha_{k}\\}$
(see Figure 7). If $\sigma_{n}=\alpha_{k}$, then
$E(w_{\ell+1})=E_{\sigma_{n}(u)}(\varepsilon)=E_{\alpha_{k}(u)}(\varepsilon)$.
Then from Lemma 30 (ii) and Table 2, we have
$E(w_{\ell+1})=\\{ik,jk,ki,kj,kk\\}$, $E(w_{\ell})=\\{jk,ki,kj,kk\\}$ and
$E(w^{\prime}_{\ell})=\\{ik,kk\\}$. Then $w_{\ell}$ is bispecial ordinary and
$w^{\prime}_{\ell}$ is not bispecial.

Figure 8: Life of a bispecial word if
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\alpha_{i},\alpha_{j}\\}$.
The extension types depicted represent the case $\sigma_{n}=\alpha_{j}$.

Line 4. Assume
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\alpha_{i},\alpha_{j}\\}$
(see Figure 8). If $\sigma_{n}=\alpha_{i}$, then
$E(w_{\ell+1})=E_{\sigma_{n}(u)}(\varepsilon)=E_{\alpha_{i}(u)}(\varepsilon)$.
Then from Lemma 30 (ii) and Table 2, we have
$E(w_{\ell+1})=\\{ii,ij,ik,ji,ki\\}$, $E(w_{\ell})=\\{ji,jj,jk,ki\\}$, and
$E(w^{\prime}_{\ell})=\\{ii,ij,ik,ki\\}$. Then $w_{\ell}$ and
$w^{\prime}_{\ell}$ are both bispecial ordinary.

If $\sigma_{n}=\alpha_{j}$, then
$E(w_{\ell+1})=E_{\sigma_{n}(u)}(\varepsilon)=E_{\alpha_{j}(u)}(\varepsilon)$.
Then from Lemma 30 (ii) and Table 2, we have
$E(w_{\ell+1})=\\{ij,ji,jj,jk,kj\\}$, $E(w_{\ell})=\\{ji,jj,jk,kj\\}$ and
$E(w^{\prime}_{\ell})=\\{ij,ki,kj,kk\\}$. Then $w_{\ell}$ and
$w^{\prime}_{\ell}$ are both bispecial ordinary.

Figure 9: Life of a bispecial word if
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\pi_{ji},\pi_{ki},\pi_{ij},\pi_{kj}\\}$.
The extension types depicted represent the case $\sigma_{n}=\pi_{kj}$.

Line 5. Assume
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\pi_{ji},\pi_{ki},\pi_{ij},\pi_{kj}\\}$
(see Figure 9). If $\sigma_{n}=\pi_{ji}$, then
$E(w_{\ell+1})=E_{\sigma_{n}(u)}(\varepsilon)=E_{\pi_{ji}(u)}(\varepsilon)$.
Then from Lemma 30 (ii) and Table 2, we have
$E(w_{\ell+1})=\\{ii,ij,ik,ji,kj\\}$, $E(w_{\ell})=\\{ji,jj,jk,kj\\}$ and
$E(w^{\prime}_{\ell})=\\{ii,ij,ik,ki\\}$. Then $w_{\ell}$ and
$w^{\prime}_{\ell}$ are both bispecial ordinary.

If $\sigma_{n}=\pi_{ki}$, then
$E(w_{\ell+1})=E_{\sigma_{n}(u)}(\varepsilon)=E_{\pi_{ki}(u)}(\varepsilon)$.
Then from Lemma 30 (ii) and Table 2, we have
$E(w_{\ell+1})=\\{ii,ij,ik,jk,ki\\}$, $E(w_{\ell})=\\{ji,jj,jk,ki\\}$ and
$E(w^{\prime}_{\ell})=\\{ii,ij,ik,kk\\}$. Then $w_{\ell}$ and
$w^{\prime}_{\ell}$ are both bispecial ordinary.

If $\sigma_{n}=\pi_{ij}$, then
$E(w_{\ell+1})=E_{\sigma_{n}(u)}(\varepsilon)=E_{\pi_{ij}(u)}(\varepsilon)$.
Then from Lemma 30 (ii) and Table 2, we have
$E(w_{\ell+1})=\\{ij,ji,jj,jk,ki\\}$, $E(w_{\ell})=\\{jk,jj,jk,ki\\}$ and
$E(w^{\prime}_{\ell})=\\{ij,ki,kj,kk\\}$. Then $w_{\ell}$ and
$w^{\prime}_{\ell}$ are both bispecial ordinary.

If $\sigma_{n}=\pi_{kj}$, then
$E(w_{\ell+1})=E_{\sigma_{n}(u)}(\varepsilon)=E_{\pi_{kj}(u)}(\varepsilon)$.
Then from Lemma 30 (ii) and Table 2, we have
$E(w_{\ell+1})=\\{ik,ji,jj,jk,kj\\}$, $E(w_{\ell})=\\{ji,jj,jk,kj\\}$ and
$E(w^{\prime}_{\ell})=\\{ik,ki,kj,kk\\}$. Then $w_{\ell}$ and
$w^{\prime}_{\ell}$ are both bispecial ordinary.

Figure 10: Life of a bispecial word if
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\pi_{jk},\pi_{ik}\\}$.
The extension types shown represent the case $\sigma_{n}=\pi_{jk}$.

Line 6. Assume
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\\{\pi_{jk},\pi_{ik}\\}$
(see Figure 10). If $\sigma_{n}=\pi_{jk}$, then
$E(w_{\ell+1})=E_{\sigma_{n}(u)}(\varepsilon)=E_{\pi_{jk}(u)}(\varepsilon)$.
Then from Lemma 30 (ii) and Table 2, we have
$E(w_{\ell+1})=\\{ij,jk,ki,kj,kk\\}$, $E(w_{\ell})=\\{jj,jk,ki,kj,kk\\}$ and
$E(w^{\prime}_{\ell})=\\{ij,kk\\}$. Then $w_{\ell}$ is bispecial strong and
$w^{\prime}_{\ell}$ is bispecial weak.

If $\sigma_{n}=\pi_{ik}$, then
$E(w_{\ell+1})=E_{\sigma_{n}}(u)(\varepsilon)=E_{\pi_{ik}(u)}(\varepsilon)$.
Then from Lemma 30 (ii) and Table 2, we have
$E(w_{\ell+1})=\\{ik,ji,ki,kj,kk\\}$, $E(w_{\ell})=\\{ji,jk,ki,kj,kk\\}$ and
$E(w^{\prime}_{\ell})=\\{ik,ki\\}$. Then $w_{\ell}$ is bispecial strong and
$w^{\prime}_{\ell}$ is bispecial weak. ∎

###  4.5 Quadratic complexity is achievable

According to Remark 37, each time $\pi_{jk}$ and $\pi_{ik}$ are found one next
to the other in a certain $\mathcal{S}$-adic sequence, a new pair of strong
and weak bispecial factors is created (see Lemma 36) and the length of a newly
created weak bispecial factor can be larger than the length of an older strong
bispecial factor. Therefore, the complexity can increase by more than $3$,
i.e., $p(n+1)-p(n)>3$ for some values of $n$. Let us illustrate it on the
following example. Let

$\displaystyle u$
$\displaystyle=\pi_{23}\pi_{23}\pi_{13}\pi_{23}\pi_{23}\alpha_{1}\alpha_{3}\alpha_{2}(1)$
$\displaystyle=1232333233123233332331232333333123233323\cdots$

The bispecial factors of $u$ of age $\leq 5$ and their life are shown in
Figure 11. We see that some weak bispecial factors are longer than older
strong bispecial factors. Because of this fact and of Equation (7), the non-
zero values of the sequence $(b(n))_{n}$ do not alternate in the set
$\\{+1,-1\\}$. Therefore, there are values of $n$ for which $s(n)>3$. The
complete computation of $b(n)$, $s(n)$ and $p(n)$ for $n\leq 10$ is given in
Table 4. The complexity $p(n)$ of the finite word $u$ satisfies
$p(n+1)-p(n)=4$ for some values of $n$ and $p(n)>3n+1$ for $n$ such that
$7\leq n\leq 17$ (recall Equations (2), (3), (4), (5), (7) and in particular
that $s(n)=2+\sum_{\ell=0}^{n-1}b(\ell)$ when the size of alphabet is $3$).

Figure 11:  The young bispecial factors of
$u=\pi_{23}\pi_{23}\pi_{13}\pi_{23}\pi_{23}\alpha_{1}\alpha_{3}\alpha_{2}(1)$
of age $\leq 5$ and their life. The factors $3$, $33$, $333$, $3333$ are
strong while $33333$ is neutral. For the age $k$ equal to $2$ and $3$, the
weak factor of age $k$ is longer than the strong factor of age $k+1$. The
quantity under parenthesis indicates the value of $m$.
$\begin{array}[]{c|c|c|c|c|c|c}n&\displaystyle\sum_{\begin{subarray}{c}w\in\mathcal{L}_{n}(u)\\\
w\,\text{is
strong}\end{subarray}}m(w)&\displaystyle\sum_{\begin{subarray}{c}w\in\mathcal{L}_{n}(u)\\\
w\,\text{is weak}\end{subarray}}m(w)&b(n)&s(n)&p(n)&3n+1\\\ \hline\cr
0&0&0&0&2&1&1\\\ 1&+1&0&1&2&3&4\\\ 2&+1&-1&0&3&5&7\\\ 3&+1&0&1&3&8&10\\\
4&+1&-1&0&4&11&13\\\ 5&0&0&0&4&15&16\\\ 6&0&0&0&4&19&19\\\ 7&0&0&0&4&23&22\\\
8&0&0&0&4&27&25\\\ 9&0&-1&-1&4&31&28\\\ 10&0&0&0&3&35&31\\\ \end{array}$
Table 4: The lengths of strong bispecial factors of $u$ are $1$, $2$, $3$, $4$
while the lengths of weak bispecial factors of $u$ are $2$, $4$, $9$, $14$.
Since there are two more strong bispecial factors of length $\leq n$ than the
number of weak bispecial factors of length $\leq n$ for all $n$ such that
$3\leq n\leq 8$, then $s(n)=4$ for each $n$ with $4\leq n\leq 9$. For example,
$s(4)=p(5)-p(4)=s(0)+\sum_{\ell=0}^{3}b(\ell)=4$. Moreover, $p(7)=23>22=3\cdot
7+1$.

In fact the complexity can get higher. It follows from Theorem 4.7.66 of
[CN10, p. 214] that the fixed point of $\pi_{23}\pi_{13}$ starting with letter
$1$ has a quadratic factor complexity because it has infinitely many distinct
factors, namely the factors $3^{n}$, that are bounded (in fact fixed) under
$\pi_{23}\pi_{13}$.

###  4.6 Partial and strict partial order on $\mathbb{R}^{3}$

In this section, we consider two distinct partial orders on $\mathbb{R}^{3}$
and consider how these partial orders are preserved by the application of
Arnoux-Rauzy and Poincaré substitutions. The results allow the understanding
of the growth of bispecial factors and are used in the proof of Theorem 1 in
the next section.

Let
$\overrightarrow{u}=(u_{1},u_{2},u_{3}),\overrightarrow{v}=(v_{1},v_{2},v_{3})\in\mathbb{N}^{3}$
be two abelianized vectors (for two words $u,v$). We define $<$ as the strict
partial order (irreflexive, transitive and thus asymmetric) defined coordinate
per coordinate on $\mathbb{N}^{3}$ by:

$\overrightarrow{u}<\overrightarrow{v}\iff u_{1}<v_{1}\quad\text{and}\quad
u_{2}<v_{2}\quad\text{and}\quad u_{3}<v_{3}.$

Also, we define $\leq$ as the partial order (reflexive, transitive and
antisymmetric) defined coordinate per coordinate on $\mathbb{N}^{3}$:

$\overrightarrow{u}\leq\overrightarrow{v}\iff u_{1}\leq
v_{1}\quad\text{and}\quad u_{2}\leq v_{2}\quad\text{and}\quad u_{3}\leq
v_{3}.$

Moreover, we say that the inequality
$\overrightarrow{u}\leq\overrightarrow{v}$ is _strict on the index $i$_ if
$u_{i}<v_{i}$. Note that $\leq$ is not the reflexive closure of $<$ since it
includes more relations.

The next lemma shows that the relation $<$ is preserved by Arnoux-Rauzy and
Poincaré substitutions and that some stronger conditions are satisfied. These
stronger conditions are used to show at Lemma 39 that the relation $<$ is also
preserved for extended images of factors. In the next lemma and the next
sections, we fix $\mathbf{e}_{1}=(1,0,0)$, $\mathbf{e}_{2}=(0,1,0)$ and
$\mathbf{e}_{3}=(0,0,1)$.

######  Lemma 38.

Let $v,v^{\prime}\in\mathcal{A}^{*}$ be such that
$\overrightarrow{v}<\overrightarrow{v^{\prime}}$. For all
$\\{i,j,k\\}=\\{1,2,3\\}$,

  1. (i)

$\overrightarrow{\alpha_{k}(v)}+2\mathbf{e}_{k}<\overrightarrow{\alpha_{k}(v^{\prime})}$,

  2. (ii)

$\overrightarrow{\pi_{jk}(v)}+\mathbf{e}_{j}+2\mathbf{e}_{k}<\overrightarrow{\pi_{jk}(v^{\prime})}$.

In particular, if $\overrightarrow{v}<\overrightarrow{v^{\prime}}$ then
$\overrightarrow{\alpha_{k}(v)}<\overrightarrow{\alpha_{k}(v^{\prime})}$ and
$\overrightarrow{\pi_{jk}(v)}<\overrightarrow{\pi_{jk}(v^{\prime})}$.

The proof is in the appendix.

The next lemma shows that the relation $<$ is preserved by Arnoux-Rauzy and
Poincaré substitutions from a pair of factors to their extended images.

######  Lemma 39.

Let $\sigma\in\mathcal{S}$. Let $v,v^{\prime},w,w^{\prime}\in\mathcal{A}^{*}$
and suppose $w$ (resp. $w^{\prime}$) is an extended image of $v$ (resp.
$v^{\prime}$) under $\sigma$. If
$\overrightarrow{v}<\overrightarrow{v^{\prime}}$, then
$\overrightarrow{w}<\overrightarrow{w^{\prime}}$.

The proof is in the appendix.

######  Remark 40.

The previous lemma is false for the order $\leq$. Indeed $\pi_{jk}$ does not
preserve the relation $\leq$ for extended images. For example, if
$v=\varepsilon$ and $v^{\prime}=3$, then
$\overrightarrow{v}=(0,0,0)\leq(0,0,1)=\overrightarrow{v^{\prime}}$ but

$\overrightarrow{13\pi_{13}(v)}=\overrightarrow{13}=(1,0,1)\not\leq(0,0,2)=\overrightarrow{33}=\overrightarrow{3\pi_{13}(v^{\prime})},$

and this may even lead after some more substitutions to an inversion of the
order:

$\overrightarrow{3\pi_{23}(13)}=\overrightarrow{31233}=(1,1,3)\geq(0,0,3)=\overrightarrow{333}=\overrightarrow{3\pi_{23}(33)}.$

This example can be seen between age $3$ and $4$ in Figure 11.

##  5 Proof of Theorem 1

We now consider $\mathcal{S}$-adic words $\mathbf{u}$ generated by the Arnoux-
Rauzy-Poincaré algorithm applied to a totally irrational vector
$\mathbf{x}\in\Delta$. By Proposition 12, $\mathbf{u}^{(m)}$ is proper and
uniformly recurrent for all $m$ so the hypothesis introduced in the previous
section is satisfied. Such sequences are in the Arnoux-Rauzy-Poincaré
$\mathcal{S}$-adic system (Type $3$), that is, we take into account the
restrictions on the directive sequences provided by Proposition 6. The
examples in Section 4.5 show that Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic
sequences can lead in general to quadratic factor complexity. Nevertheless we
show that the factor complexity $p(n)$ of $\mathcal{S}$-adic words
$\mathbf{u}$ generated by the Arnoux-Rauzy-Poincaré algorithm applied to a
totally irrational vector satisfy $p(n+1)-p(n)\in\\{2,3\\}$. Thus, their
factor complexity is bounded below and above, that is, $2n+1\leq p(n)\leq
3n+1$ for all $n$. In fact, we even prove that $p(n+1)-p(n)$ is equal to $2$
more often than it is equal to $3$ which implies that
$p(n)\leq\frac{5}{2}n+1$. More precisely, we will show that strong and weak
bispecial words alternate when the length increases in Section 5.1. We then
consider more closely the lengths of consecutive values of $2$ and $3$ in the
sequence $(p(n+1)-p(n))_{n}$ in Section 5.2. By making use of Lemma 19
together with Lemma 44 (see Figure 14), we will be able to prove Theorem 1 in
Section 5.3.

###  5.1 Alternance of strong and weak bispecial factors

We first gather the lemmas required in the proof (see Section 5.3) of the fact
that the $\mathcal{S}$-adic words $\mathbf{u}$ (with $\mathbf{u}^{(m)}$
recurrent for all $m$) such that
$\sigma_{k}\sigma_{k+1}\cdots\sigma_{\ell}\in\mathcal{L}(\mathcal{G})$ (for
all $k,\ell$) provide words that satisfy $p(n+1)-p(n)\in\\{2,3\\}$.

Restricted to the language of the automaton $\mathcal{G}$, illustrated in
Figure 2, the history of a strong or weak bispecial factor necessarily
contains Arnoux-Rauzy substitutions.

######  Lemma 41.

Let $\mathbf{u}=\lim_{n\to\infty}\sigma_{0}\sigma_{1}\cdots\sigma_{n}(a_{n})$
be an $\mathcal{S}$-adic word generated by the Arnoux-Rauzy-Poincaré algorithm
applied to a totally irrational vector $\mathbf{x}\in\Delta$. Let $w$ be a
bispecial factor of $\mathbf{u}$ and let $n=\mathrm{age}(w)$.

If $w$ is weak or strong and the history of $w$ is in the regular language
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{L}(\mathcal{G})$, then

$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\\{\alpha_{j}\\}^{*}\,\alpha_{i}\,\mathcal{S}_{\alpha}^{*}\,\,\\{\pi_{ik},\pi_{jk}\\}$

for some $\\{i,j,k\\}=\\{1,2,3\\}$.

###### Proof.

From Lemma 36, we have

$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\,\mathcal{S}_{\alpha}^{*}\,\\{\pi_{ik},\pi_{jk}\\}$

for some $\\{i,j,k\\}=\\{1,2,3\\}$. Let $p\in\mathcal{S}^{*}\,\pi_{jk}$ and
$q\in\mathcal{S}_{\alpha}^{*}\,\\{\pi_{ik},\pi_{jk}\\}$ such that
$pq=\sigma_{0}\sigma_{1}\sigma_{2}\cdots\sigma_{n}$. The word $p$ starts at
the initial state $\Delta$ and ends in the state $H_{jk}$, the word $q$ starts
from the state $H_{jk}$ and ends in state $H_{jk}$ or $H_{ik}$ (see Figure
12).

Figure 12: The subautomaton of $\mathcal{G}$ describing a path
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}=pq$ such that
$p\in\mathcal{S}^{*}\,\pi_{jk}$ and
$q\in\mathcal{S}_{\alpha}^{*}\,\\{\pi_{ik},\pi_{jk}\\}$.

In the automaton $\mathcal{G}$, the possible transitions issued from state
$H_{jk}$ are $\pi_{ij}$, $\pi_{ji}$, $\pi_{ki}$, $\alpha_{j}$ and $\alpha_{i}$
where only $\alpha_{j}$ (looping on state $H_{jk}$) and $\alpha_{i}$ (going to
state $\Delta$) are allowed by
$q\in\mathcal{S}_{\alpha}^{*}\,\\{\pi_{ik},\pi_{jk}\\}$. Once in state
$\Delta$, $q$ allows loops for each symbol in $\mathcal{S}_{\alpha}$, and
finally the transitions $\pi_{jk}$ or $\pi_{ik}$ (see Figure 12). It follows
from this that

$q\in\\{\alpha_{j}\\}^{*}\,\alpha_{i}\,\mathcal{S}_{\alpha}^{*}\,\,\\{\pi_{ik},\pi_{jk}\\}$

which was to be proved. ∎

######  Lemma 42.

Let $w$ be a bispecial factor of an Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic
word. If for some $\\{i,j,k\\}=\\{1,2,3\\}$,

$\mathrm{history}(w)\in\pi_{jk}\,\mathcal{S}^{*}\alpha_{i}\,\mathcal{S}^{*}\mathcal{S},$

then $\overrightarrow{w}\geq(1,1,1)$.

Figure 13: We suppose here that
$\mathrm{history}(w)\in\pi_{jk}\,\mathcal{S}^{*}\alpha_{i}\,\mathcal{S}^{*}\mathcal{S}$.

###### Proof.

Let $w_{1}$ be the ancestor of $w$ under $\pi_{jk}$. Let $r$ and $n$ be
integers such that $1\leq r<n=\mathrm{age}(w)$ and $w_{r+1}$ is the ancestor
of $w_{r}$ under substitution $\alpha_{i}$ as depicted in Figure 13. We have
that $\overrightarrow{w_{n}}=(0,0,0)$. Also,
$\overrightarrow{w_{r+1}}\geq(0,0,0)$ but $w_{r}=i\alpha_{i}(w_{r+1})$
contains at least one occurence of the letter $i$. Then, $w_{1}$ also contains
at least one occurrence of the letter $i$. Therefore
$\overrightarrow{w}\geq(1,1,1)$, because $\pi_{jk}$ maps $i$ to $ijk$. ∎

In order to prove that $p(n+1)-p(n)\in\\{2,3\\}$ for Arnoux-Rauzy-Poincaré
$\mathcal{S}$-adic words $\mathbf{u}$ such that $\mathbf{u}^{(m)}$ is proper
and recurrent for all $m$, it is sufficient that strong and weak bispecial
words alternate when the length increases because of Lemma 19. More precisely,
if $z_{1}$ and $z_{3}$ are two strong (with multiplicity $+1$) bispecial
factors of a word $\mathbf{u}$ such that $|z_{1}|<|z_{3}|$, then there exists
a weak (with multiplicity $-1$) bispecial factor $z_{2}$ such that
$|z_{1}|<|z_{2}|\leq|z_{3}|$. Note that the notion of alternance was also used
to prove Theorem 4.11.2 in [CN10, p. 238].

######  Lemma 43.

Let $\mathbf{u}$ be an Arnoux-Rauzy-Poincaré $\mathcal{S}$-adic word such that
$\mathbf{u}^{(m)}$ is proper and recurrent for all $m$. Let $z^{+}$ and
$z^{-}$ be two bispecial factors of $\mathbf{u}$ of the same age. Suppose that
$z^{-}$ is weak and $z^{+}$ is strong. Then $|z^{+}|<|z^{-}|$.

###### Proof.

In this proof, we denote by
$\overrightarrow{z^{+}}\leq_{j}\overrightarrow{z^{-}}$ when
$\overrightarrow{z^{+}}\leq\overrightarrow{z^{-}}$ is strict on the coordinate
$j\in\\{1,2,3\\}$.

We prove by induction on the age of bispecial factors that
$\overrightarrow{z^{+}}\leq_{j}\overrightarrow{z^{-}}$ is strict on at least
one coordinate $j\in\\{1,2,3\\}$ with $j\in E^{-}(z^{+})$.

Let us prove the base step of the induction. Suppose that $z^{+}$ and $z^{-}$
have a common neutral bispecial antecedent $v$ thus under the substitution
$\pi_{jk}$ for some $\\{i,j,k\\}=\\{1,2,3\\}$. Then, $z^{+}=k\pi_{jk}(v)$ and
$z^{-}=jk\pi_{jk}(v)$ so that
$\overrightarrow{z^{+}}\leq_{j}\overrightarrow{z^{-}}$ is strict on the
coordinate $j$. Moreover $E^{-}(z^{+})=\\{j,k\\}$ and $E^{-}(z^{-})=\\{i,k\\}$
and hence $j\in E^{-}(z^{+})$.

Suppose now that $z^{+}_{h}$ and $z^{-}_{h}$ are two respectively strong and
weak bispecial factors of a word $u$ of the same age such that
$\overrightarrow{z^{+}_{h}}\leq_{k}\overrightarrow{z^{-}_{h}}$ is strict on at
least one coordinate $k\in E^{-}(z_{h}^{+})$. Let $z^{+}_{h-1}$ and
$z^{-}_{h-1}$ be respectively the unique bispecial extended images of
$z^{+}_{h}$ and $z^{-}_{h}$ under the application of $\sigma_{h-1}$. We want
to show the following implication for proving the induction:

$\overrightarrow{z^{+}_{h}}\leq_{k}\overrightarrow{z^{-}_{h}}\text{ and }k\in
E^{-}(z_{h}^{+})\implies\text{there exists $j$ such that
}\overrightarrow{z^{+}_{h-1}}\leq_{j}\overrightarrow{z^{-}_{h-1}}\text{ and
}j\in E^{-}(z_{h-1}^{+}).$

Since the letters prepended to the left of bispecial extended images depend on
the left extensions by Table 1, if $E^{-}(z^{-}_{h})=E^{-}(z^{+}_{h})$, it is
clear that $E^{-}(z^{-}_{h-1})=E^{-}(z^{+}_{h-1})$ and
$\overrightarrow{z^{+}_{h-1}}\leq_{j}\overrightarrow{z^{-}_{h-1}}$ is strict
for some letter $j\in E^{-}(z^{+}_{h-1})$. Suppose now that
$E^{-}(z^{-}_{h})\neq E^{-}(z^{+}_{h})$ and suppose without lost of generality
that $E^{-}(z^{+}_{h})=\\{2,3\\}$ and $E^{-}(z^{-}_{h})=\\{1,3\\}$. The
possible cases depending on $\sigma_{h-1}$ are described in the following
table:

$\begin{array}[]{c|cc|cc|cc}&&&&&\text{if }k=2&\text{if }k=3\\\
\sigma_{h-1}&z^{+}_{h-1}&E^{-}(z^{+}_{h-1})&z^{-}_{h-1}&E^{-}(z^{-}_{h-1})&\\{j\mid\overrightarrow{z^{+}_{h-1}}\leq_{j}\overrightarrow{z^{-}_{h-1}}\\}&\\{j\mid\overrightarrow{z^{+}_{h-1}}\leq_{j}\overrightarrow{z^{-}_{h-1}}\\}\\\
\hline\cr\alpha_{1}&1\alpha_{1}(z^{+}_{h})&\\{2,3\\}&1\alpha_{1}(z^{-}_{h})&\\{1,3\\}&\\{1,2\\}&\\{1,3\\}\\\
\alpha_{2}&2\alpha_{2}(z^{+}_{h})&\\{2,3\\}&2\alpha_{2}(z^{-}_{h})&\\{1,3\\}&\\{2\\}&\\{2,3\\}\\\
\alpha_{3}&3\alpha_{3}(z^{+}_{h})&\\{2,3\\}&3\alpha_{3}(z^{-}_{h})&\\{1,3\\}&\\{2,3\\}&\\{3\\}\\\
\pi_{12}&2\pi_{12}(z^{+}_{h})&\\{1,2\\}&12\pi_{12}(z^{-}_{h})&\\{2,3\\}&\\{1,2\\}&\\{1,2,3\\}\\\
\pi_{32}&2\pi_{32}(z^{+}_{h})&\\{2,3\\}&32\pi_{32}(z^{-}_{h})&\\{1,2\\}&\\{2,3\\}&\\{2,3\\}\\\
\pi_{13}&3\pi_{13}(z^{+}_{h})&\\{1,3\\}&3\pi_{13}(z^{-}_{h})&\\{1,3\\}&\\{1,2,3\\}&\\{3\\}\\\
\pi_{23}&3\pi_{23}(z^{+}_{h})&\\{2,3\\}&3\pi_{23}(z^{-}_{h})&\\{2,3\\}&\\{2,3\\}&\\{3\\}\\\
\pi_{21}&21\pi_{21}(z^{+}_{h})&\\{1,3\\}&1\pi_{21}(z^{-}_{h})&\\{1,2\\}&\\{1\\}&\\{1,3\\}\\\
\pi_{31}&31\pi_{31}(z^{+}_{h})&\\{1,2\\}&1\pi_{31}(z^{-}_{h})&\\{1,3\\}&\\{1,2\\}&\\{1\\}\end{array}$

We check that for all nine possible values of $\sigma_{h-1}\in\mathcal{S}$, we
always have that
$\overrightarrow{z^{+}_{h-1}}\leq_{j}\overrightarrow{z^{-}_{h-1}}$ is strict
for some $j\in E^{-}(z^{+}_{h-1})$. Since we proved
$\overrightarrow{z^{+}}\leq_{j}\overrightarrow{z^{-}}$ is strict on at least
one coordinate $j$, then we conclude that $|z^{+}|<|z^{-}|$. ∎

######  Lemma 44.

Let $\mathbf{u}=\lim_{n\to\infty}\sigma_{0}\sigma_{1}\cdots\sigma_{n}(a_{n})$
be an $\mathcal{S}$-adic word generated by the Arnoux-Rauzy-Poincaré algorithm
applied to a totally irrational vector $\mathbf{x}\in\Delta$. Let $z^{-}$ and
$w^{+}$ be two bispecial factors of ${\bf u}$ such that $z^{-}$ is weak,
$w^{+}$ is strong, and the history of both $z^{-}$ and $w^{+}$ are in the
regular language
$\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{L}(\mathcal{G})$. If
$\mathrm{age}(z^{-})<\mathrm{age}(w^{+})$, then $|z^{-}|<|w^{+}|$.

Figure 14: Lifes of two pairs of strong and weak bispecial factors: $z^{+}$,
$z^{-}$ and $w^{+}$, $w^{-}$.

###### Proof.

In this proof, we denote a bispecial factor $w$ as $w^{+}$ if it is strong,
$w^{-}$ if it is weak, and with no sign if it is neutral. Let
$m=\mathrm{age}(z^{-})$, $z^{-}_{0}=z^{-}$ and $z_{i+1}$ be the unique
antecedent of $z_{i}$ under $\sigma_{i}$ for $0\leq i\leq m-1$. Let
$n=\mathrm{age}(w^{+})$, $w^{+}_{0}=w^{+}$ and $w_{i+1}$ be the unique
antecedent of $w_{i}$ under $\sigma_{i}$ for $0\leq i\leq n-1$. From Lemma 41,
we have

$\begin{array}[]{l}\mathrm{history}(w^{+})=\sigma_{0}\sigma_{1}\cdots\sigma_{n}\in\mathcal{S}^{*}\,\pi_{jk}\\{\alpha_{j}\\}^{*}\,\alpha_{i}\,\mathcal{S}_{\alpha}^{*}\,\,\\{\pi_{ik},\pi_{jk}\\},\\\
\mathrm{history}(z^{-})=\sigma_{0}\sigma_{1}\cdots\sigma_{m}\in\mathcal{S}^{*}\,\pi_{j^{\prime}k^{\prime}}\\{\alpha_{j^{\prime}}\\}^{*}\,\alpha_{i^{\prime}}\,\mathcal{S}_{\alpha}^{*}\,\,\\{\pi_{i^{\prime}k^{\prime}},\pi_{j^{\prime}k^{\prime}}\\},\end{array}$

for some $\\{i,j,k\\}=\\{1,2,3\\}$ and some other values of
$\\{i^{\prime},j^{\prime},k^{\prime}\\}=\\{1,2,3\\}$. We want to show that
$\overrightarrow{w^{+}}>\overrightarrow{z^{-}}$ in order to conclude that
$|w^{+}|>|z^{-}|$. Let $\ell$ ($h$ resp.) be the largest integer such that
$w^{+}_{\ell}$ ($z^{-}_{h}$ resp.) is strong (weak resp.). The situation is
illustrated in Figure 14.

We have $m\leq\ell$. Indeed, suppose on the contrary that $m>\ell$. We know
that $\sigma_{m}\in\mathcal{S}_{\pi}$. Also,
$\sigma_{i}\in\mathcal{S}_{\alpha}$ for all $\ell+1\leq i\leq n-1$. This
implies that $m\geq n$ which is a contradiction. Hence, $h<m\leq\ell<n$. Since
$\mathrm{history}(w^{+}_{\ell})\in\pi_{jk}\\{\alpha_{j}\\}^{*}\,\alpha_{i}\,\mathcal{S}_{\alpha}^{*}\,\,\\{\pi_{ik},\pi_{jk}\\}$,
from Lemma 42 we have that $\overrightarrow{w^{+}_{\ell}}\geq(1,1,1)$. Then,

$\overrightarrow{z_{m}}=(0,0,0)<(1,1,1)\leq\overrightarrow{w^{+}_{\ell}}\leq\overrightarrow{w^{+}_{m}}.$

Using induction and Lemma 39, we obtain that
$\overrightarrow{z^{-}}<\overrightarrow{w^{+}}$. Then, $|w^{+}|>|z^{-}|$. ∎

###  5.2 Ranges of $2$ and $3$ in the sequence $(p(n+1)-p(n))_{n}$

The next lemma, whose proof requires a deeper understanding of the abelianized
vectors of bispecial factors, will allow us in Section 5.3 to get a more
precise information concerning the alternance of weak and strong bispecial
factors.

Figure 15: Three phases of the lifes of two pairs of strong and weak bispecial
factors: $z^{+}$, $z^{-}$ and $w^{+}$, $w^{-}$.

######  Lemma 45.

Let $\mathbf{u}$ be an $\mathcal{S}$-adic word generated by the Arnoux-Rauzy-
Poincaré algorithm applied to a totally irrational vector
$\mathbf{x}\in\Delta$. Let $w^{+}$ and $w^{-}$ be two bispecial factors of the
same age of $\mathbf{u}$ such that $w^{+}$ is strong and $w^{-}$ is weak. If
there exists a younger weak bispecial factor $z^{-}$ of ${\bf u}$, i.e.,
$\mathrm{age}(z^{-})<\mathrm{age}(w^{+})=\mathrm{age}(w^{-})$, then
$|w^{+}|-|z^{-}|>|w^{-}|-|w^{+}|$. If there is no younger weak bispecial
factor, then $|w^{+}|\geq|w^{-}|-|w^{+}|$.

###### Proof.

The proof is divided into three phases according to the lifes of the bispecial
factors (see Figure 15).

  1. (i)

At the end of Phase A, we have
$\overrightarrow{w_{m}^{+}}-\overrightarrow{z_{m}}\geq\overrightarrow{w_{m}^{-}}-\overrightarrow{w_{m}^{+}}$
is strict on two letters in $\\{1,2,3\\}$.

  2. (ii)

At the end of Phase B, we have
$\overrightarrow{w_{h}^{+}}-\overrightarrow{z_{h}^{-}}>\overrightarrow{w_{h}^{-}}-\overrightarrow{w_{h}^{+}}$
and the words $w_{h}^{-}$ and $w_{h}^{+}$ have the same left extensions.

  3. (iii)

At the end of Phase C, we have
$\overrightarrow{w^{+}}-\overrightarrow{z^{-}}>\overrightarrow{w^{-}}-\overrightarrow{w^{+}}$.

Phase A. Let $\ell$ be the largest index such that $w^{+}_{\ell}\neq
w^{-}_{\ell}$. One has that $w^{+}_{\ell}$ is strong and $w^{-}_{\ell}$ is
weak and their antecent $w^{+}_{\ell+1}=w^{-}_{\ell+1}=w_{\ell+1}$ are equal
and neutral. The bispecial factor $w_{\ell}^{+}$ contains each of the letters
in $\\{1,2,3\\}$ because of Lemma 41 and Lemma 42. Also
$\overrightarrow{w_{\ell}^{-}}-\overrightarrow{w_{\ell}^{+}}=\mathbf{e}_{a}$
for some $a\in\\{1,2,3\\}$. Thus
$\overrightarrow{w_{\ell}^{+}}\geq\overrightarrow{w_{\ell}^{-}}-\overrightarrow{w_{\ell}^{+}}$
is a strict inequality on at least two coordinates. One checks that this
property is preserved by each of the nine possible substitutions. This implies
that
$\overrightarrow{w_{m}^{+}}\geq\overrightarrow{w_{m}^{-}}-\overrightarrow{w_{m}^{+}}$
is strict on at least two letters in $\\{1,2,3\\}$ as well. This also proves
the last part of the lemma, concerning the case where there is no younger weak
bispecial factor.

Phase B. Each of the inequality below is implied by the precedent one. The
substitution $\alpha_{i}$ brings the inequality (by at least two units) on the
coordinate $i$. Then, the substitution $\pi_{jk}$ spreads the strict
inequality on every coordinate:

$\overrightarrow{w_{m}^{+}}-\overrightarrow{z_{m}}\geq\overrightarrow{w_{m}^{-}}-\overrightarrow{w_{m}^{+}}$
is strict on at least two letters in $\\{1,2,3\\}$,
---
$\overrightarrow{w_{t+1}^{+}}-\overrightarrow{z_{t+1}}\geq\overrightarrow{w_{t+1}^{-}}-\overrightarrow{w_{t+1}^{+}}$
is strict on at least two letters in $\\{1,2,3\\}$,
$\overrightarrow{w_{t}^{+}}-\overrightarrow{z_{t}}-2\mathbf{e}_{i}\geq\overrightarrow{w_{t}^{-}}-\overrightarrow{w_{t}^{+}}$,
$\overrightarrow{w_{h+1}^{+}}-\overrightarrow{z_{h+1}}-2\mathbf{e}_{i}\geq\overrightarrow{w_{h+1}^{-}}-\overrightarrow{w_{h+1}^{+}}$,
$\overrightarrow{\pi_{jk}(w_{h+1}^{+})}-\overrightarrow{\pi_{jk}(z_{h+1})}-(2,2,2)\geq\overrightarrow{\pi_{jk}(w_{h+1}^{-})}-\overrightarrow{\pi_{jk}(w_{h+1}^{+})}$,
$\overrightarrow{w_{h}^{+}}-\overrightarrow{z_{h}^{-}}+\mathbf{e}_{j}-(2,2,2)\geq\overrightarrow{w_{h}^{-}}-\overrightarrow{w_{h}^{+}}$,
$\overrightarrow{w_{h}^{+}}-\overrightarrow{z_{h}^{-}}>\overrightarrow{w_{h}^{-}}-\overrightarrow{w_{h}^{+}}$.

The left extensions of $w_{m}^{+}$ and $w_{m}^{-}$ are $\\{j,k\\}$ or
$\\{i,k\\}$. Arnoux-Rauzy substitutions preserve the extensions so that
$E^{-}(w_{h+1}^{+})=E^{-}(w_{m}^{+})$ and
$E^{-}(w_{h+1}^{-})=E^{-}(w_{m}^{-})$. Finally, according to Table 1,
$\pi_{jk}$ projects those left extensions onto the same set
$E^{-}(w_{h+1}^{+})=E^{-}(w_{h+1}^{-})=\\{j,k\\}$.

Phase C. We have
$\overrightarrow{w_{h}^{+}}-\overrightarrow{z_{h}^{-}}>\overrightarrow{w_{h}^{-}}-\overrightarrow{w_{h}^{+}}$.
Since the words $w_{h}^{-}$ and $w_{h}^{+}$ have the same left extensions,
then so do $w_{h-1}^{-}$ and $w_{h-1}^{+}$ for all
$\sigma_{h-1}\in\mathcal{S}_{\pi}$. But the left extensions of $z_{h}^{-}$ can
be different from the one of $w_{h}^{-}$ and $w_{h}^{+}$. This can lead to
$z_{h-1}^{-}=jk\pi_{jk}(z_{h}^{-})$ while $w_{h-1}^{-}=k\pi_{jk}(w_{h}^{-})$
and $w_{h-1}^{+}=k\pi_{jk}(w_{h}^{+})$. Thus, the proof of Phase C relies on
the following recurrences on the age of bispecial factors (all other cases for
left extensions are easier and follow from the same recurrences):

  1. (i)

(Recurrence AR) If
$\overrightarrow{w^{+}}-\overrightarrow{z^{-}}>\overrightarrow{w^{-}}-\overrightarrow{w^{+}}$,
then
$\overrightarrow{\alpha_{k}(w^{+})}-\overrightarrow{\alpha_{k}(z^{-})}>\overrightarrow{\alpha_{k}(w^{-})}-\overrightarrow{\alpha_{k}(w^{+})}$.

  2. (ii)

(Recurrence P) If
$\overrightarrow{w^{+}}-\overrightarrow{z^{-}}>\overrightarrow{w^{-}}-\overrightarrow{w^{+}}$,
then
$\overrightarrow{\pi_{jk}(w^{+})}-\overrightarrow{\pi_{jk}(z^{-})}-\mathbf{e}_{j}>\overrightarrow{\pi_{jk}(w^{-})}-\overrightarrow{\pi_{jk}(w^{+})}$.

Let $\overrightarrow{z^{-}}=(x,y,z)$, $\overrightarrow{w^{+}}=(a,b,c)$,
$\overrightarrow{w^{-}}=(d,e,f)$ where the convention
$\mathbf{e}_{i}=(1,0,0)$, $\mathbf{e}_{j}=(0,1,0)$, $\mathbf{e}_{k}=(0,0,1)$
is used. For the Arnoux-Rauzy recurrence, we have

$\overrightarrow{\alpha_{k}(z^{-})}=(x,y,x+y+z),\quad\overrightarrow{\alpha_{k}(w^{+})}=(a,b,a+b+c),\quad\overrightarrow{\alpha_{k}(w^{-})}=(d,e,d+e+f).$

Then

$\displaystyle\overrightarrow{\alpha_{k}(w^{+})}-\overrightarrow{\alpha_{k}(z^{-})}$
$\displaystyle=$
$\displaystyle\overrightarrow{w^{+}}-\overrightarrow{z^{-}}+(0,0,a-x)+(0,0,b-y)$
$\displaystyle>$
$\displaystyle\overrightarrow{w^{-}}-\overrightarrow{w^{+}}+(0,0,a-x)+(0,0,b-y)$
$\displaystyle\geq$
$\displaystyle\overrightarrow{w^{-}}-\overrightarrow{w^{+}}+(0,0,d-a+1)+(0,0,e-b+1)$
$\displaystyle=$
$\displaystyle\overrightarrow{w^{-}}-\overrightarrow{w^{+}}+(0,0,d-a)+(0,0,e-b)+(0,0,2)$
$\displaystyle=$
$\displaystyle\overrightarrow{w^{-}}-\overrightarrow{w^{+}}+(0,0,d-a)+(0,0,e-b)+(0,0,2)$
$\displaystyle=$ $\displaystyle(d,e,d+e+f)-(a,b,a+b+c)+(0,0,2)$
$\displaystyle=$
$\displaystyle\overrightarrow{\alpha_{k}(w^{-})}-\overrightarrow{\alpha_{k}(w^{+})}+2\mathbf{e}_{k}$

For the Poincaré recurrence, we have

$\overrightarrow{\pi_{jk}(z^{-})}=(x,x+y,x+y+z),\quad\overrightarrow{\pi_{jk}(w^{+})}=(a,a+b,a+b+c),\quad\overrightarrow{\pi_{jk}(w^{-})}=(d,d+e,d+e+f).$

Then

$\displaystyle\overrightarrow{\pi_{jk}(w^{+})}-\overrightarrow{\pi_{jk}(z^{-})}-\mathbf{e}_{j}$
$\displaystyle=$
$\displaystyle\overrightarrow{w^{+}}-\overrightarrow{z^{-}}+(0,a-x,a-x)+(0,0,b-y)-(0,1,0)$
$\displaystyle>$
$\displaystyle\overrightarrow{w^{-}}-\overrightarrow{w^{+}}+(0,a-x,a-x)+(0,0,b-y)-(0,1,0)$
$\displaystyle\geq$
$\displaystyle\overrightarrow{w^{-}}-\overrightarrow{w^{+}}+(0,d-a+1,d-a+1)+(0,0,e-b+1)-(0,1,0)$
$\displaystyle=$
$\displaystyle\overrightarrow{w^{-}}-\overrightarrow{w^{+}}+(0,d-a,d-a)+(0,0,e-b)+(0,0,2)$
$\displaystyle=$
$\displaystyle\overrightarrow{w^{-}}-\overrightarrow{w^{+}}+(0,d-a,d-a)+(0,0,e-b)+(0,0,2)$
$\displaystyle=$ $\displaystyle(d,d+e,d+e+f)-(a,a+b,a+b+c)+(0,0,2)$
$\displaystyle=$
$\displaystyle\overrightarrow{\pi_{jk}(w^{-})}-\overrightarrow{\pi_{jk}(w^{+})}+2\mathbf{e}_{k}.\qed$

###  5.3 Linear growth for the factor complexity

We now have gathered all the elements for proving Theorem 1.

###### Proof of Theorem 1.

Since $\mathbf{x}$ is totally irrational, Proposition 12 certifies that lemmas
of the previous two sections can be applied since the $\mathcal{S}$-adic words
$\mathbf{u}^{(m)}$ are proper and uniformly recurrent for all $m$. The set of
bispecial factors of length $n$ contains at most one weak or strong bispecial
factor. Indeed, suppose on the contrary that it contains two of them: $w$ and
$z$. They cannot have the same age according to Lemma 43 since this would
otherwise imply $|w|\neq|z|$. Also, if one is older, e.g.
$\mathrm{age}(w)>\mathrm{age}(z)$, then $|w|>|z|$ from Lemma 44. Then
$b(n)\in\\{-1,0,+1\\}$ according to Equation (7) of Theorem 20. Finally, it
remains to prove that the assumptions of Lemma 19 are satisfied. The first
non-zero value of $b(n)$ is $+1$ because strong and weak bispecial factors
come in pairs and the strong one is smaller than the weak one from Lemma 43.
Moreover, non-zero values are alternating. Indeed, let $z^{+}$ and $w^{+}$ be
two strong bispecial factors such that
$\mathrm{age}(w^{+})>\mathrm{age}(z^{+})$. Let $z^{-}$ be the weak bispecial
factor such that $\mathrm{age}(z^{-})=\mathrm{age}(z^{+})$. From Lemma 43 and
Lemma 44, $|z^{+}|<|z^{-}|<|w^{+}|$. Hence, there is always a $-1$ between two
$+1$ in the sequence $(b(n))_{n\geq 0}$. This alternance of non-zero values in
the sequence $(b(n))_{n}$ shows that $p(n+1)-p(n)\in\\{2,3\\}$ (Lemma 19), so
that $2n+1\leq p(n)\leq 3n+1$ for $n\geq 0$.

Now we show that $p(n)\leq\frac{5}{2}n+1$. We prove by recurrence that
$p(q+1)\leq\frac{5}{2}(q+1)+1$ for each $q$ such that $b(q)=-1$. By assuming
that $b(-1)=-1$, we remark that the statement is valid for $q=-1$ because
$p(0)=1\leq 1$. Suppose $q$ and $t$ are two consecutive occurrences of $-1$ in
the sequence $(b(\ell))_{\ell}$, that is, $b(q)=b(t)=-1$ and $b(\ell)\neq-1$
for all $\ell$ such that $q<\ell<t$. We show that if
$p(q+1)\leq\frac{5}{2}(q+1)+1$ then $p(n+1)\leq\frac{5}{2}(n+1)+1$ for each
$n$ such that $q<n\leq t$. From the alternance of non-zero values $+1$ and
$-1$ in the sequence $(b(\ell))_{\ell}$, there exists an integer $r$ with
$q<r<t$ such that $b(r)=+1$ and such that for all integers $r^{\prime}\neq r$
with $q<r^{\prime}<t$ then $b(r^{\prime})=0$. Since the first non-zero value
of $(b(\ell))_{\ell\geq 0}$ is $+1$, then $\sum_{\ell=0}^{q}b(\ell)=0$. The
consequence of Lemma 45 is that $r-q>t-r$ which is true if and only if
$\frac{t-q}{2}>t-r$. Note that if $n$ is such that $q<n\leq r$, then
$s(n)=s(0)+\sum_{\ell=0}^{n-1}b(\ell)=2+\sum_{\ell=0}^{q}b(\ell)=2$. Also, if
$n$ is such that $r<n\leq t$, then
$s(n)=s(0)+\sum_{\ell=0}^{n-1}b(\ell)=2+\sum_{\ell=0}^{q}b(\ell)+b(r)=2+1=3$.
Therefore, for each $n$ such that $r<n\leq t$ we have

$\displaystyle p(n+1)-p(q+1)$ $\displaystyle=$
$\displaystyle\sum_{\ell=q+1}^{r}s(\ell)+\sum_{\ell=r+1}^{n}s(\ell)=2(r-q)+3(n-r)$
$\displaystyle=$ $\displaystyle
2(n-q)+(n-r)<2(n-q)+\frac{n-q}{2}=\frac{5}{2}(n-q).$

But since $p(q+1)\leq\frac{5}{2}(q+1)+1$ we conclude that
$p(n+1)\leq\frac{5}{2}(n+1)+1$. We get the same conclusion for each $n$ such
that $q<n\leq r$. From this we conclude that $p(n)\leq\frac{5}{2}n+1$ and
$\limsup_{n\to\infty}\frac{p(n)}{n}\leq\frac{5}{2}$. ∎

We in fact prove the more general result.

######  Theorem 46.

Let $\mathbf{u}$ be a word of the Arnoux-Rauzy-Poincaré system.

  * •

If $\mathbf{u}$ is of Type $1$, then it has a bounded factor complexity.

  * •

If $\mathbf{u}$ is of Type $2$, then its factor complexity satisfies
ultimately $p(n)=n+k$ for some constant $k$.

  * •

If $\mathbf{u}$ is of Type $3$, then $p(n+1)-p(n)\in\\{2,3\\}$ and $2n+1\leq
p(n)\leq\frac{5}{2}n+1$ for all $n\geq 0$.

###### Proof.

Words $\mathbf{u}$ of Type $1$ are periodic and thus have a bounded factor
complexity. A word $\mathbf{u}$ of Type $2$ is an image by a substitution of a
Sturmian sequences. Then, according to [Cas97b], its factor complexity
satisfies ultimately $p(n)=n+k$ for some constant $k$. A word $\mathbf{u}$ of
Type $3$ is weakly primitive, $\mathbf{u}^{(m)}$ is recurrent and proper for
all $m$, and its factor complexity was proven to satisfy the desired bounds in
Theorem 1. ∎

##  6 Convergence and unique ergodicity

We start with some terminology. Let $\mathbf{u}$ be an infinite word in
${\mathcal{A}}^{\mathbb{N}}$. Let $X_{\mathbf{u}}$ be the orbit closure of the
infinite word $\mathbf{u}$ under the action of the shift $S$, that is,
$X_{\mathbf{u}}$ is the closure in ${\mathcal{A}}^{\mathbb{N}}$ of the set
$\\{S^{n}(\mathbf{u})\mid n\in\mathbb{N}\\}=\\{(u_{k})_{k\geq n}\mid
k\in\mathbb{N}\\}$, where the shift $S$ satisfies $S((u_{n})_{n})=(u_{n+1})$.
The set $X_{\mathbf{u}}$ coincides with the set of infinite words whose
language is contained in ${\mathcal{L}}({\mathbf{u}})$, and is called the
_symbolic dynamical system_ generated by $\mathbf{u}$. The topological
dynamical system $(X_{\bf u},S)$ can be endowed with a structure of a measure-
theoretic dynamical system $(X_{u},T,\mu,{\cal B})$, where ${\cal B}$ is a
$\sigma$-algebra, by taking any probability measure $\mu$ preserved by $T$,
that is, for all $B\in\mathcal{B}$, $\mu(S^{-1}(B))=\mu(B)$. The system
$X_{\mathbf{u}}$ is said to be _uniquely ergodic_ if there exists a unique
shift-invariant probability measure on $X$.

One natural way for getting an $S$-invariant measure is to consider factor
frequencies (for more details, see [FM10]). The _frequency_ of a letter $i$ in
$\mathbf{u}$ is defined as the limit when $n$ tends towards infinity, if it
exists, of the number of occurrences of $i$ in $u_{0}u_{1}\cdots u_{n-1}$
divided by $n$. The infinite word $\mathbf{u}$ has _uniform letter
frequencies_ if, for every letter $i$ of $u$, the number of occurrences of $i$
in $u_{k}\cdots u_{k+n-1}$ divided by $n$ has a limit when $n$ tends to
infinity, uniformly in $k$. Similarly, we can define the frequency and the
uniform frequency of a factor, and we say that $u$ has _uniform frequencies_
if all its factors have uniform frequency. The property of having uniform
factor frequencies for a shift $X$ is actually equivalent to unique ergodicity
(see e.g. [FM10]).

Factor complexity is a priori a topological notion. However it may yield (in
particular when it has a linear growth order) measure-theoretical information
on the the symbolic dynamical system $X_{\bf u}$. Indeed, according to
[Bos85], if $\mathbf{u}$ is assumed to be uniformly recurrent, and if $\limsup
p(n)/n<3$, then $(X_{\mathbf{u}},S)$ is uniquely ergodic.

###### Proof of Theorem 2.

We now have gathered all the elements for observing that Theorem 2 is a direct
consequence of Theorem 1 together with the above mentioned result of [Bos85]
and Proposition 12. ∎

##  7 Conclusion

Given a totally irrational vector of frequencies
$\mathbf{x}=(x_{1},x_{2},x_{3})\in\mathbb{R}^{3}_{+}$ (with $\sum x_{i}=1$),
we thus have shown how to construct an infinite word $\mathbf{u}$ over the
alphabet $\mathcal{A}=\\{1,2,3\\}$ such that the frequency of each letter
$i\in\mathcal{A}$ exists and is equal to $x_{i}$, with this word $\mathbf{u}$
having a linear factor complexity. This word is contructed by translating
symbolically within the $S$-adic formalism a multidimensional continued
fraction algorithm, namely the Arnoux-Rauzy-Poincaré algorithm.

Observe that usual proofs of convergence for multidimensional continued
fraction algorithms rely on linear algebra and on the use of the Hilbert
projective metric (see e.g. [Sch00]). Let us stress the fact that we provide
here a purely combinatorial proof of convergence for a two-dimensional
continued fraction algorithm based on the unique ergodicity.

The restriction to the regular language $\mathcal{L}(\mathcal{G})$ is clearly
important; there exist examples of $\mathcal{S}$-adic words constructed with
the alphabet of substitutions $\mathcal{S}$ for which the upper bound
$\frac{5}{2}n+1$ does not hold. Moreover, a quadratic complexity is even also
achievable (see Section 4.5). Hence, the present study gives some more insight
on a statement of the $S$-adic conjecture (it rather should be qualified of
problem) which is to find conditions for which $S$-adic sequences have a
linear complexity (see e.g. [DLR13, Ler12]). Note that any uniformly recurrent
word $\mathbf{u}$ whose complexity function $p(n)$ satisfies
$p(n+1)-p_{u}(n)\leq k$, for all $n$, is $S_{k}$-adic, with a set $S_{k}$ of
substitutions that depends on $k$ ([Fer96]).

The upper bound $\limsup_{n\to\infty}\frac{p(n)}{n}\leq\frac{5}{2}$ is not
sharp. Numerical experimentations tend to indicate that the worst case in the
language $\mathcal{L}(\mathcal{G})$ of the Arnoux-Rauzy-Poincaré algorithm is
obtained with the fixed point of $\pi_{23}\alpha_{1}$ for which the value is
approximately $\limsup_{n\to\infty}\frac{p(n)}{n}\approx 2.26079201$.

Factor complexity of Poincaré and Arnoux-Rauzy substitutions can be described
exactly by considering left and right extensions of length one. It is not
always the case, and the study of Brun substitutions (provided by the Brun
multidimensional continued fraction algorithm) seems to be an example for
which extensions of length longer than one are necessary to describe bispecial
factors. Recently, Klouda [Klo12] described bispecial factors in fixed points
of morphisms where extensions of length longer than one were considered.
Extending this work to $S$-adic words deserves further research.

Balance properties of the Poincaré and Arnoux-Rauzy $S$-adic system have also
nice properties and their study should be done more deeply. An infinite word
$\mathbf{u}\in{\mathcal{A}}^{\mathbb{N}}$ is said to be $C$-balanced if for
any pair $v,w$ of factors of the same length of $\mathbf{u}$, and for any
letter $i\in\mathcal{A}$, one has $||v|_{i}-|w|_{i}|\leq C$. It is said
balanced if there exists $C>0$ such that it is $C$-balanced. For example, it
was proven in [DHS13] that words generated by Brun algorithm gives almost
everywhere balanced sequences. Balance properties are intimately connected
with Diophantine properties of the algorithm. Indeed, an infinite word
$\mathbf{u}\in{\mathcal{A}}^{\mathbb{N}}$ is balanced if and only if it has
uniform letter frequencies and there exists a constant $B$ such that for any
factor $w$ of $u$, we have $||w|_{i}-f_{i}|w||\leq B$ for all letter $i$ in
${\mathcal{A}}$, where $f_{i}$ is the frequency of $i$.

##  8 Appendix

###### Proof of Proposition 6.

We define

$\widetilde{\mathcal{P}}=\\{A_{j}H_{jk}:\\{i,j,k\\}=\\{1,2,3\\}\\}\cup\\{P_{jk}H_{jk}:\\{i,j,k\\}=\\{1,2,3\\}\\}$

which describes another partition of $\Delta$ into 12 triangles shown in
Figure 16.

First, we show that the transformation $T$ is a Markov transformation for the
partition $\widetilde{\mathcal{P}}$.

Figure 16: The Markov partition $\widetilde{\mathcal{P}}$ of Arnoux-Rauzy-
Poincaré algorithm.

Let $\\{i,j,k\\}=\\{1,2,3\\}$. The image of $A_{j}H_{jk}$ and of
$P_{jk}H_{jk}$ under $T$ are the same and are equal to the half triangle
$H_{jk}$:

$T(A_{j}H_{jk})=T(P_{jk}H_{jk})=H_{jk}.$

But the half triangle $H_{jk}$ is a union of elements of
$\widetilde{\mathcal{P}}$:

$H_{jk}=A_{i}H_{ik}\cup A_{i}H_{ij}\cup A_{j}H_{jk}\cup P_{ij}H_{ij}\cup
P_{ji}H_{ji}\cup P_{ki}H_{ki}.$

Thus, the transformation $T$ is a Markov transformation for the partition
$\widetilde{\mathcal{P}}$. This defines an automaton
$\widetilde{G}=(\widetilde{\mathcal{P}},\widetilde{\Sigma},\widetilde{\delta},\widetilde{I},\widetilde{F})$
where the alphabet is

$\widetilde{\Sigma}=\\{A_{1}^{-1},A_{2}^{-1},A_{3}^{-1},P_{31}^{-1},P_{13}^{-1},P_{23}^{-1},P_{32}^{-1},P_{12}^{-1},P_{21}^{-1}\\},$

the transitions are

$\widetilde{\delta}=\\{(p,M,q)\in\widetilde{\mathcal{P}}\times\widetilde{\Sigma}\times\widetilde{\mathcal{P}}:q\subseteq
M\cdot p=T(p)\\},$

or, more precisely,

$\widetilde{\delta}=\left\\{\begin{array}[]{ll}A_{j}H_{jk},A_{j}^{-1}\to
A_{i}H_{ik},&P_{jk}H_{jk},P_{jk}^{-1}\to A_{i}H_{ik},\\\
A_{j}H_{jk},A_{j}^{-1}\to A_{i}H_{ij},&P_{jk}H_{jk},P_{jk}^{-1}\to
A_{i}H_{ij},\\\ A_{j}H_{jk},A_{j}^{-1}\to
A_{j}H_{jk},&P_{jk}H_{jk},P_{jk}^{-1}\to A_{j}H_{jk},\\\
A_{j}H_{jk},A_{j}^{-1}\to P_{ij}H_{ij},&P_{jk}H_{jk},P_{jk}^{-1}\to
P_{ij}H_{ij},\\\ A_{j}H_{jk},A_{j}^{-1}\to
P_{ji}H_{ji},&P_{jk}H_{jk},P_{jk}^{-1}\to P_{ji}H_{ji},\\\
A_{j}H_{jk},A_{j}^{-1}\to P_{ki}H_{ki},&P_{jk}H_{jk},P_{jk}^{-1}\to
P_{ki}H_{ki}\end{array}\text{for each }\,\\{i,j,k\\}=\\{1,2,3\\}\right\\},$

the initial states and final states are all of the twelve states, i.e.,
$\widetilde{I}=\widetilde{F}=\widetilde{\mathcal{P}}$. The automaton
$\widetilde{G}$ recognize all the expansions of the Arnoux-Rauzy-Poincaré
continued fraction algorithm. It is clearly not deterministic. A minimized and
deterministic version of it is the automaton $\mathcal{G}$ shown in Figure 2
where the alphabet considered is
$\mathcal{S}=\\{\alpha_{1},\alpha_{2},\alpha_{3},\pi_{31},\pi_{13},\pi_{23},\pi_{32},\pi_{12},\pi_{21}\\}$
instead of $\widetilde{\Sigma}$. In fact, amongst all the elements of
$2^{\widetilde{\mathcal{P}}}$ considered in the determinization process, only
the states in the set
$Q=\\{\Delta,H_{12},H_{13},H_{21},H_{23},H_{31},H_{32}\\}$ survive the
minimization. ∎

###### Proof of Lemma 38.

(i) Let
$\overrightarrow{z}=(z_{1},z_{2},z_{3})=\overrightarrow{\alpha_{k}(v)}$. Let
$\overrightarrow{z^{\prime}}=(z^{\prime}_{1},z^{\prime}_{2},z^{\prime}_{3})=\overrightarrow{\alpha_{k}(v^{\prime})}$.
We have

$\left\\{\begin{array}[]{l}z_{i}=v_{i}\\\ z_{j}=v_{j}\\\
z_{k}=v_{i}+v_{j}+v_{k}\end{array}\right.\quad\text{and}\quad\left\\{\begin{array}[]{l}z^{\prime}_{i}=v^{\prime}_{i}\\\
z^{\prime}_{j}=v^{\prime}_{j}\\\
z^{\prime}_{k}=v^{\prime}_{i}+v^{\prime}_{j}+v^{\prime}_{k}.\end{array}\right.$

Then

$z_{k}+2=v_{i}+v_{j}+v_{k}+2=(v_{i}+1)+(v_{j}+1)+(v_{k}+1)-1\leq
v^{\prime}_{i}+v^{\prime}_{j}+v^{\prime}_{k}-1<z^{\prime}_{k}$

and $\overrightarrow{z}+2e_{k}<\overrightarrow{z^{\prime}}$.
(ii) Let
$\overrightarrow{z}=(z_{1},z_{2},z_{3})=\overrightarrow{\pi_{jk}(v)}$. Let
$\overrightarrow{z^{\prime}}=(z^{\prime}_{1},z^{\prime}_{2},z^{\prime}_{3})=\overrightarrow{\pi_{jk}(v^{\prime})}$.
We have

$\left\\{\begin{array}[]{l}z_{i}=v_{i}\\\ z_{j}=v_{i}+v_{j}\\\
z_{k}=v_{i}+v_{j}+v_{k}\end{array}\right.\quad\text{and}\quad\left\\{\begin{array}[]{l}z^{\prime}_{i}=v^{\prime}_{i}\\\
z^{\prime}_{j}=v^{\prime}_{i}+v^{\prime}_{j}\\\
z^{\prime}_{k}=v^{\prime}_{i}+v^{\prime}_{j}+v^{\prime}_{k}\end{array}\right.$

As above we have $z_{k}+2<z^{\prime}_{k}$. Moreover,

$z_{j}+1=v_{i}+v_{j}+1=(v_{i}+1)+(v_{j}+1)-1\leq
v^{\prime}_{i}+v^{\prime}_{j}-1<z^{\prime}_{j}.$

Then $\overrightarrow{z}+e_{j}+2e_{k}<\overrightarrow{z^{\prime}}$. ∎

###### Proof of Lemma 39.

(i) Under Arnoux-Rauzy substitution, the extended image of $v$ and
$v^{\prime}$ are uniquely determined: $w=k\alpha_{k}(v)$ and
$w^{\prime}=k\alpha_{k}(v^{\prime})$. From Lemma 38,
$\overrightarrow{\alpha_{k}(v)}<\overrightarrow{\alpha_{k}(v^{\prime})}$. Then

$\overrightarrow{w}=\overrightarrow{\alpha_{k}(v)}+e_{k}<\overrightarrow{\alpha_{k}(v^{\prime})}+e_{k}=\overrightarrow{w^{\prime}}.$

(ii) The proof is divided into four disjoint cases depending on the values of
$w\in\\{jk\pi_{jk}(v),k\pi_{jk}(v)\\}$ and
$w^{\prime}\in\\{jk\pi_{jk}(v^{\prime}),k\pi_{jk}(v^{\prime})\\}$. The proof
relies on the fact that
$\overrightarrow{\pi_{jk}(v)}<\overrightarrow{\pi_{jk}(v^{\prime})}$ but only
the fourth case makes a stronger use of Lemma 38, i.e.,
$\overrightarrow{\pi_{jk}(v)}+e_{j}<\overrightarrow{\pi_{jk}(v^{\prime})}$.

(ii.i) If $w=jk\pi_{jk}(v)$ and $w^{\prime}=jk\pi_{jk}(v^{\prime})$, then

$\overrightarrow{w}=\overrightarrow{\pi_{jk}(v)}+e_{j}+e_{k}<\overrightarrow{\pi_{jk}(v^{\prime})}+e_{j}+e_{k}=\overrightarrow{w^{\prime}}.$

(ii.ii) If $w=k\pi_{jk}(v)$ and $w^{\prime}=k\pi_{jk}(v^{\prime})$, then

$\overrightarrow{w}=\overrightarrow{\pi_{jk}(v)}+e_{k}<\overrightarrow{\pi_{jk}(v^{\prime})}+e_{k}=\overrightarrow{w^{\prime}}.$

(ii.iii) If $w=k\pi_{jk}(v)$ and $w^{\prime}=jk\pi_{jk}(v^{\prime})$, then

$\overrightarrow{w}=\overrightarrow{\pi_{jk}(v)}+e_{k}<\overrightarrow{\pi_{jk}(v^{\prime})}+e_{j}+e_{k}=\overrightarrow{w^{\prime}}.$

(ii.iv) If $w=jk\pi_{jk}(v)$ and $w^{\prime}=k\pi_{jk}(v^{\prime})$, then

$\overrightarrow{w}=\overrightarrow{\pi_{jk}(v)}+e_{j}+e_{k}<\overrightarrow{\pi_{jk}(v^{\prime})}+e_{k}=\overrightarrow{w^{\prime}}.\qed$

## References

  * [Ada03] B. Adamczewski.  Balances for fixed points of primitive substitutions.  Theoret. Comput. Sci., 307(1):47–75, 2003.
  * [And03] E. Andres.  Discrete linear objects in dimension $n$: the standard model.  Graphical Models, 65:92–111, 2003.
  * [AR91] P. Arnoux and G. Rauzy.  Représentation géométrique de suites de complexité 2n+1.  Bull. Soc. Math. France, 119(2):199–215, 1991.
  * [Bar95] Y. Baryshnikov.  Complexity of trajectories in rectangular billiards.  Comm. Math. Phys., 174(1):43–56, 1995.
  * [BD14] V. Berthé and V. Delecroix.  Beyond substitutive dynamical systems: $S$-adic expansions.  To appear in RIMS Lecture note ‘Kokyuroku Bessatu’, 2014.
  * [Bed03] N. Bedaride.  Billiard complexity in rational polyhedra.  Regul. Chaotic Dyn., 8(1):97–104, 2003.
  * [BL11] V. Berthé and S. Labbé.  Uniformly balanced words with linear complexity and prescribed letter frequencies.  In P. Ambrož, Š. Holub, and Z. Masáková, editors, Proc. 8th Int. Conf. on Words, Prague, Czech Republic, September 12-16th, 2011, volume 63 of Electronic Proceedings in Theoretical Computer Science, pages 44–52. Open Publishing Association, 2011.
  * [BL13] V. Berthé and S. Labbé.  Convergence and factor complexity for the Arnoux-Rauzy-Poincaré algorithm.  In WORDS, volume 8079 of Lecture Notes in Computer Science, pages 71–82. Springer, 2013.
  * [Bos85] M. Boshernitzan.  A unique ergodicity of minimal symbolic flows with linear block growth.  J. Analyse Math., 44:77–96, 1984/85.
  * [Bre81] A. J. Brentjes.  Multidimensional continued fraction algorithms.  Mathematisch Centrum, Amsterdam, 1981.
  * [Cas97a] J. Cassaigne.  Complexité et facteurs spéciaux.  Bull. Belg. Math. Soc. Simon Stevin, 4(1):67–88, 1997.  Journées Montoises (Mons, 1994).
  * [Cas97b] Julien Cassaigne.  Sequences with grouped factors.  In Symeon Bozapalidis, editor, Developments in Language Theory, pages 211–222. Aristotle University of Thessaloniki, 1997.
  * [CN10] J. Cassaigne and F. Nicolas.  Factor complexity.  In Combinatorics, automata and number theory, volume 135 of Encyclopedia Math. Appl., pages 163–247. Cambridge Univ. Press, Cambridge, 2010.
  * [DHS13] V. Delecroix, T. Hejda, and W. Steiner.  Balancedness of Arnoux-Rauzy and Brun words.  In J. Karhumäki, A. Lepistö, and L. Q. Zamboni, editors, WORDS, volume 8079 of Lecture Notes in Computer Science, pages 119–131. Springer, 2013.
  * [DLR13] F. Durand, J. Leroy, and G. Richomme.  Do the Properties of an S-adic Representation Determine Factor Complexity?  Journal of Integer Sequences, 16(Article 13.2.6), 2013.
  * [Dur03] F. Durand.  Corrigendum and addendum to: “Linearly recurrent subshifts have a finite number of non-periodic subshift factors” [Ergodic Theory Dynam. Systems 20 (2000), no. 4, 1061–1078; MR1779393 (2001m:37022)].  Ergodic Theory Dynam. Systems, 23(2):663–669, 2003.
  * [Fer96] S. Ferenczi.  Rank and symbolic complexity.  Ergodic Theory Dynam. Systems, 16(4):663–682, 1996.
  * [FM10] S. Ferenczi and T. Monteil.  Infinite words with uniform frequencies, and invariant measures.  In Combinatorics, automata and number theory, volume 135 of Encycl. Math. Appl., pages 373–409. Cambridge Univ. Press, 2010.
  * [Fog02] N. Pytheas Fogg.  Substitutions in dynamics, arithmetics and combinatorics, volume 1794 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 2002.  Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel.
  * [Klo12] K. Klouda.  Bispecial factors in circular non-pushy D0L languages.  Theoret. Comput. Sci., 445:63–74, 2012.
  * [Lab12] S. Labbé.  Structure des pavages, droites discrètes 3D et combinatoire des mots.  PhD thesis, Université du Québec à Montréal, May 2012.
  * [Ler12] J. Leroy.  Some improvements of the $S$-adic conjecture.  Adv. in Appl. Math., 48(1):79–98, 2012.
  * [Lot02] M. Lothaire.  Algebraic Combinatorics on Words.  Cambridge University Press, Cambridge, 2002.
  * [Nog95] A. Nogueira.  The three-dimensional Poincaré continued fraction algorithm.  Israel J. Math., 90(1-3):373–401, 1995.
  * [Sch00] F. Schweiger.  Multidimensional continued fractions.  Oxford Science Publications. Oxford University Press, Oxford, 2000.
  * [Zor97] A. Zorich.  Deviation for interval exchange transformations.  Ergodic Theory Dynam. Systems, 17(6):1477–1499, 1997.