Diskrepanz-Vermutung

Die Diskrepanz-Vermutung ist eine von Paul Erdős aufgestellte und 2015 von Terence Tao bewiesene Vermutung aus der Mathematik.

Anschauliche Problemdarstellung

Die folgende Veranschaulichung stammt von James Grime:

Ein Mensch ist auf einem Felsvorsprung gefangen. Zwei Schritte zu seiner Linken befindet sich ein Abgrund, zwei Schritte zur Rechten eine Schlangengrube. Um ihn zu quälen, zwingt ein bösartiger Wärter sein Opfer, sich ständig nach links und rechts zu bewegen. Der Gefangene muss eine Folge von Schritten finden, mit der er den Gefahren auf beiden Seiten ausweicht. Bewegt er sich zuerst nach rechts, muss er sofort nach links zurück, sonst ist der Absturz vorprogrammiert.

Abwechselnd in beide Richtungen zu gehen, scheint die Lösung zu sein – doch hier ist der Haken: Der Gefangene muss seine Schrittfolge im Vorhinein festlegen, und der Wärter kann bestimmen, dass jener nur jeden zweiten Schritt ausführt, beginnend mit dem zweiten. Oder er lässt nur jeden dritten, vierten, … zu. Die Frage lautet: Existiert eine Taktik, mit welcher der Gefangene am Leben bleibt, unabhängig von der Strategie, die sein Peiniger wählt?

Die Diskrepanz-Vermutung besagt, dass eine solche Taktik nicht existiert – und zwar nicht nur für $C=1$, sondern auch für jede andere Entfernung zum Abgrund.

Mathematische Formulierung

Für jede Folge $(x_{n})_{n\in \mathbb {N} }$ mit $x_{n}\in \left\{+1,-1\right\}$ für alle $n$ und für jede ganze Zahl $C$ gibt es ganze Zahlen $k$ und $d$ mit

$\left|\sum _{i=1}^{k}x_{d\cdot i}\right|>C$.

Geschichte des Problems

Paul Erdös und Terence Tao (1985)

Die Vermutung wurde von Erdős um 1932 aufgestellt.

2010 wurde die Frage zu einem der ersten Polymath-Projekte.

2014 bewiesen Lisitsa und Konev die Vermutung für $C\leq 2$. In diesem Fall kann stets $k<1161$ gewählt werden. Ihr Computerbeweis war mit 13 Gigabyte der bis dahin aufwendigste Beweis der Mathematik.

2015 bewies Tao die Vermutung aufbauend auf den Vorarbeiten des Polymath-Projekts. Seine Arbeit wurde 2016 als erster Artikel der neugegründeten Fachzeitschrift Discrete Analysis veröffentlicht.

Literatur

• W. Timothy Gowers: Erdős and Arithmetic Progressions. In: László Lovász, Imre Z. Ruzsa, Vera T. Sós (Hrsg.): Erdős Centennial (= Bolyai Society Mathematical Studies. Band 25). Springer, 2013, ISBN 978-3-642-39285-6, ISSN 1217-4696, S. 265–287, doi:10.1007/978-3-642-39286-3 (englisch). 
• Boris Konev, Alexei Lisitsa: Computer-Aided Proof of Erdős Discrepancy Properties. In: Artificial Intelligence. Band 224, 2015, ISSN 0004-3702, S. 102–118 (englisch). 
• Kaisa Matomäki, Maksym Radziwiłł: Multiplicative functions in short intervals. In: Annals of Mathematics. Band 183, Nr. 3, 2016, ISSN 0003-486X, S. 1015–1056, doi:10.4007/annals.2016.183.3.6, JSTOR:24735181 (englisch). 
• Terence Tao: The Erdős discrepancy problem. In: Discrete Analysis. Band 1, 2016, ISSN 2397-3129, doi:10.19086/da.609, arxiv:1509.05363 (englisch).