Results on van der Waerden numbers, arrangements, the local lemma and cyclic colourings, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Van der Waerden's theorem with a recursive bound — Theorem 2.1. W_r(k) <= F(r,k) for an explicit recursion; W_r(1) = 1, W_r(2) = r + 1, W_1(k) = k.
• Digit product — Proposition 3.1. A two-colouring of Z/NZ without monochromatic k-term progressions gives W_r(k) > N^floor(log2 r).
• Many colours — Theorem 4.1. W_r(k) > exp((log r)^2 / (64 log 2)) for r >= 256 and k >= 3.
• Sign vectors of affine functions — Lemma 1.1. s affine functions on R^e realize at most (e+1)^2 (s+1)^e sign vectors in {-,0,+}^s.
• Tails of fair coin flips — Lemma 2.1. For l fair bits, P(|X - l/2| >= l/4) <= 2 exp(-l/8).
• Local lemma (Erdos-Lovasz) — Lemma 3.1. If P(E) <= z_E prod over neighbours (1 - z_F), all events are avoided with positive probability.
• A prime between k and 2k^2 — Lemma 4.1. For large k there is a prime in (k, 2k^2].
• Neighbourhoods of the adaptive mesh — Lemma 3.2. Near an interval of width w, mesh intervals have width at least w/16 and there are at most 49 endpoints.
• Global label words — Lemma 4.1. The number of label words along progressions is exp(O(k^(3/10) log k)).
• Local patterns through a label (OpenAI) — Lemma 4.3. At most (CDh)^(6D) eligible patterns of period h pass through a given label, independently of interval widths.
• Balanced outer colouring (OpenAI) — Proposition 1.1. A colouring of labels balancing light positions of progressions and regular positions of eligible patterns.
• Balanced-or-affine dichotomy (OpenAI) — Theorem 4.1. Every progression sees each outer colour at least k/100 times or has affine centred second coordinates.
• Four occurrences of a key — Lemma 1.1. A box together with an integer squared-norm band occurs at most four times along a progression.
• Cyclic two-colouring (OpenAI) — Theorem 3.1. Z/NZ with N >= k^(ck) has a two-colouring without monochromatic k-term progressions, for all large k.
• Superexponential van der Waerden numbers (OpenAI) — Theorem 4.1. W_r(k) > k^(ck floor(log2 r)) with c = 10^-5 for all large k and every r >= 2.

Reading order

Read the lessons in order; each uses the notation and results of the previous ones.