1 Introduction↩︎

A central question in Diophantine approximation is to determine how well a given irrational real number \(\xi\) can be approximated by rational numbers.

It follows from the theory of continued fractions that every convergent \(p/q\) of \(\xi\) satisfies \(|\xi - p/q| < 1/q^2\). Consequently, we get the lower bound \(\mu (\xi) \ge 2\). In the opposite direction, an easy covering argument, usually called the Cantelli lemma, shows that we have \(\mu (\xi) \le 2\) (and thus \(\mu (\xi) = 2\)) for almost all \(\xi\), with respect to the Lebesgue measure. However, to determine the irrationality exponent of a given real number is a very difficult problem, unless we know explicitly its continued fraction expansion. For example, the irrationality exponent of \({\rm e}\) is equal to \(2\). By Roth’s Theorem, the irrationality exponent of any algebraic irrational real number is also equal to \(2\). Classical numbers known to have their irrationality exponent equal to \(2\) include non-zero rational powers of \({\rm e}\), badly approximable numbers, \(\tan \frac{1}{a}\), where \(a\) is any positive integer, etc. Further examples are given in [1], [2]. Note that the irrationality exponents of classical numbers like \(\pi\), \(\zeta(2)\), \(\zeta(3)\), \(\log (2)\) remain unknown. At present, the best known estimate for \(\pi\) is \(\mu (\pi) \le 7.10321\), established in [3].

Throughout the present paper, \(b\) always denotes an integer greater than or equal to \(2\) and \(\xi\) a real number. There exists a unique infinite sequence \((a_j)_{j \ge 1}\) of integers from \(\{0, 1, \ldots, b-1\}\), called the \(b\)-ary expansion of \(\xi\), such that \[\label{xiexp} \xi = \lfloor \xi \rfloor + \sum_{j\ge 1} \, \frac{a_j}{b^j}\tag{1}\] and \(a_j \not= b-1\) for infinitely many indices \(j\). Here, \(\lfloor \cdot \rfloor\) denotes the integer part function. Clearly, the sequence \((a_j)_{j \ge 1}\) is ultimately periodic if, and only if, \(\xi\) is rational.

Let us introduce some terminology from combinatorics on words. Let \(\mathcal{A}\) be a finite set called an alphabet and denote by \(|\mathcal{A}|\) its cardinality. A word over \(\mathcal{A}\) is a finite or infinite sequence of elements of \(\mathcal{A}\). For a (finite or infinite) word \({\boldsymbol{x}} = x_1 x_2 \ldots\) written over \(\mathcal{A}\), let \(n \mapsto p (n, {\boldsymbol{x}})\) denote its subword complexity function which counts the number of different subwords of length \(n\) occurring in \(\mathbf{x}\), that is, \[p (n,{\boldsymbol{x}}) = {\rm Card} \{ x_{j+1} x_{j+2} \dots x_{j+n} : j \ge 0 \}, \quad n \ge 1.\] Clearly, we have \[1 \le p(n, {\boldsymbol{x}}) \le |\mathcal{A}|^n, \quad n \ge 1.\] If \({\boldsymbol{x}}\) is ultimately periodic, then there exists an integer \(C\) such that \(p(n, {\boldsymbol{x}}) \le C\) for \(n \ge 1\). Otherwise, we have \[\label{pincr} p(n+1, {\boldsymbol{x}}) \ge p(n, {\boldsymbol{x}}) + 1, \quad n \ge 1,\tag{2}\] thus \(p(n, {\boldsymbol{x}}) \ge n+1\) for \(n \ge 1\). There exist uncountably many infinite words \({\boldsymbol{s}}\) over \(\{0, 1\}\) such that \(p(n, {\boldsymbol{s}}) = n+1\) for \(n \ge 1\). These words are called Sturmian words. Classical references on combinatorics on words and on Sturmian sequences include [4]–[6]. The Fibonacci word \({\boldsymbol{f}}\) defined in Section 5 is an emblematic example of a Sturmian word.

A natural way to measure the complexity of the real number \(\xi\) written in base \(b\) as in 1 is to count the number of distinct blocks of given length in the infinite word \({\boldsymbol{a}} = a_1 a_2 \ldots\). We set \[p(n, \xi, b) = p (n, {\boldsymbol{a}}), \quad n \ge 1.\]

A real number \(\xi\) is normal to base \(b\) if, for every \(k \ge 1\), every block of \(k\) digits over \(\{0, 1, \ldots b-1\}\) occurs in the \(b\)-ary expansion of \(\xi\) with the same frequency \(1/b^k\). In particular, if \(\xi\) is normal to base \(b\), then \(p(n, \xi, b) = b^n\) for every positive integer \(n\). To establish a good lower bound for \(p(n, \xi, b)\) is a first step towards the confirmation that \(\xi\) is normal to base \(b\). This point of view has been taken by Ferenczi and Mauduit [7], who showed that the \(b\)-ary expansion of an irrational algebraic number cannot be too simple.

It has been observed in [1] that the statements on the combinatorial structure of Sturmian words established in [8] and [9] almost immediately imply that the irrationality exponent of any real number, whose sequence of digits in some integer base is Sturmian, is greater than \(2\). In view of Roth’s Theorem mentioned above, this extends Theorem 1. The main result of [2], reproduced below, is much stronger and establishes an unexpected connection between the irrationality exponent of a real number and the complexity of its \(b\)-ary expansion. It asserts that any irrational real number, whose expansion in some integer base has sufficiently small complexity, has an exponent of irrationality larger than \(2\).

The purpose of the present work is to show how Theorem 2 can be strengthened by means of a more precise combinatorial study than that given in [2]. We establish the following result.

Theorem 3 improves [2], where, for \(\mu = 2\), we got the lower bounds \(9/8 = 1.125\) and \(8/7\), respectively. Inequality 3 gives a non-trivial result on the \(b\)-ary expansion of any real number \(\xi\) whose irrationality exponent satisfies \[2 \le \mu (\xi) < \mu_1 := 2.246 \ldots,\] where \(\mu_1\) is the root greater than \(2\) of the polynomial \(X^3 - 2 X^2 - X + 1\). Inequality 4 gives a non-trivial result on the \(b\)-ary expansion of any real number \(\xi\) whose irrationality exponent satisfies \[2 \le \mu (\xi) < \mu_2 := 2.324\ldots,\] where \(\mu_2\) is the root greater than \(2\) of the polynomial \(X(X-1)(X-2) - 1\). The ranges are larger than the one in [2], where \(\mu(\xi)\) has to be smaller than \(2.19 \ldots\) (which is the root greater than \(2\) of the polynomial \(2 X(X-1)(X-2) - 1\)). Thus, Theorem 3 applies to a slightly wider class of classical numbers than Theorem 2, which includes in particular the transcendental number \(\log (1 + \frac{1}{a})\), where \(a\) is a sufficiently large positive integer. More examples are given in [2]. As noted in [2], the badly approximable number \(\sum_{k \ge 0} 2^{-2^k}\) shows that Theorem 3 is sharp up to the values of the numerical constants.

A key ingredient for the proof of Theorems 2 and 3 is the study of a complexity function defined in terms of the smallest return time of a factor of an infinite word. For an infinite word \({\boldsymbol{x}} = x_1 x_2 \dots\) and an integer \(n \ge 1\), set \[r(n,{\boldsymbol{x}}) = \min \{ m \ge 1 : x_{i} \ldots x_{i+n-1} = x_{m-n+1} \ldots x_{m} \text{ for some } i \text{ in } \{1, \ldots , m-n\} \} .\] Said differently, \(r(n,\mathbf{x})\) denotes the length of the smallest prefix of \({\boldsymbol{x}}\) containing two (possibly overlapping) occurrences of some word of length \(n\).

A key ingredient in the proof of Theorem 2 is an improvement of the trivial inequality \({\rm Rep}({\boldsymbol{x}}) \ge {\rm rep}({\boldsymbol{x}})\). Namely, we established in [2] that \[\label{RrepPisa} {\rm Rep}({\boldsymbol{x}}) \ge {\rm rep}({\boldsymbol{x}}) + \frac{1}{1 + {\rm rep}({\boldsymbol{x}}) + ({\rm rep}({\boldsymbol{x}}))^2}.\tag{5}\] We improve this result in Section 3, where we establish the following lower bound.

Our paper is organized as follows. We gather several auxiliary combinatorial lemmas in Section 2. Then, we establish Proposition 4 in Section 3 and complete the proof of Theorem 3 in the subsequent section. We conclude the paper by some additional remarks.

2 Auxiliary combinatorial lemmas↩︎

The function \(n \mapsto r(n, {\boldsymbol{x}})\) defined in Section 1 has been introduced and studied in [10], where the following two assertions are established.

Lemma 3.1 of [2], reproduced below, shows how the functions \(n \mapsto p(n, {\boldsymbol{x}})\) and \(n \mapsto r(n, {\boldsymbol{x}})\) are related.

For a word \(U = u_1 \dots u_n\) composed of \(n\) letters, set \[\Lambda(U) = \{ 1 \le k < n : u_i = u_{i + k} \text{ for all }1 \le i \le n-k \}.\] An element of \(\Lambda(U)\) is called a period of \(U\). A finite word \(U\) is called periodic if \(\Lambda (U)\) is not empty. We stress that a period of a word of length \(n\) may not be a divisor of \(n\). The next lemma is a classical tool in combinatorics on words.

We conclude this section with an easy lemma, for which some notation is required.

3 Proof of Proposition 4↩︎

Let \(\mathbf{x}\) be an infinite word which is not ultimately periodic. For simplicity, we often write \(r(\cdot)\) for \(r(\cdot , {\boldsymbol{x}})\). Set \(\sigma = {\rm Rep}({\boldsymbol{x}})\) and \(\rho = {\rm rep}({\boldsymbol{x}})\). Let \({\varepsilon}\) be an arbitrarily small positive real number. We have \[\rho - {\varepsilon}\le \dfrac{r(n, {\mathbf{x}})}{n} \le \sigma + {\varepsilon}, \quad for all sufficiently large n.\] From Theorem 5, we note that \({\rm Rep}({\boldsymbol{x}}) \ge 2\). Therefore, we assume that \(\rho \ge \rho_2\), where \(\rho_2 := 1.754 \ldots\) is the real root of \(X (X- 1)^2 - 1\). This is equivalent to \[\frac{\rho+1}{2} + \frac{\sqrt{\rho^2(\rho-1)^2+4(\rho-1)}}{2\rho} \ge 2.\] Since \[\rho + \frac{1}{1+\rho} > \frac{\rho+1}{2} + \frac{\sqrt{\rho^2(\rho-1)^2+4(\rho-1)}}{2\rho},\] we also assume that \[\label{disj} \sigma < \rho + \frac{1}{1 + \rho}.\tag{6}\] Otherwise, Proposition 4 holds immediately. We will see in Section 5 that the inequality \(\sigma \ge \rho + 1 / (1 + \rho)\) does not hold for all \({\boldsymbol{x}}\). This justifies the assumption 6 .

Let \((n_j)_{j \ge 1}\) be the increasing sequence composed of all the jumps of the function \(n \mapsto r( n, {\boldsymbol{x}})\), that is, of all the integers \(n\) such that \(r(n + 1) > r(n) +1\). Between two consecutive jumps, the function \(n \mapsto r( n, {\boldsymbol{x}})\) has slope \(1\). Consequently, for \(j \ge 2\), we have \[r(n_{j-1} + h) = r(n_{j-1} + 1) + h - 1, \quad h=1, \ldots , n_j - n_{j-1},\] thus, in particular, \[\label{rcst} r(n_{j-1} + 1) = r(n_{j}) - n_{j} + n_{j-1} + 1.\tag{7}\] Observe that \[{\rm rep}({\boldsymbol{x}}) = \liminf_{j \to + \infty} \, \frac{r(n_j, {\boldsymbol{x}})}{n_j}, \quad {\rm Rep}({\boldsymbol{x}}) = \limsup_{j \to + \infty} \, \frac{r(n_j + 1, {\boldsymbol{x}})}{n_j +1}.\] We further define \[\beta ({\boldsymbol{x}}) = \liminf_{j \to + \infty} \, \frac{r(n_j + 1, {\boldsymbol{x}})}{n_j +1}.\]

We will bound \({\rm Rep}({\boldsymbol{x}})\) and \(\beta ({\boldsymbol{x}})\) from below. To this end, we take a large integer \(n\) in the sequence \((n_j)_{j \ge 1}\), that is, such that \(r(n+1) > r(n) + 1\), and we bound \(r(n+1) / (n+1)\) from below.

Let \(n\) be an integer such that \(r(n+1) > r(n) +1\). Let \(\lambda, \lambda'\) denote the positive integers defined by \[x_{r(n)-n+1}^{r(n)} = x_{r(n)-n+1-\lambda}^{r(n)-\lambda}, \quad x_{r(n+1)-n}^{r(n+1)} = x_{r(n+1)-n-\lambda'}^{r(n+1)-\lambda'}.\]

It follows from 6 that \[\label{rndiff} r(n+1) - r(n) \le \frac{n}{2}\tag{8}\] since \[r(n+1) - r(n) \le (\sigma - \rho + 2 {\varepsilon}) n + \sigma + {\varepsilon}< \left( \frac{1}{1 + \rho} +2{\varepsilon}\right) n+ \sigma + {\varepsilon}.\]

Observe that \[\lambda = \min\Lambda \bigl(x_{r(n)-n+1-\lambda}^{r(n)} \bigr), \quad \lambda' = \min \Lambda \bigl(x_{r(n+1)-n-\lambda'}^{r(n+1)} \bigr).\] Set \[V_n = x_{r(n+1)-n}^{r(n)} = x_{r(n+1)-n-\lambda}^{r(n)-\lambda} = x_{r(n+1)-n-\lambda'}^{r(n)-\lambda'}.\] The length \(v_n\) of \(V_n\) satisfies \[\label{lgth} v_n = r(n)-r(n+1)+n+1 < n.\tag{9}\] Note that the assumption 6 guarantees that \[v_n \ge \frac{\rho}{1 + \rho} n.\] We have \[\label{lambdadiff} \lambda \ne \lambda',\tag{10}\] since otherwise we would get from 8 that \(x_{r(n) - \lambda + 1} = x_{r(n) + 1}\), in contradiction to the definition of \(r(n)\).

Since there are two occurrences of \(V_n\) in \(x_1^{r(n) - \min\{\lambda, \lambda'\}}\), we have \[\begin{align} r(n)-\lambda \ge r(v_n), \;&\text{ if } \;\lambda < \lambda', \tag{11} \\ r(n)-\lambda' \ge r(v_n), \;&\text{ if } \;\lambda > \lambda'. \tag{12} \end{align}\] We distinguish five cases.

\(\bullet\) Assume that \(\lambda < \lambda'\). If \(\lambda \ge v_n\), then \[r(v_n) \le r(n) - \lambda \le r(n) - v_n = r(n+1) - n - 1 \le (\sigma + {\varepsilon}) (n+1) - n - 1\] and \[r(v_n) \ge (\rho - {\varepsilon}) v_n \ge (\rho - {\varepsilon}) \bigl( (\rho - {\varepsilon}) n - (\sigma + {\varepsilon}) (n+1) + n + 1 \bigr).\] Consequently, we get \[(\rho - {\varepsilon})^2 n \le (\sigma + {\varepsilon}) (\rho+1 - {\varepsilon}) (n+1) - (\rho + 1 - {\varepsilon}) (n+1),\] a contradiction with 6 if \({\varepsilon}\) is small enough. Thus, we have \(v_n > \lambda\). Furthermore, \[V_n = x_{r(n+1)-n-\lambda'}^{r(n)-\lambda'} = x_{r(n+1)-n}^{r(n)} is a subword of x_{r(n)-n+1}^{r(n)},\] thus \(\lambda\) is in \(\Lambda \bigl(x_{r(n+1)-n-\lambda'}^{r(n)-\lambda'} \bigr)\). It then follows from Lemma 3 that \[\label{ineq2:case12} r(n) -\lambda' \ge r(v_n - \lambda).\tag{13}\]

\(\bullet\) Assume that \(\lambda > \lambda'\) and \(r(n+1) -\lambda' < r(n) +1\). If \(\lambda' \ge n\), then \[r(v_n) \le r(n) - \lambda' \le r(n) - n.\] Arguing as above, we get as well a contradiction with 6 . Thus, we have \(n > \lambda'\). Furthermore, \[x_{r(n)-n+1-\lambda}^{r(n)-\lambda} = x_{r(n)-n+1}^{r(n)} is a subword of x_{r(n+1)-n-\lambda'}^{r(n+1)}, \] thus \(\lambda'\) is in \(\Lambda \bigl( x_{r(n)-n+1-\lambda}^{r(n)-\lambda} \bigr)\). It then follows from Lemma 3 that \[\label{ineq2:case3} r(n) -\lambda \ge r(n - \lambda').\tag{14}\]

\(\bullet\) Assume that \(\lambda > \lambda'\) and \(r(n+1) -\lambda' \ge r(n) +1\). Then, \[x_{r(n+1)-n-\lambda'-\lambda}^{r(n)-\lambda} = x_{r(n+1)-n-\lambda'}^{r(n)} is a subword of x_{r(n+1)-n-\lambda'}^{r(n+1)},\] thus \(\lambda'\) is in \(\Lambda \bigl( x_{r(n+1)-n-\lambda'-\lambda}^{r(n)-\lambda} \bigr)\). It then follows from Lemma 3 that \[\label{ineq2:case4} r(n) -\lambda \ge r(v_n).\tag{15}\]

\(\bullet\) Assume that \(r(n+1)-\lambda' \le r(n)-\lambda+1\). Then \(x_{r(n)-n+1-\lambda}^{r(n)}\) is a subword of \(x_{r(n+1)-n-\lambda'}^{r(n+1)}\), thus \(\lambda'\) is in \(\Lambda \bigl( x_{r(n)-n+1-\lambda}^{r(n)} \bigr)\). Since \(\lambda\) is also in \(\Lambda \bigl( x_{r(n)-n+1-\lambda}^{r(n)} \bigr)\), we deduce from Lemma 2 that \[\label{ineq3:case1} \lambda' > n+\lambda - \lambda +1 = n+1.\tag{16}\]

\(\bullet\) Assume that \(r(n+1)-\lambda' > r(n)-\lambda+1\). Then \(x_{r(n+1)-n-\lambda'}^{r(n)}\) is a subword of \(x_{r(n)-n+1-\lambda}^{r(n)}\), thus \(\lambda\) is in \(\Lambda \bigl( x_{r(n)-n+1-\lambda'}^{r(n)} \bigr)\) and we see that \[\lambda, \lambda' \in \Lambda \bigl( x_{r(n+1)-n-\lambda'}^{r(n)} \bigr).\] We deduce from Lemma 2 that \[\lambda' > v_n+\lambda' -\lambda +1,\] that is, \[\label{ineq3:case234} \lambda > v_n+ 1.\tag{17}\]

These five cases can be summarized in the following four cases:

\(\bullet\) Case (i): \(r(n+1)-\lambda' \le r(n)-\lambda+1\) (in this case we have \(\lambda < \lambda'\)).

We have 11 , 13 , 16 , that is, \[r(n)-\lambda \ge (\rho - {\varepsilon}) v_n, \quad r(n) -\lambda' \ge (\rho - {\varepsilon}) (v_n - \lambda), \quad \lambda' > n+1.\] Consequently, \[\begin{align} n+1 < \lambda' &\le r(n) - (\rho - {\varepsilon}) v_n + (\rho - {\varepsilon}) \lambda \\ & \le r(n) - (\rho - {\varepsilon}) v_n + (\rho - {\varepsilon}) r(n) - (\rho - {\varepsilon})^2 v_n, \end{align}\] thus \[n+1 < (1+ \rho - {\varepsilon}) r(n) - (\rho - {\varepsilon}) (1+ \rho - {\varepsilon}) v_n.\] Combining this with \[(\rho - {\varepsilon}) (1+ \rho - {\varepsilon}) r(n+1) = (r(n) + n + 1 - v_n) (\rho - {\varepsilon}) (1+ \rho - {\varepsilon}),\] given by 9 , we get \[(\rho - {\varepsilon}) (1+ \rho - {\varepsilon}) r(n+1) > (n+1) (1 + (\rho - {\varepsilon}) (1+ \rho - {\varepsilon}) ) + r(n) (1 + \rho - {\varepsilon}) (\rho - 1 - {\varepsilon}),\] thus, \[\label{beta1} \frac{r(n+1)}{n+1} > 1 + \frac{1}{ (\rho - {\varepsilon}) (1+ \rho - {\varepsilon}) } + \frac{r(n)}{n+1} \cdot \frac{\rho - 1 - {\varepsilon}}{\rho - {\varepsilon}}.\tag{18}\] By letting \({\varepsilon}\) tend to \(0\), we obtain \[\sigma - \rho \ge \frac{1}{\rho (\rho +1)}.\]

\(\bullet\) Case (ii): \(r(n)-\lambda +1< r(n+1)-\lambda'\) and \(\lambda < \lambda'\).

We have 11 , 17 . We get \[r(n)-\lambda \ge (\rho - {\varepsilon}) v_n, \quad \lambda > v_n+ 1.\] Consequently, \[(1 + \rho - {\varepsilon}) v_n < r(n) - 1,\] thus, by 9 , we obtain \[(1 + \rho - {\varepsilon}) r(n+1) > (1+\rho - {\varepsilon}) (r(n) + n + 1) - r(n) + 1\] and \[\label{beta2} \frac{r(n+1)}{n+1} > 1 + \frac{r(n)}{n+1} \cdot \frac{\rho - {\varepsilon}}{1 + \rho - {\varepsilon}}.\tag{19}\] This gives eventually \[\sigma - \rho \ge \frac{1}{\rho +1}.\]

\(\bullet\) Case (iii): \(r(n+1)-\lambda' < r(n) + 1\) and \(\lambda > \lambda'\).

We have 12 , 14 , 17 , that is, \[r(n)-\lambda' \ge (\rho - {\varepsilon}) v_n, \quad r(n) -\lambda \ge (\rho - {\varepsilon}) (n - \lambda'), \quad \lambda > v_n+ 1.\] Consequently, \[v_n + 1 < \lambda \le r(n) - (\rho - {\varepsilon}) n + (\rho - {\varepsilon}) \lambda' \le r(n) - (\rho - {\varepsilon}) n + (\rho - {\varepsilon}) r(n) - (\rho - {\varepsilon})^2 v_n,\] thus \[(1+ (\rho - {\varepsilon})^2) v_n + (\rho - {\varepsilon}) n + 1 < (1 + \rho - {\varepsilon}) r(n).\] By using by 9 , this implies \[(1+ (\rho - {\varepsilon})^2) r(n+1) > (1+ (\rho - {\varepsilon})^2) (r(n) + n +1) + (\rho - {\varepsilon}) n - (1 + \rho - {\varepsilon}) r(n),\] thus \[\label{beta3} \frac{r(n+1)}{n+1} > 1 + \frac{n}{n+1} \cdot \frac{\rho - {\varepsilon}}{1+ (\rho - {\varepsilon})^2} + \frac{r(n)}{n+1} \cdot \frac{(\rho - {\varepsilon})^2 - \rho + {\varepsilon}}{1+ (\rho - {\varepsilon})^2}.\tag{20}\] This gives eventually \[\sigma - \rho \ge \frac{1}{\rho^2 +1}.\]

\(\bullet\) Case (iv): \(r(n+1)-\lambda' \ge r(n)+1\) and \(\lambda > \lambda'\).

We have 15 , 17 , that is, \[r(n) -\lambda \ge (\rho - {\varepsilon}) v_n, \quad \lambda > v_n+ 1.\] As in Case (ii), we get \[\sigma - \rho \ge \frac{1}{\rho +1}.\]

To summarize, we have established that \[\sigma - \rho \ge \begin{cases} \dfrac{1}{\rho(\rho+1)}, &\text{ in Case (i)},\\ \dfrac{1}{\rho^2+1}, &\text{ in Case (iii)},\\ \dfrac{1}{\rho+1}, &\text{ in Cases (ii) and (iv)}.\\ \end{cases}\] This improves 5 , but we will do slightly better below. It may be tempting to conjecture that Case (ii) or Case (iv) occurs infinitely often, but the discussion in Section 5 shows that this is not true in whole generality.

But before going further, let us observe that, by 18 , 19 , and 20 , we get \[\label{liminfbeta} \beta({\boldsymbol{x}}) \ge \rho + \dfrac{1}{\rho(\rho+1)}.\tag{21}\]

For \(j \ge 1\), let \(\lambda_j\) be the positive integer such that \[x^{r(n_j)}_{r(n_j)-n_j+1} = x^{r(n_j) - \lambda_j}_{r(n_j)-n_j+1 - \lambda_j}.\] By 10 , there exist infinitely many integers \(j\) such that \(\lambda_{j+1} > \lambda_j\). Hence, there are infinitely many integers \(n\) for which we are in Case (i) or in Case (ii).

Therefore, Case (i) happens infinitely often and we consider now the subsequent jump. This means that we take integers \(n\) and \(n+k\) such that \[r(n+1) > r(n) +1, \;r(n+k+1) > r(n+k) +1, \; r(n+k) = r(n+1) + k-1.\] This implies that \(r(m+1) = r(m) + 1\) for \(m=n+1, \ldots , n+k-1\). Let \(\lambda, \lambda', \lambda''\) be the integers satisfying \[x_{r(n)-n+1}^{r(n)} = x_{r(n)-n+1-\lambda}^{r(n)-\lambda}, \quad x_{r(n+1)-n}^{r(n+1)} = x_{r(n+1)-n-\lambda'}^{r(n+1)-\lambda'},\] \[x_{r(n+k+1)-n-k}^{r(n+k+1)} = x_{r(n+k+1)-n-k-\lambda''}^{r(n+k+1)-\lambda''}.\]

Since \(r(n+1)+k-1 = r(n+k) \ge (\rho - {\varepsilon}) (n+k)\), we get \[\label{kbound} k \le \frac{ r(n+1) - (\rho - {\varepsilon}) n -1}{\rho - {\varepsilon}-1}.\tag{22}\] By letting \({\varepsilon}\) tend to \(0\), this gives \[\label{kboundbis} k \le \frac{ \sigma - \rho}{\rho -1} \, n.\tag{23}\]

Since we are in Case (i), we get 16 , that is, \[\label{minlambda} \lambda' > n + 1.\tag{24}\] For the subsequent jump, we are in one of the cases (i), (ii), (iii), or (iv). Since Cases (ii) and (iv) can occur only finitely often, we have only to consider Cases (i) and (iii).

\(\bullet\) Case (i) for the subsequent jump: \(r(n+k+1)-\lambda'' \le r(n+k)-\lambda'+1\) (in this case we have \(\lambda' < \lambda''\)).

Then, by 11 we have \[r(n+k)-\lambda' \ge (\rho - {\varepsilon}) v_{n+k} = (\rho - {\varepsilon}) (r(n+k) - r(n+k+1) +n+k+1),\] thus, by 24 , \[\begin{align} (\rho - {\varepsilon}) r(n+k+1) &\ge (\rho - {\varepsilon}-1) r(n+k) + (\rho - {\varepsilon}) (n+k+1) +\lambda' \\ &> (\rho - {\varepsilon}) (\rho - {\varepsilon}-1) (n+k) + (\rho - {\varepsilon}) (n+k+1) + n+1 \\ & = (\rho - {\varepsilon})^2 (n+k) + \rho - {\varepsilon}+ n+1. \end{align}\] Combined with 23 , this gives \[\begin{align} \frac{r(n+k+1)}{n+k+1} & > \frac{(\rho - {\varepsilon})(n+k) + 1}{n+k+1} + \frac{n+1}{(\rho - {\varepsilon}) (n+k+1)} \\ & \ge \frac{(\rho - {\varepsilon})(n+k) + 1}{n+k+1} + \frac{n+1}{(\rho-{\varepsilon}) (n + \frac{ \sigma - \rho}{\rho -1}n +1)}. \end{align}\] By letting \({\varepsilon}\) tend to \(0\), we get \[\sigma \ge \rho + \frac{\rho-1}{\rho(\sigma -1)}.\]

\(\bullet\) Case (iii) for the subsequent jump: \(r(n+k+1)-\lambda'' < r(n+k) + 1\) and \(\lambda' > \lambda''\).

Then, by 12 and 14 we have \[r(n+k)- (\rho - {\varepsilon}) v_{n+k} \ge \lambda'' \ge n+k + \frac{\lambda'}{\rho - {\varepsilon}} - \frac{r(n+k)}{\rho - {\varepsilon}}.\] Instead of the lower bound \(\lambda' > v_{n+k} + 1\), we use 24 and obtain \[\begin{gather} (\rho - {\varepsilon}) r(n+k)- (\rho - {\varepsilon})^2 (r(n+k) - r(n+k+1) +n+k+1) \\ > (\rho - {\varepsilon}) (n+k) + n + 1 - r(n+k). \end{gather}\] Letting \({\varepsilon}\) tend to \(0\), this gives \[\rho^2 r(n+k+1) \ge (\rho^2 - \rho - 1) r(n+k) + \rho (\rho +1) (n+k) + n+1 + \rho^2.\] By dividing both members of the inequality by \(n+k+1\), using 23 , we eventually arrive at \[\sigma \ge \rho + \frac{\rho-1}{\rho^2( \sigma -1)}.\]

Consequently, we have shown that, in every case, we have \[\sigma \ge \rho + \frac{\rho - 1}{\rho^2 (\sigma - 1)}.\] This proves Proposition 4. This can be rewritten as \[\label{mino} \sigma \ge \frac{\rho + 1}{2} + \frac{\sqrt{\rho^2 (\rho - 1)^2 + 4(\rho - 1)}}{2 \rho}.\tag{25}\] A rapid calculation shows that the right hand side of 25 is larger than \(\rho + 1 / (\rho^2 + 1)\) for \(\rho \ge \rho_2\).

4 Proof of Theorem 3↩︎

Observe that, by definition of the sequence \((n_j)_{j \ge 1}\), we have (see 7 ) \[r(n_{j+1}, {\boldsymbol{x}}) = r(n_j + 1, {\boldsymbol{x}}) + n_{j+1} - n_j - 1 \ge (\rho - {\varepsilon}) n_{j+1}.\] Consequently, \[\label{nj1bound} n_{j+1} \le \frac{r(n_j + 1, {\boldsymbol{x}}) - n_j - 1}{\rho - 1 - {\varepsilon}}.\tag{26}\] Let \(n\) be an integer with \(n_j + 1 \le n \le n_{j+1}\). By 2 and Lemma 1 we have \[p(n, {\boldsymbol{x}}) \ge p(n_j + 1, {\boldsymbol{x}}) + n - n_j - 1 \ge r(n_j + 1, {\boldsymbol{x}}) + n - 2 n_j - 2,\] thus \[\frac{p(n, {\boldsymbol{x}})}{n} \ge 1 + \frac{r(n_j + 1, {\boldsymbol{x}}) - 2 n_j - 2}{n} \ge 1 + \frac{r(n_j + 1, {\boldsymbol{x}}) - 2 n_j - 2}{n_{j+1}}.\] Combined with 26 , this gives \[\begin{align} \frac{p(n, {\boldsymbol{x}})}{n} & \ge 1 + (\rho - 1 - {\varepsilon}) \, \frac{r(n_j + 1, {\boldsymbol{x}}) - 2 n_j - 2}{r(n_j + 1, {\boldsymbol{x}}) - n_j - 1} \\ & \ge \rho - {\varepsilon}- (\rho - 1 - {\varepsilon}) \, \frac{1}{\frac{r(n_j + 1, {\boldsymbol{x}})}{n_j + 1} - 1} \\ & \ge \rho - {\varepsilon}- (\rho - 1 - {\varepsilon}) \, \frac{1}{ \beta({\boldsymbol{x}}) - {\varepsilon}- 1}, \end{align}\] if \(j\) is sufficiently large. Since \({\varepsilon}\) can be taken arbitrarily small, we deduce from 21 that \[\label{liminfpn} \liminf_{n \to + \infty} \, \frac{p(n, {\boldsymbol{x}})}{n} \ge \rho - \frac{\rho - 1}{\rho + \dfrac{1}{\rho(\rho+1)} - 1} = \rho \cdot \frac{ \rho^3 - \rho^2 - \rho + 2 }{\rho^3 - \rho +1}.\tag{27}\] Note that 21 and 27 give trivial bounds if \(\rho < \rho_1\), where \(\rho_1 : = 1.8019\dots\) is the root greater than 1 of the polynomial \(X^3-X^2-2X+1\).

Let \(b \ge 2\) be an integer. Our last auxiliary result establishes a close connection between the exponent of repetition of an infinite word \({\mathbf{x}}\) written over \(\{0, 1, \ldots , b-1\}\) and the irrationality exponent (see Definition 1) of the real number whose \(b\)-ary expansion is given by \({\boldsymbol{x}}\). This is [2].

Lemma 4 shows that, when the exponent of repetition of an infinite word \({\boldsymbol{x}} = x_1 x_2 \ldots\) is less than \(2\), then the irrationality exponent of the associated real number \(\xi := \sum_{k \ge 1} \, {x_k}/{b^k}\) exceeds \(2\). Indeed, there are \({\varepsilon}> 0\) and infinitely many pairs of positive integers \((u, v)\) such that \[\| b^u (b^v - 1) \xi \| < \frac{1}{(b^u (b^v - 1))^{1 + {\varepsilon}}} .\] This does not mean, however, that all the (or all but finitely many) best rational approximations to \(\xi\) can be read off its \(b\)-ary expansion. In particular, we do not know if (nor under which additional assumptions) equality holds in 28 .

We are in position to complete the proof of Theorem 3.

Let \(b \ge 2\) be an integer and \(\xi\) an irrational real number. Put \(\mu = \mu (\xi)\). Write \(\xi\) in base \(b\) as in 1 and put \({\mathbf{a}} = a_1 a_2 \ldots\). Lemma 4 asserts that \[{\rm rep}({\mathbf{a}}) \ge \frac{\mu}{\mu - 1}.\] Combined with 25 , this gives \[{\rm Rep}({\mathbf{a}}) \ge \frac{\mu (2 \mu - 1) + \sqrt{ 4(\mu - 1)^3 + \mu^2}}{2 \mu (\mu - 1)}.\] By Theorem 5, this is non-trivial as soon as the lower bound is greater than or equal to \(2\), that is, as soon as \(\mu\) is less than the root \(\mu_2\). Observe that \(\mu_i = \rho_i / (\rho_i - 1)\) for \(i =1,2\). This gives \[\limsup_{n \to + \infty} \, \frac{p(n, {\mathbf{a}})}{n} \ge {\rm Rep}({\mathbf{a}}) - 1 \ge \frac{\mu + \sqrt{ 4(\mu - 1)^3 + \mu^2 } }{2 \mu (\mu - 1)}.\] As well, by 27 , we obtain \[\liminf_{n \to + \infty} \, \frac{p(n, {\mathbf{a}})}{n} \ge \rho \cdot \frac{ \rho^3 - \rho^2 - \rho + 2 }{\rho^3 - \rho +1} \ge \frac{\mu}{\mu - 1} \cdot \frac{\mu^3 - 3 \mu^2 + 5 \mu - 2}{\mu^3 - \mu^2 + 2 \mu - 1}.\] We have completed the proof of Theorem 3.

5 Final discussion↩︎

The Fibonacci word \[{\boldsymbol{f}}= f_1 f_2 f_3 \ldots = 010010100100101001010 \ldots\] is defined as the limit of the sequence of finite words \(({\boldsymbol{f}}_j)_{j \ge 1}\), where \({\boldsymbol{f}}_1 = 0\), \({\boldsymbol{f}}_2 = 01\), and \({\boldsymbol{f}}_{j+2} = {\boldsymbol{f}}_{j+1} {\boldsymbol{f}}_j\), for \(j \ge 1\). Clearly, the length of \({\boldsymbol{f}}_j\) is equal to the Fibonacci number \(F_j\) for \(j \ge 1\). We check that, for \(n \ge 3\), we have \[r(F_{n}-2, {\boldsymbol{f}}) = F_{n+1} - 2, \quad r(F_{n}-1, {\boldsymbol{f}}) = 2 F_{n} - 1,\] and \[r(F_n + h, {\boldsymbol{f}}) = 2 F_n + h, \quad h=-1, 0, \ldots , F_{n-1} - 2.\] We derive that \({\rm rep}({\boldsymbol{f}}) = (1 + \sqrt{5})/2\) and \({\rm Rep}({\boldsymbol{f}}) = 2\), thus \[{\rm Rep}({\boldsymbol{f}}) = {\rm rep}({\boldsymbol{f}}) + \frac{1}{1 + {\rm rep}({\boldsymbol{f}})}.\] As noted in the course of Section 3, it could be tempting to conjecture that \[{\rm Rep}({\boldsymbol{x}}) - {\rm rep}({\boldsymbol{x}}) \ge \frac{1}{1 + {\rm rep}({\boldsymbol{x}})},\] for every \({\boldsymbol{x}}\) which is not ultimately periodic. This is however not true. Indeed, we proved in [10] the existence of a Sturmian word \({\boldsymbol{s}}\) such that \({\rm rep}({\boldsymbol{s}}) = \sqrt{10} - \frac{3}{2}\). A rapid calculation shows that \[{\rm rep}({\boldsymbol{s}}) + \frac{1}{1 + {\rm rep}({\boldsymbol{s}})} = \frac{43}{39} \sqrt{10} - \frac{113}{78} = 2.037\ldots ,\] while Theorem 5 asserts that \({\rm Rep}({\boldsymbol{s}}) = 2\).

The difficulty for estimating the gap between \({\rm Rep}({\boldsymbol{x}})\) and \({\rm rep}({\boldsymbol{x}})\) comes from the following fact. At a jump \(n_j\) of the function \(n \mapsto r(n, {\boldsymbol{x}})\), the second occurrence of a word of length \(n_{j} +1\) in \({\boldsymbol{x}}_1^{r(n_{j} +1, {\boldsymbol{x}})}\) may overlap the second occurrence of a word of length \(n_{j}\) in \({\boldsymbol{x}}_1^{r(n_{j}, {\boldsymbol{x}})}\). If there are no such overlaps when \(n_j\) is sufficiently large, then we say that the word \({\boldsymbol{x}}\) has the disjointness property and we have \[r(n_{j} + 1, {\boldsymbol{x}}) - n_{j} - 1 \ge r(n_{j}, {\boldsymbol{x}}),\] hence, \[\label{Rep1rep} {\rm Rep}({\boldsymbol{x}}) \ge {\rm rep}({\boldsymbol{x}}) + 1.\tag{29}\] This disjointness property is automatically satisfied if, instead of looking for repetitions of an arbitrary word, we consider only repetitions of the digit \(0\), that is, if we look only at large blocks of \(0\). In that case, \(r(n, {\boldsymbol{x}})\) is replaced by the length of the shortest prefix of \({\boldsymbol{x}}\) containing two occurrences of \(0^n\). This special case corresponds to the approximation by rational numbers whose denominator is a power of \(b\) and has been studied in [12]. The inequality 29 then corresponds to the inequality \(v_b \ge {\widehat v}_b / (1 - {\widehat v}_b)\) proved in [12]. Here, as noted below Lemma 4, we consider approximation by rational numbers whose denominator is of the form \(b^u (b^v - 1)\), for positive integers \(u\) and \(v\). This explains why the combinatorial analysis is much more delicate in the present case than in [12].

References↩︎