Suites automatiques

Xuedong Shang
École Normale Supérieure

26 Janvier 2012

1 Définitions et exemples
1.1 La suite de Thue-Morse
1.2 La suite de Rudin-Shapiro
2 Théorème de Cobham
2.1 Le q-noyau
2.2 Théorème de Cobham
3 Théorème de Christol
3.1 Opérateur de Cartier
3.2 Théorème de Christol
4 Divers

Abstract

Nous donnons ici, dans ce petit rapport, un premier traitement, très bref, des suites engendrées par un automate, modèle le plus simple de machine. Une suite automatique n’est pas nécessairement très simple ou régulière (ultimement périodique par exemple) malgré le fait que cela soit dûe à un automate dont les états sont finis. La premère partie de ce rapport est consacrée à une première aperçu des suites automatiques avec quelques exemples connus. Puis nous traiterons quelques caractérisations de l’automaticité en cherchant les liens entre les automates et leurs suite engendrée associée. À la fin, nous donnerons certains résultats divers sur les suites automatiques.

1 Définitions et exemples

On va commencer par définir la k-automaticité et donner deux exemples de suites 2-automatiques. Ces suites présenteront des similarité dont les liens seront développés dans la partie suivante.

Les automates que l’on va utiliser sont déterministes et complets. L’ensemble des états sera noté Q et au lieu d’avoir certains états finaux on dispose d’une fonction de sortie τ qui à chaque état associe un valeur "de sortie".

Définition 1. Un automate fini est la donnée de {Q, Σ,δ,i,τ, Γ} où Q est l’ensemble des états, i ∈ Q est l’état initial, Σ est l’alphabet d’entrée, δ la fonction de transition de Q × Σ dans Q. Γ l’alphabet de sortie et τ la fonction de sortie de Q dans Γ.

On remarque que pour obtenir un automate usuel, il suffit de prendre Γ = {0, 1} et de considérer q état final si et seulement si τ(q) = 1. Dans la suite, on n’introduit plus l’alphabet de sortie Γ dans l’automate s’il n’y pas d’ambiguïté.

Définition 2. Soit k un entier ≥ 2. On dit qu’une suite (u_n)_n est k-automatique s’il existe un automate = {Q, Σ,δ,i,τ} tel que :

∀n, τ(δ(i,⟨n⟩k)) = un

où ⟨n⟩_k désigne l’écriture en base k de n à partir du chiffre de poids faible. Si on lit dans l’automate la suite constituée des chiffres de n en base k à partir du chiffre de poids faible, on tombe sur un état dont la valeur de sortie est u_n. Il est tout à fait naturel de considérer que la fonction de sortie est à valeur dans le même ensemble que la suite et que les arêtes de l’automate sont étiqueées par {0, 1, ⋅⋅⋅ ,k - 1}.

Remarque 3. Un tel automate est appelé k-automate, et on peut ainsi dire qu’une suite est k-automatique si elle est engendrée par un k-automate.

1.1 La suite de Thue-Morse

La suite de Thue-Morse (appelée souvent suite de Prouhet-Thue-Morse chez les francophones) fut décrite pour la première fois par le mathématicien français Eugène Prouhet en 1851. Il la utilisa pour donner une solution à un problème de théorie des nombres qui s’appelle le problème de Prouhet-Tarry-Escott. La suite fut redécouverte par le mathématicien norvégien Axel Thue dans un article publié en 1906 qui est l’article fondateur de la combinatoire des mots. Puis Marston Morse, en 1922, donna une nouvelle interprétation de la suite, dans le cadre de la géométrie différentielle.

Définition 4. On définit la suite de Thue-Morse, (t_n)_n de la façon suivante :

t0 = 0, ∀n ≥ 0,t2n = tn, ∀n ≥ 0,t2n+1 = 1 - tn

On donne ses premiers termes ci-dessous : 0110100110…

On voit que, d’après la définition de t, t_n correspond à la somme des chiffres dans l’écriture en base 2 de n modulo 2. La suite de Thue-Morse est ainsi 2-automatique; elle est engendrée par l’automate suivant¹ :

PICT

Figure 1: L’automate de Thue-Morse.

Donnons une autre manière pour définir la suite de Thue-Morse. On considère le morphisme 2-uniforme² σ : {0, 1}^* →{0, 1}^* donné par :

σ(0) = 01 σ(1) = 10

La suite (σⁿ(0))_n converge simplement vers t. Il en résulte que t est point fixe de σ.

1.2 La suite de Rudin-Shapiro

La suite de Rudin-Shapiro, aussi appelée la suite de Golay-Rudin-Shapiro est une suite automatique nommée par Marcel Golay, Walter Rudin et Harold S.Shapiro, qui l’ont décourvert indépendemment.

Définition 5. On définit la suite de Rudin-Shapiro (r_n)_n de la façon suivante :

r0 = 0, ∀n ≥ 0,r = r , 2n n ∀n ≥ 0,r4n+1 = rn, ∀n ≥ 0,r4n+3 = 1 - r2n+1.

Ses premiers termes sont les suivants : 000100100001…

Il s’agit encore d’une suite 2-automatique. Elle est engendrée par l’automate suivant :

PICT

Figure 2: L’automate de Rudin-Shapiro.

Cette suite donne le nombre d’occurrences de "11" dans l’écriture de n en base 2, le tout modulo 2. On ne peut pas trouver comme pour la suite de Thue-Morse un morphisme 2-uniforme dont la suite soit point fixe. Il faut d’abord "agrandir" l’alphabet. Définissons un morphisme σ sur l’alphabet {A,B,C,D} par :

σ(A ) = AB σ(B ) = AC σ(C ) = DB σ(D ) = DC

La limite simple de σⁿ(A) est de la forme suivante :

ABACABDBABACDCAC ⋅⋅⋅

La suite de Rudin-Shapiro s’obtient alors en prenant l’image du point fixe pour σ par la projection π : {A,B,C,D}→{0, 1} définie par :

π (A ) = π(B ) = 0 π(C ) = π(D ) = 1

2 Théorème de Cobham

2.1 Le q-noyau

Au niveau des ressemblances entre les deux suites, il est pertinent d’introduire certaines définitions.

Définition 6. Soit u une suite donnée et k ∈ ℕ. le q-noyau que l’on notera désormais K_u^(q) (ou plus simplement K_u s’il n’y a pas d’ambiguïté) est :

(q) α Ku = {(u(q n + r))n | α ∈ ℕ, 0 ≤ r < α }

Le q-noyau nous intéresse lorsqu’il n’est pas "trop gros" et qu’il contraint les suites à coïncider avec leurs propres sous-suites extraites de pas q^k. Or il y a au plus un nombre dénombrable de telle suite, on s’intéresse alors au cas fini.

Lorsque le q-noyau est fini, il est facile de le calculer par machine. Il suffit de construire récursivement les ensembles X_k donnés par :

X0 = {(an)n≥0}etXk+1 = Xk ∪ {(bqn+r)n|(bn)n ∈ Xk, r ∈ [0,q - 1]}.

S’il existe k tel que X_k = X_k+1 alors c’est la valeur du q-noyau, ce dernier est alors fini.

Proposition 7. Le 2-noyau de la suite de Thue-Morse est fini.

Proof. On a

X1 = { (t2n)n,(t2n+1)n} = {(tn)n,(1 - tn)n}

Donc K_t = {(t_n)_n, (1 - t_n)_n} dont le 2-noyau est fini. __

Proposition 8. Le 2-noyau de la suite de Rudin-Shapiro est fini.

Proof. On a

X1 = {(rn)n, (r2n+1)n}

Puis

X2 = {(rn)n,(r2n+1)n,(r4n+3)n}

Ensuite

X3 = {(rn)n,(r2n+1 )n, (r4n+3)n,(r8n+3)n}

Enfin

X4 = {(rn)n,(r2n+1)n,(r4n+3 )n,(r8n+3)n} = X3

D’où le 2-noyau K_r = {(r_n)_n, (r_2n+1)_n, (r_4n+3)_n, (r_8n+3)_n} est fini. __

2.2 Théorème de Cobham

Donnons maintenant un lien avec les morphismes q-uniformes.

Définition 9. Une suite u à valeur dans un alphabet Σ est dite l’image d’un point fixe d’un point fixe d’un morphisme k-uniforme σ : Σ^′ → Σ^′ s’il existe w ∈ Σ^′ℕ point fixe de σ et π projection de Σ^′ dans Σ tels que ∀n ∈ ℕ,u_n = π(w_n).

En écrivant le fait d’être un point fixe lettre à lettre on obtient la caractérisation suivante qui sera souvent utile.

Lemme 10. Si σ est un morphisme q-uniforme d’un alphabet Σ dans lui même, alors w en est un point fixe si et seulement si :

∀n ∈ ℕ,∀r ≤ q,σ(w ) = w n r qn+r

Le lemme est facile à démontrer d’une façon très intuitive. Les deux suites t et r sont image de point fixe d’un morphisme 2-uniforme. On est à présent en mesure de donner une généralisation qui porte le nom de Cobham :

Proposition 11 (Cobham, 1972). Soient q ∈ ℕ^* et (u_n)_n une suite à valeurs dans {0, ⋅⋅⋅ ,q - 1}, alors les trois assertions suivantes sont équivalentes :

la suite (u_n)_n est q-automatique
le q-noyau K_u de u est fini
la suite (u_n)_n est image d’un point fixe d’un morphisme q-uniforme

Proof. i) ⇒ ii). On dispose d’un k-automate = {Q, Σ,δ,i,τ} qui engendre (u_n)_n. On rappelle que u_n = τ(δ(q₀,⟨n⟩_q)). Or pour i ≥ 0, 0 ≤ j < i, (qⁱn + j)_q = j0…0⟨n⟩_q = w⟨n⟩_q où l’on note w = j0^i-1. On a alors u_qⁱn+j = τ(δ(q₀,w⟨n⟩_q)) = τ(δ(δ(q₀,w),⟨n⟩_q)).

Comme il y a un nombre fini d’états, ainsi que δ(q₀,w) selon que i et j varient. Le q-noyau est alors bien fini.

ii) ⇒ iii). Le q-noyau étant fini supposé de cardinal d, on peut alors écrire K_u = {(u_n⁽¹⁾)_n, (u_n⁽²⁾)_n,…, (u_n^(d))_n} avec (u_n⁽¹⁾)_n = (u_n)_n. On définit une suite (V _n)_n sur l’alphabet Σ^d par ∀n ∈ ℕ, V _n = (u_n⁽¹⁾,u_n⁽²⁾,…,u_n^(d)). Pour j ∈ [0,q - 1], on dispose d’une application :

σ : Σd → Σd telleque ∀n ∈ ℕ,V = σ (V ) j qn+j j n

On considère le morphisme σ : (Σ^d)^* → (Σ^d)^* défini par :

∀V ∈ Σd, σ(V ) = σ0(V)σ1 (V )⋅⋅⋅ σq-1(V).

Il est aisé à voir que le morphisme h est q-uniforme, et par le lemme 10, la suite (V _n)_nest point fixe de σ. (u_n)_n est l’image de (V _n)_n par la projection sur la première coordonnée.

iii) ⇒ i). On pose (v_n)_n = σ^∞(v)³ , c’est-à-dire le point fixe de σ où σ est un morphisme q-uniforme sur l’alphabet Σ^′ et posons aussi une application f telle que ∀n,u_n = f(v_n).

Consiérons maintenant l’automate = {Σ^′, Σ,δ,v,f} où la fonction de transition δ est définie par : σ(x) = δ(x, 0)δ(x, 1) ⋅⋅⋅ δ(x,q - 1). On a alors ∀n ∈ ℕ,u_n = f(δ(v,⟨n⟩_q)). En effet, on montre par récurrence que :

∀k, σk(v) = δ(v,⟨0⟩ )δ(v,⟨1⟩ )⋅⋅⋅δ(v,⟨qk - 1⟩ ). q q q

L’initialisation est claire. Pour l’héritage, on a :

σk+1(v) = σ (δ(v,⟨0⟩q)δ(v, ⟨1 ⟩q) ⋅⋅⋅δ(v,⟨qk - 1 ⟩q)) = δ(δ(v,⟨0⟩q),0)⋅ ⋅⋅δ(δ (v, ⟨0 ⟩q),q - 1)⋅⋅ ⋅δ(δ (v, ⟨qk - 1⟩q),0)⋅⋅⋅δ (δ (v, ⟨qk - 1⟩q),q - 1) k+1 k+1 = δ(v, ⟨0 ⟩q) ⋅⋅⋅δ(v,⟨q - 1 ⟩q) ⋅⋅⋅δ(v,⟨q - q⟩q) ⋅⋅⋅δ(v,⟨q - q + (q - 1)⟩q).

Donc (u_n)_n est bien engendrée par le q-automate . __

3 Théorème de Christol

Nous présentons dans cette partie un résultat de Gilles Christol. Auparavant, les suites considérées sont q-automatiques, avec q = pⁿ et p premier. Le théorème donne une caractérisation surprenante du fait d’être automatique en terme d’algébricité (voir [1]) de série sur le corps F_q(X).⁴ Plus précisément, le théorème donne une équivalence entre l’algébricité d’une série formelle à coefficients dans un corps fini et la nature automatique de la suite des coefficients. On va, dans un premier temps, définir un opérateur qui porte le nom de Cartier.

3.1 Opérateur de Cartier

Notons F_q[[X]] l’ensemble des séries formelles à coefficients dans F_q. Soit u une suite à valeur dans F_q, on note :

∑∞ F (u) = Fu = unXn. n=0

Pour éclaircir l’idée, regardons les deux exemples suivantes:

Exemple 12. On se place dans F₂⁵ . En utilisant la définition de la suite de Thue-Morse t, il vient :

∑ n ∑ 2n ∑ 2n+1 Ft(X ) = n tnX = ∑ n t2nX +∑ nt2n+1X ∑ = n tnX2n + nX2n+1 + n tnX2n+1 = F (X2) + --X-2 + XF (X2 ) = (1 + X )F1(+XX2 ) + -X--. 1+X2

F est donc algébrique sur le corps F₂(X) des fractions rationnelles modulo 2. Elle est racine du polynôme P à coefficients dans F₂(X) :

P(Y ) = (1 + X )Y2 + Y + --X----. 1 + X2

Exemple 13. Par des calculs analogues, on obtient la relation suivante pour la suite de Rudin-Shapiro r :

5 2 4 3 (1 + X ) F (X ) + (1 + X ) F (X ) + X = 0.

Avant de continuer, il sera utile d’introduire une famille d’opérateurs sur les séries formelles qui portent le nom de l’opérateur de Cartier.

Définition 14 (Cartier). Soit r ∈{0, ⋅⋅⋅ ,q - 1}. On définit l’opérateur Λ_r :

∑ ∑ Λr : anXn ∈ Fq [[X ]] ↦→ aqn+rXn. n n

Le lemme suivant se vérifie facilement.

Lemme 15. Soit r ∈{0, ⋅⋅⋅ ,q - 1} et F,G ∈ F_q[[X]]. Alors :

q Λr(F G ) = Λr (F)G.

Précisons maintenant ce que veut dire être algégrique sur F_q(X) pour une série formelle F.

Lemme 16. Soit F = ∑ _na_nXⁿ une série formelle à coefficients dans F_q, alors F est algébrique si et seulement si on peut trouver des polynômes B₀(X),B₁(X), ⋅⋅⋅ ,B_k(X), non tous nuls tels que :

q qk B0F + B1F + ⋅⋅⋅ + BkF = 0

On peut supposer en outre que B₀≠0.

Proof. Si F est algébrique sur F_q(X), la famille (F^{q^k})_k≥0 est liée, d’où une relation de combinaison linéaire non triviale de la forme de l’énoncé. Réciproquement une telle liaison implique l’algébricité de F. Il reste à montrer que B₀ n’est pas nul.

Prenons k ∈ ℕ minimal tel que l’on ait une relation de liaison non triviale comme ci-dessus et montrons par l’absurde que B₀ = 0 :

q qk B1F + ⋅⋅⋅ + BkF = 0

Puis, en utilisant le lemme plus haut :

k k-1 Λr(B1F q + ⋅⋅⋅ + BkF q ) = Λr(B1)F + ⋅⋅⋅ + Λr (Bk)F q = 0

Ce qui contredit alors la minimalité de k. __

3.2 Théorème de Christol

Théorème 17 (Christol, 1979). ⁶ Soit p ≥ 2 un nombre premier et q une puissance de p. Une suite u à valeurs dans F_q est q-automatique si et seulement si la série formelle F(u) = ∑ _nu_nXⁿ est algébrique sur F_q(X).

Proof. (⇒). Soit u une suite q-automatique. On se servira de l’équivalence prouvée par Cobham : le q-noyau K_u est fini. Posons alors d = Card(K_u).

q∑-1 ∑ F (u ) = Xr uqn+rXnq r=0 n

Comme on a dans F_q, G(X^q) = G(X)^q où G est un polynôme

q-1 ∑ r∑ n q F (u) = X ( uqn+rX ) r=0 n

Ce qui montre que :

F(u ) ∈ V ectv∈K ⟨F (v)q⟩ u

On peut ainsi répéter le processus de la même manière :

k k+1 ∀k ≤ d : F (u )q ∈ V ectv∈Ku⟨F (v)q ⟩

Et donc par une récurrence simple, on obtient :

qk qd+1 ∀k ≤ d : F (u ) ∈ V ectv∈Ku⟨F (v) ⟩

Mais V ect_{v∈K_u}⟨F(v)^{q^d+1}⟩ est de dimension au plus d, la famille {F(u),F(u)^q, ⋅⋅⋅

,F(u)^{q^d}} est liée. F(u) = ∑ _nu_nXⁿ est donc algébrique sur F_q(X).

(⇐). Réciproquement, si la série formelle F(u) est algébrique sur F_q(X), d’après le lemme 16, on peut trouver des polyômes B_i avec B₀ non nul tels que :

∑k qi Bi (X )Fu(X ) = 0 i=0

Posons G_u = F_u∕B₀. Il vient G_u = ∑ _i=0^kC_iG_u^qⁱ où ∀i ∈{1,…,k},C_i = -B_iB₀^qⁱ-2. Posons ensuite N = max{deg(B₀),deg(C₁), ⋅⋅⋅

,deg(C_k)} et

l’ensemble défini par :

∑ i H = {H ∈ Fq[[X ]]|H = ki=0 DiGqu etDi ∈ Fq[X ],deg (Di ) ≤ N }.

est un ensemble fini contenant F_u. Pour montrer que K_u est fini, il suffit de montrer que ∀r < q, est stable par Λ_r. Soit alors H un élément de , on a :

∑k ∑k ∑k Λr (H ) = Λr (D0Gu + DiGqi ) = Λr ( (D0Gu + Di )Gqi) = Λ (D0Ci + Di)Gqi-1 u u u i=1 i=1 i=1

Comme pour tout i, on a deg(D₀C_i + D_i) ≤ deg(D₀C_i + D_i)∕q ≤ 2N∕q ≤ N, donc Λ_r(H) ∈

. __

4 Divers

Dans cette partie, nous donnons quelques autres résultats importants sur les suites automatiques. Cobham a démontré le résultat qui suit dont on trouvera une démonstration dans [2] :

Théorème 18. Soit k et l deux entiers multiplicativement indépendants⁷ et soit u une suite k et l-automatique, alors u est ultimement périodique.

Corollaire 19. Soit q₁ et q₂ multiplicativement indépendants et soit u une suite telle que F_u soit à la fois algébrique sur F_q1 et F_q2, alors u est ultimement périodique.

Proof. En vertu du théorème précédent et celui de Christol. __

En particulier, les suites de Thue-Morse et de Rudin-Shapiro ne sont pas 3-automatiques.⁸ Il est donc intéressant de comparer ce corollaire à la conjecture suivante.

Conjecture 20. Soit (u_n)_n ∈{0, 1}^ℕ telle que les deux nombres réels ∑ _n∈N unn-
2 et ∑ _n∈N unn
3 sont algébriques sur ℚ, alors ces deux nombres sont rationnels.

Par ailleurs, on montre que si deux suites u et v à valeurs dans {0,…,q - 1} sont q-automatiques, leur produit uv l’est aussi. En appliquant le théorème de Christol, on a :

Corollaire 21. Soient u et v à valeurs dans {0,…,q-1} telles que F_u et F_v sont algébriques sur F_q(X), alors le produit d’Hadamard⁹ de F_u et F_v est aussi algébrique que l’on note F_uv.

Le lien entre les automates et l’algébricité laisse entrevoir un champ de recherche en théorie des nombres et en algèbre.

References

[1] J-P.Allouche. Automates et algébricité. In Journal de Théorie des Nombres de BORDEAUX, volume 17, pages 1–11. Université Bordeaux 1, 2005.

[2] J-P.Allouche and J.Shallit. Automatic sequences, volume 1. Cambridge University Press, 2003.