%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-24/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}{Corollary}
\newtheorem{lmma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{conj}{Conjecture}
\theoremstyle{remark}
\newtheorem*{rmrk}{Remark}

\title{The Ramsey property for collections of sequences not containing all arithmetic progressions}
\author{
Tom C. Brown\footnote{Department of Mathematics and Statistics, ¶¡ÏãÔ°AV, Burnaby, British Columbia, V5A 1S6, Canada} and
Bruce M. Landman\footnote{Department of Mathematical Sciences, University of North Carolina at Greensboro, North Carolina 27412, USA}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown} and Bruce~M. Landman, \emph{The {Ramsey} property for collections
  of sequences not containing all arithmetic progressions}, Graphs and
  Combinatorics \textbf{12} (1996), 149--161.}\bigskip\end{center}


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

\newcommand{\A}{\ensuremath{\mathcal{A}}}
\newcommand{\B}{\ensuremath{\mathcal{B}}}

\begin{abstract}A family \B{} of sequences has the Ramsey property if for every positive
integer $k$, there exists a least positive integer $f_\B(k)$ such that for every
2-coloring of $\{1,2,\ldots,f_\B(k)\}$ there is a monochromatic $k$-term member
of \B. For fixed integers $m>1$ and $0\leq q<m$, let $\B_{q(m)}$ be the collection
of those increasing sequences of positive integers $\{x_1,\ldots,x_k\}$ such that
$x_{i+1}-x_i\equiv q\Mod{m}$ for $1\leq i\leq k - 1$. For $t$ a fixed positive
integer, denote by $\A_t$ the collection of these arithmetic progressions having
constant difference $t$. Landman and Long showed that for all $m\geq2$ and $1\leq
q<m$, $\B_{q(m)}$ does not have the Ramsey property, while $\B_{q(m)}\cup\A_m$
does. We extend these results to various finite unions of $\B_{q(m)}$'s and \A's.
We show that for all $m\geq2$, $\bigcup{q=1}{m-1}\B_{q(m)}$ does not have the
Ramsey property. We give necessary and sufficient conditions for collections of
the form $\B\cup \left(\bigcup_{t\in T}\A_t\right)$ to have the Ramsey property.
We determine when collections of the form $\B_{a(m_1)}\cup\B_{b(m_2)}$ have the
Ramsey property. We extend this to the study of arbitrary finite unions of
$\B_{q(m)}$'s. In all cases considered for which \B{} has the Ramsey property,
upper bounds are given for $f_\B$.
\end{abstract}

\section{Introduction \label{s1}}

One of the oldest and most well-known theorems of Ramsey theory is van der Waerden's
theorem, which says that for all $k$ and $r$, there is a least positive integer
$w(k,r)$ such that for every partition of $\{1,2,\ldots,w(k,r)\}$ into $r$ classes,
at least one of the classes contains an arithmetic progression of length $k$
\cite{vanderwaerden1927}. The estimation of $w(k,r)$ has been, and remains, one
of the more intriguing and difficult Ramsey theory problems. In particular, it
is still unknown whether $w(k,2)$ (usually denoted more simply by $w(k)$) is
bounded above by a tower of $k$'s having height $k$, while the best lower bounds
for $w(k)$ are of a much smaller order of magnitude (see \cite{graham+rothschild+spencer1990}
for a general discussion).

More generally, if \B{} represents any particular collection of sequences, we say
\B{} has the \emph{Ramsey property} if for every positive integer $k$, there exists
a least positive integer $f_\B(k)$ such that for every partition of $\{1,2,\ldots,
f_\B(k)\}$ into two classes, at least one of the classes will contain a $k$-term
member of \B. Clearly, whenever $\B\subseteq\mathcal{C}$ and \B{} has the Ramsey
property, we know that $\mathcal{C}$ has the Ramsey property and that $f_\mathcal{C}(k)
\leq f_\B(k)$ for all $k$. In particular, any collection $\mathcal{C}$ of sequences
that contains the arithmetic progressions has the Ramsey property; the corresponding
Ramsey functions $f_\mathcal{C}$ have been studied for a variety of such collections
$\mathcal{C}$ \cite{brown+erdos+freedman1990,greenwell+landman1989,landman1986,
landman1992,landman1993,landman1994,landman+greenwell1988,landman+greenwell1990-2,
landman+greenwell1990-1}.

For collections not containing the arithmetic progressions, the behavior of the
associated Ramsey functions can be somewhat unpredictable. Of course, if the
collection is too small, it will not have the Ramsey property. For example, if
$d$ is a fixed positive integer, let $\A_d$ consist only of those arithmetic
progressions for which the difference between consecutive terms is $d$. Then it
is a trivial matter to partition the positive integers into two classes so as
to avoid even 2-term members of $\A_d$, and hence $\A_d$ does not have the
Ramsey property. In fact, it is known that if $T$ is any finite set of positive
integers, then the family $\bigcup_{d\in T}\A_d$ does not have the Ramsey
property \cite{brown1981}. For fixed integers $m\geq2$ and $0\leq q<m$ define
a $q\Mod{m}$-\emph{sequence} to be an increasing sequence of positive integers
$\{x_1,\ldots,x_k\}$ such that $x_{i+1}-x_i\equiv q\Mod{m}$ for $1\leq i
\leq k-1$. It was shown in \cite{landman+long1994} that, for fixed $m$ and
$q$ with $q\neq 0$, the family of all $q\Mod{m}$-sequences, $\B_{q(m)}$,
does not have the Ramsey property (the associated Ramsey function $f_{q(m)}(k)$
is undefined for all $k > 2$). This is not surprising, if we think of a
$q\Mod{m}$-sequence as an arithmetic progression, modulo $m$, with constant difference
$q$. Less expectedly, it turns out \cite{landman+long1994} that for all $m$ and
$q$, the family $\B_{q(m)}\cup\A_m$ does have the Ramsey property, and its
associated Ramsey function, which we denote by $f_{q(m),m}(k)$, satisfies
\[ f_{q(m),m}(k) = mk^2(1 + o(1)). \]

In this paper we consider several situations that are more general than those
dealt with in \cite{landman+long1994}. If $S = \{a_i \Mod{m_i}):
1\leq i\leq n\}$ is any set of congruence classes, we consider the family
of sequences that are $a_i\Mod{m_i}$-sequences for some $i$. For example,
if
\[ S = \{ 1\Mod4, 2\Mod3)\}, \]
then the sequences $\{1,2,11\}$ and $\{1,9,11\}$ belong to the family, while
$\{1,2,4\}$ and $\{1,9,10\}$ do not. We ask: (i) For which choices of $S$ will
the family of sequences have the Ramsey property? (ii) For such $S$, what is
the rate of growth of the associated Ramsey function $f_S(k)$?

In particular, we look at the family of arithmetic progressions modulo $m$, i.e.,
$\bigcup_{q=1}^{m-1}\B_{q(m)}$. It is clear that for almost all choices of $k$,
$m$ and $q$, the number of $k$-term arithmetic progressions modulo $m$ is
considerably greater than the number of sequences belonging to $\B_{q(m)}\cup
\A_m$. Yet, in Section \ref{s2} we show that the arithmetic progressions
modulo $m$ do not have the Ramsey property. As a corollary, if $T$ is a set
of positive integers, we are able to characterize those families $\B_{q(m)}
\cup \left(\bigcup_{t\in T} \A_t\right)$ which have the Ramsey property,
and we give upper bounds for the associated Ramsey functions $f_{q(m),T}$,
which generalize known results about $f_{q(m),m}$ from \cite{landman+long1994}.

In Section \ref{s3}, we first consider $|S| = 2$, and characterize those $S$
that give rise to the Ramsey property. We also give an upper bound for the
associated Ramsey function. We then look at the function $f_S$ for general
$S$. We give sufficient conditions for $f_S(k)$ to be defined for all $k$,
and show that for a large variety of $S$'s, these conditions are also
necessary. In Section \ref{s4} we consider a special case involving
partitions into $r\geq2$ classes, and obtain an upper bound for the
associated Ramsey function, where $S$ consists of $r$ congruences. Section
\ref{s5} includes some observations, based on computer output, concerning
the sharpness of the bounds.

We make use of the following additional notation and terminology.

If $i<j$, the symbol $[i,j]$ denotes the set $\{i,i+1,\ldots,j\}$.

A ($k$-term) \emph{arithmetic progression} (or simply \emph{a.p.}) is a
sequence $\{a+id:i=0,1,\ldots,k-1\}$ where $a,d>0$. For a fixed $t>0$, an
a.p. is called a \emph{$t$-a.p.} if $d=t$. If $m\geq2$ and $0\leq q<m$,
we call an increasing sequence $X = \{x_1,\ldots,x_k\}$ a \emph{$k$-term
$q\Mod{m}$-sequence} if $x_{i+1}-x_i\equiv q\Mod{m}$ for $1\leq i\leq k-1$.
If we drop the requirement that the sequence be increasing, we will call
it a \emph{semi-$q\Mod{m}$-sequence}. For example $\{1,2,18,4,15,1\}$ is
a 6-term semi $1\Mod5$-sequence, but it is not a $1\Mod5$-sequence.

An \emph{$r$-coloring} of a set $A$ of positive integers is a function
$\chi:A\to\{1,2,\ldots,r\}$ (i.e., it is a partition of $A$ into $r$
classes). A coloring $\chi$ is \emph{monochromatic} on a set $Y$ if
$\chi$ is constant on $Y$. Since most of this paper deal with 2-colorings,
we sometimes use the word \emph{coloring} to indicate a 2-coloring.

Let $S = \{a_i\Mod{m_i}$: $1\leq i\leq n\}$ be a set of congruence
classes where $1\leq a_i< m_i$ for all $i$, and let $T$ be a set of
positive integers. The symbol $f_{S,T}(k)$ will denote the least positive
integer such that whenever $[1,f_{S,T}(k)]$ is 2-colored, there will be
a $k$-term monochromatic $a_i\Mod{m_i}$-sequence for some $i\in\{1,
\ldots,n\}$ or a $k$-term monochromatic $t$-a.p., for some $t\in T$.
If $f_{S,T}(k)$ does not exist, we write $f_{S,T}(k) = \infty$. If
$S$ consists of a single congruence class $q\Mod{m}$, we denote
$f_{S,T}$ by $f_{q(m),T}$; if, in addition, $T = \{t\}$, we use
$f_{q(m),t}$. If $T = \phi$, we use the symbol $f_S$ rather than $f_{S,T}$;
or in case $|S| = 1$ or 2, simply $f_{a(m_1)}$ or $f_{a(m_1),b(m_2)}$,
respectively.

As a more general notation, we use $f_{q(m),T}(k_1,k_2)$ to denote
the Ramsey function corresponding to $k_1$-term $q\Mod{m}$-sequences
or $k_2$-term $t$-a.p.'s for some $t\in T$. If $\vec{k} = (k_1,k_2,\ldots,k_n)$,
$f_S(\vec{k})$ represents the least positive integer so that every 2-coloring
of $[1,f_S(\vec{k})]$ will contain a monochromatic $k_i$-term $a_i\Mod{m}$-sequence
for some $a_i\Mod{m_i}\in S$.

Finally, when considering a Ramsey function associated with $r$-colorings
we use the symbol $f^{(r)}$ in place of $f$.

\section{Using a Single Modulus \label{s2}}

In \cite{landman+long1994} it was shown that when $q\neq 0$ the Ramsey
number $f_{q(m)}(k)$ corresponding to $q\Mod{m}$-sequences is infinite
for all $k\geq3$, while $f_{q(m),m}$, the Ramsey function corresponding
to $q\Mod{m}$-sequences or $m$-a.p.'s, is always finite. More specifically,
the following upper bounds for $f_{q(m),m}$ were obtained.

\begin{thrm}[Landman and Long]\label{t1} Let $m\geq2$, $1\leq q< m$, and
$k,n\geq2$. Let $e = \gcd(q,m)$. If $m/e$ is even, then
\begin{equation} f_{q(m),m}(k,n) \leq m(k-1)(n-1) + (k-2)q + 1 \label{eq1}\end{equation}
If $m/e$ is odd, then
\begin{equation} f_{q(m),m}(k,n) \leq m[(k-2)(n-1)+1] + kq - e + 1\label{eq2}\end{equation}
\end{thrm}

Theorem \ref{t1} deals with the case in which for some fixed $m$ and $q$,
$S = \{q\Mod{m}\}$ and $T = \{m\}$. We now consider the case in which
$S = \{a\Mod{m}:1\leq a\leq m-1\}$ and $T = \phi$, i.e., the case of
the a.p.'s modulo $m$. As the next theorem shows, the size of the collection
of sequences does not, in itself, tell us whether the corresponding Ramsey
function is defined.

\begin{thrm} Let $m\geq2$ and $S = \{a\Mod{m}:1\leq a\leq m-1\}$. Then
$f_S(k) = \infty$ whenever $k>\ceil{m/2}$.\label{t2}\end{thrm}
\begin{proof} Let $m\geq2$ and consider the following 2-coloring, $\chi$,
of the positive integers. For $1\leq x\leq \ceil{m/2}$ let $\chi(x)=0$,
and for $\ceil{m/2} + 1\leq x\leq m$ let $\chi(x) = 1$. When $x>m$, let
$\chi(x) = \chi(\bar{x})$, where $x\equiv\bar{x}\Mod{m}$ and $1\leq\bar{x}
\leq m$.

We will show that, with respect to $\chi$, the maximum size of a monochromatic
$q\Mod{m}$-sequence is bounded above by $\ceil{\frac{m}{2\gcd(q,m)}}\leq\ceil{
\frac{m}2}$ for each $q$, $1\leq q\leq m-1$. From this it follows immediately
that $f_S(k)=\infty$ if $k>\ceil{\frac{m}2}$.

Let $q$ be fixed ($1\leq q \leq m-1$), and let $d = \gcd(q,m)$, $s=m/d$. Now
regard $1,2,\ldots,m$ as the elements of the $m$-element cyclic group (where
$\bar{x} + \bar{y} = \overline{x+y}$), and let $H$ be the $s$-element cyclic
subgroup of $[1,m]$. By elementary group theory, we know that
\begin{equation}
H = \{\overline{q},\overline{2q},\ldots,\overline{sq}\} = \{d,2d,\ldots,sd\}.
\label{eq3}\end{equation}

Now let $x_1<x_2<\cdots<x_s$ be any $s$-term $q\Mod{m}$-sequence. Then $x_{i+1}
= x_i+d_i$ for $1\leq i\leq s-1$, with $d_i\equiv q\Mod{m}$, so that
\[ \{ \overline{x_1},\ldots,\overline{x_s}\} = \{\overline{x_1},\overline{x_1+q},
\ldots, \overline{x_1 + (s-1)q}\} = \overline{x_1}+H. \]

From \eqref{eq3} we see that the subset $\overline{x_1}+H$ of $[1,m]$ forms an
arithmetic progression with $s = m/d$ terms and common difference $d$. Exactly
$\floor{\frac{s}2}$ of these terms will be less than or equal to $m/2$, and
hence exactly $\ceil{\frac{s}2}$ terms will form a monochromatic set with
respect to $\chi$. Since $\chi(x_i) = \chi(\overline{x_i})$, this shows that
if $x_1<\cdots<x_t$ is a monochromatic $q\Mod{m}$-sequence, then $t\leq\ceil{\frac{s}2}$, as required. [Note:
one can also show that if $1\leq q\leq m/2$, the maximum size of a monochromatic
$q\Mod{m}$-sequence, with respect to this same coloring, is exactly $\ceil{\frac{m}{2q}}$.
We omit the details.]\end{proof}

As a consequence of Theorems \ref{t1} and \ref{t2}, we are able to characterize,
for given $q$ and $m$, those sets $T$ such that $f_{q(m),T}(k)$ exists for all
$k$. We also generalize the bounds of Theorem \ref{t1}, which deals with the
case of $T =\{m\}$, to any set $T$ containing some multiple of $m$.

\begin{corl}\label{c1} Let $m\geq2$, $1\leq q\leq m-1$, and let $T$ be a
set of positive integers.
\begin{enumerate}
\item[(a)] $f_{q(m),T}(k)<\infty$ for all $k$ if and only if $cm\in T$ for some
positive integer $c$.
\item[(b)] Let $d=\gcd(q,m)$, $k$, $n\geq2$, and $c\geq1$. Assume that $cm\in T$.

If $m/d$ is even, then
\begin{equation} f_{q(m),T}(k,n)\leq cm(k-1)(n-1) + (k-2)q + 1. \label{eq4}\end{equation}
If $m/d$ is odd, then
\begin{equation} f_{q(m),T}(k,n)\leq cm(k-2)(n-1) + m + kq - d + 1. \label{eq5}\end{equation}
\end{enumerate}\end{corl}
\begin{proof} Assume no multiple of $m$ belongs to $T$. Then for each $t\in T$,
every $t$-a.p. is an $a\Mod{m}$-sequence for some $a\in\{1,\ldots,m-1\}$. It
then follows from Theorem \ref{t2} that $f_{q(m),T}(k)=\infty$ for all $k>m/2$.

Now assume $cm\in T$. Note that if $\{x_1,\ldots,x_{(n-1)c+1}\}$ is an $m$-a.p.,
then $\{ x_{ic+1}:i=0,\ldots,n-1\}$ is a $cm$-a.p. Hence,
\[ f_{q(m),cm}(k,n) \leq f_{q(m),m}(k,(n-1)c+1). \]
Inequalities \eqref{eq4} and \eqref{eq5} follow from \eqref{eq1} and \eqref{eq2},
respectively.\end{proof}

\section{Using an Arbitrary Set of Congruence Classes\label{s3}}

We now direct our attention to the function $f_S$ for general $S$. The case
in which $|S|=1$ was considered in \cite{landman+long1994}. The authors showed
that if $S$ consists of the single congruence class $a\Mod{m}$, then as long
as $a\neq0$ and $k\geq3$, $f_S(k)=\infty$. They also showed that the only
case in which $|S|=1$ and $f_S(3)<\infty$ is if $q=0$, and that in fact,
for all $k\geq2$
\begin{equation} f_{0(m)}(k) = 2m(k-1)+1. \label{eq6}\end{equation}

We also see by Theorem \ref{t2}, that if $S = \{a_1\Mod{m},\ldots,a_r\Mod{m}:
a_i\neq0 \text{ for } 1\leq i\leq r\}$, then $f_S(k)=\infty$ whenever $k>m/2$.

Before dealing with the most general set $S$, we first consider the case in
which $|S|=2$. We now characterize those sets $S = \{a\Mod{m_1},b\Mod{m_2}:
a,b\neq0\}$ for which the corresponding collection of sequences has the
Ramsey property (if $a=0$ or $b=0$ we see by \eqref{eq6} that $f_S(k)$ does
exist for all $k$), and provide an upper bound for the corresponding Ramsey
function.

\begin{thrm}\label{t3}Let $m_1,m_2>1$, let $1\leq a<m_1$ and $1\leq b<m_2$,
and assume $k>3$. Let $d=\gcd(m_1,m_2)$ and $m=\lcm\{m_1,m_2\}$. Then
$f_{a(m_1),b(m_2)}(k)<\infty$ if and only if $d|a$ or $d|b$. Furthermore,
for all $k\geq3$, if $d|a$ or $d|b$, then $f_{a(m_1),b(m_2)}(k)<m(k-1)^2$.
\end{thrm}
\begin{proof} First assume $d$ divides neither $a$ nor $b$. To prove
$f_{a(m_1),b(m_2)}(k)$ does not exist, it suffices to prove $f_{a(d),b(d)}(k)$
does not exist because any coloring of the positive integers that avoids
monochromatic $q\Mod{d}$-sequences also avoids monochromatic $q\Mod{m_1}$-
and $q\Mod{m_2}$-sequences. Note also that if $\chi$ is a 2-coloring of
$[1,d]$ that avoids monochromatic semi $q\Mod{d}$-sequences, then the coloring
$\chi'$ of the set of positive integers defined by
\[ \chi'(j) = \chi(i) \text{ if } j\equiv i\Mod{d} \]
will avoid $k$-term monochromatic $q\Mod{d}$-sequences. Thus, to prove
$f_{a(m_1),b(m_2)}(k)$ does not exist it suffices to find a 2-coloring of
$[1,d]$ that avoids $k$-term monochromatic semi $a\Mod{d}$-sequences and
$k$-term monochromatic semi $b\Mod{d}$-sequences. Finally, we can assume
$a\leq d/2$ and $b\leq d/2$, because if $q>d/2$, then $S = \{x_1,\ldots,
x_k\}$ is a semi $q\Mod{d}$-sequence in $[1,d]$ if and only if $S=\{x_k,
\ldots,x_1\}$ is a semi $(d-q)\Mod{d}$-sequence.

We now give a coloring of $[1,d]$ that avoids both 4-term monochromatic
semi $a\Mod{d}$-sequences and 4-term monochromatic semi $b\Mod{d}$-sequences.
Assuming $a<b$ (we may assume $a\neq b$, since, as stated in the introduction,
there is a 2-coloring of the positive integers that avoids monochromatic
$a\Mod{d}$-sequences), define the coloring $\chi$ recursively:
\begin{enumerate}
\item[(i)] $\chi(x) = 1$ if $1\leq x\leq a$
\item[(ii)] $\chi(x) \neq \chi(x-a)$ if $a< x\leq b$
\item[(iii)] $\chi(x)\neq \chi(x-b)$ if $b<x\leq d$.
\end{enumerate}
It is apparent that there is no monochromatic 3-term semi $b\Mod{d}$-sequence
in $[1,d]$. To show there is no monochromatic 4-term semi $a\Mod{d}$-sequence,
we consider two cases.

\paragraph{Case I.} $a\leq b/2$.

\noindent Let $B_i=[ib+1,(i+1)b]$ for $i=0,\ldots,j-1$ where $j=\floor{d/b}$,
and let $B_j = [jb+1,d]$ ($B_j$ is empty if $b$ divides $d$). Assume $x_1,
\ldots,x_4$ is a semi $a\Mod{d}$-sequence. Then $x_3-x_1\equiv e\Mod{d}$
and $x_4-x_2\equiv f\Mod{d}$ where $0\leq e$, $f\leq b$. Since $a\leq b/2$,
some pair $x_r$, $x_{r+1}$ must be in the same block $B_i$ (for otherwise
$x_4-x_2>b$ or $x_3-x_1>b$). Thus, by definition of $\chi$, $\chi(x_r)
\neq \chi(x_{r+1})$.

\paragraph{Case II.} $a>b/2$.

\noindent Let $A_0 = [1,a]$, let $A_i = [(i-1)b+a+1,ib+a]$ for $i=1,\ldots,
h$ where $h=\floor{(d-a)/b}$, and let $A_{h+1} = [hb+1,d]$ ($A_{h+1}$
could be empty). Then each $A_i$ is monochromatic and the $A_i$'s alternate
in color. Assume $\{x,y,z\}$ is a monochromatic semi $a\Mod{d}$-sequence.
If $x$ and $y$ are in different $A_i$'s, then $y$ must be in $A_0$; but
then $\chi(z)\neq\chi(y)$. Therefore, we assume $x$ and $y$ are in the
same $A_{i_1}$. So $z\notin A_{i_1}$. Thus, $z\in A_0$, and hence $\chi(z+a)
\neq\chi(z)$. Thus there is no 4-term semi $a\Mod{d}$-sequence that is
monochromatic.

Now assume $d$ divides (say) $a$. We first consider the case in which
$\frac{m_2}{\gcd(m_2,b)}$ is even. Now $a\neq0$ implies $m_1\neq d$, so
that there exists a positive integer $c<m_1/d$ such that
\begin{equation} cm_2\equiv a\Mod{m_1} \label{eq7}\end{equation}
By \eqref{eq4}, every 2-coloring of $[1,cm_2(k-1)^2+b(k-2)+1]$ contains
either a monochromatic $k$-term a.p. with difference $cm_2$ or a
monochromatic $k$-term $b\Mod{m_2}$-sequence. Since
\begin{align*}
cm_2(k-1)^2+b(k-2)+1
&\leq \left(\frac{m_1}d-1\right)m_2(k-1)^2 + (m_2-1)(k-2)+1 \\
&< m(k-1)^2,
\end{align*}
the result follows from \eqref{eq7}. The case in which $\frac{m_2}{\gcd(m_2,b)}$
is odd is easily done in the same way, using \eqref{eq5} instead of \eqref{eq4}.
\end{proof}

\begin{rmrk} Since the coloring $\chi$ of $[1,d]$ in the proof of Theorem
\ref{t3} avoided both 4-term semi $a\Mod{d}$-sequences and 3-term semi
$b\Mod{d}$-sequences, we have actually shown the slightly stronger result
that if $a\equiv a'\Mod{d}$ and $b\equiv b'\Mod{d}$ with $1\leq a'\leq
b'\leq d- 1$, then $f_{a(m_1),b(m_2)}(4,3)=\infty$.\end{rmrk}

We now direct our attention to the more general case in which $|S|=n$. The
following sufficient condition for $f_S$ to exist, and the corresponding
upper bound, are immediate from Theorem \ref{t3}.

\begin{thrm}\label{t4} Let $S = \{a_i\Mod{m_i}:1\leq i\leq n\}$ with $1\leq
a_i <m_i$ for each $i$. For $1\leq i<j\leq n$, let $d_{ij}=\gcd(m_i,m_j)$
and $m_{ij} = \lcm\{m_i,m_j\}$. If for some pair $i< j$, $d_{ij}$ divides
$a_i$ or $a_j$, then
\begin{equation} f_S(k) < m_{ij}(k-1)^2\text{ for all } k\geq 3 \label{eq8}\end{equation}
\end{thrm}

We now wish to consider the converse of Theorem \ref{t4}. In other words, if
$S$ and $d_{ij}$ are defined as in Theorem \ref{t4}, and if $f_S$ is finite
for all $k$, does it follow that for some $i\neq j$, $d_{ij}$ divides $a_i$
or $a_j$?

Before proceeding, we give some results which simplify the determination of
whether, given $S$, the corresponding collection of sequences has the Ramsey
property.

\begin{lmma}\label{l1} Let $S = \{a_i\Mod{m_i}:1\leq i\leq n\}$. Let $m=
\lcm\{m_1,\ldots,m_n\}$ and $\vec{k}=(k_1,\ldots,k_n)$. Then $f_S(\vec{k})
= \infty$ if and only if there is an $m$-periodic coloring of the
positive integers that avoids monochromatic $k_i$-term $a_i\Mod{m_i}$-sequences
for all $i$.\end{lmma}
\begin{proof} Clearly, if $f_S(\vec{k})<\infty$, no $m$-periodic coloring
can avoid monochromatic $k_i$-term $a_i\Mod{m_i}$-sequences for all $i$.

Now assume $f_S(\vec{k})=\infty$. Let $C$ be a coloring of the positive integers
that avoids monochromatic $k_i$-term $a_i\Mod{m_i}$-sequences for all $i$. Denote
$C$ by a sequence of 0's and 1's. For each positive integer $j$, let $C_j$
represent that portion of the sequence $C$ that is restricted to the interval
$[(j-1)m+1,jm]$. There are $2^m$ possible colorings for each $C_j$. So at least
one of these $2^m$ colorings must occur infinitely often in $C=C_1C_2\ldots$.
Say that $B = C_{j_1} = C_{j_2} = \cdots$, where $j_1<j_2<\cdots$. Now color
the positive integers with the coloring $BBB\ldots$, and denote the coloring
by $D$.

To complete the proof we will show that the $m$-periodic coloring $D$ avoids
$k_i$-term monochromatic $a_i\Mod{m_i}$-sequences for all $i$. Assume by way
of contradiction that under $D$ the sequence $x_1,\ldots,x_{k_i}$ is a
monochromatic $a_i\Mod{m_i}$-sequence. For each $s$, $1\leq s\leq k_i$, let
$y_s$ be an element of $C_{j_s}$ such that $y_s\equiv x_s\Mod{m}$. Then the
$C$-color of $y_s$ is the same as the $D$-color of $x_s$ for each $s$. Thus,
under $C$, $y_1,\ldots,y_{k_i}$ is a $k_i$-term monochromatic $a_i\Mod{m_i}$-sequence,
a contradiction.\end{proof}

\begin{lmma}\label{l2} Let $S = \{a_i\Mod{m_1}:1\leq i<m\}$. Let $m=\lcm\{m_1,
\ldots,m_n\}$ and $\vec{k}=(k_1,\ldots,k_n)$. Then $f_S(\vec{k})<\infty$ if
and only if every 2-coloring of $[1,m]$ contains, for some $i$, a monochromatic
$k_i$-term semi $a_i\Mod{m_i}$-sequence.\end{lmma}
\begin{proof}Assume that for every 2-coloring of $[1,m]$, there is a monochromatic
$k_i$-term semi $a_i\Mod{m_i}$-sequence for some $i$. Let $\chi$ be an $m$-periodic
coloring of the positive integers. Then, under $\chi$, there is, for some $i$,
a monochromatic semi $a_i\Mod{m_i}$-sequence $x_1,\ldots,x_{k_i}$ that is
contained in $[1,m]$. For $1\leq j\leq k_i$, let $y_j\equiv x_j\Mod{m}$ with
$y_j\in [(j-1)m+1,jm]$. Then, since $\chi$ is $m$-periodic, $y_1,\ldots,y_{k_i}$
is a (increasing) monochromatic $a_i\Mod{m_i}$-sequence that is contained in
$[1,mk_i]$. Since $\chi$ is an arbitrary $m$-periodic coloring, by Lemma \ref{l1}
we know that $f_S(k)<\infty$.

Now assume there is a 2-coloring of $[1,m]$ that avoids monochromatic $k_i$-term
semi $a_i\Mod{m_i}$-sequences. Extend this coloring to an $m$-periodic 2-coloring
of the positive integers. Relative to this extended coloring, there is no
monochromatic $k_i$-term $a_i\Mod{m_i}$-sequence. Hence $f_S(\vec{k})=\infty$.
\end{proof}

The following result tells us that to determine whether the collection of sequences
corresponding to a given $S$ has the Ramsey property, it suffices to check whether
the associated Ramsey function is defined at one particular vector $\vec{k}^*$.

\begin{prop}Let $S=\{a_i\Mod{m_i}:1\leq i\leq n\}$ and $\vec{k}^*=(k_1^*,\ldots,
k_n^*)$ where $k_i^* = \frac{m_i}{\gcd(a_i,m_i)}$ for $1\leq i\leq n$. Then
$f_S(k)<\infty$ for all $k$ if and only if $f_S(\vec{k}^*)<\infty$.\label{p1}
\end{prop}
\begin{proof} One direction is trivial. For the other direction, we proceed by
contradiction. Suppose $f_S(k)=\infty$ but that $f_S(\vec{k}^*)<\infty$. Let
$m=\lcm\{m_1,\ldots,m_n\}$. By Lemma \ref{l1}, let $C$ be an $m$-periodic coloring
of the positive integers which avoids $k$-term monochromatic $a_i\Mod{m_i}$-sequences
for all $i$.

By the proof of Lemma \ref{l2}, under the coloring $C$ there exists, for some $i$,
a monochromatic $k_i^*$-term $a_i\Mod{m_i}$-sequence contained in $[1,mk_i^*]$.
Denote this sequence by $x_1,\ldots,x_{k_i^*}$. Note that for each positive integer
$r$,
\[ rmk_i^* + x_i - [(r-1)mk_i^* + x_{k_i^*}] \equiv -a_i(k_i^*-1)\Mod{m}. \]
Therefore,
\[ rmk_i^* + x_1 - [(r-1)mk_i^* + x_{k_i^*}] \equiv a_i\Mod{m_i}e \]
Since $C$ has period $m$, the sequence
\begin{align*}
&x_1,x_2,\ldots,x_{k_i^*}, mk_i^*+x_1, mk_i^*x_2,\ldots, mk_i^* + x_{k_i^*}, 2mk_i^*+x_1, \\
&2mk_i^*+x_2,\ldots,2mk_i^*+x_{k_i^*},\ldots
\end{align*}
is an infinite monochromatic $a_i\Mod{m_i}$-sequence, contradicting the assumption
that under $C$ there is no monochromatic $k$-term $a_i\Mod{m_i}$-sequence.\end{proof}

Theorem \ref{t3} tells us that, for the case in which $|S| = 2$, the converse
of Theorem \ref{t4} holds. That is, if $d$ divides neither $a_1$ nor $a_2$
then $f_S(k)=\infty$ for $k$ large enough. This converse of Theorem \ref{t4}
does not, however, hold in the general case of $|S|=n$. In Proposition \ref{p2}
we exhibit a special class of sets $S$ for which, for all $i$ and $j$, $\gcd(m_i,m_j)$
divides neither $a_i$ nor $a_j$, yet $f_S(k)$ is always finite.

\begin{prop}\label{p2} Let $S = \{a_i\Mod{m_i}:i=1,2,3\}$ where for all $i\neq j$,
$\gcd(m_i,m_j)$ divides neither $a_i$ nor $a_j$. Assume $a_1=m_1/2$, and that
$a_1,a_2$ are odd, and $a_3$ is even. Assume $m_2=2b$ such that $b$ is odd and
$\gcd(a_1,b)=1$. Assume $m_3$ is a divisor of $\frac12m_1m_2 = \lcm\{m_1,m_2\}$.
Then $f_S(\vec{k})<\infty$ for all $\vec{k}$.\end{prop}
\begin{proof}Let $k_1^* = 2$, $k_2^* = \frac{m_2}{\gcd(a_2,m_2)}$, and $k_3^*
= \frac{m_3}{\gcd(a_3,m_3)}$. Let $m=\frac12m_1m_2$. By Proposition \ref{p1}
and Lemma \ref{l2}, it suffices to show that every 2-coloring of $[1,m]$
contains, for some $i$, a $k_i^*$-term monochromatic semi $a_i\Mod{m_i}$-sequence.
Suppose that $\chi$ is a 2-coloring of $[1,m]$ with no 2-term monochromatic
semi $\frac{m_1}2\Mod{m_1}$-sequence and not $k_2^*$-term monochromatic semi
$a_2\Mod{m_2}$-sequence.

Let $S_0=\{m_1,2m_1,\ldots,(m/m_1)m_1\}$ and, for $1\leq j\leq m_1-1$, let
$S_j = j + S_0\Mod{m}$. Since there are no 2-term monochromatic semi
$\frac{m_1}2\Mod{m_1}$-sequences, no member of $S_j$ could have the same
color as a member of $S_{j+m_1/2}$, for all $j$. So each $S_j$ is monochromatic.

Our strategy is to show that one color class consists of even elements of $[1,m]$,
while the other color class consists of the odd elements of $[1,m]$. Since
$a_3$ is even, it will then follow that $m_3,m_3+a_3,\ldots,m_3+(k_3^*-1)a_3$
is a monochromatic $k_3^*$-term semi $a_3\Mod{m_3}$-sequence. In view of
Proposition \ref{p1}, this will complete the proof.

Let $T_0=\{m_2,2m_2,\ldots,(m/m_2)m_2\}$ and, for $1\leq j\leq m_2-1$, let
$T_j = j+T_0\Mod{m}$. Let $0\leq j\leq m_1-2$, and assume $x,y\in S_j\cup
S_{j+1}$, with $x\neq y$. In case $x,y\in S_j$ or $x,y\in S_{j+1}$, then
$x\equiv y\Mod{m_1}$. Then $x\not\equiv y\Mod{m_2}$ for otherwise $x\equiv
y\Mod{m}$. If $x\in S_j$ and $y\in S_{j+1}$ then $x$ and $y$ have opposite
parity (since $m_1$ is even), so that $x\not\equiv y\Mod{m_2}$ (since $m_2$
is even). Hence, in all cases, no two elements of $S_j\cup S_{j+1}$ are
congruent $\Mod{m_2}$. It then follows, since $S_j\cup S_{j+1}$ has $2(m/m_1)
= m_2$ elements, and since all elements of any $T_h$ are congruent $\Mod{m_2}$,
that
\begin{equation} (S_j\cup S_{j+1})\cap T_h\neq\varnothing\label{eq9}\end{equation}
for all $0\leq j\leq m_1-2$ and all $0\leq h\leq m_2-1$. It follows from
\eqref{eq9} that, for each $1\leq j\leq m_1-2$, $S_j\cup S_{j+1}$ contains a
semi $a_2\Mod{m_2}$-sequence with $m_2/\gcd(a_2,m_2)$ terms. Since no such
sequence can be monochromatic, and since each $S_j$ is monochromatic, $S_j$
and $S_{j+1}$ have opposite colors. Thus, since $m_1$ is even, one color
class consists of the even elements of $[1,m]$ and the other class consists
of the odd elements of $[1,m]$, as claimed.\end{proof}

Specific examples of sets $S$ which satisfy the hypotheses of Proposition
\ref{p2} include the following: $S= \{a\Mod{2a}, b\Mod{2bc}, 2c\Mod{2abc}\}$
where $a,b$ and $c$ are odd, $a>1$, $b>1$ and $\gcd(a,bc) = 1$.

Proposition \ref{p2} gives a very special class of sets $S$ for which the
converse of Theorem \ref{t4} fails. The next theorem gives sufficient
conditions on $S$ for $f_S(\vec{k})$ to be infinite for some $\vec{k}$,
which are satisfied by a large class of sets $S$. Note, in particular,
that Theorem \ref{t5} implies that the converse of Theorem \ref{t4}
does hold if $\gcd(a_i,m_i) = 1$ for all $i$.

\begin{thrm}\label{t5} Let $S=\{a_i\Mod{m_i}:1\leq i\leq n\}$. Let $e_i
=\gcd(a_i,m_i)$ for $1\leq i\leq n$, and $d_{ij}=\gcd\left(\frac{m_i}{e_i},
\frac{m_j}{e_j}\right)$ for $i\neq j$. Assume that for every pair $i\neq j$,
$d_{ij}$ divides neither $a_i$ nor $a_j$. Then $f_S(\vec{k}^*) = \infty$ where
$\vec{k}^* = (m_1/e_1,\ldots,m_n/e_n)$.\end{thrm}
\begin{proof} We first prove the result for the case in which $e_1=1$ for
all $i$. Let $m=\lcm\{m_1,\ldots,m_n\}$. By Lemma \ref{l2}, it suffices to
find a 2-coloring of $[1,m]$ that avoids $m_i$-term monochromatic semi
$a_i\Mod{m_i}$-sequences for all $i$.

Define the coloring $\chi:[1,m]\to\{0,1\}$ as follows:
\[ \chi(x) = \left\{\begin{array}{ll}
1&\text{if }x\equiv0\Mod{m_i}\text{ for some }i\\
0&\text{if }x\equiv{a_i}\Mod{m_i}\text{ for some }i\\
\text{arbitrary}&\text{otherwise}\end{array}\right. \]
Note that $\chi$ is well-defined on $[1,m]$ because if $i\neq j$ and $x\equiv0
\Mod{m_i}$, then (since $d_{ij}$ does not divide $a_j$) $x\not\equiv a_j\Mod{m_j}$.
Since $e_1=1$ for all $i$, any $m_i$-term semi $a_i\Mod{m_i}$-sequence
must contain an element from each congruence class modulo $m_i$. Hence,
no such sequence can be monochromatic under $\chi$. This proves the
theorem in case all $e_i=1$.

Now let the $e_i$ be arbitrary. Consider
\[ S' = \{a_i\Mod{m_i/e_i}:1\leq i\leq n\}. \]
Since $\gcd\left(a_i,\frac{m_i}{e_i}\right)=1$ and since $\gcd\left(\frac{a_i}{m_i},
\frac{a_j}{m_j}\right)$ divides neither $a_i$ nor $a_j$, we can apply the
case proven above (the case of all $e_i = 1$). Thus, there is a coloring
of the positive integers that avoids, for all $i$, $(m_i/e_i)$-term
monochromatic $a_i\Mod{m_i/e_i}$-sequences. Observing that every $a_i\Mod{m_i}$-sequence
is also an $a_i\Mod{m_i/e_i}$-sequence, the proof is complete.\end{proof}

\section{A Special Case\label{s4}}

Theorem \ref{t3} gives an upper bound, using 2 colors, for $f_{a(m_1),b(m_2)}(k)$,
when $d=\gcd(m_1,m_2)$ divides $a$ or $b$. If we use the stronger hypothesis that
$d$ divides both $a$ and $b$, we are able to give a much better upper bound.
In fact, we shall prove a result which deals with the more general case in
which there are $r$ colors and $|S| = r$. We first prove the following theorem.

\begin{thrm}\label{t6}Let $r\geq2$ and, for $1\leq i\leq r$, let $m_i>1$ and
$1\leq a_i<m_i$. Let $a_0 = \min\{a_i\}$, $d=\gcd(m_1,\ldots,m_r)$, and
$m=\lcm\{m_1,\ldots,m_r\}$. Assume that $d$ divides $a_i$ for all $i$ and
that the $m_i/d$ are pairwise relatively prime. Then, for each $t\geq 2$, every
$r$-coloring $\chi$ of $[1,m(t-2)+a_0+1]$ contains, for $1\leq i\leq r$, a
monochromatic $k_i$-term $a_i\Mod{m_i}$-sequence $X_i$, with
\[ \chi(X_i)\neq \chi(X_j) \text{ for }i\neq j\text{ and} \]
\[ \sum_{i=1}r k_i = t \text{ with } k_i\geq 0. \]
\end{thrm}
\begin{proof} We first prove the theorem for the case in which $d =1$,
using induction on $t$.

If $t=2$ then since $\{1,a_0+1\}$ is a 2-term $a_i\Mod{m_i}$-sequence for
some $i$, $[1,a_0+1]$ will either contain a monochromatic 2-term $a_i\Mod{m_i}$-sequence
or else will contain a 1-term monochromatic $a_i\Mod{m_i}$-sequence and
a 1-term monochromatic $a_j\Mod{m_j}$-sequence, with $j\neq i$, not of the
same color. Hence the result holds for $t = 2$.

Now assume that for a fixed $t$ the result holds (still assuming $d=1$).
Let $F(t) = m(t-2)+a_0+1$ and let $\chi$ be an $r$-coloring of $[1,F(t+1)]$.
For $i = r$, let
\[ X_i = \{x_{i_1},\ldots,x_{i_{k_i}}\} \subseteq [1, F(t)] \]
be the monochromatic $a_i\Mod{m_i}$-sequences given by the induction
hypothesis. By the Chinese remainder theorem there is a $z$ with $F(t)<z
\leq F(t)+m$ satisfying
\[ z \equiv (a_i+x_{i_{k_i}})\Mod{m_i} \]
for $i = 1,\ldots,r$. Then, for some $i$, $X_i\cup \{z\}$ is a $(k_i+1)$-term
monochromatic $a_i\Mod{m_i}$-sequence such that $\chi(X_i\cup\{z\})\neq \chi(X_j)$
for all $j\neq i$. Hence in $[1,F(t)+m] = [1, F(t+1)]$ there is, for each $i=
1,\ldots,r$ a monochromatic $a_i\Mod{m_i}$-sequence, with no two sequences
of the same color, such that the sum of the length of the sequences is $t+1$.
This completes the proof for the case in which $d=1$.

We now assume $d\neq1$. Let $\alpha$ be any $r$-coloring of $[1,F(t)]$. Let
\[ N = 1+\frac{a_0}d + \frac{m_1\cdots m_r}{d^r}(t-2) = \frac{F(t)-1}{d}+1. \]
Define $\alpha'$ on $[1,N]$ by $\alpha'(i) = \alpha(d(i-1)+1)$. Since $\gcd(
m_i/d,m_j/d) = 1$ for $i\neq j$ we know that by the previous case, under
$\alpha'$, $[1,N]$ contains, for each $i=1,\ldots,r$, a monochromatic $k_i$-term
$\frac{a_i}{d}\Mod{\frac{m_i}d}$-sequence $X_i = \{x_{i_1},\ldots,x_{i_{k_i}}\}$
such that
\[ \sum_{i=1}^r k_i = t \text{ and } \alpha'(X_{i_1}) = \alpha'(X_{i_2}) \text{ for } i_1\neq i_2. \]
Then under $\alpha$, for each $i$,
\[ Y_i = \{d(x_{i_s}-1) + 1: s = 1,\ldots, k_i \} \]
is a monochromatic $a_i\Mod{m_i}$-sequence contained in $[1,F(t)]$ with
$\alpha(Y_i)\neq \alpha(Y_j)$ for $i\neq j$.\end{proof}

\begin{corl}\label{c2} Let $S = \{a_i\Mod{m_i}:1\leq i\leq r\}$ and assume
$r$, $d$, $m$, all $a_i$, and all $m_i$ satisfy the hypotheses of Theorem
\ref{t6}. Then for all $k\geq2$
\[ f_S^{(r)}(k)\leq m[r(k-1)-1]+a_0+1.\]
\end{corl}
\begin{proof} By Theorem \ref{t6}, each $r$-coloring of $[1,m(r(k-1)-1)+a_0+1]$
contains, for each $i$, a monochromatic $k_i$-term $a_i\Mod{m_i}$-sequence,
each of a different color, such that $\sum_{i=1}^r k_i = r(k-1)+1$. Then at
least one of these sequences has length at least $k$.\end{proof}

We state separately the upper bound for $f_{a(m_1),b(m_2)}(k)$ provided by
Corollary \ref{c2}.

\begin{corl}\label{c3} Let $1\leq a\leq m_1$, $1\leq b\leq m_2$, and $a_0
= \min\{a,b\}$. Let $d = \gcd(m_1,m_2)$, $m=\lcm\{m_1,m_2\}$, and assume
$d$ divides both $a$ and $b$. Then for all $k\geq2$,
\[ f_{a(m_1),b(m_2)}(k) \leq (2k-3)m+a_0+1. \]
\end{corl}

\section{Remarks\label{s5}}

The upper bounds given by Theorem \ref{t1} and Corollary \ref{c1} are very
sharp. In fact, lower bounds for $f_{q(m),m}(k,n)$ were given in \cite{landman+long1994}
which are of the same order of magnitude as the upper bounds of Theorem
\ref{t1}. For the case in which $m/e$ is odd, the bounds of Theorem \ref{t1}
are best possible; for example, $f_{5(7),7}(3,5)=50$ and $f_{8(13),13}(3,4)
= 76$ (these agree precisely with the bounds provide by Theorem \ref{t1}).
For $m/e$ even, we have found instances in which the upper bound of Theorem
\ref{t1} differs from the actual value of $f$ by only 1; for example,
$f_{9(10),10}(3,3)=49$.

Since Theorem \ref{t1} is just a special case of Corollary \ref{c1} (the case
in which $T = \{m\}$), the above examples also show that the bounds of
Corollary \ref{c1} are sharp. We have found many additional examples,
however, in which the bounds of Corollary \ref{c1} are sharp (and sometimes
precise). For example, it is easy to see, from the proof of Corollary \ref{c1},
that $f_{5(7),14}(3,3)\leq f_{5(7),7}(3,5) = 50$, and this is the exact
value of $f_{5(7),14}(3,3)$. Perhaps more surprisingly, when $T = \{9,14\}$,
the value of $f_{5(7),T}(3,3)$ is still 50, again coinciding with the upper
bound of Corollary \ref{c1}.

There are many cases in which the bound given by Theorem \ref{t3}, and
hence Theorem \ref{t4}, is more than twice the actual value of $f$. However,
we have also found many examples where the bound is very sharp. In particular,
computer data suggests the following conjecture is true:

\begin{conj}\label{cjj} Let $c\geq2$, let $m_1$ be even and let $b = (c-1)m_1$. Then
$f_{a(m_1),b(m_2)}(3) = 4(c-1)m_1+1$.\end{conj}

We see that, under the same hypotheses of Conjecture \ref{cjj}, the upper
bound for $f$ given by Theorem \ref{t3} is $4cm_1$.

The bound given by Corollary \ref{c3} has order of magnitude $2mk$, where
$m = \lcm\{m_1,m_2\}$. We have computed many values of $f$, where the
hypotheses of Corollary \ref{c3} are satisfied, and have not found any
where $f$ grows quite that fast, but have found many examples in which
it grows faster than $mk$. One interesting set of examples is where
$a=1$, $m_1=2$, $b$ is odd, and $m_2$ is odd. In all such cases,
$f_{a(m_1),b(m_2)}(3) = m+a+2b$ and, whenever $k\geq 4$ and $b<m_2/2$,
we found that $f_{a(m_1),b(m_2)}(k) = m+a+2b + (k-3)(m+b)$. In addition,
when $b = (m_2+1)/2$ (so $m_2\equiv1\Mod4$), $f_{a(m_1),b(m_2)}(k) =
m+a+2b+(k-3)(m+b-1)$. Hence, in the case of $b = (m_2\pm1)/2$, $f(k)$
has value $m+a+\frac{m}2\pm1+(k-3)\left(m+\frac12\left(\frac{m}2-1\right)\right)$.
This would suggest a growth rate of $f$ of $\frac54mk$.


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