Dr. Christian Elsholtz, Oberseminar WS01/02

Arithmetische Progressionen oder Ordnung im Chaos

1 Einleitung

Auch noch so chaotische, zufällige Strukturen können gar nicht so unregelmäßig sein, dass es nicht doch hochgradig reguläre Teilstrukturen gibt. Es gibt eine Reihe von Sätzen der Form: Für alle k ∈ ℕ gibt es ein n(k), so dass eine beliebige Struktur der Größe n(k) eine reguläre Teilstruktur die Größe k hat. Für dieses Prinzip nennen wir drei Beispiele. Mit den letzten beiden Beispielen werden wir uns näher befassen. (Einen guten Überblick zu diesem Prinzip gibt [9].)

• Ramseytheorie. Gegeben sei ein vollständiger Graph K_{n}. Färbt man die Kanten auf beliebige Weise rot oder blau, so gibt es einen vollständigen Teilgraphen K_{r}, der nur aus einer der beiden Farben besteht, also monochromatisch ist. Man kann zeigen, dass man r von der Größenordnung r ≥ c log n wählen kann. Zur Übung beweise man, dass unter 6 Personen, man immer 3 findet, die sich entweder alle kennen, oder alle nicht kennen. (Wobei ”sich kennen“ natürlich als reflexiv und symmetrisch, aber nicht als transitiv angenommen wird).

• B. van der Waerden bewies: Teilt man die natürlichen Zahlen in zwei Klassen (Farben) ein, so muss mindestens eine der Klassen beliebig lange arithmetische Progressionen enthalten. Dies wurde von I. Schur und P. Baudet vermutet.

• E. Szemerédi bewies, dass eine Folge A ⊂ ℕ mit positiver oberer Dichte beliebig lange arithmetische Progressionen haben muss. In anderen Worten, sei r_{k}(n) die maximale Anzahl einer Menge natürlicher Zahlen in [1, n], die keine Progression der Länge k enthält, so gilt für k ≥ 3: r_{k}(n) = o(n). Dies wurde von P. Erdős und P. Turán vermutet.

Das dritte Thema ist mit dem zweiten eng verwandt. Man kann zu Sätzen vom van der Waerden-Typ oft eine sogenannte Dichteversion vom Szemerédi-Typ angeben. Gerade dieser letzte Themenkreis hat in den vergangenen Jahrzehnten eine ungeheure Aufmerksamkeit erhalten. Insbesondere wurden drei Fieldsmedaillen an Leute vergeben, die zu diesem Thema fundamentale Beitrage geleistet haben. (K. Roth, J. Bourgain und T. Gowers).

Für einen Überblick und Verallgemeinerungen vergleiche man auch [28]. In dem Seminar werde ich zunächst die entscheidenden Beweisideen für den Satz von van der Waerden skizzieren und den Satz von Szemerédi für k = 3 beweisen. In einem zweiten Teil fragen wir uns, inwieweit es Umkehrungen gibt. D.h. zu den erhaltenen oberen Schranken der Sätze geben wir komplementäre untere Schranken an.

2 Der Satz von van der Waerden

2.1 Endliche Version

Anstelle des obigen Satzes von van der Waerden betrachten wir folgende Variante:

Satz 1 (van der Waerden, 1928). Für alle k, r ∈ ℕ gibt es eine Zahl W̃ (k, r) mit der Eigenschaft, dass bei einer beliebigen Einteilung der Zahlen {1, 2, …, W̃ (k, r)} in r Klassen (Farben) mindestens eine der Klassen eine arithmetische Progression der Länge k enthält.

Wir definieren für festes k und r die kleinstmögliche Zahl W (k, r) = min W̃ (k, r). Die ursprüngliche Frage betrachtete nur den Fall r = 2, aber beim Beweis stellte es sich heraus, dass alles einfacher wird, wenn man eine stärkere Induktionsbehauptung zugrunde legt. (Lange war kein Beweis bekannt, der den Fall r = 2 direkt angeht, vgl. Deuber [10]). Die Reduktion der unendlichen Mengen mit beliebig langen Progressionen auf endliche Intervalle der Länge W̃ (k, r) mit Progressionen der Länge folgt mittels ”Kompaktheit“ aus der Logik bzw. Mengenlehre. Ein Diagonalenargument zeigt, dass es nicht sein kann, dass die unendliche Version gilt, aber nicht die endliche, vgl. den Aufsatz von van der Waerden [47]. Gilt andersherum die endliche Version, gilt natürlich erst recht die unendliche Version.

2.2 Ein Beispiel

Satz 2. Es gilt W (3, 2) = 9.

Zum Beweis versuchen wir, eine Progression der Länge 3 zu verhindern. Beweis durch Fallunterscheidung: 1 ist o.B.d.A. rot. Fall 1. Sei nun 2 rot, dann ist 3 blau.

r 1 2 b 3

Fall 1.1. Wir nehmen an, dass 4 rot sei. Dann muss 6 und 7 blau sein, wegen (2,4,6) und (1,4,7). Wegen (5,6,7) muss dann 5 rot sein.

r 1 2  4 5 b  3  6 7

Dann aber kann 8 weder rot sein (2,5,8), noch blau (6,7,8). Fall 1.2. Wir nehmen an, 4 sei blau, dann muss wegen (3,4,5) 5 rot sein.

r 1 2  5 b  3 4

Über 6 ist nichts bekannt, man könnte eine weitere Fallunterscheidung machen, aber man will ja auch nicht zu viele Unterfälle betrachten. Wegen (2,5,8) und (1,5,9) müssen 8 und 9 blau sein. Dann aber muss 7 rot sein.

r 1 2  5  7 b  3 4  8 9

Jetzt sieht man, dass 6 weder rot noch blau sein kann.

Andererseits, weil wir die Fallunterscheidung bei 6 nicht vorgenommen haben, sondern gleich benutzten, dass wir Intervalllänge 9 haben, haben wir noch nicht gesehen, ob nicht vielleicht auch Intervalllänge 8 ausgereicht hätte. Das folgende Beispiel zeigt aber W (3, 2) > 8.

r 1 2  5 6 b  3 4  7 8

Wir haben also systematisch Fall 1 behandelt. Fall 2. 1 ist o.b.d.A. rot, aber 2 ist blau.

r 1 b 2

Fall 2.1. Wir nehmen an, 3 sei rot. Es ist dann wegen (1,3,5) 5 blau, und wegen (2,5,8) 8 rot.

r 1  3  8 b  2  5

Fall 2.1.1. Wir nehmen an, 4 sei rot. Es ist dann wegen (1,4,7) 7 blau, und wegen (4,6,8) und (5,6,7) kann 6 weder rot noch blau sein.

r 1  3 4  8 b  2  5  7

Fall 2.1.2. Wir nehmen an, 4 sei blau. Es ist dann wegen (2,4,6) 6 rot, und wegen (6,7,8) ist 7 blau.

r 1  3  6  8 b  2  4 5  7

Wegen (3,6,9) und (5,7,9) kann 9 weder rot noch blau sein. Fall 2.2. Wir nehmen an, 3 sei blau. Dann muss wegen (2,3,4) 4 rot sein und wegen (1,4,7) 7 blau. Wegen (3,5,7) ist 5 rot.

r 1  4 5 b  2 3  7

Dann ist aber wegen (4,5,6) 6 blau. Wegen (1,5,9) und (3,6,9) kann 9 weder rot noch blau sein.

r 1  4 5  8 b  2 3  6 7

ist übrigens ein zweites Beispiel für W (3, 2) > 8.

2.3 Der allgemeine Fall

Es ist folgendes bekannt:

W (2, r) = r+1, W (3, 2) = 9, W (3, 3) = 27, W (3, 4) = 76, W (4, 2) = 35, W (5, 2) = 178, W (6, 2) > 230.

Die Funktion W (k, r) wächst so stark und nicht vorhersehbar an, dass man dies nicht mehr allgemein analog durch Fallunterscheidungen bearbeiten kann. Die besten bekannten oberen Schranken sind riesengroß. Das Problem ist, dass man eine allgemeine Methode benötigt. Man verwendet doppelte Induktion und dabei werden die vorher berechneten Werte rekursiv aufgerufen.

2.3.1 W (3, 2) ≤ 325

Wir zeigen mit einer anderen Methode, (die verallgemeinerungsfähig ist), W (3, 2) ≤ 325. Erneut versuchen wir, eine Progression der Länge 3 zu verhindern. Wir unterteilen [1, 325] in 65 Blöcke B_{i} der Länge 5:

[1, 5] ∪ [6, 10] ∪ … ∪ [321, 325].

Vgl. Bild 1. Es gibt 2^{5} = 32 Möglichkeiten, die 5er Blöcke mit 2 Farben zu färben. Unter den ersten 33 B_{i} sind also zwei mit gleicher Färbung, nennen wir diese B_{a} und B_{b}. Wir beachten, dass auch B_{2b−a} einer der 65 Blöcke ist.

B_{a} = {5(a − 1) + 1, 5(a − 1) + 2, 5(a − 1) + 3, 5(a − 1) + 4, 5(a − 1) + 5}.

Unter den ersten drei Zahlen gibt es zwei, die die gleiche Farbe (o.B.d.A. rot) haben, sagen wir j und j + d, wobei d ∈ {1, 2}. Falls j + 2d auch rot wäre, sind wir fertig, j + 2d ist also blau. Wir haben übrigens die Blöcklänge 5 gewählt, damit j +2d im gleichen Block liegt.

Vgl. Bild 2. Von den 5 Elementen interessieren uns also nur drei in Progression, j, j + d, j + 2d. B_{a} sieht also vereinfacht wir rrb aus. Genauso sind in B_{b} die drei Zahlen 5(b − a) + {j, j + d, j + 2d} als rrb gefärbt. Betrachten wir nun B_{2b−a}, insbesondere die Zahl 10(b − a) + j + 2d. Diese kann wegen (j, 5(b − a) + j + d, 10(b − a) + j + 2d) nicht rot sein, und wegen (j + 2d, 5(b − a) + j + 2d, 10(b − a) + j + 2d) nicht blau sein. Diese Farbfokussierung auf eine Zahl zeigt, dass [1, 325] eine monochromatische Progression der Länge drei enthalten muss. Vgl. Bild 3.

2.3.2 W (3, 3) < ∞

Satz 3.

W (3, 3) ≤ 7(2 · 3^{7} + 1)(2 · 3^{7(2·3^{7}+1)} + 1).

Diese Zahl ist riesengroß, ungefähr 10^{14.600}, wo man doch W (3, 3) = 27 nachweisen kann. Immerhin funktioniert dies mit einer allgemeinen Methode, und man sieht in diesem Abschnitt den allgemeinen Beweis durchschimmern. Wir teilen das Intervall [1, 7(2 · 3^{7} + 1)(2 · 3^{7(2·3^{7}+1)} + 1)] in (2 · 3^{7(2·3^{7}+1)} + 1) Blöcke B_{i} der Länge l = (7 · 3^{7} + 1) ein. Es gibt 3^{l} viele Möglichkeiten, diese Blöcke mit drei Farben zu färben. Es sei z = 7(2 · 3^{7} + 1). Unter den ersten 3^{z} + 1 Blöcken B_{i} müssen also zwei identisch gefärbte sein, B_{i_{1}} und B_{i_{1}+d_{i}}. Man beachte, dass B_{i_{1}+2d_{i}} definiert ist, daher also die Anzahl der Blöcke. Beim letzten Schritt benutzen wir, dass W (2, r) für riesengroßes r bekannt ist. Allgemein, beim Induktionsschritt schließt man von W (k − 1, r′) für große r′ und W (k, r − 1) auf W (k, r).

Wir zerlegen die Blöcke B_{i} in 2·3^{7}+1 Teilblöcke B_{i,j} der Länge 7. Es gibt 3^{7} Färbungen dieser 7er Blöcke, also gibt es unter den ersten 3^{7} +1 Blöcken zwei Blöcke B_{i_{1},i_{2}} und Bi_{1}, i_{2} + d_{2} die gleich gefärbt sind. Unter den ersten 4 Zahlen des ersten 7er Blocks B_{i_{1},i_{2}} kommt eine Farbe doppelt vor. O.B.d.A. sind also i_{3} und i_{3} + d_{3} beide rot. Hierbei ist d_{3} ∈ {1, 2, 3}. Beachte {i_{3}, i_{3} + d_{3}, i_{3} + 2d_{3}} ∈ B_{i_{1},i_{2}}. Es ist also o.B.d.A.: rrb. Da

{i_{3} + 7d_{2}, i_{3} + 7d_{2} + d_{3}, i_{3} + 7d_{2} + 2d_{3}} ∈ B_{i_{1},i_{2}+d_{2}}

identisch gefärbt ist, liegt auch hier der Fall rrb vor. Analog wie im vorigen Abschnitt über W (3, 2) folgt, dass i_{3} + 14d_{2} + 2d_{3} weder rot noch blau sein kann, also gelb sein muss. Soweit haben wir nur den großen Block B_{i_{1}} behandelt. In Kurzform also rrb rrb xxg. Der Block B_{i_{2}} ist identisch gefärbt. Die konkreten Zahlen sind (Hinweis, ab jetzt hat (zumindest die erste Auflage) [26] Ungenauigkeiten):

{i_{3} + ld_{1}, i_{3} + d_{3} + ld_{1}, i_{3} + 2d_{3} + ld_{1}} ∈ B_{i_{1}+d_{1},i_{2}}.
{i_{3} + ld_{1} + 7d_{2}, i_{3} + d_{3} + ld_{1} + 7d_{2}, i_{3} + 2d_{3} + ld_{1} + 7d_{2}} ∈ B_{i_{1}+d_{1},i_{2}+d_{2}}.

Und analog

i_{3} + 2d_{3} + ld_{1} + 14d_{2} ∈ B_{i_{1}+d_{1},i_{2}+d_{2}}.

Das ergibt also schematisch (vergleiche auch Bild 4):

\begin{matrix}r & r & b & r & r & b & x & x & g \\ r & r & b & r & r & b & x & x & g \\ x & x & x & x & x & x & x & x & ? \end{matrix}

Wenn wir nun auf

m = i_{3} + 2d_{3} + 2ld_{1} + 14d_{2}

fokussieren, so kann m wegen

i_{3}, i_{3} + d_{3} + ld_{1} + 7d_{2}, m = i_{3} + 2d_{3} + 2ld_{1} + 14d_{2}

nicht rot sein, wegen

i_{3} + 2d_{3}, i_{3} + 2d_{3} + ld_{1} + 7d_{2}, m = i_{3} + 2d_{3} + 2ld_{1} + 14d_{2}

nicht blau sein, und wegen

i_{3} + 2d_{3} + 14d_{2}, i_{3} + 2d_{3} + ld_{1} + 14d_{2}, m = i_{3} + 2d_{3} + 2ld_{1} + 14d_{2}

nicht gelb sein.

(Folgendes ist etwas unpräzise: Durch das rekursive Zurückgreifen auf Färbungen ganzer Blöcke, erhält man riesige Zahlen. Die Blockreihe hat zwar nur Länge k−1, dafür benötigt man aber für die Schranke für W (k, r) die Schranken für W (k − 1, r′) mit sehr großem r′. Die obigen Schranken W (k, 2) wachsen bereits schneller als die Ackermannfunktion, die wiederum ein Beispiel einer nicht primitiv rekursiven Funktion ist. Diese ist wie folgt definiert. Es sei A(0, n) = n + 1, A(m + 1, 0) = A(m, 1), A(m + 1, n + 1) = A(m, A(m + 1, n))

Daraus folgt dann z.B.: A(0, n) = n + 1, A(1, n) = 2 + (n + 3) − 3, A(2, n) = 2(n + 3) − 3, A(4, n) = 2^{2^{^{···}^{2}}} − 3 (Turm der Höhe) n + 3 etc. Die Ackermannfunktion ist die Diagonale A(n, n). Shelah (siehe [35], aber auch die zweite Auflage von [26]) hat gezeigt, dass man nicht die Ackermannfunktion, sondern nur die 5.te oder 6.te Stufe benötigt. Aber auch diese Schranken sind ungeheuer groß. In diesem Jahr nun erschien die Arbeit von Gowers über die Verbesserung des Satzes von Szemerédi. Während Szemerédi in seinem Beweis van der Waerdens Satz (mit den damals bekannten Werten) benutzte, und daher keine neuen Schranken an W (k, r) erhielt, dafür aber schlechte Schranken für r_{k}(n), vermeidet Gowers den Satz von van der Waerden. Aus guten Schranken für r_{k}(n) kann er dann auch gute Schranken für W (k, r) erhalten. Gowers erhielt für seine Schranken einen von Ron Graham ausgelobten Preis von $1000. Grahams Vermutung besagte, dass für W (k, 2) ein Turm von 2er-Potenzen der Höhe k ausreicht. Gowers bewies also für große k etwas viel besseres, aber für 5 ≤ k ≤ 8 ist die Vermutung meines Wissens noch offen.)

Satz 4 (Gowers, 2001).

W (k, 2) ≤ 2^{2^{2^{2^{2^{k+9}}}}} .

2.4 Untere Schranken

Die komplementären unteren Schranken sind sehr weit von den oberen Schranken entfernt.

Satz 5 (Berlekamp, 1968). Für primes p gilt W (p + 1, 2) ≥ p 2^{p}.

(Argumentation in endlichen Korpern. Der Beweis geht so ähnlich, wie in der Codierungstheorie, wo man bestimmte Codes konstruiert.) Wir beweisen etwas weniger. Wir verwenden ein probabilistisches Argument unter Benutzung des Lovász Local Lemma.

Satz 6.

W (k, 2) ≥ \frac{2^{k}}{2ek} (1 + o(1).

Seien A_{i}, B_{i} Ereignisse eines Wahrscheinlichkeitsraums Ω. Es sei A unabhängig von B_{1}, …, B_{r}, in folgendem stärkeren Sinne von Unabhängigkeit: Für alle nichtleeren Teilmengen J ⊆ [1, r] gilt

p (A ⋀ (_{⋀j∈J}B_{j})) = p(a)p (_{⋀j∈J}B_{j}) .

Wir nennen dann A von den B_{i} wechselseitig unabhängig (mutually independent). Es bezeiche S die Menge aller arithmetischen Progressionen S ⊂ [1, n] der Länge k. Man beachte, dass (für festes k) es etwa c_{k}n^{2} viele Progressionen gibt, da die Progressionen der Länge k, also {a + ib : 0 ≤ i ≤ k − 1}, ja durch zwei Parameter a und b beschrieben werden können.

c′_{k}n^{2} ≤ |S| ≤ n^{2}.

Wir definieren auf S den Abhängigkeitsgraphen G. Die Ecken des Graphen sind die Mengen S ∈ S, also E = S. Hierbei sind S ∈ E und T ∈ E durch eine Kante verbunden, wenn S ∩ T ≠ ∅. (Achtung: im Vortrag hatte ich aus Versehen S ∩ T = ∅ gesagt!) Der Graph verbindet also arithmetische Progressionen, die sich schneiden. Da dies für großes n und kleines k recht selten vorkommt, ist der Graph also recht leer. Eine Progression, die eine zweite Progression nicht schneidet, ist von der zweiten Progression wechselseitig unabhängig.

Um das ”wechselseitig“ brauchen wir uns nicht kümmern, es ist halt nur Voraussetzung des benötigten Hilfsmittels. Wir färben nun das Intervall [1, n] mit zwei Farben zufällig. Die Zahl i ist mit Wahrscheinlichkeit p = \frac{1}{2} rot bzw. blau. Wir bezeichnen mit A_{S} das Ereignis, dass die arithmetische Progression S monochrom ist und mit Ā_{S} das komplementäre Ereignis. Es gilt also p(A_{s}) = \frac{2}{2^{k}} und p(Ā_{s}) = 1 − \frac{1}{2^{k−1}} . Wir fragen uns, für welches n(k) wir

p( ⋀_{S∈S} Ā_{S}) > 0

nachweisen können. Denn dann gibt es eine Färbung des Intervalls, in der keine monochromatische arithmetischen Progression existiert. Somit würde dieses n eine untere Schranke an W (k, 2) liefern. Wir zitieren nach Alon und Spencer [2]:

Lemma 1 (Lovász Local Lemma). Seien A_{1}, A_{2}, … A_{r} Ereignisse eines Wahrscheinlichkeitsraumes. Ein gerichteter Graph D(V, E) auf der Menge der Kanten V = {1, …, r} wird Abhängigkeitsgraph der Ereignisse A_{1}, … A_{r} genannt, wenn für alle i, (1 ≤ i ≤ r), das Ereignis A_{i} wechselseitig unabhängig von allen Ereignissen {A_{j} : (i, j) ∉ E} ist. Sei also D(V, E) ein derartiger gerichteter Graph zu den genannten Ereignissen. Wir nehmen an, dass es reelle Zahlen 0 ≤ x_{i} < 1 gibt, und dass für alle 1 ≤ i ≤ r

p(A_{i}) ≤ x_{i} ∏_{(i,j)∈E}(1 − x_{j})

gilt. Dann gilt

p(⋀_{i=1}^{r} Ā_{i}) ≥ ∏_{i=1}^{r}(1 − x_{i}).

(Hinweis: Mir scheint, dass bei dieser Definition Ereignisse, die durch Kanten verbunden sind, dennoch unabhängig sein können. Der Graph ist also zunächst nicht eindeutig definiert. Für Anwendungen ist es aber günstig, ihn so klein wie möglich zu wählen, und nicht willkürlich Kanten stehen zu lassen.) Man beachte, dass die Voraussetzung an die Wahrscheinlichkeiten lokal sind, dass die Aussage aber global ist. Gerade deswegen ist das Lemma nützlich. Für viele Anwendungen reicht es bereits, dass p(∧_{i=1}^{r}Ā_{i}) > 0 gilt. Das Lemma ist recht allgemein, oft braucht man nur einen symmetrischen Spezialfall. Dieser ist besonders nützlich, wenn der Graph nicht sehr dicht ist, was ja in unserer Situation der Fall ist.

Korollar 1. Es seien A_{1}, …, A_{r} Ereignisse wie oben. Die A_{i} seien von fast allen anderen A_{j}, mit höchstens d Ausnahmen, wechselseitig unabhängig. Der Abhängigkeitsgraph hat also maximalen Grad d (maximale Anzahl von Kanten, die von einer Ecke ausgeht). Es sei p(A_{i}) ≤ p für 1 ≤ i ≤ r. Falls

ep(d + 1) ≤ 1

gilt, dann gilt auch

p(⋀_{i=1}^{r} Ā_{i}) > 0.

Zum Beweis des Korollars: Für d = 0 (leerer Graph) ist alles klar, für d ≥ 1 setze man für

x_{i} = \frac{1}{d+1} < 1. Man beachte (1 − \frac{1}{d+1})^{d} > \frac{1}{e}. Bei der Anwendung auf die van der Waerden Zahlen sehen wir nun: Eine arithmetische Progression der Länge k schneidet höchstens nk andere Progressionen. (Gehen wir zu dem Schnittpunkt, von dort kann es höchstens n andere Progressionen geben. Andererseits kommen bei jeder Progression k Punkte als Schnittpunkte in Frage.) Um das Korollar anwenden zu können, muss also p = \frac{1}{2^{k−1}} < \frac{1}{e(nk+1)} gelten. Dies ist für

n < \frac{2^{k}}{2ek}(1 + o(1)) gegeben.

3 Der Satz von Roth bzw. der Satz von Szemerédi für k = 3

Erdős und Turán [14] betrachteten für sehr kleine Intervalle [1, n] die maximale Anzahl r_{3}(n) von Zahlen, die keine arithmetische Progression der Länge 3 enthalten. So bewiesen sie für n ≥ 8, dass r_{3}(2n) ≤ n gilt, und verbesserten dies schrittweise für genügend große n zu r_{3}(n) < (\frac{3}{8} + ε)n. Sie vermuteten, dass man so im Prinzip zu immer besseren Schranken komme, dass also r_{3}(n) = o(n) gilt. Insbesondere hoffte man anfangs, durch gute Schranken bei diesem Problem auch die Schranken im van der Waerden Problem zu verbessern. Eine weitere Motivation war, dass man auch die Existenz beliebig langer Progressionen in der Menge der Primzahlen nachweisen wollte. Falls man nämlich nachweisen kann, dass für die maximale Anzahl r_{k}(n) von Zahlen im Intervall [1, n], die keine arithmetische Progression der Länge k enthalten, r_{k}(n) = o (\frac{n log log n}{log n}) gilt, so folgt, dass es Primzahlprogressionen

beliebiger Länge geben muss. (Für r_{k}(n) = o (\frac{n}{log n}) folgt dies sofort aus den Tschebyscheffschranken π(n) ≫ \frac{n}{log n}. Für die Verfeinerung vergleiche man [17].) Erdős setzte einen Preis von $1000 für folgende Vermutung aus:

Vermutung 1.

r_{k}(n) = o(n).

Auch wenn die Vermutung nach Erdős und Turán benannt ist, so bekommt man beim Lesen von [14] den Eindruck, dass die Vermutung vielleicht eher von Szekeres stammt. Darüber hinaus vermutete er:

Vermutung 2 (Erdős, $3000). Sei (a_{i}) eine monoton wachsende Folge und ∑_{i} \frac{1}{a_{i}} sei divergent. Dann enthält die Folge arithmetische Progressionen beliebiger Länge.

Diese Vermutung impliziert natürlich den Fall der Primzahlen. Die Erdős-Turán Vermutung wurde von Roth für k = 3 bewiesen. Der Beweis benutzte die Hardy-Littlewoodsche Kreismethode.

Satz 7 (Roth, [32]). Es sei A eine Menge positiver Zahlen mit positiver oberer Dichte. Dann enthält A eine arithmetische Progression der Länge 3. Sei andersherum r_{3}(n) die größte Anzahl von Zahlen im Intervall [1, n], die keine arithmetische Progression der Länge 3 haben, dann gilt r_{3}(n) = o(n). Genauer gilt sogar r_{3}(n) = O (\frac{n}{log log n}).

Dies wurde wie folgt verbessert.

Satz 8 (Szemerédi [42], Heath-Brown [27]). Es gibt eine positive Konstante c, so dass r_{3}(n) = O (\frac{n}{(log n)^{c}} ) gilt.

Das derzeit stärkste Ergebnis ist:

Satz 9 (Bourgain, [8]). Es gilt r_{3}(n) = O (_{\frac{n}{( \frac{log n}{log log n} )^{1/2}}} ).

Folgende untere Schranken sind bekannt. Man beachte, dass zwischen der oberen und unteren Schranke noch viel Raum für Verbesserungen ist.

Satz 10 (Behrend, [4]). Es gibt eine positive Konstante c, so dass gilt:

r_{3}(n) ≥ \frac{n}{exp (c(log n)^{1/2})}.

(Der Beweis ist geometrisch sehr anschaulich. Man legt eine Menge von Punkten auf eine (hochdimensionale) Sphäre. Geraden durch diese Punkte schneiden die Menge natürlich in keinem dritten Punkt. Auf Details gehen wir hier nicht ein.) Man hätte vermuten können, dass es für Mengen mit mindestens N^{α} vielen Elementen zumindest für α > \frac{1}{2} immer Progressionen der Länge 3 gibt. Es gibt dann ja N^{2α} viele Paare, und die Chance, dass bei derart vielen Paaren wenigstens einmal das dritte Element dann auch zur Menge gehört, ist gut. Die untere Schranke zeigt also, dass der probabilistisch typische Fall und der extremale Fall weit voneinander entfernt sind. Ob der extremale Fall sich aber durch eine geometrische Konstruktion beschrieben läßt, ist natürlich keineswegs klar. (Sollte jemand also einen probabilistischen Beweis von 200 Seiten Länge für eine besser untere Schranke angeben, wird der Beweis wohl schon alleine deswegen falsch sein!) Soweit zum Fall k = 3. Szemerédi bewies den Fall k = 4 mit kombinatorischen Methoden. Roth gab später einen analytischen Beweis an. Diese Beweise sind leider sehr kompliziert. Schließlich bewies Szemerédi den allgemeinen Fall und verdiente sich damit den ausgesetzten Preis. (Meines Wissens ist $1000 der höchste Erdős-Preis der jemals ausgezahlt wurde. (Die Wirsingschen $10^{10} wurden ja natürlich nicht ausgezahlt.)

Satz 11 (Szemerédi, [41]). Es gilt r_{k}(n) = o(n).

Da Szemerédi die schlechten Schranken von dem van der Waerden Beweis verwendet, erhält er keine obere Schranke vom Typ r_{k}(n) = O (\frac{n}{log log... log n}). Seine Schranke ist nur so extrem wenig besser als o(n), dass dies niemand genau ausgearbeitet hat. Später gab Fürstenberg einen ergodentheoretischen Beweis an. Für Leute, die sich mit den Methoden auskennen, ist dieser Beweis sicher leichter. Es gab auch einige Verllgemeinerungen von Szemerédi’s Satz, z.B. auf mehrdimensionale Strukturen oder auf polynomiale Werte, die meistens zunächst mittels der ergodentheorie bewiesen wurden. Leider liefert diese Methode abger grundsätzlich nur ein o(n) und keine besseren Schranken. Die Arbeit von Gowers, die im wesentlichen Methoden der harmonischen Analyse verwendet, liefert für alle k

r_{k}(n) = O_{k} (\frac{n}{(log log n)^{c_{k}}} ) !!

Dies war ja nicht einmal für k = 4 bekannt! Gowers beschreibt Roths Arbeit so: es gelingt Unterprogressionen der Länge \sqrt{N} zu finden, auf denen die Dichte der Menge ein bisschen zugenommen hat. Wenn man das ein paar Mal iteriert, nimmt die Dichte weiter zu. Allerdings gibt die starke Abnahme der Länge der Folge eine Grenze an, wie oft man iterieren kann. Diese Idee verwendet Gowers, allerdings sehr viel effizienter. Wie dem auch sei, auch Szemerédis Beweis wird überleben. Er enthält nämlich zwei wichtige Lemmata, die wiederum selber zum Forschungsgegenstand und wichtigen Hilfsmittel bei anderen Fragen wurden: das Regularity Lemma der Graphentheorie (siehe [7]) und das Cube Lemma. Gowers [19] bewies übrigens auch, und das war unerwartet, dass die schwachen Abschätzungen beim Regularity Lemma nicht wesentlich verbessert werden können. Er bewies also, dass es untere Schranken vom Turmexponentialtyp gibt. Dadurch war klar, dass es nicht reicht, Szemerédis Beweis zu verfeinern, um zu einer wesentlich besseren Schranke zu kommen. Wir begnügen uns beim Beweis mit r_{3}(n) = o(n). Den Beweis führen wir nach [26]. Wir nennen M ∈ A einen Würfel, wenn es einen Aufpunkt a und Seitenlängen d_{i} derart gibt, dass gilt:

M(a; d_{1}, …, d_{l}) = {a + ∑_{i=1}^{l} ε_{i}d_{i} : ε_{i} ∈ {0, 1}} .

(Man beachte, dass A ⊂ ℕ gilt, dass der Würfel also nur eine gedachte mehrdimensionale Struktur auf der eindimensionalen Zahlengeraden ist.)

Lemma 2 (Cube Lemma). Sei A ⊂ [1, n] mit |A| ≥ cn. Dann gibt es einen Würfel der Dimension l = log log n + O(1) mit M ⊂ A.

Beweisskizze: Es sei |A| = α_{0}. Es gibt \binom{α_{0}}{2} Differenzen a_{1} − a_{2}, a_{1} ∈ A, a_{2} ∈ A\\{a_{1}\}, die positiv sind. Da wegen A ⊂ [1, n] nur n − 1 verschiedenen Differenzen in Frage kommen, muss es eine

Differenz d_{1} geben, die mindestens \frac{\binom{α_{0}}{2}}{n − 1} mal vorkommt. Wir bilden

A_{1} = {a ∈ A : a + d_{1} ∈ A}.

Es gilt |A_{1}| ≥ α_{1} := \frac{\binom{α_{0}}{2}}{n − 1}. Analog finden wir eine häufige Differenz d_{2}, so dass

A_{2} = {a ∈ A_{1} : a + d_{2} ∈ A_{1}} = {a + ε_{1}d_{1} + ε_{2}d_{2} ∈ A, ε_{i} ∈ {0, 1}}.

Auf diese Weise schachtelt man immer größere Würfel ineinander:

A_{l} ⊂ A_{l−1} ⊂ … ⊂ A_{1} ⊂ A

mit d_{i} + A_{i} ⊂ A_{i−1}, |A_{i}| ≥ α_{i}, wobei α_{i} = \frac{\binom{α_{i−1}}{2}}{n − 1} gilt.

Es ist α_{1} ≥ \frac{cn(cn − 1)}{2(n − 1)} ≈ \frac{c^{2}n}{2} und analog α_{i} ≈ \frac{c^{2^{i}}n}{2^{2^{i}−1}} . (Genaugenommen verliert man in

jedem Schritt noch ein ganz kleines bisschen. Es ist etwas aufwendig, dies ganz genau zu machen. Man könnte dies mit ε ausdrücken.) Falls α_{i} ≥ 1 kann man auch im i-ten Schritt noch ein d_{i} wählen. Die Schrittanzahl ist daher wegen log log (\frac{2}{c})^{2^{l}} ≈ log log n ungefähr l ≈ \frac{log log n}{log 2} + log log \frac{2}{c}, also für großes n auf jeden Fall größer als log log n.

Es ist erstaunlich einfach nachzuwesien, dass der Grenzwert lim_{n→∞} \frac{r_{k}(n)}{n} existiert. Das Problem ist nachzuweisen, dass er gleich Null ist.

Lemma 3 (Subadditivität). Der Grenzwert lim_{n→∞} \frac{r_{k}(n)}{n} existiert. Darüber hinaus gilt lim_{m→∞} \frac{r_{k}(m)}{m} ≤ \frac{r_{k}(n)}{n}.

Proof. Aus der Definition von r_{k}(n) folgt unmittelbar, dass

r_{k}(m + n) ≤ r_{k}(m) + r_{k}(n),

denn bei dem längeren Intervall können ja noch Progressionen aufreten, die in keinem der Teile auftreten. Es folgt also r_{k}(2n) ≤ 2r_{k}(n) bzw. induktiv das Analogon für andere Vorfaktoren. Wir zerlegen m wie folgt: m = [\frac{m}{n}] n+(m−[\frac{m}{n}] n). Man beachte, dass (m−[\frac{m}{n}] n) < n gilt. Daher ist

r_{k}(m) ≤ r_{k}(n) [\frac{m}{n}] + r_{k}(m − n [\frac{m}{n}]) ≤ r_{k}(n)\frac{m}{n} + n.

Daraus folgt

\frac{r_{k}(m)}{m} ≤ \frac{r_{k}(n)}{n} + \frac{n}{m}.

Dies gilt für alle m. Also gilt auch

lim sup_{m→∞} \frac{r_{k}(m)}{m} ≤ \frac{r_{k}(n)}{n}.

Da dies nun auch für alle n gilt, folgt auch

lim sup_{m→∞} \frac{r_{k}(m)}{m} ≤ lim inf_{n→∞} \frac{r_{k}(n)}{n}.

Der Grenzwert existiert also, d.h. es ist lim sup = lim inf. Dann aber folgt wegen

lim_{m→∞} \frac{r_{k}(m)}{m} ≤ \frac{r_{k}(n)}{n}

auch die zweite Behauptung.

Proof. Wir beweisen nun den Satz von Roth. Angenommen es sei c = lim_{n→∞} \frac{r_{3}(n)}{n} > 0, so gilt wegen der Subadditivität r_{3}(n) ≥ cn. Wir setzen ε = 10^{−10}c^{2}, und n_{0} sei groß. Für alle genügend großen n ≥ n_{1} ≥ n_{0} gilt

c ≤ \frac{r_{3}(n)}{n} ≤ c + ε.

Hinweis: später benötigen wir, dass \frac{c^{2} log log n}{100} > n_{0} gilt. Es sei nun A ⊂ [1, n] eine Menge mit |A| = r_{3}(n) ≥ cn, aber ohne Progression der Länge 3. Die Folge muss einigermaßen gleichmäßig verteilt sein. Wir überlegen uns kurz, dass A im Intervall (0.49n, 0.5n) mindestens Dichte \frac{c}{2} haben muss, (genaugenommen sogar fast c). Das Intervall [1, 0.49n] hat höchstens (c + ε)0.49n Elemente mit A gemeinsam. Das Intervall [0.5n, n] hat höchstens (c + ε)n − \frac{c}{2}n Elemente mit A gemeinsam. (An der oberen Grenze n eine obere Schranke verwenden und davon eine untere Schranke für die untere Grenze 0.5n abziehen.) Da es insgesamt in [1, n] aber mindestens cn viele Elemente in A gibt, muss also (0.49n, 0.5n) ∩ A mindestens

cn − (c + ε)0.49n − ((c + ε)n − \frac{c}{2}n) = \frac{cn}{100} − \frac{149εn}{100} ≥ \frac{cn}{2 × 100}

viele Elemente enthalten.

Dieses war die erste Aufspaltung des Intervalls in Teile. Es werden noch einige folgen. Wir spalten (0.49n, 0.5n) in Intervalle der Größe [\sqrt{n}] auf. Mindestens eines dieser Intervalle muss Dichte \frac{c}{2} haben. Das Cube Lemma garantiert, dasss es einen Würfel gibt mit folgenden Eigenschaften:

1. M(a; d_{1}, …, d_{l}) ⊂ A ∩ (0.49n, 0.5n). (Genauer: sogar in diesem Teilintervall der Länge [\sqrt{n}].)

2. l = log log[\sqrt{n}] + O(1) = log log n + O(1).

3. d_{i} ≤ 2\sqrt{n} für i = 1, …, l.

Wir setzen M_{−1} = {a}, wobei ja a ∈ (0.49n, 0.5n). Schrittweise bauen wir wie im Beweis des Cube Lemma die Kette von Würfeln auf:

M_{i} = M(a; d_{1}, …, d_{i}), 0 ≤ i ≤ l.

Da in A keine arithmetische Progression der Länge 3 vorkommt, ist mit x, m ∈ A automatisch y = 2m−x ∉ A. Da nun A einen großen Würfel enthält, kann man daraus eine große Struktur von derart verbotenen Elementen y ableiten. Wir notieren in jedem Schritt die verbotenen Elemente.

N_{i} = {2m − x : x ∈ (A ∩ [1, a]), m ∈ M_{i}}.

Da ja in A gerade diese Elemente verboten sind, gilt A ∩ N_{i} = ∅. Es gilt also

|N_{i}| ≥ |N_{−1}| = |{2a − x : x ∈ A ∩ [1, a]}| = |A ∩ [1, a]| ≥ 0.49cn.

Da M_{i+1} = M_{i} ∪ (M_{i} + d_{i}) gilt analog N_{i+1} = N_{i} ∪ (N_{i} + 2d_{i}). Da die |N_{i}| monoton wachsen, aber natürlich nach oben beschränkt sind, |N_{l}| ≤ n, muss es einen Schritt i → i + 1 geben, wo

|N_{i+1}\N_{i}| < \frac{n}{l}.

(Natürlich gilt sogar etwas Strengeres, nach obigen Bemerkungen über N_{−1}.) Eine arithmetische Progression B = {x, x + 2d_{i}, x + 4d_{i}, …, x + s(2d_{i})} mit Differenz nennen wir einen Block. Ist B in N_{i} aber, x + (s + 1)2d_{i} ∈ N_{i+1}\N_{i}, so nenenn wir den Block einen maximalen Block. Man beachte, dass also maximale Blöcke in N_{i} und Elemente in N_{i+1}\N_{i} bijektiv zugeordnet sind. Wir können also Blöcke zählen, indem wir Elemente zählen. Außerdem ist die Anzahl der Blöcke im Kompliment [1, n]\N_{i} gleich (bis auf evtl. einen am Rand). Da also |N_{i+1}\N_{i}| < \frac{n}{l} gilt, wissen wir jetzt, dass die Anzahl der maximalen Blöcke in [1, n]\N_{i} ebenfalls höchstens \frac{n}{l} + 1 beträgt. Nun, kommt eine letzte Aufteilung. Wir teilen [1, n] in 2d_{i} Klassen modulo 2d_{i} ein. Dann haben wir [1, n]\N_{i} in höchstens \frac{n}{l} + 2d_{i} ∼ \frac{n}{l} Blöcke geteilt, (da d_{i} ≤ 2\sqrt{n} und l ≈ log log n). Wir zählen zunächst die Anzahl aller Elemente in kurzen Blöcken mit Länge von höchstens \frac{c^{2}l}{100}. Die Anzahl beträgt also insgesamt höchstens \frac{c^{2}n}{100}(1 + o(1)). Die anderen, langen Blöcke sind lang genug, um zu garantieren, dass die Dichte der Menge A auf ihnen höchstens c + ε beträgt. (Denn wenn ein langer Block zu große Dichte hat, kann man ihn (und entsprechend A ja durch eine affine Transformation auf ein Intervall [1, r] abbilden. Wenn r groß genug ist, hat dort A′ höchstens Dichte c + ε. Ganz oben wählten wir n ≥ n_{1} ≥ n_{0} groß genug, damit dieses Argument keine Probleme macht.)

Wir zählen nun abschließend alle Elemente in A und erhalten einen Widerspruch:

|A| = |A ∩ [1, n]|

= |A ∩ ([1, n]\N_{i})| da A ∩ N_{i} = ∅

= Anzahl der Elemente in kurzen und langen Blöcken

< \frac{c^{2}n}{100}(1 + o(1)) + (c + ε)(n − |N_{i}|)

= \frac{c^{2}n}{100}(1 + o(1)) + cn − 0.49c^{2}n + εn − ε|N_{i}| + o(n)

< cn

da ε oben sehr klein gewählt war; ε = \frac{c^{2}}{4} sollte auch bereits ausreichen. Dieser Widerspruch beweist also, dass r_{3}(n) = o(n) gilt.

Wir hoffen, dass dem Leser durch die parallele Betrachtung von dem Satz von van der Waerden und dem Satz von Roth bzw. Szemerédi auch die gegenseitige Abhängigkeit aufgefallen ist. Der Satz von Szemerédi ist der stärkere Satz. Man bezeichnet diese Form von Satz auch als Dichteversion der endlichen van der Waerden Version. Aus dem Satz von Szemerédi folgt der satz von van der Waerden. Beweistechnisch benutzte Szemerédi allerdings den Satz von van der Waerden. Es gibt in der kombinatorischen Zahlentheorie eine ganze Reihe von Arbeiten, die andere Muster als Progressionen vermeiden. Man kann ja eine Progression der Länge 3 auch als Lösung der Gleichung a_{1} +a_{3} = 2a_{2} mit a_{1}, a_{2}, a_{3} ∈ A auffassen. Derartige Gleichungen kann man natürlich weit verallgmeinern, wobei dann die Progressionsstruktur verloren geht. Hierzu gibt es Arbeiten von Rado (die Hunderte weiterer Arbeiten hervorrief, Chung, Graham, Ruzsa, Schoen, Łuczak und vielen anderen. Bei der umfangreichen Bibliographie habe ich diesen Themenkreis nicht berücksichtigt. Arbeiten von Angehörigen der TU Clausthal zu diesem Themenkreis: Klotz, W.: Generalization of some theorems on sets of multiples and primitive sequences. Acta Arith. 32 (1977), 15–26. Lucht, L.G.: Dichtentheoretische Sätze der Zahlentheorie. J. Reine Angew. Math. 243 (1970), 192–218 und Band 244 (1970), 220. Ich selber arbeite daran, interessante Muster in der Menge der Primzahlen nachzuweisen. Dazu gibt es z.B. die Arbeit Elsholtz, C.: Triples of primes in arithmetic progressions (2001).

Die Ausarbeitung stützt sich erheblich auf das Buch Ramseytheorie von Graham et. al. Für die Vorträge stand mir leider nur die erste Auflage zur Verfügung. In der zweiten Auflage befindet sich die Verbesserung von Shelah zu den verbesserten van der Waerden Zahlen. Ich danke Prof. Hilgert, Prof. Lucht und Prof. Sander und dem Oberseminar Zahlentheorie für die Rückfragen, die zu einer Verbesserung der Darstellung führten.

Literatur

[1] Ajtai, M.; Szemerédi, E.: Sets of lattice points that form no squares. Stud. Sci. Math. Hungar. 9 (1974), 9–11 (1975).

[2] Alon, N.; Spencer, J. H.: The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1992. xvi+254 pp.

[3] Anderson, P.G.: A generalization of Baudet’s conjecture (van der Waerden’s theorem). Amer. Math. Monthly 83 (1976), 359–361.

[4] Behrend, F.A.: On sets of integers which contain no three in arithmetic progression, Proc. Nat. Acad. Sci. 23 (1946), 331–332.

[5] V. Bergelson, A. Leibman, Polynomial extensions of van der Waerden’s and Szemerédi’s theorems, J. Amer. Math. Soc. 9 (1996), 725–753.

[6] Berlekamp, E. R.: A construction for partitions which avoid long arithmetic progressions. Canad. Math. Bull. 11 1968 409–414.

[7] Bollobás, B.: Modern graph theory. Graduate Texts in Mathematics, 184. Springer-Verlag, New York, 1998. xiv+394 pp.

[8] Bourgain, J.: On triples in arithmetic progression. Geom. Funct. Anal. 9 (1999), no. 5, 968–984.

[9] Burkill, H.; Mirsky, L.: Monotonicity. J. Math. Anal. Appl. 41 (1973), 391–410.

[10] Deuber, W.: On van der Waerden’s theorem on arithmetic progressions. J. Combin. Theory Ser. A 32 (1982), no. 1, 115–118.

[11] Deuber, W. und Voigt, B.: Der Satz von van der Waerden über arithmetische Progressionen, Jahresber. Deutsch. Math.-Verein. 85 (1983), 66–85.

[12] Erdős, P.; Graham, R. L.: Old and new problems and results in combinatorial number theory: van der Waerden’s theorem and related topics. Enseign. Math. (2) 25 (1979), no. 3-4, 325–344 (1980).

[13] Erdős, P.; Graham, R. L.: Old and new problems and results in combinatorial number theory. Monographies de L’Enseignement Mathématique, 28. Université de Genève, 1980. 128 pp.

[14] Erdős, P.; Turán, P.: On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.

[15] Fürstenberg, H.: Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204–256.

[16] Fürstenberg, H.; Katznelson, Y.; Ornstein, D.: The ergodic theoretical proof of Szemerédi’s theorem. Bull. Amer. Math. Soc. (N.S.) 7 (1982), no. 3, 527–552.

[17] Gerver, J. L.: The sum of the reciprocals of a set of integers with no arithmetic progression of k terms. Proc. Amer. Math. Soc. 62 (1977), no. 2, 211–214.

[18] Gerver, Joseph L.; Ramsey, L.: Thomas Sets of integers with nonlong arithmetic progressions generated by the greedy algorithm. Math. Comp. 33 (1979), no. 148, 1353–1359.

[19] Gowers, W. T.: Lower bounds of tower type for Szemerédi’s uniformity lemma. Geom. Funct. Anal. 7 (1997), no. 2, 322–337.

[20] Gowers, W. T.: Fourier analysis and Szemerédi’s theorem. Proceedings of the International Congress of Mathematicians, Vol. I (Berlin, 1998). Doc. Math. 1998, Extra Vol. I.

[21] Gowers, W. T.: A new proof of Szemerédi’s theorem for arithmetic progressions of length four. Geom. Funct. Anal. 8 (1998), no. 3, 529–551.

[22] Gowers, W. T.: Rough structure and classification. GAFA 2000 (Tel Aviv, 1999). Geom. Funct. Anal. 2000, Special Volume, Part I, 79–117.

[23] Gowers, W. T.: A new proof of Szemerédi’s theorem. Geom. Funct. Anal. 11 (2001), no. 3, 465–588.

[24] Graham, R. L.: Arithmetic progressions: from Hilbert to Shelah. A joint AMS-MAA lecture presented in Phoenix, Arizona, January 1989. AMS-MAA Joint Lecture Series. American Mathematical Society, Providence, RI, 1989. 1 videocassette (NTSC; 1/2 inch; VHS) (60 min.)

[25] Graham, R. L.; Rothschild, B. L.: A short proof of van der Waerden’s theorem on arithmetic progressions. Proc. Amer. Math. Soc. 42 (1974), 385–386.

[26] Graham, R. L.; Rothschild, Bruce L.; Spencer, Joel H.: Ramsey theory. Wiley-Interscience Series in Discrete Mathematics. New York, 1980. (2. Auflage 1990).

[27] Heath-Brown, D.R.: Integer sets containing no arithmetic progressions, J. London Math. Soc. (2) 35 (1987), 385–394.

[28] Nešetřil, J.: Ramsey theory. Handbook of combinatorics, Vol. 1, 2, 1331–1403, Elsevier, Amsterdam, 1995.

[29] Rankin, R.A.: Sets of integers containing not more than a given number of terms in arithmetical progression Proc. R. Soc. Edinb., Sect. A 65 (1965), 332-344.

[30] Riddell, J. A lattice point problem related to sets containing no l-term arithmetic progression. Canad. Math. Bull. 14 (1971), 535–538.

[31] Roth, K.F.: Sur quelques ensembles d’entiers. (French) C. R. Acad. Sci. Paris 234, (1952). 388–390.

[32] Roth, K. F.: On certain sets of integers. J. London Math. Soc. 28, (1953). 104–109.

[33] Roth, K. F.: On certain sets of integers. II. J. London Math. Soc. 29, (1954). 20–26.

[34] Roth, K. F.: Irregularities of sequences relative to arithmetic progressions. IV. Period. Math. Hungar. 2 (1972), 301–326.

[35] Shelah, S.: Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1 (1988), 683–697.

[36] Soifer, A.: Pierre Joseph Henry Baudet: Ramsey theory before Ramsey. Geombinatorics 6 (1996), no. 2, 60–70.

[37] Szemerédi, E.: On sets of integers containing no four elements in arithmetic progression. Acta Math. Acad. Sci. Hungar. 20, (1969) 89–104.

[38] Szemerédi, E.: On sets of integers containing no four elements in arithmetic progression. 1970 Number Theory (Colloq., János Bolyai Math. Soc., Debrecen, 1968) pp. 197-204 North-Holland, Amsterdam

[39] Szemerédi, E.: On sets of integers containing no k elements in arithmetic progression. Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974), Vol. 2, pp. 503–505. Canad. Math. Congress, Montreal, Que., 1975.

[40] Szemerédi, E.: The number of squares in an arithmetic progression. Studia Sci. Math. Hungar. 9 (1974), no. 3-4, 417 (1975).

[41] Szemerédi, E.: On sets of integers containing no k elements in arithmetic progression. Acta Arith. 27 (1975), 199–24.

[42] Szemerédi, E.: Integer sets containing no arithmetic progressions. Acta Math. Hungar. 56 (1990), no. 1-2, 155–158.

[43] Thouvenot, Jean-Paul: La démonstration de Furstenberg du théorème de Szemerédi sur les progressions arithmétiques. (French) Séminaire Bourbaki, 30e année (1977/78), Exp. No. 518, pp. 221–232, Lecture Notes in Math., 710, Springer, Berlin, 1979.

[44] Vaughan, R.C.: The Hardy-Littlewood Method (2nd ed.), Cambridge Tracts in Mathematics 125, CUP 1997.

[45] van der Waerden, B.L.: Beweis einer Baudetschen Vermutung. Nieuw Arch. Wisk. 15 (1928), 212–216.

[46] van der Waerden, B.L.: Wie der Beweis der Vermutung von Baudet gefunden wurde. Elemente der Math. 9 (1954), 49–56; Reprint Elem. Math. 53 (1998), no. 4, 139–148.

[47] van der Waerden, B. L.: Wie der Beweis der Vermutung von Baudet gefunden wurde. Abh. Math. Sem. Univ. Hamburg 28 (1965), 6–15. Englische Übersetzung in Studies in Pure Mathematics (Presented to Richard Rado), 251–260, Academic Press, London, 1971.

[48] Wagstaff, S. S.: Some questions about arithmetic progressions. Amer. Math. Monthly 86 (1979), no. 7, 579–582.

[49] Walters, M.: Combinatorial proofs of the polynomial van der Waerden theorem and the polynomial Hales-Jewett theorem. (English. English summary) J. London Math. Soc.

(2) 61 (2000), no. 1, 1–12.