Theorema Magnum MMIV: der Satz von Green-Tao

Ein 1837 von Dirichlet bewiesener Satz besagt, dass die arithmetische Folge unendlich viele Primzahlen enthält, wenn a und m teilerfremd sind. Zum Beispiel gibt es unendlich viele Primzahlen, die bei Division durch 35 den Rest 6 lassen.
Andererseits ist nach dem 1896 von Hadamard und de La Vallée Poussin bewiesenen Primzahlsatz die Dichte der Primzahlen in den natürlichen Zahlen approximativ log(n)/n. Diese Dichte geht gegen Null. Es kann also keine unendlich langen arithmetischen Folgen von Primzahlen geben. Zum Beispiel kann es nicht passieren, dass die Folge ab einer bestimmten Stelle nur noch aus Primzahlen besteht, denn andernfalls wäre ja die Dichte der Primzahlen im Grenzwert mindestens 1/m und damit positiv.

Erdös und Turán stellten 1936 die Vermutung auf, dass eine Folge natürlicher Zahlen, die positive Dichte in den natürlichen Zahlen hat, unendlich viele arithmetische Folgen der Länge 3 enthält. Das wurde 1952 von Roth bewiesen (mit Methoden der analytischen Zahlentheorie, nämlicher einer Variante der Kreismethode von Hardy-Littlewood) und 1975 von Szemerédi (mit einem kombinatorischen Beweis) verallgemeinert: es gibt unendlich viele arithmetische Folgen beliebiger vorgegebener Länge. Auf die Folge der Primzahlen läßt sich das natürlich nicht anwenden, weil deren Dichte nicht positiv ist. Erdös lobte deshalb 1976 dreitausend Dollar auf die bis heute offene Frage aus, ob dieselbe Folgerung auch noch gilt, wenn man nur Divergenz der Reihe aus den Inversen der Folgenglieder voraussetzt. Das würde sich dann auch auf die Folge der Primzahlen anwenden lassen.

Man kann das Resultat von Szemerédi als eine Verallgemeinerung des Schubfachprinzips sehen, mit dem Dirichlet im 19. Jahrhundert durchaus tiefliegende zahlentheoretische Sätze und insbesondere seinen Satz über arithmetische Folgen von Primzahlen bewiesen hatte. (Der Beweis benutzte natürlich noch weitaus mehr, er gilt heute als ein Meilenstein der analytischen Zahlentheorie und führte unter anderem erstmals L-Funktionen ein.)
Das Schubfachprinzip besagt zunächst nur, dass bei Aufteilung vieler Elemente auf wenige Klassen mindestens eine Klasse viele Elemente enthalten muß. Oft gilt aber mehr, viele mathematische Systeme haben ein Untersystem mit wesentlich höherem Organisationsgrad. Das ist das Thema der Ramsey-Theorie, die sich um den 1930 bewiesenen Satz von Ramsey entwickelte. Dieser besagt die Existenz einer Ramsey-Zahl, welche angibt, wie groß ein Graph sein muss, damit für eine Färbung stets eine Clique in gegebener Farbe und Größe existiert.

Zur Ramsey-Theorie gehört der schon 1927 bewiesene Satz von van der Waerden, dass man bei einer Färbung der natürlichen Zahlen stets einfarbige arithmetische Folgen beliebiger Länge findet. Damit konnte man aber nicht beweisen, dass es zu einer bestimmten Farbe eine beliebig lange arithmetische Folge gibt. Das war der Hintergrund der Vermutung von Erdös und Turán gewesen, die dann (nach Teilergebnissen von Roth) durch Szemerédi 1975 in einer kombinatorischen Tour de Force bewiesen wurde.

Der zentrale Teil in Szemerédis Beweis war das sogenannte Regularitätslemma. Beim Regularitätslemma geht es darum, Graphen mit einer sehr hohen Zahl von Knoten dadurch zu verstehen, dass man die Knoten in eine (sehr viel kleinere) Zahl von Mengen partitioniert, so dass man für Paare von Knotenmengen innerhalb dieser Mengen jeweils eine recht präzise Aussage zur Zahl der verbindenden Kanten treffen kann.
In mathematischen Begriffen heißt ein Paar A und B von Teilmengen der M-elementigen Knotenmenge eines Graphen ε-regulär, wenn für alle Teilmengen X von A und Y von B mit mindestens bzw. Knoten sich die Kantendichte d(X,Y) von der Dichte d(A,B) um höchstens ε unterscheidet. (Als Kantendichte d(X,Y) bezeichnet man die Anzahl der Verbindungskanten dividiert durch .)
Die Aussage des Regularitätslemmas ist, dass es zu jedem positiven ε Zahlen m,M gibt, so dass jeder endliche Graph auf M Knoten in n Teile (m ≤ n ≤ M) zerlegt werden kann, so dass alle annähernd die gleiche Größe haben und fast alle (nämlich mindestens (1-ε)n² der insgesamt n²) Paare ε-regulär sind.
In gewisser Weise bedeutet das, dass man jeden Graphen durch ein einfacheres Bild beschreiben kann.

Erdös kommentierte das Regularitätslemma so: komplettes Chaos ist unmöglich.
Szemerédis Beweis war lang und völlig unverständlich. Furstenberg fand zwei Jahre später einen ergodentheoretischen Beweis und Gowers gab 1998 einen Beweis, der Ergodentheorie vermeidet und nur elementare harmonische Analysis benötigt.