AKS

Cela fait longtemps que ce blog n’a pas parlé de mathématiques. Je suis allé faire un tour chez Lhuna qui recense avec ses élèves les manières de compter. Ce qui m’a amené, je ne sais pas trop comment ni pourquoi sur ce fameux algorithme AKS. Comment ? Vous ne connaissez pas AKS ? On va combler cette lacune.

En août 2002, trois chercheurs indiens annoncent qu’ils ont trouvé un test de primalité déterministe en temps polynomial. La belle affaire me direz vous ! Eh bien figurez-vous que c’est un truc très vachement (vache sacrée bien sûr) étonnant.

« New Method Said to Solve Key Problem in Math » titrait le New York Times du 8 août 2002. (A) -Manindra Agrawal, (K) -Neeraj Kayal et (S) - Nitin Saxena de l’ Indian Institute of Technology ont trouvé un algorithme d’une éclatante simplicité et d’une surprenante élégance. Quelques jours plus tard, les experts s’enthousiasment. Quatre jours avant le gros titre du New York Times, un dimanche, les trois auteurs avaient envoyé à quinze experts un preprint de neuf pages intitulé « PRIMES is in P ». Le soir du même jour Jaikumar Radhakrishnan et Vikraman Arvind, deux papes de ce domaine des mathématiques, leur envoyaient leurs félicitations. Le lundi, un des maîtres du sujet, Carl Pomerance, vérifiait le résultat et, dans son enthousiasme, organisait un séminaire pour l’après-midi et informait Sara Robinson du New York Times. Le mardi le preprint était en accès libre sur Internet. François Morain fit un exposé sur ce sujet au séminaire Bourbaki de mars 2003. Et le vendredi, Dan Bernstein affichait sur le web une amélioration de la preuve du résultat principal, qui tenait en une seule page.

Bref, la brièveté, inhabituelle en mathématiques, de la période de vérification reflète la concision et l’élégance de l’argument et sa simplicité technique. Une preuve, simple, courte, innovante et tellement plaisante « suited for undergraduates ».

Deux autres choses étonnantes:

• Deux des auteurs, Kayal et Saxena, venaient juste de recevoir leur diplôme de licence en informatique.
• Cette découverte sensationnelle est accessible à l’« homme ordinaire » ce qui est inédit pour les mathématiques de ces cent dernières années. 

Pour être honnête, je dois avouer que, soit cette dernière prétention est très excessive, soit je suis un homme « sous-ordinaire ». Au départ, j'étais content, cela partait du petit théorème de Fermat : (x − a)^n ≡  (x^n − a) mod n... des nombres de Sophie Germain. Puis soudain quelques anneaux et corps plus loin, j'ai perdu pied... Au secours!

Bref, à lire superficiellement la démonstration, je veux bien admettre que je pourrais sans doute tenter de la comprendre un jour (mais je n’ai pas envie :-) alors que, j’ai abandonné sans même lutter l’idée même de comprendre la démonstration de Wiles du grand théorème de Fermat. 

A votre bon coeur c'est « suited for undergraduates ».