# Untitled Document

On Generalized Van der Waerden Triples   
Bruce Landman

Department of Mathematical Sciences

University of North Carolina at Greensboro

Greensboro, NC 27402

email: bmlandma@uncg.edu and Aaron Robertson

Department of Mathematics

Colgate University

Hamilton, NY 11346

email: aaron@math.colgate.edu

## Abstract

Van der Waerden’s classical theorem on arithmetic progressions states that for any positive integers $`k`$ and $`r`$, there exists a least positive integer, $`w(k,r)`$, such that any $`r`$-coloring of $`\{1,2,\mathrm{},w(k,r)\}`$ must contain a monochromatic $`k`$-term arithmetic progression $`\{x,x+d,x+2d,\mathrm{},x+(k1)d\}`$. We investigate the following generalization of $`w(3,r)`$. For fixed positive integers $`a`$ and $`b`$ with $`ab`$, define $`N(a,b;r)`$ to be the least positive integer, if it exists, such that any $`r`$-coloring of $`\{1,2,\mathrm{},N(a,b;r)\}`$ must contain a monochromatic set of the form $`\{x,ax+d,bx+2d\}`$. We show that $`N(a,b;2)`$ exists if and only if $`b2a`$, and provide upper and lower bounds for it. We then show that for a large class of pairs $`(a,b)`$, $`N(a,b;r)`$ does not exist for $`r`$ sufficiently large. We also give a result on sets of the form $`\{x,ax+d,ax+2d,\mathrm{},ax+(k1)d\}`$.

1. Introduction

B.L. van der Waerden  proved that for any positive integers $`k`$ and $`r`$, there exists a least positive integer, $`w(k,r)`$, such that any $`r`$-coloring of $`[1,w(k,r)]=\{1,2,\mathrm{},w(k,r)\}`$ must contain a monochromatic $`k`$-term arithmetic progression $`\{x,x+d,x+2d,\mathrm{},x+(k1)d\}`$. The only known non-trivial values of $`w(k,r)`$ are $`w(3,2)=9`$, $`w(4,2)=35`$, $`w(5,2)=178`$, $`w(3,3)=27`$ and $`w(3,4)=76`$. The function $`w(k,r)`$ is sometimes called the Ramsey function for the collection of arithmetic progressions. In  the authors considered a generalization of van der Waerden’s theorem, by considering, for a given function $`f:𝐍𝐍`$, the Ramsey function corresponding to the collection of arithmetic progressions $`\{a,a+d,a+2d,\mathrm{},a+(k1)d\}`$ with the property that $`df(a)`$. The Ramsey functions for other “substitutes” for the set of arithmetic progressions were studied in , , and . In this paper we consider a new generalization of $`w(k,r)`$. To help describe this generalization, we begin with three definitions.

Definition 1.1: Fix $`1ab`$. A set, $`S`$, of three natural numbers is called an $`(a,b)`$-triple if there exist natural numbers $`x`$ and $`d`$ such that $`S=\{x,ax+d,bx+2d\}`$.

Definition 1.2: Fix $`1ab`$. Define $`N(a,b;r)`$ to be the least positive integer, if it exists, such that any $`r`$-coloring of $`[1,N(a,b;r)]`$ must contain a monochromatic $`(a,b)`$-triple.

Definition 1.3: Fix $`1ab`$. Define $`(a,b)`$ to be regular if $`N(a,b;r)`$ exists for all positive integers $`r`$. If $`(a,b)`$ is not regular, the degree of regularity of $`(a,b)`$ is the largest $`r`$ such that $`N(a,b;r)`$ exists. Denote this by $`dor(a,b)`$.

We note here that $`N(1,1;r)`$ is the van der Waerden number $`w(3,r)`$ so that $`N(a,b;r)`$ is a generalization of $`w(3,r)`$, and obviously $`(1,1)`$ is regular. We now discuss the sections which follow.

In Section 2 we consider $`r=2`$. We show that, except for the case in which $`b=2a`$, $`N(a,b;2)`$ does exist; we also find upper and lower bounds on $`N(a,b;2)`$ (for $`b2a`$). For certain pairs $`(a,b)`$, we obtain stronger bounds; in particular, we use a result of  to deal with $`N(a,2a1;2)`$ (when $`a=1`$ this is just $`w(3,2)`$). In Section 3 we establish that $`(a,b)`$ is not regular for a rather large class of pairs $`(a,b)`$, and give an upper bound (for these pairs) on the degree of regularity. We then give lower bounds on $`N(a,b;r)`$ for all $`1ab`$ and $`r>2`$. In Section 4 we make some observations about monochromatic sets of the form $`\{x,ax+d,ax+2d,\mathrm{},ax+(k1)d\}`$ for $`a1`$. We establish that for $`a>1`$ and $`k`$ sufficiently large (dependent upon $`a`$), we can $`4`$-color the natural numbers so that no monochromatic such $`k`$-set exists (this is in contrast to van der Waerden’s theorem which says that there are arbitrarily long monochromatic arithmetic progressions in any $`r`$-coloring of the natural numbers).

2. Using Two Colors

Our first theorem categorizes those $`(a,b)`$ pairs for which $`N(a,b;2)`$ exists, i.e., those pairs for which $`dor(a,b)2`$. It also provides an upper bound on $`N(a,b;2)`$ whenever it exists.

Theorem 2.1: Let $`a,b𝐍`$ with $`ab`$. Then $`dor(a,b)=1`$ if and only if $`b=2a`$.

Furthermore, if $`b2a`$,

$`N(a,b;2)\{\begin{array}{cc}4a(b^3+b^23b3)+2b^3+6b^2+6b\hfill & \mathrm{for}b>2a\hfill \\ 4a(b^3+2b^2+2b)4b^2\hfill & \mathrm{for}b<2a\hfill \end{array}`$

Proof. We first consider the case in which $`b=2a`$. To show that $`N(a,2a;2)`$ does not exist, we exhibit a 2-coloring of N which avoids monochromatic $`(a,2a)`$-triples. Namely, color the natural numbers so that the odd numbers are colored arbitrarily, and so that for each even number $`2n`$, the color of $`2n`$ is different from the color of $`n`$. Such a coloring avoids monochromatic $`(a,2a)`$-triples since such a triple has the form $`\{x,y,z\}`$ where $`z=2y`$.

We next consider the case $`b>2a`$. Let $`M=4a(b^3+b^23b3)+2b^3+4b^2+6b`$ and let $`\chi :[1,M]\{0,1\}`$ be a $`2`$-coloring. Assume there is no monochromatic $`(a,b)`$-triple. Then within the set $`\{2,4,\mathrm{},2b+4\}`$ there exist $`x`$ and $`x+2`$ that are not the same color, since otherwise $`\{2,2a+2,2b+4\}`$ would be a monochromatic $`(a,b)`$-triple. Without loss of generality, assume $`\chi (x)=0`$ and $`\chi (x+2)=1`$. Let $`z`$ be the least integer greater than $`a(x+2)`$ such that $`b2a`$ divides $`z`$.

Let $`S=\{z,az+(b2a),bz+2(b2a)\}`$. Since $`z2a(b+1)+b`$, we have

$$bz+2(b2a)2a(b^2+b2)+b^2+2bM.$$
(1)   
Hence, since $`S`$ is an $`(a,b)`$-triple, some member, say $`s`$, of $`S`$ has color $`1`$. Let

$$T=\{s+i(b2a):0i\frac{s(b1)}{b2a}+2\}.$$

Note that $`bs+2(b2a)`$ is the largest member of $`T`$, and that $`as+(b2a)T`$ since $`b2a`$ divides $`s`$. Also, by (1)

$$bs+2(b2a)2a(b^3+b^22b2)+b^3+2b^2+2bM,$$
(2)   
so some member of $`T`$ must have color 0 (otherwise $`\{s,as+(b2a),bs+2(b2a)\}`$ is monochromatic).

Let $`t`$ be the least member of $`T`$ with color 0. Then $`\chi (t(b2a))=1`$. Note that (2) implies that

$$b(x+2)+2(taxb)=2t+x(b2a)M.$$

Thus, since $`\chi (x+2)=\chi (t(b2a))=1`$, we must have $`\chi (b(x+2)+2(taxb))=0`$ (that $`t(b2a)>a(x+2)`$ follows from the definition of $`t`$). This implies that $`\{x,t,bx+2(tax)\}`$ is a monochromatic $`(a,b)`$-triple, a contradiction.

The case for $`b<2a`$ is very similar. Let $`M=4a(b^3+2b^2+2b)4b^2`$ and let $`\chi `$ be a $`2`$-coloring of $`[1,M]`$. Then the set $`\{2,4,\mathrm{},2b+4\}`$ contains $`x2`$ and $`x`$ that are not the same color. Assume $`\chi (x)=0`$ and $`\chi (x2)=1`$, and let $`z`$ be the least integer greater than $`ax(2ab)`$ such that $`2ab`$ divides $`z`$. Let $`S=\{z,az+(2ab),bz+2(2ab)\}`$. Let $`sS`$ have color $`1`$ and define $`T=\{s,s+(2ab),s+2(2ab),\mathrm{},bs+2(2ab)\}`$. As in the previous case, $`as+(2ab)T`$ and $`T[1,M]`$. Hence, $`T`$ must have a least member, $`t`$, with color $`0`$. Then $`\chi (t(2ab))=1`$, and since $`\chi (x2)=\chi (t(2ab))=1`$, we must have $`\chi (b(x2)+2(tax+b))=0`$. This gives the monochromatic $`(a,b)`$-triple $`\{x,t,bx+2(tax)\}`$, a contradiction. (That $`bx+2(tax)M`$ follows easily from the definitions of $`z`$, $`s`$, and $`t`$, and the fact that $`x4`$.) $`\mathrm{}`$

For certain pairs $`(a,b)`$, we are able to improve the upper bounds of Theorem 2.1. The next theorem deals with the case in which $`a=b`$. Theorem 2.1 gives an upper bound for this case of $`O(a^4)`$. The following theorem improves this to $`O(a^2)`$.

Theorem 2.2: $`N(a,a;2)\{\begin{array}{cc}3a^2+a\hfill & \mathrm{for}\mathrm{\hspace{0.17em}\hspace{0.17em}4}a\mathrm{even}\hfill \\ 8a^2+a\hfill & \mathrm{for}a\mathrm{odd}\hfill \end{array}`$

Proof. We start with the case when $`a`$ is even. We may assume that $`a6`$ since $`N(4,4;2)=40`$ was obtained by computer search (for other exact values see Table 1 at the end of this section). We shall show that every red-blue coloring of $`S=[1,3a^2+a]`$ yields a monochromatic $`(a,a)`$-triple by considering all possible 2-colorings of the set $`\{1,a+1,(3/2)a^2+a,2a^2+a\}`$. Assume, by way of contradiction, that there is a 2-coloring $`\chi `$ of $`S`$ that yields no monochromatic $`(a,a)`$-triple.

Let $`R`$ be the set of red elements of $`S`$ under $`\chi `$, and $`B`$ the set of blue elements of $`S`$ under $`\chi `$. Without loss of generality we assume $`1R`$.

Case I: $`a+1,2a^2+aR`$.

We then have the following implications.

$`1,a+1Ra+2B`$ (by considering the triple with $`d=1`$).   
$`1,2a^2+aRa^2+aB`$ (taking $`d=a^2`$).   
$`a+1,2a^2+aR(3/2)a^2+aB`$.   
$`a+2,(3/2)a^2+aB(5/4)a^2+(3/2)aR`$.   
$`a^2+a,(3/2)a^2+aBa/2+1R`$.   
$`a+1,(5/4)a^2+(3/2)aR(3/2)a^2+2aB`$.   
$`a/2+1,(5/4)a^2+(3/2)aR2a^2+2aB`$.   
This gives a contradiction since $`\{a+2,(3/2)a^2+2a,2a^2+2a\}`$ is a monochromatic $`(a,a)`$-triple.

Case II: $`a+1,(3/2)a^2+aR`$ and $`2a^2+aB`$.

As in Case I, we must have $`a+2B`$. The following sequence of implications then leads to a contradiction.   
$`a+1,(3/2)a^2+aR(5/4)a^2+aB`$.   
$`a+2,2a^2+aB3a^2R`$.   
$`1,(3/2)a^2+aR3a^2+aB`$.   
$`a+2,3a^2+aB2a^2+(3/2)aR`$.   
$`3a^2,2a^2+(3/2)Ra+3B`$.   
$`a+2,(5/4)a^2+aB(3/2)a^2R`$.   
$`1,(3/2)a^2R3a^2aB.`$   
We now have a contradiction since $`\{a+3,2a^2+a,3a^2a\}`$ is a blue $`(a,a)`$-triple.

Case III: $`(3/2)a^2+a,2a^2+aB`$.

This implies $`a+1R`$, so that again we have $`a+2B`$. Then   
$`a+2,2a^2+aB(3/2)a^2+(3/2)aR`$ and $`3a^2R`$.   
$`a+1,(3/2)a^2+(3/2)aR2a^2+2aB`$ .   
$`a+2,(3/2)a^2+aB2a^2R`$.   
$`2a^2,3a^2RaB`$.   
Hence, the $`(a,a)`$-triple $`\{a,(3/2)a^2+a,2a^2+2a\}`$ is blue, again a contradiction.

Case IV: $`(3/2)a^2+a,2a^2+aR`$.

Using this assumption and the fact that $`1R`$, we have $`(3/4)a^2+aB`$, $`a^2+aB`$, and $`3a^2+aB`$. Then   
$`(3/4)a^2+a,a^2+aB(a/2)+1R`$.   
$`(a/2)+1,(3/2)a^2+aR(5/2)a^2+aB`$.   
$`3a^2+a,(5/2)a^2+aB2a+1R`$.

We now consider two subcases.

Subcase (i): $`2R`$.

Then $`2,(3/2)a^2+aR3a^2B`$.   
$`2,2a+1R2a+2B`$.   
Thus the $`(a,a)`$-triple $`\{2a+2,(5/2)a^2+a,3a^2\}`$ is monochromatic.

Subcase (ii): $`2B`$

$`2,(3/4)a^2+aB(3/2)a^2R`$.   
$`2,a^2+aB2a^2R`$.   
$`(3/2)a^2,a/2+1Ra^2+a/2B`$.   
$`(3/2)a^2,2a^2RaB`$.   
Thus the $`(a,a)`$-triple $`\{a,(3/2)a^2,2a^2\}`$ is monochromatic.

Case V: $`a+1`$, $`2a^2+aB`$.

In this case both $`(3/2)a^2+a`$ and $`3a^2+a`$ must be red, so that the $`(a,a)`$-triple $`\{1,(3/2)a^2+a,3a^2+a\}`$ is monochromatic.

Case VI: $`a+1`$, $`(3/2)a^2+aB`$.

This assumption implies that $`(5/4)a^2+a`$ and $`2a^2+a`$ are red. Then   
$`1,2a^2+aRa^2+aB`$.   
$`a^2+a,(3/2)a^2+aBa/2+1R`$.   
Thus the $`(a,a)`$-triple $`\{a/2+1,(5/4)a^2+a,2a^2+a\}`$ is monochromatic.

We now move onto the situation where $`a`$ is odd. We may assume that $`a5`$ since $`N(1,1;2)`$ is the van der Waerden number $`w(3;2)`$, which equals nine, and $`N(3,3;2)=39`$ (see Table 1). Our method is very similar to that of the even case. Here we 2-color $`T=[1,8a^2+a]`$ and consider the various ways in which the set $`\{4a+1,5a^2+a,8a^2+a\}`$ may be colored. The following six cases cover all possibilities.

Case I: $`4a+1,5a^2+aR`$.

In this case $`6a^2+aB`$ and, since $`1R`$, $`(5a+1)/2B`$.

We consider two subcases.

Subcase (i): $`2B`$.

Then $`2,(5a+1)/2B3a+1R`$.   
$`1,3a+1R5a+2B`$.   
$`5a+2,6a^2+aB7a^2R`$.   
$`1,7a^2R(7a^2+a)/2B`$.   
$`(5a+1)/2,(7a^2+a)/2B(9a^2+a)/2R`$.   
$`(9a^2+a)/2,5a^2+aR4aB`$.   
$`2,4aB6aR`$.   
$`6a,7a^2R8a^2B`$.   
$`6a^2+a,8a^2B4a+2R`$.   
$`4a,8a^2B6a^2R`$.   
This gives the monochromatic $`(a,a)`$-triple $`\{4a+2,5a^2+a,6a^2\}`$.

Subcase (ii): $`2R`$.

$`2,5a^2+aR(5a^2+3a)/2B`$.   
$`(5a+1)/2,(5a^2+3a)/2B(5a^2+5a)/2R`$.   
$`(5a^2+5a)/2,5a^2+aR4B`$.   
$`2,4a+1R6a+2B`$.   
$`(5a+1)/2,(5a^2+3)/2B(5a^2+5a)/2R`$.   
$`1,(5a^2+5a)/2R5a^2+4aB`$.   
$`2,(5a^2+5a)/2R5a^2+3aB`$.   
$`5a^2+3a,5a^2+4aB5a+2R`$.   
$`4,6a+2B8a+4R`$.   
Thus, $`\{2,5a+2,8a+4\}`$ is a monochromatic $`(a,a)`$-triple.

Case II: $`4a+1,8a^2+aR`$ and $`5a^2+aB`$.

By using an obvious “forcing” argument (as in the previous cases) on the following sequence of $`(a,a)`$-triples, it is a routine exercise to show that the $`(a,a)`$-triple $`\{1,3a,5a\}`$ must be red: $`\{1,(5a+1)/2,4a+1\}`$, $`\{1,4a^2+a,8a^2+a\}`$, $`\{4a+1,6a^2+a,8a^2+a\}`$, $`\{(5a+1)/2,4a^2+a,(11a^2+3a)/2\}`$, $`\{4a+1,(11a^2+3a)/2,7a^2+2a\}`$, $`\{3a,5a^2+a,7a^2+2a\}`$, $`\{5a,6a^2+a,7a^2+2a\}`$.

Case III: $`4a+1R`$ and $`5a^2+a,8a^2+aB`$.

For this case we may use the $`(a,a)`$-triples $`\{2a+1,5a^2+a,8a^2+a\}`$, $`\{1,2a+1,3a+2\}`$, $`\{3a+2,5a^2+a,7a^2\}`$, $`\{3a+2,(11a^2+3a)/2,8a^2+a\}`$, $`\{1,(7a^2+a)/2,7a^2\}`$, $`\{4a+1,(11a^2+3a)/2,7a^2+2a\}`$, $`\{2a,(7a^2+a)/2,5a^2+a\}`$, $`\{3a,5a^2+a,7a^2+2a\}`$ to prove that the $`(a,a)`$-triple $`\{1,2a,3a\}`$ must be red.

Case IV: $`5a^2+a,8a^2+aR`$.

By considering the triples $`\{1,4a^2+a,8a^2+a\}`$, $`\{2a+1,5a^2+a,8a^2+a\}`$, $`\{2a+1,3a^2+a,4a^2+a\}`$, and $`\{2a+1,4a^2+a,6a^2+a\}`$, we find that the $`(a,a)`$-triple $`\{1,3a^2+a,6a^2+a\}`$ must be red.

Case V: $`5a^2+aR`$ and $`4a+1,8a^2+aB`$.

In this case we have $`6a^2+aR`$ and hence $`3a^2+aB`$.

We now consider two subcases.

Subcase (i): $`2B`$.   
By examining the triples $`\{2,3a^2+a,6a^2\}`$, $`\{4a+2,5a^2+a,6a^2\}`$, $`\{6a1,6a^2,6a^2+a\}`$, $`\{6a1,7a^2,8a^2+a\}`$, $`\{2,3a+1,4a+2\}`$, $`\{3a+1,4a^2+a,5a^2+a\}`$, $`\{2,4a^2+a,8a^2\}`$, $`\{4a,6a^2,8a^2\}`$, $`\{6a,7a^2,8a^2\}`$, we find that the $`(a,a)`$-triple $`\{2,4a,6a\}`$ must be blue.

Subcase (ii): $`2R`$.   
By examining the triples $`\{2,(5a^2+3a)/2,5a^2+a\}`$, $`\{2a+2,(5a^2+3a)/2,3a^2+a\}`$, $`\{2,2a+2,2a+4\}`$, $`\{2,2a+1,2a+2\}`$, $`\{2a+2,(7a^2+3a)/2,5a^2+a\}`$, $`\{2a+4,(5a^2+5a)/2,3a^2+a\}`$, $`\{(3a+3)/2,(5a^2+3a)/2,(7a^2+3a)/2\}`$, $`\{2a+1,(5a^2+3a)/2,3a^2+2a\}`$, $`\{1,(5a^2+5a)/2,5a^2+4a\}`$, $`\{(3a+3)/2,3a^2+2a,(9a^2+5a)/2\}`$, we find that the $`(a,a)`$-triple $`\{4a+1,(9a^2+5a)/2,5a^2+4a\}`$ is blue.

Case VI: $`4a+1,5a^2+aB`$.

The sequence of triples $`\{4a+1,5a^2+a,6a^2+a\}`$, $`\{1,3a^2+a,6a^2+a\}`$, $`\{a+1,3a^2+a,5a^2+a\}`$, $`\{1,a+1,a+2\}`$, $`\{a+2,3a^2+a,5a^2\}`$, $`\{4a1,5a^2,6a^2+a\}`$, $`\{1,(5a^2+a)/2,5a^2\}`$, $`\{2a,(5a^2+a)/2,3a^2+a\}`$, $`\{a+2,(5a^2+a)/2,4a^2a\}`$, $`\{2a,4a^2a,6a^22a\}`$, $`\{1,4a^2a,8a^23a\}`$ leads us to conclude that the $`(a,a)`$-triple $`\{4a1,6a^22a,8a^23a\}`$ is blue. $`\mathrm{}`$

Another circumstance for which we can improve the upper bounds of Theorem 2.1 is the case in which $`b=2a1`$ (for $`a=1`$ this is the van der Waerden number $`w(3,2)`$). By Theorem 2.1, $`N(a,2a1;2)`$ is bounded above by a function having order of magnitude $`32a^4`$. We can improve this to $`16a^3`$ by making use of the following theorem which is taken from .

First, we introduce some notation. Let $`f:𝐍𝐑^+`$ be a non-decreasing function. Denote by $`w(f,k)`$ the least positive integer (if it exists) such that whenever $`[1,w(f,k)]`$ is 2-colored, there must exist a monochromatic $`k`$-term arithmetic progression $`\{a,a+d,a+2d,\mathrm{},a+(k1)d\}`$ with $`df(a)`$. In  it is shown that $`w(f,3)`$ always exists, and bounds for this function are given as follows.

Theorem 2.3: (Brown and Landman ) Let $`f:𝐍𝐑^+`$ be a non-decreasing function. Let $`b=1+4\frac{f(1)}{2}`$. Then

$$w(f,3)4f(b+4\frac{f(b)}{2})+14\frac{f(b)}{2}+7b/213/2.$$

Further, if $`f`$ maps into $`𝐍`$ with $`f(n)n`$ for all $`n𝐍`$, then $`w(f,3,2)8f(h)+2h+2c`$, where $`h=2f(1)+1`$ and $`c`$ is the largest integer such that $`f(c)+c4f(h)+h+1`$.

Relating Theorem 2.3 to $`(a,b)`$-triples, we have the following corollary.

Corollary 2.1: For all $`a2`$,

$$16a^212a+6N(a,2a1;2)\{\begin{array}{cc}16a^32a^2+4a3\hfill & \mathrm{for}a\mathrm{even}\hfill \\ 16a^3+14a^2+2a3\hfill & \mathrm{for}a\mathrm{odd}\hfill \end{array}$$

Proof. Note that $`\{x,y,z\}`$ is an $`(a,2a1)`$-triple if and only if it is an arithmetic progression with $`yx(a1)x+1`$. By applying Theorem 2.3 with $`f(x)=(a1)x+1`$ we obtain the desired bounds. $`\mathrm{}`$

We now present some lower bounds for all $`(a,b)`$-triples. This is done by providing $`2`$-colorings which avoid monochromatic $`(a,b)`$-triples.

Theorem 2.4: If $`b2a`$ then $`N(a,b;2)2b^2+5b(2a4)`$. If $`b<2a`$ then $`N(a,b;2)3b^2(2a5)b(2a4)`$.

Proof. For the case $`b2a`$, we will exhibit a $`2`$-coloring of $`[1,2b^2+5b2a+3]`$ with no monochromatic $`(a,b)`$-triple. Color $`[b+2,b^2+2b+1]`$ red and its complement blue. It is an easy exercise to show that monochromatic $`(a,b)`$-triples are avoided.

For the case where $`b<2a`$ the $`2`$-coloring of $`[1,3b^2(2a5)b(2a4)]`$ with $`[b+2,b^2+2b+1]`$ colored red and its complement colored blue is easily seen to avoid monochromatic $`(a,b)`$-triples. $`\mathrm{}`$

We are able to improve slightly the lower bound given in Theorem 2.5 for the case when $`a=1`$. In fact, from computer calculations (see Table 1 below), it appears that this inequality may in fact be an equality.

Theorem 2.5: $`N(1,b;2)2b^2+5b+6`$ for all $`b3`$.

Proof. Consider the following red-blue coloring of $`[1,2b^2+5b+5]`$: color $`[1,b+1]`$, $`\{b+3\}`$, and $`[b^2+2b+4,2b^2+5b+5]`$ red and the other integers blue. We now show that this coloring avoids monochromatic $`(1,b)`$-triples.

Assume $`\{x,y,z\}=\{x,x+d,bx+2d\}`$ is a blue $`(1,b)`$-triple. Since the largest blue element is $`b^2+2b+3`$, we must have $`x=b+2`$. Thus, since we must have $`d2`$, we see that $`z>b^2+2b+3`$, which is not possible.

Now assume $`\{x,y,z\}`$ is red. First, if $`x,x+d\{1,2,\mathrm{},b,b+1,b+3\}`$ then we have $`b+2bx+2db^2+b+4`$. Hence, the only possibility here is $`z=b+3`$, but $`bx+2d=b+3`$ has no solution in $`x`$ for $`b3`$. Second, if $`y[b^2+2b+4,2b^2+5b+5]`$ then $`bx+2dbx+2b^2+2b+2`$. Hence, we must have $`x\{1,2,3,4\}`$ ($`4`$ is possible if $`b=3`$). However, this gives $`bx+2dbx+2b^2+4b`$, which implies that $`x\{1,2\}`$ ($`2`$ is possible if $`b=3`$). This in turn implies that $`zbx+2b^2+2b+4`$ which gives $`x=1`$ as the only possibility. However with $`x=1`$ we must have $`z>2b^2+5b+5`$, which is out of bounds. $`\mathrm{}`$

Below we present a table of computer-generated values for $`N(a,b;2)`$ for small $`a`$ and $`b`$. We also include computer-generated lower bounds for those cases where the computer time became excessive (the program is available for download as the Fortran77 program VDW.f at http://math.colgate.edu/~aaron/).

$`𝐍(𝐚,𝐛;\mathrm{𝟐})`$ Values

| $`ab`$ | $`1`$ | $`2`$ | $`3`$ | $`4`$ | $`5`$ | $`6`$ | $`7`$ |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $`1`$ | 9 | dne | $`39`$ | $`58`$ | $`81`$ | $`108`$ | $`139`$ |
| $`2`$ |  | $`16`$ | $`46`$ | dne | $`139`$ | $`106`$ | $`133`$ |
| $`3`$ |  |  | $`39`$ | $`60`$ | $`114`$ | dne | $`135`$ |
| $`4`$ |  |  |  | $`40`$ | $`87`$ | $`124`$ | $`214`$ |
| $`5`$ |  |  |  |  | $`70`$ | $`100`$ | $`150`$ |
| $`6`$ |  |  |  |  |  | $`78`$ | $`105`$ |
| $`7`$ |  |  |  |  |  |  | $`95`$ |

Table 1

3. The Degree of Regularity of $`(𝐚,𝐛)`$

In this section we consider $`N(a,b;r)`$ for general $`r`$. We begin by showing, in Theorems 3.1 and 3.2, that for many choices of $`a`$ and $`b`$, the pair $`(a,b)`$ is not regular. For such pairs we find an upper bound on $`dor(a,b)`$.

Theorem 3.1: Let $`1a<b`$, and assume that $`b(2^{3/2}1)a+22^{3/2}`$. Let $`c=b/a`$. Then $`dor(a,b)log_\sqrt{2}c`$.

Proof. Let $`r=\mathrm{log}_\sqrt{2}c+1`$. We will give an $`r`$-coloring of the natural numbers which contains no monochromatic $`(a,b)`$-triple. For readability, let $`p=\sqrt{2}`$. Using the colors $`0,1,\mathrm{},r1`$, define the coloring $`\chi `$ by letting $`\chi (x)i`$ (mod $`r`$), where $`p^ix<p^{i+1}`$.

Assume that there exists an $`(a,b)`$-triple, say $`x<y<z`$, that is monochromatic under $`\chi `$. Let $`j`$ be the integer such that $`p^jy<p^{j+1}`$. Since $`\{x,y,z\}`$ is an $`(a,b)`$-triple, $`y=ax+d`$ and $`z=bx+2d`$ for some $`d`$. Thus $`zcy<p^{r1}p^{j+1}=p^{j+r}`$. Hence, by the way $`\chi `$ is defined and the fact that $`\chi (y)=\chi (z)`$, we must have $`p^jy<z<p^{j+1}`$.

We now consider two cases.

Case I: $`b2a1`$.

In this case, $`yx=(a1)x+d(ba)x+d=zy<p^j(p1)p^j(11/p^{r1})`$. Hence, since $`y>p^j`$, we have that $`xp^jp^j(11/p^{r1})=p^{jr+1}`$. Since $`\chi (x)=\chi (y)`$, and by the definition of $`\chi `$, we must have $`p^jx<y<p^{j+1}`$. Thus we have that all three numbers $`x,y,z`$ belong to the interval $`[p^j,p^{j+1})`$. Hence, $`zx=(b1)x+2d<p^j(p1)x(p1)`$, a contradiction (since $`b1>p1`$).

Case II: $`c=2`$ and $`b(2^{3/2}1)a+22^{3/2}`$.

In this case, $`2(a1)(ba)/(p1)`$, so that $`(a1)x/(ba)x1/(2p2)`$. Therefore, $`((a1)x+d)/((ba)x+d)1/(2p2)`$. Hence, $`yx(zy)/(2p2)<(p1)p^j/(2p2)=p^j/2=p^{j2}`$. So, $`xp^jp^{j2}=p^{j2}`$. Since $`r=3`$ in this case, and $`\chi (x)=\chi (y)`$, we must have $`p^jx<p^{j+1}`$. Thus, as in Case I, $`x`$ and $`z`$ both belong to the interval $`[p^j,p^{j+1})`$, and we again have a contradiction. $`\mathrm{}`$

In the following theorem we give an upper bound on $`dor(a,b)`$ for several pairs $`(a,b)`$ that are either not covered by Theorem 3.1 or for which we are able to improve the bound of Theorem 3.1.

Theorem 3.2: $`dor(1,3)3`$, $`dor(2,2)5`$, $`dor(2,5)3`$, $`dor(2,6)3`$, $`dor(3,3)5`$, $`dor(3,4)5`$, $`dor(3,8)3`$, and $`dor(3,9)3`$.

Proof. We give the proof for the pair $`(2,2)`$, and outline the proofs for the other cases, which are quite similar.

To show that $`dor(2,2)5`$, we provide a 6-coloring of the positive integers that avoids monochromatic $`(2,2)`$-triples. Let

$$\chi (i)=\{\begin{array}{cc}2k(\mathrm{mod}\mathrm{\hspace{0.17em}\hspace{0.17em}6})\hfill & \mathrm{if}i[2^k,p2^k)\hfill \\ 2k+1(\mathrm{mod}\mathrm{\hspace{0.17em}\hspace{0.17em}6})\hfill & \mathrm{if}i[p2^k,2^{k+1})\hfill \end{array}$$

where $`p=\sqrt{2}`$ . Assume $`\{x,2x+d,2x+2d\}`$ is a (2,2)-triple such that $`\chi (x)=\chi (2x+d)`$. We will show that $`\chi (2x+2d)\chi (x)`$. We consider two cases.

Case I: $`2^kx<p2^k`$ for some $`k\{0,1,2,\mathrm{}\}`$.

Since $`\chi (x)=\chi (2x+d)`$ and $`2x+d>p2^k`$, there exists an $`m𝐍`$ such that $`2x+d[2^{k+3m},p2^{k+3m})`$. Hence $`d[2^{k+3m}p2^{k+1},p2^{k+3m}2^{k+1}]`$. This yields

$$2x+2d2^{k+3m}+2^{k+3m}p2^{k+1}p2^{k+3m},$$
(3)   
and

$$2x+2d<p2^{k+3m+1}2^{k+1}<2^{k+3(m+1)}.$$
(4)   
By (3) and (4) it follows that $`\chi (2x+2d)\chi (x)`$.

Case II: $`p2^kx<2^{k+1}`$ for some $`k\{0,1,2,\mathrm{}\}`$.

As in Case I, there must exist an $`m\{1,2,\mathrm{}\}`$ such that $`2x+d[p2^{k+3m},2^{k+3m+1})`$. Thus, $`d[p2^{k+3m}2^{k+2}1,2^{k+3m+1}p2^{k+1}]`$. Therefore

$$2x+2d2^{k+3m+1}(p2^{13m}2^{k3m})2^{k+3m+1},$$
(5)   
and

$$2x+2d<2^{k+3m+2}p2^{k+1}<2^{k+3(m+1)}.$$
(6)   
It follows from (5) and (6) that $`\chi (2x+2d)\chi (x)`$.

The proofs that $`dor(3,3)5`$ and $`dor(3,4)5`$ may be done in the same way as that for $`dor(2,2)`$ except that we use $`p=\sqrt{3}`$ instead of $`p=\sqrt{2}`$ and we use powers of $`3`$ instead of $`2`$ in the defined intervals.

The cases of $`(2,5)`$, $`(2,6)`$, $`(3,8)`$, and $`(3,9)`$ are done similarly, where we use a 4-coloring rather than a 6-coloring, which is defined the same as $`\chi `$ except that “mod 6” is replaced by “mod 4;” where we take $`p`$ to be $`1.6`$, $`1.5`$, $`1.9`$, and $`1.9`$, respectively; and where the powers in the defined intervals are powers of the given value of $`a`$. The case $`(1,3)`$ is done using a “mod 4” coloring with $`p=\sqrt{3}`$, where the powers in the given intervals of the coloring are powers of $`3`$. $`\mathrm{}`$

By using Theorems 2.4 and 2.5, we are able to obtain the following lower bounds for $`N(a,b;r)`$.

Proposition 3.1: If $`b2a`$ then $`N(a,b;r)2b^r+5b^{r1}(2a4)b^{r2}+_{i=0}^{r3}b^i`$ for $`r2`$. If $`b<2a`$ then $`N(a,b;r)3b^r(2a5)b^{r1}(2a4)b^{r2}+2_{i=0}^{r3}b^i`$ for $`r2`$.

Proof. We induct on $`r`$. The case $`b2a`$ and $`r=2`$ is proved in Theorem 2.4. Assuming $`r3`$ and that the result holds for $`r1`$ with $`b2a`$, there exists an $`(r1)`$-coloring of $`[1,2b^{r1}+5b^{r2}(2a4)b^{r3}+2_{i=0}^{r4}b^i1]`$ with no monochromatic triple. Color the interval $`[2b^{r1}+5b^{r2}(2a4)b^{r3}+2_{i=0}^{r4}b^i,2b^r+5b^{r1}(2a4)b^{r2}+2_{i=0}^{r3}b^i1]`$ with the remaining color. By construction this $`r`$-coloring avoids monochromatic triples.

The case $`b<2a`$ is quite similar and will be omitted. $`\mathrm{}`$

Proposition 3.2: $`N(1,b;r)2b^r+5b^{r1}+6b^{r2}+2_{i=0}^{r3}b^i`$ for all $`b,r2`$.

Proof. We induct on $`r`$. The case $`r=2`$ is proved in Theorem 2.5. Assuming $`r3`$ and that the inequality is true for $`r1`$, we have the existence of an $`(r1)`$-coloring of $`[1,2b^{r1}+5b^{r2}+6b^{r3}+2_{i=0}^{r4}b^i1]`$ which does not contain a monochromatic $`(1,b)`$-triple. Color the interval $`[2b^{r1}+5b^{r2}+6b^{r3}+2_{i=0}^{r4}b^i,2b^r+5b^{r1}+6b^{r2}+2_{i=0}^{r3}b^i1]`$ with the remaining color. It is an easy exercise to show that there is no monochromatic $`(1,b)`$-triple in this $`r`$-coloring. $`\mathrm{}`$

We conclude this section with a table which describes what is known about $`dor(a,b)`$ for some small values of $`a`$ and $`b`$. By Theorem 2.1, we know that if $`b2a`$, then $`dor(a,b)2`$. In the third column of the table below we give the reason for the given upper bound on $`dor(a,b)`$.

Values of $`\mathrm{𝐝𝐨𝐫}(𝐚,𝐛)`$

| $`(a,b)`$ | $`dor(a,b)`$ | reason |
| --- | --- | --- |
| (1,1) | $`\mathrm{}`$ | van der Waerden’s Theorem |
| (1,2) | $`1`$ | Theorem 2.1 |
| (1,3) | $`23`$ | Theorem 3.2 |
| (1,4) | $`24`$ | Theorem 3.1 |
| (1,5) | $`25`$ | Theorem 3.1 |
| (1,6) | $`26`$ | Theorem 3.1 |
| (1,7) | $`26`$ | Theorem 3.1 |
| (1,8) | $`26`$ | Theorem 3.1 |
| (1,9) | $`27`$ | Theorem 3.1 |
| (2,2) | $`25`$ | Theorem 3.2 |
| (2,3) | $`2`$ | Theorem 3.1 |
| (2,4) | $`1`$ | Theorem 2.1 |
| (2,5) | $`23`$ | Theorem 3.2 |
| (2,6) | $`23`$ | Theorem 3.2 |
| (2,7) | $`24`$ | Theorem 3.1 |
| (2,8) | $`24`$ | Theorem 3.1 |
| (2,9) | $`25`$ | Theorem 3.1 |
| (3,3) | $`25`$ | Theorem 3.2 |
| (3,4) | $`25`$ | Theorem 3.2 |
| (3,5) | $`2`$ | Theorem 3.1 |
| (3,6) | $`1`$ | Theorem 2.1 |
| (3,7) | $`24`$ | Theorem 3.1 |
| (3,8) | $`23`$ | Theorem 3.2 |
| (3,9) | $`23`$ | Theorem 3.2 |

Table 2

4. A More General Question

In this section we move from $`(a,b)`$-triples to sets of the form $`\{x,ax+d,ax+2d,\mathrm{},ax+(k1)d\}`$ for $`a1`$ and $`k3`$. Let us call such a set a $`k`$-term $`a`$-progression. For $`a=1`$ these are simply the $`k`$-term arithmetic progressions. Van der Waerden’s theorem states that given $`r1`$, any $`r`$-coloring of the natural numbers must contain arbitrarily long monochromatic arithmetic progressions. Theorem 4.1 shows that a similar result does not hold for $`a>1`$ and $`r>3`$. Denote by $`dor_k(a)`$ the largest number of colors with which we can arbitrarily color N and be guaranteed the existence of a monochromatic $`k`$-term $`a`$-progression. Theorem 4.1 shows that for $`k`$ large enough, $`dor_k(a)3`$.

Theorem 4.1: For all $`a2`$ and all integers $`k\frac{a^2}{a+1}+2`$, $`dor_k(a)3`$.

Proof. It suffices to exhibit a $`4`$-coloring of $`𝐍`$ which avoids monochromatic $`k`$-term $`a`$-progressions. Clearly, we may assume $`k=\frac{a^2}{a+1}+2`$.

Define a $`4`$-coloring of $`𝐍`$ by coloring each interval $`[a^j,a^{j+1})`$ with the color $`j`$ (mod $`4`$). We will show that there is no monochromatic $`k`$-term $`a`$-progression by showing that if $`x`$ and $`ax+d`$ are the same color, then $`ax+(k1)d`$ is a different color.

Let $`x[a^i,a^{i+1})`$, and assume $`ax+d`$ has the same color as $`x`$. Then clearly $`ax+d[a^i,a^{i+1})`$. Hence, there exists an $`m𝐍`$ such that $`ax+d[a^{i+4m},a^{i+4m+1})`$. From this we conclude that

$$a^i(a^{4m}a^2)da^{i+1}(a^{4m}1).$$

To complete the proof we will show that

$$ax+(k1)d<a^{i+4(m+1)}$$
(7)   
and

$$a^{i+4m+1}ax+(k1)d.$$
(8)   
From (7) and (8) we can conclude that $`ax+(k1)d`$ is colored differently than $`x`$ and $`ax+d`$.

To prove (7), note that $`k<a^3+1`$ for all $`a2`$. Thus

$$1+(k2)(1a^{4m})<a^3,$$

and hence

$$a^{i+4m+1}+(k2)a^{i+1}(a^{4m}1)<a^{i+4(m+1)}.$$

This last inequality, together with the fact that

$$ax+(k1)d=ax+d+(k2)da^{i+4m+1}+(k2)a^{i+1}(a^{4m}1),$$

implies (7).

To prove (8), first note that since $`ka^2/(a+1)+2`$, we have $`(k2)(a^21)a^3a^2`$. Hence

$$a^{i+4m}+(k2)a^i(a^{4m}a^2)a^{i+4m+1}.$$

This last inequality, along with the fact that

$$ax+(k1)da^{i+4m}+(k2)a^i(a^{4m}a^2),$$

shows that (8) holds. $`\mathrm{}`$

According to Theorem 4.1, it is not true that every 4-coloring of $`𝐍`$ yields arbitrarily long monochromatic $`a`$-progressions. We are not sure if this holds for two or three colors. However, if for $`r=2`$ or $`r=3`$, every $`r`$-coloring of $`𝐍`$ does yield arbitrarily long monochromatic $`a`$-progressions, then a somewhat stronger result holds, as stated in Proposition 4.1 below. We omit the proof, a trivial generalization of the proof of \[3, Theorem 2, p. 70\].

Proposition 4.1 Let $`a𝐍`$ and let $`r\{2,3\}`$. If for every $`r`$-coloring of $`𝐍`$ there are arbitrarily long monochromatic $`a`$-progressions, then for all $`s1`$ there exists $`n=n(a,r,s)`$ such that if $`[1,n]`$ is $`r`$-colored then for all $`k𝐍`$ there exists $`\widehat{x},\widehat{d}`$ so that $`\{\widehat{x},a\widehat{x}+\widehat{d},a\widehat{x}+2\widehat{d},\mathrm{},a\widehat{x}+k\widehat{d}\}\{s\widehat{d}\}`$ is monochromatic.

5. Some Concluding Remarks

Although we have not proved that $`dor(a,b)<\mathrm{}`$ for general $`a`$ and $`b`$, the evidence in this paper leads us to believe that this is the case for all $`(a,b)(1,1)`$. In particular, we make the following conjecture:

Conjecture: Let $`a>1`$ and $`r>3`$. Define $`K(a,r)`$ to be the least positive integer such that $`dor_K(a)r`$. Then there exists an $`s>r`$ such that $`K(a,s)<K(a,r)`$.

By Theorem 4.1, we know that $`K(a,r)`$ exists. Clearly, $`K(a,s)K(a,r)`$ for $`sr`$, but if we are able to show that the inequality is strict for some $`s`$, then we can conclude that $`dor(a,a)<\mathrm{}`$ for all $`a>1`$. In fact it may be true that $`dor(a,b)=2`$ for all $`b2a`$, although we have presented scant evidence for this.

References

 T.C. Brown and B. Landman, Monochromatic arithmetic progressions with large differences, Bull. Australian Math. Soc. 60 (1999), 21-35.

 T.C. Brown, B. Landman, M. Mishna, Monochromatic homothetic copies of $`\{1,1+s,1+s+t\}`$, Canadian Math. Bull. 40 (1997), 149-157.

 R.L. Graham, B.L. Rothschild, J.H. Spencer, Ramsey Theory, Second Ed., John Wiley and Sons, New York, 1990.

 B. Landman, Avoiding arithmetic progressions (mod $`m`$) and arithmetic progressions, Utilitas Math. 52 (1997), 173-182.

 B. Landman, Ramsey functions for quasi-progressions, Graphs and Combinatorics 14 (1998), 131-142.

 B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wisk. 15 (1927), 212-216.