Les problèmes importants auxquels nous faisons face ne peuvent être résolus au même niveau de pensée que celui qui les a engendrés.
Albert Einstein[1]
Avec l'hypothèse de Riemann et la conjecture de Goldbach, un des problèmes ouverts les plus célèbres en mathématiques est la conjecture de Syracuse, due à Lothar Collatz au début du XXe siècle.
Soit n un nombre entier. On lui applique l'opération suivante : s'il est pair, on le divise par deux, s'il est impair on le multiplie par trois et on lui ajoute un. On réitère successivement ce traitement sur le résultat, générant ainsi la n-ième suite de Syracuse. La 7-ième suite de Syracuse est ainsi 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...
La conjecture de Syracuse fait état que chaque suite de Syracuse aboutira tôt ou tard au cycle 4, 2, 1. Mais elle a résisté jusqu'à présent à toute démonstration. Le mathématicien hongrois Paul Erdős a dit à propos de cette hypothèse : « les mathématiques ne sont pas encore prêtes pour de tels problèmes ».
Une autre famille de suites dont les termes peuvent monter très haut avant de redescendre a été inventée par le mathématicien britannique Reuven Goodstein en 1944.
Tout entier n possède une unique décomposition en base b : \(n = \Sigma k_i · b^i\), où \(b\) est la base et les \(k_i\) sont les chiffres ; ainsi en base 2 : \(266 = 2^8 + 2^3 + 2^1\). La n-ième suite faible de Goodstein est définie de la façon suivante : à partir de la représentation binaire de n, qui constitue le premier terme, le second terme est obtenu en incrémentant la base de 1 et en retranchant 1 au résultat. Les termes suivants sont construits de façon analogue, en réécrivant au besoin le terme dans la base en cours (cf \(n_4\) ci-dessous) qui est par la suite incrémentée avant de soustraire 1 du résultat s'il est non nul. Les premiers termes de la 266-ième suite faible de Goodstein sont donc :
\(n_0 = 2^8 + 2^3 + 2^1 = 266\)
\(n_1 = 3^8 + 3^3 + 2 = 6 590\)
\(n_2 = 4^8 + 4^3 + 1 = 65 601\)
\(n_3 = 5^8 + 5^3 = 390 750\)
\(n_4 = 6^8 + 6^3 − 1 = 6^8 + 5 · 6^2 + 5 · 6^1 + 5 = 1 679 831\)
\(n_5 = 7^8 + 5 · 7^2 + 5 · 7^1 + 4 = 5 765 085\)
Bien que les premiers termes croissent rapidement, cette suite est à support fini, c'est-à-dire qu'il existe un rang à partir duquel tous les termes deviennent nuls, et c'est en fait le cas pour toutes les suites faibles de Goodstein. C'est le fait de retrancher 1 à chaque étape qui finit par l'emporter sur l'incrémentation de la base.
Contrairement à la conjecture de Collatz, la convergence des suites faibles de Goodstein est simple à démontrer. Intuitivement, à chaque terme d'une suite peut être associé un polynôme de \(\mathbb{N}[X]\) dont les coefficients sont les chiffres de la représentation du terme. Ainsi pour la 266-ème suite de Goodstein, la suite de polynômes est :
\(P_0 = X^8 + X^3 + X^1\)
\(P_1 = X^8 + X^3 + 2\)
\(P_2 = X^8 + X^3 + 1\)
\(P_3 = X^8 + X^3\)
\(P_4 = X^8 + 5 · X^2 + 5 · X^1 + 5\)
\(P_5 = X^8 + 5 · X^2 + 5 · X^1 + 4\)
Cette correspondance, où pour chaque terme la base d'écriture est remplacée par une indéterminée, met en lumière une suite de polynômes qui décroît au sens lexicographique dans \(\mathbb{N}_8[X]\), un ensemble bien ordonné, donc converge, la seule limite possible respectant ce processus étant le polynôme nul.
La représentation complète d'un nombre n en base b est un peu plus complexe : comme précédemment, n est écrit comme somme de puissances de b, mais la même opération est effectuée avec les exposants, avec les exposants des exposants, et ainsi de suite jusqu'à obtenir une écriture stable.
Ainsi \(266 = 2^8 + 2^3 + 2^1 = 2^{2^{2+1}} + 2^{2+1} + 2^1\).
On peut à présent définir les suites de Goodstein.
Soit n un entier naturel. La n-ième suite de Goodstein est construite de la façon suivante :
\(n_0\) est la représentation complète de \(n\) en base 2
\(n_1\) est obtenu à partir de \(n_0\) en remplaçant tous les 2 par des 3, et en retranchant 1
\(n_2\) est obtenu à partir de \(n_1\) en remplaçant tous les 3 par des 4, et en retranchant 1
Soit, pour n = 266 :
\(n_0 = 2^{2^{2+1}} + 2^{2+1} + 2^1 = 266 \)
\(n_1 = 3^{3^{3+1}} + 3^{3+1} + 3^1 − 1 = 3^{3^{3+1}} + 3^{3+1} + 2 = 443 426 488 243 037 769 948 249 630 619 149 892 886 \approx 10^{38} \)
\(n_2 = 4^{4^{4+1}} + 4^{4+1} + 1 \approx 10^{616}\)
\(n_3 = 5^{5^{5+1}} + 5^{5+1} \approx 10^{10921}\)
\(n_4 = 6^{6^{6+1}} + 6^{6+1} − 1 = 6^{6^{6+1}} + 5 · 6^6 + 5 · 6^5 + 5 · 6^4 + 5 · 6^3 + 5 · 6^2 + 5 · 6^1 + 5 \approx 10^{217 832}\)
\(n_5 = 7^{7^{7+1}} + 7^{7+1} − 1 = 7^{7^{7+1}} + 5 · 7^7 + 5 · 7^5 + 5 · 7^4 + 5 · 7^3 + 5 · 7^2 + 5 · 7^1 + 4 \approx 10^{4 871 822}\)
Théorème (Goodstein) : les suites de Goodstein sont à support fini.
De même que les suites faibles de Goodstein, les suites de Goodstein finissent par s'annuler. Mais le processus est long : la 4-ième suite de Goodstein s'annule après la \(3·2^{402 653 211}-3\)-ème étape (un nombre à plus de 121 millions de chiffres).
L'idée de démonstration est similaire à celle des suites faibles, mais au lieu de polynômes, une correspondance pourra être établie avec une suite d'ordinaux, la base étant substituée par \(\omega\) (le premier ordinal limite).
Pour n = 266 :
\(\beta_0 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} + \omega^1 \)
\(\beta_1 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} + 2 \)
\(\beta_2 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} + 1 \)
\(\beta_3 = \omega^{\omega^{\omega+1}} + \omega^{\omega+1} \)
\(\beta_4 = \omega^{\omega^{\omega+1}} + 5 · \omega^\omega + 5 · \omega^5 + 5 · \omega^4 + 5 · \omega^3 + 5 · \omega^2 + 5 · \omega^1 + 5 \)
\(\beta_5 = \omega^{\omega^{\omega+1}} + 5 · \omega^\omega + 5 · \omega^5 + 5 · \omega^4 + 5 · \omega^3 + 5 · \omega^2 + 5 · \omega^1 + 4 \)
Cette suite d'ordinaux est strictement décroissante et donc converge vers le seul élément possible : l'ordinal nul, et il en est de même pour les suites de Goodstein.
À la différence de la convergence des suites faibles de Goodstein, le théorème de Goodstein ne peut être prouvé dans le cadre de l'arithmétique du premier ordre (ou arithmétique de Peano) ; cela a été démontré en 1982 par Kirby et Paris. Toute preuve nécessite de sortir du cadre de l'arithmétique, comme le fait celle basée sur les ordinaux (il apparait ainsi que les ordinaux, grâce à leur bon ordre structurel, peuvent servir à établir la terminaison d'un processus). Le théorème de Goodstein est donc un exemple de proposition de l'arithmétique de Peano vraie mais improuvable en son sein, et constitue une illustration d'énoncé arithmétique indécidable tel que prédit par le premier théorème d'incomplétude de Gödel.
Sources et références (en anglais) :
Reuven L. Goodstein, On the restricted ordinal theorem (1944) - article séminal
Laurie Kirby, Jeff Paris, Accessible Independence Results for Peano Arithmetic (1982) - démonstration de la non-prouvabilité du théorème de Goodstein au sein de l'arithmétique de Peano et introduction du jeu de l'hydre
Bernard G. Hodgson, Herculean or Sisyphean tasks? - article de vulgarisation soulignant que l'annulation des suites de Goodstein est une tâche herculéenne et non sisyphéenne
Michèle Artigue, Ferdinando Arzarello, Susanna Epp, Goodstein Sequences: The Power of a Detour via Infinity - article de vulgarisation
13 derniers coms