10/01/2019

Les nombres de Lychrel existent-ils?

nombres2.jpgCelles et ceux qui goûtent les palindromes, ces mots qui se lisent dans les deux sens, apprécieront peut-être les constructions mathématiques qui vont suivre. D'autant plus qu'elles débouchent sur l'un de ces problèmes ouverts qui semblent nous défier pour l'éternité et qu'on peut résumer en une seule question: les nombres de Lychrel existent-ils? Mais de quoi s'agit-il? De nombres théoriques mis au jour par un certain Wade VanLandingham, qui leur a donné ce nom pour créer un presque anagramme avec le prénom de sa fiancée (Cheryl). Pour faire simple, un nombre de Lychrel est un nombre naturel qui ne peut pas former un palindrome lorsqu'on le soumet au processus itératif consistant à l'additionner à son miroir, c'est-à-dire au nombre formé par ses chiffres inversés. Un exemple clarifiera immédiatement l'affaire. Prenons un nombre au hasard: 59. Additionnons-le à son miroir, soit 95 :


59 + 95 = 154


Sur ce, on répète l'opération :


154 + 451 = 605


Jusqu'à obtenir un joli palindrome :


605 + 506 = 1111


Pour ce nombre, seules trois itérations ont été nécessaires avant d'atterrir sur un palindrome. Ce qui signifie que ni 59 ni 95 ne sont des nombres de Lychrel - ni 154, 451, 605 et 506. Mais il en faut parfois davantage (d'itérations). Avec le nombre 89, cela va un peu moins vite, puisqu'il en faut vingt-quatre. Quant au record du nombre d'itérations, ou plutôt du palindrome le plus retardé, il est détenu en ce moment par 1 186 060 307 891 929 990, qui nécessite 261 itérations avant de tomber sur un beau palindrome formé de 119 chiffres. Paradoxe, c'est un algorithme qui a permis de le découvrir, alors qu'il n'existe aucun algorithme permettant de contourner les opérations d'addition et d'inversion. Notons encore  que 80 % des nombres en dessous de 10 000 aboutissent à un palindrome en moins de 4 itérations, et environ 90 % en moins de 7.
Mais tout cela ne nous amène pas pour autant à un nombre de Lychrel. Mieux, on n'en connaît à ce jour aucun. En revanche, il y a des candidats. Soit des nombres pour lesquels cela ne marche pas. C’est-à-dire pour lesquels le processus d'itération ne semble jamais s'arrêter. Le plus petit de ces candidats est le nombre 196, qui mérite qu'on s'y attarde quelques instants. Suspecté d'être un Lychrel, 196 attire l'attention de plusieurs mathématiciens. Le 12 août 1987, John Walker lance une recherche via un programme qui vérifie les itérations et produit un rapport toutes les deux heures. Trois ans plus tard, le 24 mai 1990, le programme s'arrêtait après 2 415 836 itérations sur un nombre d'un million de chiffres. Et sans trace de palindrome.
En 1995, un certain Tim Irvin prend le relais. En trois mois, il obtient un nombre de deux millions de chiffres. Qui n'est pas un palindrome, on s'en doute. Jason Doucette continue sur la même lancée. En mai 2000, il débouche sur un nombre de 12,5 millions de chiffres. Toujours pas de palindrome en vue. C'est là qu'intervient Wade VanLandingham, bien décidé à continuer les investigations. Avec le même programme, il passe le cap des 13 millions, et le 1er mai 2006, atteint même la barre impressionnante des 300 millions de chiffres. Evidemment sans palindrome en vue. En d'autres termes, 196 a tout du parfait candidat. C'est le cas d'autres nombres, comme 887, 1495, 1497, 1945, 1947 ou 1997. Pour le moment, tous les candidats de moins de 17 chiffres ont été identifiés.
Actuellement, on est incapable de montrer pourquoi le processus d'itération ne s'arrête pas pour ces nombres-là. Du moins en base 10. Car pour certaines bases, il est prouvé que des Lychrel existent. Des tentatives de démonstration de l'existence des Lychrel en base dix fleurissent ici ou là, dont une fort intéressante qui stipule que celle-ci est due à une brisure de symétrie dans l'espace des nombres analogue à celle que l'on retrouve en physique des particules. Aucune des conjectures liées aux nombres de Lychrel n’est pour l’instant mise à prix.

20:27 Publié dans Mathématiques, Sciences | Lien permanent | Commentaires (1) | |  Facebook | | | |

21/10/2018

Guérison du cancer, sécurité bancaire en péril, addiction à «Candy Crush» : a-t-on résolu le problème P = NP ?

P NP.jpgSi vous êtes attentifs et accro aux news de toute provenance, il ne vous aura sans doute pas échappé qu’en août 2017, un mathématicien allemand, Norbert Blum, affirmait avoir résolu le plus célèbre problème ouvert de mathématiques et d'informatique théorique, soit le problème P = NP, concluant par la négative que P n'est pas égal à NP. La communauté, qui se penche depuis sur la question et les 38 pages de sa démonstration, n'a pas encore rendu son verdict, tout en laissant entendre qu'il y a peut-être une erreur dans son raisonnement. C'est que l'enjeu est énorme. Il y a d'abord la récompense d'un million de dollars (décerné par le Clay Mathematics Institute). Et ensuite la renommée mondiale que cette démonstration impliquerait. Le problème P = NP a été énoncé pour la première fois dans les années 70. Il s'agit d'une conjecture dont l'importance est fondamentale dans l'histoire des sciences. Tenter de la présenter n'est pas le plus simple des exercices et j'y serai sans doute moins à l'aise que Siraj Raval, dont voici la chaîne YouTube (https://www.youtube.com/channel/UCWN3xxRkmTPmbKwht9FuE5A), et dont je recommande le visionnement de plusieurs vidéos, comme s'il n'avait déjà pas assez de clics.
De manière caricaturale, on pourrait réduire les définitions de P et NP en affirmant qu’on a d’un côté les problèmes (mathématiques) faciles à résoudre (P) et de l’autre ceux qui ne le sont pas (ou moins) (NP). Les problèmes dits de classe P peuvent en effet être décidés (et résolus) en temps polynomial par une machine de Turing ou apparentée. Donc se décomposer en un algorithme ou une suite de calculs relativement basiques que les ordinateurs peuvent exécuter assez rapidement. Ceux de classe NP (pour «nondeterministic polynomial time») ne peuvent pas être résolus si rapidement. Pire, le nombre de solutions qu’ils comportent pose problème, et ne présupposent pas forcément l’existence d’un algorithme. Prenons un exemple concret, celui de la décomposition d’un nombre entier en facteurs premiers. Facile ? Non, pas si le nombre est trop grand. Car il faut alors tenter de le diviser par tous les facteurs premiers inférieurs, et cela peut prendre un temps infiniment long. Sans algorithme, même les plus puissants des ordinateurs n’en viendraient pas à bout assez vite. Et prendraient parfois jusqu’à plusieurs milliers d’années pour casser le nombre. C’est d’ailleurs sur ce type de clés que repose la sécurité bancaire, vous me suivez ?

carte.jpgLe problème du voyageur de commerce, qui consiste à déterminer le chemin le plus court pour passer dans plusieurs villes une et une seule fois sur un circuit donné, est fréquemment utilisé pour illustrer ce qu’on appelle un problème NP-complet - j’y consacrerai un autre billet prochainement. Ce joli graphe ci-dessus l’illustre et un petit détour par la théorie des graphes est elle aussi au menu d’un billet futur. Dans l’attente, revenons à l’interrogation cruciale mise à prix par le Clay Institute. Et rappelons qu’à l’heure actuelle, on ne sait pas si P = NP, si P ≠ NP ou si l’égalité est non décidable, et cela même si certains chercheurs isolés affirment avoir démontré la chose. En revanche, on sait que P est inclus dans NP. Soit, mais à quoi tout cela mène-t-il ? Si on ramène l’égalité P = NP à une question, on peut la formuler ainsi : lorsqu’une solution à un problème est rapidement vérifiable, peut-elle être rapidement trouvée ? Autrement dit, peut-on trouver en temps polynomial ce que l'on peut prouver en temps polynomial?

Intuitivement, la plupart des mathématiciens pensent que P ≠ NP, et c’est sans doute le cas. Mais si c’était l’inverse, si P = NP était vrai, alors cela changerait la face du monde. En effet, entre autres implications, cela signifierait, en médecine, qu’on pourrait soigner certaines formes de cancer. Si des algorithmes suffisaient à prouver que des problèmes complexes n’étaient que des variantes de problèmes simples (P = NP), une meilleure compréhension du processus conférant leur structure aux protéines permettrait ainsi d’empêcher qu’il ne s’en forme des anormales, et donc à terme freiner, voire stopper la prolifération de certaines catégories de cancer. Le chiffrement des données bancaires, lui, serait sacrément mis à mal, et casser un code de 256-bit (c’est généralement celui qui est utilisé pour vos cartes bancaires) serait assez aisé, du moins si le temps pour décomposer un nombre très grand en facteurs premiers diminuait, ce qu’on peut supposer si P = NP. Même chose pour la protection des données et des informations sur Internet, a priori déjà fragilisées. Il faudrait tout revoir (après un probable krach informatique mondial), d’autant plus que les protocoles de sécurité sur le net reposent tous sur le fait que…  P ≠ NP.

Ce n’est évidemment pas tout. On pourrait alors viser plus haut et tenter de déterminer une partie d’échecs parfaite ou encore résoudre le casse-tête posé par ce jeu addictif et sucré nommé «Candy Crush», qui se pratique aussi bien sur smartphone que derrière un écran : tous deux sont en effet considérés comme des problèmes NP-complets. Pour l’instant, nous en sommes loin. Et comme la solution du problème risque d’être P ≠ NP, toutes ces séduisantes hypothèses risquent bien de s’effondrer comme châteaux de sable.

17:20 Publié dans Mathématiques, Sciences | Lien permanent | Commentaires (3) | |  Facebook | | | |

24/05/2018

Variations autour de l’infini (1)

infini.jpgL’infini est un concept purement mathématique qui ne recouvre aucune réalité physique. Cette vérité est dure à entendre, et encore plus malaisée à comprendre. Affirmer, penser ou croire l'inverse repose sur une confusion fréquente entre l’immensément grand et l’infini en soi, autrement dit ce qui n’a pas de fin. Dans les deux cas intervient la notion de comptage, qui, là aussi et dans les deux occurrences, dépasse souvent une vie humaine, et même une vie remontant à, mettons, dix générations, ce qui pour certains peut représenter, à défaut de l’être, l’infini. On tend souvent vers l’infini, et pas seulement dans les limites en mathématiques, mais on ne l’égalise jamais. Car l’infini n’est pas un nombre, il est ce vers quoi on tend (ou pas), un symbole, si l’on préfère (représenté par le lemniscate), que la vision de deux miroirs qui se font face permet d’entrevoir. Ce qui est immensément grand, même lorsque c’est hors de portée de notre entendement – les bornes de l’univers, le nombre d’atomes contenus dans la Voie lactée, et autres collections d’objets plus ou moins analogues – est par définition impossible à compter dans un laps de temps contenu entre douze mois et mille ans, par exemple. Laps de temps fermé donc fini. Tout ce qui est physique s’inscrit dans semblable intervalle et possède une borne. Le nombre d’atomes contenus dans l’univers est fini. Le nombre de nos ancêtres, même à supposer qu’on puisse remonter aux origines de notre espèce, également.

Le nombre de livres possible est lui aussi fini (relisez La Bibliothèque de Babel de Borges, qui en fournit d’élégantes preuves). Le nombre de films possible est à son tour fini. Il suffit pour cela de décomposer chaque photogramme en milliers de particules lumineuses puis d’y appliquer le schéma borgesien. Le nombre obtenu sera gigantesque, il faudra encore le multiplier par le nombre de photogrammes combinés à tous les autres, dans une incessante spirale, et on obtiendra un nombre sans doute trop petit pour être contenu dans une bibliothèque qui aurait la taille de notre système solaire. Il n’empêche que cela resterait un nombre fini. Le même raisonnement aboutit à des paradoxes. Le nombre d’espèces contenues dans l’univers entier est fini, tout comme le nombre de sites internet envisageables, celui des fruits, légumes et mauvaises herbes qui pousseront sur terre jusqu’à la fin du monde, et les secondes égrenant la somme de toutes les vies humaines apparues depuis le début de l’humanité. Idem pour les individus, tous différents entre eux, mais pas de manière infinie.

La perspective mathématique ouvre d’autres horizons. Il y existe des nombres univers. Et infinis (mais l’un est le corollaire de l’autre, si on me permet ce raccourci sémantique). Projections mentales, non représentables. Exemple ce nombre constitué de la suite de tous les entiers, de leur concaténation, suite pour le coup infinie. Il contient n’importe quelle séquence finie possible de chiffres autant de fois qu’on le désire. On suppose que Pi et racine carrée de 2 sont des nombres univers, mais ce n’est pas prouvé. Je puis même supposer qu’ils ne le sont pas, aucune preuve, y compris par l’absurde, ne pourra étayer mes convictions. Et puis il y eut Cantor, qui découvrit l’impensable, des infinis de tailles différentes. Les transfinis, puisque c’est d’eux qu’il s’agit, ensembles avec ou sans bijections, dénombrables ou pas, inclusions sans fin et hypothèse du continu, aujourd’hui considérée comme indécidable.

Et ceci amène cela. Les problèmes non résolus en mathématiques coincent tous sur leur infinitude. Démontrer l’hypothèse de Riemann reviendrait à passer en revue tous les zéros (non triviaux) de la fonction zêta, jusqu’à l’infini. Certains y sont parvenus pour des très grands nombres, mais même un milliard de milliard de milliards reste dérisoire par rapport à l’infini. La conjecture des premiers jumeaux ne pourra se prouver que lorsque son infinitude sera domptée. Semblable perspective terrorisa plusieurs générations de chercheurs qui butèrent sur le théorème de Fermat. Jusqu’à ce qu’Andrew Wiles, au XXe siècle, résolve l’affaire et atteigne le Graal après plus de 350 ans d’échecs. Et s’il fond en larmes lorsqu’il l’évoque dans un documentaire à lui consacré, au moment où il réalise qu’il a dompté Fermat, s’il éclate en sanglots à cet instant précis, c’est parce qu’il sait qu’il vient de toucher l’infini. Le geste est sublime, il ne survient qu’une fois par siècle et vaut tous les trésors de ce monde fini qui est le nôtre.

14:01 Publié dans Mathématiques, Sciences | Lien permanent | Commentaires (2) | |  Facebook | | | |