Van der Waerden Theorem - Deducing Ackermann function Upper bound

Question

According to the book "Ramsey Theory on the Integers, Landman", the original proof of Van der Waerden's Theorem yields the upper bound ack(n) for w(k;2).

I didn't quite understand the proof that book gave but I read this one and it was quite clear: http://www.sfu.ca/~vjungic/RamseyNotes/sec_proof_vdW.html

Is there a way to deduce this ackermann function upperbound (or a similar one) from the proof in this link?

Answer 1

It's more that there's a bound which grows roughly like the Ackermann function, with some other things happening that are less relevant. (Although I did see the actually-literally-Ackermann bound in Landman and Robertson's book, it's not clear to me if that's meant to be taken literally.)

From the prove you give, let's define $F(\ell, k, r)$ to be the least $M$ such that if $[1,M]$ is $k$-colored, there is either

• a monochromatic $\ell$-term arithmetic progression, or
• $r$ color-focused $(\ell-1)$-term arithmetic progressions.

The proof gives us three inequalities:

1. $F(\ell,k,1) \le 2W(\ell-1,k)$.
2. $F(\ell,k,r) \le 2 F(\ell, k, r-1) \cdot W(\ell-1, k^{2 F(\ell,k,r-1)})$.
3. $W(\ell,k) \le 2 F(\ell,k,k)$.

Define two related functions $w(\ell,k)$ and $f(\ell,k,r)$ by:

1. $f(\ell,k,1) = w(\ell-1,k)$.
2. $f(\ell,k,r) = w(\ell-1, f(\ell,k,r-1))$.
3. $w(\ell,k) = f(\ell,k,k)$.

These are a sort of "lower bound on the upper bound": we have stripped away the less-relevant parts of the recursions in the upper bounds on $W$ and $F$. In one sense, $w$ and $f$ will end up much smaller than $W$ and $F$: where $F(\ell,k,r)$ has a $k^{2 F(\ell,k,r-1)}$ in its recursion, $f(\ell,k,r)$ just has $f(\ell,k,r-1)$. But when we get to Ackermann-sized bounds, the difference between these two things is insignificant, so $w$ and $f$ still capture the essence of the growth rate of $W$ and $F$.

So where does the Ackermann function come in? Well, the recurrence for $f$ and $w$ unpacks into $$ w(\ell,k) = w(\ell-1, w(\ell-1, w(\ell-1, \dots w(\ell-1,k)\dots))) $$ with $k$ applications of $w$, and the Ackermann function satisfies $A(m,n) = A(m-1,A(m,n-1))$ and $A(m,0) = A(m-1,1)$ from which we get $$ A(m,n) = A(m-1, A(m-1, A(m-1, \dots A(m-1,1)\dots))) $$ with $n$ applications of $A$. These aren't quite the same, and may not have the same base cases (actually, I haven't said what the base case for $w$ is). But they will still follow the same pattern that $A(m,\bullet)$ is a nested application of $A(m-1,\bullet)$ and $w(\ell,\bullet)$ is a nested application of $w(\ell-1,\bullet)$. If at one "level" (one value of $m$ or of $\ell$ respectively) the function grows like addition, then at the next it will grow like multiplication, at the next like exponentiation, at the next like power towers, and so on through the Knuth up-arrows.