|
|||||||||||||||||||||||||||||
|
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. |
|
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:
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. |
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. |
|
|
|
||
|
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. |
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. |
|
|
|
||
|
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:
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 |
|
|
Voir |
|
|
Cette page |
