De ces polynômes qui ne servent pas forcément à quelque chose

Quel est le point commun entre...

(*)
Combien l'armée de Han Xing comporte-t-elle de soldats si, rangés par 3 colonnes, il reste deux soldats, rangés par 5 colonnes, il reste trois soldats et, rangés par 7 colonnes, il reste deux soldats ?
(Problème du livre le Sunzi suanjing, de Sun Zi (IIIe siècle))

,...

(**)
L'équation xⁿ+yⁿ=zⁿ a t-elle des solutions entières strictement positives quand n>2 ?
(Conjecture de Fermat)

et...

(***)
L'équation 9(u²+7v²)²-7(r²+7s²)²=2 a t-elle une nombre fini de solutions ?
(Équation de Martin Davis)

Et bien, dans les 2 cas, on cherche des solutions entières... Ce type de problèmes amène a des équations diophantiennes (Du nom du mathématicien grec Diophante, qui a étudié au IIIe siècle ces équations), c'est à dire, ne faisant intervenir que des entiers.
Dans (*), il "suffit" d'appliquer le théorème des restes chinois (daté de 1247) pour trouver que l'armée de Han Xing compte 23 soldats (ou alors 128, 233, ..., 23+105k, ...).
Pour (**), Wiles a démontré en 1994 que l'équation n'a aucune solution, à l'aide d'outils mathématiques plus élaborés que ceux demandés pour démontrer le théorème chinois. La conjecture de Fermat s'appelle en fait maintenant le théorème de Wiles.
Pour ce qui est de (***), on ne sait pas bien s'il y a une infinité de solutions. On en connait une cinquantaine, comme (u,r,v,s)=(1,1,0,0) (solution triviale) ou (u,r,v,s)=(525692038369576, 2484616164142152, 1556327039191013, 1381783865776981) (solution pas triviale du tout)...

Un problème diophantien peut posséder une seule solution, une infinité de solution ou alors absolument aucune. Certains de ces problèmes sont faciles à résoudre, d'autre bien plus coriace et encore d'autre où les mathématiciens sont totalement désarmés. Une méthode générale pour résoudre tous les problèmes diophantiens, ça serait le pied, non ?

Le dixième problème de Hilbert
En 1900, David Hilbert a tenu une célèbre conférence où il allait poser 23 problèmes (en fait, pour ménager le suspens, il en a posé que 10 lors de sa conférence) qui allait occuper les mathématiciens pendant le siècle à venir. 108 ans après, 11 problèmes sont résolus, 7 partiellement résolus, 4 non résolus et pour le dernier l'énoncé étant trop vague.
Dans le problème n°10, Hilbert parle des problèmes diophantiens, et on peut résumer le problème ainsi : "Existe-il un algorithme qui permettrait de savoir si un problème diophantien possède ou non des solutions ?"

Après de nombreux efforts, Youri Matiiassevitch fini par trancher en 1970 : un tel algorithme ne peut pas exister ! (Et il va falloir y aller au cas par cas...)

Mais Matiiassevitch ne s'est pas contenté de démontrer cette impossibilité, puisqu'il a également établi un théorème génial : tout ensemble récursivement énumérable est diophantien ! Bon, dit comme ça, ça n'a pas l'air génial, mais en tout cas, ça donne de très jolies formules, aussi inutiles les unes que les autres !

Les ensembles diophantiens
Un ensemble de nombres M est dit "diophantiens" s'il a une représentation diophantienne !... Ahem...

Dit autrement : l'ensemble M est diophantien d'équation paramétrée D (D est un polynôme) si pour tout élément a∈M, on peut trouver des entiers naturels x₁, ..., x_n tels que D(a,x₁,...,x_n)=0.
De manière plus formel, on dirait ça comme ça :

M est diophantien si
a ∈ M ⇔ ∃x₁, ..., x_n [D(a,x₁, ..., x_n)=0]

Dit d'une façon équivalente : un ensemble est diophantien si, et seulement si, c'est l'ensemble de toutes les valeurs entières positives prise par un certain polynôme à coefficients entiers pour les valeurs entières positives de ses variables.

Prenons quelques exemples :

L'ensemble des nombres non premiers (plus grands que 2) est un ensemble diophantien, d'équation paramétrée a-(x+2)(y+2)=0.
En effet, un nombre est composé s'il est de la forme a=bc, avec b et c supérieur à 2, donc a=(x+2)(y+2). Ainsi, pour n'importe quel a non premier, on trouve bien des x et y vérifiant a-(x+2)(y+2)=0, et, inversement, en prenant des x et y positifs vérifiant a-(x+2)(y+2)=0, on aboutit à un a non premier.

L'ensemble des nombres pairs est un ensemble diophantiens :
a est pair ⇔∃ x tel que a-2x=0
(Et c'est pas trop difficile à le voir)

Plus difficile : l'ensemble des nombres de Fibonacci (l'ensemble {1,2,3,5,8,13,...}) est un ensemble diophantien :
a est un nombre de Fibonacci ⇔∃ x,y tel que y(2 – (x² + xy – y²)²)=a
Démontrer cette formule est bien plus technique (et je vais d'ailleurs pas le faire, parce que je n'ai aucune idée de la façon dont on peut le faire...), mais trouver une telle représentation de l'ensemble de Fibonacci fut une étape importante dans la résolution du 10eme problème de Hilbert ! C'était soit trouver une représentation de Fibonacci, soit montrer que l'équation de Martin Davis (***) n'a qu'un nombre fini de solutions...

Les ensembles récursivement énumérables
Un ensemble "récursivement énumérable", c'est (grosso modo) un ensemble de nombre que l'on peut trouver grâce à un programme informatique, sans utiliser de fonction hasardeuses du genre "random()"...

Par exemple, l'ensemble des nombres premiers est un ensemble récursivement énumérable : un programme qui les énumérerait le ferait en faisant défiler tous les entiers en testant leur primalité (en testant la divisibilité par tous les nombres inférieurs). Ce n'est pas le meilleur des programmes permettant d'énumérer tous les nombres premiers, mais il ne fait pas intervenir de probabilités.

D'après Youri Matiiassevitch, n'importe quel ensemble récursivement énumérable est diophantien. On peut donc, en théorie, trouver un polynôme dont toutes les valeurs positives sont des nombres premiers...
De la théorie à la pratique, il n'y a qu'un pas ! Après sept ans de travail, Jones, Sato, Wada et Wiens ont réussi a trouvé ce polynôme (à 26 variables et de degré 25 !) dont toutes les valeurs positives sont des nombres premiers :

λ est un nombre premier ⇔∃ a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z tel que

(k+2)[1 – (wz+h+j–q)² – [(gk+2g+k+1)(h+j) + h – z]²   – (2n+p+q+z–e)² – [16(k+1)³(k+2)(n+1)²     + 1 – f²]²   – [e³(e+2)(a+1)² + 1 – o²]²     – [(a²–1)y² + 1 – x²]²   – [16r²y⁴(a²–1) + 1 – u²]²   – [((a+u²(u²–a))²–1)(n+4dy)²     + 1 – (x+cu)²]² – [n+l+v–y]²   – [(a²–1)l² + 1 – m²]²     – [ai+k+1–l–i]²   – [p + l(a–n–1) + b(2an+2a–n²–2n–2) – m]²   – [q+ y(a–p–1) + s(2ap + 2a – p² – 2p – 2) – x]²   – [z + pl(a–p) + t(2ap – p² – 1) – pm]²] = λ

Les nombres premiers servis sur un plateau sous la forme d'un polynôme (Appelé polynôme de Matijasevic, en l'honneur de celui qui a démontré qu'un tel polynôme pouvait exister) ! Sans doute un excellent moyen d'en savoir plus sur les nombres premiers, et d'en trouver de très grands très facilement !
En fait, quand on regarde de plus près l'équation, on voit que cette équation n'a absolument rien de pratique, car il est de la forme (k+2)(1-A²-B²-C²-...-N²). Pour trouver un entier positif (et donc un premier), il faut que le deuxième facteur soit égal à 1, ce que l'on ne peut obtenir qu'avec A=B=...=N=0, soit 14 plus petites équations diophantiennes, difficile à résoudre ! Et la seule chose que peut nous apprendre ce polynôme, c'est la façon dont il a été conçu, c'est à dire, à partir d'un algorithme décrivant l'ensemble des nombres premiers... Autant dire que ce polynôme ne va rien nous apprendre de nouveau !
D'autres polynômes décrivant l'ensemble des nombres premiers ont également été découverts, de différents degrés et nombre de variables. Le record du plus petit degré d'un tel polynôme est 5 (avec 46 variables, et le record du plus petit nombre de variables est de 10 (avec un degré supérieur à 10⁴⁵ !).

Et dans le zoo des ensembles diophantiens, on peut en citer deux autres, composés par Christophe Baxa en 1993, qui ont également une beau polynôme caractéristique :

L'ensemble des nombres premiers de Mersenne (les nombres premiers de la forme 2ⁿ -1) est diophantien, représenté par :

x est un nombre premier de Mersenne ⇔∃ a,b,c,d,f,g,h,i,j,k,l,m tel que

n(1-(4b+3-n)² - b((2 +hn² -a)² + (n³d³(nd+2)(h+1)² +1-m²)² +(db+d+chn²  +g(4a-5)-kn)² + ((a²-1)c² +1 - k²n²)²+(4(a²-1)i²c⁴ +1 -f²)²+((k n+lf)² -((a+f²(f²-a))² -1)(b+1+2jc)²-1)²)) = x

L'ensemble des nombres premiers de Fermat (les nombres premiers de la forme 2^{2^n} +1, bien pratique dans les problèmes de découpage de tartes, dont on soupçonne qu'ils sont en nombre finis) est diophantien, représenté par :

x est un nombre premier de Fermat ⇔∃ a,b,c,d,f,g,h,i,j,k,l,m tel que

(6g+5)(1-(bh+(a-12)c+n(24a-145)-d)² - (16b³h³(bh+1)(a+1)²+1-m²)²-(3g+2-b)² - (2be+e-bh-1)² - (k+b-c)²-((a²-1)c²+1-d²)²-(4(a²-1)i²c⁴+1-f²)² - ((d+lf)²-((a+f²(f²-a))²-1)(b+2jc)²-1)²) = x

Si on parvenait à montrer que l'ensemble des nombres premiers de Fermat est fini, ce polynôme serait réduit à une seule variable !

Et comme pour les polynômes engendrant les nombres premiers, ces deux derniers polynôme n'ont absolument aucun intérêt pour la recherche de propriétés des nombres premiers...

---

Sources :
Le dixième problème de Hilbert, son indécidabilité, Youri Matiiassevitch
Merveilleux nombres premiers, Jean-Paul Delahaye
Wikipédia, toujours

Comments

[Bertaga]

Juste une suggestion d'article : le Loto vient de changer de formule.
La Française des Jeux affirme qu'il y aura plus de "petits" gagnants, que le gros lot sera encore plus gros, mais que ça sera plus difficile de la décrocher. J'ai même lu que "le taux de retour aux joueurs - 50,5 % pour l'actuel Loto - atteindra 55 %"

Mais moi, la seule chose qui m'intéresse c'est l'espérance de gain.

Est-ce que tu pourrais faire un point sur tout cela ?

[Tom Roud]

A noter que le 10ième problème de Hilbert est celui qui a motivé Turing pour décrire ses fameuses machines, définir un programme, etc ... donc en gros pour fonder l'informatique !
(voir :
http://tomroud.com/2008/09/26/il-naurait-jamais-eu-le-nobel-alan-turing/

)