10 avancées majeures en mathématiques et en informatique théorique, expliquées simplement

Les mathématiques et l'informatique théorique font rarement la une comme le fait un nouveau smartphone ou une décision de justice, mais une poignée de résultats dans ces domaines ont discrètement transformé ce que les ordinateurs peuvent faire, ce que le chiffrement peut garantir, et ce qui compte comme un problème résolu. Voici dix des plus significatifs, choisis pour l'ampleur avec laquelle ils ont changé leur domaine plutôt que pour leur seule difficulté technique.

Le dernier théorème de Fermat, qui affirme qu'aucun triplet de nombres entiers positifs ne peut satisfaire une certaine équation simple dès lors que l'exposant dépasse deux, est resté sans démonstration pendant environ 350 ans après que le mathématicien du XVIIe siècle Pierre de Fermat eut affirmé détenir une preuve qu'il n'a jamais écrite. Le mathématicien britannique Andrew Wiles l'a finalement démontré en 1994, dans une preuve de plusieurs centaines de pages s'appuyant sur des techniques bien au-delà de ce que Fermat aurait pu connaître, clôturant l'une des questions ouvertes les plus célèbres des mathématiques.

La conjecture de Poincaré, un énoncé sur la forme des espaces tridimensionnels formulé pour la première fois en 1904, est restée non résolue jusqu'à ce que le mathématicien russe Grigori Perelman publie une preuve en 2002 et 2003 utilisant une technique appelée flot de Ricci, qui lisse progressivement les irrégularités des formes géométriques. Elle demeure à ce jour le seul des sept problèmes du prix du millénaire, une liste de grandes questions non résolues dotées chacune d'une récompense d'un million de dollars, à avoir été résolu ; Perelman a refusé aussi bien l'argent du prix que la médaille Fields.

En 1976, le théorème des quatre couleurs, selon lequel toute carte peut être coloriée avec seulement quatre couleurs de sorte que deux régions adjacentes n'aient jamais la même couleur, est devenu le premier grand théorème mathématique démontré avec l'aide substantielle d'un ordinateur, lorsque Kenneth Appel et Wolfgang Haken ont utilisé un programme pour vérifier des milliers de configurations de cartes individuelles qu'il aurait été impossible de vérifier à la main. Ce résultat a déclenché un débat de longue date sur la question de savoir si une preuve trop volumineuse pour être vérifiée ligne par ligne par un humain compte encore comme une preuve.

Les progrès sur la conjecture des nombres premiers jumeaux, l'idée toujours non démontrée selon laquelle il existe une infinité de paires de nombres premiers différant exactement de deux, ont fait un bond en avant majeur en 2013 lorsque Yitang Zhang, alors chargé de cours relativement inconnu, a démontré qu'il existe une infinité de paires de nombres premiers différant de moins de 70 millions. Un effort collaboratif rapide impliquant le mathématicien James Maynard et d'autres a ramené cet écart à 246, bien que le réduire à la valeur conjecturée de deux reste non résolu.

L'algorithme de Peter Shor, publié en 1994, a montré qu'un ordinateur quantique suffisamment puissant pourrait factoriser de grands nombres exponentiellement plus vite que toute méthode connue sur un ordinateur classique, un résultat d'une importance considérable car une grande partie du chiffrement moderne, y compris les systèmes qui sécurisent les opérations bancaires en ligne et les communications, repose sur le fait que factoriser de grands nombres est calculatoirement infaisable. L'algorithme de Shor reste une raison centrale pour laquelle gouvernements et entreprises se pressent de développer à la fois des ordinateurs quantiques et un chiffrement résistant au quantique.

Le théorème PCP, développé au début des années 1990 par un groupe d'informaticiens théoriciens, a montré que toute preuve mathématique peut être réécrite sous une forme qu'un vérificateur peut contrôler en n'examinant qu'une petite fraction choisie au hasard, tout en détectant néanmoins toute erreur avec une forte probabilité. Ce résultat a transformé l'étude des algorithmes d'approximation, fournissant un moyen rigoureux de démontrer que certains problèmes d'optimisation ne peuvent pas être approchés efficacement, et non simplement que personne n'avait encore trouvé le moyen de le faire.

Déterminer si deux grands graphes complexes sont structurellement identiques, ce que l'on appelle le problème de l'isomorphisme de graphes, avait résisté pendant des décennies à des algorithmes généraux efficaces. En 2015, le mathématicien László Babai a annoncé un algorithme en temps quasi polynomial pour ce problème, une amélioration significative par rapport aux approches précédentes et une avancée notable en théorie de la complexité computationnelle, un domaine qui s'intéresse à la classification de la difficulté des différents problèmes de calcul.

La question de savoir comment empiler des sphères aussi densément que possible dans un nombre donné de dimensions n'avait été résolue que pour une poignée de dimensions basses jusqu'à ce que la mathématicienne Maryna Viazovska démontre l'empilement optimal pour un espace à huit dimensions en 2016, puis, peu après, en collaboration avec plusieurs autres chercheurs, étende la technique pour résoudre le même problème en 24 dimensions, des résultats qui ont également eu des implications pour la théorie de l'information et les codes correcteurs d'erreurs.

Le problème de discrépance d'Erdős, posé par le prolifique mathématicien Paul Erdős, portait sur le degré d'inégalité avec lequel une suite de valeurs plus un et moins un pouvait être répartie. Un cas particulier a été vérifié en 2014 à l'aide d'un solveur SAT informatique, dans une preuve si volumineuse qu'elle nécessitait environ 13 gigaoctets pour être stockée, l'une des plus grandes preuves mathématiques jamais produites à l'époque. L'année suivante, Terence Tao a démontré la conjecture complète et générale à l'aide de méthodes analytiques plus traditionnelles, résolvant un problème resté ouvert depuis les années 1930.

Ce qui unit ces résultats, disent les mathématiciens, tient moins à leur sujet qu'à ce qu'ils révèlent sur la façon dont progressent les mathématiques : parfois par des décennies de raffinement progressif mené par de nombreux chercheurs, comme pour les écarts entre nombres premiers, et parfois par une seule intuition qui recadre un problème entier, comme pour le flot de Ricci ou le théorème PCP, les ordinateurs jouant un rôle croissant, soit comme outil de vérification, soit, plus récemment, comme collaborateur de recherche à part entière.