Théorème de Cobham

Le théorème de Cobham est un théorème de combinatoire des mots qui a des connexions importantes avec la théorie des nombres, et notamment des nombres transcendants, et avec la théorie des automates. Le théorème stipule que si les écritures, en deux bases multiplicativement indépendantes, d'un ensemble d'entiers naturels S sont des langages rationnels, alors l'ensemble S est une union finie de progressions arithmétiques. Le théorème a été prouvé par Alan Cobham en 1969. Depuis, il a donné lieu à de nombreuses extensions et généralisations.

Définitions

Soit $b>0$ un entier. L'écriture en base $b$ d'un entier naturel $n$ est la suite de chiffres $n_0{n}_1\cdots n_h$ tels que

$n=n_0+n_{1}b+\cdots +n_h{b}^h$

avec $0\le n_0,n_1,\dots ,n_h<b$ et $n_h>0$. La suite $n_0{n}_1\cdots n_h$ est souvent noté $⟨n{⟩}_b$ ou plus simplement $n_b$.

Un ensemble d'entiers naturels S est reconnaissable en base $b$ ou plus simplement $b$-reconnaissable si l'ensemble $\{n_b\mid n\in S\}$ des écritures en base b de ses éléments est un langage reconnu par un automate fini, sur l'alphabet $\{0,1,\dots ,b-1\}$.

Deux entiers positifs $k$ et $\ell$ sont multiplicativement indépendants s'il n'existe pas d'entiers non nuls $p$ et $q$ tels que $k^p={\ell }^q$. Par exemple, 2 et 3 sont multiplicativement indépendants, alors que 8 et 16 ne le sont pas puisque $8^4=16^3$. Deux entiers sont multiplicativement dépendants si et seulement s'ils sont puissances d'un même troisième entier.

Énoncés

Énoncé original

Plusieurs énoncés équivalents du théorème ont été donnés. La version originale de Cobham est la suivante : Modèle:Théorème

Une autre façon d'énoncer le théorème le relie aux suites automatiques. Cobham lui-même les appelle « uniform tag sequences ». Il se trouve sous la forme suivante dans le livre d'Allouche et Shallit : Modèle:Théorème

On peut en effet montrer que la suite caractéristique d'un ensemble entiers naturels S reconnaissable par automate fini en base k est une suite k-automatique et que réciproquement, pour toute suite k-automatique $u$ et tout entier $0\le i<k$, l'ensemble $S_i$ des entiers $s$ tels que $u_s=i$ est reconnaissable en base $k$.

Formulation en logique

Le théorème de Cobham peut se formuler dans une logique du premier ordre, en utilisant un théorème démontré par Büchi en 1960. Cette formulation logique a donné lieu à des extensions et généralisations. L'expression logique fait appel à la théorie

$⟨N,+,V_r⟩$

des entiers naturels équipés de l'addition et de plus de la fonction $V_r$ définie par V_r(0)=1 et pour un entier positif $n$, prend la valeur $V_r(n)=m$ si $r^m$ est la plus haute puissance de $r$ qui divise $n$. Par exemple, $V_2(20)=4$, et $V_3(20)=1$. Un ensemble

Un ensemble d’entiers $S$ est définissable en logique du premier ordre dans $⟨N,+,V_r⟩$ s’il peut être décrit par un formule du premier ordre avec égalité, addition et $V_r$.

Exemples :

• L’ensemble des nombres impairs est définissable (sans $V_r$) par la formule $(\mathrm{\exists }y)(x=y+y+1)$
• L’ensemble $\{2^n\mid n\ge 0\}$ des puissances de 2 est définissable par la formule toute simple $V_2(x)=x$.

On peut pousser plus loin l’analogie avec la logique en notant que S est définissable au premier ordre dans l’arithmétique de Presburger si et seulement s’il est ultimement périodique. Ainsi, un ensemble S est définissable dans les logiques $⟨N,+,V_k⟩$ et $⟨N,+,V_{\ell }⟩$ si et seulement s'il est définissable dans l'arithmétique de Presburger.

Généralisations

Approche par morphisme

Une suite automatique est un mot morphique particulier, dont le morphisme générateur est uniforme. Un ensemble d'entiers est donc k-reconnaissable si et seulement si sa suite caractéristique est engendrée par un morphisme uniforme suivie d'un morphisme de codage. Par exemple, la suite caractéristique des puissances de 2 est produite par le morphisme 2-uniforme sur l'alphabet $B=\{a,0,1\}$ défini par

$a\mapsto a1,1\mapsto 10,0\mapsto 00$

qui engendre le mot infini

$a11010001\cdots$,

suivi du morphisme de codage (c'est-à-dire lettre à lettre) qui envoie $a$ sur $0$ et laisse $0$ et $1$ inchangés, ce qui donne $011010001\cdots$.

La notion a été étendue comme suit : Un mot morphique $s$ est $\alpha$-substitutif pour un certain nombre $\alpha$ s'il s'écrit sous la forme

$s=\pi (f^{\omega }(b))$

où le morphisme $f:B^{*}\to B^{*}$, prolongeable en $b$, a les propriétés suivantes :

• toutes les lettres de $B$ ont des occurrences dans $f^{\omega }(b)$, et
• $\alpha >1$ est la valeur propre dominante de la matrice du morphisme $f$.

Un ensemble S d'entiers naturels est $\alpha$-reconnaissable si sa suite caractéristique $s$ est $\alpha$-substitutive.

Une dernière définition : Un nombre de Perron est un nombre algébrique $z>1$ tel que tous ses conjugués appartiennent au disque $\{z^{\prime }\in ℂ,|z^{\prime }|<z\}$. Ce sont exactement les valeurs propres dominantes des matrices entières positives primitives.

On a alors l'énoncé suivant :

Approche logique

L'équivalence logique a permis de considérer des situations plus générales : les suites automatiques sur les entiers naturels $\mathbb{N}$ ou ensembles reconnaissables ont été étendues aux entiers relatifs $\mathbb{Z}$, aux produits cartésiens ${\mathbb{N}}^m$, aux nombres réels $ℝ$ et aux produits cartésiens ${ℝ}^m$.

Extension à $\mathbb{Z}$

On code les entiers base $k$ en faisant précéder l’écriture d'un entier positif par le chiffre 0, et d’un entier négatif par $k-1$ suivi du complément à $k$. Par exemple, en base 2, l’entier -6=-8+2 s’écrit 1010. Les puissances de 2 s’écrivent 010^* , et leurs opposés 110^* (car 11000 = -16+8=-8)

Extension à ${\mathbb{N}}^m$

Une partie $X$ de $N^m$ est reconnaissable en base $k$ si les éléments de $X$, écrits comme vecteurs à $m$ composantes sont reconnaissables sur l’alphabet produit.

Par exemple

En base 2, on a $3=11_2$ et $9=1001_2$; le vecteur $\left(\begin{array}{c}3\\ 9\end{array}\right)$ est écrit comme $\left(\begin{array}{c}0011\\ 1001\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)\left(\begin{array}{c}0\\ 0\end{array}\right)\left(\begin{array}{c}1\\ 0\end{array}\right)\left(\begin{array}{c}1\\ 1\end{array}\right)$.

Une preuve élégante de ce théorème est de Muchnik en 2003, par récurrence sur $m$.

D'autres extensions ont été données aux nombres réels et aux vecteurs de nombres réels.

Démonstrations

Samuel Eilenberg énonce le théorème sans preuve dans son livre ; il dit « The proof is correct, long, and hard. It is a challenge to find a more reasonable proof of this fine theorem ». Georges Hansel a proposé une preuve plus simple, publiée dans des actes difficilement accessibles d'un colloque. La preuve de Dominique Perrin et celle du livre d'Allouche et Shallit contiennent la même erreur dans un des lemmes, mentionnée dans la liste d'erratas du livre. Cette erreur a été relevée dans une note de Tomi Kärki, et corrigée par Michel Rigo et Laurent Waxweiler. Cette partie de la démonstration a fait l'objet d'une rédaction récente.

En janvier 2018, Thijmen J. P. Krebs annonce, sur Arxiv, une preuve simplifiée du théorème original, basée sur un critère d'aproximation de Dirichlet plutôt que de Kronecker ; l’article est paru en 2021. La méthode employée est raffinée et utilisée par Mol, Rampersad, Shallit et Stipulanti.

Bibliographie

• Modèle:Article.

• Modèle:Article.

• Modèle:Ouvrage.

• Modèle:Lien web
• Modèle:Article.

• Modèle:Article.

• Modèle:Article.

• Modèle:Chapitre.

• Modèle:Chapitre.

• Modèle:Article

• Modèle:Article.