TAOCP 7.2.2.2 Exercise 6

Exercise 6. ▶ [HM27] [HM27] Use the Local Lemma to show that $W(k, k) > \Omega(k/(\log k))^{1/2}$.

Verified: yes
Solve time: 1m17s

Setup

Let $[n]={1,2,\ldots,n}$. A $k$-term arithmetic progression (abbreviated $k$-AP) in $[n]$ is a set

$$ P={a, a+d, \ldots, a+(k-1)d} $$

with $d\ge 1$ and $a+(k-1)d\le n$.

Define $W(k,k)$ as the least $n$ such that every red-blue coloring of $[n]$ contains a monochromatic $k$-AP. The goal is to show that there exists a constant $c>0$ such that

$$ W(k,k) \ge c \left(\frac{k}{\log k}\right)^{1/2}. $$

It suffices to construct, for such $n$, a 2-coloring of $[n]$ with no monochromatic $k$-AP.

For each $k$-AP $P\subseteq [n]$, define the bad event $A_P$ that $P$ is monochromatic.

Solution

Color each element of $[n]$ independently red or blue with probability $1/2$ each.

Fix a $k$-AP $P$. The event $A_P$ occurs exactly when all $k$ elements of $P$ receive the same color. The probability is

$$ \mathbb{P}(A_P)=2\cdot 2^{-k}=2^{1-k}. $$

Define a dependency graph on the events ${A_P}$ by joining $A_P$ and $A_Q$ when $P\cap Q\ne \varnothing$. For a fixed $k$-AP $P$, an upper bound on the number of intersecting $k$-APs is obtained as follows.

Each intersection point $x\in P$ belongs to at most $O(n)$ arithmetic progressions of length $k$. Indeed, for a fixed $x$, an AP containing $x$ is determined by a choice of common difference $d\le n$ and a position $1\le i\le k$ such that $x=a+(i-1)d$, which uniquely determines $a$ when $d$ and $i$ are fixed, and yields a valid progression only when $a\ge 1$ and $a+(k-1)d\le n$. Hence the number of choices is at most $kn$.

Since $P$ has $k$ elements, the number of $k$-APs intersecting $P$ is at most

$$ D \le k\cdot kn = k^2 n. $$

Apply the symmetric Lovász Local Lemma in the form: if $p \le 2^{-1} e^{-1}(D+1)^{-1}$ then

$$ \mathbb{P}\left(\bigcap_P \overline{A_P}\right) > 0. $$

It suffices to enforce

$$ e \cdot 2^{1-k} \cdot (k^2 n + 1) \le 1. $$

This inequality holds whenever

$$ k^2 n \le c_1 2^k $$

for an absolute constant $c_1>0$, hence whenever

$$ n \le c_2 \frac{2^k}{k^2}. $$

For every sufficiently large $k$, the bound

$$ \frac{2^k}{k^2} \gg \left(\frac{k}{\log k}\right)^{1/2} $$

holds. Therefore, for

$$ n = \left\lfloor c \left(\frac{k}{\log k}\right)^{1/2} \right\rfloor $$

with $c>0$ sufficiently small, the Lovász Local Lemma condition is satisfied. Hence there exists a red-blue coloring of $[n]$ with no monochromatic $k$-AP.

This implies

$$ W(k,k) > n, $$

which yields the stated bound.

This completes the proof. ∎

Verification

The probability computation uses that each of the $k$ elements in a fixed progression must independently avoid two favorable patterns (all red or all blue), giving probability $2^{1-k}$.

The dependency bound follows from counting, for each fixed point $x$ and each position $i$ in the progression, at most one arithmetic progression with step $d$ passing through $x$, and at most $n$ choices for $d$, yielding at most $kn$ progressions through $x$, hence at most $k^2 n$ that intersect a fixed progression.

The Lovász Local Lemma applies because the events are determined by disjoint sets of independent variables except when progressions intersect, matching the constructed dependency graph.

The final comparison uses only that $2^k$ grows faster than any polynomial in $k$, hence dominates $\left(k/\log k\right)^{1/2}$ for all sufficiently large $k$.

Notes

The bound obtained here is far from sharp. The same probabilistic setup, combined with tighter control of dependencies or entropy compression methods, yields exponentially stronger lower bounds in $k$. The present formulation suffices to demonstrate that van der Waerden numbers grow at least superpolynomially in a direct application of the Local Lemma.