En mathématiques, le problème de la discrépance d'Erdős concerne l'amplitude des sommes de termes d'une suite de 1 et de -1 dont les indices forment une suite arithmétique.
Énoncé du problème Vers 1932, le mathématicien Paul Erdős a conjecturé que pour toute suite infinie de 1 et de −1 , et pour tout entier , il existe des entiers et tels que
Il s'agit de démontrer ou de réfuter cette conjecture.
De façon formelle, la discrépance de la suite vaut par définition, et la conjecture énonce que la discrépance de toute suite de 1 et de -1 est infinie.
Le terme " discrépance ", du latin discrepantia, peut signifier, au figuré, " désaccord " ou " discordance ".
En février 2014, Alexei Lisitsa et Boris Konev, de l'Université de Liverpool, ont démontré que toute suite de 1161 éléments ou plus satisfait la conjecture dans le cas particulier , ce qui prouve la conjecture pour . C'était la meilleure borne de ce type disponible à l'époque. Leur démonstration s'appuyait sur un algorithme informatique de résolution SAT dont la sortie occupe 13 gigaoctets de données, soit plus que l'intégralité du corpus de Wikipédia à l'époque, de sorte qu'elle ne peut être vérifiée indépendamment par des mathématiciens humains sans l'utilisation d'un ordinateur .
En septembre 2015, Terence Tao a annoncé une démonstration de la conjecture, s'appuyant sur des travaux réalisés en 2010 lors de Polymath5 (une forme de production participative appliquée aux mathématiques) et sur une suggestion faite par le mathématicien allemand Uwe Stroinski dans le blog de Tao . Sa démonstration a été publiée en 2016, comme premier article de la nouvelle revue Discrete Analysis .
Références
Bibliographie
Voir aussi
Articles connexes Flux binaire
Suite de Rudin-Shapiro Liste de sujets portant le nom de Paul Erdős
Liens externes The Erdős discrepancy problems – Projet Polymath Un ordinateur résout le casse-tête d'Erdős – mais aucun cerveau humain ne peut vérifier la réponse — The Independent (vendredi 21 février 2014)
Catégorie:Suite d'entiers