Dans la deuxième partie , nous avons calculé la complexité de la multiplication scolaire à N chiffres : il s'agit d'un calcul à temps quadratique, nous avions vu que l'addition scolaire est un calcul à temps linéaire dans la première partie
Nous avions conclut que ces deux opérations appartiennent à l'ensemble P, qui représente l'ensemble des calculs déterministes à temps polynomial.
Dans la conjecture P = NP, l'ensemble NP représente les calculs non déterministes à temps polynomial. Mais avant de revenir sur cet ensemble plus en détail, il nous faut voir une dernière notion.
Avant, je dois préciser que certains passages peuvent contenir des erreurs pour deux raisons : d'une part, je ne suis pas un spécialiste de la théorie de la complexité et encore moins du problème P = NP. D'autre part, je présenterai à certains endroits mon point de vue, qui là encore peut contenir des erreurs ou même sembler simpliste aux spécialistes, vous voilà prévenus...
Les calculs à temps exponentiel
Imaginons que l'on souhaite connaître le nombre d'ancêtres A que nous avons, pour une génération N, par exemple :
A(1) = 2 (parents)
A(2) = 4 (grands parents)
A(3) = 8 (arrière grands parents)
...
A(N) = 2^N
Pour calculer A(N), il nous faut multiplier le résultat précédent A(N-1) par deux. En prenant comme opération unitaire la multiplication, on a donc un calcul à temps exponentiel, c'est à dire du type :
T(calcul exponentiel) = K^N
Où K est un nombre fixé (2 dans le cas du calcul des ancêtres) et N le nombre de données (dans notre exemple, le nombre de générations)
Un point fréquent dans les calculs à temps exponentiels est qu'ils sont récursifs : pour calculer A(N), on doit calculer A(N-1). Le résultat final n'est possible qu'en faisant tous les calculs
Mon point de vue : On peut se représenter le calcul à temps polynomial ou exponentiel comme une série de calculs à effectuer dans l'ordre : les calculs sont "branchés" en série, un peu comme des composants d'un circuit électrique. Tous les "circuits sont nécéssaires pour alimenter" le résultat. Les problèmes P ou E (voir plus bas) sont des "calculs en ET".
Nous pouvons maintenant définir l'ensemble E, comme étant l'ensemble des calculs à temps exponentiel. Mais quel rapport avec P = NP ? En quoi cela peut-il nous aider à définir l'ensemble NP ?
Calculs non déterministes à temps polynomial
Que signifie un calcul "non déterministe" ? En gros, que l'algorithme doit effectuer un certain nombre de calculs indépendants les uns des autres et qu'en fonction du "choix" qu'il fera, il pourra mettre moins de temps que nécéssaire, s'il avait dû tous les calculer, ou s'il les avait calculé dans un "ordre déterministe".
Pour cette raison, on dit souvent que les problèmes de la classe NP sont des problèmes de "décision".
On observe plusieurs propriétés importantes des problèmes de la classe NP :
- On peut calculer un problème NP avec un algorithme à temps exponentiel
- On peut vérifier le calcul d'un problème NP avec un algorithme à temps polynomial
On voit qu'en terme d'efficacité, les problèmes NP semblent se situer "entre" les problèmes P et E.
Autre point important : un problème P fait également partie de la classe NP. En termes ensembliste, on dira que l'ensemble P est inclus dans l'ensemble NP.
En mathématique, pour que deux ensembles (P et NP) soient égaux, il faut (et il suffit) qu'ils soient inclus l'un dans l'autre. Nous savons déjà que P est inclus dans NP. Toute la question de l'hypothèse P = NP est en fait de savoir si la réciproque est vraie : En fait la question n'est pas "P est-il égal à NP ?", mais plus précisément "NP est-il inclus dans P ?", autrement dit :
Pour chaque problème NP, existe-il un algorithme déterministe à temps polynomial capable de le résoudre ?
Généralement, les problèmes mathématiques commençant par "Pour chaque...existe t'il..." sont les plus difficiles à résoudre , car il faut démontrer l'existence d'un tel algorithme pour chaque problème, mais comment peut-on étudier en même temps TOUS les problèmes de type NP ? (Une blague de mathématicien serait de dire qu'on se trouve en face d'un problème à temps exponentiel...)
En fait, dans les années 60, un mathématicien américain du nom de Stephen Cook a découvert qu'on pouvait étudier tous les problèmes d'une classe, en étudiant uniquement "les plus difficiles" de cette classe : En résumé, "qui peut le plus, peut le moins". On appelle ces problèmes des problèmes complets.
Un problème NP-Complet : le problème du voyageur
Imaginons qu'un touriste veuille visiter N villes. Il souhaite effectuer le trajet le plus court possible, ou plus précisément, plus court qu'une certaine distance autorisée, qu'on appelera D, tout en passant par toutes les villes.
Pour résoudre ce calcul il faudrait à priori calculer toutes les combinaisons possibles de trajets, soit (N-1)! et sélectionner uniquement celles inférieures à D, par exemple :
Pour deux villes (N=2), il y a 1 seul trajet possible (T=1), donc une seule distance à calculer.
N = 3, T = 2
N = 4, T = 6
N = 5, T = 24
...
N = k, T = (k-1)! = (k-1) * (k-2) * ... * 1
On retrouve un peu le même schéma que pour le calcul des ancêtres (à temps exponentiel) : une série de multiplications, on peut donc à priori classer cet algorithme dans l'ensemble E.
Cependant, on peut vérifier si notre solution est correcte en beaucoup moins de temps : en faisant la somme des distances des trajets parcourus, on obtient une distance qui doit nécéssairement être inférieure à D. L'algorithme de vérification appartient à la classe P, car le temps de calcul est proportionnel au nombre de villes.
Ces deux éléments (calcul dans E et vérification dans P) suffisent à classer notre problème dans la catégorie NP.
En plus de cela (la démonstration m'est inconnue) ce problème est un problème "NP difficile", un problème NP-Complet. On peut reformuler la conjecture P = NP comme cela :
Si on parvient à trouver un algorithme déterministe à temps polynomial pour résoudre le problème du voyageur, alors on pourra le faire pour n'importe quel problème NP. La classe NP sera alors réduite à la classe P.
Le problème, c'est que personne n'a encore trouvé d'algorithme déterministe à temps polynomial pour aucun problème NP-Complet, donc pour l'instant, force est de constater que P n'est pas égal à NP !
Mon point de vue : P n'est pas égal à NP
Comme je l'ai dit dans la première partie de cet article, je ne suis pas un spécialiste, pourtant, en lisant divers articles sur le problème P = NP, dont l'excellent livre "les énigmes mathématiques du 3ème millénaire", je me suis mis à rêver d'une légitimité pour donner ma conception de ce problème... Voici mon idée, peut-être naïve ou stupide, mais c'est une idée...
Les problèmes NP consistent à effectuer plusieurs calculs, qui sont à priori pas tous nécéssaires, pour les résoudre : Dans le problème du voyageur, "si on a de la chance", on peut tomber sur le plus court trajet du premier coup, pas besoin de tous les calculer.
On peut se représenter les problèmes NP comme des calculs "en parallèle" (comme dans un circuit électrique), nous n'avons pas besoin "d'alimenter tous les circuits" pour arriver au résultat. Les problème NP sont des "calculs en OU".
J'ai dit plus haut que les problèmes P ou E sont des "calculs en ET". D'où la nécéssité d'effectuer TOUS les calculs pour arriver au résultat.
Les mathématiciens, car il existe de nombreuses méthodes (appelées heuristiques) pour trouver les meilleurs chemins, ont conjecturé qu'un problème NP ("calcul en OU") n'est pas aussi complexe qu'un problème E ("calcul en ET"). ET que donc, on pouvait réduire les problèmes NP à des problèmes P ("calculs en ET") beaucoup plus simples que le problème E ("calcul en ET") équivalent.
Mon idée est que pour un algorithme donné, il existe un seul "calcul en ET" et que celui-ci est nécéssairement le problème E d'origine. Je dirais donc que NP n'est pas inclus dans P mais qu'au contraire, NP est inclus dans E.
Je pense que le meilleur moyen de résoudre un problème NP est donc d'utiliser ces heuristiques ou des algorithmes non déterministes comme par exemple les algorithmes génétiques.
Car il est vrai qu'un problème NP se distingue d'un problème E, par la possibilité de "sauter" des étapes du calcul, mais je suis convaincu qu'il n'existe pas de "formule magique" pour effectuer ce choix, on peut simplement éviter de faire de "mauvais choix" (heuristiques), ou expérimenter des échantillons prometteurs de choix (algo génétique).
J'ai bien conscience qu'il s'agit d'un avis tranché, sans aucun vrai argument scientifique ou mathématique. J'essayerai d'étayer cette idée plus tard avec, si je peux, des arguments plus rigoureux ou à défaut, par d'autres images peut-être plus convaincantes.
Une dernière précision sur P = NP : on peut se poser la question de savoir si cette conjecture est démontrable (ou réfutable). Autrement dit, il y a trois réponses possibles à la question P = NP ?
1- Vrai
2- Faux
3- Indémontrable
J'ai dis que je pensais que la réponse était Faux, mais je dois avouer que la troisième solution est tentante : Cela pourrait signifier soit une limite dans les outils mathématiques à notre portée (3A), soit que la question n'a pas de sens dans l'absolu (3B).
En résumé, je pencherais pour la solution 2 ou - dans une moindre mesure - la solution 3B.
Et vous, qu'en pensez-vous ? Quelle solution vous semble la plus plausible ?
PS : Si j'ai commis des erreurs dans cet article, je vous prie de m'en excuser, je n'aime pas trop me documenter pour écrire, mon but n'était pas de faire une "leçon" sur la théorie de la complexité. N'hésitez pas à apporter des corrections si nécéssaire.
Affichage des articles dont le libellé est mathématiques. Afficher tous les articles
Affichage des articles dont le libellé est mathématiques. Afficher tous les articles
lundi 11 février 2008
vendredi 25 janvier 2008
P = NP : problème ou illusion ? (partie 2)
Dans la première partie nous avons calculé la complexité de l'addition scolaire, dans le cas d'une addition à N chiffres, on a vu que l'addition scolaire était un calcul à temps linéaire, c'est à dire que le temps de calcul est proportionnel à N.
Calculons maintenant la complexité de la multiplication scolaire à N chiffres. Pour cela, nous allons prendre comme unité de temps, l'opération AxB, où A et B sont des nombres à un seul chiffre, donc :
T(AxB) = 1
Si on note A(N) et B(N) des nombres à N chiffres, calculer T(A(N)xB(N)) revient à calculer combien de multiplications "unitaires" (chiffre à chiffre) il faut réaliser pour calculer A(N)xB(N) avec la méthode scolaire.
Pour N = 2, par exemple, avec A(2) = 12 et B(2) = 34
12 * 34 = 2*4 + 10*(4*1) + 10*( 3*2 + 10*(3*1) )
Comme nous sommes en base 10, l'opération X + 10*Y revient à accoler les chiffres X et Y, en écrivant le nombre "YX", cette opération ne sera pas comptabilisé dans le calcul de la ocmplexité, on a donc :
T(A(2)xB(2)) = 4
De manière générale, pour multiplier deux nombres à N chiffres, il faudra multiplier deux à deux chaque chiffre de l'un avec ceux de l'autre, on obtient donc :
T(A(N)xB(N)) = N²
On en déduit que la multiplication scolaire est un calcul à temps quadratique : Le temps de calcul nécéssaire dépend du carré du nombre de chiffres.
De la même manière, on peut calculer le temps de calcul de n'importe quelle opération ou algorithme.
Les calculs comme l'addition ou la multiplication sont dits à temps "polynomial", car le temps dépend d'une fonction polynomiale de N (le nombre de données), c'est à dire :
T(calcul polynomial) = somme (a(k)*N^k) pour k entier
On peut donc classer l'addition et la multiplication (et un grand nombre d'autres calculs) dans l'ensemble des calculs à temps polynomiaux, on appelle cet ensemble P. (le fameux P de P = NP)
Plus précisément, l'ensemble P est appellé "Ensemble des calculs déterministes à temps polynomial", c'est à dire l'ensemble des calculs qui ne font pas appel à des fonctions aléatoires (comme l'addition ou la multiplication)
On devine donc que l'ensemble NP est tout simplement "L'Ensemble des calculs non déterministes à temps polynomial" (et non comme on le croit parfois, "L'ensemble des calculs à temps non polynomial)
Voilà pour la base... Dans la prochaine partie, nous verrons un troisième ensemble et je tenterai de donner une explication concrète du problème P = NP.
Calculons maintenant la complexité de la multiplication scolaire à N chiffres. Pour cela, nous allons prendre comme unité de temps, l'opération AxB, où A et B sont des nombres à un seul chiffre, donc :
T(AxB) = 1
Si on note A(N) et B(N) des nombres à N chiffres, calculer T(A(N)xB(N)) revient à calculer combien de multiplications "unitaires" (chiffre à chiffre) il faut réaliser pour calculer A(N)xB(N) avec la méthode scolaire.
Pour N = 2, par exemple, avec A(2) = 12 et B(2) = 34
12 * 34 = 2*4 + 10*(4*1) + 10*( 3*2 + 10*(3*1) )
Comme nous sommes en base 10, l'opération X + 10*Y revient à accoler les chiffres X et Y, en écrivant le nombre "YX", cette opération ne sera pas comptabilisé dans le calcul de la ocmplexité, on a donc :
T(A(2)xB(2)) = 4
De manière générale, pour multiplier deux nombres à N chiffres, il faudra multiplier deux à deux chaque chiffre de l'un avec ceux de l'autre, on obtient donc :
T(A(N)xB(N)) = N²
On en déduit que la multiplication scolaire est un calcul à temps quadratique : Le temps de calcul nécéssaire dépend du carré du nombre de chiffres.
De la même manière, on peut calculer le temps de calcul de n'importe quelle opération ou algorithme.
Les calculs comme l'addition ou la multiplication sont dits à temps "polynomial", car le temps dépend d'une fonction polynomiale de N (le nombre de données), c'est à dire :
T(calcul polynomial) = somme (a(k)*N^k) pour k entier
On peut donc classer l'addition et la multiplication (et un grand nombre d'autres calculs) dans l'ensemble des calculs à temps polynomiaux, on appelle cet ensemble P. (le fameux P de P = NP)
Plus précisément, l'ensemble P est appellé "Ensemble des calculs déterministes à temps polynomial", c'est à dire l'ensemble des calculs qui ne font pas appel à des fonctions aléatoires (comme l'addition ou la multiplication)
On devine donc que l'ensemble NP est tout simplement "L'Ensemble des calculs non déterministes à temps polynomial" (et non comme on le croit parfois, "L'ensemble des calculs à temps non polynomial)
Voilà pour la base... Dans la prochaine partie, nous verrons un troisième ensemble et je tenterai de donner une explication concrète du problème P = NP.
A suivre...
vendredi 7 décembre 2007
P = NP : problème ou illusion ?
D'après le livre "Les énigmes mathématiques du 3ème millénaire" (Keith Devlin), le problème P = NP serait, parmi les sept, le problème le plus accessible au commun des mortels, voire, pourquoi pas, le seul problème qu'un non spécialiste pourrait éventuellement résoudre.
Etant moi-même un éminent non-spécialiste, voici ma conception de ce problème et, si on peut dire, la réponse que je pense pouvoir y apporter. Mais avant, je vais tenter de planter le décor, que signifie P = NP ?
Théorie de la complexité
La théorie de la complexité est une méthode qui permet, quel que soit le problème que l'on ait à résoudre, de calculer le temps qu'il faudra pour trouver la ou les réponses.
Plus précisément, on ne calcule pas le temps (en secondes), car cela dépend bien-sûr de la vitesse du calculateur (ordinateur ou humain), mais plutôt le nombre d'opérations simples nécéssaires pour effectuer un calcul.
Qu'est-ce qu'une opération "simple" : en fait, cela n'a pas d'importance, on pourrait prendre n'importe quelle opération comme étant "l'unité". Prenons par exemple une des opérations les plus simples qui existe : l'addition entre deux chiffres décimaux. (nombres compris entre 0 et 9)
Soient A et B deux chiffres compris entre 0 et 9, le calcul de A+B, sans retenue, nécéssite une seule opération, donc le temps T de ce problème est de 1 : T(A+B) = 1
Si l'on souhaite maintenant calculer la somme avec la retenue, il nous faut une opération supplémentaire : T(A+B+R) = 2
Combien de temps faut-il pour calculer la somme de deux nombres décimaux composés chacuns de N chiffres ?
Soient A et B deux nombres décimaux, on note A(n) le n-ième chiffre de A et B(n) celui de B (on prendra n entre 1 et n pour simplifier les formules).
Additionner A et B revient à additionner leurs chiffres respectifs, en ajoutant la retenue précédente, on notera R(n), la retenue de l'opération A(n)+B(n)+R(n-1)
A+B = (A(1)+B(1))*10^0 + (R(1)+A(2)+B(2))*10^1 + ... + (R(n-1)+A(n)+B(n))*10^(n-1) + R(n)*10^n
Autrement dit :
A+B = Somme ((A(k+1)+B(k+1)+R(k))*10^k), pour k allant de 0 à n, avec R(0)=A(n+1)=B(n+1)=0
Comme nous sommes en base 10, l'opération 10^k revient simplement à écrire les chiffres à différents emplacements (unités, dizaines, centaines...), cette partie n'entre donc pas dans le calcul de compexité de A+B.
Pour calculer T(An+Bn), il suffit de compter le nombre d'additions entre deux chiffres, dans la formule ci-dessus : chaque étape comporte 2 additions et il y a (n+1) étapes. La première et la dernière étape, ne comptent qu'une opération, on pourra donc enlever 2 au résultat final, en résumé :
T(An+Bn) = 2*(n+1) - 2 = 2*n
Cette formule signifie que le temps de calcul de l'addition de deux nombres composés de n chiffres est proportionnel à 2 fois le nombre de chiffres.
On dira que l'addition est un calcul à temps (ou à complexité) linéaire : le temps nécéssaire au calcul est proportionnel à la quantité de données en entrée, à un facteur k près. Pour l'addition de deux nombres, nous avons k = 2.
Cet indice k, représente tout simplement le nombre d'opérations nécéssaires à ajouter, à chaque fois que l'on rajoutera une donnée en entrée dans notre calcul (ici, un chiffre de plus à A et B).
Nous allons maintenant calculer la complexité de la multiplication entre deux nombres A et B composés chacuns de n chiffres décimaux : T(An*Bn)
Calculons d'abord la complexité de l'opération T(A*B), soit le cas n = 1 :
A * B = A + A + ... + A
Nous avons ici (B-1) additions, on aurait tout aussi bien pu dire (A-1). D'où :
T(A*B) = k * T(A+B), où k est une valeur qui dépend des données A et B.
Etant moi-même un éminent non-spécialiste, voici ma conception de ce problème et, si on peut dire, la réponse que je pense pouvoir y apporter. Mais avant, je vais tenter de planter le décor, que signifie P = NP ?
Théorie de la complexité
La théorie de la complexité est une méthode qui permet, quel que soit le problème que l'on ait à résoudre, de calculer le temps qu'il faudra pour trouver la ou les réponses.
Plus précisément, on ne calcule pas le temps (en secondes), car cela dépend bien-sûr de la vitesse du calculateur (ordinateur ou humain), mais plutôt le nombre d'opérations simples nécéssaires pour effectuer un calcul.
Qu'est-ce qu'une opération "simple" : en fait, cela n'a pas d'importance, on pourrait prendre n'importe quelle opération comme étant "l'unité". Prenons par exemple une des opérations les plus simples qui existe : l'addition entre deux chiffres décimaux. (nombres compris entre 0 et 9)
Soient A et B deux chiffres compris entre 0 et 9, le calcul de A+B, sans retenue, nécéssite une seule opération, donc le temps T de ce problème est de 1 : T(A+B) = 1
Si l'on souhaite maintenant calculer la somme avec la retenue, il nous faut une opération supplémentaire : T(A+B+R) = 2
Combien de temps faut-il pour calculer la somme de deux nombres décimaux composés chacuns de N chiffres ?
Soient A et B deux nombres décimaux, on note A(n) le n-ième chiffre de A et B(n) celui de B (on prendra n entre 1 et n pour simplifier les formules).
Additionner A et B revient à additionner leurs chiffres respectifs, en ajoutant la retenue précédente, on notera R(n), la retenue de l'opération A(n)+B(n)+R(n-1)
A+B = (A(1)+B(1))*10^0 + (R(1)+A(2)+B(2))*10^1 + ... + (R(n-1)+A(n)+B(n))*10^(n-1) + R(n)*10^n
Autrement dit :
A+B = Somme ((A(k+1)+B(k+1)+R(k))*10^k), pour k allant de 0 à n, avec R(0)=A(n+1)=B(n+1)=0
Comme nous sommes en base 10, l'opération 10^k revient simplement à écrire les chiffres à différents emplacements (unités, dizaines, centaines...), cette partie n'entre donc pas dans le calcul de compexité de A+B.
Pour calculer T(An+Bn), il suffit de compter le nombre d'additions entre deux chiffres, dans la formule ci-dessus : chaque étape comporte 2 additions et il y a (n+1) étapes. La première et la dernière étape, ne comptent qu'une opération, on pourra donc enlever 2 au résultat final, en résumé :
T(An+Bn) = 2*(n+1) - 2 = 2*n
Cette formule signifie que le temps de calcul de l'addition de deux nombres composés de n chiffres est proportionnel à 2 fois le nombre de chiffres.
On dira que l'addition est un calcul à temps (ou à complexité) linéaire : le temps nécéssaire au calcul est proportionnel à la quantité de données en entrée, à un facteur k près. Pour l'addition de deux nombres, nous avons k = 2.
Cet indice k, représente tout simplement le nombre d'opérations nécéssaires à ajouter, à chaque fois que l'on rajoutera une donnée en entrée dans notre calcul (ici, un chiffre de plus à A et B).
Nous allons maintenant calculer la complexité de la multiplication entre deux nombres A et B composés chacuns de n chiffres décimaux : T(An*Bn)
Calculons d'abord la complexité de l'opération T(A*B), soit le cas n = 1 :
A * B = A + A + ... + A
Nous avons ici (B-1) additions, on aurait tout aussi bien pu dire (A-1). D'où :
T(A*B) = k * T(A+B), où k est une valeur qui dépend des données A et B.
A suivre ...
mardi 27 novembre 2007
De l'ordre des nombres ...
Une des activités des mathématiques qui me fascine le plus est l'étude des nombres premiers. Il m'arrive parfois de prendre un carnet, de calculer les nombres premiers dans l'ordre, puis de tracer toutes sortes de représentations graphiques, ou suite logique basée sur les nombres premiers (par exemple une suite composé d'un "0" pour chaque nombre non premier et un "1" pour chaque nombre premier) en espérant pouvoir y déceler une sorte de structure secrète des nombres, voire de l'univers, d'être le MAITRE DU MONDE !!! ... Mais un peu de sérieux.
Malheureusement, comme la plupart de mes tentatives naïves pour trouver une réponse là où les plus grands spécialistes n'ont pas encore trouvé grand chose, cela échoue systématiquement.
Mais avant de vous raconter ma dernière tentative, je tiens d'abord à vous donner deux formules, qui sont parmi les plus belles dans l'étude des nombres premiers.
Le Théorème des Nombres Premiers (TNP)
Il s'agit d'une formule qui permet d'estimer le nombre de nombres premiers (non, ce n'est pas une répétition) inférieurs à un certain nombre. La voici :
PI(n) ~ Li(n)
Ce qui signifie "le nombre de nombres premiers inférieurs à n est environ égal au logarithme intégral de n".
Cette formule permet d'estimer, avec une précision de plus en plus fine au fur et à mesure que n est grand, le nombre de nombres premiers inférieurs à n.
Il est vrai que ce théorème ne donne pas une estimation exacte. Pour obtenir LA formule exacte il faudrait résoudre la "conjecture de Rieman". Je ne vais pas entrer dans les détails (je vous conseille plutôt le livre "Dans la jungle des nombres premiers" de John Derbyshire), mais en résumé : en résolvant cette conjecture, on pourrait (peut-être) découvrir le petit quelque chose qu'il manque pour que le "environ égal" se transforme en "égal" (le "terme correctif", pour les puristes...)
Pour conclure sur ce théorème et sur cette conjecture, l'intérêt de connaître exactement le nombre de nombres premiers inférieurs à n, permettrait de déterminer de manière très simple si un nombre est premier ou pas.
Imaginons qu'on sache calculer PI(n) (le nombre de nombres premiers inférieurs à n), alors pour savoir si n est premier, il suffit de calculer PI(n+1) - PI(n) : si le résultat est un, alors bingo ! n est premier.
La formule d'Euler
zêta(s) = produit(1/(1-p^-s))
Cette formule se lit "zêta de s est égal au produit de un divisé par un moins p à la puissance moins s, pour p parcourant l'ensemble des nombres premiers". Mais avant d'en donner une lecture plus compréhensible, je dois rappeler la définition de la fonction zêta de Rieman (tiens, ce nom m'est familier ?...)
En réalité la fonction zêta de Rieman n'a pas été inventée par Rieman, mais par Euler. Voici cette définition :
zêta(s) = somme(1/n^s)
En français : La fonction zêta est la "somme de 1 sur n à la puissance s, lorsque n parcoure l'ensemble des nombres entiers". Enfin, l'argument de la fonction, "s", est un nombre complexe quelconque différent de 1 (sinon la somme tend vers l'infini et la fonction est indéfinie).
Donc, la puissance de cette formule d'Euler, est de mettre en relation l'ensemble des nombres entiers naturel avec l'ensemble des nombres premiers (le fameux motif que je recherchais aussi naïvement avec mon carnet). Elle est donc à priori la meilleure candidate pour connaître répartition des nombres premiers et pour compléter le TNP.
En réalité, cela s'avère très difficile et on peut dire que l'hypothèse de Rieman consiste en gros, à partir de la formule d'Euler, à compléter le TNP (ou du moins à faire une partie du boulot).
Pour conclure cette première partie, je ne peux pas m'empêcher de citer l'hypothèse de Rieman, qui même si elle n'est qu'une hypothèse, est bien entendu une formule très belle :
Pour tout s!=-2n, zêta(s) = 0 => s = 1/2 + ik
Expliquer cette formule en détail serait trop long, je donnerais simplement cette même hypothèse de Rieman en Français :
"Tout les zéro non triviaux de la fonction zêta se trouvent sur la droite critique du plan complexe y = 1/2"
J'ai bien conscience que présenter tous ces outils sans donner plus d'explication rend la compréhension bien difficile, c'est pourquoi je vous invite à consulter wikipédia ou même à livre ce livre ("Dans la jungle des nombres premiers") pour une avoir une meilleure approche du sujet.
J'ai cependant tenu à présenter d'abord brièvement l'approche "standard" des nombres premiers, qui est certes très prometteuse et très rigoureuse, mais assez peu accessible pour les non spécialistes (comme moi) : la résolution de l'hypothèse de Rieman est d'aileurs l'un des problèmes du millénaire, irrésolu depuis près de deux cent ans ! AI-je une chance avec mon carnet ? ... Après tout j'ai rien d'autre à faire pour l'instant...
Mon approche naïve : Les nombres premiers...oui mais dans quel ordre ?
Cet été, lorsque je m'aventurai "Dans la jungle des nombres premiers", il m'est venu une question un peu stupide :
Plutôt que de s'intéresser uniquement aux nombres premiers, pourquoi ne s'intéresse t'on pas à tous les nombres : les nombres "seconds", les nombres "troisièmes", etc. ?
J'ai donc défini (bien que j'imagine que cette fonction existe déjà quelque part...), ce que j'ai appelé la "fonction d'ordre", que j'appelerai originalement "o".
o(n) est une fonction qui pour un nombre entier donné, nous retourne le nombre de diviseurs premiers qui composent ce nombre. Autrement dit :
o(p) = 1 <=> p est premier
Exemples :
o(2)=1
o(3)=1
o(4)=2 (2 et 2)
o(5)=1
o(6)=2 (2 et 3)
o(7) = 1
o(8) = 3 (2, 2 et encore 2)
...
o(n) = k <=> n à k diviseurs premiers
Est-il possible, en étudiant cette fonction un peu bizarre, non seulement d'étudier la répartition des nombres premiers, mais aussi la répartition de tous les nombres d'ordre 2, 3 ? Peut-être cette fonction a-t'elle une schéma plus simple et cohérent que le schéma chaotique (ou du moins Riemaniesque) de la fonction PI(n) ?
Etant donné qu'il est déjà deux heures du mat' passées et que je dois bosser demain, je me contenterai pour l'instant de donner deux éléments qui pourraient être intéressants sur la fonction d'ordre :
Cette fonction possède les mêmes propriétés qu'une fonction logarithmique, c'est à dire :
o(a*b) = o(a) + o(b)
o(a/b) = o(a) - o(b)
o(a^n) = n*o(a)
...
et bien sûr o(1) = 0 , le nombre 1 ne possédant aucun diviseur premier
enfin, o(0) = infini, puisque 0 est divisible par tous les nombres premiers
Enfin, le dernier élément est un joli graphique, qui montre l'allure de la fonction d'ordre (en bleu) entre 1 et 132 (pourquoi 132 ? et bien parce que j'ai eu la flemme d'aller plus loin...)
Cliquez sur l'image pour l'aggrandir
Lorsque j'ai vu cette courbe, j'ai d'abord pensé à une sorte de fractale et puis j'ai essayé de borner de différentes manières la fonction d'ordre, histoire d'en savoir un peu plus. (courbes en rouge, vert et jaune) Pour la petite histoire, ce magnifique graphique a été réalisé avec le logiciel libre VisualMaths, que vous pouvez télécharger gratuitement sur sourceforge
En travaillant sur ce graphique, j'ai donc essayé de calculer une suite de fonctions qui permettent de majorer la fonction d'ordre à plusieurs niveaux :
La fonction d'ordre atteint un maximum local à chaque fois que n est une puissance de deux : en effet, le plus petit nombre entier ayant k diviseurs premiers n'est autre que 2^k. Avec un peu de calcul, on obtient que la fonction qui majore au mieux o(n) est f2(t) = ln(t)/ln(2), il s'agit de la fonction en
rouge sur le graphique.
Ensuite, si on élimine ces maximums, que reste t'il ? Quels sont les nombres les plus petits, d'ordre k, mais n'étant pas de la forme 2^k ? Les nombres de la forme 3*2^(k-1) (autrement dit, on remplace un deux par un trois)
On obtient alors la fonction f3, qui majore les points restants (en vert) : f3(t) = ln(t/3)/ln(2)+1
Ma supposition est qu'on pourrait (peut-être) trouver une formule générale de la fonction fa (a étant l'indice, nous connaissons déjà f2 et f3).
Je n'ai malheureusement pas encore eu le temps (ou le courage) de creuser cette question, j'ai juste calculé f4 (en orange) :
f4(t) = ln(t/4.5)/ln(2)+1
Il me paraît encore difficile de faire un pronostic sur la généralisation de cette formule, car la fonction f4 par exemple a un gros inconvénient : elle ne majore pas 5 (f4(1) = 4.5). Pourtant elle majore au mieux tout le reste de la fonction d'ordre.
En conclusion, je ne sais pas si cette approche peut réellement m'apporter quelque chose à la compréhension de la répartition des nombres premiers. Mais j'aime assez l'idée d'étudier la fonction d'ordre et peut-être de pouvoir avoir plus d'informations sur la répartition des nombres premiers en étudiant également la répartition des autres nombres.
Je pense en fait que cette approche est un peu similaire à celle du crible d'eratosthène (supprimer tous les nombres divisibles par deux, puis par trois ... afin qu'il ne reste que les nombres premiers). Mais quand on sait que le crible d'érathosthène est un algorithme à temps exponentiel, cela ne présage rien de bon quant à l'efficacité de cette méthode pour étudier les nombres premiers. A moins peut-être de savoir généraliser et utiliser correctement les fonctions que j'ai appelé fa, ou éventuellement de tenter une autre approche sur cette fonction d'ordre.
Si vous n'avez rien, mais vraiement rien d'autre à faire ;) vous pouvez m'envoyer vos tables de la fonction d'ordre pour des valeurs supérieurs à 132, cela me permettra de continuer mon délire...euh je veux dire mon étude !
J'attends aussi vos commentaires sur l'approche "standard", sur mon approche modeste et sur d'autres approches qui pourraient être intéressantes, le but étant d'essayer de trouver l'approche la plus simple sans pour autant qu'elle soit triviale.
Amusez-vous bien et à très bientôt.
Malheureusement, comme la plupart de mes tentatives naïves pour trouver une réponse là où les plus grands spécialistes n'ont pas encore trouvé grand chose, cela échoue systématiquement.
Mais avant de vous raconter ma dernière tentative, je tiens d'abord à vous donner deux formules, qui sont parmi les plus belles dans l'étude des nombres premiers.
Le Théorème des Nombres Premiers (TNP)
Il s'agit d'une formule qui permet d'estimer le nombre de nombres premiers (non, ce n'est pas une répétition) inférieurs à un certain nombre. La voici :
PI(n) ~ Li(n)
Ce qui signifie "le nombre de nombres premiers inférieurs à n est environ égal au logarithme intégral de n".
Cette formule permet d'estimer, avec une précision de plus en plus fine au fur et à mesure que n est grand, le nombre de nombres premiers inférieurs à n.
Il est vrai que ce théorème ne donne pas une estimation exacte. Pour obtenir LA formule exacte il faudrait résoudre la "conjecture de Rieman". Je ne vais pas entrer dans les détails (je vous conseille plutôt le livre "Dans la jungle des nombres premiers" de John Derbyshire), mais en résumé : en résolvant cette conjecture, on pourrait (peut-être) découvrir le petit quelque chose qu'il manque pour que le "environ égal" se transforme en "égal" (le "terme correctif", pour les puristes...)
Pour conclure sur ce théorème et sur cette conjecture, l'intérêt de connaître exactement le nombre de nombres premiers inférieurs à n, permettrait de déterminer de manière très simple si un nombre est premier ou pas.
Imaginons qu'on sache calculer PI(n) (le nombre de nombres premiers inférieurs à n), alors pour savoir si n est premier, il suffit de calculer PI(n+1) - PI(n) : si le résultat est un, alors bingo ! n est premier.
La formule d'Euler
zêta(s) = produit(1/(1-p^-s))
Cette formule se lit "zêta de s est égal au produit de un divisé par un moins p à la puissance moins s, pour p parcourant l'ensemble des nombres premiers". Mais avant d'en donner une lecture plus compréhensible, je dois rappeler la définition de la fonction zêta de Rieman (tiens, ce nom m'est familier ?...)
En réalité la fonction zêta de Rieman n'a pas été inventée par Rieman, mais par Euler. Voici cette définition :
zêta(s) = somme(1/n^s)
En français : La fonction zêta est la "somme de 1 sur n à la puissance s, lorsque n parcoure l'ensemble des nombres entiers". Enfin, l'argument de la fonction, "s", est un nombre complexe quelconque différent de 1 (sinon la somme tend vers l'infini et la fonction est indéfinie).
Donc, la puissance de cette formule d'Euler, est de mettre en relation l'ensemble des nombres entiers naturel avec l'ensemble des nombres premiers (le fameux motif que je recherchais aussi naïvement avec mon carnet). Elle est donc à priori la meilleure candidate pour connaître répartition des nombres premiers et pour compléter le TNP.
En réalité, cela s'avère très difficile et on peut dire que l'hypothèse de Rieman consiste en gros, à partir de la formule d'Euler, à compléter le TNP (ou du moins à faire une partie du boulot).
Pour conclure cette première partie, je ne peux pas m'empêcher de citer l'hypothèse de Rieman, qui même si elle n'est qu'une hypothèse, est bien entendu une formule très belle :
Pour tout s!=-2n, zêta(s) = 0 => s = 1/2 + ik
Expliquer cette formule en détail serait trop long, je donnerais simplement cette même hypothèse de Rieman en Français :
"Tout les zéro non triviaux de la fonction zêta se trouvent sur la droite critique du plan complexe y = 1/2"
J'ai bien conscience que présenter tous ces outils sans donner plus d'explication rend la compréhension bien difficile, c'est pourquoi je vous invite à consulter wikipédia ou même à livre ce livre ("Dans la jungle des nombres premiers") pour une avoir une meilleure approche du sujet.
J'ai cependant tenu à présenter d'abord brièvement l'approche "standard" des nombres premiers, qui est certes très prometteuse et très rigoureuse, mais assez peu accessible pour les non spécialistes (comme moi) : la résolution de l'hypothèse de Rieman est d'aileurs l'un des problèmes du millénaire, irrésolu depuis près de deux cent ans ! AI-je une chance avec mon carnet ? ... Après tout j'ai rien d'autre à faire pour l'instant...
Mon approche naïve : Les nombres premiers...oui mais dans quel ordre ?
Cet été, lorsque je m'aventurai "Dans la jungle des nombres premiers", il m'est venu une question un peu stupide :
Plutôt que de s'intéresser uniquement aux nombres premiers, pourquoi ne s'intéresse t'on pas à tous les nombres : les nombres "seconds", les nombres "troisièmes", etc. ?
J'ai donc défini (bien que j'imagine que cette fonction existe déjà quelque part...), ce que j'ai appelé la "fonction d'ordre", que j'appelerai originalement "o".
o(n) est une fonction qui pour un nombre entier donné, nous retourne le nombre de diviseurs premiers qui composent ce nombre. Autrement dit :
o(p) = 1 <=> p est premier
Exemples :
o(2)=1
o(3)=1
o(4)=2 (2 et 2)
o(5)=1
o(6)=2 (2 et 3)
o(7) = 1
o(8) = 3 (2, 2 et encore 2)
...
o(n) = k <=> n à k diviseurs premiers
Est-il possible, en étudiant cette fonction un peu bizarre, non seulement d'étudier la répartition des nombres premiers, mais aussi la répartition de tous les nombres d'ordre 2, 3 ? Peut-être cette fonction a-t'elle une schéma plus simple et cohérent que le schéma chaotique (ou du moins Riemaniesque) de la fonction PI(n) ?
Etant donné qu'il est déjà deux heures du mat' passées et que je dois bosser demain, je me contenterai pour l'instant de donner deux éléments qui pourraient être intéressants sur la fonction d'ordre :
Cette fonction possède les mêmes propriétés qu'une fonction logarithmique, c'est à dire :
o(a*b) = o(a) + o(b)
o(a/b) = o(a) - o(b)
o(a^n) = n*o(a)
...
et bien sûr o(1) = 0 , le nombre 1 ne possédant aucun diviseur premier
enfin, o(0) = infini, puisque 0 est divisible par tous les nombres premiers
Enfin, le dernier élément est un joli graphique, qui montre l'allure de la fonction d'ordre (en bleu) entre 1 et 132 (pourquoi 132 ? et bien parce que j'ai eu la flemme d'aller plus loin...)
Cliquez sur l'image pour l'aggrandir
Lorsque j'ai vu cette courbe, j'ai d'abord pensé à une sorte de fractale et puis j'ai essayé de borner de différentes manières la fonction d'ordre, histoire d'en savoir un peu plus. (courbes en rouge, vert et jaune) Pour la petite histoire, ce magnifique graphique a été réalisé avec le logiciel libre VisualMaths, que vous pouvez télécharger gratuitement sur sourceforge
En travaillant sur ce graphique, j'ai donc essayé de calculer une suite de fonctions qui permettent de majorer la fonction d'ordre à plusieurs niveaux :
La fonction d'ordre atteint un maximum local à chaque fois que n est une puissance de deux : en effet, le plus petit nombre entier ayant k diviseurs premiers n'est autre que 2^k. Avec un peu de calcul, on obtient que la fonction qui majore au mieux o(n) est f2(t) = ln(t)/ln(2), il s'agit de la fonction en
rouge sur le graphique.
Ensuite, si on élimine ces maximums, que reste t'il ? Quels sont les nombres les plus petits, d'ordre k, mais n'étant pas de la forme 2^k ? Les nombres de la forme 3*2^(k-1) (autrement dit, on remplace un deux par un trois)
On obtient alors la fonction f3, qui majore les points restants (en vert) : f3(t) = ln(t/3)/ln(2)+1
Ma supposition est qu'on pourrait (peut-être) trouver une formule générale de la fonction fa (a étant l'indice, nous connaissons déjà f2 et f3).
Je n'ai malheureusement pas encore eu le temps (ou le courage) de creuser cette question, j'ai juste calculé f4 (en orange) :
f4(t) = ln(t/4.5)/ln(2)+1
Il me paraît encore difficile de faire un pronostic sur la généralisation de cette formule, car la fonction f4 par exemple a un gros inconvénient : elle ne majore pas 5 (f4(1) = 4.5). Pourtant elle majore au mieux tout le reste de la fonction d'ordre.
En conclusion, je ne sais pas si cette approche peut réellement m'apporter quelque chose à la compréhension de la répartition des nombres premiers. Mais j'aime assez l'idée d'étudier la fonction d'ordre et peut-être de pouvoir avoir plus d'informations sur la répartition des nombres premiers en étudiant également la répartition des autres nombres.
Je pense en fait que cette approche est un peu similaire à celle du crible d'eratosthène (supprimer tous les nombres divisibles par deux, puis par trois ... afin qu'il ne reste que les nombres premiers). Mais quand on sait que le crible d'érathosthène est un algorithme à temps exponentiel, cela ne présage rien de bon quant à l'efficacité de cette méthode pour étudier les nombres premiers. A moins peut-être de savoir généraliser et utiliser correctement les fonctions que j'ai appelé fa, ou éventuellement de tenter une autre approche sur cette fonction d'ordre.
Si vous n'avez rien, mais vraiement rien d'autre à faire ;) vous pouvez m'envoyer vos tables de la fonction d'ordre pour des valeurs supérieurs à 132, cela me permettra de continuer mon délire...euh je veux dire mon étude !
J'attends aussi vos commentaires sur l'approche "standard", sur mon approche modeste et sur d'autres approches qui pourraient être intéressantes, le but étant d'essayer de trouver l'approche la plus simple sans pour autant qu'elle soit triviale.
Amusez-vous bien et à très bientôt.
Inscription à :
Articles (Atom)