Il y a près d’un siècle, un mathématicien a imaginé un puzzle si simple en apparence et pourtant si diaboliquement difficile qu’il a depuis distrait d’autres mathématiciens. C’est devenu un mème qui passe d’un cerveau à l’autre, et de nombreuses personnes prétendent l’avoir résolu, pour ensuite voir leurs espoirs anéantis à mesure que les preuves se dévoilent. Et soyez prévenu : une fois que j’aurai expliqué les règles, vous aurez immédiatement envie de commencer à jouer avec vous-même, et je n’assume aucune responsabilité quant au temps que vous perdez.

Cela commence un peu comme un tour de magie. Choisissez un nombre, n’importe quel nombre – enfin, au moins n’importe quel nombre entier positif ; n’essayez pas d’être intelligent avec quelque chose comme pi. S’il s’agit d’un nombre pair, divisez-le par 2. S’il s’agit d’un nombre impair, multipliez-le par 3 et ajoutez 1. Appliquez ensuite les mêmes règles au nombre obtenu. Faites cela assez longtemps et vous finirez toujours à 1.

Ou du moins, les mathématiciens pensent que oui. Que cela soit vrai pour chaque nombre entier positif possible est une question ouverte appelée conjecture de Collatz, du nom de Lothar Collatz, qui a étudié la question pour la première fois dans les années 1930. Et, étonnamment, c’est une question très difficile à répondre. En effet, Paul Erdős, l’un des mathématiciens les plus prolifiques du 20e sièclea dit un jour que « les mathématiques ne sont peut-être pas prêtes à affronter de tels problèmes ».

Alors pourquoi la conjecture de Collatz est-elle si difficile à prouver ? Si vous êtes comme moi, lorsque vous entendez parler du problème pour la première fois, vous prenez immédiatement votre calculatrice et commencez à calculer des nombres pour voir si vous obtenez 1. En effet, les mathématiciens ont utilisé des ordinateurs pour vérifie chaque numéro jusqu’à 2⁷¹. Malheureusement, cela laisse une infinité de nombres à vérifier, donc cela ne nous aide pas vraiment dans la quête d’une preuve.

L’un des problèmes est que les chiffres ne se comportent pas de manière ordonnée. Si nous commençons par 1, nous avons terminé. Pour 2, on le divise par deux et c’est fini. Mais pour 3, la chaîne de nombres devient : 10, 5, 16, 8, 4, 2, 1. Pour 7, elle devient : 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Vous remarquerez peut-être que la chaîne pour 7 contient la chaîne pour 3, et c’est un aspect intéressant de Collatz : une fois que vous arrivez sur un numéro qui a déjà été vérifié, vous n’avez pas besoin de le vérifier à nouveau, car vous savez déjà où aboutit la chaîne.

Tout cela fait du problème une herbe à chat pour les mathématiciens. Je me souviens d’une citation de l’excellent bande dessinée xkcd: « Il existe un certain type de cerveau qui est facilement désactivé. Si vous lui montrez un problème intéressant, il abandonne involontairement tout le reste pour y travailler. » Et en effet, à mesure que le mème Collatz s’est répandu, c’est exactement ce qui s’est produit.

Définir l’inconnu

Cerner l’origine de la conjecture de Collatz est étonnamment difficile, mais pas aussi difficile que de trouver une preuve. Dans une lettre de 1980, Collatz a écrit qu’il avait commencé à enquêter « il y a presque 50 ans ». Il semble qu’il ait gardé cette conjecture pour lui pendant de nombreuses années, la considérant sans doute comme rien de plus qu’une vaine curiosité. Cela n’a commencé à se répandre plus largement qu’en 1950, lorsque Collatz s’est rendu au Congrès international des mathématiciens – la plus grande réunion dans le domaine – et a discuté de manière informelle du problème avec d’autres participants.

De là, il s’est répandu à travers les réseaux mathématiques et semble même avoir été redécouvert et rebaptisé par d’autres mathématiciens, sous de nombreux noms, comme le problème de Syracuse, l’algorithme de Hasse ou même simplement le problème 3x+1. Selon Jeffrey Lagariasqui a étudié de manière approfondie la conjecture, elle n’a été publiée qu’en 1971, lorsqu’elle a été décrite comme « un potin mathématique », mais elle a vraiment fait son apparition dans la cour des grands un an plus tard, lorsque Martin Gardner en a parlé dans son ouvrage. Colonne Jeux mathématiques pour Américain scientifique. Si vous ne l’avez jamais rencontré auparavant, Gardner est une figure légendaire dans le domaine des « mathématiques récréatives » – essentiellement des choses que les mathématiciens de recherche sérieux méprisent légèrement, tout en les appréciant secrètement avec d’autres fans de mathématiques.

La conjecture de Collatz a continué pendant un certain temps encore à chevaucher la frontière entre les mathématiques récréatives et les mathématiques de recherche. J’ai été amusé de trouver un article de 1983 intitulé «N’essayez pas de résoudre ces problèmes», qui énumère la conjecture, parmi d’autres, mettant en garde les mathématiciens tout en sachant qu’ils succomberont inévitablement à la tentation.

L’un des premiers grands résultats est survenu en 1976, lorsque Terrasses Riho s’est avéré un résultat important. Vous remarquerez que si vous commencez avec un nombre pair, votre chaîne Collatz descend toujours en dessous de ce nombre de départ car votre première étape consiste à la réduire de moitié. Cependant, si vous commencez avec un nombre impair, votre premier arrêt dépasse votre numéro de départ – la question devient donc : combien de temps faudra-t-il pour redescendre en dessous de votre point de départ, avec un peu de chance sur la voie de 1 ? Terras a appelé cela le « temps d’arrêt » d’un nombre et a prouvé que dans presque tous les cas, le temps d’arrêt est fini – ce qui signifie que les nombres finissent par diminuer, plutôt que d’exploser pour toujours.

Cela ne suffit pas à prouver la conjecture de Collatz, car un seul contre-exemple d’un nombre incroyablement grand qui n’atteint jamais 1 suffirait à la réfuter. Il est également d’une imprécision insatisfaisante : que signifie « presque tout » lorsqu’il s’agit de possibilités infinies ? Plus de précision viendrait en 2002, lorsque Ilia Krasikov et Lagarias prouvé que pour un nombre x donné, au moins x^0,84 les nombres en dessous finiront par atteindre 1. C’est un peu déroutant – par exemple, si nous prenons x comme 100, cela signifie qu’au moins 47 nombres en dessous de 100 atteindront 1. En fait, nous savons que chaque nombre en dessous de 100 atteint 1, mais ce que fait la preuve est de placer un plafond explicite sur les inconnues de Collatz.

La plus grande avancée a eu lieu en 2019, lorsque Terrence Tao, sans doute le plus grand mathématicien vivant au monde, a décidé de s’attaquer à ce problème notoire. Il s’est avéré une version beaucoup plus forte du résultat de Terrasmontrant que non seulement « presque tous » les nombres finissent par descendre en dessous de leur point de départ, mais que, effectivement, vous pouvez les réduire aussi bas que vous le souhaitez. Cela semble assez proche d’une preuve de la conjecture de Collatz – sauf que, dans un sens, ce n’est pas plus proche, car il y a toujours la possibilité d’un contre-exemple caché aux confins de la droite numérique.

Alors, quelle est la prochaine étape pour la conjecture de Collatz ? Alors que j’écrivais cet article, la nouvelle est tombée qu’OpenAI avait utilisé un grand modèle de langage pour résoudre un problème majeur qui déconcertait les mathématiciens depuis 80 ans. Il l’a fait non pas en prouvant son exactitude, mais en trouver un contre-exemple inattendu. La même chose pourrait-elle arriver pour Collatz ? Je n’oserais pas le prédire à ce stade, mais il serait certainement ironique qu’un problème qui a infecté tant d’esprits humains finisse par être résolu par une IA.