24 jours après le Big Bang

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 H₁ = 22 jusqu'à l'uranium U₉₂ = 3, en passant par exemple par le carbone C₆ = 3113112211322112211213322112 (tous les éléments communs ne sont pas aussi simples que H₁ ou U₉₂). 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 Np₉₃ et Nu₉₄, 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 :

Le 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 Sm₆₂ = 311332 devient après un jour 13212312, qui se scinde sous la forme 132·12·312 = Pm₆₁·Ca₂₀.Zn₃₀. : Du coup, on peut réécrire la suite de graine 311332 sous la forme suivante :

Sm₆₂
Pm₆₁·Ca₂₀.Zn₃₀
Nd₆₀·K₁₉·Cu₂₉
Pr₅₉·Ar₁₈·Ni₂₈
Ce₅₈·Cl₁₇·Zn₃₀·Co₂₇
...

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 H₁ = 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 U₉₂, on aura après 91 génération l'élément H₁, 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é Hf₇₂·Sn₅₀ :

1
11
21
1211
111221
312211
13112221
11132·13211 = Hf₇₂·Sn₅₀
311312·11131221 = Lu₇₁·In₄₉
...

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 u_n le nombre de termes d'une suite LS, on a :

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

x⁷¹ - x⁶⁹ - 2x⁶⁸ - x⁶⁷ + 2x⁶⁶ + 2x⁶⁵ + x⁶⁴ - x⁶³ - x⁶² - x⁶¹ - x⁶⁰ - x⁵⁹ +
2x⁵⁸ + 5x⁵⁷ + 3x⁵⁶ - 2x⁵⁵ - 10x⁵⁴ - 3x⁵³ - 2x⁵² + 6x⁵¹ + 6x⁵⁰ + x⁴⁹ + 9x⁴⁸ - 3x⁴⁷ +
- 7x⁴⁶ - 8x⁴⁵ - 8x⁴⁴ + 10x⁴³ + 6x⁴² + 8x⁴¹ - 5x⁴⁰ - 12x³⁹ + 7x³⁸ - 7x³⁷ + 7x³⁶ + x³⁵ +
- 3x³⁴ + 10x³³ + x³² - 6x³¹ - 2x³⁰ - 10x²⁹ - 3x²⁸ + 2x²⁷ + 9x²⁶ - 3x²⁵ + 14x²⁴ - 8x²³ +
- 7x²¹ + 9x²⁰ + 3x¹⁹ - 4x¹⁸ - 10x¹⁷ - 7x¹⁶ + 12x¹⁵ + 7x¹⁴ + 2x¹³ - 12x¹² - 4x¹¹ +  
- 2x¹⁰ + 5x⁹ + x⁷ - 7x⁶ + 7x⁵ - 4x⁴ + 12x³ - 6x² + 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 à (F_n), la suite de Fibonacci (1, 1, 2, 3, 5, 8, ...), où le rapport des termes consécutifs converge vers le nombre d'or φ :

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

Dans une telle situation, on peut montrer (avec ce qu'il faut d'algèbre linéaire) que les rapports F_n+1/F_n 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

Comments

[Thomas Cabaret]

Bonjour,

Merci pour cet article sur ce beau théorème.

Quelques remarques/productions intéressantes:

-Toutes les assemblages d’éléments ne sont pas valides:

Parfois de manière triviale Ca.H ne va clairement pas évoluer comme on aimerait.

Parfois de manière moins triviale voir par exemple le cas U.Ca



Je me suis demandé du coup quelle était la règle, il se trouve qu'a priori elle s’énonce de manière concise (je ne saisi pas vraiment pourquoi c'est aussi concis, ça semble être une règle naïve au premier abord mais c'est a priori juste.)

-Tous les éléments qui terminent par 2 ET SEULEMENT EUX se branchent en préfixe de tous les éléments sauf de H.

-Les autres ET SEULEMENT EUX se branche en préfixe de H.



Un autre point intéressant est l’évolution des préfixe et des suffixe d'une chaine:

http://postimg.org/image/6y2dburoj/ << préfixe

http://postimg.org/image/jbeqze0fh/ << suffixe

Par exemple si on fait évoluer itérativement une chaine finissant par Ge elle finira par avoir comme suffixe He - Li en boucle (une itération sur deux). (voir 2eme image)



(Résultats et remarques ci dessus sous réserve d'aucune erreur de ma part dans le recopiage du graphe de transition des éléments www.se16.info/js/lands2.htm, ni dans les raisonnements et les quelques lignes de code nécessaires. :P)

[Groug]

John Dalbec a réussi à gagner l'IOCCC (International Obfuscated C Code Contest, c'est-à-dire concours international du programme en C le plus incompréhensible possible...) en 2004, catégorie "Best abuse of the periodic table", avec un programme qui implémente cette suite "look and say" et donne les décompositions en éléments. Le programme, absolument illisible bien entendu, est disponible sur http://www.ioccc.org/2004/jdalbec.c avec un commentaire (je n'ose pas dire un mode d'emploi) sur http://www.ioccc.org/2004/jdalbec.hint