Une très longue démonstration


Erdos

La suite de + et de - ci-dessus a été difficile à trouver. Elle fait avancer l'étude d'un problème posé par Paul Erdös dans les années 1930 sous la forme d'une conjecture. Son énoncé est assez court. La conjecture de Erdös est la suivante :

Conjecture (Erdös discrepancy problem) :

Pour tout nombre entier C positif, et toute suite infinie s(0), s(1), s(2), ..., s(n), ... de '-1' et de '+1', il existe deux entiers d et k tels que :

| s(d) + s(2d) + s(3d) + ... + s(kd) | > C

Autrement dit, pour tout nombre C, par exemple 7, et toute suite infinie de '-1' et '+1' qu'on se donnera, on pourra extraire une suite finie de termes en retenant les k premiers termes dont l'indice est multiple d'un certain entier d, cela de façon à avoir une somme qui dépasse 7 en valeur absolue.
La conjecture concerne toutes les valeurs possibles de C, mais on peut aussi la voir comme une infinité de conjectures de plus en plus fortes : la conjecture pour C = 1, la conjecture pour C = 2, etc.

Pour C = 1, la conjecture se démontre à la main. En fait, jusqu'à 11 on réussit à construire des suites finies de '-1' et de '+1' telles que pour tout d et k  (tels que  kd < 12)

| s(d) + s(2d) + s(3d) + ... + s(kd) | ≤ 1.

En revanche quand on essaie avec les suites finies de longueur 12 (ou n'importe quel nombre supérieur), il devient impossible de satisfaire la même propriété. Avec un peu de soin, on réussit à établir le résultat rigoureusement.

Pour C = 2, la conjecture est beaucoup plus difficile et elle est restée irrésolue jusqu'en 2014. Elle vient d'être démontrée par Boris Konev et Alexei Lisitsa.

Voir : A Sat-Attack on the Erdös Discrepancy Conjecture : http://arxiv.org/pdf/1402.2184.pdf

La méthode a consisté à rechercher de manière systématique des suites finies de plus en plus longues de '-1' et de '+1' pour lesquelles on a toujours l'inégalité :

| s(d) + s(2d) + s(3d) + ... + s(kd) | ≤ 2.

Jusqu'à la longueur 1160, on trouve de telles suites et la suite recopiée plus haut convient pour 1160. En revanche, si on recherche une suite de longueur 1161, on échoue (c'est donc aussi le cas pour toutes les longueurs supérieures).

La méthode utilisée consiste à écrire l'ensemble des conditions que doit vérifier la suite de longueur 1161 sous la forme d'un système d'équations booléennes (il y a 1161 variables booléennes). Confié au meilleur algorithme connu pour ce type de systèmes d'équations, on a obtenu la réponse qu'il n'y pas de solutions, ce qui signifie que dans chaque cas possible au moins une suite extraite du type recherché vérifie :

| s(d) + s(2d) + s(3d) + ... + s(kd) | > 2

La démonstration de la machine

Les données produites par l'algorithme lors de sa recherche occupent un espace de 13 Giga-Octets (13 milliards de caractères). On peut les voir comme une démonstration de la conjecture pour C = 2.

Pour C = 3, la même méthode, malgré les qualités du programme utilisé et la puissance de nos ordinateurs reste impuissante. Elle n'a fourni (après plus de trois jours de calcul) qu'une suite de longueur 13000 vérifiant toujours l'inégalité :

| s(d) + s(2d) + s(3d) + ... + s(kd) | ≤ 3.

Le 12 du cas C = 1, devenu 1161 pour C = 2, sera donc supérieur à 13000 pour C = 3 (si la conjecture pour C = 3 est vraie).

Il est amusant de réaliser que la longueur de la démonstration pour C = 2 produite par la machine est supérieure à la taille de l'encyclopédie Wikipédia (environ 10 giga-octets). Inutile de dire qu'aucun humain ne pourra jamais la contrôler à la main.

Le pire ici est que ce que le formidable travail de l'ordinateur a réussi n'est que le début de la résolution de la conjecture générale de Erdös qui concerne tous les entiers C.

Quelle sera la longueur de la preuve pour C = 3 (si on y arrive) ? Qu'en sera-t-il pour C quelconque (si on y arrive) ?

Cette complexité des preuves envisagées donne le vertige.

Notons toutefois que rien de permet d'affirmer aujourd'hui que ce qui nous semble intrinsèquement difficile l'est vraiment. Bien que cela apparaisse improbable, personne ne peut exclure qu'un mathématicien génial vienne demain avec une solution pour C quelconque à l'aide d'une démonstration de quelques lignes !


7 commentaires pour “Une très longue démonstration”

  1. Diziet Sma Répondre | Permalink

    Est-il si improbale qu'un cerveau humain puisse concevoir une démonstration plus courte qu'une machine ?
    Question de béotien je précise,mais je pense à ces ordinateurs au jeu d'échecs qui à chaque coup passe en revue tous les options possibles,alors que le joueur humain n'hésitera qu'entre 2 ou 3 mouvements.

    • Jean-Paul Delahaye Répondre | Permalink

      Il est possible qu'un humain puisse trouver une démonstration courte. Il se trouve qu'on peut penser que les mathématiciens qui ont cherché ont sans doute (de manière implicite) exploré une grande quantité de tentatives courtes. Le fait qu'ils n'en aient pas trouvées qui aboutissent rend assez certain qu'il n'y pas de démonstrations très courtes.

      Concernant le jeu d'échecs, je pense que même si le bon joueur n'envisage que peu de coups, il s'aide pour cela d'une connaissance intuitive du jeu, elle-même résultat d'un grand nombre de "calculs". Ce qu'il fait n'est pas vraiment assimilable à une démonstration courte, mais plutôt à l'utilisation de règles judicieuses élaborées à l'aide de longs calculs.

  2. Diziet Sma Répondre | Permalink

    Merci pour votre réponse.Doit-on en déduire que les avancées les plus cruciales en mathématiques ne pourront plus se faire sans l'aide de machines toujours plus puissantes ?
    Il me vient à l'esprit la théorie des nombres dont les travaux sur ses briques de base que sont les nombres premiers ne peuvent guère se passer de l'assistance de gros calculateurs. Fonction Zéta de Riehmann,nombres premiers jumeaux....

    • Jean-Paul Delahaye Répondre | Permalink

      Non. De nombreux sujets mathématiques ne sont pas des questions de calcul. Même si l'ordinateur intervient de plus en plus souvent pour la résolution de questions mathématiques, le mathématicien reste pour l'essentiel aujourd'hui le créateur des nouvelles mathématiques.
      Voir à ce sujet :
      http://arxiv.org/pdf/1308.4678.pdf

  3. Diziet Sma Répondre | Permalink

    Merci pour le lien,mais sa richesse est telle qu'elle englobe et dépasse de loin nos propos(enfin surtout les votres).
    Je suis quand mème un peu surprise que l'auteur de l'article ne voit qu'un équivalent des très grands matheux du passé (Gallois,Grothendieck,Riemann,Gauss....) pour que la discipline fasse un bond en avant.
    Mème si les maths ne peuvent se comparer à la physique qui n'a guère avancé depuis la RG de 1915 et la MQ de 1927.
    La science en général n'est-elle pas devenue une affaire plus collective et surtout plus dépendante des crédits engagés ?

    • Jean-Paul Delahaye Répondre | Permalink

      Vous faites allusion à ce passage du texte :

      if one tries to assess quantitatively the contributions of Riemann, Gödel, or Grothendieck to mathematics, one could say that it is ten to a hundred times greater than that of a “normal” high-level mathematician. In other words, the contribution of one of the “great” mathematicians mentioned above is worth as much as the contribution of ten to a hundred members of the mathematical section of a
      good academy of sciences (say French, or US).

      Il se trouve qu'en mathématiques à côté du travail des chercheurs "de base" nombreux et qui font avancer les multiples spécialités, il y a des contributions rares et importantes qui proviennent d'esprits que tout le monde reconnaît très supérieurs. C'est un fait.
      Par ailleurs en mathématiques, les financements jouent un rôle bien moins important que dans les autres disciplines scientifiques. Le cas Grigori Perelman est exemplaire : alors que des financements importants étaient attribués à des groupes de chercheurs travaillant sur le même sujet, c'est lui, seul, qui a résolu le problème de la conjecture de Poincaré.

  4. AUJALEU Cedric Répondre | Permalink

    Une démonstration me paraît evidente : statistiquement, une somme infinie de 1 et de -1 peut prendre n'importe quelle valeur entre -infini et +infini. En effet, quelle que soit la valeur C d'une somme infinie donnée, on peut obtenir une suite donnant une somme supérieure à C en valeur absolue de la manière suivante :
    - si C supérieur à 0, on remplace un -1 par un 1
    - si C inférieur à 0, on remplace un 1 par un -1
    Or, pour une infinité de valeurs du pas de saut d, on obtient une infinité de suites de -1 et de 1. Il y en a donc nécessairement au moins une pour laquelle la somme est infinie.

Publier un commentaire