Skip to main content
3 of 3
deleted 3 characters in body
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114

Yes, this should follow from the elementary bound. The point is that having a Kalmar elementary time bound is "closed under" searches through exponentially large collections.

Suppose $N=W(r,k)$ is least such that if the integers $\{1, 2, \dots, N\}$ are colored, each with one of $r$ different colors, then there are at least $k$ integers in arithmetic progression all of the same color.

Say we have an elementary upper bound $b$ on $N$. Then starting with $n=0$ we just try all $n\le b$, try all possible colorings ($r^n$ many) try all possible $k$-tuples (less than $n^k$ many) and check whether they are same-colored and in arithmetic progression. Once we have an $n$ such that for all colorings we have found such a progression, then $n=N$.

Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114