Les mathématiciens ont réalisé une percée dans l'étude du problème «dangereux»

Les mathématiciens considèrent l'hypothèse de Collatz comme un «marais» et se préviennent mutuellement qu'il vaut la peine de s'en éloigner. Maintenant, cependant, Terence Tao a fait plus de progrès que quiconque depuis des décennies.

Prenez n'importe quel nombre. S'il est pair, divisez-le en deux. S'il est impair, multipliez par trois, ajoutez-en un. Répétez. Est-ce qu'un nombre finit par atteindre 1?

Les mathématiciens expérimentés conseillent aux débutants de rester loin de l'hypothèse de Collatz . Ils appellent cela une chanson de sirène: tombez sous son influence et vous ne pourrez jamais accéder à un travail significatif.

L'hypothèse de Collatz, peut-être le plus simple des problèmes non résolus des mathématiques, est précisément ce qui la rend si dangereusement attrayante.

«C'est une tâche très dangereuse. Les gens deviennent obsédés par cela, même si c'est complètement impossible », a déclaré Jeffrey Lagarias , mathématicien à l'Université du Michigan, expert de l'hypothèse Collatz.

Mais en 2019, l'un des meilleurs mathématiciens du monde a osé l'approcher et a reçu le plus important de tous les résultats obtenus en plusieurs décennies.

Le 8 septembre 2019, Terence Tao a publié une preuve montrant que l'hypothèse de Collatz est au moins «presque» vraie «presque» pour tous les nombres. Bien que le résultat de Tao ne soit pas une preuve complète de l'hypothèse, il s'agit d'une percée très sérieuse pour une tâche qui n'est pas si facile de révéler tous ses secrets.

"Je ne m'attendais pas à résoudre complètement le problème", a déclaré Tao, mathématicien à l'Université de Californie à Los Angeles. "Mais j'ai réussi à faire plus que ce à quoi je m'attendais."

Collatz Puzzle

Lothar Collatz a probablement avancé une hypothèse du même nom dans les années 1930. Le défi ressemble à un tour de fête. Prenez n'importe quel nombre. S'il est pair, divisez-le en deux. S'il est impair, multipliez par trois, ajoutez-en un. Obtenez un nouveau numéro. Appliquez-lui les mêmes règles. L'hypothèse dit ce qui se passera si vous répétez constamment ce processus.

L'intuition suggère que le nombre de départ affecte le résultat final. Peut-être que certains nombres finiront par tomber à 1. Peut-être que d'autres nombres augmenteront indéfiniment.

Cependant, Collatz a prédit que ce n'était pas le cas. Il a suggéré que si vous commencez avec un entier positif et répétez la séquence pendant une longue période, à partir de n'importe quel nombre initial, vous arriverez à 1. Et étant parvenus à l'unité, les règles d'hypothèse vous rattraperont dans une boucle sans fin: 1, 4, 2, 1, 4, 2, 1, etc., à l'infini.

Au fil des ans, de nombreux amateurs de tâches ont été attirés par la simplicité attrayante de l'hypothèse de Collatz, ou «problème 3x + 1», comme on l'appelle également. Les mathématiciens ont déjà vérifié un quintillion d'exemples (c'est un nombre avec 18 zéros), ne trouvant pas une seule exception à la prédiction de Collatz. Vous pouvez vous-même essayer de vérifier quelques exemples avec l'un des nombreux « calculateurs Collatz » disponibles sur Internet. L'Internet regorge de preuves amateurs injustifiées d'une hypothèse, dont les auteurs affirment avoir pu la prouver ou la réfuter.



«Il suffit de pouvoir multiplier par 3 et diviser par 2, et vous pouvez déjà commencer à jouer avec. Et c'est très tentant », a déclaré Mark Chamberlain , mathématicien au Grinnel College, qui a enregistré une vidéo populaire sur ce problème intitulée« Le plus simple des problèmes impossibles ».


Mais il y a peu de preuves réelles.

Dans les années 1970, les mathématiciens ont montré que presque toutes les séquences de Collatz - une liste de nombres que vous obtenez lorsque vous répétez le processus - finissent par atteindre un nombre inférieur à celui initial. C'était une preuve faible que presque toutes les séquences de Collatz conduisaient à 1, mais néanmoins, c'était le cas. Et de 1994 au résultat Tao en 2019, Ivan Korets a conservé le record de démonstration de la valeur minimale. D'autres travaux ont également tenté d'attaquer la tâche, n'atteignant pas son objectif principal.

"Nous ne comprenons pas vraiment assez bien la question de Collatz, donc il n'y a pas eu de travail important sur cette question", a déclaré Kannan Saundararajan , mathématicien à l'Université de Stanford qui a travaillé sur cette hypothèse.

La futilité de ces tentatives a conduit de nombreux mathématiciens à conclure que cette hypothèse n'était tout simplement pas disponible au niveau actuel des connaissances et qu'il valait mieux pour eux consacrer leur temps à d'autres études.

"Le problème de Collatz est connu pour sa complexité - à tel point que les mathématiciens précèdent généralement chaque discussion avec un avertissement de ne pas y perdre de temps", a déclaré Joshua Cooper de l'Université de Caroline du Sud.

Des conseils inattendus

Pour la première fois, Lagarias s'est intéressé à cette hypothèse en tant qu'étudiant il y a au moins 40 ans. Pendant des décennies, il a été conservateur officieux de tout ce qui se rapportait à elle. Il a rassemblé toute une bibliothèque d' ouvrages liés à elle, et en 2010 a publié certains d'entre eux sous la forme d'un livre intitulé: "Le défi décisif: problème 3x +1 ".

"Maintenant, j'en sais beaucoup plus sur ce problème, et je peux toujours dire qu'il est impossible de le résoudre", a déclaré Lagarias.

Tao ne passe généralement pas son temps sur des tâches impossibles. En 2006, il a reçu le Fields Prize , la plus haute distinction en mathématiques, et est considéré comme l'un des meilleurs mathématiciens de sa génération. Il est habitué à résoudre des problèmes, pas à chasser des châteaux en l'air.

«Ce sont les risques associés à la profession de mathématique», a-t-il déclaré. "Vous pouvez devenir obsédé par l'une des grandes tâches connues qui dépassent les capacités de toute personne et perdre une tonne de temps."

Cependant, Tao ne parvient pas toujours à résister aux tentations de cette région. Chaque année, il passe un ou deux jours sur le plus célèbre des problèmes non résolus en mathématiques. Au fil des ans, il a adopté plusieurs approches de l'hypothèse Collatz, mais en vain.

Puis en août, un lecteur anonyme a laissé un commentaire sur le blog de Tao. Il a suggéré d'essayer de résoudre l'hypothèse de Collatz «pour presque tous» les nombres, sans essayer de le prouver pleinement.

"Je n'ai pas répondu, mais cela m'a fait réfléchir à nouveau à cette tâche", a expliqué Tao.

Et il a réalisé que l'hypothèse de Collatz était en quelque sorte similaire aux types spéciaux d'équations - équations différentielles partielles - qui apparaissaient dans les résultats les plus significatifs qu'il avait obtenus au cours de sa carrière.

Entrées et sorties

Les équations différentielles partielles (EDP) peuvent être utilisées pour modéliser bon nombre des processus physiques les plus fondamentaux de l'univers, tels que l'évolution des liquides ou le passage des ondes gravitationnelles dans l'espace-temps. Ils apparaissent dans des situations où la position future du système - par exemple, l'état de l'étang cinq secondes après avoir jeté une pierre dessus - dépend des contributions de deux ou plusieurs facteurs, tels que la viscosité et la vitesse de l'eau.

Il semblerait que les EDP complexes aient peu à voir avec une question arithmétique aussi simple que l'hypothèse de Collatz.

Mais Tao s'est rendu compte qu'ils avaient quelque chose en commun. Il est possible de substituer des valeurs dans le PDE, d'obtenir d'autres valeurs, de répéter le processus - et tout cela pour comprendre l'état futur du système. Pour chaque EDP donnée, les mathématiciens doivent savoir si les valeurs initiales à l'entrée mèneront à des valeurs infinies à la sortie, ou si les équations produiront toujours des valeurs finales, indépendamment des valeurs initiales.


Terence Tao, inspiré par le commentaire de son blog, a fait le plus grand progrès depuis des décennies dans l'étude de l'hypothèse de Collatz

Pour Tao, cet objectif était du même ordre que si vous obtenez toujours la même valeur (1) du processus Collatz, quelle que soit la valeur initiale. En conséquence, il s'est rendu compte que les techniques d'étude des EDP pourraient convenir à l'étude de l'hypothèse de Collatz.

Une technique particulièrement utile utilise une méthode statistique pour étudier le comportement à long terme d'un petit nombre de valeurs initiales (quelque chose comme un petit nombre de configurations d'eau initiales dans un étang) et extrapole le résultat au comportement à long terme de toutes les configurations d'étang initiales possibles.

Dans le contexte de l'hypothèse Collatz, imaginez que nous avons commencé avec un large échantillon de nombres. Notre objectif est d'étudier comment ces nombres se comportent lorsque nous leur appliquons le processus de Collatz. Si près de 100% des nombres de l'échantillon atteignent 1 ou très près de 1, nous pouvons conclure que presque tous les nombres se comporteront de la même manière.

Mais pour que cette conclusion soit justifiée, il est nécessaire de sélectionner soigneusement l'échantillon. Cette tâche est similaire à la compilation d'un échantillon d'électeurs lors de l'élection présidentielle américaine. Pour un échantillonnage minutieux de l'ensemble de la population, des proportions pondérées devraient être utilisées pour les républicains et les démocrates, les hommes et les femmes, etc.

Les nombres ont leurs propres paramètres «démographiques». Nombres pairs et impairs, nombres divisibles par 3 et nombres qui diffèrent les uns des autres de manière encore plus délicate. En créant une sélection de nombres, vous pouvez vous assurer que certains types de nombres y entrent, et que d'autres n'entrent pas, selon un principe équilibré - et mieux vous choisissez des poids, plus vos conclusions seront précises sur tous les nombres en général.

Choix pondéré

La tâche de Tao était beaucoup plus compliquée que de simplement comprendre comment créer une sélection initiale de nombres avec les bons poids. À chaque étape du processus Collatz, les chiffres avec lesquels vous travaillez changent. Un changement évident est que presque tous les chiffres de l'échantillon diminuent.

Un autre changement, peut-être moins évident, est que les chiffres peuvent commencer à s'accumuler en groupes. Par exemple, vous pouvez commencer avec une belle distribution uniforme des nombres de un à un million. Mais après cinq itérations, les nombres sont susceptibles de se concentrer sur plusieurs petits intervalles de la droite numérique. En d'autres termes, vous pouvez commencer avec un bon échantillon, qui en cinq étapes sera désespérément déformé.

"Vous pouvez généralement vous attendre à ce que la distribution après l'itération soit complètement différente de la distribution initiale", a déclaré Tao. Cependant, son idée clé était de savoir comment créer un échantillon de nombres qui, pour la plupart, conservent leurs poids d'origine dans le processus Collatz.

Par exemple, l'échantillon initial de Tao est pondéré de sorte qu'il n'a pas de nombres divisibles par trois, car le processus Collatz élimine encore assez rapidement de tels nombres. Certains autres poids choisis par Tao sont plus difficiles. Il préfère les nombres dont le reste de la division par 3 est 1, et s'écarte des nombres dont le reste de la division par 3 est 2.

En conséquence, l'échantillon avec lequel Tao commence conserve son caractère même après le début du processus Collatz.

"Il a trouvé un moyen de poursuivre ce processus afin qu'après quelques étapes, il soit encore clair de ce qui se passe", a déclaré Saundararajan. «Quand j'ai vu ce travail pour la première fois, j'étais très heureux et j'ai décidé que c'était incroyable.»

Tao a utilisé sa technique d'attribution de poids pour prouver que presque toutes les valeurs initiales - au moins 99% - ont finalement atteint une valeur très proche de 1. Cela lui a permis de conclure que 99% des valeurs initiales sont supérieures à un quadrillion , par conséquent, atteignent des valeurs inférieures à 200.

C'est sans doute le résultat le plus fort de la longue histoire de cette hypothèse.

"Il s'agit d'une grande percée dans notre connaissance de ce qui se passe avec cette tâche", a déclaré Lagarias. «C'est définitivement le meilleur résultat depuis très longtemps.»

La méthode Tao est presque certainement incapable d'obtenir la preuve complète de l'hypothèse de Collatz. La raison en est que sa sélection initiale est encore un peu déformée après chaque étape. La distorsion sera minime, tandis que l'échantillon contient toujours de nombreuses valeurs différentes, loin de 1. Mais dans le processus Collatz, tous les nombres de l'échantillon commencent à tendre vers un, et une petite distorsion devient plus grande - tout comme une petite erreur dans le calcul du résultat du vote n'a pas une grande valeur dans le cas d'un grand échantillon, mais affecte fortement le résultat lorsque l'échantillon est petit.

Toute preuve d'une hypothèse complète sera très probablement basée sur une approche différente. En conséquence, le travail de Tao est à la fois un triomphe et un avertissement à tous ceux qui sont intéressés: dès qu'il vous semble que vous avez acculé la tâche, il échappe.

"Vous pouvez vous rapprocher arbitrairement de l'hypothèse de Collatz, mais cela reste inaccessible", a déclaré Tao.