Improving the Use of Cyclic Zippers in Finding Lower Bounds for van der Waerden Numbers

Abstract

For integers $k$ and $l$, each greater than $1$, suppose that $p$ is a prime with $p\equiv1\,(\textrm{mod}\, k)$ and that the $k^{\rm th}$-power classes $\textrm{mod}\, p$ induce a coloring of the integer segment $[0,\, p-1]$ that admits no monochromatic occurrence of $l$ consecutive members of an arithmetic progression. Such a coloring can lead to a coloring of $[0,\,(l-1)p]$ that is similarly free of monochromatic $l$-progressions, and, hence, can give directly a lower bound for the van der Waerden number $W(k,l)$. P. R. Herwig, M. J. H. Heule, P. M. van Lambalgen, and H. van Maaren have devised a technique for splitting and "zipping" such a coloring of $[0,\, p-1]$ to yield a coloring of $[0,\,2p-1]$ which, for even values of $k$, is sometimes extendable to a coloring of $[0,\,2(l-1)p]$ where both new colorings still admit no monochromatic $l$-progressions. Here we derive a fast procedure for checking whether such a zipped coloring remains free of monochromatic $l$-progressions, effectively reducing a quadratic-time check to a linear-time check. Using this procedure we find some new lower bounds for van der Waerden numbers.