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\leq n_{0},n_{1},\ldots ,n_{h}<b$ et $n_{h}>0$. La suite $n_{0}n_{1}\cdots n_{h}$ est souvent noté $\langle n\rangle _{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,\ldots ,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 :

Théorème (Cobham 1969) — Soit S un ensemble d'entiers naturels, et soient $k$ et $\ell$ deux entiers positifs multiplicativement indépendants. Alors S est reconnaissable par automate fini en base $k$ et en base $\ell$ si et seulement si S est ultimement périodique.

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 :

Théorème — Soient $k$ et $\ell$ deux entiers multiplicativement indépendants. Une suite est à la fois $k$-automatique et $\ell$-automatique seulement si elle est $1$-automatique.

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\leq 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

$\langle N,+,V_{r}\rangle$

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 $\langle N,+,V_{r}\rangle$ 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 $(\exists y)(x=y+y+1)$
• L’ensemble $\{2^{n}\mid n\geq 0\}$ des puissances de 2 est définissable par la formule toute simple $V_{2}(x)=x$.

Théorème de Cobham reformulé — Soit S un ensemble d'entiers naturels, et soient $k$ et $\ell$ deux entiers positifs multiplicativement indépendants. Alors S définissable au premier ordre dans $\langle N,+,V_{k}\rangle$ et dans $\langle N,+,V_{\ell }\rangle$ si et seulement si S est ultimement périodique.

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 $\langle N,+,V_{k}\rangle$ et $\langle N,+,V_{\ell }\rangle$ 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\ ,\quad 1\mapsto 10\ ,\quad 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'\in \mathbb {C} ,|z'|<z\}$. Ce sont exactement les valeurs propres dominantes des matrices entières positives primitives.

On a alors l'énoncé suivant :

Théorème de Cobham pour les substitutions — Soient α et β deux nombres de Perron multiplicativement indépendants. Alors une suite x à élément dans un ensemble fini et à la fois α-substitutive et β-substitutive si et seulement si x est ultimement périodique.

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 $\mathbb {R}$ et aux produits cartésiens $\mathbb {R} ^{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 ${\begin{pmatrix}3\\9\end{pmatrix}}$ est écrit comme ${\begin{pmatrix}0011\\1001\end{pmatrix}}={\begin{pmatrix}0\\1\end{pmatrix}}{\begin{pmatrix}0\\0\end{pmatrix}}{\begin{pmatrix}1\\0\end{pmatrix}}{\begin{pmatrix}1\\1\end{pmatrix}}$.

Théorème de Semenov (1997) — Soient $r$ et $s$ deux entiers positifs multiplicativement indépendants. Une partie $S$ de $N^{m}$ est $r$-reconnaissable et $s$-reconnaissable si et seulement si $S$ est une union finie de parties semi-linéaires.

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

• [1969] (en) Alan Cobham, « On the base-dependence of sets of numbers recognizable by finite automata », Mathematical Systems Theory, vol. 3, n^o 2,‎ 1969, p. 186–192 (DOI 10.1007/BF01746527, MR 0250789).

• [1972] (en) Alan Cobham, « Uniform tag sequences », Mathematical Systems Theory, vol. 6, n^os 1-2,‎ 1972, p. 164–192 (DOI 10.1007/BF01706087, MR 0457011).

• (en) Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences : theory, applications, generalizations, Cambridge, Cambridge University Press, 2003, 571 p. (ISBN 0-521-82332-3).

• Véronique Bruyère, « Around Cobham's theorem and some of its extensions », Dynamical Aspects of Automata and Semigroup Theories, Satellite Workshop of Highlights of AutoMathA, 2010 (consulté le 19 janvier 2017)
• (ru) Alexei Lvovich Semenov, « Predicates regular in two number systems are Presburger », Sib. Mat. Zh., vol. 18,‎ 1977, p. 403-418 (MR 0450050, zbMATH 0369.02023).

• Andrej A. Muchnik, « The definable criterion for definability in Presburger arithmetic and its applications », Theoret. Comput. Sci., vol. 290, n^o 3,‎ 2003, p. 1433–1444 (MR 1937730, zbMATH 1052.68079).

• (en) Fabien Durand, « Cobham's theorem for substitutions », Journal of the European Mathematical Society, vol. 13, n^o 6,‎ 2011, p. 1797–1812 (DOI 10.4171/JEMS/294, arXiv 1010.4009, lire en ligne).

• Fabien Durand et Michel Rigo, « On Cobham’s Theorem », dans J.-É. Pin (éditeur), Automata: from Mathematics to Applications, European Mathematical Society, 2010 (en préparation) (lire en ligne).

• Boris Adamczewski et Jason Bell, « Automata in number theory », dans J.-É. Pin (éditeur), Automata: from Mathematics to Applications, European Mathematical Society, 2010 (en préparation).

• Lucas Mol, Narad Rampersad, Jeffrey Shallit et Manon Stipulanti, « Cobham’s Theorem and Automaticity », International Journal of Foundations of Computer Science, vol. 30, n^o 08,‎ 2019, p. 1363–1379 (ISSN 0129-0541, DOI 10.1142/S0129054119500308, arXiv 1809.00679)

• Thijmen J. P. Krebs, « A More Reasonable Proof of Cobham’s Theorem », International Journal of Foundations of Computer Science, vol. 32, n^o 02,‎ 2021, p. 203207 (ISSN 0129-0541, DOI 10.1142/S0129054121500118, arXiv 1801.06704).