A word of low complexity without uniform frequencies

Abstract

In this paper, we construct a uniformly recurrent infinite word of low complexity without uniform frequencies of letters. This shows the optimality of a bound of Boshernitzan, which gives a sufficient condition for a uniformly recurrent infinite word to admit uniform frequencies.

1 Introduction

Let us consider an infinite word u over a finite alphabet. We can naturally associate a subshift with it. The goal of this paper is to describe some ergodic properties of this subshift. By Oxtoby’s theorem, we know that the subshift is uniquely ergodic if and only if, in u, each finite word has uniform frequency. Moreover, the subshift is minimal if u is uniformly recurrent.

For a long time, people have tried to find some conditions on infinite words which imply one of these properties. Keane gave in [7] a uniformly recurrent infinite word with complexity $3n+1$ (from a 4-interval exchange map) which does not have uniform frequencies. Later, Boshernitzan, in [2], proved that a uniformly recurrent infinite word admits uniform frequencies if either of the following sufficient conditions is satisfied:

$$ \begin{align*} \liminf\frac{\mathbf{p}(n)}{n}<2 \quad \textrm{or} \quad \limsup\frac{\mathbf{p}(n)}{n}<3, \end{align*} $$

where $\mathbf {p}$ denotes the complexity function of u (see [1, Ch. 4, by Cassaigne and Nicolas], for more details on the subject).

The bound of the second sufficient condition of Boshernitzan being already optimal by Keane’s result, our goal in this work is to establish the optimality of the bound of the first sufficient condition. Additionally, we succeed to construct a uniformly recurrent infinite word without uniform frequencies, the complexity function of which satisfies $\liminf \, {\mathbf {p}(n)}/{n}~=~2$ .

This result can be viewed as part of the more general question of relating some properties of the complexity function and of the ergodic measures of a subshift. The goal is then to bound the number of ergodic measures of the subshift in terms of the complexity function.

Boshernitzan was the first to look at this question, see [2]. During his PhD thesis, see [8, Ch. 5] and [1, Ch. 7, by Ferenczi and Monteil], Monteil has proved the same result with different techniques: if $\limsup {\mathbf {p}(n)}/{n} < K$ for some integer $K\geq 3$ , then the subshift has at most $K-2$ ergodic measures. Since that time, more results have appeared in the same vein. Cyr and Kra have also obtained similar results, see [4, 5]. In the first paper, they prove that the bound of Boshernitzan is sharp. In the second one, they construct minimal subshifts with complexity function arbitrarily close to linear but having uncountably many ergodic measures. We can also cite Damron and Fickenscher [6] who obtained the bound ${K+1}/{2}$ under a condition on the bispecial words.

The construction presented in this paper was first announced at a conference in 2007, and published without proof in [1] (Proposition 7.5.12). For several reasons, including the fact that the more general results discussed above had appeared in the meantime, its complete proof was not published then. Nevertheless, it was pointed out to us that our proof is of a different nature, with an explicit construction of the infinite word, and that it was thus interesting by itself.

After the preliminaries (§2), we construct an infinite word in §3, then we show in §4 that this word is without uniform frequencies of letters, we study the complexity of this word in §5, and finally we prove that it is uniformly recurrent in §6.

2 Preliminaries

In all that follows, we consider the alphabet $\mathcal {A}=\lbrace 0, 1\rbrace $ . Let $\mathcal {A}^\ast $ denote the set of the finite words on alphabet $\mathcal {A}$ , and $\varepsilon $ the empty word. For all u in $\mathcal {A}^\ast $ , $|u|$ denotes the length of the word u (the number of letters it contains, with $|\varepsilon |=0$ ) and for any letter x of $\mathcal {A}$ , $|u|_x$ denotes the number of occurrences of the letter x in u. We call the Parikh vector of a finite word u the vector denoted by U and defined by $U=(\begin {smallmatrix}|u|_0\\ |u|_1 \end {smallmatrix}). $

A finite word u of length n formed by repeating a single letter x is typically denoted by $x^n$ . We define the nth power of a finite word w as being the concatenation of n copies of w; it is denoted by $w^n$ . An infinite word is an infinite sequence of letters of $\mathcal {A}$ . Let $\mathcal {A}^\omega $ denote the set of infinite words on $\mathcal {A}$ .

We say that a finite word v is a factor of u if there exist two words $u_1$ and $u_2$ on the alphabet $\mathcal {A}$ such that $u=u_1vu_2$ ; we also say that u contains v. The number of different pairs $(u_1,u_2)$ such that $u=u_1vu_2$ is called the number of occurrences of v in u and is denoted by $|u|_v$ , generalizing the notation $|u|_x$ for $x\in \mathcal {A}$ defined above. The factor v is said to be a prefix (respectively suffix) of u if $u_1$ (respectively $u_2$ ) is the empty word. For any word u, the set of factors of length n is denoted by $\mathcal {L}_n(u)$ . The set of all factors of u is simply denoted by $\mathcal {L}(u)$ .

Definition 2.1. Let u be an infinite word on the alphabet $\mathcal {A}=\lbrace 0, 1\rbrace $ . A factor v of u is said to be:

1. • a right special factor if $v0$ and $v1$ are both factors of u, and a left special factor if $0v$ and $1v$ are both factors of u;

2. • a bispecial factor of u if v is simultaneously a right special factor and a left special factor of u;

3. • a strong bispecial factor of u if $0v0,\ 0v1,\ 1v0,\ 1v1$ are factors of u and a weak bispecial factor if uniquely $0v0$ and $1v1$ , or $0v1$ and $1v0$ , are factors of u;

4. • a neutral bispecial factor of u if v is a bispecial factor of u which is neither strong nor weak.

An infinite word u is said to be recurrent if any factor of u appears infinitely often. An infinite word u is uniformly recurrent if for all $n\in \mathbb {N}$ , there exists N such that any factor of u of length N contains all the factors of u of length n.

Definition 2.2. Let u be an infinite word on an alphabet $\mathcal {A}$ . The complexity function of u is a function counting the number of distinct factors of u of length n for any given n. It is denoted by $\mathbf {p}$ and satisfies

$$ \begin{align*} \mathbf{p}(n)=\#\mathcal{L}_n(u). \end{align*} $$

We also define the functions $\mathbf {s}$ and $\mathbf {b}$ , respectively called first difference and second difference of the complexity of u, as follows: $\mathbf {s}(n)= \mathbf {p}(n+1)-\mathbf {p}(n)$ and $\mathbf {b}(n)=\mathbf {s}(n+~1)-\mathbf {s}(n)$ .

On a binary alphabet, the function $\mathbf {s}$ counts the number of special factors of a given length in u. Let $\mathbf {m}$ denote the map from $\mathcal {L}(u)$ to $\lbrace -1, 0, +1\rbrace $ defined by

$$ \begin{align*} \text{ for all } v\in \mathcal{L}(u),\ \mathbf{m}(v)=\left\{ \begin{array}{ll} -1& \textrm{if}\ v\ \textrm{is}\ \textrm{weak}\ \textrm{bispecial},\\ +1& \textrm{if} \ v\ \textrm{is}\ \textrm{strong}\ \textrm{bispecial} ,\\ 0& \textrm{otherwise}.\\ \end{array} \right. \end{align*} $$

The following formula was given by the first author in [3].

Proposition 2.1. If u is a recurrent binary infinite word, then

$$ \begin{align*} \text{ for all } n\geq 0, \quad \mathbf{s}(n)=1+\sum\limits_{\substack{w \in \mathcal{L}(u)\\ |w|<n }}\mathbf{m}( w)=1+\sum\limits_{\substack{w\ \textrm{bispecial}\\ |w|<n}}\mathbf{m}( w). \end{align*} $$

This relation allows to compute the complexity $\mathbf {p}(n)$ when we are able to describe the set of strong and weak bispecial factors of the binary infinite word u.

Definition 2.3. Two bispecial factors v and w of an infinite word u on the alphabet $\lbrace 0, 1\rbrace $ are said to have the same type if they are both strong, weak, or neutral. In other words, the bispecial factors v and w have the same type if $\mathbf {m}(v)=\mathbf {m}(w)$ .

Definition 2.4. [1, Ch. 7, by Ferenczi and Monteil]

Let u be an infinite word on an alphabet $\mathcal {A}$ .

1. • We say that u admits frequencies if for any factor w, and any sequence $(u_n)$ of prefixes of u such that $\lim \nolimits _{n\rightarrow \infty } |u_n|=\infty $ , then $\lim \nolimits _{n\rightarrow \infty } {|u_n|_w}/{|u_n|}$ exists.

2. • We say that u admits uniform frequencies if for any factor w, and any sequence $(u_n)$ of factors of u such that $\lim \nolimits _{n\rightarrow \infty }|u_n|=\infty $ , then $\lim _{n\rightarrow \infty } {|u_n|_w}/{|u_n|}$ exists.

In [7], M. Keane gave an example of a uniformly recurrent infinite word with complexity $3n+1$ which does not admit uniform frequencies. Later, Boshernitzan [2] obtained the following results.

Theorem 2.1. (Boshernitzan [2])

Let u be an infinite word on an alphabet $\mathcal {A}$ . Then, u admits uniform frequencies if its complexity function satisfies at least one of the following conditions:

1. • ${\liminf {\mathbf {p}(n)}/{n}<2};$

2. • ${\limsup {\mathbf {p}(n)}/{n}<3}.$

The example of Keane ensures that constant $3$ is optimal in the second condition, that is, it cannot be replaced with a larger constant.

3 Construction of a class of uniformly recurrent words

Let $(l_i)$ , $(m_i)$ , $(n_i)$ be three integer sequences which are strictly increasing and satisfy the following conditions:

1. • $0<l_i<m_i<n_i$ ;

2. • ${m_i}/{l_i}$ increases exponentially to $+\infty $ ;

3. • ${n_i}/{m_i}$ increases exponentially to $+\infty $ .

Let us define in $\mathcal {A}^\ast $ two sequences $(u_i)$ and $(v_i)$ in the following way: $u_0=0$ , $v_0=1$ and for all $i\in \mathbb {N}$ , $u_{i+1}=u_i^{m_i}v_{i}^{l_i}$ and $v_{i+1}=u_i^{m_i}v_{i}^{n_i}$ . The sequence $(u_i)$ converges toward an infinite word u.

For $i\geq 1$ , consider the substitution $\sigma _i$ defined by $\sigma _i(0)=0^{m_i}1^{l_i}$ , $\sigma _i(1)=0^{m_i}1^{n_i}$ . Then, we have

$$ \begin{align*} u_{i}=\sigma_0\sigma_1\sigma_2\ldots \sigma_{i-1}(0)\quad \text{and}\quad v_{i}=\sigma_0\sigma_1\sigma_2\ldots \sigma_{i-1}(1). \end{align*} $$

Theorem 3.1. Any infinite word u so defined is uniformly recurrent.

The proof of Theorem 3.1 is given in §6 at the end of this paper.

4 The word u is without uniform frequencies

Lemma 4.1. For all $i\geq 1$ , we have:

1. (1) ${{\vert u_i\vert _0}/{\vert u_i\vert }\geq (1 + ({l_0}/{m_0}))^{-1} \prod _{j=1}^{i-1} (1+ ({l_jn_{j-1}}/{m_jl_{j-1}}))^{-1}};$

2. (2) ${{\vert v_i\vert _1}/{\vert v_i\vert } \geq \prod _{j=0}^{i-1}(1+ ({m_j}/{n_j}))^{-1}}.$

Proof. (1) Lower bound on ${\vert u_{i+1}\vert _0}/{\vert u_{i+1}\vert }$ . First, for all $i\geq 0$ , we have $\vert u_{i}\vert \leq \vert v_i\vert $ since $\vert u_0\vert =\vert v_0\vert =1$ and $u_i$ is a strict prefix of $v_i$ for $i\geq 1$ . Then, ${\vert v_i\vert }/{\vert u_i\vert } = {m_{i-1}\vert u_{i-1}\vert +n_{i-1} \vert v_{i-1}\vert }/{m_{i-1}\vert u_{i-1}\vert + l_{i-1}\vert v_{i-1}\vert } \leq {n_{i-1}}/{l_{i-1}}$ since $l_{i-1}< n_{i-1}$ for $i\geq 1$ .

As

$$ \begin{align*} \vert u_{i+1}\vert_0=m_i\vert u_i\vert_0+l_i\vert v_i\vert_0\geq m_i\vert u_i\vert_0 \end{align*} $$

and

$$ \begin{align*} \vert u_{i+1}\vert=m_i \vert u_i\vert+l_i\vert v_i\vert=\vert u_i\vert\bigg( m_i+l_i \frac{\vert v_i\vert}{\vert u_i\vert}\bigg), \end{align*} $$

we deduce the following inequalities:

$$ \begin{align*} \vert u_{i+1}\vert\leq \vert u_i\vert\bigg( m_i+l_i\frac{n_{i-1}}{l_{i-1}}\bigg) \end{align*} $$

and

$$ \begin{align*} \frac{\vert u_{i+1}\vert_0}{\vert u_{i+1}\vert}\geq \bigg( 1+\frac{l_i}{m_i}\frac{n_{i-1}}{l_{i-1}}\bigg)^{-1} \cdot {\vert u_{i}\vert_0}/{\vert u_{i}\vert}. \end{align*} $$

Thus,

$$ \begin{align*} \frac{\vert u_i\vert_0}{\vert u_i\vert}\geq \frac{\vert u_{1}\vert_0}{\vert u_{1}\vert}\prod_{j=1}^{i-1}\bigg(1+\frac{l_jn_{j-1}}{m_jl_{j-1}} \bigg)^{-1}. \end{align*} $$

(2) Lower bound on ${\vert v_{i+1}\vert _1}/{\vert v_{i+1}\vert }$ . We have

$$ \begin{align*} \vert v_{i+1}\vert_1=m_i\vert u_i\vert_1+n_i\vert v_i\vert_1\geq n_i\vert v_i\vert_1 \textrm{ and } \vert v_{i+1}\vert=m_i\vert u_i\vert+n_i \vert v_i\vert\leq\vert v_i\vert( m_i+n_i), \end{align*} $$

since $\vert u_i\vert \leq \vert v_i\vert $ . So,

$$ \begin{align*} \frac{\vert v_{i+1}\vert_1}{\vert v_{i+1}\vert}\geq \frac{n_i}{m_i+n_i}.\frac{\vert v_{i}\vert_1}{\vert v_{i}\vert}. \end{align*} $$

Hence,

$$ \begin{align*} \frac{\vert v_{i}\vert_1}{\vert v_{i}\vert}\geq \prod_{j=0}^{i-1}\bigg( 1+\frac{m_j}{n_j}\bigg)^{-1} \\[-46pt] .\end{align*} $$

In the rest of the paper, we shall fix

(*) $$ \begin{align} l_i=2^{2.2^i+4},\quad m_i=2^{8.2^i},\quad \text{and}\quad n_i=2^{10.2^i}\quad \text{for } i\geq 0. \end{align} $$

Remark 4.1. The particular choice of sequences in $(\ast )$ was designed to get simple bounds for frequencies (in Lemma 4.3) and to ensure the desired ordering of bispecial factors (in Lemma 5.4). It is not the only possible choice, and we could have stated results for a larger class of words. However, this would have made computations more complicated and less explicit, while our purpose here is to construct one example as explicit as possible.

With $(\ast )$ , the inequalities of Lemma 4.1 become:

1. (1) ${{\vert u_i\vert _0}/{\vert u_i\vert }\geq \prod _{j=1}^{i} {1}/({1+2^{-2^{j}}})}$ ;

2. (2) ${{\vert v_i\vert _1}/{\vert v_i\vert }\geq \prod _{j=1}^{i} {1}/({1+2^{-2^{j}}})}$ .

So we get the following lemma.

Lemma 4.2. For all $i\geq 1$ ,

$$ \begin{align*}\min\bigg( \frac{\vert u_i\vert_0}{\vert u_i\vert},\,\frac{\vert v_i\vert_1}{\vert v_i\vert} \bigg)\geq \prod_{j=1}^{i}\frac{1}{1+2^{-2^{j}}}.\end{align*} $$

Then we have the following lemma.

Lemma 4.3. For all $i\in \mathbb {N}$ ,

$$ \begin{align*} \frac{\vert u_i\vert_0}{\vert u_i\vert}+\frac{\vert v_i\vert_1}{\vert v_i\vert}\geq \frac{3}{2}.\end{align*} $$

Proof. For $i=0$ , the inequality is evident.

For $i\geq 1$ , write $P_i=\prod \nolimits _{j=1}^{i} {1}/({1+2^{-2^j}})$ . The sequence $(P_i)$ is decreasing. Let us show, by induction, that $\tfrac {4}{3} P_i = {1}/({1-2^{-2^{i+1}}})$ .

We have $\tfrac {4}{3} P_0= {1}/({1-2^{-2}}).$

Assuming that for some $i\geq 0$ , $\tfrac {4}{3}P_i= {1}/({1-2^{-2^{i+1}}})$ , it follows that

$$ \begin{align*} \frac{4}{3}P_{i+1}=\frac{4}{3}P_i\times\frac{1}{1+2^{-2^{i+1}}} = \frac{1}{1-2^{-2^{i+1}}}\times\frac{1}{1+2^{-2^{i+1}}} = \frac{1}{1-2^{-2^{i+2}}}. \end{align*} $$

So, for all $i\in \mathbb {N}$ ,

$$ \begin{align*} P_i = \frac{3}{4} \times \frac{1}{1-2^{-2^{i+1}}}. \end{align*} $$

Hence, with Lemma 4.2, we get

$$ \begin{align*} \frac{\vert u_i\vert_0}{\vert u_i\vert}+\frac{\vert v_i\vert_1}{\vert v_i\vert}\geq2\times \frac{3}{4}\times\frac{1}{1-2^{-2^{i+1}}}\geq \frac{3}{2}.\\[-41pt] \end{align*} $$

Theorem 4.1. The letters of the word u do not admit uniform frequencies.

Proof. If the letters of u had uniform frequencies, then the frequencies of 0 and 1, respectively denoted by $\mathbf {f}_u(0)$ and $\mathbf {f}_u(1)$ , would satisfy $\mathbf {f}_u(0)=\lim \nolimits _{i\rightarrow \infty } {\vert u_i\vert _0}/{\vert u_i\vert }$ , $\mathbf {f}_u(1)=\lim \nolimits _{i\rightarrow \infty } {\vert v_i\vert _1}/{\vert v_i\vert }$ , and $\mathbf {f}_u(0)+\mathbf {f}_u(1)=1$ , which is contradictory with Lemma 4.3.

5 Complexity of u

To estimate the complexity of u, we are going to observe its bispecial factors.

Notation 5.1. Let $h, i\in \mathbb {N}$ . We let $u_{i}^{( h) }$ denote the finite word

$$ \begin{align*} u_{i}^{( h) } = \sigma_h\sigma_{h+1}\sigma_{h+2}\ldots \sigma_{h+i-1}(0) \end{align*} $$

and $u^{( h) }$ denotes the infinite word $\lim \nolimits _{i\rightarrow \infty }u_{i}^{( h) }$ . Note that $u_{i}^{( 0) }=u_i$ and $u^{( 0) }=u$ .

Definition 5.1. A factor of $u^{( h) }$ is said to be short if it does not contain $10$ as a factor. A factor of $u^{( h) }$ which is not short is said to be long.

Lemma 5.1. (Synchronization lemma)

Let w be a long factor of $u^{( h) }$ . Then there exist $x, y\in \mathcal {A}$ and $v\in \mathcal {A}^\ast $ such that $xvy$ is a factor of $u^{( h+1) }$ and $w=s\sigma _h( v) p$ , where s is a non-empty suffix of $\sigma _h(x)$ and p is a non-empty prefix of $\sigma _h(y)$ . Moreover, the triple $(s, v, p)$ is unique.

Proof. Since w is long, it cannot occur inside the image of one letter. Any occurrence of w in u is therefore of the form $s\sigma _h(v)p$ , so existence follows.

Uniqueness is a consequence of the fact that $10$ occurs in $u^{( h) }$ only at the border between two images of letters under $\sigma _h$ .

Lemma 5.2

1. (1) The short and strong bispecial factors of $u^{(h)}$ are $\varepsilon $ and $1^{l_h}$ .

2. (2) The short and weak bispecial factors of $u^{(h)}$ are $0^{m_h-1}$ and $ 1^{n_h-1}$ .

Proof. Let us first observe that in $u^{( h) }$ , the factor $01$ is always preceded by $10^{m_{h}-1}$ . Therefore, a bispecial factor containing $01$ must also contain $10$ and is long.

Then the short bispecial factors are all of the form $0^k$ or $1^k$ , $k\geq 0$ . We see that $\varepsilon $ is strong bispecial (extensions $00, 01, 10, 11$ ); $0^k$ ( $0\leq k<m_h-1$ ) is neutral bispecial (extensions $00^k0, 00^k1, 10^k0$ ), as well as $1^k$ ( $1\leq k<n_h-1$ , $k\neq l_h$ ); $1^{l_h}$ is strong bispecial (extensions $01^{l_h}0, 01^{l_h}1, 11^{l_h}0, 11^{l_h}1$ ); $0^{m_h-1}$ is weak bispecial (extensions $00^{m_h-1}1$ and $10^{m_h-1}0$ ), as well as $1^{n_h-1}$ ; $0^{m_h}$ and $1^{n_h}$ are not special, and $0^k$ ( $k>m_h$ ) and $1^k$ ( $k>n_h$ ) are not factors.

Lemma 5.3. Let w be a factor of $u^{(h)}$ . Then the following assertions are equivalent:

1. (1) w is a long bispecial factor of $u^{(h)}$ ;

2. (2) there exists a bispecial factor v of $u^{(h+1)}$ such that $w=\widehat {\sigma }_h(v)$ , where $\widehat {\sigma }_h(v)=1^{l_h}\sigma _h(v)0^{m_h}1^{l_h}$ .

Moreover, v and w have the same type and $|v|<|w|$ .

Proof. First, let us observe this fact: if a finite word v is a factor of $u^{(h+1)}$ , then $\widehat {\sigma }_h(v)=1^{l_h}\sigma _h(v)0^{m_h}1^{l_h}$ is a factor of $u^{(h)}$ . Now, let us consider a bispecial factor v of $u^{(h+1)}$ . Therefore, the words $\widehat {\sigma }_h(0v),\ \widehat {\sigma }_h(1v),\ \widehat {\sigma }_h(v0)$ , and $\widehat {\sigma }_h(v1)$ are factors of $u^{(h)}$ ; moreover, $0\widehat {\sigma }_h(v)$ and $1\widehat {\sigma }_h(v)$ are respectively the suffix of the first two words, whereas $\widehat {\sigma }_h(v)0$ and $\widehat {\sigma }_h(v)1$ are respectively the prefix of the last two words. Hence, the word $w=\widehat {\sigma }_h(v)$ is bispecial in $u^{(h)}$ , and $\mathbf {m}(w)\geq \mathbf {m}(v).$

Conversely, let w be a long bispecial factor of $u^{(h)}$ . Then, according to the synchronization lemma, we can write w uniquely in the form $s\sigma _{h}(v)p$ , where s and p are respectively the non-empty suffix and prefix of images of letters.

As $0w$ and $1w$ are factors of $u^{( h) }$ , and $\sigma _h(v)p$ starts with $0$ , it follows that $0s0$ and $1s0$ are factors of $u^{( h) }$ . This is only possible if $s=1^{l_h}$ ( $s=1^k$ with $1\leq k<l_h$ or $l_h<k<n_h$ are excluded since $0s0\notin L( u^{( h) }) $ ; $s=0^{k}1^{l_{h}}$ with $1\leq k<m_h$ and $s=0^{k}1^{n_{h}}$ with $0\leq k<m_h$ are excluded since $1s0\notin \mathcal {L}( u^{( h) }) $ ; and $s=0^{m_h}1^{l_{h}}$ and $s=0^{m_h}1^{n_{h}}$ are excluded since $0s0\notin \mathcal {L}( u^{( h) }) $ ).

Similarly, $1p0$ and $1p1$ are factors of $u^{( h) }$ , and this is only possible if $p=0^{m_h}1^{l_{h}}$ . Therefore, $w=\widehat {\sigma }_h(v)$ .

If w extends as $awb$ with $a, b\in \mathcal {A}$ , then v also extends as $avb$ . Therefore, $\mathbf {m}(v)\geq \mathbf {m}(w).$ It follows that $\mathbf {m}(v)=\mathbf {m}(w)$ : v and w have the same type. Moreover, it is clear that $|v|<|w|$ .

In fact, long bispecial factors of $u^{(h)}$ are the images under $\widehat {\sigma }_h$ of the ‘less long’ bispecial factors of $u^{(h+1)}$ . Thus, step by step, any non-neutral bispecial factor w of $u^{(h)}$ of given type will be written in the form $\widehat {\sigma }_h\widehat {\sigma }_{h+1}\ldots \widehat {\sigma }_{h+i-1}(v)$ , where v is a short bispecial factor of $u^{(h+i)}$ with the same type.

We will call bispecial factors of rank i, ( $i\geq 0$ ) of $u^{(h)}$ , and write $a_{i}^{(h)}$ , $b_{i}^{(h)}$ , $c_{i}^{(h)}$ , $d_{i}^{(h)}$ as the following words:

$$ \begin{align*} \begin{aligned} a_{i}^{(h)}&=\widehat{\sigma}_h\widehat{\sigma}_{h+1}\ldots\widehat{\sigma}_{h+i-1}(\varepsilon);\\ b_{i}^{(h)}&=\widehat{\sigma}_h\widehat{\sigma}_{h+1}\ldots\widehat{\sigma}_{h+i-1}(1^{l_{h+i}});\\ c_{i}^{(h)}&=\widehat{\sigma}_h\widehat{\sigma}_{h+1}\ldots\widehat{\sigma}_{h+i-1}(0^{m_{h+i}-1});\\ d_{i}^{(h)}&=\widehat{\sigma}_h\widehat{\sigma}_{h+1}\ldots\widehat{\sigma}_{h+i-1}(1^{n_{h+i}-1}). \end{aligned} \end{align*} $$

The short bispecial $\varepsilon ,\ 1^{l_h}$ , $0^{m_h-1}$ , and $ 1^{n_h-1}$ of $u^{(h)}$ are the bispecial factors of rank $0$ : $a_{0}^{(h)}$ , $b_{0}^{(h)}$ , $c_{0}^{(h)}$ , and $d_{0}^{(h)}$ .

The non-neutral bispecial factors of u are therefore $a_i=a_{i}^{(0)}$ , $b_i=b_{i}^{(0)}$ , $c_i=c_{i}^{(0)}$ , and $d_i=d_{i}^{(0)}$ , for $i\geq 0$ .

Definition 5.2. Let $V, W\in \mathbb {R}^2$ . Let us write $V<W$ when $W-V$ has non-negative entries and $V\neq W$ .

Proposition 5.1. Let v, w, $v'$ , $w'$ be four words such that $v'=\widehat {\sigma }_i(v)$ and $w'=\widehat {\sigma }_i(w)$ . Then their Parikh vectors satisfy

$$ \begin{align*} V<W\Longrightarrow V'<W'. \end{align*} $$

Proof. Assume that $V<W$ . Then, $\vert v\vert _0\leq \vert w\vert _0$ , $\vert v\vert _1\leq \vert w\vert _1$ , and $\vert v\vert <\vert w\vert $ . On the one hand, we have $\vert v'\vert _0= m_i( \vert v\vert +1) $ and $\vert w'\vert _0=m_i( \vert w\vert +1) $ ; hence, $\vert v'\vert _0<\vert w'\vert _0$ . On the other hand, we have $\vert v'\vert _1= l_i\vert v\vert _0+n_i\vert v\vert _1+2l_i $ and $\vert w'\vert _1= l_i\vert w\vert _0+n_i\vert w\vert _1+2l_i $ ; so $\vert v'\vert _1\leq \vert w'\vert _1$ . Finally, $\vert v'\vert =\vert v'\vert _0+\vert v'\vert _1<\vert w'\vert _0+\vert w'\vert _1=\vert w'\vert .$

Lemma 5.4. For all $i\geq 0$ , let $A_i, B_i, C_i, D_i$ be the Parikh vectors corresponding to the non-neutral bispecial factors of u, $a_i, b_i, c_i, d_i$ . Then, we have

$$ \begin{align*} \text{ for all } i\geq 1,\quad D_{i-1}< B_{i}< C_{i}< A_{i+1} < D_{i}. \end{align*} $$

Proof. Applying $\widehat {\sigma }_{i-1} $ on the words $b_{0}^{(i)}$ , $c_{0}^{(i)}$ , $\widehat {\sigma }_{i} ( a_{0}^{(i+1)}) =1^{l_i}0^{m_i}1^{l_i}$ , and $d_{0}^{(i)}$ , we get the following words:

$$ \begin{align*}\begin{array}{l} d_{0}^{(i-1)}= 1^{n_{i-1}-1};\\ b_{1}^{(i-1)}=1^{l_{i-1}}(0^{m_{i-1}}1^{n_{i-1}})^{l_i}0^{m_{i-1}}1^{l_{i-1}};\\ c_{1}^{(i-1)}=1^{l_{i-1}}(0^{m_{i-1}}1^{l_{i-1}})^{m_i-1}0^{m_{i-1}}1^{l_{i-1}};\\ a_{2}^{(i-1)}=1^{l_{i-1}}(0^{m_{i-1}}1^{n_{i-1}})^{l_i}( 0^{m_{i-1}}1^{l_{i-1}})^{m_i}(0^{m_{i-1}}1^{n_{i-1}})^{l_i}0^{m_{i-1}}1^{l_{i-1}} \vphantom{{d_{1}^{(i-1)}}_{l}};\\ d_{1}^{(i-1)}=1^{l_{i-1}}( 0^{m_{i-1}}1^{n_{i-1}}) ^{n_i-1}0^{m_{i-1}}1^{l_{i-1}}.\\ \end{array} \end{align*} $$

The Parikh vectors corresponding to these words are:

$$ \begin{align*}\begin{array}{l} D_{0}^{(i-1)}=\begin{pmatrix} 0\\ n_{i-1}-1 \\ \end{pmatrix}\!;\\ B_{1}^{(i-1)}=\begin{pmatrix} m_{i-1}( l_i+1) \\ n_{i-1}l_i+2l_{i-1} \end{pmatrix}\!;\\ C_{1}^{(i-1)}=\begin{pmatrix} m_i m_{i-1}\\ l_{i-1}( m_i+1) \\ \end{pmatrix}\!;\\ A_{2}^{(i-1)} =\begin{pmatrix} m_{i-1}( m_i+2 l_i+1) \\ l_{i-1}( m_i+2) +2l_in_{i-1} \end{pmatrix}\!; \\ D_{1}^{(i-1)}=\begin{pmatrix} m_{i-1}n_i\\ n_{i-1}( n_i-1)+2l_{i-1} \\ \end{pmatrix}\!.\\ \end{array} \end{align*} $$

From $(\ast )$ , we have

$$ \begin{align*}n_{i-1}l_i+l_{i-1}<l_{i-1}m_i, m_i+2l_i+1<n_i, l_{i-1}m_i+2n_{i-1}l_i<n_{i-1}( n_i-1). \end{align*} $$

It follows the inequalities:

$$ \begin{align*} D_{0}^{(i-1)}<B_{1}^{(i-1)}< C_{1}^{(i-1)}< A_{2}^{(i-1)} < D_{1}^{(i-1)}. \end{align*} $$

Applying $\widehat {\sigma }_{i-2} $ on the words $d_{0}^{(i-1)}$ , $b_{1}^{(i-1)}$ , $c_{1}^{(i-1)}$ , $a_{2}^{(i-1)}$ , and $d_{1}^{(i-1)}$ , we get the words $d_{1}^{(i-2)}$ , $b_{2}^{(i-2)}$ , $c_{2}^{(i-2)}$ , $a_{3}^{(i-2)}$ , and $d_{2}^{(i-2)}$ . By Proposition 5.1, it results in the following inequalities:

$$ \begin{align*} D_{1}^{(i-2)}< B_{2}^{(i-2)}< C_{2}^{(i-2)}< A_{3}^{(i-2)} < D_{2}^{(i-2)}. \end{align*} $$

And so, after the ith iteration, we get

$$ \begin{align*} D_{i-1}^{(0)}< B_{i}^{(0)}< C_{i}^{(0)}< A_{i+1}^{(0)} < D_{i}^{(0)}.\\[-37pt] \end{align*} $$

Lemma 5.5. For all $i\geq 0$ ,

$$ \begin{align*}|b_{i}|<|c_{i}|< |a_{i+1}| < |d_{i}|< |b_{i+1}| .\end{align*} $$

Proof.

1. • For $i\geq 1$ , the inequalities $ |b_{i}|<|c_{i}|< |a_{i+1}| < |d_{i}|< |b_{i+1}| $ follow from Lemma 5.4.

2. • For $i=0$ , recall that $|b_0|=l_0$ , $|c_0|=m_0-1$ , $|a_1|=2l_0+m_0$ , $|d_0|=n_0-1$ , and $|b_1|=l_1( m_0+n_0) +m_0+2l_0$ . So,

   $$ \begin{align*}|b_{0}|<|c_{0}|< |a_{1}| < |d_{0}| < |b_{1}|.\\[-50pt] \end{align*} $$

Lemma 5.6. The function $\mathbf {s} $ associated with the word u satisfies:

$$ \begin{align*} \text{ for all } n\in\mathbb{N},\quad \mathbf{s}(n)=\left\{\! \begin{array}{l} 1 \textrm{ if } n=0,\\ 2 \textrm{ if } n\in \bigcup\limits_{i\geq0}( [|c_i|+1, |a_{i+1}| ]\cup [|d_i|+1,\, |b_{i+1}| ]) \cup ] 0, |b_0|], \\ 3 \textrm{ if } n\in \bigcup\limits_{i\geq0}( [|b_i|+1, |c_{i}| ]\cup [|a_{i+1}|+1, |d_i| ]) .\\ \end{array} \right.\end{align*} $$

Proof. Let $n\in \mathbb {N}$ . We know that $a_i$ , $b_i$ , $c_i$ , and $d_i$ , for $i\geq 0$ , are the only bispecial factors of u which are strong or weak. Hence, using Proposition 2.1, we have

$$ \begin{align*} \begin{aligned} \mathbf{s}( n) = 1&+\sum\limits_{\substack{w\ \textrm{bispecial}\\ |w|<n }} \mathbf{m} ( w) \\ =1&+\#\lbrace i\geq0:|a_{i}|<n\rbrace \\ &+\#\lbrace i\geq0:|b_{i}|<n\rbrace \\ &-\#\lbrace i\geq0:|c_{i}|<n\rbrace\\ &-\#\lbrace i\geq0:|d_{i}|<n\rbrace. \end{aligned}\end{align*} $$

Since for $m\in [1,\, |b_0|-1]$ , there is not a strong or weak bispecial factor of u with length m, we have, for $0<n\leq |b_0|$ :

$$ \begin{align*}\mathbf{s}(n)=1+\sum\limits_{\substack{w\ \textrm{bispecial}\\ |w|\leq n-1 }}\mathbf{m} ( w)=1+\mathbf{m}(\varepsilon)=2. \end{align*} $$

Suppose $n> |b_0|$ . Then, there exists $i\in \mathbb {N}$ such that $n\in [|b_i|+1,\, |b_{i+1}|]$ . Since the sequences $|a_i|$ , $|b_i|$ , $|c_i|$ , and $|d_i|$ are increasing, we are in one of the following cases:

1. • $n\in [|b_i|+1,\, |c_i|]$ , then $\mathbf {s}(n)=1+ (i+1)+(i+1)-(i)-(i)=3;$

2. • $n\in [|c_i|+1,\, |a_{i+1}|]$ , then $\mathbf {s}(n)=1+ (i+1)+(i+1)-(i+1)-(i)=2;$

3. • $n\in [|a_{i+1}|+1,\, |d_{i}|]$ , then $\mathbf {s}(n)=1+ (i+2)+(i+1)-(i+1)-(i)=3;$

4. • $n\in [|d_i|+1,\, |b_{i+1}|]$ , then $\mathbf {s}(n)=1+ (i+2)+(i+1)-(i+1)-(i+1)=2.$

Theorem 5.1. The complexity function $\mathbf {p}$ of u satisfies:

$$ \begin{align*} \text{ for all } n\geq1,\quad \mathbf{p}(n)\leq3n+1. \end{align*} $$

Proof. By Lemma 5.6, $\text {s}(n)\leq 3$ for all $n\geq 0$ . As $\mathbf {p}(n)=\mathbf {p}(0)+\sum ^{n-1}_{m=0}\mathbf {s}(m)$ , it follows that $\mathbf {p}(n)\leq \mathbf {p}(0)+3(n)=3n+1$ .

Proposition 5.2. Let v, w, $v'$ , $w'$ be four finite words such that $v'=\widehat {\sigma }_i(v)$ and $w'=\widehat {\sigma }_i(w)$ . Then for all $\unicode{x3bb}>0$ , we have

$$ \begin{align*} W>\unicode{x3bb} \bigg[ V+\begin{pmatrix} 1\\1 \end{pmatrix}\bigg] \Longrightarrow W'>\unicode{x3bb} \bigg[ V'+\begin{pmatrix} 1\\1 \end{pmatrix}\bigg].\end{align*} $$

Proof. Assume that $W>\unicode{x3bb} [ V+ (\begin {smallmatrix} 1\\1 \end {smallmatrix})]$ . Since $\vert v'\vert _0= m_i( \vert v\vert +1) $ and $\vert v'\vert _1= l_i\vert v\vert _0+n_i\vert v\vert _1+2l_i $ , then

$$ \begin{align*}V'=\begin{pmatrix} m_i&m_i\\ l_i&n_i \end{pmatrix} V +\begin{pmatrix} m_i\\ 2l_i \end{pmatrix}.\end{align*} $$

Here, $W'$ is written in the same way. It follows

$$ \begin{align*}W'-\unicode{x3bb} \bigg[ V'+\begin{pmatrix} 1\\1 \end{pmatrix}\bigg]=\begin{pmatrix} m_i&m_i\\ l_i&n_i \end{pmatrix} (W-\unicode{x3bb} V) + ( 1-\unicode{x3bb}) \begin{pmatrix} m_i\\ 2l_i \end{pmatrix} -\unicode{x3bb}\begin{pmatrix} 1\\1 \end{pmatrix}\!.\end{align*} $$

Since

$$ \begin{align*} W>\unicode{x3bb} V +\unicode{x3bb}\begin{pmatrix} 1\\1 \end{pmatrix}\quad \textrm{and}\quad ( 1-\unicode{x3bb}) \begin{pmatrix} m_i\\ 2l_i \end{pmatrix}>-\unicode{x3bb} \begin{pmatrix} m_i\\ 2l_i \end{pmatrix}, \end{align*} $$

it follows that

$$ \begin{align*} \begin{aligned} W'-\unicode{x3bb} \bigg[ V'+\begin{pmatrix} 1\\1 \end{pmatrix}\bigg]&>\unicode{x3bb}\bigg[ \begin{pmatrix} m_i&m_i\\ l_i&n_i \end{pmatrix}\begin{pmatrix} 1\\ 1 \end{pmatrix} - \begin{pmatrix} m_i+1\\ 2l_i+1 \end{pmatrix} \bigg]\\ &\qquad =\unicode{x3bb}\begin{pmatrix} m_i-1\\n_i-l_i-1 \end{pmatrix} >\begin{pmatrix} 0\\0 \end{pmatrix}.\\[-2pc] \end{aligned} \end{align*} $$

This proposition allows us to prove the following lemma.

Lemma 5.7. For all $i\geq 0$ ,

$$ \begin{align*} B_{i+1}>l_{i+1}\bigg[ D_{i}+\begin{pmatrix} 1\\1 \end{pmatrix}\bigg]. \end{align*} $$

Proof. Let us choose an integer $i\geq 1$ . Then, we have $b_{1}^{(i)}=\widehat {\sigma }_{i} ( b_{0}^{(i+1)}) = 1^{l_{i}} ( 0^{m_{i}}1^{n_{i}}) ^{l_{i+1}}0^{m_{i}}1^{l_{i}}$ and $d_{0}^{(i)}=1^{n_{i}-1}$ ; the corresponding Parikh vectors are $B_{1}^{(i)}=(\begin {smallmatrix} l_{i+1}m_i+m_i\\ l_{i+1}n_i+2l_i \end {smallmatrix})$ and $D_{0}^{(i)}= (\begin {smallmatrix} 0\\ n_i-1 \end {smallmatrix})$ . It follows the inequality:

$$ \begin{align*} \ B_{1}^{(i)}>l_{i+1}\bigg[ D_{0}^{(i)}+\begin{pmatrix} 1\\1 \end{pmatrix}\bigg]. \end{align*} $$

By regressive induction on $j\leq i$ , suppose that

$$ \begin{align*}B_{i+1-j}^{(j)}>l_{i+1}\bigg[ D_{i-j}^{(j)}+\begin{pmatrix} 1\\1 \end{pmatrix}\bigg],\end{align*} $$

where $B_{i+1-j}^{(j)}$ and $ D_{i-j}^{(j)}$ are respectively Parikh vectors of the words $b_{i+1-j}^{(j)}$ and $ d_{i-j}^{(j)}$ . Thus, by Proposition 5.2,

$$ \begin{align*}B_{i+2-j}^{(j-1)}>l_{i+1}\bigg[ D_{i-j+1}^{(j-1)}+\begin{pmatrix} 1\\1 \end{pmatrix}\bigg]\end{align*} $$

since $B_{i+2-j}^{(j-1)}$ is the Parikh vector of $b_{i+2-j}^{(j-1)}=\widehat {\sigma }_{j-1} ( b_{i+1-j}^{(j)})$ and $D_{i-j+1}^{(j-1)}$ is the Parikh vector of $d_{i-j+1}^{(j-1)}=\widehat {\sigma }_{j-1} ( d_{i-j}^{(j)})$ . So,

$$ \begin{align*}B_{i+1-j}^{(j)}>l_{i+1}\bigg[ D_{i-j}^{(j)}+\begin{pmatrix} 1\\1 \end{pmatrix}\bigg]\quad \text{for } 0\leq j\leq i.\end{align*} $$

In the inequality above, we find the lemma by making $j=0$ .

Theorem 5.2. The complexity function $\mathbf {p}$ of u satisfies $\liminf {\mathbf {p}(n)}/{n} = 2$ .

Proof. We have $\mathbf {s}(n)=2$ for $ |d_i|<n\leq |b_{i+1}|$ . So,

$$ \begin{align*}\mathbf{p}( |b_{i+1}|) =\mathbf{p}( |d_{i}|+1) +2( |b_{i+1}|-|d_{i}|-1).\end{align*} $$

By Lemma 5.6, we have $\mathbf {p}(n)\leq 3n+1$ and we deduce that

$$ \begin{align*} \begin{aligned} \mathbf{p} ( |b_{i+1}|) &\leq ( 3|d_{i}|+4) +2 ( |b_{i+1}|-|d_{i}|-1)\\ &\leq2 |b_{i+1}| +\frac{1}{l_{i+1}}|b_{i+1}| \end{aligned}\end{align*} $$

since $|b_{i+1}|>l_{i+1}(|d_{i}|+2)$ as $B_{i+1}>l_{i+1}[ D_{i}+(\begin {smallmatrix} 1\\1 \end {smallmatrix})]$ . So,

$$ \begin{align*} \frac{\mathbf{p}( |b_{i+1}|)}{ |b_{i+1}|}\leq 2+\frac{1}{l_{i+1}}\quad \textrm{and} \quad \lim_{i \rightarrow \infty}\frac{\mathbf{p} ( |b_{i+1}|)}{ |b_{i+1}|}=2. \end{align*} $$

As $\mathbf {p}(n)\geq 2n$ since $\mathbf {s}(n)\geq 2$ for $n\geq 1$ , we get $\liminf {\mathbf {p}(n)}/{n}=2$ .

6 Proof of Theorem 3.1

Now, with Notation 5.1, we are able to explain the proof of Theorem 3.1.

Proof. Let us show that for $i\geq 0$ , there exists $N_i$ such that any factor of u of length $N_i$ contains the prefix $u_i$ . Note that u does not contain $1^{n_0+1}$ .

1. (i) For $i=0$ , any factor of u of length $N_0=n_0+1$ contains the prefix $0=u_0$ .

2. (ii) For $i\geq 1$ , any factor of $u^{(i)}$ of length $N_{0}^{( i) }=n_i+1$ contains the prefix $0=u_{0}^{(i)}$ of $u^{(i)}$ . Thus, any factor of $u^{(i-1)}$ of length

   $$ \begin{align*}N_{1}^{(i-1)}= ( m_{i-1}+n_{i-1}) ( N_0^{( i)} +1) \end{align*} $$

   contains $\sigma _{i-1}( 0)=u_1^{(i-1)}$ .

By regressive induction on j, suppose that for some $j\leq i-1$ , there exists $N_{i-j}^{(j)}$ such that any factor of $u^{(j)}$ of length $N_{i-j}^{(j)}$ contains the word $u_{i-j}^{(j)}$ . Then, any factor of $u^{(j-1)}$ of length

$$ \begin{align*} N_{i-j+1}^{(j-1)}= ( m_{j-1}+n_{j-1}) ( N_{i-j}^{(j)} +1) \end{align*} $$

contains $\sigma _{j-1}(u_{i-j}^{(j)}) =u_{i-j+1}^{(j-1)}$ .

So, for $0\leq j\leq i-1$ , there exists $N_{i-j}^{(j)}$ such that any factor of $u^{(j)}$ of length $N_{i-j}^{(j)}$ contains the word $u_{i-j}^{(j)}$ .

Consequently, letting $N_i=N_{i}^{(0)}$ , it follows that any factor of $u=u^{(0)}$ of length $N_{i}$ contains the word $u_i$ . This completes the proof.