%%%% 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 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}