Lorsque est -reconnaissable, la distribution des possède des propriétés assez contraignantes. Elles s'expriment au moyen des deux nombres
Ils estiment chacun asymptotiquement ``l'écart'' séparant deux éléments consécutifs de .
Il est clair que et que . De plus, si est infini et si
alors . En effet, sous ces hypothèses
Proposition 0.3.4
Si est -reconnaissable, alors
.
Preuve. Cela arrive à cause de la Proposition . Avec ses notations, posons
C'est une sous-suite de . Par conséquent si est assez grand, il existe tel que
D'où
Or le membre de droite est borné puisque
.
Voici le résultat principal de cette section.
Théorème 0.3.5
Si est -reconnaissable, alors ou
, ces deux situations étant mutuellement exclusives.
Preuve. On sait déjà qu'elles sont en effet exclusives vu que si est borné alors vaut .
Nous supposons désormais que est un langage régulier et nous notons A le langage
, régulier lui aussi(0.19). Deux cas se présentent alors. Ils épuisent toutes les possibilités.
a) Pour tout
, il existe
tel que contienne au moins un mot de chaque longueur . On peut alors prendre le même pour tous les . En effet, comme est régulier, son automate minimal est fini: il n'y a qu'un nombre fini d'ensembles de la forme . Un assez grand convient dès lors pour chacun. Prenons , où . Il existe
tel que . Comme , ne commence pas par 0. Par conséquent, est la représentation en base d'un élément de , compris entre et . Puisque rencontre chaque intervalle
, les différences
sont majorées par et
.
b) Il existe
et une infinité de tels que ne contienne aucun mot de longueur . L'ensemble de ces contient une progression arithmétique
de raison : comme 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 par un mot de la forme , où est de longueur , nous pouvons supposer que : ne contient aucun mot de longueur
, ou encore, ne contient aucun élément de
. En particulier, ne commence pas par 0 et représente donc un entier
. De plus, aucun des entiers de l'intervalle
n'appartient à car ils sont représentés par des éléments de
. Dès que est assez grand, on a donc
pour un certain . Il en résulte que
Corollaire 0.3.6
Les ensembles
ne sont -reconnaissables pour aucune base .