%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-18/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{thrm}{Theorem}
\newtheorem{corl}[thrm]{Corollary}
\newtheorem{lmma}[thrm]{Lemma}
\newtheorem{conj}{Conjecture}
\newtheorem{prop}[thrm]{Proposition}

\title{Monochromatic Arithmetic Progressions With Large Differences}
\author{Tom C. Brown and Bruce M. Landman}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown} and Bruce~M. Landman, \emph{Monochromatic arithmetic progressions with large differences},
  Bull. Austral. Math. Soc. \textbf{60} (1999), no.~1, 21--35.}\bigskip\end{center}

\newcommand{\ceil}[1]{{\left\lceil{#1}\right\rceil}}

\begin{abstract}A generalisation of the van der Waerden numbers $w(k,r)$ is
considered. For a function $f:\mathbb{Z}^+\to\mathbb{R}^+$ define
$w(k,f,r)$ to be the least positive integer (if it exists) such that
for every $r$-coloring of $\left[1,w(f,k,r)\right]$ there is a
monochromatic arithmetic progression $\{a+id:0\leq i \leq k - 1\}$
such that $d\geq f(a)$. Upper and lower bounds are given for
$w(f,3,2)$. For $k>3$ or $r>2$, particular functions $f$ are given
such that $w(f,k,r)$ does not exist. More results are obtained for
the case in which $f$ is a constant function.
\end{abstract}

\section{Introduction}

It was proved by wan der Waerden \cite{vanderwaerden1927,vanderwaerden1971}
that for arbitrary positive integers $k$ and $r$, there exists a least
positive integer $w(k,r)$ such that whenever the interval $\intv{w(k,r)}
= \{1,2,\ldots,w(k,r)\}$ is $r$-colored, there must be a monochromatic
$k$-term arithmetic progression $\left\{a,a+d,a+2d,\ldots,a+(k-1)d\right\}$
(in other words, if $\intv{w(k,r)}$ is partitioned into $r$ parts, then
one part contains a $k$-term arithmetic progression).

In this paper, we shall consider a generalisation of $w(k,r)$. Namely,
let $f$ be an arbitrary function from the set of positive integers to
the set of positive reals. We ask whether or not there exists a smallest
positive integer $w(f,k,r)$ such that whenever $\intv{w(f,k,r)}$ is
$r$-colored, there must exist a monochromatic $k$-term arithmetic progression
$\left\{a,a+d,a+2d,\ldots,a+(k-1)d\right\}$, with $d\geq f(a)$. For example,
if $f(x) = x^2$ and $k = 3$, then we are interested in arithmetic progressions
such as $\{2,6,10\}$, $\{2,7,12\}$ and $\{3,12,21\}$, but would ignore
$\{2,3,4\}$, $\{2,4,6\}$ $\{2,5,8\}$ and $\{3,11,19\}$.

In Section \ref{s2}, we consider $w(f,k,r)$ when $f$ is a constant function.
Section \ref{s3} deals with the more general case of $f:\mathbb{Z}^\to
\mathbb{R}^+$. Section \ref{s4} includes a brief discussion of some related
work that has been done, as well as a few remarks and open questions.

We shall use the following terminology. For an arithmetic progression $A
= \left\{a,a+d,a+2d,\ldots,a+(k-1)d\right\}$, we call $d$ the \emph{common
difference} of $A$. If $f:\mathbb{Z}^\to\mathbb{R}^+$, and $d\geq f(a)$,
we say that $A$ is an \emph{$f$-arithmetic progression}. Thus, $w(f,k,r)$
is the least positive integer such that for every $r$-coloring of
$\intv{w(f,k,r)}$ there is a $k$-term monochromatic $f$-arithmetic progression.
If $\chi$ is a coloring (of some set of positive integers) that yields no
monochromatic $k$-term $f$-arithmetic progression, we say that $\chi$ is
\emph{$(f,k)$-valid}.

To represent a particular $r$-coloring of an interval of size $n$, we shall
often use a string of digits. For example, the string 11000 could be used
to denote the 2-coloring of $[1,5]$, where the color of the first two elements
is 1 and the color of the last three elements is 0.

\section{\label{s2} The Case in Which $f$ is Constant}

When $f$ is the constant function $c$, we denote $w(f,k,r)$ by $w(c,k,r)$.
It is clear that $w(1,k,r) = w(k,r)$ and $w(c_1,k,r) \leq w(c_2,k,r)$
whenever $c_1\leq c_2$.

The existence of $w(c,k,r)$ is well-known. By the following proposition,
we see that it is always bounded above by $\ceil{c}(w(k,r) - 1) + 1$.

\begin{prop}\label{p1} Let $c_0>0$, and let $M = w(c_0,k,r)<\infty$. Then
for all $c\geq c_0$,
\[ w(c,k,r) \leq \ceil{\frac{c}{c_0}}(M - 1) + 1 \]\end{prop}
\begin{proof} Let $j = \ceil{c/c_0}$. Every $r$-coloring of $\{1,j+1,
2j+1,\ldots,(M-1)j+1\}$ yields a monochromatic $k$-term arithmetic
progression with common difference at least $jc_0\geq c$.\end{proof}

In \cite{landman1999-1} it was noted that $w(c,3,2) = 8c + 1$. The
fact that $8c+1$ is an upper bound follows from Proposition \ref{p1},
since $w(3,2) = 9$. That $8c + 1$ is also a lower bound may be seen
by considering the coloring $S_1S_2S_1S_2$ where $S_1$ is a string
of 1's having length $2c$ and $S_2$ is a string of 0's having length
$2c$. We may generalise this coloring to obtain a lower bound for
$w(c,k,r)$. Namely, let $\lambda(c,k,r)$ denote the $r$-coloring
$\lambda:\intv{cr(k-1)^2}\to\{0,1,\ldots,r-1\}$ defined by the string
\[ (B_1B_2\ldots B_r)(B_1B_2\ldots B_r)\ldots(B_1B_2\ldots B_r),\]
where for each $i\in\{1,\ldots,r-1\}$, $B_i$ is a string of $i$'s
having length $c9k-1)$, $B_r$ is a string of 0's having length
$c(k-1)$, and where there are $(k-1)$ copies of the block $(B_1B_2
\ldots B_r)$. For example, $\lambda(3,3,2) = 111111000000111111000000$.

By using $\lambda(c,k,r)$ we have the following result.

\begin{prop}\label{p2} For all positive integers $c,k,r$ with $k,r\geq 2$,
\[ w(c,k,r) \geq cr(k-1)^2 + 1. \]\end{prop}
\begin{proof} Let $M = cr(k-1)^2$. It is clear that if we color $[1,M]$
with the coloring $\lambda(c,k,r)$, there will be no monochromatic $k$-term
arithmetic progression with common difference at least $c$.\end{proof}

We have run a computer program to calculate various values of $w(c,k,r)$.
In addition to giving the value of $w(c,k,r)$, the program also lists all
the $r$-colorings of maximal length that avoid monochromatic $k$-term
arithmetic progressions with common difference at least $c$ (that is,
the $(c,k)$-valid $r$-colorings). It is well-known that the (1,3)-valid
2-colorings of $[1,8]$ are 11001100, 10100101, and 10011001, and, of
course, the three colorings obtained from these by reversing the roles
of 0 and 1. Note that the first of these colorings is the coloring
$\lambda(1,3,2)$ described above. The following theorem shows that for
all $c\geq2$, $\lambda(c,3,2)$ is the \emph{only} maximal length $(c,3)$-valid
2-coloring (assuming that 1 is assigned the color 1).

Before proceeding we adopt the following notation. We shall denote the
following colorings of $[1,8]$ by the given symbols:
\[ \begin{array}{llll} A = 11001100 &A' = 00110011 &B = 10011001 &B' = 01100110\\
C = 10100101 &C' = 01011010. \end{array} \]

We need the following two lemmas.

\begin{lmma} \label{l3} Let $c,k$ and $m$ be positive integers, and let
$g$ be a $(c,k)$-valid 2-coloring of $[1,mc]$. Let $i\in\{1,2,\ldots,c\}$.
Let $g^*$ be the coloring of $[1,m]$ defined by $g^*(j) = g((j-1)c + i)$
for each $j = 1,\ldots, m$. Then $g^*$ is $(1,k)$-valid on $[1,m]$.\end{lmma}
\begin{proof} Assume $g^*$ is not $(1,k)$-valid. Then there is a $g^*$-monochromatic
arithmetic progression $\{a,a+d,\ldots,a+(k-1)d\} \subseteq [1,m]$. Then
$\{ (a-1)c + i, (a - 1 + d)c + i, \ldots, (a - 1 + (k - 1)d)c + i\}$ is
a $g$-monochromatic arithmetic progression, contained in $[1,mc]$, having
common difference of $cd\geq c$, contradicting the fact that $g$ is $(c,k)$-valid.
\end{proof}

\begin{lmma}\label{l4} If $c\geq 3$ and $g$ is a $(c,3)$-valid 2-coloring
of $[1,8c]$ with $g(c) = 1$, then $S = \{c, 2c, \ldots, 8c\}$ has color
pattern $A = 11001100$.\end{lmma}
\begin{proof} Define $g^*$ on $[1,8]$ by $g^*(j) = g(jc)$. By Lemma \ref{l3},
$g^*$ is (1,3)-valid. Hence, since $g(c) = 1$, as noted earlier, $g^*$ has
one of the color patterns $A$, $B$ or $C$, so that $S$ has one of these three
color patterns. To complete the proof, we show that $S$ cannot have color
pattern $B$ or $C$.

We consider two cases.

\paragraph{Case I.} $c$ is odd. Let $T = \{1, c+1, 2c + 1, \ldots, 7c + 1\}$.
By Lemma \ref{l3}, the function $g'$ defined on $[1,8]$ by $g'(j) = g((j-1)c+1)$
has one of the six color patterns $A$, $A'$, $B$, $B'$, $C$, or $C'$; that is,
under $g$, $T$ has one of these six color patterns.

First assume, by way of contradiction, that $S$ has color pattern $B$.

If $T$ has coloring $A$ or $C'$, then we have $g(c+1) = g(8c) = 1$. Hence, $g(4.5c
+ 1/2) = 0$ (for otherwise $g$ is not $(c,3)$-valid). This implies that $\{2c + 1,
4.5c + 1/2, 7c\}$ is monochromatic under $g$, a contradiction.

The remaining possibilities for coloring $T$ are $B'$ and $C$. For each of these
cases, $g(2c+1) = g(5c) = 1$, so that $g(8c - 1) = 0$. Then $\{ 4c + 1, 6c, 8c-1\}$
is monochromatic with common difference at least $c$, a contradiction.

Now assume that $S$ has color pattern $C$.

If $T$ has any of the color patterns $A$, $B'$, or $C$, then $g(3c) = g(5c + 1)
= 1$, so that $g(c-1) = 0$. This implies that $\{c-1,2c,3c+1\}$ is monochromatic,
which is not possible. If $T$ has either of the color patterns $A'$ or $C'$, then
$g(c) = g(6c+1) = 1$, implying that $g(3.5c+1/2)=0$; but then $\{ 2c,3.5c+1/2,5c
+1\}$ is monochromatic, a contradiction. Finally, if $T$ has color pattern $B$,
the fact that $g(4c+1) = 1$ and $g(6c+1) = 0$ yields a contradiction in a similar
fashion, by first looking at $\{2c-1,3c,4c+1\}$ and then $\{2c-1,4c,6c+1\}$.

\paragraph{Case II.} $c$ is even. This is done in the same way as case I, but
instead of using the set $T$, we use $U = \{2,c+2,2c+2,\ldots,7c+2\}$. Since
this is quite similar to case I, we do two subcases, and omit the rest.

If $S$ has color pattern $B$ and $U$ has color pattern $A$, then $g(c+2) = g(8c)
= 1$, so $g(4.5c+1) = 0$; but then $\{ 2c+2,4.5c+1,7c\}$ is monochromatic, giving
a contradiction.

If $S$ has color pattern $B$ and $U$ has one of the colorings $A'$ or $B$, then
$g(4c) = g(7c+2) = 1$, and hence $g(c-2) = 0$ (note that $c - 2 > 0$). Then $\{
c-2,3c,5c+2\}$ is monochromatic, which is not possible.\end{proof}


\begin{thrm}\label{t5} Assume $c\geq2$ and $g$ is a 2-coloring of $[1,8c]$ with
$g(1) = 1$. If $g$ is $(c,3)$-valid on $[1,8c]$, then $g = \lambda(c,3,2)$.\end{thrm}
\begin{proof} For $c = 2$, one can check directly that 1111000011110000 is the
only valid 2-coloring of $[1,16]$ such that 1 is given color 1.

Now let $c\geq 3$ and let $g$ be a 2-coloring of $[1,8c]$ such that $g(c) = 1$.
It suffices to show that for each $i=1,2,\ldots,c$,
\begin{equation} \label{e1} T_i = \{ (j-1)c + i:1 \leq j \leq 8 \} \text{ has color scheme 11001100.} \end{equation}

By Lemma \ref{l4}, \eqref{e1} holds for $i = c$. Now consider $i\in\{1,\ldots,c-1\}$.

Let $g_i$ be the coloring of $[1,8]$ defined by $g_i(j) = g((j-1)c + i)$. Then
by Lemma \ref{l3}, $g_i$ is (1,3)-valid on [1,8]. Thus $g_i$ has one of the color
patterns $A$, $A'$, $B$, $B'$, $C$, $C'$. Thus, it suffices to show that $T_i$
does not have any of the color patterns $A$, $A'$, $B$, $B'$, $C$, $C'$.

If $T_i$ has one of the patterns $A'$, $B$, or $C$, then $g(c + i) = g(3c)$,
which implies that $\{ 5c-i, 6c, 7c + i\}$ is monochromatic, a contradiction.

If $T_i$ has the pattern $B'$, then $g(2c + i) = g(5c)$, so that $g(8c-i)
= g(4c) = g(i)$, again a contradiction.

Finally, if $T_i$ has pattern $C'$, then $g(i) = g(4c) = 0$. This implies that
$\{ 3c+i, 5c,7c-i\}$ is monochromatic, also impossible.\end{proof}

Although we do not have a result analogous to Theorem \ref{t5} for arithmetic
progressions of length greater than three, we do have some evidence that suggests
a similar result may be true. Namely, we have computed the values of $w(c,4,2)$
for all $c,1\leq c \leq 12$. In Table \ref{tab:t1}, we list these values.
In the third column of Table \ref{tab:t1}, we give the lower bound for $w(c,4,2)$
as provided by Proposition \ref{p2}.

\begin{center}\begin{table}
\centering
\begin{tabular}{||c|c|c||}
\hline\hline
$c$ & $w(c,4,2)$ & lower bound \\
\hline
1 & 35 & 19 \\
2 & 45 & 37 \\
3 & 63 & 55 \\
4 & 75 & 73 \\
5 & 92 & 91 \\
6 & 109 & 109 \\
7 & 127 & 127 \\
8 & 145 & 145 \\
9 & 163 & 163 \\
10 & 181 & 181 \\
11 & 199 & 199 \\
12 & 217 & 217 \\
\hline\hline
\end{tabular}
\caption{Values of $w(c,4,2)$}
\label{tab:t1}
\end{table}\end{center}

We notice from Table \ref{tab:t1}, that as $c$ increases from 1 to 6,
the ratio of $w(4,3,2)$ to the lower bound of Proposition \ref{p2}
decreases, and for each $c$, $6\leq c\leq12$, these two values are
equal. We have also found, for each $c$ in the table, all maximal
length $(c,4)$-valid 2-colorings (that is, $(c,4)$-valid 2-colorings
of $\intv{w(c,4,2)-1}$). For each $c$, $6\leq c\leq 11$, all maximal
length $(c,4)$-valid 2-colorings have a rather simple form that is
quite similar to $\lambda(c,4,2)$ (of course, by Proposition \ref{p2},
one of these colorings is $\lambda(c,4,2)$).

Based on Theorem \ref{t5} and the computer data for $k=4$, we offer
the following conjectures.

Let us first adopt the following notation: for $c\in\mathbb{Z}^+$,
denote by $I_1$ and $I_0$ a string of 1's with length $3c$ and a
string of 0's with length $3c$, respectively. If $c$ is even, denote
by $J_1$ and $J_0$, monochromatic strings of length $(3/2)c - 1$ of
1's and 0's, respectively. Finally, if $c$ is odd, denote by $K_1$ and
$K_0$ strings of length $(3c-1)/2$ of 1's and 0's, respectively.

\begin{conj}\label{cj1} Let $c\geq6$ and let $g$ be a $(c,4)$-valid
2-coloring of $[1,18c]$, with $g(1)=1$. If $c$ is even, then $g$ is
one of the colorings $J_1abJ_1I_0I_1I_0I_1J_0cdJ_0$, where $a,b,c,d$
may be assigned any colors. If $c$ is odd, then $g$ is one of the
colorings $K_1uK_1I_0I_1I_0I_1K_0vK_0$, where $u,v$ may be assigned
any colors.\end{conj}

Note that if $a=b=u=1$ and $c=d=v=0$ in Conjecture \ref{cj1}, then
the only valid colorings we get are $\lambda(c,4,2)$. Also, if
Conjecture \ref{cj1} is true, then there are exactly sixteen valid
colorings of $[1,18c]$ if $c$ is even, and four if $c$ is odd (assuming
$g(1) = 1$). Finally, note that Conjecture \ref{cj1} would imply
$w(c,4,2) = 18c+1$ for all $c\geq6$, because none of the colorings
described in the conjecture can be extended to a $(c,4)$-valid
2-coloring of $[1,18c+1]$ (it is true that $w(c,4,2) = 18c + 1$
for all $c$ that are multiples of 6, by virtue of the fact that
$w(6,4,2)\leq109$ and Propositions \ref{p1} and \ref{p2}).

\begin{conj}\label{cj2} For all $k\geq2$, there is a least positive
integer $c_k$ such that $w(c_k,k,2) = 2c_k(k-1)^2 + 1$.\end{conj}

By Table \ref{tab:t1}, the fact that $w(3,2) = 9$, and the trivial
case of $k = 2$, we have that $c_2 = 1$, $c_3 = 1$, and $c_4 = 6$.
Our hope is that for each $k\geq5$ and $c_k'$ large enough, one
could describe in a simple manner all of the $(c_k',k)$-valid
2-colorings of $\intv{2c_k(k-1)^2}$ (as is the case, for example,
with $(c_k',k) = (2,3)$ and $(c_k',k) = (6,4)$). Finding a
reasonable upper bound for such a $c_k$ or $c_k'$ is most certainly
a difficult problem, since such an upper bound would yield an
upper bound on the classical van der Waerden numbers.

We note that the above discussion, and the conjectures, can be extended
from two colors to $r$ colors in an obvious way. When $r = 3$, we
have found that $w(1,3,3) = 27$, $w(2,3,3) = 38$, $w(3,3,3) = 51$,
$w(4,3,3) = 67$, but do not know any other values (a conjecture
for $k = r = 3$ would be that for large enough $c$, $w(c,3,3) = 12c+1$).

\section{\label{s3} The General Case}

In this section we consider the function $w(f,k,r)$ where $f$ is a
function from the positive integers to the positive real numbers.

We begin with the simplest case, namely $k=2$. To simplify the notation
in this case, we assume that $f$ is a function from the positive integers
to the positive integers. If $g$ is a function, the symbol $g^{(r)}$
will denote the $r$th iterate of $g$.

\begin{thrm}\label{t6} Let $f:\mathbb{Z}^+\to\mathbb{Z}^+$ be
nondecreasing. Then $w(f,2,r) = g^{(r)}(1)$, where $g(x)=f(x)+x$.
\end{thrm}
\begin{proof} To show that $g^{(r)}(1)$ serves as an upper bound,
consider any $r$-coloring of $\intv{g^{(r)}(1)}$. Then there must
be two members of the set $\{1,g(1),g^{(2)}(1),\ldots,g^{(r)}(1)\}$
with the same color, say $g^{(i)}(1)$ and $g^{(j)}(1)$, where
$0\leq i<j\leq r$. Since
\[ g^{(j)}(1) - g^{(i)}(1) \geq g^{(i+1)}(1) - g^{(i)}(1) = f(g^{(i)}(1)), \]
there is a monochromatic 2-term $f$-arithmetic progression.

To complete the proof we give an $r$-coloring $\chi$ of $\intv{g^{(r)}(1)-1}$
under which there is no monochromatic 2-term $f$-arithmetic progression.
Namely, for $i=1,\ldots,r$, let $A_i=[g^{(i-1)}(1),g^{(i)}(1)-1]$, and
let $\chi(A_i) = i$. Now, for each $i$, no two members of $A_i$ differ
by more than $f(g^{(i)}(1))-1$. Since $f$ is non-decreasing, there do
not exist $a,b\in A_i$ with $b-a > f(a) - 1$.\end{proof}

We now consider $w(f,3,2)$. We give two proofs of the fact that $w(f,3,2)$
exists. The first is a simple argument that merely shows the existence of
this number. The second proof, under the assumption that $f$ is non-decreasing,
gives an upper bound on $w(f,3,2)$.

\begin{thrm}\label{t7} Let $f$ be arbitrary function from $\mathbb{Z}^+$
to $\mathbb{R}^+$. Then $w(f,3,2)$ exists.\end{thrm}
\begin{proof} Let us assume without loss of generality that $f$ is non-decreasing.
We show that every 2-coloring of $\mathbb{Z}^+$ produces a progression of the
desired type. By the compactness principle, the result follows.

Let $g$ be a 2-coloring of $\mathbb{Z}^+$. We identify $g$ with the binary
sequence $g(1)g(2)g(3)\ldots$. If this sequence does not contain infinitely
many 001's (that is $g(y) = 0$, $g(y+1) = 0$, $g(y+2) = 1$ for infinitely
many $y$'s) or infinitely many 110's, then the sequence has a tail consisting
of 000\ldots or 111\ldots or 101010\ldots, and the result follows immediately.

Assume that 001 occurs infinitely often. Choose two occurrences, say $g(x) = 0$,
$g(x + 1) = 0$, $g(x+2) = 1$, and $g(x+d) = 0$, $g(x+d+1)= 0$, $g(x+d+2) = 1$,
where $d\geq f(x+2)$.

If $g(x+2d+2) = 1$, then $\{x+2,x+d+2,x+2d+d\}$ is the desired progression.
If $g(x+2d+2) = 0$, then $\{x,x+d+1,x+2d+2\}$ is the desired progression.
\end{proof}

The second proof we give of Theorem \ref{t7} uses the following two lemmas.

\begin{lmma}\label{l8} Let $f$ be a non-decreasing function from $\mathbb{Z}^+$
to $\mathbb{R}^+$. Let $a\geq1$, $e\geq1$, $d\geq3e+f(a+4e)$, and $n\geq a+2d$.
Assume that $g$ is a 2-coloring of $[1,n]$ such that there does not exist a
monochromatic 3-term $f$-arithmetic progression. Assume that $g(a) = 0$, $g(a+2e)=1$,
and $g(a+4e)=0$. Then $g(a+d) = g(a+d+e)$.\end{lmma}
\begin{proof} There are two cases, depending on the color of $a+d$.

Suppose first that $g(a+d) = 0$. Then $g(a+2d) = 1$, since otherwise the
$f$-arithmetic progression $\{a,a+d,a+2d\}$ would be monochromatic. Since
$g(a+2e) = g(a+2d+2(d-e)) = 1$, we must have $g(a+d+e) = 0$, for otherwise
the $f$-arithmetic progression $\{a + 2e, a + 2e + (d-e), a+2e+2(d-e)\}$
would be monochromatic.

Suppose next that $g(a+d) = 1$. Then $g(a+2d - 2e) = 0$, since otherwise
$\{a+2e,a+2e+(d-2e),a+2e+2(d-e)\}$ would be a monochromatic $f$-arithmetic
progression. Since now $g(a+4e) = 0$ and $g(a+4e+2(d-3e)) = 0$, we must
have $g(a+d+e) = 1$, for otherwise the $f$-arithmetic progression $\{a+4e,
a+4e+(d-3e),a+4e+2(d-3e)\}$ would be monochromatic.\end{proof}

\begin{lmma}\label{l9} Let $f$ be a non-decreasing function from $\mathbb{Z}^+$
to $\mathbb{R}^+$. Let $a,e$ and $q$ be positive integers and let $d\geq3e +
f(a+4e)$ and $n\geq a + 2(d+qe)$. Assume that $g$ is an $(f,3)$-valid 2-coloring
of $[1,n]$. If $g(a) = 0$, $g(a+2e) = 1$, and $g(a+4e) = 0$, then
the set $\{a+d+ie:0\leq i \leq q + 1\}$ is monochromatic.\end{lmma}

\begin{proof} Lemma \ref{l8} gives $g(a+d) = g(a+d+e)$. Replacing $d$ by
$d+e$, and applying Lemma \ref{l8} again, gives $g(a+d+e) = g(a+d+2e)$.
We repeat this until the desired monochromatic sets is obtained.\end{proof}

\setcounter{thrm}{6}
\begin{thrm}{(Stronger version.)} Let $f$ be a non-decreasing
function from $\mathbb{Z}^+$ to $\mathbb{R}^+$. Let $b = 1+ 4\ceil{f(1)/2}$.
Then
\begin{equation}
w(f,3,2) \leq \ceil{4f\left(b + 4\ceil{\frac{f(b)}2}\right) + 14\ceil{\frac{f(b)}2} + 7b/2 - 13/2}.
\label{eq2}\end{equation}
\end{thrm}
\setcounter{thrm}{9}
\begin{proof}Let $p = \ceil{f(1)/2}$ and $s = \ceil{f(b)/2}$. Now let $g$ be
any 2-coloring of $[1,n]$ where $n$ represents the right-hand side of
\eqref{eq2}. Assume that $g$ is $(f,3)$-valid. We shall obtain a contradiction
by means of Lemma \ref{l9}.

Without loss of generality, assume that $g(1) = 0$. The proof is divided
into three cases.
\paragraph{Case 1.} $g(1+4p) = 0$. Since $\{1,1+2p,1+4p\}$ is an $f$-arithmetic
progression, we must have $g(1+2p) = 1$. Now choose $t\in\mathbb{Z}^+$ so that
\[ 4p + f(1+4p) - 1 \geq tp \geq 3p + f(1+4p) \]
Then
\begin{align*}
n &\geq 4f(1+4p+4s) + 14(p+s) - 3 \\
&> 4f(1+4p) + 14p - 3 \\
&= 1 + 4(4p + f(1+4p) - 1) - 2p \\
&\geq 1 + 4tp - 2p \\
&= 1 + 2(tp + (t-1)p).
\end{align*}

We now apply Lemma \ref{l9} with $a=1$, $e=p$, $d=tp$, and $q=t-1$, and conclude
that the set $\{1 + tp + ip : 0 \leq i \leq t\}$ is monochromatic. In particular,
$1 + tp$, $1 + (pt - 2)p$, and $1 + 2tp$ all have the same color.

If $g(1+tp) = 0$, then $\{1,1+tp,1+2tp\}$ is a monochromatic $f$-arithmetic
progression. If $g(1+tp) = 1$, then $\{1 + 2p, 1+2p + (t-2)p, 1 + 2p + 2(t-2)p\}$
is a monochromatic $f$-arithmetic progression. These contradictions finish Case 1.

\paragraph{Case 2.} $g(1+4p) = 1$ and $g(1+4p+4s) = 0$. Since $\{1,1+2(p+s),1+
4(p+s)\}$ is an $f$-arithmetic progression, we must have $g(1+2(p+s)) = 1$. We
shall apply Lemma \ref{l9} using $g(1) = 0$, $g(1+2(p+s)) = 1$, and $g(1+4(p+s)) = 0$.

Define $t$ to be the positive integer such that
\[ 4(p+s) + f(1+4p+4s) - 1 \geq t(p+s)\geq 3(p+s) + f(1+4p+4s).\]
Then
\begin{align*}
n &\geq 4f(1+4p+4s) + 14(p+s) - 3 \\
&= 1 + 4(4(p+s) + f(1+4p+4s) - 1) - 2(p+s) \\
&\geq 1 + 4t(p+s) - 2(p+s) \\
&= 1 + 2(t(p+s) + (t-1)(p+s)).
\end{align*}

Hence Lemma \ref{l9} applies with $a=1$, $e=p + s$, $d=t(p+s)$, and $q = t-1$,
and we conclude that $\{1+t(p+s)+i(p+s): 0\leq i \leq t\}$ is monochromatic.
In particular $1 + t(p+s)$, $1 + (2t-2)(p + s)$, and $1 + 2t(p+s)$ all have
the same color.

If $g(1+t(p+s)) = 0$, then $\{1,1+t(p+s), 1 + 2t(p+s)\}$ is a monochromatic
$f$-arithmetic progression. If $g(1+t(p+s)) = 1$, then $\{1+2(p+s),1+2(p+s)
+ (t-2)(p+s), 1 + 2(p+s) + 2(t-2)(p+s)\}$ is a monochromatic $f$-arithmetic
progression. In either case, we again have a contradiction.

\paragraph{Case 3.} $g(1 + 4p) = 1$, $g(1 + 4p + 4s) = 1$. Since $\{1+4p,
1+4p+2s,1+4p+4s\}$ is an $f$-arithmetic progression, we must have $g(1+4p+2s)
= 0$. Define $t$ to be the integer such that
\[ 4s + f(1+4p+4s) - 1 \geq ta \geq 3s + f(1+4p+4s). \]
Then
\begin{align*}
n &> 1 + 4(4s + f(1+4p+4s)-1) - 2a \\
&\geq 1 + 4ts - 2s \\
&= 1 + 2(ts + (t-1)s).
\end{align*}

Hence Lemma \ref{l9} applies (with the colors reversed) with $a = 1+4p$,
$e+s$, $d = ts$ and $q = t-1$, and we conclude that the set $\{1+4p+ts
+ is : 0 \leq i \leq t\}$ is monochromatic. In particular, $1 + 4p + ts,
1 + 4p + (2t-2)s$, and $1 + 4p + 2ts$ have the same color.

If $g(a+4p + ts) = 1$, then $\{ 1 + 4p, 1 + 4p + ts, 1 + 4p + 2ts\}$
is a monochromatic $f$-arithmetic progression. If $g(a +4p+ts) = 0$,
then $\{1 + 4p + 2s, 1 + 4p+2s + (t-2)s, 1 + 4p + 2s + 2(t-2)s\}$ is
a monochromatic $f$-arithmetic progression. These contradictions finish
Case 3 and the proof of the theorem.\end{proof}

The next result gives a lower bound for $w(f,3,2)$. To simplify the
notation, we again assume that $f$ is a function from the positive
integers to the positive integers.

\begin{thrm}\label{t10} Let $f$ be a non-decreasing function from $\mathbb{Z}^+$
to $\mathbb{Z}^+$ with $f(n) \geq n$ for all $n\in\mathbb{Z}^+$. Let $h = 2f(1)+1$.
Then $w(f,3,2)\geq 8f(h) + 2h + 2 - c$, where $c$ is the largest integer
such that $f(c) + c \leq 4f(h) + h + 1$.\end{thrm}
\begin{proof} Let $M = 8f(h) + 2h + 1 - c$. We shall give a 2-coloring of $[1,M]$
for which there is no monochromatic 3-term $f$-arithmetic progression; the existence
of the coloring proves the theorem.

Let $A_1 = [1,h-1]$, $A_2 = [h, 2f(h) + h - 1]$, $A_3 = [2f(h) + h, 4f(h) + h]$,
and $A_4 = [4f(h) + h + 1, M]$. Define $\chi:[1,M]\to\{0,1\}$ by $\chi(A_1\cup A_3)
= 1$ and $\chi(A_2\cup A_4) = 0$.

Assume that $X = \{x_1,x_2,x_3\}$ is an $f$-arithmetic progression in $[1,M]$
that is monochromatic under $\chi$. Say $x_2 - x_1 = x_3 - x_2 = d \geq f(x_1)$.
Using the fact that $\chi(x_1) = \chi(x_2)$, we split the proof up into six cases,
each of which gives a contradiction.

\paragraph{Case 1.} $x_1,x_2\in A_1$. Then since $f(1)\leq d\leq h-2$, we have
$1 + 2f(1) \leq x_3 \leq 2h - 3$. Thus $x\in A_2$, contradicting the fact that
$X$ is monochromatic.

\paragraph{Case 2.} $x_1\in A_1,x_2\in A_3$. Then $d\geq 2f(h)+1$, and hence
$x_3\geq 4f(h) + h + 1$. This again implies $\chi(x_3) = 0$, a contradiction.

\paragraph{Case 3.} $x_1,x_2\in A_3$. Then
\[ x_3 \geq x_1 + 2f(x_1) \geq 2f(h) + h + 2f(2f(h) + h) \geq 4f(h) + h + 1, \]
so that $\chi(x_3) = 0$.

\paragraph{Case 4.} $x_1,x_2\in A_2$. In this case, $d\leq 2f(h) - 1$, and
therefore $x_3\leq x_2 + 2f(h) - 1\leq 4f(h)+h-2$. Also, $x_3\geq x_1 + 2f(x_1)
\geq h + 2f(h)$. Thus, $x_3\in A_3$, a contradiction.

\paragraph{Case 5.} $x_1\in A_2$, $x_2\in A_4$. Then $d\geq 4f(h) + h + 1 - x_1$,
and therefore $x_3 \geq 8f(h) + 2h + 2 - x_1$. Therefore, $x_1\geq c+1$. Hence,
\[ x_3\geq x_1 + 2f(x_1)\geq c + 1 + 2f(c+1) > 4f(h) + h + 1 + f(c+1) > 8f(h) + 2h + 2 - (c+1) = M, \]
a contradiction.

\paragraph{Case 6.} $x_1,x_2\in A_4$. Then
\[ x_3 \geq x_1 + 2f9x_1) \geq 2x_1 > M, \]
which is impossible.\end{proof}

As one example of the upper and lower bounds given by Theorems \ref{t7} and
\ref{t10}, for $m\geq 4$ an even integer, we have $16m^2 + 4m + 6 \leq w(mx,3,2)
\leq 16m^3 + 30m^2 + 18m - 3$ (the case for odd $m$ is slightly different).

We have also computed the exact values of $w(f,3,2)$ for some functions $f$.
We found the following: $w(x,3,2) = 24$, $w(x+1,3,2) = 46$, $w(x+2,3,2) = 67$,
$w(x+3,3,2) = 89$, $w(x+4,3,2) = 110$, $w(x+5,3,2) = 132$, $w(2x,3,2) = 77$,
and $w(2x + 1,3,2) = 114$. In all of these examples, the lower bound of
Theorem \ref{t10} agrees precisely with the computed value. We wonder if
the bound of Theorem \ref{t10} is the actual value of $w(f,3,2)$ for all
linear $f$. It is not true for general $f$, as we have found that $w(x^2,3,2)
\geq 115$, while the bound provided by Theorem \ref{t10} is 77.

For the case in which $f(x) = x + c$, we have the following fairly close
bounds on $w(f,3,2)$.

\begin{thrm}\label{t11} Let $c$ be a non-negative integer. Then
\[ 21.5c + 24 + \delta \leq w(x+c,3,2)\leq 23c + 24, \]
where $\delta=0$ if $c = 0$, and $\delta = 1/2$ if $c$ is odd.\end{thrm}
\begin{proof} The lower bound is an immediate consequence of Theorem \ref{t10}.

For the upper bound, let $g$ be any 2-coloring of $[1,23c+24]$. Let $g'$
be the coloring of $[1,24]$ defined by $g'(i) = g((c+1)(i-1)+1)$. Since
(as noted earlier) $w(x,3,2) = 24$, under $g'$ there must be a monochromatic
arithmetic progression $\{a,a+d,a+2d\}$ with $d\geq a$. Therefore $A = \{(c+1)(a-1)
+1, (c+1)(a + d - 1) + 1, (c+1)(a + 2d - 1)+1\}$ is an arithmetic progression
that is monochromatic under $g$ and has common difference that is no less than
$(c+1)a = (c+1)(a - 1) + 1 + c$. Thus, $A$ is a monochromatic $f$-arithmetic
progression where $f(x) = x + c$.
\end{proof}

\paragraph{Remark.} By the same method used in the proof of Theorem \ref{t11},
one can show that $w(bx + bc,3,2)\leq (w(bx,3,2) - 1)c + w(bx,3,2)$. Thus,
for example, since $w(2x,3,2) = 77$ we have $w(2x+2c,3,2)\leq 76c+77$.

Given the above results which pertain to arithmetic progressions of length
three, it may seem surprising that $w(f,4,2)$ does not exist for all $f$.
In fact we have the following stronger and more general result, which shows
that if $k>3$ or $r>2$, then there is a linear function $f$ such that
$w(f,k,r)$ does not exist.

\begin{thrm}\label{t12} Let $k\geq3$ and $r\geq2$. If $k>3$ or $r>2$, then
$w(cx,k,r)$ does not exist, where
\[ c = \left(\frac{2^{1/(r-1)} - 1}{k-1}\right). \]
\end{thrm}
\begin{proof} Assume $k > 3$ or $r > 2$. Let $v = 2^{1/(r-1)}$ and define
the coloring $g$, which uses the colors 0,1,\ldots,$r-1$ by: $g(x) = i$
(mod $r$) if $v^i \leq x < v^{i+1}$, for all $i\geq 0$.

Assume that $\{a,a+d,a+2d,\ldots,a+(k-1)d\}$ is monochromatic, and that $v^i
\leq a + d < v^{i+1}$. Then $d < v^{i+1}$, and $a + 2d < 2v^{i+1} = v^{i+r}$.
Since $g(a+2d) = g(a+d)$, this implies $v^i\leq a + d < a + 2d < v^{i+1}$.
Next, $a+3d = (a + 2d) + d < 2v^{i+1} = v^{i+r}$. Since $g(a+3d) = g(a+d)$,
this implies $v^i\leq a + d < a + 3d < v^{i+1}$. Similarly, $a+4d,\ldots,
a+(k-1)d$ are all less than $v^{i+1}$.

We now have $v^i \leq a + d < a + (k-1)d < v^{i+1}$, so that $d<(v^{i+1} - v^i)
/(k-2)$ and
\[ a \geq v^i - d > v^i\left(1 - \frac{v-1}{k-2}\right)\geq \frac{v^i}{2} = v^{i-(r-1)}. \]
Since $g(a) = g(a + d)$, it follows that $a > v^i$.

Finally, we have $v^i \leq a < a + (k-1)d < v^{i+1}$, so
\[ d < \frac1{k-1}(v^{i+1} - k^i) = cv^i \leq ca. \]
Hence $w(cx,k,r)$ does not exist.\end{proof}

For $k,r\geq 2$, let $A(k,r) = \{c > 0 : w(cx,k,r) \text{ exists} \}$. Then by Theorems
\ref{t6} and \ref{t7}, $A(2,r) = A(3,2) = (0,\infty)$. According to Theorem \ref{t12},
for all other choices of $k$ and $r$, $A(k,r)$ is bounded. The following result
shows that $A(k,r)$ is never empty.

\begin{thrm}\label{t13} For all $k$ and $r$, $w(x/(w(k,r) - k + 1), k, r) = w(k,r)$,
where $w(k,r)$ is the ordinary van der Waerden function.\end{thrm}
\begin{proof} If $\{ a,a+d,\ldots, a + (k-1)d\}$ is a monochromatic arithmetic
progression contained in $\intv{w(k,r)}$, then $a\leq w(k,r) - k + 1$, so $d\geq
1\geq a/(w(k,r) - k + 1)$.\end{proof}

By Theorems \ref{t12} and \ref{t13}, for all $k\geq 3$, $r\geq2$, such that either
$k>3$ or $r>2$, the set $A(k,r)$ is bounded and non-empty, and we define $\beta(k,r)
= \sup A(k,r)$. Clearly, $A(k,r) = (0,\beta(k,r))$ or $A(k,r) = (0,\beta(k,r)]$.

Theorem \ref{t12} shows that $\beta(k,2)\leq 1/(k-1)$ for all $k\geq4$. For $r=2$,
Theorem \ref{t12} is strengthened by the following result.

\begin{thrm}\label{t14} If $k\geq4$, then $w(x/(k^2 - 4k + 3),k,2)$ does not exist.
\end{thrm}
\begin{proof} Let $q = k^2 - 4k + 3$. Let $A_0 = [a_0,b_0] = [1,k-1]$, and for
$i\geq1$, let $A_i = [a_i,b_i]$, where
\begin{equation}\label{eq3}
a_i = b_{i-1} +1 \text{ and } b_i = b_{i-1} + (k-1)\ceil{\frac{b_{i-1} +1}q}.
\end{equation}

Now 2-color $\mathbb{Z}^+$ with the coloring $g$ defined by $g(A_i) = 1$ if $i$ is
even and $g(A_i) = 0$ if $i$ is odd. We shall show, by contradiction, that $g$ is
$(x/q,k)$-valid.

Assume $g$ is not $(x/q,k)$-valid. Then there is a monochromatic arithmetic progression
$X = \{x_1,\ldots,x_k\}$ with $d = x_j - x_{j-1}\geq x_1/q$ for $j = 2,\ldots,k$. Let
$m$ be the largest integer such that $X\cap A_m$ is not empty. Note that $X\not\subseteq
A_m$, since if $x_1\in A_m$, then
\begin{align*}
x_k = x_1 + (x-1)d
&\geq b_{m-1}+1+(k-1)\ceil{\frac{x_1}q} \\
&\geq b_{m-1}+1+(k-1)\ceil{\frac{b_{m-1}+1}q} \\
&> b_m.
\end{align*}

To complete the proof we shall obtain a contradiction by showing:
\begin{enumerate}
\item[(i)] at most two members of $X$ belong to $A_m$.
\item[(ii)] at most $k-3$ members of $X$ do not belong to $A_m$.
\end{enumerate}
Since not all of $X$ belongs to $A_m$, by the way $g$ and $m$ are defined we
know there is some $j>1$ such that $x_j\in A_m$ and $x_{j-1}\in A_i$, with
$h\leq m-2$. Hence
\begin{equation}\label{eq4}
d \geq |A_{m-1}| + 1 \geq (k-1)y + 1 \text{ where } y = \ceil{\frac{b_{m-2}+1}q}
\end{equation}

To obtain (i), we prove that $a_m + 2d > b_m$. To prove this, by \eqref{eq3}
and \eqref{eq4} it suffices to show that
\[ b_{m-1}+1+2((k-1)y + 1) > b_{m-1}+ (k-1)\ceil{\frac{b_{m-1}+1}q}, \]
that is, that
\[ 3 + 2(k-1)y > (k-1)\ceil{\frac{b_{m-2} + (k-1)y + 1}q}. \]
We see that this last inequality is true, since the right-hand side is less
than $(k-1)(y + (k-1)y/q)$.

To establish (ii), we shall show that $x_{j-1} - (k-3)d \leq 0$. By \eqref{eq4},
\begin{align*}
(k-3)d
&\geq (k-1)\left((k-1)\ceil{\frac{b_{m-2}+1}q}\right) \\
&\geq (\sqrt{q+1} - 1)(\sqrt{q+1} + 1)\frac{b_{m-2}}q \\
&= b_{m-2} \\
&\geq x_{j-1}.
\end{align*}
\end{proof}

We have computed $w(x/4,4,2) = 134$, so that $\beta(4,2)\geq 1/4$. Using this
fact, and the facts that $w(3,3) = 27$ and $w(3,4) = 76$, along with Theorems
\ref{t12}--\ref{t14}, we summarise what we know about $\beta(k,r)$ in the
following statement.

\begin{corl}\label{c15} Let $k\geq 3$. Then
\begin{enumerate}
\item[(i)] $1/4\leq \beta(4,2)\leq 1/3$
\item[(ii)] $1/25\leq \beta(3,3)\leq (\sqrt2 - 1)/2$
\item[(iii)] $1/74\leq\beta(3,4)\leq(\sqrt[3]{2} - 1)/2$
\item[(iv)] For $k\geq5$, $1/(w(k,2) - k + 1)\leq \beta(k,2)\leq 1/(k^2 - 4k + 3)$
\item[(v)] For $r>2$, $1/(w(k,r)-k+1)\leq \beta(k,r) \leq (2^{1/(r-1)}-1)/(k-1)$.
\end{enumerate}
\end{corl}

Since, by Theorem \ref{t12}, for each fixed $c\geq 3$, $w(x/3,k,2)$ does not
exist when $k\geq c + 1$, one wonders if there are any functions $f(k)$ such
that $f(x)\to\infty$ as $x\to\infty$ and $w(f,k,2)$ exists for all $k$. One
such function is given by the next theorem.

\begin{thrm}\label{t16} For each $r\geq2$, there is a function $f(x)$ such
that $f(x)\to\infty$ as $x\to\infty$ and $w(f,k,r)$ exists for all $k$.
\end{thrm}
\begin{proof} We construct such a function $f(x)$ for the case $r=2$. The case
of more colors can be handled in exactly the same way. Let $w(k,2)$ denote the
ordinary van der Waerden function for two colors. Let $B_2,B_3,\ldots,B_k,\ldots$,
be consecutive blocks of integers, where $B_2 = [1,6]$, $B_3 = [7,33]$, and,
in general, $|B_k| = kw(k,2)$. So $B_2$ has length $2\cdot3$, $B_3$ has length
$3\cdot9$, $B_4$ has length $4\cdot35$, et cetera. Define the function $f(x)$
by $f(x) = k$ when $x$ belongs to the block $B_k$. Then $f(x)$ goes to infinity.

Also, $w(f,k,2)\leq n = 2w(2,2) + 3w(3,2) + 4w(4,2) + \cdots + kw(k,2)$, for
if $[1,n]$ is 2-colored, then $B_k$ has been 2-colored. Since $|B_k| = kw(k,2)$,
$B_k$ contains $w(k,2)$ consecutive multiples of $k$. Hence there is a monochromatic
$k$-term arithmetic progression $\{a + id: 0 \leq i \leq (k-1)\}$ in $B_k$
consisting of multiples of $k$; hence $d\geq k = f(a)$.\end{proof}

\section{\label{s4} Concluding Remarks and Questions}

Analogs of van der Waerden's theorem, where other restrictions are placed on
the type of arithmetic progression which is allowed, have been considered in
earlier papers.

In \cite{beck1980,brown1981,justin1971}, it is shown that in order to guarantee
monochromatic arithmetic progressions $\{a,a+d,\ldots,a+(k-1)d\}$, one cannot
require $d$ or $a$ to be too small as a function of $k$.

In \cite{bergelson+liebman1996} it is shown that every 2-coloring of $\mathbb{Z}^+$
produces, for every $k$, a monochromatic $k$-term arithmetic progression where
one can require the common difference to be a perfect square, or to be a perfect
cube, or to have the form $g(z)$, where $g$ is any specified polynomial satisfying
some mild conditions (see also \cite{furstenberg1996}). For extensions of this,
see the excellent survey paper \cite{bergelson1996}.

In \cite{brown+graham+landman1999}, general properties of the set $A$ are studied,
where $A$ is any set of positive integers such that every $r$-coloring of
$\mathbb{Z}^+$ produces, for every $k$, a monochromatic $k$-term arithmetic
progression whose common difference is an element of $A$. The question of
determining the existence of the associated van der Warden-type function and
its value, for a given small finite set $A$, and given $k$, is considered in
\cite{landman1999-2}.

We conclude with some open questions.
\begin{enumerate}
\item By Proposition \ref{p1} and the coloring $\lambda(c,k,2)$, we know that
if $w(c_0,k,2) = 2c_0(k-1)^2+1$ and $j\in\mathbb{Z}^+$, then $w(jc_0,k,2) =
2jc_0(k-1)^2+1$. Based on what is true when $k = 3$ and on Table \ref{tab:t1},
we wonder if the following stronger statement holds: if $w(c_0,k,2) = 2c_0(k-1)^2
+ 1$ and $c\geq c_0$, then $w(c,k,2) = 2c(k-1)^2 + 1$.

\item Theorem \ref{t14} suggests questions such as: does $w(x/2^k,k,2)$ exist
for all large $k$? Is it true that for all large $k$, the fastest growing
function $f$ such that $w(f,k,2)$ grows like $x/k^2$?

\item It would be interesting to know the exact values, or have tighter bounds
than those of Corollary 15, for $\beta(4,2)$ and $\beta(3,3)$. We have found a
3-coloring of $[1,534]$ that is $(x/5,3)$-valid, so that $w(x/5,3,3)\geq 535$.
Since $w(3,3) = 27$ is so small in comparison, we suspect that $w(x/5,3,3)$
does not exist, which, if true, would give $1/25\leq \beta(3,3)\leq1/5$.

\item The function of Theorem \ref{t16} is apparently a very slowly growing function.
We wonder if there are any faster growing functions $f$, such that, for fixed $r$,
$w(f,k,r)$ exists for all $k$.

\item Another generalisation of a 3-term arithmetic progression is a set of
the form $\{x,ax + d, bx+2d$, where $x,a,b,d\in\mathbb{Z}^+$. For each pair
$a,b$, we can define $F(a,b)$ to be the least positive integer (if it exists)
such that for all 2-colorings of $\intv{f(a,b)}$ there is a monochromatic
set of this type. Notice that for any case in which $b = 2a-1$, the collection
of sets of this type is exactly the set of arithmetic progressions $\{x_1,x_2,
x_3\}$ with common difference at least $(a-1)x_1+1$. Thus, $F(a,2a-1) = w((a-1)x
+1,3,2)$, and hence by Theorems \ref{t7} (strong form) and Theorem \ref{t10}
we have upper and lower bounds for $F(a,2a-1)$. In particular, for $a$ even,
$16a^2 - 12a + 6\leq F(a,2a-1)\leq 16a^3-2a^2+4a-3$. We have calculated that
$F(2,3) = 46$ and $F(3,5) = 114$, coinciding with the lower bound. We would
like to know about $F(a,b)$ if $b\neq2a-1$ (it is very easy to show that
$F(a,2a)$ does not exist, but we do not know about other cases).
\end{enumerate}


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}

