Theorema Magnum MMXVI: Erdős‘ Diskrepanz-Problem

Pál Erdős war ein aus Ungarn stammender Mathematiker, der vor allem für zahlreiche Vermutungen bekannt ist, auf deren Lösung er Geldpreise aussetzte, 50 Dollar bei kleineren Vermutungen, vierstellige Beträge bei größeren. Eine bekannte Vermutung, die er bereits 1932 als 19-Jähriger und damals noch ohne Geldpreis – später lobte er dann 500 Dollar aus – aufgestellt hatte, war die Diskrepanz-Vermutung. Die wird anschaulich so erklärt:
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 er aus der festgelegten Folge 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 besagte, dass eine solche Taktik nicht existiert – und zwar nicht nur für C=1, sondern auch für jede andere Entfernung zum Abgrund.
Die mathematische Formulierung ist wie folgt: Für jede Folge xn, deren Glieder alle 1 oder -1 sind, und für jede ganze Zahl C gibt es ganze Zahlen k und d mit .
Später wurde die Vermutung allgemeiner für Hilbert-Räume statt für R formuliert. Man hat also eine Folge in einem Hilbert-Raum, deren Glieder Norm 1 haben und dann soll es zu jeder ganzen Zahl C wieder k und d geben mit .

Nach Meinung von Erdős sollten Theorien nicht alles in der Mathematik ausmachen. Es gebe genug Probleme, die man mit fortgeschrittenen Methoden nicht angehen könne und die trotzdem nicht uninteressant seien. Trotzdem hat sich eine Diskrepanztheorie entwickelt, bei der es grob gesagt um die Approximierbarkeit kontinuierlicher Objekte durch diskrete geht. Beispielsweise bewies Erdős’ früherer Student Joel Spencer 1985, dass man zu je n Teilmengen eine Zerlegung von {1,…,n} in zwei Teilmengen R und B finden kann, die bezüglich jedem der S_i annähernd ausgeglichen ist: . Solche Resultate hatten Anwendungen auf Approximationsalgorithmen und numerische Verfahren. Eine spekatakuläre Anwendung der Diskrepanztheorie wurde das seit 1959 offene Kadison-Singer-Problem aus der Theorie der Operatoralgebren über die Eindeutigkeit der durch den Satz von Hahn-Banach gegebenen Erweiterung gewisser linearer Funktionale auf C*-Algebren: auf einer maximalen abelschen Unteralgebra hat man einen reinen Zustand ρ (ein positives Funktional, das keine Konvexkombination positiver Funktionale ist) und fragt nach der Eindeutigkeit der Fortsetzung auf . (Physikalisch ist das analog den in der Quantenmechanik den Observablen entsprechenden Wahrscheinlichkeitsverteilungen als lineare Funktionale auf kommutierenden Operatoren, die man dann auf andere Observablen ausdehnen will, welche nichtkommutierenden Operatoren entsprechen.) Kadison und Singer hatten gezeigt, dass für Zustände die Erweiterungen nicht immer eindeutig sind, sie hatten aber Eindeutigkeit der Fortsetzung für Zustände vermutet. Über die Jahrzehnte war dieses Problem zu einem Problem in endlichdimensionalen Vektorräumen (statt dem Hilbert-Raum l²N) reduziert worden. Für jedes ε›0 soll es ein k geben, so dass für jedes n und jede nxn-Matrix T mit verschwindenden Diagonalelementen es eine Aufteilung der ersten n Zahlen in k Mengen Ai gibt mit für alle i, wobei Pi die Projektion auf den Unterraum ist, der von denjenigen Vektoren der Standardbasis aufgespannt wird, deren Indizes in der Menge liegen. Die Diskrepanztheorie kam ins Spiel, als Nik Weaver 2004 das Kadison-Singer-Problem umformulierte in das Problem, zu α>0 und Vektoren v₁,…,v_n mit und für alle eine Aufteilung von {1,…,n} in zwei Teilmengen R und B zu finden, so dass und für alle gilt. Diese Formulierung konnten Spielman, Marcus und Srivastava 2013 mit elementaren Methoden beweisen.

Eine Anwendung in der Theoretischen Informatik war die von denselben Autoren dann bewiesene Existenz k-regulärer Ramanujan-Graphen für beliebiges k. Ramanujan-Graphen sind durch gewisse Bedingungen an die Eigenwerte ihrer Adjazenzmatrix charakterisiert und sie haben annähernd optimale Expander-Eigenschaften. “Expansivität” mißt die Stabilität des durch den Graphen beschriebenen Netzwerkes: sie ist klein, wenn man den Graphen so in zwei annähernd gleich große Teile zerlegen kann, daß es nur wenige Verbindungen zwischen den beiden Teilen gibt. Expander waren ursprünglich von Kolmogorow und Barzdin eingeführt worden: sie hatten bewiesen, dass man einen (mit Radius 1 verdickten) d-regulären Graphen mit N Ecken im R³ in einen Ball mit Radius R=c_dN^1/2 einbetten kann und dass sich die Abschätzung dür den Radius wegen der Existenz von Expander-Graphen nicht verbessern läßt. Die Verallgemeinerungen von Expander-Graphen auf Mannigfaltigkeiten und Simplizialkomplexe wurden in den Nuller und Zehner Jahren zu einem wichtigen Thema der geometrischen Topologie.

Die Diskrepanz-Vermutung wurde 2010 auf Vorschlag von Timothy Gowers eines der ersten Polymath-Projekte massiver Kollaboration von Mathematikern im Internet. Zwar konnte die Vermutung nicht gelöst werden, es konnte aber gezeigt werden, dass die Vermutung sich auf eine andere über (stochastische) multiplikative Funktionen mit Werten im Einheitskreis zurückführen läßt.
Multiplikative Funktionen sind ein Thema der analytischen Zahlentheorie, ein klassisches Beispiel ist die Liouville-Funktion λ(n), die den Wert -1 oder 1 annimmt, je nachdem ob n ungerade oder gerade viele Primfaktoren hat. Ein anderes Beispiel ist die Möbius-Funktion μ(n), die für eine quadratfreie Zahl mit λ(n) übereinstimmt und ansonsten den Wert 0 annimmt. Für teilerfremde Zahlen gilt μ(ab)=μ(a)μ(b). Der Primzahlsatz über die Verteilung der Primzahlen ist äquivalent zu und Denjoy bemerkte 1931, dass sich die Riemannsche Vermutung über Nullstellen der Zetafunktion mit Hilfe der Möbius-Funktion wahrscheinlichkeitstheoretisch formulieren läßt: es soll gelten.
Das Verständnis solcher multiplikativer Funktionen, insbesondere ihres Verhaltens auf kurzen Intervallen, verbesserte sich vor allem durch Arbeiten von Matomäki und Radziwiłł. Insbesondere konnten sie in einer 2016 in Annals of Mathematics veröffentlichten Arbeit ihre Mittelwerte auf kurzen Intervallen zu Mittelwerten auf langen Intervallen in Beziehung setzen, womit sie ältere Vermutungen über die Liouville- und Möbius-Funktion und die Existenz von “x^ε-glatten Zahlen” (Zahlen mit relativ kleinen Primfaktoren) in Intervallen [x,x+c(ε)√x] beweisen konnten. Diese Arbeit und weitere gemeinsame Arbeiten von Matomäki und Radziwiłł lieferten auch partielle Resultate für die Chowla-Vermutung über die asymptotische Vernachlässigbarkeit von Paarkorrelationen der Liouville-Funktion, derzufolge solche Summen asymptotisch o(x) sein sollen. Allgemeiner stellte die Elliott-Vermutung dieselbe Behauptung nicht nur für die Liouville-Funktion, sondern für multiplikative Funktionen mit gewissen Voraussetzungen auf. Aus der Elliott-Vermutung würde die Diskrepanz-Vermutung folgen, jedoch fanden Matomäki-Radziwiłł-Tao in ihrer Arbeit Gegenbeispiele zur Elliott-Vermutung, die sie deshalb durch eine mit stärkeren Voraussetzungen ersetzten. (Taos Reduktion der Diskrepanz-Vermutung auf die Elliott-Vermutung benutzte wesentlich die Argumente aus dem Polymath-Projekt.)

Terence Tao stellte anhand einiger Fast-Gegenbeispiele fest, dass multiplikative Funktionen ein wichtiger Testfall für die Diskrepanz-Vermutung sind. Seine gemeinsamen Arbeiten mit Matomäki und Radziwiłł über multiplikative Funktion dienten insofern der Vorbereitung des Beweises der Diskrepanz-Vermutung.

Das Foto zeigt Tao, wie er als 9-jähriges Wunderkind mit dem damals 71-jährigen Erdős auf einem Sofa sitzt und sich mathematische Probleme erklären läßt. Es ist nicht bekannt, ob sie auch über das Diskrepanz-Problem gesprochen haben.
Lisitsa und Konev, zwei Informatiker aus Liverpool, bewiesen 2014 die Diskrepanz-Vermutung zunächst für C≤2. Sie zeigten, dass dann stets k≥1161 gewählt werden kann. Ihr Computerbeweis war mit 13 Gigabyte der bis dahin aufwendigste Beweis der Mathematikgeschichte. (Diesen Rekord verloren sie bald darauf an eine Gruppe, welche bewies, dass 7824 die maximale Zahl ist, bis zu der man die ganzen Zahlen mit zwei Farben färben kann ohne dass es ein einfarbiges Tripel (a,b,c) mit a2+b2=c2 gibt. Jener Beweis benötigte 200 Terabyte.)
Ein Jahr später bewies Tao dann die Vermutung aufbauend auf den Vorarbeiten des Polymath-Projekts, ganz ohne Computerhilfe. Der wesentliche neue Teil war eine gemittelte logarithmische Version der Elliott-Vermutung, aufbauend auf Abschätzungen aus der gemeinsamen Arbeit mit Matomäki und Radziwiłł. Seine Arbeit “The Erdös discrepancy problem” wurde 2016 als erster Artikel der neugegründeten Fachzeitschrift Discrete Analysis veröffentlicht.

Bild: https://commons.wikimedia.org/wiki/File:Paul_Erdos_with_Terence_Tao.jpg