%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-23/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}

\title{Monochromatic Homothetic Copies of $\{1, 1+s, 1+s+t\}$ }
\author{Tom C. Brown, Bruce M. Landman and
Marni Mishna\footnote{The first and third authors were partially supported by NSERC.}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, Bruce~M. Landman, and Marni Mishna, \emph{Monochromatic
  homothetic copies of $\lbrace s, 1+s, 1+s+t \rbrace$ }, Canad. Math. Bull.
  \textbf{40} (1997), 149--157.}\bigskip\end{center}

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

\begin{abstract}
For positive integers $s$ and $t$, let $f(s,t)$ denote the smallest
positive integer $N$ such that every 2-coloring of $[1,N] = \{1,2,\ldots,N\}$
has a monochromatic homothetic copy of $\{1,1+s,1+s+t\}$.

We show that $f(s,t) = 4(s+t)+1$ whenever $s/g$ and $t/g$ are not congruent
to 0 (modulo 4), where $g = \gcd(s,t)$. This can be viewed as a generalization
of part of van der Waerden's theorem on arithmetic progressions, since the
3-term arithmetic progressions are the homothetic copies of $\{1,1+1,1+1+1\}$.
We also show that $f(s,t) = 4(s+t)+1$ in many other cases (for example,
whenever $s>2t>2$ and $t$ does not divide $s$), and that $f(s,t)\leq4(s+t)+1$
for all $s,t$.

Thus the set of homothetic copies of $\{1,1+s,1+s+t\}$ is a set of triples with
a particularly simple Ramsey function (at least for the case of two colours),
and one wonders what other ``natural'' sets of triples, quadruples, etc.,
have simple (or easily estimated) Ramsey functions.
\end{abstract}

\section{Introduction}

Van der Waerden's Theorem on Arithmetic Progressions \cite{vanderwaerden1927}
states that for every positive integer $k$ there exists a smallest positive
integer $w(k)$ such that for every 2-coloring of $[1,w(k)] = \{1,2,\ldots,
w(k)\}$, there is a monochromatic $k$-term arithmetic progression. (In other
words, if $[1,w(k)]$ is partitioned in any way into two parts $A$ and $B$,
then either $A$ or $B$ must contain a $k$-term arithmetic progression.) The
only known non-trivial values of $w(k)$ are $w(3) = 9$, $w(4) = 35$, $w(5)
= 178$. Furthermore the estimation of the function $w(k)$ for large $k$ is
one of the most outstanding (and presumably one of the most difficult)
problems in Ramsey theory. For a discussion of this, see \cite{graham+rothschild+spencer1990}.

The function $w(k)$ is often called the \emph{Ramsey function} for the set
of $k$-term arithmetic progressions. Landman and Greenwell \cite{landman+greenwell1988,
landman+greenwell1990-1} considered the Ramsey function $g(n)$ of the set
of all $n$-term sequences that are homothetic copies (see the definition
below) of $\{1,2,2+t,2+t+t^2,\ldots,2+t+t^2+\cdots+t^{n-2}\}$ for some
positive integer $t$. They obtained a lower bound for $g(n)$ and an upper
bound for $g^{(r)}(3)$, where the $(r)$ indicates that $r$ colours are
used. Other ``substitutes'' for the set of $k$-term arithmetic progressions
were introduced in \cite{brown+erdos+freedman1990}.

In contrast, in this paper we consider the Ramsey function associated with
a much smaller set of sequences, namely the set of homothetic copies of
$\{1,1+s,1+s+t\}$ for given positive integers $s$ and $t$.

A \emph{homothetic copy} of $\{1,1+s,1+s+t\}$ is any set of the form
$\{x,x+ys,x+ys+yt\}$, where $x$ and $y$ are positive integers. From now
on, let us agree to use the term ``$(s,t)$-progression'' to refer to a
homothetic copy of $\{1,1+s,1+s+t\}$.

Instead of considering 3-term arithmetic progressions, as in the case
$k=3$ of van der Waerden's theorem, we consider the set of $(s,t)$-progressions
for given positive integers $s$ and $t$. (Note that the $(1,1)$-progressions
are the 3-term arithmetic progressions.)

For positive integers $s$ and $t$ we define $f(s,t)$ to be the smallest
positive integer $N$ such that every 2-colouring of $[1,N]$ has a monochromatic
$(s,t)$-progression. Note that $f(s,t) = f(t,s)$. We will use this fact
several times.

We show that for all positive integers $s$ and $t$, if $s/g\not\equiv0$ and $t/g\not\equiv0$
(mod 4), where $g = \gcd(s, t)$, then $f(s,t) = 4(s + t) + 1$. A special case
of this is $w(3) = f(1,1) = 9$. Thus this result can be viewed as a
generalization of the case $k = 3$ of van der Waerden’s theorem.

We also show that $f(s,t)\leq4(s + t) + 1$ for all $s$ and $t$, and we show
that even if $s/g\equiv0$ or $t/g\equiv0$ (mod 4), the equality $f(s,t) =
4(s + t) + 1$ still holds, except for a small number of possible exceptions.
For example, we are unable to find the exact value of $f(4m,1)$, although we
show in Theorem \ref{t4} that $4(4m + 1)\leq f(4m,1)\leq 4(4m + 1) + 1$.
The remaining cases where $f(s,t)$ is unknown are described in Section \ref{s4}.

\section{Upper bounds}

First we give a simple proof of the weak bound $f(s,t) \leq 9s + 8t$,
which is subsequently refined (in Theorem \ref{t2} below) to give the stronger
bound $f(s,t)\leq4(s + t) + 1$. The equality $w(3) = 9$ will be used in our
proof of this weak bound, but will not be used again.

We prove $f(s,t)\leq 9s + 8t$ by contradiction. Assume that $f(s,t)>9s + 8t$,
and let $[1,9s + 8t]$ be 2-coloured, using the colours Red and Blue, in such
a way that there is no monochromatic $(s,t)$-progression. Since $w(3) = 9$,
the set $\{s, 2s, 3s, \ldots, 9s\}$ contains a monochromatic (say in the
colour Red) 3-term arithmetic progression. Let us suppose, in order to
simplify our notation, that this Red progression is $\{s, 5s,9s\}$. (In all
other cases, the argument is essentially the same.)

Consider the $(s,t)$-progressions $\{s,5s,5s+4t\}$, $\{5s,9s,9s + 4t\}$,
$\{s, 9s, 9s + 8t\}$. Since by assumption none of these is monochromatic,
and $s$, $5s$, $9s$ are all Red, it follows that $\{5s + 4t, 9s + 4t, 9s + 8t\}$
is a Blue $(s,t)$-progression, a contradiction, completing the proof.

The following theorem will be useful in obtaining both upper and lower bounds for
$f(s,t)$.

\begin{thrm}\label{t1} Let $s,t,c$ be positive integers. Then $f(cs,ct) =
c(f(s,t)-1)+1$. \end{thrm}
\begin{proof} Let $M = f(s,t)$. Let $B$ be a 2-colouring of $[1,c(M-1)+1]$. Since
every 2-colouring of $[0,M-1]$ contains a monochromatic $(s,t)$-progression, every
2-colouring of $\{1,c+1,2c+1,\ldots,(M-1)c+1\}$ contains a monochromatic $(cs,ct)$-progression.
Thus, $f(cs,ct)\leq c(M-1)+1$.

On the other hand, we know there is a 2-colouring, B, of $[1,M-1]$ that
contains no monochromatic $(s,t)$-progressions. Define $B'$ on $[1, c(M-1)]$ by
$B'([c(i-1)+1,ci]) = B(i)$, for $i = 1,\ldots,M-1$. We will show that $B'$ avoids
monochromatic $(cs,ct)$-progressions, which will complete the proof.

Assume, by way of contradiction, that $x_1, x_2, x_3$ is a $(cs,ct)$-progression,
contained in $[1, c(M-1)]$, that is monochromatic under $B'$. Then there exists
$r>0$ such that $x_3- x_2 = rct$, $x_2-x_1 = rcs$. Let $y_j = \ceil{x_j/c}$ for
$j = 1,2,3$. Then $y_3 - y_2 = \ceil{x_3/c} - \ceil{x_2/c} = rt$, and similarly
$y_2 - y_1 = rs$.

Hence $y_1, y_2, y_3$ is an $(s, t)$-progression. Also, $B(y_j) = B(\ceil{x_j/c})
= B' (x_j)$, for each j. This contradicts our assumption that there is no
monochromatic $(s,t)$-progression relative to the colouring $B$.
\end{proof}

Note that this proof easily extends to a proof that if $f(a_1,\ldots,a_k) = M$,
then $f(ca_1,\ldots,ca_k) = c(M-1)+1$, where $f(a_1,\ldots,a_k)$ denotes the
least positive integer $N$ such that every 2-coloring of $[1,N]$ will contain
a monochromatic homothetic copy of $\{1,1+a_1,1+a_1+a_2,\ldots,1+a_1+a_2+\cdots+a_k\}$.

\begin{thrm}\label{t2} For all positive integers $s$ and $t$, $f(s,t)\leq 4(s+t)+1$.
\end{thrm}
\begin{proof} Let $s,t$ be given. We may assume without loss of generality that
$s\leq t$. We may also assume that $\gcd(s,t) = 1$, for if we knew the result in
this case then, with $g=\gcd(s,t)$, Theorem \ref{t1} would give $f(s,t)=g\ceil{f(s/g,t/g)-1}
+1\leq g[4(s/g+t/g)+1-1]+1 = 4(s+t)+1$.

Consider the following set of 20 triples contained in $[1,4(s+t)+1]$, which
are all $(s,t)$-progressions:
\[ \{ 1, s + 1, s + t + 1\}, \{ s + 1, 2s + 1, 2s + t + 1\} \]
\[ \{ 2s + 1, 3s + 1, 3s + t + 1\}, \{ 3s + 1, 4s + 1, 4s + t + 1\} \]
\[ \{ 1, 2s + 1, 2s + 2t + 1\}, \{ s + 1, 3s + 1, 3s + 2t + 1\} \]
\[ \{ 2s + 1, 4s + 1, 4s + 2t + 1\}, \{ 1, 3s + 1, 3s + 3t + 1\} \]
\[ \{ s + 1, 4s + 1, 4s + 3t + 1\}, \{ 1, 4s + 1, 4s + 4t + 1\} \]
\[ \{ s + t + 1, 2s + t + 1, 2s + 2t + 1\}, \{ 2s + t + 1, 3s + t + 1, 3s + 2t + 1\} \]
\[ \{3s + t + 1, 4s + t + 1, 4s + 2t + 1\}, \{ s + t + 1, 3s + t + 1, 3s + 3t + 1\} \]
\[ \{2s + t + 1, 4s + t + 1, 4s + 2t + 1\}, \{ s + t + 1, 4s + t + 1, 4s + 4t + 1\} \]
\[ \{2s + 2t + 1, 3s + 2t + 1, 3s + 3t + 1\}, \{ 3s + 2t + 1, 4s + 2t + 1, 4s + 3t + 1\} \]
\[ \{2s + 2t + 1, 4s + 2t + 1, 4s + 4t + 1\}, \{ 3s + 3t + 1, 4s + 3t + 1, 4s + 4t + 1\} \]

It is straightforward to check (under the assumptions that $s\leq t$ and $\gcd(s,t)
= 1$) that except in the cases $s = 1, 1 \leq t\leq 3$, the 15 integers which
appear in these 20 triples are distinct. It is then a simple matter to check all
2-colourings of these 15 integers and verify that each 2-colouring has a
monochromatic triple from the above list of 20 triples. (If one identifies these
15 integers with the numbers 1,2,\ldots,15 via the correspondence
\[ 1 \leftrightarrow 1, s + 1 \leftrightarrow 2, 2s + 1\leftrightarrow 3, 3s+1\leftrightarrow4, 4s+1\leftrightarrow5, \]
\[ s+t+1\leftrightarrow6, 2s+t+1\leftrightarrow7, 3s+t+1\leftrightarrow8, 4s+t+1\leftrightarrow9, \]
\[ 2s+2t+1\leftrightarrow10, 3s+2t+1\leftrightarrow11, 4s+2t+1\leftrightarrow12, \]
\[ 3s + 3t + 1\leftrightarrow13, 4s+3t+1\leftrightarrow14, 4s+4t+1\leftrightarrow15, \]
the resulting set of 20 triples contained in $[1,15]$ has a particularly pleasing
form.) The cases $s=1,1\leq t\leq 3$ can be checked separately. In all cases we
obtain $f(s,t)\leq 4(s+t)+1$.\end{proof}

\section{Lower bounds and exact values for $f(s,t)$}

\begin{thrm}\label{t3} Let $s,t$ be positive integers, and let $g=\gcd(s,t)$. If $s/g\not\equiv0$
and $t/g\not\equiv0$ (mod 4) then $f(s,t) = 4(s+t)+1$.\end{thrm}
\begin{proof} The proof splits naturally into two cases.

\paragraph{Case 1.} Assume that $s/g$ and $t/g$ are both odd. In view of Theorem \ref{t2},
we only need to show that $f(s,t) \geq 4(s+t)+1$.

First, assume $g=1$. Now colour $[1,4(s+t)]$ as
\[ 101010\cdots10~010101\cdots01, \]
where each of the two long blocks has length $2(s+t)$. Assume $x,y,z$ is a monochromatic
$(s,t)$-progression. Then $y=x+ds$ and $z=y+dt$, for some positive integer $d$. Let $B_1$
and $B_2$ represent $[1,2(s+t)]$ and $[2(s+t)+1,4(s+t)]$, respectively.

In case $d$ is odd, then $x$ and $y$ have opposite parity, and $y$ and $z$ have
opposite parity. Since $x$ and $y$ have the same colour and opposite parity, $x$
is in $B_1$, while $y$ is in $B_2$. Hence $z$ is in $B_2$, so that $y$ and $z$ cannot
have the same colour, a contradiction.

If $d$ is even, then $x$, $y$ and $z$ all have the same parity, so they all
must be in the same $B_i$. But then $d(s+t) = z - x \leq 2(s+t)$, and hence
$d=1$, a contradiction.

If $g$ is unequal to 1, then by Theorem \ref{t1} and the case in which $g=1$,
$f(s,t) = g[f(s/g,t/g)-1]+1\geq g[4(s/g+t/g)+1-1]+1=4(s+t)+1$. This finishes
the proof of Case 1.

\paragraph{Case 2.} Assume without loss of generality that $s/2\equiv2$ (mod 4).
First we assume that $g=1$. Then $s\equiv2$ (mod 4) and $t$ is odd.

By Theorem \ref{t2}, we only need to provide a 2-colouring of $[1,4(s+t)]$ that
contains no monochromatic $(s,t)$-progression. Let $C$ be the colouring
$11001100\cdots1100$ (i.e., $s+t$ consecutive blocks each having the form 1100).

We proceed by contradiction. Assume that $x,y,z$ is a monochromatic
$(s,t)$-progression. So there exists a $d>0$ such that $y-x = ds$ and $z-y = dt$.
By the way $C$ is defined, if $C(i) = C(j)$ and $j - i$ is even, then 4 divides
$j - i$. Now since $z - x = d(s+t) \leq 4(s+t) - 1$, we must have that $d < 4$.
The case $d = 2$ is impossible, for if $d = 2$, then $C(z) = C(x)$, $z - x =
d(s + t)$ is even, but 4 does not divide $z - x$, a contradiction. Hence $d$ is
odd. But then, since $s\equiv2$ (mod 4), $y - x$ is even yet 4 doesn't divide
$y - x$, again a contradiction.

This shows that $f(s,t) \geq 4(s+t)+1$ in the case $g=1$.

If $g$ is unequal to 1, we proceed just as at the end of Case 1.\end{proof}

Suppose that $s/g\equiv0$ (mod 4), where $g = \gcd(s,t)$. Then $t/g$ is odd,
and in the case $t/g = 1$, that is, $t$ divides $s$, we have the following
result.

\begin{thrm}\label{t4} Let $m,t$ be positive integers. Then either
\[ f(4mt,t) = 4(4mt +t) - t + 1 \text{ or } f(4mt,t) = 4(4mt+t)+1. \]
\end{thrm}
\begin{proof} By Theorem \ref{t1}, it is sufficient to show that $4(4m+1)\leq f(4m,1)
\leq 4(4m+1)+1$. By Theorem \ref{t2}, we only need to show that $4(4m+1)\leq f(4m,1)$.
Thus it suffices to find a 2-colouring of $[1,16m+3]$ that avoids monochromatic
$(4m,1)$-progressions. Let $\chi$ be the colouring $1A0B0C1D0$, where
\begin{align*}
A &= 00110011\cdots0011 \text{ has length } 4m \\
B &= 11001100\cdots11 \text{ has length } 4m-2 \\
C &= 11001100\cdots1100 \text{ has length } 4m \\
D &= 00110011\cdots0011 \text{ has length } 4m.
\end{align*}

Assume $x,y,z$ is a monochromatic $(4m,1)$-progression. We shall reach a contradiction.
We know there exists a positive integer $d$ such that $y-x = 4md$ and $z-y=d$. Hence,
$d(4m+1)\leq16m+2$, so that $d\leq3$. Let
\begin{align*}
S_1 &= [2,4m+1] \text{ (corresponds to $A$ above)} \\
S_2 &= [4m+3,8m] \text{ (corresponds to $B$ above)} \\
S_3 &= [8m+2,12m+1] \text{ (corresponds to $C$ above)} \\
S_4 &= [12m+3,16m+2] \text{ (corresponds to $D$ above).}
\end{align*}

\paragraph{Case 1.} $d = 1$. Then $y,z$ belong to the same $S_i$, for some $1\leq i\leq4$.
Denote by $S(i,j)$ the $j$th element of $S_i$. We see that $y = S(i,j)$ for some odd $j$.
Note that for each even $p$, if $i = 2$ or 4, then $\chi(S(i-1),p)$ is unequal to $\chi
(S(i,p-1))$. Now if $i=2$ or $i=4$, then $x = y-4m = S(i-1,j+1)$, so that (by the preceding
remark), $\chi(x)$ is different from $\chi(y)$, a contradiction. Now if $i = 3$ and $j>1$,
then $y - 4m = S(2, j-1)$, and $\chi(x) = \chi(y - 4m)$ is unequal to $\chi(y)$, a
contradiction. If $i = 3$ and $j = 1$, then $x = 4m + 2$ and $y = 8m + 2$, and these again
have different colours.

\paragraph{Case 2.} $d = 2$. Then $y - x = 8m$ and $z-y = 2$. If $\chi(y) = \chi(z)$ then
$y$ must be one of the following: $4m+1,8m,12m+1$; and since $y-x=8m$, this reduces the
possibilities for $y$ to only $12m+1$. However we see that $\chi(4m+1)$ is unequal to
$\chi(12m+1)$, a contradiction.

\paragraph{Case 3.} $d = 3$. Then $y-x = 12m$ and $z-y = 3$. Clearly $x$ belongs to $[1,4m]$,
so that $y$ belongs to $[12m+1,16m]$. Now $[1,4m]$ has colouring $1~0011\cdots001100~1$
while $[12m+1,16m]$ has colouring $0100110011\cdots001100$. Hence, since $\chi(x) = \chi(y)$,
$y$ belongs to the set $\{12m+3,12m+5,12m+7,\ldots,16m-1\}$. Now $z$ belongs to $[12m+4,
16m+3]$, so let's compare the colouring of $[12m+1,16m]$ to that of $[12m+4,16m+3]$:
$[12m+1,16m]$ has colouring as noted above, while $[12m+4,16m+3]$ has colouring $0~11001100
\cdots11~0$. Hence, in order for $\chi(y) = \chi(z)$, $y$ must belong to the set $\{12m+1,
12m+2,12m+4,12m+6,\ldots,16m\}$, a contradiction.\end{proof}

\begin{thrm}\label{t5} Let $s,t$ be positive integers such that $s>t>1$ and $t$ does
not divide $s$. If $\floor{s/t}$ is even or $\floor{2s/t}$ is even, where $\floor{\cdot}$
is the floor function, then $f(s,t)=4(s+t)+1$. If $\floor{s/t}$ and $\floor{2s/t}$ are
both odd, then $f(s,t) = 4(s+t)+1$ provided $s$,$t$ satisfy the additional condition
$s/t\notin(1.5,2)$.\end{thrm}
\begin{proof} Let $s,t$ satisfy the hypotheses of the theorem. By Theorems \ref{t1} and
\ref{t2}, it suffices to show that $f(s,t)\geq 4(s+t)+1$ under the additional assumption
that $\gcd(s,t) = 1$, hence throughout the proof we assume $\gcd(s,t) = 1$.

Let $a = \floor{s/t}$ and $b = \floor{2s/t}$. Then $s=at+r$, where $0<r<t$. Also, $2s=2at
+2r$, so if $2r=t$ we would have $t=2$. However, since $\gcd(s,t) = 1$, the case $t=2$ is
already covered by Theorem \ref{t3}. Therefore we assume throughout that proof that $2r
\neq t$.

\paragraph{Case 1.} We assume that $a$ is even and $b$ is odd. Then $b = 2a + 1$,
$2r > t$, and $2(s + t) = 2(at + r) + 2t = (b - 1)t + 2r + 2t = (b + 2)t + (2r-t)$.

Hence we can colour $[1,4(s+t)]$ as follows. Let
\[ C = QRQR\cdots QRQJ~RQRQ\cdots RQRJ', \]
where $Q = 11\cdots1$ and $R = 00\cdots0$ each have length $t$, $J = 00\cdots0$ and
$J' = 11\cdots1$ each have length $2r-t$, and where each of $Q$ and $R$ appears $b+2$
times.

Suppose $x,y,z$ is any $(s,t)$-progression in $[1,4(s+t)]$ with $y-x = ds$, $z-y=dt$.
We will show that $\{x,y,z\}$ is not monochromatic. Clearly $d\leq3$, since $d(s+t)
z-x\leq 4(s+t)-1$.

If $d=2$, then $z-x=2(s+t)$, so $C(z)\neq C(x)$. (This is because the colouring on the
second half of $[1,4(s+t)]$ is the reversal of the colouring on the first half.)

If $d=3$, then, since $z=y+3t$ and $C(i) \neq C(i+t)$ for all $i>2(s+t)$, if $C(y)
= C(z)$ we must have $y\leq 2(s+t)$; but then $x = y - 3s \leq 2t - s$. However,
the conditions $s>t$, $s = at + r$, $0<r<t$, $a$ even, imply that $s>2t$, hence
$x<0$, a contradiction.

Now assume that $d=1$ and $C(y)=C(z)$. Since $z=y+t$, $y$ must occur in the block $J$,
so $C(y) = 0$. Since $J$ has length $2r-t<r$, we see that $y-r$ must occur in the
block $Q$ just to the left of block $J$, so that $y-at-r=x$ also occurs in a block
$Q$, and $C(x) = 1$.

Hence there is no monochromatic $(s,t)$-progression with respect to the colouring
$C$, therefore $f(s,t)\geq 4(s+t)+1$. This finishes Case 1.

\paragraph{Case 2.} We assume that $a$ is odd and $b$ is even. Again we have $s=at+r$,
$0<r<t$, but now $b=2a$, $2r<t$, and $2(s+t) = (b+2)t+2r$.

Now colour $[1,4(s+t)]$ with the colouring
\[ D = QRQR\cdots QRK~RQRQ\cdots RQK', \]
where $Q,R$ are defined as in Case 1, and $K = 11\cdots1, K'=00\cdots0$ each have
length $2r$.

Assume $x,y,z$ is an $(s,t)$-progression contained in $[1,4(s+t)]$, with $y-x = ds$,
$z-y=dt$; then $d\leq3$.

If $d = 2$, then as in Case 1, $D(x)\neq D(z)$.

If $d = 3$, and $D(y) = D(z)$, then as in Case 1, $y\leq 2(s+t)$. In fact, since $K$
and $R$ have opposite colours, $y\leq2(s+t)-2r$. On the other hand, $y\geq1+3s\geq2s
+t+r+1$, so $y$ is an element of the last occurrence of $R$ in $[1,2(s+t)]$, hence
$D(y) = 0$. Then $x = y-3s\leq 2(s+t)-2r-3s<t$, so $D(x) = 1$ and $D(x)\neq D(y)$.

Now assume $d=1$ and $D(y)=D(z)$. Then $y$ belongs to the last occurrence of $R$ in
$[1,2(s+t)]$, and $y\equiv i$ (mod $t$), where $2r<i\leq t$. Hence, since $a$ is odd,
$x = y - (at+r)$ lies in one of the $Q$'s, and $D(x) = 1$, $D(y) = 0$.

Thus, no monochromatic $(s,t)$-progression exists in $[1,4(s+t)]$, hence $f(s,t)\geq
4(s+t)+1$.

\paragraph{Case 3.} We assume that both $a$ and $b$ are even. Then $s = at + r$,
$b = 2a$, $0<2r<t$, and $2(s+t)=(b+2)t+2r$. Note that $a\geq2$, since $s>t$.

We define the colouring $E$ on $[1,4(s+t)]$ as follows. Let us use the notation
$\sim0 = 1$ and $\sim1 = 0$. Then we define, in turn,
\begin{enumerate}
\item[(1)] $E(i) = 1$, $1\leq i\leq r$,
\item[(2)] $E(i) = \sim E(i-r)1$, $r<i\leq t$,
\item[(3)] $E(i) = \sim E(i-t)$, $t< i\leq 2(s+t)$,
\item[(4)] $E(i) = \sim E(i-2(s+t))$, $2(s+t)< i\leq 4(s+t)$.
\end{enumerate}

That is,
\[ E = XYXY\cdots XYL~YXYX\cdots YXL', \]
where $X$ has length $t$ and consists of $\floor{t/r}$ blocks, each block of length $r$,
followed by a single block of length $t - \floor{t/r}r$, the blocks alternating in
colour; $Y$ is the same as $X$, except the colours are reversed; $L$ is $X$ restricted
to $[1,2r]$; and $L'$ is the same as $L$, except the colors are reversed.

Let $x,y,z$ be an $(s,t)$-progression contained $[1,4(s+t)]$, with $y-x = ds$, $z-y=dt$.

If $d = 2$, then by (4), $E(x)=\sim E(z)$.

If $d = 3$ and $E(y) = E(z)$, then $y\leq 2(s+t)$, hence $x = y-3s\leq 2t - s = 2t -
(at+r)\leq -r < 0$, a contradiction.

If $d = 1$ and $E(y) = E(z)$, then $y\leq 2(s+t)$. We consider two subcases.

The first subcase is $y\equiv i$ (mod $t$), $r+1\leq i\leq t$. Then $y$ and $y-r$ are in
the same block $(X,Y$ or $L$) hence by (2) $E(y) = \sim E(y-r)$. By (3), and the fact
that $a$ is even, $E(y) = \sim E(y-r) = \sim E(y-at-r) = \sim E(x)$.

The second subcase is $y\equiv i$ (mod $t$), $1\leq i\leq r$. Since $E(y)=E(z) = E(y+t)$,
$y$ must belong to the block $L$, that is, $y = (b+2)t+i = (2a+2)t+i$, $1\leq i\leq r$.
Since $x = y - s = (2a+2)t+i-at-r = (a+1)t+ (i+t-r)$, and $1\leq i + t - r\leq t$, by
(3) $E(x) = \sim E(i+t-r)$. Also, since $y = 2(s+t) - 2r+i$, we have $z=y+t=2(s+t)+
(i+t-2r)$, so by (4), $E(z) = \sim E(i+t-2r)$. Since $1\leq i + t - 2r\leq t$, (2)
gives $E(z) = E(i+t-r) = \sim E(x)$.

Thus, under the colouring $E$, there is no monochromatic $(s,t)$-progression in $[1,
4(s+t)]$, hence $f(s,t)\geq 4(s+t)+1$.

\paragraph{Case 4.} Assume that both $a$ and $b$ are odd, and $s/t\notin(1.5,2)$. It
follows that $s = at+r$, $0<r<t$, $b = 2a+1$, $t<2r$, and $2(s+t) = (b+2)t+(2r-t)$.
Also, $a\geq3$, as a consequence of the assumption $s/t\notin(1.5,2)$.

Let $p = t-r$. Then $p<t/2$. Define the colouring $F$ by setting, in turn,
\begin{enumerate}
\item[(5)] $F(i) = 1$, $1\leq i\leq p$,
\item[(6)] $F(i) = \sim F(i-p)$, $p< i\leq p$,
\item[(7)] $F(i) = \sim F(i-t)$, $t< i\leq 2(s+t)$,
\item[(8)] $F(i) = \sim F(i - 2(s+t))$, $2(s+t)< i\leq 4(s+t)$,
\end{enumerate}

That is,
\[ F = ABAB\cdots ABAM~BABA\cdots BABM', \]
where $A$ and $B$ are the same as blocks $X$ and $Y$ in Case 3, except that $p$ replaces
$r$; $M$ is $B$ restricted to $[1,2r-t]$; and $M'$ is the same as $M$ with the colours
interchanged.

Let $x,y,z$ be an $(s,t)$-progression contained in $[1,4(s+t)]$, with $y-x = ds$, $z-y=dt$.

If $d=2$, then by (8), $E(x) = \sim E(z)$.

If $d=3$ and $E(y) = E(z)$, then $y\leq 2(s+t)$, hence (since $a\geq3$) $x = y - 3s\leq 2t
- s = 2t - (at+ r) < 0$, a contradiction.

If $d=1$ and $E(y) = E(z)$, then $y\leq2(s+t)$, and we again consider two subcases.

The first subcase is $y = ut + i$, $1\leq i\leq r$. Then $1\leq i<i+p = i+t-r\leq t$,
so by (6), $F(i+p) = \sim F(i)$. Using (7) and the oddness of $a$, we get $F(x) = F(y-at-r)
= F(ut - (a+1)t+i+t-r) = F(ut+i+t-r) = F(ut+i+p) = \sim F(ut + i) = \sim F(y)$.

The second subcase is $y = ut + i$, $r+1\leq i \leq t$. Since $F(y) = F(y+t)$ and $M$ has
fewer than $i$ elements, $y$ must belong to the last occurrence of the block $A$ in $[1,
2(s+t)]$. Since $2(s+t) = (b+2)t + (2t-r)$, this means that $y = (b+1)t + i$, hence by
(7), $F(y) = F(i)$. Since $x = y - at - r = (b+1)t + i - at - r$, we have $F(x) = \sim
F(i-r) = F(i+t-r) = F(i+p) = \sim F(i) = \sim F(y)$.

Thus, under the colouring $F$, there is no monochromatic $(s,t)$-progression in $[1,4(s+t)]$,
hence $f(s,t) \geq 4(s+t) +1$.
\end{proof}

\section{Remarks\label{s4}}

By Theorems \ref{t1} and \ref{t3}, we would know the value of $f(s, t)$ for all $s,t$
provided we knew the value of $f(4m,t)$ when $t$ is odd, and $\gcd(m,t) = 1$. (Here we
are using $f(s,t) = f(t,s)$.) Theorem \ref{t4} shows $4(4m + 1)\leq f(4m,1)\leq4(4m+1)+1$.
Theorem \ref{t5} takes care of many of the cases where $t>1$. For example, Theorem
\ref{t5} shows that $f(4m,3) = 4(4m + 3) + 1$ whenever 3 does not divide $m$. By
examining the cases not covered by Theorem \ref{t5}, one sees that these are exactly
the cases $f(t + r,t)$ where $0<r<t<2r$, and 4 divides $t$ or 4 divides $t + r$.

The computations $f(4,1) = 20$, $f(8,1) = 36$, $f(12,1) = 52$ suggest that perhaps
$f(4m,1) = 4(4m + 1)$ for all $m\geq 1$.

For positive integers $r,a_1,\ldots,a_n$, let $f^{(r)}(a_1,\ldots,a_n)$ denote the smallest
positive integer $N$ such that every $r$-colouring of $[1,N]$ ha a monochromatic homothetic copy
of $\{1,1+a_1,\ldots,1+a_1+\cdots+a_n\}$. Of course $f^{(r)}(a_1,\ldots,a_n)$ always
exists (by a statement of van der Warden's theorem which involves any number of colours),
but perhaps one can say something about the rate of growth of $f^{(r)}(a_1,\ldots,a_n)$
as a function of $a_1+\cdots+a_n$. The computations $f^{(2)}(1,1,1) = 35$, $f^{(2)}(1,1,2)
= 38$, $f^{(2)}(1,1,3) = 44$, $f^{(2)}(1,1,4) = 56$, $f^{(2)}(1,1,5) = 59$ suggest that
$f^{(2)}(1,1,n)$ does not grow linearly with $n$. Perhaps $f^{(2)}(1,1,n)\sim c2^n$.

We have no idea of the growth rate of $f^{(3)}(s,t)$ as a function of $s+t$.


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