Improving the use of cyclic zippers in finding lower bounds for van der Waerden numbers (Q426917)

Summary: For integers \(k\) and \(l\), each greater than 1, suppose that \(p\) is a prime with \(p \equiv 1 \pmod k\) and that the \(k^{\text{th}}\)-power classes \(\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)\). \textit{P.R. Herwig}, \textit{M.J.H. Heule}, \textit{P.M. van Lambalgen}, and \textit{H. van Maaren} [ibid. 14, No. 1, Research paper R6, 18 p. (2007; Zbl 1115.05092)] 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.