hardyC’est l’histoire d’un physicien à qui on demande d’étudier la conjecture

« Tout nombre impair est un nombre premier. »

Il commence donc à regarder les nombres impairs les uns après les autres :

1 : ok.     3 : ok.    5 : ok.     7 : ok.    9 : …hum.     11 : ok.    

13 : ok.     15 : …euh.     17 : ok.     19 : ok.

Et le physicien finit par conclure :

« La conjecture est vraie; …en première approximation. »

Au-delà du fait que cette conjecture est évidemment carrément fausse, cette histoire illustre le fait qu’en mathématiques il n’y a pas de demi-mesure : soit une conjecture est vraie pour ABSOLUMENT TOUS les nombres, soit elle est fausse ! Un seul contre-exemple suffit pour démolir l’édifice.

Et pourtant aujourd’hui nous allons parler d’une conjecture un peu étrange : la deuxième conjecture de Hardy-Littlewood. Personne n’en a jamais trouvé de contre-exemple, et malgré cela les spécialistes sont convaincus qu’elle est fausse ! Mais le premier contre-exemple est attendu fabuleusement loin, au point qu’on estime que la conjecture est vraie jusqu’à au moins 10 puissance 174 !

L’énoncé de la conjecture

Si vous vous amusez à regarder une liste de nombres premiers, vous devez vous apercevoir d’une chose : il y en a de moins en moins. Plus vous allez vers des valeurs élevées, plus les nombres premiers se raréfient. On peut même mesurer ce phénomène et constater que la proportion de nombres premiers aux environs de N est de l’ordre de \(1/log(N)\).

Un cas particulier de cette raréfaction, c’est que si vous comptez les nombres premiers entre 0 et N, il semble y en avoir toujours plus (ou autant) que dans n’importe quel intervalle de longueur N situé plus loin. Et c’est cela qu’on appelle la deuxième conjecture de Hardy-Littlewood.

hl2

On peut écrire la conjecture plus formellement. Si \(\Pi(N)\) désigne la quantité de nombres premiers entre 0 et N, alors pour tout M et tout N supérieurs à 2 :

\(\Pi(M+N) – \Pi(M) \leq \Pi(N)\)

[une autre manière de le dire, c’est d’affirmer que la fonction \(\Pi()\) est ce qu’on appelle « sous-additive » puisqu’on a alors \(\Pi(M+N) \leq \Pi(M) + \Pi(N)\).]

Voilà, c’est une conjecture. Il faut donc essayer de savoir si elle est vraie ou fausse !

Vérifier la conjecture par ordinateur

Quand on fait des conjectures en arithmétique, il est assez pratique d’essayer de les vérifier par ordinateur aussi loin qu’on le peut. Par exemple dans un billet précédent, j’ai eu l’occasion de vous parler de la célèbre conjecture de Goldbach, qui affirme que tout nombre pair peut toujours s’écrire comme somme de deux nombres premiers.

Personne n’a jamais trouvé de démonstration de cette conjecture, mais par ordinateur on a pu vérifier qu’elle était correcte jusqu’à au moins \(10^{20}\). Du coup tous les mathématiciens s’accordent à penser qu’elle est vraie et qu’il doit donc bien en exister une démonstration. Il se passe d’ailleurs exactement la même chose pour une autre conjecture célèbre : la conjecture dite de Syracuse.

Alors qu’en est-il pour la conjecture de Hardy-Littlewood ?

Commençons petit joueur : si vous avez accès à une liste de nombre premiers, vous pouvez faire quelques expériences numériques. Par exemple il y a 25 nombres premiers entre 0 et 100. Il n’y en a que 16 entre 1100 et 1000, et plus que 6 entre 100100 et 100000. (Wolfram Alpha fait ça très bien aussi) La conjecture marche bien sur ces exemples.

Si vous savez un peu coder, vous pouvez facilement programmer un test numérique de la conjecture. J’ai écrit un petit code en C qui vérifie en moins de 10 minutes que la conjecture est vraie pour (M+N) inférieur à 1 million. (J’ai aussi écrit un code en Python qui fait la même chose en 24 heures.)

Je n’ai pas pu trouver dans la littérature jusqu’à quelle valeur la seconde conjecture de Hardy-Littlewood a été vérifiée numériquement, mais à ce jour aucun contre-exemple n’a jamais été trouvé !

Existe-t-il un contre-exemple ?

Pourtant pour invalider la conjecture, c’est pas compliqué ! Il suffit de trouver une seule valeur de N et une seule valeur de M telles qu’il y ait plus de nombres premiers entre M et M+N qu’entre 0 et N.

Comme pour Syracuse ou Goldbach, si on ne trouve aucun contre-exemple jusqu’à des nombres astronomiques, le bon sens pousserait à considérer que la deuxième conjecture de Hardy-Littlewood doit être vraie elle aussi.

Et pourtant les mathématiciens spécialistes du sujet sont convaincus qu’elle est fausse et qu’un contre exemple doit exister. Et d’après leurs estimations, le premier contre-exemple doit se situer quelque part entre \(10^{174}\) et \(10^{1198}\) !

Mais qu’est-ce qui leur permet de penser cela ?  Eh bien c’est ce qu’on appelle la première conjecture de Hardy-Littlewood.

En effet dans leur article de 1923 [1], les mathématiciens John Littlewood et Godfrey Hardy n’ont pas seulement énoncé la conjecture que je viens de vous présenter — qu’on appelle la « deuxième » –, mais ils en ont proposé une autre ! Les deux conjectures leurs semblaient raisonnables, et ils pensaient donc qu’elles étaient toutes les deux vraies.

Mais pas de bol, en 1974 un petit malin nommé Ian Richards a montré que les deux conjectures sont incompatibles ! Si l’une est vraie, l’autre est obligatoirement fausse [2]. Et pour diverses raisons les chercheurs du sujet pensent que c’est la première qui est vraie, et donc que la deuxième est nécessairement fausse.

La semaine prochaine je vous parlerai donc de cette première conjecture de Hardy-Littlewood, et de comment on peut s’en servir pour espérer trouver un contre-exemple à la deuxième.

UPDATE : la suite ici avec la première conjecture de Hardy-Littlewood

Billets reliés


Références

[1] Hardy, Godfrey H., and John E. Littlewood. « Some problems of ‘Partitio numerorum’; III: On the expression of a number as a sum of primes. » Acta Mathematica 44.1 (1923): 1-70.

[2] Richards, Ian. « On the incompatibility of two conjectures concerning primes; a discussion of the use of computers in attacking a theoretical problem. » Bull. Amer. Math. Soc 80 (1974).

Crédits

G. Hardy, Wikimedia Commons

Mes remerciements à Pierre Dusart de l’Université de Limoges qui a travaillé sur le sujet il y a quelques années et a gentiment répondu à une de mes questions sur le sujet, ainsi qu’à Tomas Oliveira e Silva de l’université d’Aveiro au Portugal, et qui est un des spécialistes mondiaux de la vérification numérique des conjectures arithmétiques.

23 Comments

  1. Flavien Fremy Reply

    Le papier de 1974 est étonnamment agréable à lire 🙂
    Encore un article tip-top.

  2. Super intéressant. Juste pour nuancer le côté « absolu » des conjectures mathématiques, il existe aussi des conjectures indécidables, ni vraies ni fausses (par exemple « l’hypothèse du continu » qui suppose qu’il n’existe pas d’ensemble « plus grand que » celui des entiers mais plus petit que celui des réels) dans notre système axiomatique… Bon c’était juste pour faire mon pédant, tu connais le cas bien sûr 😉

    • On ne parle, en général, pas de « conjecture indécidable », mais plutôt de « proposition indécidable ». Avant Paul Cohen, qui a démontré l’indépendance de l’hypothèse du continu, les mathématiciens étaient prudents et ne parlaient que d’hypothèse, ne sachant de quel côté le fléau allait pencher. En fait, il n’a pas penché du tout. Cependant l’hypothèse du continu est une proposition de la théorie des ensembles, or la conjecture de Hardy-Littelwood est une proposition de l’arithmétique qui n’est pas la même théorie mathématique (autrement dit qui n’a pas les mêmes axiomes). Comme l’indécidabilité d’une proposition veut dire que ni la proposition, ni sa négation ne sont démontrables, la théorie axiomatique dont on parle joue un rôle essentiel.

      Tout ça pour dire que la conjecture n’a pas, me semble-t-il, l’allure d’une proposition indécidable de l’arithmétique. Les logiciens savent dirent des choses là-dessus.

      • David Reply

        Oui je suis toujours troublé quand il s’agit de raisonner sur des propositions indécidables de l’arithmétique (et pourtant bien sûr il en existe.) Et j’ai envie de penser que les propositions de ce genre doivent être déjà relativement sophistiquées.

        Je me demande s’il existe des propositions arithmétiques indécidables ayant la forme simple « pour tout n, la propriété P(n) est vraie » ? Ca parait possible, mais paradoxalement cela me semble impliquer qu’une proposition indécidable de ce genre est nécessairement vraie.

        En effet si cette proposition est fausse, alors il existe n0 tq P(n0) est faux. Mais si elle est indécidable, cela veut dire qu’on peut l’ajouter sans danger aux axiomes de l’arithmétique. Et là j’ai du mal à voir comment on peut ajouter « pour tout n, la propriété P(n) est vraie » comme axiome, sachant que dans le même temps on peut exhiber explicitement un n0 tel que P(n0) est faux !

        Bref des propositions indécidables mais fausses me semblent forcément devoir faire appel à des quantifications d’ordre supérieur du genre « pour toute propriété P », etc.

      • C’est exactement ça, les propositions indécidables de l’arithmétique ne peuvent pas être de la forme « pour tout n, la propriété P(n) est vraie » pourvu que P(n) ne soit pas trop compliqué. En revanche, elle n’ont pas besoin de quantification d’ordre supérieure et c’est ce que dit le théorème de Gödel : dès qu’on fait de l’arithmétique on rencontre des propositions indécidables.

        J’en connais deux.

        * Le première qui peut être créée dans toute théorie de l’arithmétique (cohérente) est une proposition qui parle d’elle-même et dit « Je ne suis pas démontrable ». Gödel a pu coder cette préposition (c’est son tour de force) comme une proposition de l’arithmétique.

        * La seconde est l’arrêt des suites de Goodstein et pourrait donner lieu à une rubrique dans science étonnante. Alors qu’elle est énoncée dans l’arithmétique ordinaire ou arithmétique de Peano, elle ne peut-être démontrée que dans l’arithmétique d’ordre supérieur ou dans la théorie des ensembles encore plus forte (voir la rubrique http://sciencetonnante.wordpress.com/2014/04/28/quel-est-le-plus-grand-nombre-possible-utile/).

        La conjecture de Hardy-Littlewood est énoncée dans l’arithmétique de Peano et elle ou sa négation devrait y être démontrée.

      • La conjecture relative aux suites de Goodstein est précisément une conjecture (un théorème, en fait) de la forme dont parle David : « Pour tout entier naturel n, P(n) », où P(n) signifie que la suite de Goodstein issue de n s’arrête, ce qui est un énoncé simple. Cette conjecture est vraie, facilement démontrable avec quelques ordinaux, tout en étant indécidable à partir des seuls axiomes de Peano.

  3. Un par semaine, c’est vraiment prendre un malin plaisir à faire mourir d’impatience les pauvres lecteurs…

    • David Reply

      Ca n’est pas par sadisme !

      D’une part en regroupant les deux, ça aurait fait un billet un peu long; d’autre part celui de la semaine prochaine risque de piquer un peu plus les yeux (ou les neurones) !

  4. Boris El Tsing Reply

    Y’en a un qui disait que si on était pas capable d’expliquer qqchose à un enfant de 6 ans, c’est qu’on ne maîtrisait pas son sujet.
    Celui de la semaine prochaine risque de piquer un peu plus les yeux? Je vais commencer par relire celui là quand je serai un peu plus tranquille…

  5. liemmerle Reply

    sinon, pour N = 1 et M = 2 ;
    on a dans l’intervalle aucun nombre premier entre 0 et 1 (0 et 1 inclus), mais deux entre 2 et 3 (2 et 3 inclus), non ?

  6. « Soit une conjecture est vraie pour ABSOLUMENT TOUS les nombres, soit elle est fausse ! Un seul contre-exemple suffit pour démolir l’édifice. »

    Tu ne parles là que des conjectures du type « pour tout entier n, A(n) ». C’est très réducteur !

  7. Pingback: La première conjecture de Hardy-Littlewood | Science étonnante

  8. Voici des résultats donnés par Tony Forbes.
    Por , par exemple, une constellation (M,N,k) (de k=14 nombres premiers nous trouvons que N = 50 et que cela peut commencer par M = 11 : 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, ce sont des résidus différents modulo 210 (=2*3*5*7). Mais pi(50) = 15 > 14. Mais n´est ce point normal puisque le 3 est le seul nombre premier divisible par 3; le 2 le seul divisible par 2….

    Le plus petit nombre permier suivant quei commence une constelaltion de 14 nombres premiers est le
    21817283854511261 et ne fut trouvé qu´en 1982 par D. Betsis & S. Säfholm.

    Il y a une autre séquence composée de nombres dont les résidius modulo 210 sont 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199. La méthode pour trouver l´algorithme consiste à exclure la posibilité de 153 mod 210 puisque le 149 mod 210 doit être aussi 2 mod 3 sinon le 151 mod 210 serait divisible par 3, mais alors le 153 mod 210 est , lui, divisible par 3. Il faut faire de Mème mod 5 et mod 7. Il suffit d´ecrire un petit programme qui fasse cette crible pour trouver les seéquences admissibles. Il n´y a que ces deux formes là pour k = 14.le pklus petit des nombres premiers quei commence cette constellation est le
    79287805466244209 trouvé la même année par les mêmes chercheurs.

    ***J´aimerais bien voir la démonstration qu´il existe un M pour tout k et que N est le même pour un même k***

    .https://sites.google.com/site/anthonydforbes/ktmin.txt?attredirects=0

  9. Mais 10^174 < p < 10^1198 ce n´est que des nombres premiers entre 173 chiffres et 1197 chiffres,ce qui actuellement n´est plus des nombre trop grands. Par contre il faudrait **beaucoup fouiller** puisqu´il y a environ 10^1000 /ln(10^1000) = 5*10^996 nombres premiers jusqu´à ceux qui ont 1000 chiffres. Sans compter que l´on n´a pas encore trouvé des constellations non triviales de plus de 21 membres et qu´il faut **beaucoup de temps** et de très trés bons algorithmes longs à construire pour trouver celles de 19 et de 20 membres; des algoritmes éliminateurs des candidats type **cible** à la manière d´Erasthotenes; pour ne tester que la primalité de peu de concurrents et gagner donc du temps.

  10. Je demandais la démonstration qu´il ya des répétitions de N mais avec des distances distintes entre les nombres premiers de la constellation, pour un même k. Pas toujours. Pour k = 6 nous avons ceci :

    k=6 N=16 B={0 4 6 10 12 16}

    1 7 11 13 17 19 23
    2 97 101 103 107 109 113
    3 16057 16061 16063 16067 16069 16073
    4 19417 19421 19423 19427 19429 19433
    5 43777 43781 43783 43787 43789 43793
    6 1091257 1091261 1091263 1091267 1091269 1091273
    7 1615837 1615841 1615843 1615847 1615849 1615853
    8 1954357 1954361 1954363 1954367 1954369 1954373
    9 2822707 2822711 2822713 2822717 2822719 2822723
    10 2839927 2839931 2839933 2839937 2839939 2839943

    Le nombre premier 11 -les angloaméricains l´ appelent un nombre premier « repunit » (qui répète l´iunité)- commence des constellations de K = 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14 et 15 membres et ne manque donc à commencer qu´au k = 6, parce que 11, 13, 17, 19, 23, 29 possède un N = 29 -11 = 18 supérieur à N = 16.

    Il faut aussi dire que l´on rejette les constellations dont les k nombres premiers ont les p résidus distincts du premier nombre premier qui les commence. Ainsi on rejette pour K = 3, la constellation 3, 5, 7 prce que ces trois nombres sont respectivement 0, 2 et 1 mod 3. Par contre on accepte la constellation qui commence avec le 11, pour k =14 : 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 52, 59, 61 parce que tous les résidus mod 11 ne sont pas représentés. Il manque un nombre premier 5 mod 11. Mais tous les autres y sont.

    Voici les repumits premiers:

    http://oeis.org/A004023

  11. Pingback: Arithmétique : Les Nombres Entiers | Pearltrees

  12. > J’ai écrit un petit code en C qui vérifie en moins de 10 minutes que la conjecture est vraie pour (M+N) inférieur à 1 million. (J’ai aussi écrit un code en Python qui fait la même chose en 24 heures.)

    Salut David,

    Comme beaucoup de physiciens je suis sûr que tu aimerais avoir la vitesse du C ou du Fortran et la souplesse de Python, ctypes est fait pour toi: https://docs.python.org/3/library/ctypes.html

    En gros là ou tu as besoin de vitesse tu utilises du C/Fortran et tu récupères tout ça dans Python via ctypes 😉

    @+

    • Conseil d’un physicien à un physicien. -:) Heureusement, l’alternative efficacité / lisibilité n’est pas seulement entre C/Fortran et Python.

      Pierre

  13. Pingback: Répartition des nombres premiers | Automaths

  14. J’ai trouvé la démonstration de la conjecture de Hardy- Littlewood.
    svp qlq me donner des informations pour les revues scientifiques

    • la deuxième conjecture : il y a plus de premiers dans n’importe quel intervalle de 0 à N , quelque soit N , qu’entre M + n , est vraie; car c’est une question de crible…! C’est à dire que les petits facteurs p 0, congrus à 1 ou à P[30] avec P premier appartenant [7 ; 29] il est trivial de montrer que l’intervalle M+n contiendra toujours moins de premiers….
      Il faudrait déjà prouver que l’estimation minimum de nombres premiers de n à 2n pour n >= 150 ne vaut pas: n / ln (2n)
      cette estimation se montre avec le crible G , variante d’Ératosthène dans ces 8 familles de premiers modulo 30.
      qui crible quel que soit une limite n fixée, le nombre de Premiers de n à 2n, mais avec les premiers <= sqrt de 2n et non de n , d'où cette évidence….!
      Mais si on regarde entre 0 et 10, et entre 10 et 20 et bien il y a autant de premiers de 0 à n =10, que de M=10 + n = 20 ….
      je pense que la conjecture utilisant les constellations n'a aucun rapport avec cette conjecture 2 , car dans cette dernière on part de 0.

  15. Bonjour.
    Je suis convaincu qu’une vidéo à ce sujet serait bienvenue. Merci d’avance.

Reply To eajo Cancel Reply

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.