\documentclass[12pt]{article}





\pagestyle{myheadings}\markboth{\hfill
{\sc the electronic journal of combinatorics 6 (1999), \#R22}}
{{\sc the electronic journal of combinatorics 6 (1999), \#R22}\hfill}
\thispagestyle{empty} 


 
\setlength{\textwidth}{6in}
\setlength{\textheight}{9in}
\setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\footskip}{.5in}
\setlength{\topmargin}{-\headheight}


\usepackage{amsfonts}
\usepackage{latexsym}


\sloppy

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{ex}[thm]{Example}
\newtheorem{prob}[thm]{Problem}
\newcommand{\dodef}{\bigbreak\noindent{\bf Definition. }}
\newcommand{\undef}{\bigbreak}
\newcommand{\proof}{\noindent{\bf Proof. }}
\newcommand{\remark}{\noindent{\bf Remark. }}
\newcommand{\se}{\subseteq}
\newcommand{\romanlist}{(\roman{enumi})}
\newcommand{\promanlist}{(\roman{enumi}$'$)}
\newcommand{\alphlist}{(\alph{enumi})}
\newcommand{\countlist}{\usecounter{enumi}}
\newcommand{\ra}{\rightarrow}
\newcommand{\nat}{\mathbb{N}}
\newcommand{\vvw}{\mbox{\it VW\/}}
\newcommand{\qed}{\hfill$\Box$\bigbreak}
\newcommand{\lcm}{\mbox{\it lcm}}
\newcommand{\mod}{\mbox{\rm mod\ }}
    
\title{A van der Waerden Variant}

\author{
      Kevin J. Compton\\
      BRICS Research Centre, University of Aarhus, Denmark\\
      and EECS Department, University of Michigan\\Ann Arbor, MI 48109-2122\\
      {\small\texttt{ kjc@umich.edu}} 
}



\date{~}
\begin{document}

\maketitle

\begin{abstract}
The classical van der Waerden Theorem says that for every 
every finite set $S$ of natural numbers and every
$k$-coloring of the natural numbers, 
there is a monochromatic set of the form 
$aS+b$ for some $a>0$ and $b\geq 0$. I.e., monochromatism
is obtained by a dilation followed by a translation.
We investigate the effect of
reversing the order of dilation and translation.
$S$ has the {\em variant
van der Waerden} property for $k$ colors if
for every $k$-coloring there is a  monochromatic set of the form 
$a(S+b)$ for some $a>0$ and $b\geq 0$.
On the positive side it is shown that
every two-element set has the variant van der Waerden
property for every $k$.
Also, for every finite $S$ and $k$ there is an
$n$  such that $nS$ has the variant van der
Waerden property for $k$ colors.  This extends the
classical van der Waerden Theorem.  On the negative side it
is shown that if $S$ has at least
three elements, the variant van der Waerden property fails
for a sufficiently large $k$. The counterexamples to the
variant van der Waerden property are constructed 
by  specifying colorings as Thue-Morse sequences. 

\bigskip

\noindent Submitted July 17, 1997; Accepted April 2, 1999.


\bigskip

\noindent {\bf AMS Subject Classification.} Primary: 05D10. Secondary: 11B85, 68R15.
\end{abstract}


\section{Introduction.}


Van der Waerden's theorem on arithmetic progressions
is over  seventy years old 
\cite{waerden:1927}, but
it continues to reveal new facets and inspire new results.
It has many generalizations, such as the
Hales-Jewett Theorem \cite{graham;spencer;rothschild:1990}
and multidimensional versions \cite{pin:1983}.  It has had
unexpected connections with other parts of 
mathematics, such as topological dynamics \cite{furstenberg:1981}.
The numerical bounds 
from van der Waerden's original proof, long thought to
be the best attainable, have been dramatically reduced
in recent years \cite{shelah:1988}.  

In its most familiar formulation,   
van der Waerden's Theorem says 
that if $\nat=\{0,1,2,\ldots\}$ is
partitioned into a finite number of classes, one of the classes  
contains arbitrarily long arithmetic progressions.
To distinguish this theorem from the variant we
will introduce, we refer to it as the {\em classical
van der Waerden Theorem}.  Another way of stating the theorem  
is to say that  for every 
{\em $k$-coloring} of $\nat$ (or mapping 
$\alpha:\nat\rightarrow\{0,\ldots,k-1\}$)
and every finite $S\se\nat$, 
there are integers $a>0$ and $b\geq 0$ such that 
$aS+b=\{as+b\mid s\in S\}$ is
{\em monochromatic}.  That is, $\alpha$ maps all elements in some set
$aS+b$ to the same color.
Thus, we can find a monochromatic set 
by dilating $S$ (multiplying every element by $a$) and 
then translating (adding $b$ to every
element).  

The question we will consider involves another, apparently
unexplored, variation:
what happens when the order of dilation and translation
is reversed?  
Is it the case that if $\nat$ is $k$-colored and $S$ is 
a finite subset of $\nat$, 
there are $a>0$ and $b\geq 0$ such that $a(S+b)$
is monochromatic?  
The answer, interestingly enough, depends on $S$ and $k$.
For some values of $S$ and $k$ this property (which we call the
{\em variant van der Waerden property}) holds; for
others it does not.  We do not yet have a characterization of
the cases where it holds, but this paper makes
some initial progress in that direction.

For a nonempty set $S\se\nat$ and $k>0$, $\vvw(S,k)$ holds
if for every $k$-coloring of $\nat$ there are integers $a>0$ and
$b\geq 0$ such that $a(S+b)$ is monochromatic.  (When we speak of a 
set of the form $a(S+b)$, we will assume that
$a>0$ and $b\geq 0$.)  
Clearly,
if $\vvw(S,k)$ holds, $T\se S$ and $l<k$, then $\vvw(T,l)$ holds.
Also, if $c\geq 0$ and $\vvw(S+c,k)$ holds, then
$\vvw(S,k)$ holds.

In Section~2 we will examine the positive instances of the variant
van der Waerden property and in Section~3 we will examine negative 
instances.  Proofs of the negative results make use of {\em Thue-Morse
sequences} which have been studied both
in formal language theory and topological dynamics.
We conclude with some open questions in Section~4.
Many of the results in this paper were originally conjectured on the basis
of computer experiments.  We will describe how the experiments
led to the results proved in this paper.  The C program
vw.c used in these experiments may be downloaded from
the EJC site.

The computer program we used computed some values of 
$M(S,k)$, which is defined to be
the least $M$ such that every $k$-coloring of 
$\{0,1,2,\ldots,M\}$ has a monochromatic subset of the form
$a(S+b)$.  If we define $M'(S,k)$ to be
the least $M'$ such that every $k$-coloring of 
$\{0,1,2,\ldots,M'\}$ has a monochromatic subset of the form
$aS+b$, it is clear that 
$M'(S,k)\leq M(S,k)$ whenever $M(S,k)$ is defined.  
Brown, {\em et al.} \cite{MR98c:05159} give a nearly
complete account of the values of $M'(S,k)$ when $|S|=3$.

In general, one may formulate many different  variants of
van der Waerden's Theorem by asking, for a given
set $A$ of finite sets of integers and a given $k>1$, whether
every $k$-coloring of $\nat$ will make at least one element of
$A$ monochromatic.  Researchers have investigated this
question for various choices of $A$ (see, {\em e.g.}
\cite{MR97e:05193,MR90b:11010b,MR90b:11010a,
MR93e:05100,MR94d:11006,MR94m:05195,MR98i:05163,MR1633760,
MR1628121,MR89d:05021,MR91i:05117,MR97a:05209,MR98b:05099}),
but not for the one considered here.   


We will require a few definitions in the sections that follow.
Besides $k$-colorings of $\nat$, 
we will also consider $k$-colorings of initial intervals
of $\nat$.  It is useful to identify a $k$-coloring
$\alpha:\{0,1,\ldots,i-1\}\rightarrow\{0,\ldots,k-1\}$ 
with a {\em word} of length $i$ over the $k$-symbol alphabet, {\em viz.},
the word $\alpha_0\alpha_1\cdots\alpha_{i-1}$, where $\alpha_i=\alpha(i)$.
Similarly, we identify a 
$k$-coloring of $\nat$ with an infinite
word over the $k$ symbol alphabet.
Thus, we may speak of $k$-coloring $\alpha:I\rightarrow\{0,\ldots,k-1\}$
being a {\em prefix} of $k$-coloring $\beta:J\rightarrow\{0,\ldots,k-1\}$
if $I$ is an initial interval of $J$ and $\alpha$ is the restriction of
$\beta$ to $I$; if, in addition, $I$ is properly contained in $J$, we
say $\alpha$ is a {\em proper prefix} of $\beta$.  
When $\alpha$ is a prefix of $\beta$, we will also
say that $\beta$ is an {\em extension} of $\alpha$.


\section{Positive Instances}
\label{positive}

Instances where the variant van der Waerden property holds 
satisfy the usual compactness property of Ramsey-type theorems (see
\cite{graham;spencer;rothschild:1990}).  That is, if $\vvw(S,k)$
holds, there is an $M$ such that for every $k$-coloring
of $\{0,1,\ldots,M\}$, there is a monochromatic set of the form
$a(S+b)$ is contained in $\{0,1,\ldots,M\}$.
For each $S$ and $k$ such that $\vvw(S,k)$ holds, 
let $M(S,k)$ be the least such $M$.

The compactness property allows us to verify through a computer search that
$\vvw(S,k)$ holds.  Suppose
$S$ and $k$ are given.   We may systematically list $k$-colorings
of sets $\{0,1,...,i\}$ until we find an $i$ 
such that all $k$-colorings contain a monochromatic 
set of the form $a(S+b)$.
This approach may be improved by applying standard search techniques.

The table in Figure~1 below shows the result of running 
a search program for various values of
$k$ and various two-element sets $S$.  For the 
empty entries the program did not return a value because it
exceeded a time limit.  In the classical Van der Waerden Theorem, the
case where $S$ has two elements is not interesting.  For the
variant van der Waerden property, the situation is not completely 
trivial, as we shall see.

\begin{figure}[htb]
\begin{center}
\begin{tabular}
{c|c|cccc|}
\multicolumn{2}{c}{ }   &\multicolumn{4}{c}{$k$}\\
\cline{3-6}
\multicolumn{2}{c|}{ }  &2      &3      &4      &5      \\
\cline{2-6}
        &\{0,1\}        &2      &4      &12     &32     \\
        &\{0,2\}        &4      &6      &12     &       \\
        &\{1,2\}        &4      &12     &32     &       \\
        &\{0,3\}        &6      &12     &24     &       \\
        &\{1,3\}        &6      &12     &24     &       \\
        &\{2,3\}        &6      &12     &48     &       \\
        &\{0,4\}        &8      &12     &24     &       \\
$S$     &\{1,4\}        &8      &24     &       &       \\
        &\{2,4\}        &8      &12     &24     &       \\
        &\{3,4\}        &8      &16     &       &       \\
        &\{0,5\}        &10     &20     &       &       \\      
        &\{1,5\}        &10     &18     &       &       \\
        &\{2,5\}        &10     &24     &       &       \\      
        &\{3,5\}        &10     &18     &       &       \\
        &\{4,5\}        &10     &24     &       &       \\
\cline{2-6}
\end{tabular}
\end{center}
\caption{Some values of $M(S,k)$}
\label{table1}
\end{figure}

When $S$ has precisely two elements
it is useful to regard the problem of whether
$\vvw(S,k)$ holds as a graph coloring problem.  
Let $S=\{c,d\}$ with $c<d$ and let ${\mathfrak G}(S)$ be the graph whose
vertex set is $\nat$ and edge set is 
$\{\{a(c+b),a(d+b)\}\mid a>0, b\geq 0\}$.  Then 
$\vvw(S,k)$ holds if and only if ${\mathfrak G}(S)$ is not $k$-colorable.
If ${\mathfrak G}(S)$ is not $k$-colorable, then $M(S,k)$ is the 
least integer $M$ such that ${\mathfrak G}(S)$ restricted to 
$\{0,1,\ldots,M\}$ is not $k$-colorable.
 

The following proposition, conjectured after a cursory 
examination of the table, is quite easy to show.

\begin{prop}
\label{two}
Let $c<d$ be nonnegative integers.  Then $M(\{c,d\},2)=2d$.
\end{prop}

\proof  ${\mathfrak G}(S)$ restricted to $\{0,1,\ldots,2d\}$ is not
2-colorable because it contains a triangle consisting of the
edges $\{c,d\}+c$, $\{c,d\}+d$ and $2\{c,d\}$.

On the other hand, ${\mathfrak G}(S)$ 
restricted to $\{0,1,\ldots,2d-1\}$ is 
2-colorable.  The only edges in this graph are of the form $\{c,d\}+b$,
where $0\leq b\leq d-1$.  Let $l=d-c$.  Color a vertex $i$ with color~0 if
$\lfloor i/l\rfloor$ is even, and with color~1 otherwise.  Since the only
vertices that $i$ might possibly be adjacent to are $i-l$ and $i+l$,
no two adjacent vertices have the same color.\qed

We now show that the variant van der Waerden property holds
for two-element sets.


\begin{thm}
\label{deux}
Let $|S|=2$.  Then $\vvw(S,k)$ holds for all $k>0$.
\end{thm}

\proof By the remarks above, it is enough to show that ${\mathfrak G}(S)$
is not $k$-colorable.  It is easier to show something a little stronger.
Let ${\mathfrak G}_n(S)$ be the graph whose
vertex set is $\nat$ and edge set is 
$\{\{a(c+b),a(d+b)\}\mid n\geq a>0, b\geq 0\}$.  Clearly, the
edge set of ${\mathfrak G}(S)$ is the union of the edge sets of the graphs
${\mathfrak G}_n(S)$.  We will show that for every $S$ and $k$, there
is an $n=n(S,k)$ such that ${\mathfrak G}_n(S)$ contains a $(k+1)$-clique.
Thus, ${\mathfrak G}(S)$ contains a $(k+1)$-clique and therefore is not
$k$-colorable.  

First, we show by induction on $k$ that for each $k$ there is an
$n$  such that ${\mathfrak G}_n(\{0,1\})$ contains
a $k$-clique whose vertices are all less than or equal to $n$.  
The case $k=1$ is trivial. If $k=2$ then we may take $n=1$.
Observe that for each $n$, ${\mathfrak G}_n(\{0,1\})$ is {\em periodic}
in the following sense.  Let $p(n)=\lcm\{1,2,\ldots,n\}$.  Consider
any edge $a(\{0,1\}+b)$ in ${\mathfrak G}_n(\{0,1\})$.  Since
$a\leq n$, $p$ is a multiple of $a$, say $p=aq$.  Then
$a(\{0,1\}+b)+p=a(\{0,1\}+b+q)$ is also an edge in ${\mathfrak G}_n(\{0,1\})$.
Thus, if ${\mathfrak G}_n(\{0,1\})$ contains a $k$-clique whose vertices
are all $\leq n$, then by periodicity, it also contains
a $k$-clique whose vertices are all $\geq p(n)$ and $\leq n+p(n)$.  
Let $n'=n+p(n)$.  Then ${\mathfrak G}_{n'}(\{0,1\})$ contains
a $k$-clique whose vertices are all $\geq p(n)$ and $\leq n+p(n)$ and, furthermore,
contains an edge from 0 to each one of the vertices in this $k$-clique.
That is, ${\mathfrak G}_{n'}(\{0,1\})$ contains a $(k+1)$-clique
all of whose vertices are $\leq n'$.

Now we consider the case where $S$ is an arbitrary two-element set.  
Let $S=\{c,d\}$ where $c<d$.  We have seen that
for a given $k$ there is an $n$ such that ${\mathfrak G}_n(\{0,1\})$
contains a $k$-clique.  We will show that ${\mathfrak G}_n(S)$ also
contains a $k$-clique by describing an embedding of ${\mathfrak G}_n(\{0,1\})$
into ${\mathfrak G}_n(S)$.   Let $l=d-c$ and define $h:\nat\ra\nat$ by
$h(x)=lx+cp(n)$ (where $p(n)$ is as above).  Consider any edge $a(\{0,1\}+b)$ in
${\mathfrak G}_n(\{0,1\})$.  As before, $p=p(n)$ is a multiple of $a$
so we may write $p=aq$.  Thus, $h$ maps $a(\{0,1\}+b)$ to
$la(\{0,1\}+b)+acq=a\{cq+lb,cq+lb+l\}$.  We know that $q\geq 1$ so setting
$b'=cq+lb-c$, we see that $b'\geq 0$, $cq+lb=c+b'$ and $cq+lb+l=d+b'$.
The image of the edge $a(\{0,1\}+b)$ under $h$ is
therefore $a(S+b')$, an edge in ${\mathfrak G}_n(S)$.\qed




\begin{figure}[htb]
\begin{center}
\begin{tabular}
{|c|c|c|c|c|}
\cline{1-2}\cline{4-5}
$S$             &$M(S,2)$&~~~~~~~~~~~~&$S$              &$M(S,2)$\\
\cline{1-2}\cline{4-5}
\{0,1,2\}       &       &       &\{2,4,5\}      &20     \\
\{0,1,3\}       &12     &       &\{3,4,5\}      &       \\
\{0,2,3\}       &12     &       &\{0,1,6\}      &36     \\
\{1,2,3\}       &       &       &\{0,2,6\}      &24     \\
\{0,1,4\}       &22     &       &\{1,2,6\}      &       \\
\{0,2,4\}       &       &       &\{0,3,6\}      &24     \\
\{1,2,4\}       &18     &       &\{1,3,6\}      &28     \\
\{0,3,4\}       &20     &       &\{2,3,6\}      &30     \\
\{1,3,4\}       &20     &       &\{0,4,6\}      &24     \\
\{2,3,4\}       &       &       &\{1,4,6\}      &32     \\
\{0,1,5\}       &       &       &\{2,4,6\}      &       \\
\{0,2,5\}       &24     &       &\{3,4,6\}      &24     \\
\{1,2,5\}       &22     &       &\{0,5,6\}      &32     \\
\{0,3,5\}       &24     &       &\{1.5.6\}      &       \\
\{1,3,5\}       &       &       &\{2,5,6\}      &30     \\
\{2,3,5\}       &24     &       &\{3,5,6\}      &24     \\
\{0,4,5\}       &       &       &\{4,5,6\}      &       \\
\{1,4,5\}       &22     &       &               &       \\
\cline{1-2}\cline{4-5}
\end{tabular}
\end{center}
\caption{Some values of $M(S,2)$}
\label{table2}
\end{figure}


The results in Figure~2 give the values of $M(S,2)$  for some
three-element sets $S$.  The program ran out of {\it space} on all the
entries where no value of $M(S,2)$ is given.  Notice that in all these
cases, the elements of $S$ represent three distinct congruence classes
modulo~3.  We give a partial explanation for this
in the next section.  


\begin{thm}
\label{dilate}
For every finite $S\se\nat$ and $k$, there is an $n=n(S,k)$ such that
$\vvw(nS,k)$ holds.
\end{thm}

\proof
By the compactness property of the
classical van der Waerden Theorem, for every $S$ and $k$,
there is an $m$ such that for any $k$-coloring of $\{0,1,\ldots,m\}$, 
there are $a>0$ and $b\geq 0$ with $aS+b$ monochromatic;
in particular, $a\leq m$ and $b\leq m$.
Let $n=\lcm\{1,2,\ldots,m\}$.  Consider any $k$-coloring $\alpha$ of
$\{0,1,\ldots,mn\}$.  Define a $k$-coloring $\beta$ on $\{0,1,\ldots,m\}$
by $\beta(i)=\alpha(ni)$.  Thus, there are $a$ and $b$, with $0<a\leq m$ and
$0\leq b\leq m$, such that $aS+b$ is monochromatic with respect to $\beta$.
Therefore, $anS+bn$ is monochromatic with respect to $\alpha$.  But
$n$ is divisible by $a$, say $n=ac$, so $a(nS+bc)$ is monochromatic with
respect to $\alpha$.\qed


\section{Negative Instances and Thue-Morse Sequences\-}

As we noted, the sets for the empty entries in Figure~2 consist of
integers representing three distinct congruence classes modulo~3.
We can show
that $\vvw(S,2)$ does not hold when elements of
$S$ represent three distinct congruence classes modulo~3.
(We do not know if the converse holds.)  The proof of this result
will serve as a model for proofs of more general results.

Suppose we run the program described in the
previous section with $S=\{0,1,2\}$ and $k=2$.  The program
does not verify that $\vvw(S,k)$ holds;  instead, when it exhausts the
space that has been allocated to it (160 integers) it outputs
the first 81 colors of the last coloring in its search:
\begin{eqnarray*}
001001101001001101101001101\\
001001101001001101101001101\\
101001101001001101101001101
\end{eqnarray*}
There is a pattern here!  Let $\sigma_i$ be the $i$-th color in
this sequence (beginning with $\sigma_0$ and ending with $\sigma_{80}$).  
If $i\equiv 1(\mod 3)$, then $\sigma_i=0$.  If $i\equiv 2(\mod 3)$, then
$\sigma_i=1$.  For all $i<27$, $\sigma_i=\sigma_{3i}$.  These rules
together with the initial value $\sigma_0=0$ determine the sequence
uniquely and allow us to continue it indefinitely.  There is a more succinct
way to express this sequence as a {\em Thue-Morse sequence}.

We will consider a simple mathematical system (sometimes
called a {\em D0L system} \cite{MR87d:68002}) 
consisting of a finite alphabet $\Sigma$,
a mapping $T:\Sigma\ra\Sigma^*$, and a word 
$w\in \Sigma^*$.  Here $\Sigma^*$ is the set of words over $\Sigma$.
We assume, for simplicity, that $\Sigma$ is a set of integers
$\{0,1,\ldots,k-1\}$; the natural order on $\Sigma$ gives a
lexicographic order on $\Sigma^*$.
Rather than $T(i)=\alpha$, we usually state a {\em rewrite rule} 
$i\ra\alpha$.

We may extend $T$ to a 
mapping $T:\Sigma^*\ra\Sigma^*$ by taking
$$
  T(\alpha_0\alpha_1\cdots\alpha_{l-1})=T(\alpha_0)T(\alpha_1)\cdots
  T(\alpha_{l-1}).
$$
for symbols $\alpha_0,\ldots,\alpha_{l-1}\in\Sigma$.
Similarly, we can extend $T$ to a mapping on infinite words over $\Sigma$.
The study of L systems concerns iterations of $T$ applied to $w$.
If $w$ is a single symbol, say 0, and 
each $i\in\Sigma$ is the initial symbol of $T(i)$, then 
$T^n(0)$ is a prefix of $T^{n+1}(0)$ 
and each of the words $0,T(0),T^2(0),T^3(0),\ldots$ is a prefix of
some (possibly infinite) limit word $\sigma$, called the
{\em Thue-Morse} sequence for $(\Sigma,T,0)$.  
This is the least word in lexicographic order such that
$T(\sigma)=\sigma$.  To specify a Thue-Morse word, it suffices
to list the rewrite rules for $T$, since we take $w=0$.

The famous sequence of Thue 
\cite{thue:1906,thue:1912} and Morse 
\cite{morse:1921,morse:1938} is generated by
the rewrite rules $0\ra 01$ and $1\ra 10$.  It begins
$$
  01101001100101101001100101100110\cdots
$$
and has many interesting combinatorial properties 
\cite{berstel;reutenauer:1983}.

The sequence at the beginning of this section is
generated by the rewrite 
rules $0\ra 001$ and $1\ra 101$.  This sequence is indeed a counterexample
to $\vvw(\{0,1,2\},2)$, as can be seen from the proof of 
the following theorem.

\begin{thm}
\label{modp}
Let $p$ be a prime and $k\geq 2$.  Take $r=\lceil(p-1)/k\rceil+2$. 
If $S$ is
a subset of $\nat$ whose elements represent at least $r$ distinct congruence
classes modulo~p, then $\vvw(S,k)$ does not hold.
\end{thm}

\proof
Let $s=r-2=\lceil(p-1)/k\rceil$, $t=\lfloor(p-1)/k\rfloor$, and $j$
be the remainder when $p-1$ is divided by $k$.  Thus,
$p-1=js+(k-j)t$.  Consider the rewrite rules
$$
  i\ra i\ 0^s\ 1^s\ \cdots\ (j-1)^s\ j^t\ (j+1)^t\ \cdots\ (k-1)^t
$$
for $i=0,1,\ldots,k-1$.  Let    
$\sigma=\sigma_0\sigma_1\sigma_2\cdots$ be the associated Thue-Morse
sequence.We show that  no set of the form $a(S+b)$ is monochromatic
with respect to $\sigma$.

The value of $\sigma_i$ is determined by its congruence
class modulo~$p$, unless $i\equiv 0(\mod p)$.  
No set representing at least $r=s+2$ distinct
congruence classes can be monochromatic because at most one of its
elements is congruent to~0 modulo~$p$, and its other elements
represent at least $s+1$ congruence classes. 

Proceed by contradiction, taking $a(S+b)$ to be a minimal
monochromatic set (i.e., its largest element is minimal).
If $a$ is divisible by~$p$,
$(a/p)(S+b)$ would be a smaller monochromatic set, a contradiction.
If $a$ is not divisible by~$p$,  then the elements of $a(S+b)$
represent at least $r$ distinct congruence classes modulo~$p$,
and hence $a(S+b)$ is not monochromatic.  
Once more we arrive at a contradiction.
\qed

We will improve this result presently.  However, it is already
strong enough to show an important result concerning the variant 
van der Waerden property.

\begin{cor}
\label{morecolors}
If $|S|\geq 3$, there is a $k$ such that $\vvw(S,k)$ fails.
\end{cor}

\proof Let $p$ be a prime larger than the greatest element of
$S$.  Thus, every element of $S$ represents a distinct congruence
class modulo~$p$.  Take $k$ large enough that $|S|\geq \lceil(p-1)/k\rceil+2$.
\qed

When $k$ is reasonably large compared to $p$, Theorem~\ref{modp}
gives very good results with respect to the Thue-Morse sequence.
When $p$ is large compared to $k$, we can obtain better bounds 
using the probabilistic method (see Alon and Spencer 
\cite{alon;spencer:1991}).  

\begin{thm}
\label{prob}
Let $p$ be a prime and $k\geq 2$.  Take $r=\lceil\log_k(p^2-p)\rceil+2$. 
If $S$ is
a subset of $\nat$ whose elements represent at least $r$ distinct congruence
classes modulo~p, then $\vvw(S,k)$ does not hold.
\end{thm}

\proof
In the proof of Theorem~\ref{modp}, the rewrite rules
are of the form $i\ra i\ \alpha$, 
where $\alpha$ is a particular word of
length $p-1$.  The only property of $\alpha$ used in the proof can be stated
as follows.
\begin{quote}
If $\alpha$ is regarded as a $k$-coloring of $\{1,2,\ldots,p-1\}$, then
no set of the form $a(S+b)(\mod p)$ with $a\not\equiv 0\ (\mod p)$
is monochromatic.
\end{quote}
Here $T(\mod p)$
indicates the set formed by replacing every $t\in T$ with an integer
$t'\equiv t\ (\mod p)$, where $0\leq t' < p$.  (If $a(S+b)(\mod p)$ happens
to contain 0, it is considered monochromatic if all its nonzero elements
have the same color.)  If we can show under the hypotheses of the
present theorem that such an $\alpha$ exists, we are done.

Consider a probability space consisting of all $k$-colorings 
$\alpha$ of the set
$\{1,2,\ldots,p-1\}$ with the uniform probability measure.  
Define the random variable $X(\alpha)$ on  this space
to be the number of pairs $(a,b)$ such that $1\leq a<p$, $0\leq b<p$,
and $a(S+b)(\mod p)$ is monochromatic with respect to $\alpha$.  Now let us
estimate $E[X]$, the expectation of $X$.  We may write $X$ as a sum
$X=\sum_{a,b}X_{a,b}$ where
$$
  X_{a,b}(\alpha)= 
 \left\{\begin{array}{ll}
 1,&\mbox{if $a(S+b)(\mod p)$ is monochromatic with respect to $\alpha$;}\\
 0,&\mbox{otherwise.}
 \end{array}\right.
$$
This sum is taken over the range $1\leq a<p$, $0\leq b<p$.  
By linearity of expectation we have  that $E[X]=\sum_{a,b}E[X_{a,b}]$.
Now for fixed values of $a$ and $b$, $a(S+b)(\mod p)$ contains 
at least $r-1$ nonzero elements.  There are $k$ ways to color
them monochromatically, so $E[X_{a,b}]\leq k/k^{r-1}=1/k^{r-2}$.
Thus, $E[X]\leq p(p-1)/k^{r-2}$.  Since $r>\log_k(p^2-p)+2$,
we have $E[X]<1$.  We see that $X$ is a nonnegative integer-valued random
variable with expectation less than~1.  Therefore, for some
$\alpha$, $X(\alpha)=0$.  This is the coloring we seek.\qed


\section{Final Questions}


Many questions remain.  Here are a few questions suggested by
the results of this paper.
\begin{enumerate}
\item Is it the case that $\vvw(S,k)$ holds if and only if
      for every prime $p$, every $k$-coloring of $\{1,2,\ldots,p-1\}$,
      every $a>0$, and every $b\geq 0$, $a(S+b)(\mod p)$ is monochromatic?

\item Is it true that whenever $\vvw(S,k)$ fails, there is
      a Thue-Morse sequence $\alpha$ over the $k$-symbol alphabet
      such that no set of the form
      $a(S+b)$ is monochromatic with respect to $\alpha$?

\item Is there a reason that the 2-coloring turned up by our 
      computer search on $S=\{0,1,2\}$ and  $k=2$ happens to
      be the initial part of a simple Thue-Morse sequence?  In particular,
      if the program continued (with 
      additional space added as needed), would
      it continue to generate the Thue-Morse sequence?  
      The computer generated 2-coloring is  the first 
      counterexample (under lexicographic ordering)  to
      the variant van der Waerden property.
      We conjecture that for all $S$ and $k$ where
      the variant van der Waerden property fails,
      the first counterexample coloring is a Thue-Morse
      sequence.  Readers
      interested in doing computer experiments to
      gain insight into this problem
      might first check to
      see how long it takes for the color of the integer~17 to
      stabilize during the search for a counterexample
      when  $S=\{0,1,2\}$ and  $k=2$.  This will 
      give some idea of the subtleties of the problem.
 
\item We see from Corollary~\ref{morecolors} and Theorem~\ref{dilate}
      that the variant van der Waerden property is affected
      both by dilation of $S$ and number of colors.  For a given $S$ with
      at least three elements, define $F_S(n)$ to be the least $k\geq 1$
      such that $\vvw(nS,k)$ fails.  It follows that 
      $F_S(n)$ is unbounded.  However, it is not monotone in 
      general.  What can we say about the behavior of
      the function $F_S(n)$?

\item Fix $k\geq 2$.  Is there an infinite set $T_k$ such that
      for each finite $S\se T_k$, $\vvw(S,k)$ holds?  A
      possibility for $T_2$ 
      might be  $\{2,\,2\cdot 3,\,2\cdot 3\cdot 5, 
      \,2\cdot 3\cdot 5\cdot 7,\, 2\cdot 3\cdot 5\cdot 7\cdot 11,\ldots\}$.

\item Characterize the $S$ and $k$ for which $\vvw(S,k)$ holds.
\end{enumerate}




\begin{thebibliography}{10}

\bibitem{alon;spencer:1991}
N.~Alon and J.~H. Spencer.
\newblock {\em The Probabilistic Method}.
\newblock Wiley, New York, 1991.

\bibitem{berstel;reutenauer:1983}
J.~Berstel and C.~Reutenauer.
\newblock Square-free words and idempotent semigroups.
\newblock In M.~Lothaire, editor, {\em Combinatorics on Words}, pages 18--38.
  Addison-Wesley, Reading, MA, 1983.

\bibitem{MR97e:05193}
T.~C. Brown and B.~M. Landman.
\newblock The {R}amsey property for collections of sequences not containing all
  arithmetic progressions.
\newblock {\em Graphs Combin.}, 12(2):149--161, 1996.

\bibitem{MR98c:05159}
T.~C. Brown, B.~M. Landman, and M.~Mishna.
\newblock Monochromatic homothetic copies of $\{1,1+s,1+s+t\}$.
\newblock {\em Canad. Math. Bull.}, 40(2):149--157, 1997.

\bibitem{furstenberg:1981}
H.~Furstenberg.
\newblock {\em Recurrence in Ergodic Theory and Combinatorial Number Theory}.
\newblock Princeton University Press, Princeton, 1981.

\bibitem{graham;spencer;rothschild:1990}
R.~L. Graham, B.~L. Rothschild, and J.~H. Spencer.
\newblock {\em Ramsey Theory}.
\newblock Addison-Wesley, Reading, MA, second edition, 1990.

\bibitem{MR90b:11010b}
R.~N. Greenwell and B.~M. Landman.
\newblock On the existence of a reasonable upper bound for the van der
  {W}aerden numbers.
\newblock {\em J. Combin. Theory Ser. A}, 50(1):82--86, 1989.

\bibitem{MR90b:11010a}
B.~M. Landman.
\newblock Generalized van der {W}aerden numbers.
\newblock {\em Graphs Combin.}, 2(4):351--356, 1986.

\bibitem{MR93e:05100}
B.~M. Landman.
\newblock Ramsey functions related to the van der {W}aerden numbers.
\newblock {\em Discrete Math.}, 102(3):265--278, 1992.

\bibitem{MR94d:11006}
B.~M. Landman.
\newblock An upper bound for van der {W}aerden-like numbers using $k$ colors.
\newblock {\em Graphs Combin.}, 9(2):177--184, 1993.

\bibitem{MR94m:05195}
B.~M. Landman.
\newblock Ramsey functions associated with second order recurrences.
\newblock {\em J. Combin. Math. Combin. Comput.}, 15:119--127, 1994.

\bibitem{MR98i:05163}
B.~M. Landman.
\newblock Avoiding arithmetic progressions (mod $m$) and arithmetic
  progressions.
\newblock {\em Util. Math.}, 52:173--182, 1997.

\bibitem{MR1633760}
B.~M. Landman.
\newblock Monochromatic sequences whose gaps belong to $\{d,2d,\cdots,md\}$.
\newblock {\em Bull. Austral. Math. Soc.}, 58(1):93--101, 1998.

\bibitem{MR1628121}
B.~M. Landman.
\newblock Ramsey functions for quasi-progressions.
\newblock {\em Graphs Combin.}, 14(2):131--142, 1998.

\bibitem{MR89d:05021}
B.~M. Landman and R.~N. Greenwell.
\newblock Values and bounds for {R}amsey numbers associated with polynomial
  iteration.
\newblock {\em Discrete Math.}, 68(1):77--83, 1988.

\bibitem{MR91i:05117}
B.~M. Landman and R.~N. Greenwell.
\newblock Some new bounds and values for van der {W}aerden-like numbers.
\newblock {\em Graphs Combin.}, 6(3):287--291, 1990.

\bibitem{MR97a:05209}
B.~M. Landman and A.~F. Long.
\newblock Ramsey functions for sequences with adjacent differences in a
  specified congruence class.
\newblock In {\em Proceedings of the Twenty-fifth Southeastern International
  Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL,
  1994)}, volume 103, pages 3--20, 1994.

\bibitem{MR98b:05099}
B.~M. Landman and B.~Wysocka.
\newblock Collections of sequences having the {R}amsey property only for few
  colours.
\newblock {\em Bull. Austral. Math. Soc.}, 55(1):19--28, 1997.

\bibitem{morse:1921}
M.~Morse.
\newblock Recurrent geodesics on a surface of negative curvature.
\newblock {\em Trans. Amer. Math. Soc.}, 22:84--100, 1921.

\bibitem{morse:1938}
M.~Morse.
\newblock A solution of the problem of infinite play in chess.
\newblock {\em Bull. Amer. Math. Soc.}, 44:632, 1938.

\bibitem{pin:1983}
J.-E. Pin.
\newblock Van der {W}aerden's theorem.
\newblock In M.~Lothaire, editor, {\em Combinatorics on Words}, pages 39--54.
  Addison-Wesley, Reading, MA, 1983.

\bibitem{MR87d:68002}
A.~Salomaa.
\newblock {\em Computation and automata}.
\newblock Cambridge University Press, Cambridge, 1985.
\newblock With a foreword by Grzegorz Rozenberg.

\bibitem{shelah:1988}
S.~Shelah.
\newblock Primitive recursive bounds for van der {W}aerden numbers.
\newblock {\em J. Amer. Math. Soc.}, 1:683--697, 1988.

\bibitem{thue:1912}
A.~Thue.
\newblock \"{U}ber die gegenseitige {L}age gleicher {T}eile gewisser
  {Z}eichenreihen.
\newblock In T.~Nagell, A.~Selberg, S.~Selberg, and K.~Thalberg, editors, {\em
  Selected Mathematical Papers of {A}xel {T}hue}, pages 413--477.
  Universitetsforlaget, Oslo, 1977.

\bibitem{thue:1906}
A.~Thue.
\newblock \"{U}ber unendliche {Z}eichenreihen.
\newblock In T.~Nagell, A.~Selberg, S.~Selberg, and K.~Thalberg, editors, {\em
  Selected Mathematical Papers of {A}xel {T}hue}, pages 139--158.
  Universitetsforlaget, Oslo, 1977.

\bibitem{waerden:1927}
B.~L. van~der Waerden.
\newblock Beweis einer {B}audet'schen {V}ermutung.
\newblock {\em Nieuw Arch. Wisk.}, 15:212--216, 1927.

\end{thebibliography}






\end{document}