NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 15/12/2015

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Théorie des NOMBRES

 

Débutants

Général

MULTIPLICATIVE

 

Glossaire

Général

 

 

INDEX

Puissance

Décomposition

 

Lambda et fonction de Liouville

Conjecture des écarts d'Erdös

 

Sommaire de cette page

>>> Le problème d'Erdös

>>> Approche de sa résolution

>>> Séquences multiplicatives

 

 

 

 

Conjecture des écarts d'Erdös

Erdös discrepancy problem

 

Une des conjectures favorites d'Erdös qui se présente au départ sous la forme d'un amusement et qui se révèle particulièrement résistante quant à sa résolution.

Terence Tao y parvient en fin 2015 en faisant appel à des notions d'entropie de l'information et de théorie multiplicative, comme, par exemple, celle des fonctions de Liouville.

 

 

Le problème d'Erdös

 

 

Problème des écarts d'Erdös

 

Version imagée du fameux problème

 

Vous êtes prisonnier sur un promontoire. Un précipice devant vous et un nid de vipères derrière. Votre geôlier vous oblige à marcher continuellement.

Les conditions:

*    vous devez prévoir vous-même le programme de votre marche. Disons +1 pour avancer et – 1 pour reculer. Votre programme sera une suite de ces deux nombres.

*    le diable est "malin". Une fois votre programme établi, il vous impose de ne prendre que les pas une fois sur deux, ou sur trois, ou davantage.

Le promontoire ne vous permet pas de vous échapper sur les côtés. Par contre, la taille en longueur peut être quelconque.

 

La quantité de pas vers le danger est appelée l'écart ou discrepancy en anglais.

 

 

Paul Erdös (1913-1996) pose ce problème qui passe pour l'un de ses favoris.

 

Il s'agit que prévoir un programme de marche assurant la survie du prisonnier quelles que soient les injonctions du diable geôlier.

 

Erdös conjecture qu'un tel programme n'existe pas, même si la longueur du promontoire est infinie.

 

Les recherches montrent qu'il existe des programmes de marche qui donnent un long moment de survie. Mais, inéluctablement vient le moment de se livrer au diable.

 

 

 

Résolution – Approche

 

Jusqu'en 2014, aucun mathématicien n'a eu l'idée géniale qui aurait fait progresser vers la solution.

 

Il est vrai que la version avec un écart de seulement trois pas exige l'exploration d'une grande quantité de possibilités. Elle fut résolue en 2014 par Boris Konev et Alexei Lisista (Université de Liverpool). Leur conclusion montre qu'il est possible d'aller jusqu'à k = 1160 pas et pas un de plus.

 

En septembre 2015, Terence Tao montre que, quel que soit l'écart, il y aura toujours un nombre maximum k de pas de survie mais pas un de plus.

 

 

Terence Chi-Shen Tao, né en 1975 à Adélaide en Australie, est un mathématicien médaillé Fields en 2006. En 2015, professeur à l'Université de Californie, Los Angeles (UCLA).

 

Tao a dû recourir à une théorie avancée faisant appel à l'entropie d'objets mathématiques – une mesure de l'aspect désordonné ou non de la séquence – impliquant les séquences multiplicatives, une notion également utilisée pour tenter de comprendre la distribution des nombres premiers.

 

 

 

Séquences multiplicatives

 

En fin 2009, ce problème d'écart fut sélectionné dans le cadre du projet Polymaths, sélection organisée par Timothy Gowers – Université de Cambridge.

 

Terence Tao eut l'idée qu'il suffisait de résoudre ce problème que pour les séquences multiplicatives:

 

Pour une séquence multiplicative formée d'une suite de nombres (ici –1 et  +1), la théorie dit que, par exemple:

 

La sixième entrée est équivalente à deuxième entrée multipliée par le troisième entrée. Les entrées de rang nxm sont égales aux entrés de rang n fois celles de rang m.

 

En fait, dans une séquence multiplicative, la sous-séquence d'un pas sur trois, par exemple, est égale à la séquence soit identique soit symétrique fois la troisième entrée de la séquence.

 

Autrement-dit, s'il existe une suite de pas de survie dans la séquence d'origine, alors il y aura une sous séquence de survie  quelle que soit la quantité de pas sautés que le geôlier va imposer.

 

En conclusion, la preuve de l'existence d'une séquence multiplicative donnerait de grands espoirs de survie.

 

 

Les séquences multiplicatives sont un sujet important de la théorie des nombres. Un exemple est donné avec la fonction de Liouville qui permet de compter les premiers inférieurs à une valeur n donnée.

 

Kaisa Matomäki et Maksym Radziwill identifient des corrélations entre voisins dans les séquences multiplicatives. Tao commence à travailler avec eux et imagine des applications. Il obtient des résultats concernant les fonctions de Liouville. Il commente en disant que ces problèmes lui rappellent les Sudokus.

 

 Finalement en maitrisant des sommes un peu compliquées, Tao finit par résoudre la conjecture d'Erdös.

 

Il analyse la séquence de marche, morceau par morceau, et il détermine s'il peut survivre.

Il raisonne:

*    Soit le geôlier vous tue ou

*    alors l'entropie de la séquence va diminuer d'une valeur déterminée. Or, elle ne peut pas être négative,

Il arrivera inéluctablement un moment où l'entropie devra passer en négatif, alors ce sera l'impasse.

 

D'après (librement) A Magical Answer to an 80-Year-Old Puzzle – Olena Shmahalo – Quanta Magazine

 

 

 

Suite

*         Autres conjectures

*         Actualités 2015

*         Théorie des nombresIndex

Voir

*         Marche de l'ivrogne

*         Biographie d'Erdös

*         Publications d'Erdös

Cette page

http://villemin.gerard.free.fr/aMaths/ThNb/Erdos.htm