%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-17/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}[section]
\newtheorem{corl}{Corollary}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{lmma}{Lemma}[section]
\newtheorem*{conj}{Conjecture}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newtheorem*{rmrk}{Remark}
\newtheorem*{rmrks}{Remarks}

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

\title{On the Set of Common Differences in van der Waerden's Theorem on Arithmetic Progressions}
\author{Tom C. Brown, Ronald L. Graham and Bruce M. Landman}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown, R.L. Graham, and B.M. Landman, \emph{On the set of common
  differences in van der Waerden's theorem on arithmetic progressions}, Canad.
  Math. Bull. \textbf{42} (1999), 25--36.}\bigskip\end{center}

\begin{abstract}Analogues of van der Waerden's theorem on arithmetic progressions are
considered where the family of all arithmetic progressions, AP, is replaced by
some subfamily of AP. Specifically, we want to know for which sets $A$, of
positive integers, the following statement holds: for all positive integers $r$
and $k$, there exists a positive integer $n = w'(k,r)$ such that for every $r$-coloring
for of $[1,n]$ there exists a monochromatic $k$-term arithmetic progression whose
common difference belongs to $A$. We will call any subset of the positive
integers that has the above property \emph{large}. A set having this property
for a specific fixed $r$ will be called \emph{$r$-large}. We give some necessary
conditions for a set to be large, including the fact that every large set must
contain an infinite number of multiples of each positive integer. Also, no
large set $\{a_n:n = 1,2,\ldots\}$ can have $\liminf_{n\to\infty} \frac{a_{n+1}}{a_n}
> 1$.

Sufficient conditions for a set to be large are also given. We show that any set
containing $n$-cubes for arbitrarily large $n$, is a large set. Results involving
the connection between the notions of ``large'' and ``2-large'' are given. Several
open questions and a conjecture are presented.
\end{abstract}

\section{Introduction\label{s1}}

An arithmetic progression of length $k$ is a set $P = \{x+id:i=0,\ldots,k-1\}$
where $x$ and $d$ are integers, $d>0$. We call $d$ the \emph{common difference}
of $P$. Van der Waerden's classic theorem on arithmetic progressions
\cite{vanderwaerden1927} says that, for each positive integer $r$, if the set
of positive integers, $\mathbb{Z}^+$, is partitioned into $r$ classes, then at
least one of the classes will contain arbitrarily long arithmetic progressions.
An alternate (and equivalent) form of van der Waerden's theorem says that for
all positive integers $k$ and $r$, there exists a least positive integer $w(k,r)$
such that for every partition of the interval $\intv{w(k,r)} = \{1,2,\ldots,
w(k,r)\}$ into $r$ classes, at least one of the classes will contain a $k$-term
arithmetic progression. A partition of a set into $r$ classes is often referred
to as an \emph{$r$-coloring} of the set. So van der Waerden's theorem can be
stated: for all positive integers $r$ and $k$, there exists a positive integer
$w(k,r)$ so that for every $r$-coloring of $\intv{w(k,r)}$ there exists a
monochromatic $k$-term arithmetic progression.

Analogues of van der Waerden's theorem may be considered, where the family of
arithmetic progressions, AP, is replaced by some other family of integer
sequences. That is, if $r$ is a positive integer and $T$ is a family of integer
sequences, we can ask whether for every $r$-coloring of the positive integers
there are arbitrarily long monochromatic members of $T$. If $T$ is a family
that does have this property, we say that $T$ has the \emph{$r$-Ramsey property}.
If $T$ has the $r$-Ramsey property for all $r$, we simply say that $T$ has
the \emph{Ramsey property}.

By van der Waerden's theorem, if $T$ includes all the arithmetic progressions,
then $T$ has the Ramsey property. The Ramsey functions associated with $T$
(i.e., the functions $w'(k,r)$ analogous to $w(k,r)$, but where members of
$T$ are sought rather than members of AP) have been studied for a variety of
such $T$ (see \cite{brown+erdos+freedman1990,greenwell+landman1989,landman1998}).

In this paper, we wish to consider the Ramsey property for collections $T$
that are not supersets of AP, but rather \emph{subsets} of AP. This is of
interest because if $T$ is a proper subset of AP, and $T$ has the Ramsey
property, the conclusion to van der Waerden's theorem is strengthened.

Of course, if $T\subseteq$ AP is too small, it will not have the Ramsey
property. For example, it is well known that if $F$ is any finite set of
positive integers, then it is possible to 2-color the positive integers
in such a way that there do not exist arbitrarily long arithmetic
progressions with common differences belonging to $F$ (one proof can be
found in \cite{bergelson+liebman1996}; this fact is also a consequence
of Theorem \ref{t21} below.)

On the other hand, one simple consequence (and strengthening) of van der
Waerden's theorem is that if $F$ is a fixed finite set of positive integers,
then the family of all arithmetic progressions having common differences
in $\mathbb{Z}^+\setminus F$ has the Ramsey property. In fact, it is easy
to see that if $m$ is a fixed positive integer, then the family of all
arithmetic progressions having common difference in the set $m\mathbb{Z}^+$
has the Ramsey property (by van der Waerden's theorem, every $r$-coloring
of $\{m,2m,\ldots,(w(k,r))m\}$ produces a $k$-term monochromatic arithmetic
progression, and this progression has common difference in $m\mathbb{Z}^+$.)

The examples just mentioned lead us to ask the general question: which
subcollections of AP have the Ramsey property?

For this paper, we consider those subcollections of AP which consist of all
arithmetic progressions having common differences in a given set $A$.

In this paper, we will call a subset $A$ of the positive integers \emph{large}
if the collection $T$, consisting of all arithmetic progressions having
common differences in $A$, has the Ramsey property. A subset of the positive
integers that is not large is called \emph{small}. Similarly, if $T$ has the
$r$-Ramsey property, we will say that $A$ is \emph{$r$-large}. Thus we seek
an answer to the question: which sets of positive integers are large?

Furstenberg, using dynamical systems methods, showed in \cite{furstenberg1981-1}
that every infinite cube (see definition below) is large.

\begin{defn}Let $\{a_1,a_2,\ldots,a_n\}$ be any set of positive integers. The
\emph{$n$-cube} $Q(a_1,\ldots,a_n)$ is the set of all linear combinations $c_1a_1
+ \cdots + c_na_n$ such that $c_i\in \{0,1\}$ for all $i$, but where not all
the $c_i$ are 0. Similarly, the \emph{infinite cube} $Q(a_1,a_2,\ldots)$
consists of all finite linear combinations of $a_1,a_2,\ldots$, with coefficients
in $\{0,1\}$, except for 0. (Note: in the literature, an ``$n$-cube'' often
refers to any translate of our $Q(a_1,\ldots,a_n)$; also, 0 is often included
the definition, and then our $Q(a_1,\ldots,a_n)$ is called a ``punctured
$n$-cube'').\end{defn}

More recently Bergelson and Liebman \cite[Corollary 1.9]{bergelson+liebman1996}
showed, using measure-preserving systems methods and ergodic theory, that if
$C$ is any infinite cube, and $p(x)$ is any polynomial with integer coefficients,
positive leading coefficient, and $p(0)=0$, then $\{p(x):x\in C\}\cap\mathbb{Z}^+$
is large (in particular, $\{p(x):x\geq1\}\cap\mathbb{Z}^+$ is large). In fact,
they showed that if $S$ is any subset of $\mathbb{Z}^+$ with positive upper
density, then $S$ contains arbitrarily long arithmetic progressions with common
differences of the form $p(x)$, $x\in C$.

For an excellent exposition of some of these results and methods, see
\cite{bergelson1996} and \cite{furstenberg1996}.

Here we give some results on large sets using completely elementary methods.
In particular, we strengthen Furstenberg's result mentioned above by showing
(Theorem \ref{t32} below) that if the set $A$ contains an $n$-cube for
arbitrarily large $n$, then $A$ is large. Our Corollary \ref{c21} and
Theorem \ref{t24} below are similar to results of Furstenberg \cite[Theorem
3.2 and Lemma 3.3]{furstenberg1981-2} which deal with recurrence in
measure-preserving systems.


\section{Necessary Conditions\label{s2}}

We begin with some conditions that are necessary for a set to be large. Of
course any condition that is necessary for 2-large sets is also necessary
for large sets.

For convenience, we will often use the term ``$d$-a.p.'' to refer to an
arithmetic progression whose common difference is $d$. Further, if $A$ is
a set of positive integers and if $P$ is a $d$-a.p., where $d\in A$, we
say that $P$ is an ``$A$-a.p.''

\begin{thrm}\label{t21} If $A$ is 2-large, then for each positive integer
$m$, $A$ contains an infinite number of multiples of $m$.\end{thrm}
\begin{proof} It suffices to show that for every positive integer $m$, $A$
contains some multiple of $m$. By way of contradiction, assume $A$ contains
no multiples of the positive integer $n$. Color the positive integers with
the coloring $\chi$ represented by the sequence $11\ldots1~00\ldots0~11\ldots
1~00\ldots0~\ldots$, where each block of 0's or 1's has length $n$.

Let $d\in A$ and $X=\{x_1,\ldots,x_{n+1}\}$ be a $d$-a.p. Since $d\equiv i
\Mod{2n}$ for some $1\leq i\leq 2n-1$, we see that $X$ must contain some
element, $a$, of the form $2k_1n + j_1$, $1\leq j_1\leq n$, as well as
some element $b$, of the form $2k_2n+j_2$, $n+1\leq j_2\leq 2n$. then
$\chi(a)\neq\chi(b)$, so $X$ is not monochromatic. Hence under $\chi$ there
do not exist monochromatic $(n+1)$-term arithmetic progressions having
common difference in $A$. Hence $A$ is not 2-large.\end{proof}

Before stating the next theorem we adopt some notation and terminology. If
$I$ and $J$ are intervals of the same size having opposite color patterns
(i.e., whenever $x$ is in position $i$ of $I$, and $y$ is in position $i$
of $J$, then $\chi(x)\neq\chi(y)$), then if $C$ is a string of 0's and 1's
representing the color pattern of $I$, we say that $J$ has color pattern
$\bar{C}$. Also, if $\chi$ is a 2-coloring and $I$ and $J$ are intervals
of the same size with color patterns $C$ and $D$, respectively, such that
either $C = D$ or $C = \bar{D}$, then we say that $I$ and $J$ \emph{imitate}
each other under $\chi$.

\begin{thrm}\label{t22} Let $A=\{a_k\}_{k=1}^\infty$ be a sequence of
positive integers where either
\begin{equation} a_k\geq3a_{k-1}\text{ for }k\geq2 \label{eq1}\end{equation}
or
\begin{equation} a_1 = 1,~~a_2 = 2,\text{ and } a_k\geq3a_{k-1}\text{ when }k\geq3.\label{eq2}\end{equation}

Then $A$ is not 2-large.\end{thrm}

\begin{proof} We will prove that $\{a_k\}_{k=1}^\infty$ is not 2-large whenever
\begin{equation} a_1 = 1,~~a_2\geq2,\text{ and } a_k\geq3a_{k-1}\text{ when }k\geq3.\label{eq3}\end{equation}
This is sufficient for the theorem since \eqref{eq2} is a special case
of \eqref{eq3}, and any $A$ satisfying \eqref{eq1} is a subset of some
$A'$ satisfying \eqref{eq3}.

Let $A=\{a_k\}$ satisfy \eqref{eq3}. Then for each $k\geq3$, $a_k$ can be
expressed uniquely in the form
\begin{equation} a_k = \sum_{j=1}^{k-1}c_j^{(k)}a_j, \label{eq4}\end{equation}
where the $c_j^{(k)}$ are defined recursively as follows: (i) $c_{k-1}^{(k)}$
is the largest positive integer such that $a_k\geq (c_{k-1}^{(k)} + 1)a_{k-1}$;
(ii) if $k\geq4$, then for each $j=2,\ldots,k-2$, once $c_{k-1}^{(k)},
c_{k-2}^{(k)},\ldots,c_{j+1}^{(k)}$ have been defined, define $c_j^{(k)}$ to
be the largest integer such that
\[ a_k \geq \left(\sum_{i=j+1}^{k-1}c_i^{(k)}a_i\right) + (c_j^{(k)}+1)a_j; \]
(iii) finally, $c_1^{(k)}$ is defined so that $a_k=\sum_{i=1}^{k-1} c_i^{(k)}
a_i$. For $k=2$, set $c_1^{(k)} = c_1^{(2)} = a_2$. It then follows from
\eqref{eq3} that $c_i^{(k)}\geq2$ for all $k\geq2$ and all $1\leq i\leq k-1$.
Thus, for each $k\geq2$, we can partition $\intv{a_k}$ into subintervals:
\[ B^{(k)}(k-1,1)\ldots B^{(k)}(k-1, c_{k-1}^{(k)})B^{(k)}(k-2,1)\ldots
B^{(k)}(k-2,c_{k-2}^{(k)})\ldots \]
\[ \ldots B^{(k)}(1,1)\ldots B^{(k)}(1,c_1^{(k)}), \]
where $|B^{(k)}(i,j)| = a_i$ for $1\leq i\leq k-1$, $1\leq j\leq c_i^{(k)}$,
and where the subintervals are listed such that each subinterval $B$ precedes
subinterval $B'$ when the members of $B$ are less than the members of $B'$.

Let $\chi$ be the 2-coloring of the positive integers defined by: (i) $\chi(1)
= 1$; (ii) once $\intv{a_1},\ldots,\intv{a_{k-1}}$ have been colored, color
$\intv{a_k}$ by coloring the $B^{(k)}(i,j)$ as follows:
\[ \chi(B^{(k)}(i,j)) = \left\{\begin{array}{cl} C_i&\text{if $j$ is odd}\\\bar{C}_i&\text{if $j$ is even}\end{array}\right. \]
where $C_i$ denotes the color pattern for $\intv{a_i}$.

We show that under $\chi$ there is no 5-term monochromatic $a_m$-a.p. for
any $m$. Let $m>0$ be fixed and let $\{x_1,\ldots,x_5\}$ be a 5-term
$a_m$-a.p. Let $k$ be the smallest positive integer such that $k>m$ and
$x_1\in\intv{a_k}$. We consider three cases.

\paragraph{Case 1.} $x_1\in B^{(k)}(i,j)$ where $1\leq i\leq m-1$ and
$1\leq j\leq c_i^{(k)}$. Let
\[ S = \bigcup\{B^{(k)}(i,j):1\leq i\leq m-1, 1\leq j\leq c_i^{(k)}\}. \]
Then $|S| = \sum_{i=1}^{m-1}c_i^{(k)}a_i$. By the way $c_m^{(k)}$ is defined,
we have
\[ a_k \leq \left(\sum_{i=m+1}^{k-1} c_i^{(k)}a_k\right) + (c_m^{(k)}+2)a_m. \]
Hence, using \eqref{eq4}, $2a_m\geq|S|$. Therefore $x_3\notin S$.

We consider two subcases. In case $x_2\in S$, then $x_3$ and $x_4$ both
belong to $[a_k+1,a_k+2a_m]$. Hence, by the definition of $k$ it follows
that $x_3$ and $x_4$ both belong to an interval that imitates $B^{(m+1)}(m,1)
\cup B^{(m+1)}(m,2)$. Then from the definition of $\chi$, $\chi(x_3)\neq
\chi(x_4)$. In case $x_2\notin S$, then by the same reasoning we have that
$\chi(x_2)\neq\chi(x_3)$. Thus, in either subcase, $\{x_1,x_2,x_3,x_4\}$
is not a 4-term monochromatic $a_m$-a.p.

\paragraph{Case 2.} $x_1\in B^{(k)}(m,j)$ for some $j$, $1\leq j\leq c_m^{(k)}$.
Now $a_m\leq a_k - \sum_{i=m}^{k-1} c_i^{(k)}$, so that $_m\leq |S|$. Therefore
$x_2\in S$, so by Case 1 $\{x_2,x_3,x_4,x_5\}$ cannot be monochromatic.

\paragraph{Case 3.} $x_1\in B^{(k)}(i,j)$ where $m+1\leq i\leq k-1$ and
$1\leq j\leq c_i^{(k)}$. The block $B^{(k)}(i,j)$ imitates $\intv{a_i}$
under $\chi$; i.e., it imitates
\[ B^{(i)}(i-1,1)\ldots B^{(i)}(i-1,c_{i-1}^{(i)})~~~B^{(i)}(i-2,1)\ldots B^{(i)}(i-2,c_{i-2}^{(i)})\ldots \]
\[ \ldots B^{(i)}(1,1)\ldots B^{(i)}(1,c_1^{(i)}). \]

Hence by Cases 1 and 2 we may assume $x_1$ belongs to a sub-block of $B^{(k)}(i,j)$
that imitates $B^{(i)}(r,j)$ where $m<r\leq i-1$. If $r>m+1$, then we can repeat
this argument, so that by a simple induction proof we may assume that $x_1$
belongs to a block $B^*$ that imitates $\intv{a_{m+1}}$ under $\chi$. This means
that we can assume $k=m+1$, and we're done by Case 1 and Case 2.

We have shown that in all cases, there is no 5-term monochromatic $a_m$-a.p. for
any $m$, so that $A$ is not 2-large.
\end{proof}

The next theorem shows that we can weaken the hypothesis of Theorem \ref{t22}
from $a_i\geq3a_{i-1}$ to $a_i\geq2a_{i-1}$, if we make the additional
assumption that $a_{i-1}$ divides $a_i$ for all $i$.

\begin{thrm}\label{t23} If $A=\{a_i\}_{i=1}^\infty$ is an increasing sequence
of positive integers where $a_i$ divides $a_{i+1}$ for all $i$, then $A$ is
not 2-large.\end{thrm}
\begin{proof} Define a 2-coloring $\chi$ on the set of positive integers recursively,
as follows. First let $\chi(x) = 1$ for all $x\in\intv{a_1}$. Once $\chi$ has been
defined on $\intv{a_i}$, we define $\chi$ on $\intv{a_{i+1}}$ by $\chi(x)\neq\chi
(x-a_i)$ for each $x\in[a_i+1,a_{i+1}]$.

First note that, from the way $\chi$ is defined on $[a_i+1,a_{i+1}]$, for each
$i\geq1$ there is no 2-term monochromatic $a_i$-a.p. contained in $\intv{a_{i+1}}$.

Now assume $j>i+1$ and that $\{x_1,x_2,x_3\}$ is a monochromatic $a_i$-a.p. that
is contained in $\intv{a_j}$. Since $a_{i+1}$ divides $a_j$, we see that every
subinterval of $\intv{a_j}$ of the form $[ka_{i+1}+1,(k+1)a_{i+1}]$, $k\geq1$,
imitates $\intv{a_{i+1}}$. Hence, since there is no 2-term monochromatic $a_i$-a.p.
in $\intv{a_{i+1}}$, neither of the pairs $\{x_1,x_2\}$ and $\{x_2,x_3\}$ could
be in any one interval $[ka_{i+1}+1,(k+1)a_{i+1}]$. This implies that $x_3-x_1>
a_{i+1}\geq2a_i$, a contradiction.

We have shown that for each $i\geq1$ and each $j\geq1$, there is no 3-term
monochromatic $a_i$-a.p. with respect to $\chi$, which is contained in $\intv{a_j}$,
which proves the theorem.\end{proof}

The next theorem, important in proving many subsequent results, shows that finite
unions of small sets cannot be large.

\begin{thrm}\label{t24}If $A=A_1\cup\cdots\cup A_n$ and $A$ is large, then
some $A_i$ is large.\end{thrm}
\begin{proof} By an obvious induction argument, it suffices to prove the result
for $n=2$. So let $A=B\cup C$, and assume neither $B$ nor $C$ is large. Since $B$
is not large, there exist positive integers $r$ and $k_1$, and some $r$-coloring
$\rho$ of $\mathbb{Z}^+$, under which there is no monochromatic $k_1$-term
$B$-a.p. Likewise, there exist positive integers $s$ and $k_2$, and an $s$-coloring
$\sigma$ of $\mathbb{Z}^+$, under which there is no monochromatic $k_2$-term
$C$-a.p.

Define $\chi$ to be the $rs$-coloring of $\mathbb{Z}^+$ given by $\chi(n) =
(\rho(n), \sigma(n))$. Let $k=\max\{k_1,k_2\}$. Let $X$ be any $k$-term a.p.
that is monochromatic with respect to $\chi$. Then $X$ must also be
monochromatic with respect to each of the colorings $\rho$ and $\sigma$. Hence
$X$ must have common difference lying outside $B\cup C$. Hence $B\cup C$ is
not large.\end{proof}

\begin{corl}\label{c21} Let $c>1$ be a fixed real number. Let $A=\{a_i\}_{i=1}^\infty$
be an increasing sequence of positive integers such that $a_i\geq ca_{i-1}$
for all but a finite number of $i\geq2$. Then $A$ is not large.\end{corl}
\begin{proof} Consider first the case in which $a_i\geq ca_{i-1}$ for all
$i\geq2$. Let $n$ be such that $c^n\geq3$. For each $i=1,\ldots,n$, let
$A_i = \{a_{jn+1}:j=0,1,2,\ldots\}$. For each $i$ and each $j\geq1$, $a_{jn+i}
\geq 3a_{(j-1)n+i}$. Hence by Theorem \ref{t22} each $A_i$ is not 2-large.
Since $A = A_1\cup\cdots\cup A_n$, by Theorem \ref{t24}, $A$ is not large
(by the proof of Theorem \ref{t24}, $A$ is not $2^n$-large).

To complete the proof, let $m\geq2$ be such that $a_i\geq ca_{i-1}$ for
all $i\geq m$. By the above case, $\{a_{m-1},a_m,\ldots\}$ is not large.
By Theorem \ref{t21}, $\{a_1,\ldots,a_{m-2}\}$ is not large. Hence, by
Theorem \ref{t24}, $A$ is not large (by the proof of Theorem \ref{t24},
it is not $2^{n+1}$-large).\end{proof}

\begin{rmrks} By Theorem \ref{t24} it is obvious that Corollary \ref{c21}
can be extended to any set $A = B_0\cup \cdots \cup B_n$ having the property
that for each $k=0,\ldots,m$, there exists a $c_k>1$ such that $B_k=\{
b_{k,i}:i=1,2,\ldots\}$ with $b_{k,i}\geq c_kb_{k,i-1}$ for $i\geq2$. For
example, let $\{f_n:n\geq1\}$ be the set of Fibonacci numbers. It is easy
to show that for each $k\geq0$ there exists a $c_k>1$ such that for all
$n\geq2$, $f_n+k\geq c_k(f_{n-1}+k)$ (when $k=0$ we can take $c_k=3/2$).
Hence if $m$ is a fixed nonnegative integer, the set $\bigcup_{n=1}^\infty
[f_n,f_n+m]$ is not large.

Although the complement of a small set is large (by Theorem \ref{t24}),
the complement of a large set need not be small. For example, by the work
of Bergelson nd Leibman, $A = \{n^2\}$ and $B = \{2n^2\}$ are both large
sets, but since $B\subset\mathbb{Z}^+\setminus A$, we have that $\mathbb{Z}^+
\setminus A$ is large.

We note that if $A$ and $B$ are small sets, then the proof of Theorem \ref{t24}
does not necessarily give the ``best'' (i.e., the least) value of $n$ such that
$A\cup B$ is not $n$-large. For example, let $m\geq3$ be odd and let $A=\{a_i\}$
be an increasing sequence of positive multiples of $m$ such that $a_{i-1}$
divides $a_i$ for all $i\geq2$. By Theorem \ref{t22} (or Theorem \ref{t23}),
$A$ is not 2-large. Now let $B$ be the set of all positive integers $n$ such
that $m\nmid n$. By Theorem \ref{t21}, $B$ is not 2-large. Hence, according
to Theorem \ref{t24}, $A\cup B$ is not 4-large. However, by the following
result, we can make the stronger statement that $A\cup B$ is not 3-large.

Before proceeding we define, for $m>1$, a $k$-term a.p. (mod $m$) to be an
increasing sequence of positive integers $\{x_i\}_{i=1}^k$ such that for some
$d\in \{1,2,\ldots,m-1\}$, $x_i-x_{i-1}\equiv d\Mod{m}$ for all $i=2,\ldots,
k$. Denote by (AP)$_m$ the family of all a.p.'s (mod $m$). In \cite{landman1998}
it was shown that if $m$ is odd and $A$ is a finite set of multiples of $m$,
then the family $A^*\cup$ (AP)$_m$ does not have the 3-Ramsey property, where
$A^*$ is the family of all $A$-a.p.'s. The next proposition extends this result
to certain cases in which $A$ contains an infinite number of multiples of $m$.
\end{rmrks}

\begin{prop} Let $m\geq3$ be odd and let $A=\{a_i\}$ be a sequence of positive
integers such that $m|a_1$ and $a_{i-1}|a_i$ for $i\geq2$. Let $A^*$ be the
family of all $A$-a.p.'s. Then $A^*\cup$ (AP)$_m$ does not have the 3-Ramsey
property.\label{p21}\end{prop}
\begin{proof} We give a 3-coloring $\chi$ of the positive integers, and show
that under $\chi$ there is no monochromatic $m$-term a.p. (mod $m$) and no
monochromatic 3-term $a_i$-a.p. for all $i$.

Let $S_1 = \intv{\ceil{m/3}}$, $S_2 = [\ceil{m/3}+1,\ceil{2m/3}]$, and $S_3
= [\ceil{2m/3}+1, m]$. Denote by $C_1$ the string of length $m$ representing
the coloring defined by
\[ C_1(x) = \left\{\begin{array}{cl}
1&\text{if } x_\in S_1 \\
2&\text{if } x_\in S_2 \\
3&\text{if } x_\in S_3.\end{array}\right. \]
Denote by $C_2$ the string of length $m$ representing the coloring defined by
\[ C_2(x) = \left\{\begin{array}{cl}
3&\text{if } x_\in S_1 \\
1&\text{if } x_\in S_2 \\
2&\text{if } x_\in S_3.\end{array}\right. \]
If $I$ is an interval of length $m$ and $\chi$ is a coloring such that $\chi(I)
= C_1$, define $\bar{\chi}(I)$ to be the coloring $C_2$; and if $\chi(I) = C_2$,
define $\bar{\chi}(I)$ to be the coloring $C_1$.

We now define the coloring $\chi$ recursively as follows: (i) for each $x\in
\intv{a_i}$, let $x'$ be the element of $[1,m]$ such that $x\equiv x'\Mod{m}$,
and let $\chi(x) = C_1(x')$; (ii) once $\intv{a_{i-1}}$, $i\geq2$, has been
colored, we color $[a_{i-1}+1,a_i]$ as follows:
\[ \chi([ka_{i-1} + (j-1)m+1, ka_{i-1} + jm]) = \bar{\chi}([(k-1)a_{i-1} + (j-1)m+1, (k-1)a_{i-1}+jm]), \]
for $1\leq k\leq (a_i/a_{i-1}) - 1$ and $1\leq j\leq a_{i-1}/m$.

Note that, from elementary group theory, since $m\geq3$, any $m$-term a.p.
(mod $m$) contains at least one element from each of $S_1$, $S_2$, and $S_3$.
Hence there is no $m$-term monochromatic a.p. (mod $m$).

Now assume that $\{x,y\}$ is monochromatic with $y-x=a_i$. Consider the
partition of the positive integers $\mathbb{Z}^+ = \bigcup_{j=1}^\infty B_j$,
where $B_j = [(j-1)a_{i+1}+1, ja_{i+1}]$. Note that, by the way $\chi$ is
defined, $x$ and $y$ cannot be monochromatic and lie in the same $B_j$. Thus,
$y$ and $y+a_i$ do lie in the same $B_j$, and hence $\chi(y)\neq\chi(y+a_i)$.
That is, there is no 3-term monochromatic $a_i$-a.p., and the proof is
complete.\end{proof}

\begin{corl}\label{c22} Let $m\geq3$ be odd and let $B$ be the set of all
positive integers not divisible by $m$. Let $A = \{a_i\}$ be an increasing
sequence of positive multiples of $m$ such that $a_{i-1}|a_i$ for $i\geq2$.
Then $A\cup B$ is not 3-large.\end{corl}
\begin{proof} This is immediate from Proposition \ref{p21} since each
$B$-a.p. is a member of (AP)$_m$.\end{proof}

\begin{rmrk} Corollary \ref{c22} follows from Proposition \ref{p21} by the
fact that $A^*(m)$, the set of all arithmetic progressions having common
differences which are not multiples of $m$, is a subset of the set (AP)$_m$.
On the other hand, there are examples showing that we cannot always replace
the collection (AP)$_m$ by the collection $A^*(m)$ and expect the Ramsey
properties to be unaffected. For example, in \cite{landman+wysocka1997}
it was shown that if $D$ is the set of all arithmetic progressions with
common difference 2, then the family (AP)$_2\cup D$ has the 3-Ramsey property.
In contrast, by Theorem \ref{t21}, we see that A$^*(2)\cup D$ does not even have the
2-Ramsey property, i.e., $A = \{2n-1:n\in\mathbb{Z}\}\cup\{2\}$ is not
2-large. In fact, $B= \{2n-1:n\in\mathbb{Z}^+\}\cup\{2^n:n\geq0\}$ is not
2-large, since $B$ contains no multiples of six.\end{rmrk}

\section{Some Positive Results\label{s3}}

In this section we give some sufficient conditions for a set to be large.

\begin{lmma} For each positive integer $r$, if $A$ is $r$-large and $F$
is finite, then $A\setminus F$ is $r$-large.\label{l31}\end{lmma}
\begin{proof} It suffices to show that $A\setminus\{a\}$ is $r$-large for
each $a\in A$. Assume that this is not the case. Then there is an $a_0\in
A$, an $r$-coloring $f$ of $\mathbb{Z}^+$, and a $k\in\mathbb{Z}^+$ such
that there is no monochromatic $k$-term $(A\setminus\{a_0\})$-a.p. Hence,
under $f$, there are arbitrarily long monochromatic $a_0$-a.p.'s. By
Theorem \ref{t21}, $ma_0\in A$ for some $m>1$. Under $f$, there are
arbitrarily long monochromatic $ma_0$-a.p.'s, a contradiction.\end{proof}

\begin{thrm}\label{t31} Let $p(x)$ be a polynomial with integer coefficients
and leading coefficient positive. If $x+a$ divides $p(x)$ for some integer
$a$, then $\left(\range(q)=\{p(x): x=1,2,\ldots\}\right)\cap\mathbb{Z}^+$
is large.\end{thrm}
\begin{proof} Let $p(x) = (x+a)s(x)$. Let $q(x) = p(x-a)$. So $q(x) = xs(x-a)$.
By the result of Bergelson and Leibman mentioned in Section \ref{s1}, $\range(q)
\cap\mathbb{Z}^+$ is large. If $a\leq0$ then $\range(q)\subseteq\range(p)$, so
$\range(p)\cap\mathbb{Z}^+$ is large. If $a>0$, then $\range(p) = \range(q)\setminus F$,
where $F$ is finite, so by Lemma \ref{l31} $\range(p)\cap\mathbb{Z}^+$ is large.
\end{proof}

\begin{rmrks} does the converse of Theorem \ref{t31} hold? That is, if no $x+a$
divides the polynomial $p(x)$, does it follow that $\{p(n):n\in\mathbb{Z}^+\}$
is not large? It is easy to see (by Theorem \ref{t21}) that the answer is yes
if $p(x)$ has degree one, for if $p(x) = ax+b$, where $b$ is not a multiple
of $a$, then the range of $p(x)$ contains no multiples of $a$. We do not know
the answer for the general case. Another question: is it true that whenever
the range of a polynomial $p(x)$ is not large, then the range fails to contain
multiples of some positive integer $m$? It would be interesting to know whether
the range of the polynomial $f(x) = (x^2-13)(x^2-17)(x^2-221)$ is large,
because although $f(x)$ has no linear factors, its range contains an infinite
number of multiples of every positive integer $m$ (using the properties of the
Legendre symbol, one can show that the congruence $f(x)\equiv 0\Mod{m}$ is
solvable for all $m$).\end{rmrks}

\begin{thrm}\label{t32} If $A$ is a set of positive integers containing $n$-cubes
for arbitrarily large $n$, then $A$ is large.\end{thrm}
\begin{proof} The proof makes use of the Hales-Jewett theorem \cite{hales+jewett1963},
for which we need some notation. Let $k$ be any fixed positive integer, and let
$B=\{0,1,\ldots,k-1\}$. For a positive integer $n$, we consider the set $B^n$
of $n$-tuples with entries from $B$ and the set $(B\cup\lambda)^n$ of $n$-tuples
with entries from $B\cup\lambda$, where $\lambda$ is indeterminate.

Let $w(\lambda)$ denote an element of $(B\cup\lambda)^n$ in which at least one
$\lambda$ occurs. For each $i$, $0\leq i\leq k-1$, let $w(i)$ denote the result
of replacing each occurrence of $\lambda$ in $w(\lambda)$ by $i$.

A \emph{combinatorial line} in $B^n$ is any set $L$ having the form $\{w(0),
w(1),\ldots,w(k-1)\}$ for some $n$-tuple $w(\lambda)$ in $(B\cup\lambda)^n$,
where $w(\lambda)$ has at least one occurrence of $\lambda$.

The Hales-Jewett theorem asserts that for any given positive integers $k$ and
$r$, with $B = \{0,1,\ldots,k-1\}$, there exists a positive integer $n$ such
that for every $r$-coloring of $B^n$ there is a monochromatic combinatorial
line.

Now let $r$ be a positive integer and let $\chi$ be any $r$-coloring of the
positive integers. We assume that $A$ contains arbitrarily large cubes, and
we wish to show that for each $k$ there are monochromatic $k$-term $A$-a.p.'s.
Let $k$ be given, and choose $n$ according to the Hales-Jewett theorem so
that every $r$-coloring $B^n$, where $B = \{0,\ldots,k-1\}$, has a monochromatic
combinatorial line. Since $A$ contains arbitrarily large cubes, $A$ contains
an $n$-cube, say $Q(a_1,\ldots,a_n)$.

Now define an $r$-coloring $\sigma$, of $B^n$, as follows: for each $(x_1,\ldots,
x_n)$ in $B^n$, let
\[ \sigma(x_1,\ldots,x_n) = \chi(x_1a_1 + x_2a_2 + \cdots + x_na_n). \]

By the choice of $n$, there exists a combinatorial line $L = \{w(0),\ldots,
w(k-1)\}$ that is monochromatic with respect to $\sigma$. To simplify our
notation, we may assume that $w(\lambda) = (x_1,x_2,\ldots,x_s,\lambda,
\lambda,\ldots,\lambda)$, where $s\leq n-1$, all the $x_i$'s belong to $B$,
and there are $n-s$ occurrences of $\lambda$. Then for $0\leq i\leq k-1$,
\[ \sigma(w(i)) = \sigma(x_1,x_2,\ldots,x_s,i,i,\ldots,i) = \chi(x_1a_1 + \cdots + x_sa_s + i(a_{s+1}+\cdots+a_n)). \]

Writing $a = x_1a_1 + \cdots + x_sa_s$ and $d = a_{s+1} + \cdots + a_n$,
we have that $d\in Q(a_1,\ldots,a_n)\subseteq A$, and $\chi$ is constant
on the $k$-term arithmetic progression $P = \{a+id:0\leq i\leq k-1\}$.
Hence we have shown that for each $r>0$ and $k>0$, every $r$-coloring of
the positive integers contains a monochromatic $k$-term $A$-a.p.\end{proof}

In the next corollary, the symbol $\{r\}$ denotes the fractional part of
the real number $r$, i.e., $\{r\} = r - \floor{r}$.

\begin{corl}\label{c31}\begin{enumerate}
\item[(a)] Let $\alpha>0$ be irrational and let $\epsilon>0$. Then $A=
\{ i\in\mathbb{Z}^+:\{i\alpha\}<\epsilon\}$ is large.
\item[(b)] Let $\alpha>0$. Then $A = \{\floor{n\alpha}:n\in\mathbb{Z}^+\}$
is large.
\item[(c)] If $A$ is a set of positive integers containing arbitrarily
long intervals, then $A$ is large.
\end{enumerate}\end{corl}
\begin{proof}\begin{enumerate}
\item[(a)] Since $\{\{i\alpha\}:i\in\mathbb{Z}^+\}$ is dense in the unit
interval, for each $k\geq1$ we may choose $a_k\in A$ such that $\{a_k\alpha\}
< \epsilon/2^k$. Let $n$ be a given positive integer. Then $\{(a_1+\cdots+
a_n)\alpha\}<\epsilon$, so $A$ contains the infinite cube $Q(a_1,a_2,\ldots)$.
By Theorem \ref{t32}, $A$ is large.
\item[(b)] The proof is essentially the same as the proof of (a).
\item[(c)] The set must contain an infinite cube (see \cite[pp. 171]{furstenberg1981-1}).
\end{enumerate}\end{proof}

By Theorem \ref{t31}, the range of any polynomial with integer coefficients,
that is divisible by $x+a$ for some $a$, is large. However, it is easy to
find a large set $A$ with the property that for each polynomial $p(x)$ with
integer coefficients, $A$ does not contain all but finitely many elements
of $\range(p)$ (we say ``all but finitely many'' because of Lemma \ref{l31}).
This follows easily from the following more general result.

\begin{prop}\label{p31} If $R_1,R_2,\ldots$ is a sequence of infinite
subsets of $\mathbb{Z}^+$, then there exists a large set $A$ such that the
complement of $A$ contains infinitely many elements of every $R_i$.\end{prop}
\begin{proof} We define $B = \{b_1,b_2,\ldots\}$ as follows. Let $b_1$
and $b_2$ be arbitrary elements of $R_1$ such that $b_2>b_1$.

Now assume $j\geq3$. Once $b_1,\ldots,b_{j-1}$ have been defined, choose
$b_j$ such that $b_j\in R_i$ and $b_j-b_{j-1} > b_{j-1}-b_{j-2}$. Then
the sequence $\{b_j:j=1,2,\ldots\}$ contains infinitely many members of
each $R_i$. Also, $b_j-b_{j-1}$ goes to infinity with $j$. Hence, if $A
=\mathbb{Z}^+\setminus\{b_j:j=1,2,\ldots\}$, $A$ contains arbitrarily
long intervals, hence is large by Corollary \ref{c31}(c).\end{proof}

The following theorem provides some simple ways of obtaining large sets
from other large sets. The proofs are relatively straightforward and
are omitted.

\begin{thrm}\label{t33}\begin{enumerate}
\item[(a)] If $A$ is large and $m$ is a positive integer, then $mA$ is large.
\item[(b)] If $A$ is large and $m$ is a positive integer, then $A\setminus \{x:m\not| x\}$ is large.
\item[(c)] If $A$ is $r$-large, and if all elements of $A$ are multiples
of the positive integer $m$, then $\frac1mA$ is $r$-large (hence, $A$
large implies $\frac1mA$ large).
\end{enumerate}\end{thrm}

We have yet to see an example of a set $A$ that is $r$-large for some
$r\geq2$, but that is not large. We make the following conjecture.

\begin{conj} If $A$ is 2-large, then $A$ is large.\end{conj}

We have some partial results concerning the above conjecture. In the
following theorem, we use the symbol $A^n$, where $A$ is a set of
positive integers, to denote the set of products $\{x_1x_2\ldots x_n:
x_i\in A\}$.

\begin{thrm}\label{t34} If $A$ is 2-large, then $A^n$ is $2^n$-large.\end{thrm}

\begin{proof}[Sketch of Proof.] We prove this by induction on $n$.
For the induction step, let $\chi$ be a $2^{n+1}$-coloring of the
positive integers, using the colors $1,2,3,\ldots,2^{n+1}$. Define
the 2-coloring $\lambda$ on $\mathbb{Z}^+$ by
\[ \lambda(x) = \left\{\begin{array}{cl}
a&\text{if } \chi(x)\in [1,2^n] \\
b&\text{if } \chi(x)\in [2^n+1,2^{n+1}].\end{array}\right. \]
\end{proof}

\begin{corl}\label{c32} If $A$ is 2-large and is closed under multiplication,
then $A$ is large.\end{corl}

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

We do not know if Theorem \ref{t24} is still true if we replace ``large''
with ``$r$-large''. In particular, if $A\cup B$ is 2-large, must it
follow that at least one of $A$ or $B$ is 2-large? We remarked in
Section \ref{s2} that, by Theorem \ref{t21}, the set $\{2n-1:n\geq1\}
\cup\{2^n:n\geq0\}$ is not 2-large. We would like to know if $\{2n-1:
n\geq1\}\cup\{n!:n\geq1\}$ (an example not covered by Theorem \ref{t21})
is 2-large (it is not 4-large by Theorem \ref{t22} and the proof of
Theorem \ref{t24}).

We also ask: which sets $A$ have the property that some translation of
$A$ is large, i.e., for which $A$ does there exist an integer $x$ such
that $x+A=\{x+a:a\in A\}$ is large? By the result of Bergelson and
Leibman, the range of any polynomial $p(x)$ has this property, since
$p(x)- p(0)$ sends 0 into 0. Also, it follows from Theorem \ref{t24}
that any set $A$ with bounded gaps has this property since then
$\mathbb{Z}^+ = \bigcup_{i=0}^s (A+i)$ for some $s$. It would be interesting
to know if some translation of the set of primes is large (by Theorem
\ref{t21}, it would have to be an odd translation).

Let $p(x)$ be any polynomial with integer coefficients, positive
leading coefficient, and $p(0) = 0$, and let $A$ be a large set.
Must $\{p(x):x\in A\}$ be large? In particular, must $\{x^2:x\in A\}$
be large?

\paragraph{Acknowledgements.} The authors are grateful for suggestions
from the referee, which led to significant improvements of this paper.


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