6
$\begingroup$

Van der Waerden's function was proved to have elementary upper bound on growth rate.

Is the Van der Waerden's function itself elementary in the sense of Kalmar?

$\endgroup$
8
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy