0.3.3 Ecarts et parties $k$-reconnaissables

Lorsque $X$ est $k$-reconnaissable, la distribution des $x_i$ possède des propriétés assez contraignantes. Elles s'expriment au moyen des deux nombres

$$% latex2html id marker 3484\left\{ \begin{array}{ccl} R_X&... ...{x_i}\\ [1ex] D_X&=&\limsup_i(x_{i+1}-x_i) \end{array}\right.$$

Ils estiment chacun asymptotiquement ``l'écart'' séparant deux éléments consécutifs de $X$. Il est clair que $R_X\geq 1$ et que $D_X > 0$. De plus, si $X$ est infini et si $D_X<\infty$ alors $R_X=1$. En effet, sous ces hypothèses

$$\frac{x_{i+1}}{x_i}=\frac{x_{i+1}-x_i}{x_i}+1\leq \frac{\sup_i(x_{i+1}-x_i)}{x_i}+1\to 1.$$

Proposition 0.3.4   Si $X$ est $k$-reconnaissable, alors $R_X<+\infty$.

Preuve. Cela arrive à cause de la Proposition . Avec ses notations, posons

$$y_j=\alpha k^{tj}+\beta.$$

C'est une sous-suite de $x_i$. Par conséquent si $i$ est assez grand, il existe $j$ tel que

$$y_j\leq x_i<x_{i+1}<y_{j+1}.$$

D'où

$$\frac{x_{i+1}}{x_i}=\frac{x_{i+1}}{y_{j+1}}\frac{y_j}{x_i}\frac{y_{j+1}}{y_j}\leq \frac{y_{j+1}}{y_j}.$$

Or le membre de droite est borné puisque $\lim_j\frac{y_{j+1}}{y_j}=k^t$.$\qed$

Voici le résultat principal de cette section.

Théorème 0.3.5   Si $X$ est $k$-reconnaissable, alors $R_X>1$ ou $D_X<+\infty$, ces deux situations étant mutuellement exclusives.

Preuve. On sait déjà qu'elles sont en effet exclusives vu que si $D_X$ est borné alors $R_X$ vaut $1$. Nous supposons désormais que $r_k(X)$ est un langage régulier et nous notons A le langage $r_k(X)\cup0\Sigma^*$, régulier lui aussi(^0.19). Deux cas se présentent alors. Ils épuisent toutes les possibilités.
a) Pour tout $w\in\Sigma^*$, il existe $s\in{\rm I\!N}$ tel que $w^{-1}.A$ contienne au moins un mot de chaque longueur $i\geq s$. On peut alors prendre le même $s$ pour tous les $w$. En effet, comme $A$ est régulier, son automate minimal est fini: il n'y a qu'un nombre fini d'ensembles de la forme $w^{-1}.A$. Un $s$ assez grand convient dès lors pour chacun. Prenons $w=r_k(n)$, où $n>0$. Il existe $v\in\Sigma^s$ tel que $wv\in A$. Comme $n>0$, $w$ ne commence pas par 0. Par conséquent, $wv$ est la représentation en base $k$ d'un élément de $X$, compris entre $nk^s$ et $(n+1)k^s$. Puisque $X$ rencontre chaque intervalle $[nk^s,(n+1)k^s[$, les différences $x_{i+1}-x_i$ sont majorées par $2k^s$ et $D_X<+\infty$.
b) Il existe $w\in\Sigma$ et une infinité de $i$ tels que $w^{-1}.A$ ne contienne aucun mot de longueur $i$. L'ensemble de ces $i$ contient une progression arithmétique $a+b{\rm I\!N}$ de raison $r>0$: comme $w^{-1}.A$ est régulier, l'ensemble des longueurs de ses éléments est une union finie de progressions arithmétiques. Son complémentaire en est donc une également(^0.20). Etant infini, il contient donc une progression de raison positive. Quitte à remplacer $w$ par un mot de la forme $wv$, où $v$ est de longueur $a$, nous pouvons supposer que $a=0$: $w^{-1}.A$ ne contient aucun mot de longueur $bt, t\in{\rm I\!N}$, ou encore, $A$ ne contient aucun élément de $w\Sigma^{bt}, t\in{\rm I\!N}$. En particulier, $w$ ne commence pas par 0 et représente donc un entier $n=val_k(w)>0$. De plus, aucun des entiers de l'intervalle $[nk^{bt},(n+1)k^{bt}[$ n'appartient à $X$ car ils sont représentés par des éléments de $w\Sigma^{bt}$. Dès que $i$ est assez grand, on a donc

$$x_i\leq n k^{bt}<(n+1)k^{bt}<x_{i+1}$$

pour un certain $t$. Il en résulte que

$$\frac{x_{i+1}}{x_i}\geq \frac{n+1}{n}\cdot$$

$\qed$

Corollaire 0.3.6   Les ensembles $\{n^r\vert n\in{\rm I\!N}\},r=2,3,\ldots$ ne sont $k$-reconnaissables pour aucune base $k$.

Preuve. En effet, on a simultanément $R_X=1$ et $D_X=+\infty$ pour chacun d'eux.$\qed$