Devinette ! Complétez la suite logique suivante :

3
13
1113
3113
132113
...

Ok, tout le monde la connaît, celle-là. Le terme qui suit, c'est 1113122113, car il s'agit de la suite "look and say" (abrégée LS) inventée en 1987 par Conway : chaque terme de la suite s'obtient en lisant les chiffres du terme précédent. Ainsi, la ligne 3113 peut se lire "un '3' puis deux '1' puis un '3'", ce qui donne 132113.

On pourrait s'arrêter au simple constat "ok, elle est marrante ta suite logique, mais t'es gentil, je regarde le match, là". Mais je me dois d'en dire plus, puisque cette suite possède de nombreuses propriétés. La plus merveilleuse d'entre elle a été intitulée "théorème cosmologique" et, résumé par son auteur, nous apprend que "24 jours après le Big Bang, l'ensemble des éléments exotiques ont disparu" ! Il faut dire que derrière cette suite se cache John Conway, qui baptise toujours ses découvertes par des noms improbables, comme le jeu de la vie, les nombres surréels ou le jeu "Sprouts"...
J'avais déjà écrit un article sur ce sujet en 2007, il est temps de le réactualiser.

Évidemment, on peut changer de terme initial pour former d'autres suites LS, comme

3333
43
1413
11141113
...

Il y a également le cas particulier de la suite 22, qui donne :

22
22
22
22
...

Théorème du jour 1 & théorème du jour 2
Avant que vous me trouviez des contre-exemples, mettons nous d'accord sur une chose : le chiffre 0 n'existe pas, tout comme les nombres supérieurs à 9. Si jamais ils venaient à exister, on les écrira quand même avec un seul chiffre. Par exemple, la chaîne qui suivra 1111111111 n'est pas 101 mais ⁂1 (où ⁂ est le chiffre que je viens d'inventer pour désigner le nombre 10) :

1111111111
⁂1
1⁂11
111⁂21
311⁂1211
...

Quelques définitions : on appellera "graine" la chaîne initiale d'une suite LS. Tous les termes qui suivent sont ses descendants : on dira que le premier est âgé de 1 jour, le suivant de 2 jours, etc.
La graine d'une suite LS peut être aussi compliquée que l'on veut, le terme suivant répondra quand même à quelques propriétés.

Du coup, on peut énoncer le théorème du jour 1 : une chaîne âgée de 1 jour...

  • ne peut pas débuter par yxzx (où x, y et z désignent trois chiffres différents - ou pas), ni contenir une telle chaîne dans une position paire.
  • ne peut pas contenir le même chiffre répété 4 fois ou plus (conséquence de la propriété précédente)
  • ne peut pas contenir la chaîne xxxyyy

En conséquence du théorème du jour 1, on a le théorème du jour 2 : une chaîne âgée de 2 jours...

  • ne peut pas faire naître un nouveau 4 (ou tout autre chiffre supérieur)
  • ne peut pas contenir la chaîne 3x3

Il n'est fait aucune mention d'un théorème du jour 3, mais je reviendrai plus tard sur celui du jour 24.

Théorème de séparation
Le point central de la théorie des suites LS est l'idée qu'elles puissent se scinder, dans le sens où il arrive qu'à partir d'une certain étape, la partie gauche de la chaîne n'interfère plus avec la partie droite. Prenons par exemple la suite débutant par 42 :

4·2
14·12
1114·1112
3114·3112
...

D'après le théorème du jour 2, aucun nouveau '4' ne peut apparaître, en particulier à droite du chiffre '4' déjà présent. De ce fait, il ne peut y avoir que un seul '4' à une étape donnée, ce qui le transformera inexorablement en '14' à l'étape suivante, n'interférant pas sur les chiffres qui suivent. On notera par "·" cette scission. 

Il existe dix cas (et pas plus) dans lesquels une chaîne se scinde (c'est le théorème de séparation). Par exemple, une chaîne contenant ...XY... (avec X≥4 et Y≤3) se scindera sous la forme ...X·Y..., ce qui est le cas dans l'exemple précédent . De la même façon, une chaîne contenant ...2111... se scindera en ...2·111... (voir [1] si vous voulez la liste en détail).

Évidemment, les sous-chaînes obtenues peuvent elles aussi se scinder, donnant au fil des étapes de nombreuses sous-chaînes indépendantes.

Il existe alors des sous-chaînes qui ne peuvent pas se scinder : on les appelle les "éléments" (ou "atomes"). Parmi ces éléments, certains finissent inexorablement par apparaître, quelle que soit la graine de la suite (sauf si c'est 22). Ces éléments particuliers (les "éléments communs") sont au nombre de 92, si bien que Conway les a nommé à partir des 92 éléments chimiques existant naturellement, allant de l'hydrogène H1 = 22 jusqu'à l'uranium U92 = 3, en passant par exemple par le carbone C6 = 3113112211322112211213322112 (tous les éléments communs ne sont pas aussi simples que H1 ou U92). Puisque ces éléments ont la fâcheuse tendance à se désintégrer les uns en les autres, Conway les a baptisé "éléments audioactifs".

On ajoute à cette liste les deux éléments transuraniens Np93 et Nu94, les deux seuls éléments comprenant un chiffre supérieur à 3. De ce fait, ces deux éléments existent sous une infinité de versions (leurs "isotopes"), autant que de chiffre supérieur à 4 possibles.

Enfin, il existe une infinité d'éléments 'exotiques', comme 1, 2 ou 4443333444, qui ne peuvent pas apparaître en tant qu'atome après plusieurs étapes.

Du coup, on peut ranger ces 94 éléments communs et transuraniens dans leur tableau périodique :

 

Tableau périodiqeLe tableau périodique des 94 éléments audioactifs de Conway (clic doit / ouvrir dans un nouvel onglet, pour voir en encore plus grand !)

A titre d'exemple, l'élément Sm62 = 311332 devient après un jour 13212312, qui se scinde sous la forme 132·12·312 = Pm61·Ca20.Zn30. : Du coup, on peut réécrire la suite de graine 311332 sous la forme suivante :

Sm62
Pm61·Ca20.Zn30
Nd60·K19·Cu29
Pr59·Ar18·Ni28
Ce58·Cl17·Zn30·Co27
...

Ainsi, si la graine de la suite est un élément commun ou transuranien, tous ses descendants seront uniquement composés d'éléments communs et transuraniens. D'ailleurs, si la graine est composée d'éléments communs et/ou transuraniens (et n'est pas H1 = 22), il arrivera tôt ou tard un descendant composé d'au moins une fois les 92 éléments (plus éventuellement des éléments transuraniens) !

L'ordre des éléments a été choisi de façon à ce qu'un élément n soit le descendant direct de l'élément n+1 . Ainsi, en partant d'une graine U92, on aura après 91 génération l'élément H1, au milieu de beaucoup d'autres. Il en fait 6 autres façons de ranger les 92 éléments en suivant cette règle, le tableau ci-dessus correspond à la liste originale dressée par Conway (voir [2] pour les détails).

Le théorème cosmologique
On arrive au théorème le plus important de la théorie des suites LS, le théorème cosmologique :

Quelle que soit la graine choisie, il arrivera une étape où les descendants seront composés uniquement d'éléments communs et transuraniques. Ceci arrivera en au plus 24 étapes !

Ce théorème prouve en particulier qu'un élément exotique ne pourra pas le rester éternellement. Par exemple, si on choisit la graine 1 (élément exotique), on fini par tomber (après 7 étapes) sur le composé Hf72·Sn50 :

1
11
21
1211
111221
312211
13112221
11132·13211 = Hf72·Sn50
311312·11131221 = Lu71·In49
...

La borne des 24 étapes est optimale, puisqu'il existe un élément exotique demandant les 24 jours pour se scinder en élément commun. Cet élément est 22333222114, découvert et baptisé Mathusalum par Mike Guy, collègue de Conway.

La démonstration de ce théorème est particulièrement difficile, si bien que Conway nous a fait le coup de la démonstration perdue. Du coup, la preuve complète la plus récente du théorème cosmologique date seulement de 2003, et, à l'image du théorème des quatre couleurs, comporte une grande partie de calcul informatique.

La constante de Conway
Entre deux termes consécutifs d'une suite LS (quelle que soit sa graine), le nombre de chiffres est en moyenne multiplié par λ = 1.303678... Autrement dit, en notant un le nombre de termes d'une suite LS, on a :

limite_suite_LS

Ce nombre n'est autre que l'unique solution réelle de l'équation

x71 - x69 - 2x68 - x67 + 2x66 + 2x65 + x64 - x63 - x62 - x61 - x60 - x59 +
2x58 + 5x57 + 3x56 - 2x55 - 10x54 - 3x53 - 2x52 + 6x51 + 6x50 + x49 + 9x48 - 3x47 +
- 7x46 - 8x45 - 8x44 + 10x43 + 6x42 + 8x41 - 5x40 - 12x39 + 7x38 - 7x37 + 7x36 + x35 +
- 3x34 + 10x33 + x32 - 6x31 - 2x30 - 10x29 - 3x28 + 2x27 + 9x26 - 3x25 + 14x24 - 8x23 +
- 7x21 + 9x20 + 3x19 - 4x18 - 10x17 - 7x16 + 12x15 + 7x14 + 2x13 - 12x12 - 4x11 +  
- 2x10 + 5x9 + x7 - 7x6 + 7x5 - 4x4 + 12x3 - 6x2 + 3x - 6 = 0

Il s'agit donc de la racine d'un polynôme de degré 71 ! (D'autant que le polynôme est irréductible, ce qui fait de λ l'un des nombres algébriques ayant le plus haut degré de toute la littérature mathématique)

Pour comprendre d'où sort ce polynôme, regardons plutôt la suite suivante, où chaque terme est obtenu à partir du précédent en transformant a en ab, et en transformant b en a :

b
a
ab
aba
abaab
abaababa
...

On peut remarquer que le nombre de caractères des termes de cette suite correspondent à (Fn), la suite de Fibonacci (1, 1, 2, 3, 5, 8, ...), où le rapport des termes consécutifs converge vers le nombre d'or φ :

limite_suite_Fibo

Une façon de démontrer ceci est de remarquer que le nombre an et bn de a et de b à la n-ième ligne de la suite vérifie :

matrice_Fibo

Dans une telle situation, on peut montrer (avec ce qu'il faut d'algèbre linéaire) que les rapports Fn+1/Fn convergent vers la plus grande valeur propre (en module) de la matrice (et indépendamment du terme initial), qui n'est autre φ. Autrement dit, ce rapport converge vers la plus grande racine du polynôme caractéristique de la matrice, qui est X² - X - 1.

Pour les suites LS, l'idée est la même, sauf que la matrice est un tantinet plus compliquée, puisqu'elle est de taille 92×92 ; mais sa plus grande valeur propre est effectivement λ. Voir [3] pour davantage de détails sur le calcul de la matrice et de son polynôme caractéristique.

 

Bref, la prochaine fois qu'un petit malin vous met au défi de compléter la suite de Conway, n'hésitez pas à lui dire que derrière cette bête devinette se cache un bestiaire chimico-mathématique étonnant et une complexité hallucinante !


Sources 
[1] Oscar Martin, Look-and-Say Biochemistry: Exponential RNA and Multistranded DNA, dont l'introduction est très complète
[2] Henry Bottomley, Seven complete sequences for the Conway Look and Say elements
[3] Nathaniel Johnston, A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial
[4] John Conway, Weird and wonderful chemistry of audioactive decay