Asymptotic repetitive threshold of balanced sequences

The concatenation of $e\in\mathbb{N}$ copies of a non-empty word $u$ is usually abbreviated as $u^{e}$. In 1972, Dejean extended this exponential notation to rational exponents. If $u$ is a non-empty word of length $\ell$ and $e$ is a positive rational number of the form $n/\ell$, then $u^{e}$ denotes the prefix of length $n$ of the infinite periodic sequence $uuu\cdots=u^{\omega}$. For instance, a Czech word $starosta$ (mayor) can be written in this formalism as $(staro)^{8/5}$. The rational exponent $e$ describes the repetition rate of $u$ in the string $u^{e}$.

The critical exponent $E(\mathbf{u})$ of an infinite sequence $\mathbf{u}=u_{0}u_{1}u_{2}\cdots$ captures the maximal possible repetition rate of factors occurring in $\mathbf{u}$, formally,

The number $E(\mathbf{u})$ can be rational or irrational. Krieger and Shallit [KrSh07] have shown that any positive real number larger than one is a critical exponent of some sequence over a finite alphabet. If the size of the alphabet is a fixed number $d\in\mathbb{N},d\geq 2$, then the critical exponent of any sequence $\mathbf{u}$ over this alphabet cannot be smaller than a threshold larger than one. This bound is denoted in [CuRa11] as $RT(d)$ and called the repetitive threshold, i.e.,

For instance, if $\mathbf{u}$ is a binary sequence over $\{0,1\}$, then $00$ or $11$ or $0101$ appears in $\mathbf{u}$, and thus $E(\mathbf{u})\geq 2$. The existence of an infinite binary sequence $\mathbf{u}$ with $E(\mathbf{u})=2$ was demonstrated by Thue in 1912. The binary sequence for which $E(\mathbf{u})=2$ is nowadays known as the Thue-Morse sequence (or the Prouhet-Thue-Morse sequence). Therefore $RT(2)=2$. Dejean [Dej72] proved that $RT(3)=\frac{7}{4}$ and this bound is attained. In the same paper she also conjectured:

• •

  $RT(4)=7/5$;

• •

  $RT(d)=1+\frac{1}{d-1}$ for $d\geq 5$.

The conjecture had been proved step by step by many people [Pan84c, Mou92, MoCu07, Car07, CuRa11, Rao11].

Recently, Rampersad, Shallit and Vandome asked the same question for $d$-ary balanced sequences. Let us recall that a sequence over a finite alphabet is balanced if, for any two of its factors $u$ and $v$ of the same length, the number of occurrences of each letter in $u$ and $v$ differs by at most 1. Binary balanced aperiodic sequences coincide with Sturmian sequences and the least critical exponent is equal to $2+\frac{1+\sqrt{5}}{2}$ and it is reached by the Fibonacci sequence [CaLu2000]. Let us denote the repetitive threshold of balanced sequences over a $d$-ary alphabet by $RTB(d)$, i.e.,

The following results have been proved so far:

• •

  $RTB(3)=2+\frac{1}{\sqrt{2}}$ and $RTB(4)=1+\frac{1+\sqrt{5}}{4}$ [RSV19];

• •

  $RTB(d)=1+\frac{1}{d-3}$ for $5\leq d\leq 10$ [Bar20, BaSh19, DDP21];

• •

  $RTB(d)=1+\frac{1}{d-2}$ for $d=11$ and all even numbers $d\geq 12$ [DOPS2022].

It remains as an open problem to prove the conjecture $RTB(d)=1+\frac{1}{d-2}$ also for all odd numbers $d\geq 13$.

In this paper we focus on the asymptotic critical exponent $E^{*}(\mathbf{u})$ of $\mathbf{u}$. It is defined to be $+\infty$ if $E(\mathbf{u})=+\infty$ and

otherwise. Obviously, $E^{*}(\mathbf{u})\leq E(\mathbf{u})$ and the equality holds true whenever $E(\mathbf{u})$ is irrational. It is for instance the case of the Fibonacci sequence. Nevertheless, $E^{*}(\mathbf{u})$ and $E(\mathbf{u})$ can coincide even if $E(\mathbf{u})$ is rational: it is the case of the Thue-Morse sequence.

While the value $E(\mathbf{u})$ takes into account repetitions of all factors of $\mathbf{u}$, $E^{*}(\mathbf{u})$ considers only repetitions of factors of length tending to infinity. There is a huge literature devoted to questions situated between these two extremes. For example, Shur and Tunev [ShTu] construct a $d$-ary sequence $\mathbf{u}$ whose all factors (except the trivial repetition of one letter in factors of the form $a_{1}a_{2}\cdots a_{d-1}a_{1}$) have the exponent $<1+\frac{1}{d-1}=RT(d)$. Other results of this flavour can be found in [BaCr, De, Sh].

We provide a simple construction showing that for any $d\in\mathbb{N},d\geq 2,$ and any $\epsilon>0$, there exists a $d$-ary sequence $\mathbf{u}$ with $E^{*}(\mathbf{u})<1+\epsilon$. Therefore, if we denote

we have $RT^{*}(d)=1\quad\text{for all $d\geq 2$}\,.$ Then we restrict our study to balanced sequences and look for the threshold

This threshold is bounded from below by $1+\frac{1}{2^{d-2}}$, see Corollary 15. It is known that $RTB^{*}(2)=RTB(2)=2+\frac{\sqrt{5}+1}{2}\doteq 3.618$ and it is reached by the Fibonacci sequence. We introduce a new tool – graphs of admissible tails – for computation of the exact value of $RTB^{*}(d)$. Using it we obtain at once $RTB^{*}(d)$ for $d\leq 10$, see Table 1. Let us point out that a similar result for $RTB(d)$ had been done step by step by several research teams.

Comparing the results with the minimal critical exponent of balanced sequences, we can see that $RTB^{*}(d)=RTB(d)$ for $d\in\{2,3,4,5\}$, but $RTB^{*}(d)<RTB(d)$ for larger $d$. Moreover, the precise values $RTB^{*}(d)$ we have found for $d\leq 10$ suggest that $RTB^{*}(d)<1+{q^{d}}$ for some positive $q<1$, whereas $RTB(d)>RT(d)=1+\frac{1}{d-1}$. Looking into Table 1 we can see that

$RTB^{*}(6)<1+\frac{1}{4}$,   $RTB^{*}(7)<1+\frac{1}{7}$,   $RTB^{*}(8)<1+\frac{1}{20}$,   $RTB^{*}(9)<1+\frac{1}{30}$,  $RTB^{*}(10)<1+\frac{1}{68}$.

An alphabet $\mathcal{A}$ is a finite set of symbols called letters. A word over $\mathcal{A}$ of length $n$ is a string $u=u_{0}u_{1}\cdots u_{n-1}$, where $u_{i}\in\mathcal{A}$ for all $i\in\{0,1,\ldots,n-1\}$. The length of $u$ is denoted by $|u|$. The set of all finite words over $\mathcal{A}$ together with the operation of concatenation forms a monoid, denoted $\mathcal{A}^{*}$. Its neutral element is the empty word $\varepsilon$ and we denote $\mathcal{A}^{+}=\mathcal{A}^{*}\setminus\{\varepsilon\}$. If $u=xyz$ for some $x,y,z\in\mathcal{A}^{*}$, then $x$ is a prefix of $u$, $z$ is a suffix of $u$ and $y$ is a factor of $u$. To any word $u$ over $\mathcal{A}$ with cardinality $\#\mathcal{A}=d$, we assign its Parikh vector $\vec{V}(u)\in\mathbb{N}^{d}$ defined as $(\vec{V}(u))_{a}=|u|_{a}$ for all $a\in\mathcal{A}$, where $|u|_{a}$ is the number of letters $a$ occurring in $u$.

A sequence over $\mathcal{A}$ is an infinite string $\mathbf{u}=u_{0}u_{1}u_{2}\cdots$, where $u_{i}\in\mathcal{A}$ for all $i\in\mathbb{N}$. The notation $\mathcal{A}^{\mathbb{N}}$ stands for the set of all sequences over $\mathcal{A}$. We always denote sequences by bold letters. The shift operator $\sigma$ maps any sequence $\mathbf{u}=u_{0}u_{1}u_{2}\cdots$ to the sequence $\sigma(\mathbf{u})=u_{1}u_{2}u_{3}\cdots$.

A sequence $\mathbf{u}$ is eventually periodic if $\mathbf{u}=vwww\cdots=vw^{\omega}$ for some $v\in\mathcal{A}^{*}$ and $w\in\mathcal{A}^{+}$. It is periodic if $\mathbf{u}=w^{\omega}$. In both cases, the number $|w|$ is a period of $\mathbf{u}$. We write $\mathrm{Per}\,\mathbf{u}$ for the minimal period of $\mathbf{u}$. If $\mathbf{u}$ is not eventually periodic, then it is aperiodic. A factor of $\mathbf{u}=u_{0}u_{1}u_{2}\cdots$ is a word $y$ such that $y=u_{i}u_{i+1}u_{i+2}\cdots u_{j-1}$ for some $i,j\in\mathbb{N}$, $i\leq j$. The number $i$ is called an occurrence of the factor $y$ in $\mathbf{u}$. In particular, if $i=j$, the factor $y$ is the empty word $\varepsilon$ and any index $i$ is its occurrence. If $i=0$, the factor $y$ is a prefix of $\mathbf{u}$. If each factor of $\mathbf{u}$ has infinitely many occurrences in $\mathbf{u}$, the sequence $\mathbf{u}$ is recurrent. Moreover, if for each factor the distances between its consecutive occurrences are bounded, $\mathbf{u}$ is uniformly recurrent.

The language $\mathcal{L}(\mathbf{u})$ of a sequence $\mathbf{u}$ is the set of all its factors. A factor $w$ of $\mathbf{u}$ is right special if $wa,wb$ are in $\mathcal{L}(\mathbf{u})$ for at least two distinct letters $a,b\in\mathcal{A}$. A left special factor is defined symmetrically. A factor is bispecial if it is both left and right special.

A sequence $\mathbf{u}\in\mathcal{A}^{\mathbb{N}}$ is balanced if for every letter $a\in\mathcal{A}$ and every pair of factors $u,v\in{\mathcal{L}}(\mathbf{u})$ with $|u|=|v|$, we have $|u|_{a}-|v|_{a}\leq 1$. Every recurrent balanced sequence over any alphabet is uniformly recurrent, see [DolceDP21]. An aperiodic balanced sequence over a binary alphabet is called Sturmian, [MoHe40]. There exist many equivalent definitions of Sturmian sequences, see for instance [BeSe02].

A morphism over $\mathcal{A}$ is a mapping $\psi:\mathcal{A}^{*}\to\mathcal{A}^{*}$ such that $\psi(uv)=\psi(u)\psi(v)$ for all $u,v\in\mathcal{A}^{*}$. Morphisms can be naturally extended to $\mathcal{A}^{\mathbb{N}}$ by setting $\psi(u_{0}u_{1}u_{2}\cdots)=\psi(u_{0})\psi(u_{1})\psi(u_{2})\cdots\,$. A fixed point of a morphism $\psi$ is a sequence $\mathbf{u}$ such that $\psi(\mathbf{u})=\mathbf{u}$.

Consider a factor $w$ of a recurrent sequence $\mathbf{u}=u_{0}u_{1}u_{2}\cdots$. Let $i<j$ be two consecutive occurrences of $w$ in $\mathbf{u}$. Then the word $u_{i}u_{i+1}\cdots u_{j-1}$ is a return word to $w$ in $\mathbf{u}$. The set of all return words to $w$ in $\mathbf{u}$ is denoted by $\mathcal{R}_{\mathbf{u}}(w)$. If $\mathbf{u}$ is uniformly recurrent, the set $\mathcal{R}_{\mathbf{u}}(w)$ is finite for each factor $w$. If $w$ is a prefix of $\mathbf{u}$, then $\mathbf{u}$ can be written as a concatenation $\mathbf{u}=r_{d_{0}}r_{d_{1}}r_{d_{2}}\cdots$ of return words to $w$. The sequence $\mathbf{d}_{\mathbf{u}}(w)=d_{0}d_{1}d_{2}\cdots$ over the alphabet of cardinality $\#\mathcal{R}_{\mathbf{u}}(w)$ is called the derived sequence of $\mathbf{u}$ to $w$. If $w$ is not a prefix, then we construct the derived sequence in an analogous way starting from the first occurrence of $w$ in $\mathbf{u}$. The concept of derived sequences was introduced by Durand [Dur98].

In [DDP21] a handy formula for computation of the critical exponent and asymptotic critical exponent of uniformly recurrent sequences is deduced. It uses the notion of return words to a factor of a sequence.

Sturmian sequences, i.e., aperiodic balanced sequences over a binary alphabet, are a principal tool in the study of balanced sequences over arbitrary alphabets. In the sequel, we will restrict our consideration to standard sequences. Let us recall that a Sturmian sequence $\mathbf{u}$ is called a standard sequence if both sequences ${\tt a}\mathbf{u}$ and ${\tt b}\mathbf{u}$ are Sturmian. For each Sturmian sequence there exists a unique standard sequence having the same language and thus the same critical exponent and the asymptotic critical exponent. Sturmian sequences have well defined frequencies of letters. Let us recall that the frequency of a letter $a$ in a sequence $\mathbf{u}$ is the limit $\rho_{a}(\mathbf{u})=\lim_{n\to\infty}\frac{|u_{0}\cdots u_{n-1}|_{a}}{n}$ if it exists.

We use the characterization of standard sequences by their directive sequences. To introduce them, we recall two morphisms

If $\Delta_{0}=D$, then $\mathtt{b}$ is the most frequent letter in $\mathbf{u}$. Otherwise, $\mathtt{a}$ is the most frequent letter in $\mathbf{u}$. We adopt the convention that $\rho_{\tt b}(\mathbf{u})>\rho_{\tt a}(\mathbf{u})$ and thus the directive sequence of $\mathbf{u}$ starts with $D$. Let us write this sequence in the run-length encoded form $\mathbf{\Delta}=D^{a_{1}}G^{a_{2}}D^{a_{3}}G^{a_{4}}\cdots$, where all integers $a_{n}$ are positive. Then the number $\theta$ having the continued fraction expansion $\theta=[0,a_{1},a_{2},a_{3},\ldots]$ equals the ratio $\frac{\rho_{\tt a}(\mathbf{u})}{\rho_{\tt b}(\mathbf{u})}$ (see [BeSe02]) and $\theta$ is called the slope of $\mathbf{u}$.

The convergents to the continued fraction of $\theta$, usually denoted $\frac{p_{N}}{q_{N}}$, have a close relation to return words in a Sturmian sequence. Recall that the sequences $(p_{N})$ and $(q_{N})$ both satisfy the recurrence relation

with initial conditions $p_{-1}=1$, $p_{0}=0$ and $q_{-1}=0$, $q_{0}=1$. Two consecutive convergents satisfy $p_{N}q_{N-1}-p_{N-1}q_{N}=(-1)^{N+1}$ for every $N\in\mathbb{N}$.

Vuillon [Vui01] showed that an infinite recurrent sequence $\mathbf{u}$ is Sturmian if and only if each of its factors has exactly two return words. Moreover, the derived sequence of a Sturmian sequence to any of its factors is also Sturmian.

All bispecial factors of any standard sequence $\mathbf{u}$ are its prefixes. So, one of the return words to a bispecial factor of $\mathbf{u}$ is a prefix of $\mathbf{u}$.

To express the length of bispecial factors and their return words in a Sturmian sequence with slope $\theta$, we use for each $N\in\mathbb{N}$ the notation

$Q_{N}:=p_{N}+q_{N}$, where $\frac{p_{N}}{q_{N}}$ is the $N^{th}$ convergent to $\theta$,

i.e., the sequence $(Q_{N})$ satisfies (1) with initial conditions $Q_{-1}=1=Q_{0}$.

In the sequel, it will be necessary to recognize which vectors are Parikh vectors of some factors in a Sturmian sequence. The answer follows.

In 2000 Hubert [Hubert00] characterized balanced sequences over alphabets of cardinality bigger than 2 in terms of Sturmian sequences, colourings, and constant gap sequences.

There is a rich literature on a notion equivalent to constant gap sequences, the so-called exact covering systems, see [Znam1969, PoSch2002, GoGrBrSh2019].

Let $\mathcal{A},\mathcal{B}$ be two disjoint alphabets. The “discolouration map” $\pi$ is defined for any word or sequence over $\mathcal{A}\cup\mathcal{B}$; it replaces all letters from $\mathcal{A}$ by $\mathtt{a}$ and all letters from $\mathcal{B}$ by $\mathtt{b}$. If $\mathbf{v}=\mathrm{colour}(\mathbf{u},\mathbf{y},\mathbf{y}^{\prime})$, where $\mathbf{y}\in\mathcal{A}^{\mathbb{N}}$, $\mathbf{y}^{\prime}\in\mathcal{B}^{\mathbb{N}}$, then $\pi(\mathbf{v})=\mathbf{u}$ and $\pi(v)\in\mathcal{L}(\mathbf{u})$ for every $v\in\mathcal{L}(\mathbf{v})$.

As a consequence of the previous corollary when studying the asymptotic critical exponent of balanced sequences, we can limit our consideration to colourings of standard Sturmian sequences.

Hoffman et al. proved that any $d$-ary constant gap sequence satisfies $\mathrm{Per}\,\mathbf{y}\leq 2^{d-1}$ (see Theorem 2 in [Hof2011] based on Corollary 2 from [Si85]). Therefore, the first item of Proposition 14 leads to the following corollary.

The main task we solve in the paper is the following: for given $P$ and $P^{\prime}$ find a balanced sequence $\mathbf{v}$ such that its asymptotic critical exponent $E^{*}(\mathbf{v})$ has the least value among all balanced sequences which arise as colouring of Sturmian sequences by two constant gap sequences $\mathbf{y}$ and $\mathbf{y}^{\prime}$ with $P=\mathrm{Per}\,\mathbf{y}$ and $P^{\prime}=\mathrm{Per}\,\mathbf{y}^{\prime}$.

Having a method for solving this task, we are able to determine $RTB^{*}(d)$ for a fixed $d$. We apply the method to all pairs of $P,P^{\prime}$ such that $P=\mathrm{Per}\,\mathbf{y}$ for some constant gap sequence $\mathbf{y}$ over $d_{\tt a}$-ary alphabet and $P^{\prime}=\mathrm{Per}\,\mathbf{y}^{\prime}$ for some constant gap sequence $\mathbf{y}^{\prime}$ over $d_{\tt b}$-ary alphabet, where $d_{\tt a}+d_{\tt b}=d$.

For a fixed $d$ there are only finitely many pairs $P,P^{\prime}$ with the described property. It seems that to find the periods of all constant gap sequences over a $d$-ary alphabet is a difficult problem. Nevertheless, it is known (see [Schnabel2015]) that constant gap sequences over $d$ letters with $d\leq 12$ may be obtained by interlacing.

The interlacing $\mathbf{y}$ of $\mathbf{y}^{(0)},\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(k-1)}$ satisfies