Quelltext der Seite 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]]:<ref>{{Internetquelle |autor=Erica Klarreich |url=https://www.spektrum.de/magazin/beweis-der-diskrepanz-vermutung/1378800 |titel=Keine Rettung vor dem Abgrund |werk=[[Spektrum.de]] |datum=2015-12-16 |abruf=2020-03-23 |sprache=de}}</ref>

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 <math>C=1</math>, sondern auch für jede andere Entfernung zum Abgrund.

== Mathematische Formulierung ==

Für jede Folge <math>(x_n)_{n\in\N}</math> mit <math>x_n\in\left\{+1, -1\right\}</math> für alle <math>n</math> und für jede ganze Zahl <Math>C</math> gibt es ganze Zahlen <Math>k</math> und <math>d</math> mit
:<math>\left|\sum_{i=1}^kx_{d\cdot i}\right| > C</math>.

== Geschichte des Problems ==
[[Datei:Paul Erdos with Terence Tao.jpg|miniatur|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-Projekt]]e.<ref>Polymath: [http://michaelnielsen.org/polymath1/index.php?title=The_Erdős_discrepancy_problem ''The Erdős discrepancy problem.'']</ref>

2014 bewiesen Lisitsa und Konev die Vermutung für <math>C\le 2</math>. In diesem Fall kann stets <math>k < 1161</math> gewählt werden.<ref>siehe Beispiel 1.7 in {{Literatur |Autor=Terence Tao |Titel=The Erdős discrepancy problem |Sammelwerk=Discrete Analysis |Band=1 |Datum=2016 |Sprache=en |Seiten=4 |Fundstelle=Beispiel 1.7 |ISSN=2397-3129 |arXiv=1509.05363 |DOI=10.19086/da.609}}</ref> 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 ==
* {{Literatur |Autor=W. Timothy Gowers |Titel=Erdős and Arithmetic Progressions |Hrsg=László Lovász, Imre Z. Ruzsa, Vera T. Sós |Sammelwerk=Erdős Centennial |Verlag=Springer |Datum=2013 |Sprache=en |Reihe=Bolyai Society Mathematical Studies |BandReihe=25 |ISBN=978-3-642-39285-6 |Seiten=265-287 |ISSN=1217-4696 |DOI=10.1007/978-3-642-39286-3}}
* {{Literatur |Autor=Boris Konev, Alexei Lisitsa |Titel=Computer-Aided Proof of Erdős Discrepancy Properties |Sammelwerk=Artificial Intelligence |Band=224 |Datum=2015 |Sprache=en |Seiten=102-118 |ISSN=0004-3702}}
* {{Literatur |Autor=Kaisa Matomäki, Maksym Radziwiłł |Titel=Multiplicative functions in short intervals |Sammelwerk=Annals of Mathematics |Band=183 |Nummer=3 |Datum=2016 |Sprache=en |Seiten=1015-1056 |ISSN=0003-486X |DOI=10.4007/annals.2016.183.3.6 |JSTOR=24735181}}
* {{Literatur |Autor=Terence Tao |Titel=The Erdős discrepancy problem |Sammelwerk=Discrete Analysis |Band=1 |Datum=2016 |Sprache=en |ISSN=2397-3129 |arXiv=1509.05363 |DOI=10.19086/da.609}}

== Einzelnachweise==
<references />

[[Kategorie:Folge ganzer Zahlen]]
[[Kategorie:Satz (Mathematik)]]