\documentclass[english,12pt]{article}
\usepackage{e-jc}
\specs{P35}{19(2)}{2012}

%\usepackage[T1]{fontenc}
%\usepackage[latin9]{inputenc}
\usepackage{array}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\numberwithin{equation}{section}
\numberwithin{figure}{section}
\newenvironment{lyxcode}
{\par\begin{list}{}{
\setlength{\rightmargin}{\leftmargin}
\setlength{\listparindent}{0pt}% needed for AMS classes
\raggedright
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\normalfont\ttfamily}%
 \item[]}
{\end{list}}

\usepackage{graphicx}

\newcommand{\mathsym}[1]{{}}
\newcommand{\unicode}{{}}

\makeatother

\usepackage{babel}
  \providecommand{\claimname}{Claim}
\providecommand{\theoremname}{Theorem}

\begin{document}

\title{Improving the Use of Cyclic Zippers in \\
Finding Lower Bounds for van der Waerden Numbers}


\author{John Rabung, Mark Lotts\\
\small Department of Computer Science\\[-0.8ex]
\small Randolph-Macon College\\
\small Ashland, VA 23005\\
\small \texttt{jrabung@rmc.edu,~marklotts@rmc.edu}
}

\date{\dateline{Nov 2, 2011}{May 19, 2012}{Jun 6, 2012}}

\maketitle


\begin{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^{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.
\end{abstract}

\section*{\noindent Introduction}

For given positive integers $k$ and $l,$ the van der Waerden
number $W(k,l)$ is the smallest of the integers $N(k,l)$
such that any $k$-coloring of the integer segment $[1,\, N(k,l)]$
is sure to yield a monochromatic set of $l$ consecutive members
of some arithmetic progression. That these numbers $N(k,l)$ exist
was demonstrated constructively by B. L. van der Waerden \cite{vw}
in 1927, but his construction, using double induction, was so loose
as to be unhelpful in any attempt to determine either the size or
the growth rate of $W(k,l)$.

Efforts to locate the numbers $W(k,l)$ have yielded few general
results and a number of computational results for particular values
of $k$ and $l$. Shelah \cite{shelah} and Gowers \cite{gowers}
have shown general primitive recursive upper bounds for $W(k,l)$,
while general results for lower bounds are attributable to Berlekamp
\cite{berlekamp} and Moser \cite{moser}. Because these upper and
lower bounds still do not put very tight constraints on the values
of $W(k,l)$, computational approaches have been used either to
determine some $W(k,l)$ exactly by exhaustive search (see \cite{chvatal,Stevens,beeler,kouril})
or to improve on a lower bound for some $W(k,l)$ by finding ever-larger
values of $n$ for which the integer segment $[1,\, n]$ can be
$k$-colored so that there is no monochromatic instance of $l$
consecutive members of an arithmetic progression (see, for example,
\cite{jrr,dransfield,zipper,heule}).

For convenience we use the term \emph{l-progression} to mean a sequence
of $l$ consecutive members of an arithmetic progression, and
we use \emph{l-string} to mean $l$ consecutive integers. For
given $k$, $l$, and $n$, we follow Herwig et al. \cite{zipper}
in referring to a $k$-coloring of {[}1,\emph{~n}{]} that is
devoid of monochromatic $l$-progressions as a \emph{van der Waerden
certificate} and use the notation $W(k,l,n)$ to represent such
a certificate. Of course, the existence of a certificate $W(k,l,n)$
implies $W(k,l)>n$.

Several recent works have encoded the construction of a van der Waerden
certificate as a constraint satisfiability problem and have used fast
satisfiability-checking algorithms to find improved lower bounds for
van der Waerden numbers. This approach is well explained in a number
of papers (see, for example, \cite{dransfield,kouril-franco,ahmed,heule-walsh}).
Herwig et al. \cite{zipper} used both satisfiability checking and
coloring by $k^{th}$-power classes modulo a prime $p$ (the latter
being a technique introduced in \cite{jrr}) to devise a clever method
for extending some certificates, $W(k,l,n)$, to certificates
$W(k,l,2n)$, thus doubling a lower bound for $W(k,l)$.
Referring to this method as \emph{zipping}, they were able to substantially
improve lower bounds for seven van der Waerden numbers.

In this paper we follow Herwig et al. by starting with certificates
generated, as in \cite{jrr}, via $k^{th}$-power-class coloring modulo
a prime $p$ and then investigating what arithmetic properties
might be preserved through the zipping technique. These arithmetic
properties lead to a certificate-checking technique that is both very
fast and quite reminiscent of checking techniques used in finding
power-class-based certificates. Using this approach we are able to
provide some new lower bounds for van der Waerden numbers.


\section*{Zipping viewed arithmetically}

Herwig et al. \cite{zipper} define a \emph{cyclic certificate} as
a van der Waerden certificate $W(k,l,n)$ that preserves its certificate
property under cyclic translation of its $k$-coloring mod $n$.
Given a cyclic certificate $W(k,l,n)$ they attempt to extend
it to a certificate $W(k,l,2n)$ by applying their \emph{zipping
procedure.} Because every application of this procedure in \cite{zipper}
begins with a cyclic certificate $W(k,l,p)$ derived from the
$k^{th}$-power classes of a prime, $p$, where $p=km+1$ for
some integer $m>0$, we shall focus our discussion on the zipping
of such certificates noting particular arithmetic properties of zipped
colorings that yield a fast mechanism for checking whether the zipping
of a certificate $W(k,l,p)$ does or does not yield a certificate
$W(k,l,2p)$. As indicated in both \cite{jrr} and \cite{zipper},
once such a cyclic certificate is in hand, one can join $l-1$ copies
of it to generate an even longer van der Waerden certificate and a
better lower bound for $W(k,l)$.

Let $\mathbb{Z}_{p}$ represent the ring of integers modulo \ensuremath{p}. That the non-zero elements of $\mathbb{Z}_{p}$ form a cyclic group
under multiplicaton allows us to use the powers of any fixed generator
of this group to generate the $k^{th}$-power classes mod $p$.
We use \ensuremath{\mathbb{Z}_{p}^{*}}
 to represent this cyclic group, and we use \ensuremath{g}
to represent a generator of that group (that is, \ensuremath{g}
 is a primitive root \ensuremath{\text{mod }p}). 
Because \textit{p} is of the form \textit{$km+1$,} the set $\ensuremath{C_{0}}=\ensuremath{\left\{g^{\text{jk}}\,\text{mod\,}p:\, j=1,2,\text{...},m\right\}}$ forms
a subgroup of \ensuremath{\mathbb{Z}_{p}^{*}}
 known as the \emph{$k^{th}$-power residues} mod \textit{p}. The
\ensuremath{k-1}
 cosets of \ensuremath{C_{0}}
 are \ensuremath{C_{i}=\left\{g^{\text{jk}+i}\text{mod}\, p:\, j=1,2,\text{...},m\right\}} 
 with \ensuremath{i=1,2,\text{...},k-1}. Together this collection \ensuremath{\left\{C_{i}:i=0,1,\text{...},k-1\right\}} 
 gives the $k^{th}$\emph{-power classes} mod \textit{p}. Indeed,
we can view these classes as inducing a $k$-coloring on $[1,\, p-1]$
by considering any element $h\in[1,\, p-1]$ to have color $i$
if $h\in C_{i}$ with $i\in[0,\, k-1]$. We extend this $k$-coloring
to $[0,\, p-1]$ by coloring 0 with any of the given $k$ colors.
In the context of devising a cyclic certificate $W(k,l,p)$,\emph{
}the only constraint on coloring 0 is that it must be done so as to
avoid forming a monochromatic $l$-progression, even in a cyclic
sense. 

Given an even integer $k$, a prime \emph{$p\equiv1\,\textrm{mod}$~k,
}and a certificate $W(k,l,p)$ derived from a coloring of $[0,\, p-1]$
via the $k^{th}$-power classes mod \textit{p} \textit{\emph{as
determined by some fixed generator $g_{0}$ of }}$\mathbb{\mathbb{Z}}_{p}^{*}$\textit{,
}\textit{\emph{the following describes the steps of the zipping procedure
as given in \cite{zipper} as they apply to the zipping of }}\textit{W(k,l,p)}\textit{\emph{.
With each step we give our arithmetic interpretation of}}\textit{
}\textit{\emph{that step's action:}}
\begin{enumerate}
\item \textbf{Spreading:} Use the given $k$-coloring of the segment
$[1,\, p]$ to color the odd numbers in $[1,\,2p]$ so that the color
of $2j-1$ in $[1,\,2p]$ is the same as the color of $j$
in the original coloring of $[1,\, p]$ for $j=1,\,2,\ldots,\, p$.
Call this \emph{partial coloring 1} of $[1,\,2p]$.\\
\\
\emph{Comment}: Here we note some minor awkwardness. Although we have
been viewing colorings of integer segments $[1,\, n]$ that begin
at 1, it is arithmetically convenient to translate such a coloring
down by one to the segment $[0,\, n-1]$. We transit between these
two views as we describe the steps of zipping and then interpret them
arithmetically.\emph{}\\
\\
\emph{Arithmetic equivalent}: Use the given $k$-coloring of the
segment $[0,\, p-1]$ to color the even numbers in $[0,\,2p-1]$ by
multiplying the elements of \ensuremath{\mathbb{Z}_{p}^{*}}
by 2 and assigning each number, $2m$ mod $2p$, to class
$C_{(i+t)\,\textrm{mod}\, k}$, where $C_{i}$ is the class to which
$m$ was assigned in the given certificate and $C_{t}$ is the
class to which 2 was assigned in the given certificate. (This is,
of course, the class to which $2m$ belongs as a member of \ensuremath{\mathbb{Z}_{p}^{*}}.) Once again we choose to color 0 arbitrarily. Call this \emph{partial
arithmetic coloring 1} of $[0,\,2p-1]$. \\
\\
Apart from shifting the underlying segment of $p$ numbers from
$[1,\, p]$ to $[0,\, p-1]$ and the consequent interchange of the
terms {}``odd'' and {}``even'' as the coloring is extended to
the doubled segment, this multiplicative step is equivalent to spreading.
Note, though, that the addition of $t$, the index of the $k^{th}$-power
class to which 2 belongs, relabels the colors without altering the
coloring pattern. This is not part of the original spreading step.
\item \textbf{Turning:} Because power-class-based certificates $W(k,l,p)$
display certain symmetries (\cite{zipper} discusses both point symmetry
and reflection symmetry), Herwig et al. highlight these by way of
a grid representation of the certificate wherein rows represent colors,
columns represent the numbers in the segment $[1,\, n]$ or $[1,\,2n]$,
and rows have been arranged so as to clearly demonstrate the symmetry
of the coloring. With this arrangement of rows and the resulting subscript
relabeling of colors (away from power-class labeling), the authors
suggest that partial coloring 1 now be {}``turned upside down''.
That is, under the symmetry-imposed labeling of the $k$ colors
of our certificate as $c_{1},\, c_{2},\ldots,\, c_{k}$, alter partial
coloring 1 by substituting color $c_{k+1-i}$ for each occurrence
of color $c_{i}$ for $i=1,\,2,\ldots,\, k$. Call this \emph{partial
coloring 2} of $[1,\,2p]$.\emph{}\\
\emph{}\\
\emph{Arithmetic equivalent}: Noting that $k$ is even and that
$p$ is a prime of the form $km+1$, we observe that the $k^{th}$-power
class to which \emph{$p-1$} belongs determines whether our
$k$-coloring is point symmetric or reflection symmetric. Given
that $p-1\in C_{h}$, we have that $p-1\equiv g_{0}^{ki+h}\, mod\, p$,
for some $i$ and our chosen generator, $g_{0}$, of \ensuremath{\mathbb{Z}_{p}^{*}}, so that for any number $n\in[1,\, p-1]$ if $n\in C_{j}$, then
$n\equiv g_{0}^{ks+j}\, mod\, p$ for some s and $p-n\equiv(p-1)n\equiv g_{0}^{k(i+s)+h+j}\, mod\, p$.
That is, if $p-1\in C_{h}$ and $n\in C_{j}$, then $p-n\in C_{(h+j)\, mod\, k}$.
Observing that $p-1\equiv-1\equiv g_{0}^{\frac{p-1}{2}}\equiv g_{0}^{\frac{km}{2}}\,(mod$~$p$),
we have that if $m$ is even, then $h=0$, and we get reflection
symmetry. If $m$ is odd, then $h=\frac{k}{2}$, and we get point
symmetry. The {}``turn upside down'' action, then, amounts to interchanging
color classes according to the underlying symmetry. Here it amounts
to shifting class indices by $h$ mod $k$. That is, if in
partial arithmetic coloring 1 a number is colored with color $j$,
change the color of that number to color $(j+h)\, mod\, k$, where
$h$ is either 0 or $\frac{k}{2}$ according as $m$ is even
or odd in the expression of $p$ as $km+1$. Call the resulting
coloring \emph{partial arithmetic coloring 2}.
\item \textbf{Shifting:} Use partial coloring 2 to produce a coloring of
the even numbers of $[1,\,2p]$ by applying the color of $2j-1$ in
partial coloring 2 to the number $2j-1-p\,(mod\,2p)$ for $j=1,\,2,\ldots,p$.
Call this \emph{partial coloring 3} of $[1,\,2p]$. (Note that this
step depends on $p$ being odd and that any attempt to do a second
zipping--a zipping of a coloring of $[1,\,2p]$--will shift by $p$
in this step, not by $2p$.)\\
\\
\emph{Arithmetic equivalent}: Noting that the odd numbers of $[0,\,2p-1]-\{p\}$,
a reduced residue system $mod\,2p$, form a cyclic group under multiplication
$mod\,2p$ (we denote this group $\mathbb{\mathbb{Z}}_{2p}^{*}$)
and that if $g$ is a generator of $\mathbb{\mathbb{Z}}_{p}^{*}$,
then either $g$ or $g+p$, whichever is odd, is a generator of
$\mathbb{\mathbb{Z}}_{2p}^{*}$, we use \textit{\emph{$g_{0}$ (or,
if $g_{0}$ is not odd, use $g_{0}+p$) to determine the }}$k^{th}$-power classes
of $\mathbb{\mathbb{Z}}_{2p}^{*}$ and use those class assignments
and an arbitrary coloring of $p$ to induce a $k$-coloring
of the odd numbers in $[0,\,2p-1]$. Call this \emph{partial arithmetic
coloring 3} of $[0,\,2p-1]$.\\
\\
A reduced residue system mod $2p$ can be obtained through a doubling
of each element of \emph{$[1,\, p-1]$}, a reduced residue system
mod $p$. If the doubled result, when reduced mod $p$ to
an integer $r$ in \emph{$[1,\, p-1]$}, is even, view it as the
integer $r+p$ in the reduced residue system $\textrm{mod}\,2p$.
If $r$ is odd, view it directly as a member of a reduced residue
system $\textrm{mod}\,2p$. This doubling action maps the integers
of $[1,\,\frac{p-1}{2}]$ consecutively to the odd integers of $[p+2,\,2p-1]$
and maps the integers of $[\frac{p+1}{2},\, p-1]$ consecutively to
the odd integers of $[1,\, p-2]$. Given that we use the same generator
$g_{0}$ (or $g_{0}+p$), this is nothing more than a cyclic shifting
by $p$ units within $[0,\,2p-1]$ of the $k$-coloring imposed
by doubling action taken in step 1, the spreading step, under
our arithmetic view.
\item \textbf{Merging:} Do a full $k$-coloring of $[1,\,2p]$ by coloring
the odd numbers of $[1,\,2p]$ as in partial coloring 1 and coloring
the even numbers of $[1,\,2p]$ as in partial coloring 3.\\
\\
\emph{Arithmetic equivalent}: Do a full $k$-coloring of $[0,\,2p-1]$
by coloring the even numbers of $[0,\,2p-1]$ as in partial coloring
2 and coloring the odd numbers of $[0,\,2p-1]$ as in partial coloring
3. The careful reader will note that we merge colorings 2 and 3 here
while the original zipping procedure merged colorings 1 and 3. If
we had shifted partial coloring 2 to get partial coloring 3, we would
have done the original merge. Rather we prefer to use the turning
step on the even numbers because it will allow us to see directly
the arithmetic structure of the power classes in the coloring of the
odd numbers and because it yields the same color labeling as that
shown in \cite{zipper} rather than a simple translation of color
labels mod $k$.
\end{enumerate}

\section*{Validation of a zipped cyclic certificate}

Given a cyclic certificate $W(k,l,p)$ whose coloring of $[0,\, p-1]$
(equivalently, $[1,\, p]$) arises from the distribution of $k^{th}$-power
classes modulo the prime $p$, the zipping procedure will yield
a $k$-coloring of $[0,\,2p-1]$, but that coloring may or may
not be free of monochromatic $l$-progressions; that is, it may
or may not be a certificate $W(k,l,2p)$. Certifying that a zipped
coloring is still $l$-progression free requires checking each
of approximately $\frac{(2p-1)^{2}}{2(l-1)}$ $l$-progressions
in $[0,\,2p-1]$. Using arithmetic properties of the zipped coloring,
however, allows us to cut this to little more than a check of at most
$2p-l-1$ $l$-strings, essentially a reduction from a quadratic-time
process to a linear-time process, since we shall be dealing with large
values of $p$ and small values of $l$.

A similar speed-up was used in \cite{jrr} to find certificates $W(k,l,p)$
based on $k^{th}$-power classes modulo a prime $p$. This speed-up
depended heavily on the following simple \emph{observations} (using
$k^{th}$-power-class notation introduced in the preceding section):
\begin{enumerate}
\item For any \ensuremath{a,\, b}
 in \ensuremath{\mathbb{Z}_{p}^{*}}, if \ensuremath{a\in C_{i}}
 for some \ensuremath{i}
 and \ensuremath{b\in C_{j}}
 for some \ensuremath{j}, then $ab\in C_{(i+j)\, mod\, k}$. That is, because indices of $k^{th}$-power
classes mod $p$ are based on exponents of a fixed generator of
\ensuremath{\mathbb{Z}_{p}^{*}}, a product of elements of two classes resides in the class whose
index is the sum of the indices of the original two classes.
\item If the members of the $l$-progression $a,\, a+d,\ldots,\, a+(l-1)d$
are all in the same $k^{th}$-power class mod $p$, then so are
the members of the $l$-string $ad^{-1},\, ad^{-1}+1,\ldots,ad^{-1}+(l-1)$,
where $d^{-1}$ represents the inverse of $d$ in \ensuremath{\mathbb{Z}_{p}^{*}}. This is just an invocation of observation 1.
\end{enumerate}
A zipped $k$-coloring of \ensuremath{\mathbb{Z}_{2p}}
 has a property similar to, but weaker than, that mentioned in observation
1 above, but even in this weaker form it allows application of essentially
the same simple criterion for checking whether the coloring is \ensuremath{l}-progression-free. Noting that the two observations above apply equally
well in the cyclic group \ensuremath{\mathbb{Z}_{2p}^{*}}, we establish the following claims.
\begin{claim}
Given that \ensuremath{k^{\text{th}}}-power classes $mod\, p$ and $mod\,2p$ are formed relative to the
same primitive root \ensuremath{g}, if \ensuremath{a}
 is in class \ensuremath{C_{i}\, mod\,2p}, then \ensuremath{a}
 is also in class \ensuremath{C_{i}}
 mod \textit{p.}\end{claim}
\begin{proof}
\ensuremath{a\in C_{i}\text{ mod\,}2p\Rightarrow a\equiv g^{\text{\textit{jk}}+i}\,\text{mod\,}2p\Rightarrow a\equiv g^{\text{\textit{jk}}+i}\,\text{mod }p\Rightarrow a\in C_{i}\,\text{mod\,}p}.\end{proof}
\begin{claim}
Given that \ensuremath{k^{\text{th}}}-power classes $mod\,\ensuremath{p}$ and $mod\,2p$ are formed relative
to the same primitive root \ensuremath{g}, if $\ensuremath{a\in C_{i}}\, mod\, p$, then also \textit{$\ensuremath{a\in C_{i}}\, mod\,2p$
}if \ensuremath{a}
 is odd, and \textit{$\ensuremath{a+p\in C_{i}}\, mod\,2p$} if \ensuremath{a}
 is even.\end{claim}
\begin{proof}
If \ensuremath{a}
 is even and \ensuremath{a\in C_{i}\, mod\, p}, then \ensuremath{a=g^{\text{\textit{jk}}+i}+\text{\textit{np}}}
 with \ensuremath{n}
 odd. (Here, since \ensuremath{g}
 must be odd to be a primitive root $mod\ensuremath{\,2p}$, if \ensuremath{g}
 mod \ensuremath{p}
 is even, we take \ensuremath{g+p}, an odd number, as the generator of $\mathbb{\mathbb{Z}}_{2p}^{*}$.)
Thus, \ensuremath{a+p=g^{jk+i}+(n+1)p\equiv g^{jk+i}\, mod\,2p}
 (since \ensuremath{n+1}
 is even), and \ensuremath{a+p\in C_{i}\,\text{mod\,}2p}. And if \ensuremath{a}
 is odd and \ensuremath{a\in C_{i}\,\text{mod\,}p}, then \ensuremath{a=g^{\text{\textit{jk}}+i}+\text{\textit{np}}}
 with \ensuremath{n}
 even (since \ensuremath{g}
 is odd), and we get immediately \ensuremath{a\equiv g^{\text{jk}+i}\,\text{mod}\,2p}
 and \ensuremath{a\in C_{i}\, mod\,2p}.\end{proof}
\begin{claim}
For any \ensuremath{a}, \ensuremath{b\in[0,\,2p-1]}
 with neither \ensuremath{a}
 nor \ensuremath{b}
 divisible by \ensuremath{p}, if \ensuremath{a}
 and \ensuremath{b}
 are in the same class, say \ensuremath{C_{j}}, under the zipped $k$-coloring of \ensuremath{[0,\,2p-1]}
 as defined above, then \ensuremath{\text{\textit{ca}}}
 and \ensuremath{\text{\textit{cb}}}
 $mod\,2p$ are in the same class if \ensuremath{c}
 is any odd integer not divisible by \ensuremath{p}.\end{claim}
\begin{proof}
We consider 3 cases: \ensuremath{a}
 and \ensuremath{b}
 both odd, $a$ and $b$ both even, and $a$ odd with
$b$ even. The first case follows directly from observation 1
above, since $a, b$, and $c$ are all in \ensuremath{\mathbb{Z}_{2p}^{*}}, whose $k^{th}$-power classes color the odd numbers in $[0,\,2p-1]$.
In the second case, let $a=2m$ and $b=2n$. Here we note that $m$
and $n$, taken $mod\, p$, are both in \ensuremath{\mathbb{Z}_{p}^{*}}, and, by the manner in which even numbers are placed in classes in
the zipped $k$-coloring of $[0,\,2p-1]$, \ensuremath{m}
 and \ensuremath{n}
 are in the same \ensuremath{k^{\text{th}}}-power class mod \textit{p}. So, by observation 1 above, \ensuremath{\text{\textit{ca}}\text{ and}\text{\textit{cb}}}
 are in the same \ensuremath{k^{\text{th}}}-power class mod \textit{p}, and, as a consequence, \ensuremath{\text{\textit{ca}}\text{ and}\text{\textit{cb}}}
 are placed in the same class in the zipped $k$-coloring of $[0,\,2p-1]$.

It remains only to show that the claim holds for \ensuremath{a}
 odd and \ensuremath{b}
 even. In this case, suppose \ensuremath{c\in C_{i}\, mod\,2p}. Then from observation 1 above $(\textrm{applied\,\ to}\,\ensuremath{\mathbb{Z}_{2p}^{*}})$
\ensuremath{ca\in C_{(i+j)\,\text{mod\,}k}\,\text{mod}\,2p}, and, so, in \ensuremath{C_{(i+j)\,\text{mod\,}k}}
 in the zipped coloring as well. Suppose, \ensuremath{b=2m}
 with \ensuremath{m\in\mathbb{Z}_{p}^{*}}. Because \ensuremath{b\in C_{j}}
 in the zipped coloring, \ensuremath{m}
 must be in \ensuremath{C_{(j-t-\frac{k}{2})\,\text{mod\,}k}}
 among the \ensuremath{k^{\text{th}}}-power classes $mod\, p$. And since \ensuremath{c\in C_{i}\,\text{\emph{mod}}\,2p}
 implies \ensuremath{c\in C_{i}\,\text{\emph{mod}}\, p}
 (see \textit{Claim 2}), observation 1 indicates that \ensuremath{cm\in C_{(i+j-t-\frac{k}{2})\,\text{mod\,}k)}\,\textrm{\emph{mod}}\, p}
 so that \ensuremath{cb=2cm\in C_{(i+j)\,\text{mod\,}k}}
 in the zipped coloring. Hence, in this zipped coloring $ca$
and $cb$ are in the same class, as claimed.
\end{proof}
(That \textit{Claim 3} does not hold when \textit{c} is even is
evidenced by using \textit{p=113}, noting that in the zipped coloring
of \ensuremath{\mathbb{Z}_{226}}
 we have \textit{a=9} in \ensuremath{C_{0}}, \textit{$b=10$} in \ensuremath{C_{0}}
 and multiplying by \textit{$c=10$} we find \textit{$ca=90$} in
\ensuremath{C_{0}}
and \textit{cb=100} in \ensuremath{C_{1}}.)
\begin{claim}
If \ensuremath{a}
 and \ensuremath{a+d}
 are in the same class $C_{i}$ under the zipped $k$-coloring
of \ensuremath{[0,\,2p-1]}
 with \ensuremath{d}
 odd and not divisible by \ensuremath{p}, then \ensuremath{ad^{-1}}
 and \ensuremath{ad^{-1}+1}
 are in the same class of the extended partition of \ensuremath{\mathbb{Z}_{2p}}, where \ensuremath{d^{-1}}
is the multiplicative inverse of \ensuremath{d}
 in \ensuremath{\mathbb{Z}_{2p}^{*}}.\end{claim}
\begin{proof}
This follows immediately from \textit{Claim 3} by multiplying both
\textit{a} and \ensuremath{a+d} by \ensuremath{d^{-1}}.
\end{proof}
It follows from \textit{Claim 4} that if under the zipped coloring
of \ensuremath{\mathbb{Z}_{2p}}
 there is a single-class arithmetic progrression of \ensuremath{l}
 terms beginning at \ensuremath{a}
 and having odd common difference \ensuremath{d}, multiplying each member of the progression by \ensuremath{d^{-1}\,\text{mod}\,2p}
 yields a set that forms a single-class \ensuremath{l}-string beginning at \ensuremath{ad^{-1}}. The contrapositive of this---and the aid in checking whether $k$-colorings
of long sequences are free of monochromatic \ensuremath{l}-progressions---is that if there is no single-class \ensuremath{l}-string found in the extended partition of \ensuremath{\mathbb{Z}_{2p}}, then there is no single-class \ensuremath{l}-progression with odd common difference.
\begin{claim}
If \ensuremath{a}
 and \ensuremath{a+d}
 are in the same class $C_{i}$ under the zipped $k$-coloring
of $[0,\,2p-1]$ with \ensuremath{d}
 even and not divisible by \ensuremath{p}, then \ensuremath{ad^{-1}}
 and \ensuremath{ad^{-1}+1}
 are in the same \ensuremath{k^{\text{th}}}-power classes $mod\, p$, where \ensuremath{d^{-1}}
is the multiplicative inverse of \ensuremath{d}
 in \ensuremath{\mathbb{Z}_{p}^{*}}.\end{claim}
\begin{proof}
This follows directly from observation 1 at the beginning of this
section. For, an \ensuremath{l}-progression of even common difference will consist either entirely
of odd numbers or entirely of even numbers. In the first case note
that in the zipped $k$-coloring odd numbers are placed in their
\ensuremath{k^{\text{th}}}-power classes $mod\,2p$, but taking these placements $mod\ensuremath{\, p}$
we still see a single-class \ensuremath{l}-progression and can quickly deduce the existence of a single-class
\ensuremath{l}-string in \ensuremath{\mathbb{Z}_{p}^{*}}. Likewise, if in the zipped $k$-coloring all members of a single-class
\ensuremath{l}-progression are even, we need only note that the classes assigned
to the even numbers in the zipped coloring are just relabelings (i.e.,
shifted labelings) of the \ensuremath{k^{\text{th}}}-power classes mod \textit{p} so that any \ensuremath{l}-progression can quickly be associated with a single-class \ensuremath{l}-string in \ensuremath{\mathbb{Z}_{p}^{*}}.
\end{proof}
As a consequence of \textit{Claim 5}, the existence of single-class
\ensuremath{l}-progressions of even common difference within the zipped $k$-coloring
of \ensuremath{\mathbb{Z}_{2p}}
 will be signaled by the existence of single-class \ensuremath{l}-strings within \ensuremath{\mathbb{Z}_{p}^{*}}. 


\paragraph{\emph{Criteria for validating that a zipped k-coloring is l-progression
free. }\textmd{For }\textmd{\emph{k }}\textmd{even, }\textmd{\emph{p
}}\textmd{a prime of the form $km+1$, and }\textmd{\emph{$l>2$}}\textmd{,
let }\textmd{\emph{W(k,l,p)}}\textmd{ be a van der Waerden certificate
whose coloring of $[0,\, p-1]$ (equivalently, $[1,\, p]$) arises
from the distribution of $k^{th}$-power classes modulo }\textmd{\emph{p
}}\textmd{and a properly chosen color for 0}\textmd{\emph{. }}\textmd{The
zipping procedure applied to }\textmd{\emph{W(k,l,p) }}\textmd{produces
a van der Waerden certificate }\textmd{\emph{W(k,l,}}\textmd{2}\textmd{\emph{p)
}}\textmd{if the zipped }\textmd{\emph{k}}\textmd{-coloring of $[0,\,2p-1]$
meets the following criteria:}}
\begin{itemize}
\item the $k^{th}$-power coloring of \ensuremath{\mathbb{Z}_{p}^{*}}
 is free of monochromatic \textit{l}-strings (if $W(k,l,p)$ is
a certificate, we already know this); 
\item the zipped $k$-coloring of \ensuremath{[0,\,2p-1]}
is likewise free of monochromatic $l$-strings; and
\item 0 and $p$ are colored without introducing a monochromatic $l$-string,
even in the cyclic sense.
\end{itemize}
Given that the zipping of a coloring based on \emph{$k^{th}$}-power
classes mod $p$ yields a certificate $W(k,l,2p)$,
we may be able to join $l-1$ of these certificate colorings together
to get a certificate $W(k,l,2(l-1)p+1)$.
The following indicates when this joining effort will succeed.


\paragraph{\emph{Criteria for validating an extension of a zipped, cyclic, power-class-based
certificate, W(k,l,2p) to a certificate W(k,l,2(l-1)p+1)}. \textmd{Given
a zipped, }\textmd{\emph{$k^{th}$}}\textmd{-power-class-based certificate,
}\textmd{\emph{W(k,l,}}\textmd{2}\textmd{\emph{p)}}\textmd{, a coloring
of \ensuremath{[0,2(l-1)p]}
 done so that}}
\begin{itemize}
\item any \textit{a} not divisible by \textit{p} is placed in class \ensuremath{C_{j}}
where $C_{j}$ is the class in which \ensuremath{b\equiv a\,\textrm{mod}\,2p}
 has been placed under $W(k,l,2p)$ and
\item the \ensuremath{2(l-1)+1}
 multiples of \textit{p} in \ensuremath{[0,2(l-1)p]}
 are placed in any of the \textit{k} color classes so that no monochromatic
\ensuremath{l}-progression occurs among these multiples
\end{itemize}
results in a coloring that is free of monochromatic $l$-progressions
providing that: 
\begin{itemize}
\item if \ensuremath{p-1}
 is in \ensuremath{k^{\text{th}}}-power class \ensuremath{C_{0}\text{\,\ mod\,}p}, then the integers \ensuremath{1,2,\ldots,[(l-1)/2]}
 are not all in the same class under the coloring of $W(k,l,2p)$; 
\item if \ensuremath{p-1}
 is not in \ensuremath{k^{\text{th}}}-power class \ensuremath{C_{0}\,\text{mod}\, p}, then the integers \ensuremath{1,2,\ldots,(l-1)}
 are not all in the same class under the coloring of $W(k,l,2p)$; and
\item there are no single-class 
\ensuremath{l}-progressions having common difference divisible by \ensuremath{p}.
\end{itemize}

\section*{Computations}

The above criteria yield a mechanism for a fast search for van der
Waerden certificates $W(k,l,2(l-1)p+1)$.
We begin by establishing $k$-coloring profiles of prime
numbers up to some reasonable computational limit. For each prime
$p$ and a small range of values for $k$ and $l$ with
$k$ even our procedure is: 
\begin{enumerate}
\item Find a generator $g$ of $\mathbb{Z}_{p}^{*}$
\item For each of the values of $k$, if \emph{$p\equiv1\,\textrm{mod}\, k$},
record the $k$-coloring profile of $p$ as follows:

\begin{itemize}
\item use $g$ to determine the $k^{th}$-power classes (our basic $k$-coloring)
of $\mathbb{Z}_{p}^{*}$;
\item record whether $p-1$ is in class $C_{0}$;
\item record the minimum value of \emph{$s\in[1,\, p-1]$} such that the
number \emph{$s+1\notin C_{0}$};
\item record the length of the longest monochromatic string of integers
in $[1,\, p-1]$.
\end{itemize}
\item With a table of $k$-coloring profiles of primes, it is a simple
(and quick) matter to search the table and apply the criteria given
in \cite{jrr} to find among the profiled primes those that
yield cyclic certificates $W(k,l,p)$.
\item Apply the zipping technique to certificates $W(k,l,p)$ and subject
the resulting colorings to inspection for monochromatic $l$-strings,
monochromatic $l$-progressions with common difference $p$,
and end conditions given by the criteria listed at the end of the
previous section. If no such monochromatic $l$-strings
or $l$-progressions are found and if the end conditions are met,
then the coloring of $[0,\,2(l-1)p]$ is free of monochromatic $l$-progressions---it
gives a certificate $W(k,l,2(l-1)p+1)$.
\end{enumerate}
We applied this procedure to all primes less than 10,000,000, getting
$k$-coloring profiles for $k=2,\,3,\,4,\,5,\,6$, and then searching
these profiles for fits to $l$-progression-free colorings with
$l=3,\,4,\,5,\ldots,12$. Table 1 shows the known exact values
of van der Waerden numbers and gives the best known lower bounds as
well as new lower bounds that our procedure has revealed. With each
of these new values we show in parentheses the prime number $p$
whose \emph{k$^{th}$}-power classes formed the basis for the cyclic
certificate $W(k,l,p)$ from which can arise a certificate $W(k,l,(l-1)p+1)$.
We denote with ``Z'' in an entry where a single zip procedure
was applied to extend successfully to a cyclic certificate $W(k,l,2p)$
from which arises a certificate $W(k, l, 2(l-1)p+1)$.
In one table entry we use ``ZZ'' to denote that double zipping
was used to gain a certificate $W(k,l,4(l-1)p+1)$. 

\begin{table}[htp]
\centering
\caption{\emph{Van der Waerden numbers W(k,l)--some exact and some lower bounds.
New lower bounds are shown as 2-line entries with the acting prime
in parentheses, {}``Z'' indicating a single zipping was applied,
and {}``ZZ'' indicating a double zipping was applied.}}

\medskip

\begin{tabular}{|c|>{\centering}m{2.2cm}|>{\centering}m{2.2cm}|>{\centering}m{2.2cm}|>{\centering}m{2.2cm}|>{\centering}m{2.2cm}|}

\hline 
\emph{l\textbackslash{}k} & 2 & 3 & 4 & 5 & 6\tabularnewline
\hline 
3 & 9 & 27 & 76 & $>$170 & $>$223\tabularnewline
\hline 
4 & 35 & $>$292 & $>$1048 & $>$2254 & $>$9778\tabularnewline
\hline 
5 & 178 & $>$2173 & $>$17705 & $>$98740 & $>$98740\tabularnewline
\hline 
6 & 1132 & $>$11191 & $>$91331 & $>$540025 & $>$816981\tabularnewline
\hline 
7 & $>$3703 & $>$48811 & $>$420217 & $>$1381687

(230281) & 7465909

(622159)Z\tabularnewline
\hline 
8 & $>$11495 & $>$238400 & $>$2388317

(85297)ZZ & $>$10743258

(1534751) & $>$57445718

(8206531)\tabularnewline
\hline 
9 & $>$41265 & $>$932745

(116593) & $>$10898729

(1362341)Z & $>$79706009

(9963251) & $>$159986609

(9999163)Z\tabularnewline
\hline 
10 & $>$103474

(11497) & $>$4173724

(463747) & $>$760492218

(8449913) & $>$89999920

(9999991) & $>$179998975

(9999943)Z\tabularnewline
\hline 
11 & $>$193941{*}

(9697)Z & $>$18603731

(1860373) & $>$198841541

(9942077)Z & $>$99999711

(9999971) & $>$199998621

(9999931)Z\tabularnewline
\hline 
12 & $>$638727

(29033)Z & $>$79134144

(7194013) & $>$219988319

(9999469)Z & $>$109999242

(9999931) & $>$219996107

(9999823)Z\tabularnewline
\hline 
\end{tabular}
\end{table}

Some of the entries in Table 1 deserve comments:
\begin{itemize}
\item Because our procedure went only through the primes less than 10,000,000,
table entries associated with primes in the vicinity of 10,000,000
are very likely improvable by more extensive search.
\item That our bound for $W(4,12)$ exceeds that shown for $W(5,12)$
is essentially a product of our limiting the search to primes less
than 10,000,000. In our attempt to find a bound for $W(5,12)$,
for example, we searched only prime profiles for $k=5$, not considering
those for $k=4$. Had our search gone far enough beyond the 10,0000,000
limit, we conjecture that a larger prime would have yielded a bound
for $W(5,12)$ that is larger than the bound given here for $W(4,12)$.
Rather than replicate the bound for $W(4,12)$ as a bound also
for $W(5,12)$, which it clearly is, we preferred to show the
prime and zipping results directly. The same comment applies to some
entries for $l=11$ as well.
\item The asterisk ({*}) on the entry for $W(2,11)$ highlights a new
value that corrects an error in \cite{jrr} where a bound for $W(2,11)
$was misreported. This error was discovered during our recent computations.
\item There is only one double zipping reported in this table. That is not
because no other double zippings would work, but rather that computional
power needed to fully check double-zipped colorings is formidable.
We have not found a shortcut for verifying that a $k$-coloring
resulting from a double zipping is $l$-progression free.\end{itemize}

\begin{thebibliography}{99}

\bibitem{ahmed}T. Ahmed, Some new van der Waerden numbers and some
van der Waerden-type numbers, \emph{Integers} \textbf{9}, pp. 65-70,
2009.

\bibitem{beeler}M. Beeler and P. O'Neil, Some new van der Waerden
numbers, \emph{Discrete Mathematics} \textbf{28}, pp. 135-146, 1979.

\bibitem{berlekamp}E. Berlekamp, A construction for partitions which
avoid long arithmetic progressions, \emph{Canad. Math. Bull.} \textbf{11},
pp. 409-414, 1968.

\bibitem{chvatal}V. Chvátal, Some unknown van der Waerden numbers,
\emph{Combinatorial Structures and Their Applications}, R. K. Guy
et al. (editors), Gordon and Breach, pp. 31-33, 1970.

\bibitem{dransfield}M, R. Dransfield, L. Liu, V. W. Marek and M.
Truszczynski, Satisfiability and computing van der Waerden numbers,
\emph{The Electronic Journal of Combinatorics} \textbf{11} (1)\textbf{
}R41, pp. 1-15, 2004.

\bibitem{gowers}T. Gowers, A new proof of Szemerédi's theorem, \emph{Geometric
and Functional Analysis} \textbf{11}, pp. 465-588, 2001.

\bibitem{heule}M. J. H. Heule, Improving the odds: New lower bounds
for van der Waerden numbers, \emph{http://www.st.ewi.tudelft.nl/sat/slides/waerden.pdf,
}2009.

\bibitem{heulewebsite}M. J. H. Heule, Van der Waerden numbers,\\ \emph{http://www.st.ewi.tudelft.nl/sat/waerden.php},
2011.

\bibitem{heule-walsh}M. J. H. Heule and T. Walsh, Symmetry within
solutions, \emph{Proc. of the Twenty-Fourth AAAI Conference on Artificial
Intelligence (AAAI '10)}, pp. 77-82, AAAI Press., 2010.

\bibitem{zipper}P. R. Herwig, M. J. H. Heule, P. M. van Lambalgen,
and H. van Maaren, A method to construct lower bounds for van der
Waerden numbers, \emph{The Electronic Journal of Combinatorics} \textbf{14
}R6, pp. 1-15, 2007.

\bibitem{kouril}M. Kouril and J. L. Paul, The van der Waerden number
W(2,6) is 1132, \emph{Experimental Mathematics} \textbf{17}, pp. 53\textendash{}61,
2008.

\bibitem{kouril-franco}M. Kouril and J. Franco, Resolution tunnels
for improved SAT solver performance, \emph{Proc. of 8th International
Conference on Theory and Applications of Satisfiability Testing,} pp.
143-157, 2005.

\bibitem{moser}L. Moser, On a theorem of van der Waerden, \emph{Canad.
Math. Bull.} \textbf{3}, pp. 23-25, 1960.

\bibitem{jrr}J. R. Rabung, Some progression-free partitions constructed
using Folkman's method, \emph{Canad. Math. Bull.} \textbf{22} (1),
pp. 87-91, 1979.

\bibitem{shelah}S. Shelah, Primitive recursive bounds for van der
Waerden numbers, \emph{J. Amer. Math. Soc.} \textbf{1}, pp. 683-697,
1988.

\bibitem{Stevens}R. S. Stevens and R. Shantaram, Computer-generated
van der Waerden partitions, \emph{Math. Comp.} \textbf{32} (142),
pp. 635-636, 1978.

\bibitem{vw}B. L. van der Waerden, Beweis einer Baudet'schen Vermutung,
\emph{Nieuw Archief voor Wiskunde} \textbf{15}, pp. 212-216, 1927.\end{thebibliography}

\end{document}
