Peut-on "brute forcer" des formules mathématiques ?

[Meiosis]

Bonjour,

J'ai une question qui va peut-être vous sembler naïve mais j'aimerais bien obtenir une réponse.
Est-il possible de "brute forcer" des formules mathématiques ? C'est-à-dire lancer des ordinateurs très puissants qui testeraient plusieurs millions de formules possibles jusqu'à trouver la formule recherchée.
De l'autre côté l'expérimentateur va dire à l'ordinateur le résultat attendu.
Si la formule trouvée par l'ordinateur colle avec le résultat attendu (il y aurait un pourcentage de correspondance, par exemple 100% ou 99% peut être très bien) alors la formule serait retenue par l'ordinateur.
Ensuite l'expérimentateur regarde la ou les formules retenues et choisit celle qui convient le mieux.

Puis ensuite il y aurait des études faites sur la formule retenue.

En gros on raisonnerait à l'inverse de ce qui se fait actuellement : c'est-à-dire qu'au lieu de partir avec un crayon/stylo et essayer de trouver la formule en introduisant de nouveaux outils, on partirait de la formule trouvée grâce à un ordi et ensuite on essayerait de voir ce qui se cache derrière la formule, comment on aurait pu la trouver sans partir de l'ordi (et donc trouver les outils mathématiques à partir de la formule).

Je vais prendre un exemple simple : une formule qui permettrait de déterminer le n-ième nombre premier.
L'expérimentateur va dire ce qu'il attend de l'ordi : ici on attend que pour n=1 on ait 2, pour n=2 on ait 3, pour n=3 on ait 5 etc.
Ce qui suppose de connaître un grand nombre de nombres premiers et ça tombe bien car on en connait déjà beaucoup.
L'ordinateur va commencer par étudier le cas le plus simple : "n", bien entendu il va voir que ça ne correspond pas et va supprimer la formule pour en tester une autre qui sera par exemple "n+1".

Pour éviter de traiter des cas inutiles (on sait que n, 2n ou n+1 ne marchera jamais par exemple) on pourrait même renseigner à l'ordi de ne pas traiter certains cas.

Bref je ne sais pas si de tels procédés sont déjà utilisés ou si c'est impossible pour diverses raisons.

Bien entendu ça ne marche pas pour les démos, là il faut un raisonnement humain.

Le terme de "brute force" est dérivé de ce qui se fait parfois pour trouver un mot de passe, un programme en teste des millions jusqu'à trouver le bon mot de passe. Par contre quand le mot de passe est trop compliqué il ne trouve pas.
C'est pour cela que je pense que ce ne serait pas possible non plus pour trouver des formules.

Merci pour vos réponses.
-----

[gg0]

Bonjour.

Voir "théorème des 4 couleurs".

[geometrodynamics_of_QFT]

Salut,

ça me parait une bonne idée, mais ça peinerait un peu si la formule contient autre chose que des opérations symboliques...comme par exemple des facteurs numériques. S'il faut tous les tester pour une formule donnée, cela fait une infinité de cas à tester par formule et par facteur numérique dans la formule...(l'ensemble des réels)
A moins, toujours dans l'idée, de restreindre l'ensemble des facteurs numériques envisagés à des valeurs "courantes" (fractions de petits entiers, nombres transcendants, ...)

Par un exemple absurde, si on teste la formule pour le nième nombre premier P(n)=An^2+B, il faut la tester pour toutes les valeurs possibles de A et B...

[geometrodynamics_of_QFT]

Mais il serait intéressant de former une sorte d'arbre avec tous les symboles possibles et opérations, et de tester, pour un nombre croissant donné N de tels symboles, toutes les permutations possibles N!.
On trouverait par exemple facilement la formule d'Euler : A.cos (B.x) + C.i.sin(D.x) = exp(E.i.x), ne faisant intervenir que 18 symboles (A=B=C=D=E=1, cos(), sin(), i, exp(), +, =, *, *, *, *, *, *, *).
A raison de 6 milliards de permutations (6 milliards d'arrangements de ces 18 symboles) testées par seconde, il ne faudrait que 11 jours maximum pour tomber sur la formule lol
Mais de nouveau, uniquement si on fixe les 6 facteurs numériques à 1...car si on doit tester toutes les valeurs possibles, on est pas sorti de l'auberge...

[A voir en vidéo sur Futura]

[Médiat]

Bonjour

Par un exemple absurde, si on teste la formule pour le nième nombre premier P(n)=An^2+B, il faut la tester pour toutes les valeurs possibles de A et B...

Non,

Il faut P(1) = 1, P(2) = 3 et P(3) = 5, ce qui est impossible!

[Meiosis]

Pour le théorème des 4 couleurs apparemment selon wikipedia c'est carrément le théorème qui a été prouvé par l'informatique, du coup c'est intéressant.

Salut,

ça me parait une bonne idée, mais ça peinerait un peu si la formule contient autre chose que des opérations symboliques...comme par exemple des facteurs numériques. S'il faut tous les tester pour une formule donnée, cela fait une infinité de cas à tester par formule et par facteur numérique dans la formule...(l'ensemble des réels)
A moins, toujours dans l'idée, de restreindre l'ensemble des facteurs numériques envisagés à des valeurs "courantes" (fractions de petits entiers, nombres transcendants, ...)

Par un exemple absurde, si on teste la formule pour le nième nombre premier P(n)=An^2+B, il faut la tester pour toutes les valeurs possibles de A et B...

Effectivement c'est ce qui pose problème (l'autre problème étant qu'une telle formule pourrait ne tout simplement pas exister) mais il se peut qu'il existe plusieurs facteurs numériques valables donc plusieurs formules existant pour le même problème, ce qui faciliterait la tâche (même si "plusieurs" ce n'est rien face à l'infini).
On peut également se servir de formules déjà existantes (approximatives pour la plupart) pour imposer à l'ordinateur de rechercher dans une certaine direction avec ces facteurs numériques.

Il est également peut-être possible de trouver d'autres formules "par hasard" si on fixe d'autres conditions moins contraignantes (et non plus comme condition d'obtenir le nième nombre premier).

[Médiat]

De plus si on cherche une formule qui donne tous les nombres premiers connus aujourd'hui, on trouvera "facilement" un polynôme d'une variable), un peu moins facilement un paramétrage de la fonction béta de Gödel, mais RIEN (à ce point) ne prouvera que ces formules aient la moindre valeur ou la moindre utilité.

[Meiosis]

De plus si on cherche une formule qui donne tous les nombres premiers connus aujourd'hui, on trouvera "facilement" un polynôme d'une variable), un peu moins facilement un paramétrage de la fonction béta de Gödel, mais RIEN (à ce point) ne prouvera que ces formules aient la moindre valeur ou la moindre utilité.

Rien ne prouvera la valeur de ces formules car pour de plus grands nombres premiers cela pourrait commencer à ne plus marcher, c'est bien cela ?

Mais au moins on aurait une formule qui marche pour tout ce qu'on connait (jusqu'au plus grand nombre premier), et il serait peut-être possible de la prouver ensuite "manuellement" pour tout n entier naturel, non ?

[Médiat]

Pour le théorème des 4 couleurs apparemment selon wikipedia c'est carrément le théorème qui a été prouvé par l'informatique,

Il serait plus juste de dire que ce théorème a été démontré par Appel et Haken qui ont utilisé un ordinateur pour faire certains calculs.

[Médiat]

Rien ne prouvera la valeur de ces formules car pour de plus grands nombres premiers cela pourrait commencer à ne plus marcher, c'est bien cela ?

Oui

Mais au moins on aurait une formule qui marche pour tout ce qu'on connait (jusqu'au plus grand nombre premier), et il serait peut-être possible de la prouver ensuite "manuellement" pour tout n entier naturel, non ?

Peu de chance, un polynôme d'une variable ne peut convenir (les nombres premiers seraient "trop bien" distribués)

[Meiosis]

Je vois mais si ça marche jusqu'au plus grand nombre premier qu'on connaisse il y a de fortes chances de trouver au moins les 10 prochains, non ?

[Médiat]

A mon avis, même pas.

[Meiosis]

Avez-vous une idée du pourquoi ?

Si vous avez un outil permettant de générer un tel polynôme pour avoir les nombres premiers actuellement connus je suis également intéressé.

Merci.

[geometrodynamics_of_QFT]

Voici un polynôme de degré 25 dont les valeurs prises qui sont strictement positives sont l'ensemble des nombres premiers...lol

Je ne suis pas prêt de m'en remettre, de l'existence d'un tel polynôme, ni que ça reste une curiosité mathématique plutôt que le chemin du Grââl...

[geometrodynamics_of_QFT]

Quelqu'un s'est-il déjà amusé à "jouer" à inventer des combinaisons linéaires avec les 26 paramètres, afin de trouver peut-être une expression plus simple, qui renseignera peut-être davantage sur la structure de la distribution des nombres premiers...?

[Meiosis]

Effectivement je l'avais déjà vu ce polynôme à 26 variables. Mais d'après Médiat il serait même possible d'en trouver un à une seule variable, ce qui est intéressant.

Peut-être moins en pratique car ça ne servirait pas pour trouver des nombres premiers qu'on ne connait pas encore. Peut-être parce qu'en tenant compte de l'ensemble des nombres premiers déjà connu on ne pourrait pas trouver le suivant, même si on a un très très grand échantillon pour le coup.

Un peu comme si on disposait de 2, 3, 5 et 7, on ne pourrait avoir 11.

[geometrodynamics_of_QFT]

Attention tout de même que le polynôme ici fournit TOUS les nombres premiers, même ceux qu'on ne connait pas, pourvu que le jeu des 25 paramètre fasse en sorte que l'évaluation du polynôme soit un nombre positif (qui est le nombre premier en question)

[Meiosis]

C'est vrai, c'est pour cela qu'il est mentionné sur wikipedia d'ailleurs. Mais pour trouver les combinaisons possibles ça a l'air vraiment chaud. Et d'ailleurs ça renvoie à ce sujet. Du coup je pense que c'est peine perdu d'essayer comme ça.

Je reste tout de même étonné d'un polynôme à une seule variable avec tout ce qu'on connait.

[geometrodynamics_of_QFT]

Il y a un autre truc marrant avec les gaps entre nombres premiers :

Soit N, un nombre entier.

Alors, N!+2 n'est pas premier, N!+3 n'est pas premier, ...N!+N n'est pas premier.
Donc entre N!+1 et N!+N, il n'y a pas de nombres premiers, donc un gap de longueur ~N.

Ce qui est vertigineux, c'est que N peut être...n'importe quel entier je veux dire surtout...aussi grand qu'on veut.

Donc on sait qu'il existe des gaps d'une longueur arbitrairement longue entre deux nombres premiers...

[geometrodynamics_of_QFT]

C'est vrai, c'est pour cela qu'il est mentionné sur wikipedia d'ailleurs. Mais pour trouver les combinaisons possibles ça a l'air vraiment chaud. Et d'ailleurs ça renvoie à ce sujet. Du coup je pense que c'est peine perdu d'essayer comme ça..

Oui en effet ^^

[geometrodynamics_of_QFT]

Je reste tout de même étonné d'un polynôme à une seule variable avec tout ce qu'on connait.

Moi à moitié, c'est un peu le principe de l'interpolation...aucune valeur prédictive, c'est juste un "fit" par des points connus.

[Meiosis]

Il y a un autre truc marrant avec les gaps entre nombres premiers :

Soit N, un nombre entier.

Alors, N!+2 n'est pas premier, N!+3 n'est pas premier, ...N!+N n'est pas premier.
Donc entre N!+1 et N!+N, il n'y a pas de nombres premiers, donc un gap de longueur ~N.

Ce qui est vertigineux, c'est que N peut être...n'importe quel entier je veux dire surtout...aussi grand qu'on veut.

Donc on sait qu'il existe des gaps d'une longueur arbitrairement longue entre deux nombres premiers...

Concernant ce résultat ce n'est pas celui récemment prouvé par Tao en 2004 ?

Sinon on sait aussi qu'il y a au moins un nombre premier entre n et 2n.

On voit bien qu'il y a plusieurs résultats concernant la distribution des nombres premiers et personne ne sait trouver le fil conducteur. Ces différents résultats pourraient être mis sur ordinateur pour orienter la recherche d'une formule mais il faudrait déjà qu'une telle formule existe.
D'après wikipedia (page formules pour les nombres premiers, premier paragraphe) il n'existerait aucun polynôme ne comprenant que des valeurs premières.
Donc si on peut trouver un polynôme à une variable renfermant tous les nombres premiers actuellement connus alors ça ne marcherait plus ensuite : à partir de quand on ne sait pas.

[Meiosis]

Moi à moitié, c'est un peu le principe de l'interpolation...aucune valeur prédictive, c'est juste un "fit" par des points connus.

Oui en effet, même si l'échantillon est très grand.
Le plus chiant c'est bien de rentrer les valeurs déjà connues et faire fonctionner la machine en fait.

Mais je parlais bien d'une formule qui ne s'appuierait pas sur un fit.

[geometrodynamics_of_QFT]

Concernant ce résultat ce n'est pas celui récemment prouvé par Tao en 2004 ?

Non, je crois que Tao lui s'est penché sur les "small gaps between primes", et a trouvé, avec les autres de polymath, une manière de réduire le X dans "il existe une infinité de paires de nombres premiers (twin primes) dont le gap est égal à X". (si je ne me trompe pas)

Ici, c'est un résultat abolissant la limite supérieure pour un gap possible entre deux nombres premiers.

Donc si on peut trouver un polynôme à une variable renfermant tous les nombres premiers actuellement connus alors ça ne marcherait plus ensuite : à partir de quand on ne sait pas.

Si, pour moi on sait : on pourra toujours obtenir un polynôme à une variable dont les valeurs prises sont l'ensemble des nombres premiers connus (ou même, n'importe quel ensemble de nombres entiers, que ça soit l'ensemble des premiers ou pas...)
Comme je disais, aucun pouvoir prédictif dans l'interpolation : tu peux faire passer un polynôme de degré N à travers N+1 points assez facilement...

[Meiosis]

Non, je crois que Tao lui s'est penché sur les "small gaps between primes", et a trouvé, avec les autres de polymath, une manière de réduire le X dans "il existe une infinité de nombres premiers dont le gap est inférieur à X".

Ici, c'est un résultat abolissant la limite supérieure pour un gap possible entre deux nombres premiers.

Ok merci.

Si, pour moi on sait : on pourra toujours obtenir un polynôme à une variable dont les valeurs prises sont l'ensemble des nombres premiers connus (ou même, n'importe quel ensemble de nombres entiers, que ça soit l'ensemble des premiers ou pas...)
Comme je disais, aucun pouvoir prédictif dans l'interpolation : tu peux faire passer un polynôme de degré N à travers N+1 points assez facilement...

Je parlais d'un polynôme à une variable ne comprenant que des valeurs premières et rien d'autre, d'après wikipedia c'est impossible (pour des valeurs entières de n dans ce polynôme donc pour la formule qu'on souhaite vu que n doit être entier : n=1, n=2 etc.).
Donc si un tel polynôme n'existe pas mais qu'on en trouve un pour tous les nombres premiers actuellement connus (sans lien avec un quelconque fit, une "vraie" formule je veux dire) alors c'est que forcément ça ne marchera plus un moment donné.

[geometrodynamics_of_QFT]

Ok merci.

Il ont en fait travaillé sur la conjecture des nombres premiers jumeaux...

Je parlais d'un polynôme à une variable ne comprenant que des valeurs premières et rien d'autre, d'après wikipedia c'est impossible (pour des valeurs entières de n dans ce polynôme donc pour la formule qu'on souhaite vu que n doit être entier : n=1, n=2 etc.).
Donc si un tel polynôme n'existe pas mais qu'on en trouve un pour tous les nombres premiers actuellement connus (sans lien avec un quelconque fit, une "vraie" formule je veux dire) alors c'est que forcément ça ne marchera plus un moment donné.

Ok j'avais mal compris...

Mais ce qui me trouble aussi, c'est que on connait peut-être des très grands nombres premiers, mais pas tous ceux qui existent avant le plus grand qu'on connaisse...
donc à quoi bon faire un polynôme qui passe par tous ceux qu'on connaisse, s'il en omet de toute façon?
Je veux dire, on ne découvre pas les nombres premiers par ordre croissant...le prochain qui sera découvert ne sera pas celui qui est "juste après" le dernier plus grand qu'on a découvert, dans la suite des nombres premiers...enfin tu vois ce que je veux dire...

Pour moi il fut se concentrer sur la distribution de l'ensemble des nombres premiers...se concentrer uniquement sur ceux qu'on connait, ça me semble futile...

[Meiosis]

En effet dans mon esprit tous les nombres premiers qu'on connait se suivaient, je n'avais pas pensé au fait que plusieurs n'ont pas été découverts avant le plus grand actuellement connu.

Mais si un tel polynôme est trouvé alors il permettrait tout de même de découvrir d'autres nombres premiers plus grands, même si ce n'est pas celui juste après et que ce n'est pas dans l'ordre (du coup ce ne serait plus le nième nombre premier mais ce serait toujours fort intéressant).

[geometrodynamics_of_QFT]

Oui mais je crois aussi qu'un tel polynôme (une variable, degré N) interpolant N points connus (les N nombres premiers connus), et bien ça correspond (ou est lié) justement à ses N racines...enfin il y a une bijection. Du coup, aucune chance, d'après le théorème fondamental de l'algèbre, que ce polynôme "passe" aussi par des nombres premiers qu'on aurait pas encore découverts

Mais je ne suis pas sûr de ce que j'avance, et je ne sais pas comment est construit ce polynôme en question...

[Meiosis]

Ce qui est sûr en tout cas c'est que ce polynôme ne passerait pas que par des nombres premiers, du coup même s'il en sort qu'on ne connait pas encore il faudra trier parmi les non-premiers et les premiers.
S'il y a plusieurs millions de non-premiers pour 1 premier ça va être compliqué.

De toute façon c'est hypothétique car il faudrait déjà découvrir un tel polynôme.

[geometrodynamics_of_QFT]

S'il y a plusieurs millions de non-premiers pour 1 premier ça va être compliqué.

On sait depuis le 19ème siècle ce qu'on appelle le théorème des nombres premiers, qui dit que le nombre de nombres premiers inférieurs ou égaux à x est noté et vaut asymptotiquement , c'est-à-dire que AU MOINS un nombre sur 60 est un nombre premier, jusqu'à 10^26.
(1 nombre sur 4 est premier jusqu'à 100 : 100/ln(100)~25)