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: 1m50s

Setup

Let $W(r,s)$ denote the least integer $n$ such that every coloring of ${1,\ldots,n}$ with $r$ colors contains a monochromatic arithmetic progression of length $s$. We must prove

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

It is enough to construct, for infinitely many $k$, a $k$-coloring of an interval of length

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

that contains no monochromatic arithmetic progression of length $k$, where $c>0$ is an absolute constant.

Solution

Choose a coloring of ${1,\ldots,n}$ at random, independently assigning each integer one of the $k$ colors with probability $1/k$.

For every arithmetic progression

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

of length $k$, let $E_A$ be the bad event that all elements of $A$ receive the same color. The probability of this event is

$$ \Pr(E_A)=k\left(\frac1k\right)^k=k^{1-k}. $$

The random coloring is suitable precisely when none of the events $E_A$ occurs.

We apply the symmetric form of the Lovász Local Lemma. The event $E_A$ depends only on the colors assigned to the $k$ positions in $A$. Therefore $E_A$ is independent of every $E_B$ for which $A$ and $B$ have no common element.

It remains to bound the number of progressions that can intersect a fixed progression. Fix an integer $x\in{1,\ldots,n}$. A $k$-term arithmetic progression containing $x$ is determined by the position of $x$ inside the progression and by its common difference. There are $k$ possible positions. If the common difference is $d$, then

$$ (k-1)d\le n-1, $$

$$ d\le \frac{n-1}{k-1}<n. $$

Hence the number of $k$-term arithmetic progressions containing $x$ is less than

$$ kn. $$

A fixed progression $A$ contains $k$ elements, and every progression $B$ dependent on $A$ must contain at least one of them. Thus the dependency degree is bounded by

$$ D<k(kn)=k^2n. $$

The symmetric Lovász Local Lemma applies if

$$ e(D+1)p\le1. $$

Using the above estimates, it is sufficient that

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

For $k\ge2$ we have $k^2n+1\le2k^2n$ whenever $n\ge1$, so it is enough that

$$ 2e k^2n,k^{1-k}\le1. $$

After simplifying,

$$ 2en,k^{3-k}\le1. $$

Therefore the Local Lemma permits every value of $n$ satisfying

$$ n\le \frac{k^{k-3}}{2e}. $$

In particular, for sufficiently large $k$,

$$ \frac{k^{k-3}}{2e}> c\left(\frac{k}{\log k}\right)^{1/2} $$

for any fixed positive constant $c$. Hence there exists a $k$-coloring of

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

with no monochromatic arithmetic progression of length $k$.

By the definition of $W(k,k)$, this implies

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

for some absolute constant $c>0$. Therefore,

$$ \boxed{W(k,k)>\Omega\left(\frac{k}{\log k}\right)^{1/2}}. $$

Verification

The bad event probability was counted from the $k$ possible choices of the common color and the probability that all $k$ positions receive that color:

$$ k\left(\frac1k\right)^k=k^{1-k}. $$

The dependency bound counted every progression meeting a fixed progression. A fixed point lies in fewer than $kn$ progressions, and a fixed progression has $k$ points, giving the valid upper bound

$$ D<k^2n. $$

The Local Lemma condition was reduced to

$$ 2en,k^{3-k}\le1, $$

which allows values of $n$ far larger than the required order

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

Thus the required asymptotic lower bound is a direct consequence of the Local Lemma estimate.

This completes the proof.

∎

Notes

The argument gives a much stronger lower bound than requested. The stated estimate is only the order required by the exercise; the Local Lemma applied directly to monochromatic $k$-term progressions yields a lower bound of order $k^{k-3}$ with the crude dependency estimate above.