J'ai assisté à deux exposés à Orsay, aujourd'hui. Le premier, par
Pierre Cartier (auquel j'avais fait
référence déjà) concernait Bourbaki. Cartier raconte toujours de
façon très intéressante, il a juste le défaut de partir parfois dans
un peu trop de digressions (même si ses anecdotes sont amusantes). Je
n'essaierai pas de résumer tout ce que j'ai appris, parce que ce sont
plutôt une multitude de petits faits isolés que des grandes idées. De
façon très succincte, son propos était : le bilan strictement
scientifique de Bourbaki est globalement positif, mais son influence
sur l'enseignement (dont il n'est d'ailleurs pas directement
responsable), c'est-à-dire les maths modernes
, a été
catastrophique. Cela pose d'ailleurs la question tout à fait générale
de comment on doit au mieux enseigner les mathématiques (entre autres
— j'en discutais tout à l'heure avec une amie qui est prof en
collège — comment présenter la notion de démonstration
et faire ressentir son intérêt ? cela me semble très délicat),
question dont je ne pense malheureusement pas qu'elle admette de
réponse satisfaisante, en fait. J'y reviendrai peut-être un jour.
Le second était un exposé scientifique (par Bjorn Poonen, un des mathématiciens qui donne les séminaires les plus clairs que je connaisse) et concernait le dixième problème de Hilbert.
Sous sa forme originale, le dixième problème de Hilbert est quelque chose comme ceci : considérons un polynôme f à N variables et à coefficients entiers, on cherche à savoir s'il existe des entiers x1,…,xN tels que f(x1,…,xN)=0 (autrement dit, à savoir si l'équation diophantienne f=0 est résoluble), et on cherche à le faire de façon algorithmique : autrement dit, on demande s'il est possible de trouver un programme informatique (peu importent les détails, si on croit à la thèse de Church-Turing) qui, quand on lui fournit le polynôme f, va déterminer si l'équation est résoluble. La réponse apportée par Yuri Matiyasevič est négative : il n'existe pas de tel algorithme (il démontre même que, quel que soit l'ensemble d'entiers E récursivement énumérable, il existe f à 1+N variables pour un certain N — qui peut être choisi uniformément — tel que a∈E si et seulement si f(a, x1,…,xN) = 0 admet une solution dans les variables x1,…,xN ; et comme on sait qu'on peut trouver des ensembles récursivement énumérables et non récursifs, il ne peut pas y avoir d'algorithme — en fait, on atteint le niveau maximal de non-récursivité au sens de Post, et par ailleurs, ce qui est peut-être encore plus frappant, on peut trouver des f tels que l'existence d'une solution soit indécidable au sens de Gödel, dans n'importe quel système formel récursif contenant au moins l'arithmétique).
Ce qui est remarquable, en revanche, c'est que si on remplace la
recherche de solutions entières par des solutions
rationnelles (on peut aussi permettre aux coefficients de
f d'être rationnels, ça ne change rien dans un cas comme
dans l'autre car on peut toujours chasser les dénominateur), on ignore
si la question est décidable ou non. La plupart des mathématiciens
pensent que la réponse est négative comme sur les entiers, mais
certains sont d'un avis différent (comme Swinnerton-Dyer, notamment,
ou, semble-t-il, Mazur : ce ne sont pas de petits noms), et d'ailleurs
un exposé récent du même Poonen au séminaire Variétés
rationnelles laissait entrevoir un espoir possible de réponse
positive ; cependant, l'exposé d'aujourd'hui laissait plutôt penser à
une réponse négative. En tout cas, c'est une situation un peu
analogue au fameux problème P=NP
: la plupart des gens pensent
qu'il n'y a pas d'algorithme, ce qui est sans doute dommage, mais on
ne sait pas le démontrer, ce qui est également dommage. Sur les
complexes ou les réels (ou les p-adiques), c'est-à-dire si
on cherche des solutions dans un de ces corps-là, il existe bien un
algorithme. L'exposé d'aujourd'hui portait sur le résultat suivant :
il existe un ensemble S de nombres premiers de densité
naturelle 1 (c'est-à-dire que pour x grand, le nombre de
nombres premiers inférieurs à x qui sont dans S
est asymptotiquement équivalent au nombre de nombres premiers
inférieurs à x tout court) tel qu'il n'existe pas
d'algorithme pour détecter l'existence de solutions rationnelles dont
le dénominateur n'a que des facteurs premiers dans S ; si
on pouvait dans cette affirmation prendre pour S l'ensemble
de tous les nombres premiers (ou même, en fait, tous sauf un nombre
fini), ce serait la réponse négative sur les rationnels, mais obtenir
un ensemble de densité naturelle 1 est déjà une indication importante
dans cette direction.
Clarification () : Yann Ollivier me fait remarquer que le résultat tel que je l'annonce est trivial si S n'est pas supposé récursif. Confirmation prise auprès de Bjorn Poonen, l'ensemble S qu'il construit est bien récursif : donc, rajouter cette précision dans les énoncés ci-dessus.