%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-5/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{lmma}{Lemma}
\newtheorem{corl}{Corollary}
\newtheorem{defn}{Definition}

\title{A partition of the non-negative integers, with applications to Ramsey Theory}
\author{Tom C. Brown\\
\\
Department of Mathematics, ¶¡ÏãÔ°AV\\
Burnaby, British Columbia, Canada V5A 1S6\\
\texttt{tbrown@sfu.ca}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{A partition of the non-negative integers, with applications to
  Ramsey theory}, Discrete Mathematics and its Applications (Proceedings of the
  International Conference on Discrete Mathematics and its Applications, Amrita
  Vishwa Vidyapeetham, Ettimadai Coimbatore, India), Narosa Publishing House,
  2006, pp.~79--87.}\bigskip\end{center}

\begin{abstract}After some general remarks about Ramsey theory, we describe
a particular partition of the non-negative integers into infinitely
many translates of an infinite set. This partition is used to settle
(negatively) the question of the truth of a statement similar in form
to the Erd\H{o}s-Graham canonical version of van der Waerden's theorem
on arithmetic progressions. It is also used to give a lower bound for
one of the classical van der Waerden functions.
\end{abstract}


\section{Introduction}

Ramsey theory is a cohesive sub-discipline of combinatorics. The theme
of Ramsey theory is that ``complete chaos is impossible''. Or, one could
say that Ramsey theory is ``the study of unavoidable regularities in
large structures''.

Two of the largest branches of Ramsey theory start with either ``Ramsey's
Theorem'' on the one hand, or ``van der Waerden's Theorem on Arithmetic
Progressions'' on the other. These two branches sometimes overlap, but a
great number of results can be placed on one branch or the other.

The simplest form of Ramsey's Theorem says that for every positive integer
$k$ there exists a (smallest) positive integer $r(k)$ such that any graph
on $r(k)$ vertices contains either a complete subgraph on $k$ vertices (all
edges are present) or an independent set of $k$ vertices (no edge is present).
A stronger statement, also proved by Ramsey, is that in any graph on infinitely
many vertices, there is either an infinite set of vertices $A$, in which all
edges are present, or there is an infinite set of vertices $B$, in which no
edge is present.

The simplest form of van der Waerden's Theorem on Arithmetic Progressions says
that for every positive integer $k$ there exists a (smallest) positive integer
$w(k)$ such that if $\{1,2,\ldots,w(k)\}$ is partitioned into two parts, in any
way whatsoever, then at least one of the parts contains a $k$-term arithmetic
progression, that is, a subset of the form $\{a,a+d,a+2d,\ldots,a+(k-1)d\}$. (An
equivalent statement is the following: If the set of all positive integers is
partitioned into two parts, then one part must contain arbitrarily large (finite)
arithmetic progressions.)

For example, $w(5) = 178$, and this means:
\begin{enumerate}
\item If $\{1,2,3,\ldots,178\}$ is the disjoint union of $A$ and $B$, then $A$
or $B$ must contain a 5-term arithmetic progression $\{a,a+d,a+2d,a+3d,a+4d\}$.
\item There exists a partition of $\{1,2,3,\ldots,177\}$ into sets $A$ and $B$
such that neither $A$ nor $B$ contains a 5-term arithmetic progression.
\end{enumerate}

The fact that $w(5) = 178$ was shown by direct computation. To establish $w(5)
\leq 178$, one has to essentially check all of the $2^{178}$ partitions into two
parts of $\{1,2,3,\ldots,178\}$, so its not surprising that the value of $w(6)$
is unknown. (It is known that $w(6)\geq 696$.) Other known values of $w(k)$ are
$w(3) = 9$, $w(4) = 35$, $w(3,3,3) = 27$ (partitions of $\{1,2,\ldots,27\}$ into
3 parts), and $w(3,3,3,3) = 76$ (partitions of $\{1,2,\ldots,76\}$ into 4 parts).
There are also a few known values such as $w(4,3,3) = 51$, which means that every
partition of $\{1,2,\ldots,51\}$ into 3 parts produces a 4-term arithmetic
progression in the first part, or a 3-term arithmetic progression in the 2nd or
3rd parts, and 51 is the smallest positive integer with this property.

In 1999, Ron Graham gave Timothy Gowers a ``reward'' of \$1000 US dollars for
showing that $w(k) < 2^{2^{2^{2^{2^{k+9}}}}}$. This bound, while quite large,
is tiny compared to the previous best-known bounds.

The true rate of growth of the function $w(k)$ is one of the holy grails of Ramsey
theory, and Ron Graham now offers \$1000 US dollars for a proof (or disproof)
that $w(k) \leq 2^{k^2}$. The best lower bound known for $w(k)$ is the following:
for every $\epsilon > 0$, $2^k/k^\epsilon < w(k)$, for all sufficiently large $k$.

\section{The Description of a Particular Partition}

Let $S$ denote the set of all distinct sums of odd powers of 2, including 0 as
the empty sum, and let $T$ denote the set of all distinct sums of even powers of
2, including 0 as the empty sum. Then every non-negative integer can be written
uniquely in the form $s+t$, where $s\in S$ and $t\in T$. Thus $\{s+T:s\in S\}$ is
a partition of $\omega=\{0,1,2,\ldots\}$ into translates of $T$.

It is more convenient to describe this partition as a \emph{coloring} $f$ of
$\omega$. Thus for each $n\in\omega$, we write $n = s + t$, $s\in S$, $t\in T$,
and define $f(n) = s$. In other words, if $n = \sum_{i\text{ odd}}2^i +
\sum_{i\text{ even}} 2^i$, then $f(n) = \sum_{i\text{ odd}} 2^i$. For this
coloring $f$, the set of colors is $S$, and for each $s\in S$, $f$ is constant
on the ``color class'' $s + T$.

\section{A van der Waerden-Like Theorem}

We need the following definition.
\begin{defn} If $A = \{a_1<a_2<\cdots<a_n\}\subset\omega=\{0,1,2,\ldots\}$, $n> 1$,
the \emph{gap size} of $A$ is $\gs(A) = \max\{a_{j+1}-a_j:1\leq j\leq n-1\}$. If
$|A| = 1$, $\gs(A) = 1$.\end{defn}

\begin{thrm} If $\omega$ is finitely colored, there exists a fixed $d\geq1$ ($d$
depends only on the coloring) and arbitrarily large (finite) monochromatic sets
$A$ with $\gs(A) = d$.\label{t1}\end{thrm}

This fact first appeared in \cite{brown1968}. A proof can be found in
\cite{landman+robertson2004}. Various applications appear in \cite{brown1971-1,
deluca+varricchio1998,lallement1979,straubing1982}.

Theorem \ref{t1} is somewhat similar in form to van der Waerden's theorem on
arithmetic progressions \cite{vanderwaerden1927}. However, Theorem \ref{t1}
differs in a number of ways.

Van der Waerden's theorem does not imply Theorem \ref{t1}, since the $d$ in the
conclusion of Theorem \ref{t1} is independent of the size of the monochromatic
sets $A$. Beck \cite{beck1980} showed the existence of a 2-coloring of $\omega$
such that if $A$ is any monochromatic arithmetic progression with common difference
$d$, then $|A|<2\log d$. Hence the presence of large monochromatic arithmetic
progressions, which is guaranteed by van der Waerden's theorem, is not enough to
imply Theorem \ref{t1}. Somewhat earlier, Justin \cite{justin1971} found an
explicit coloring such that if $A$ is any monochromatic arithmetic progression with
common difference $d$, then $|A|<h(d)$; in his example, the coloring is explicit
but the function $h(d)$ is not.

Theorem \ref{t1} (which has a simple proof) does not imply van der Waerden's
theorem in a simple way.

Theorem \ref{t1} does not have a density version corresponding to Szemer\'edi's
theorem \cite{szemeredi1975}. That is, there exists a set $X\subset\omega$ with
positive upper density for which there do not exist a fixed $d\geq1$ and
arbitrarily large sets $A=\{a_1<a_2<\cdots<a_n\}$ with $\gs(A) = d$. For an
example of such a set, see \cite{bergelson+hindman+mccutcheon1998}.

Finally, recall that the Erd\H{o}s-Graham canonical version of van der Waerden's
theorem (\cite{erdos+graham1980}) states that if $g:\omega\to\omega$ is an
arbitrary coloring of $\omega$ (using finitely many or infinitely many colors)
then there exist arbitrarily large arithmetic progressions $A$ such that either
$g$ is constant on $A$, i.e. $|g(A)| = 1$, or $g$ is one-to-one on $A$, i.e.
$|g(A)| = |A|$.

We show that there is no such canonical version of Theorem \ref{t1}. This is
Corollary \ref{c1} below.

\section{Theorem \ref{t1} Does Not Have a Simple Canonical Version}

\begin{thrm}\label{t2} For every $A\subset\omega$ (with $f$ as described above, in
the ``description of a particular coloring''),
\[ \frac14\sqrt{|A|/\gs(A)} < |f(A)| < 4\sqrt{|A|\gs(A)}. \]
\end{thrm}
\begin{corl}\label{c1} For the coloring $f$ above, there do not exist a fixed $d$
and arbitrarily large sets $A$ with $\gs(A) = d$ on which $f$ is either constant
or 1-1.\end{corl}
\begin{proof}[Proof of Corollary \ref{c1}.] If $16\gs(A)\leq|A|$, then by Theorem
\ref{t2}, $1<|f(A)|<|A|$.\end{proof}

To prove Theorem \ref{t2}, we need the following definition.

\begin{defn} For $k\geq0$, an \emph{aligned block} of size $4^k$ is a set of
$4^k$ consecutive integers whose smallest element is $m4^k$, for some $m\geq0$.
\end{defn}
\begin{proof}[Proof of Theorem \ref{t2}.] Note that the first aligned block of
size $4^k$, namely $[0,4^k-1]=[0,2^{2k}-1]$, is in 1-1 correspondence with the
set of all binary sequences of length $2k$. From this we see (by the definition
of $f$) that for $n\in[0,2^{2k}-1]$, there are $2^k$ possible values of $f(n)$,
and each value occurs exactly $2^k$ times. It is easy to see (using the definition
of $f$) that the same is true for any aligned block $[m4^k,m4^k+4^k-1]$. We express
this more simply by saying that \emph{``each aligned block of size $4^k$ has $2^k$
colors, each appearing exactly $2^k$ times''}.

Now we can establish the upper bound in Theorem \ref{t2}. Let $A = \{a_0<a_1<a_2<
\cdots<a_n\}\subset\omega$. Then $a_n\leq a_0 + n\gs(A) = a_0 + (|A|-1)\gs(A)$, or
\[ a_n-a_0 < |A|\gs(A). \]

Choose $s$ minimal so that $A$ is contained in the union of two adjacent aligned
blocks of size $4^s$. (Two blocks are needed in case $A$ contains both $m4^s-1$
and $m4^s$ for some $m$.) Then
\[ 4^{s-1} < a_n - a_0. \]

Since each aligned block of size $4^k$ has $2^k$ colors,
\[ |f(A)| \leq 2\cdot2^s. \]

Putting these three inequalities together gives
\[ |f(A)| < 4\sqrt{|A|\gs(A)}. \]

Next, we establish the lower bound for $|f(A)|$, which requires a bit more care. We
will use the following Lemma.

\begin{lmma}\label{l1} For each $k\geq0$, any two aligned blocks of size $4^k$
(consecutive or not) are either colored identically, or have no color in common.
\end{lmma}
\begin{proof}[Proof of Lemma \ref{l1}.] Consider the aligned blocks $[p4^k,p4^k+
4^k-1]$ and $[q4^k,q4^k+4^k-1]$. By the definition of $f$ (and since $4^k$ is an
even power of 2), $f(p4^k) = f(p)4^k$, so that $f(p4^k) = f(q4^k)$ if and only
if $f(p) = f(q)$. Also, for $0\leq j\leq 4^k-1$, $f(p4^k+j) = f(p4^k) + f(j)$.
This last equality obviously holds if $p = 0$, and for $p>0$ it holds since
then each power of 2 which occurs in $j$ is less that each power of 2 which
occurs in $p4^k$.
Thus the blocks $[p4^k, p4^k+4^k-1]$ and $[q4^k+4^k-1]$ are colored identically
if $f(p) = f(q)$, and have no color in common if $f(p)\neq f(q)$.

Proceeding with the lower bound in Theorem \ref{t2}, we note that for $k\geq1$,
the colors of any aligned block of size $4^k$ have the form $UUVV$, where $U$ and
$V$ are blocks of size $4^{k-1}$.

Next, we note that any block of size $4^k$, aligned or not, contains \emph{at
least} $2^k$ colors. For let $A$ be any block of size $4^k$. Let the first element
of $A$ lie in the aligned block $S$ of size $4^k$, and let $T$ be the aligned
block of size $4^k$ which immediately succeeds $S$. If $S$ and $T$ are colored
identically, then the elements of $f(A)$ are just a cyclic permutation of the
elements of $f(S)$, and hence the block $A$ contains exactly $2^k$ colors. By
Lemma \ref{l1}, the remaining case is when $S$, $T$ have no color in common. In
this case, by the preceding paragraph, $f(S)f(T) = UUVVXXYY$, where no two of
$U,V,X,Y$ have a color in common, and $U,V,X,Y$ are of size $4^{k-1}$. Then $f(A)$,
which has size $4^k$, contains either $UV$ or $VX$ or $XY$, and so has at least
$2^{k-1} + 2^{k-1} = 2^k$ colors.

Finally, we note that for $s\geq1$, $k\geq1$, every set of $4^s$ consecutive
aligned blocks of size $4^k$ contains at least $2^s$ blocks of size $4^k$, no two
of which have a common color. This follows from the fact that these $4^s$ blocks
have the form $[p4^k, p4^k+4^k-1]$, $t\leq p\leq t + 4^s - 1$, for some $t$. The
block $f([t,t+4^s-1])$ has at least $2^s$ colors, by the preceding paragraph. If
$f(p)\neq f(q)$, where $t\leq p<q\leq t + 4^s-1$, then $f(p4^k) \neq f(q4^k)$,
so by Lemma \ref{l1} the two blocks $[p4^k,p4^k+4^k-1]$ and $[q4^k,q4^k+4^k-1]$
have no color in common.

Now let $A\subset\omega$ be given. Choose $k$ so that $4^{k-1}\leq\gs(A)<4^k$.
Choose $t$ minimal so that $A$ is contained in the union of $t$ consecutive
aligned blocks of size $4^k$. Then $A$ meets each of these blocks (by the
choice of $k$), and
\[ |A| \leq t4^k. \]

Choose $s$ so that $4^s\leq t<4^{s+1}$. Then among the $t$ consecutive aligned
blocks of size $4^k$ are at least $2^s$ blocks of size $4^k$, no two of which have
a color in common. Since each of the $t$ blocks meets $A$, we have
\[ 2^s\leq |f(A)| \]

Thus $|A|\leq t4^k<4\cdot4^s\cdot4\cdot4^{k-1}\leq 4|f(A)|^2\cdot4\cdot\gs(A)$, so
$\frac14\sqrt{|A|/\gs(A)} < |f(A)|$.\end{proof}\end{proof}


\section{An Easy Lower Bound for a Classical van der Waerden Function}

\begin{defn}\label{d3} For $m\geq1$, let $w(3;m)$ denote the smallest positive
integer such that every $m$-coloring of $[1,w(3;m)]$ produces a monochromatic
3-term arithmetic progression.\end{defn}
\begin{thrm} For all $m\geq1$, $w(3;m)\geq\frac14m^2$.\label{t3}\end{thrm}
\begin{proof}[Proof of Theorem \ref{t3}.] The coloring $f$ shows (since the set
$T$ contains no 3-term arithmetic progression) that for $k\geq1$, $w(3;2^k)>
2^{2k}$. For a general $m$, choose $k$ so that $2^k\leq m<2^{k+1}$. Then
$w(3;m)\geq w(3;2^k)>2^{2k}>\frac14m^2$.\end{proof}

\section{Remarks}

\begin{enumerate}
\item The lower bound in Theorem \ref{t3} is not the best possible. Indeed, in
the standard reference Ramsey Theory \cite{graham+rothschild+spencer1990}, the
authors show with more elaborate techniques that for some positive constant $c$,
$w(3;m)>m^{c\log m}$.

\item Corollary \ref{c1} shows that a constant/1-1 canonical version of Theorem
\ref{t1} is not true. We also know by the Bergelson/Hindman/McCutcheon example
that a density version of Theorem \ref{t1} is not true. The following three
simple examples, most involving only 3-element sets, illustrate various
combinations of the truth or falsity of the ``constant/1-1 version'' and the
``density version''.
\begin{enumerate}
\item The simplest non-trivial case of van der Waerden's theorem says that every
finite coloring of the positive integers produces a monochromatic 3-term arithmetic
progression. The constant/1-1 version of the result holds by the Erd\H{o}s-Graham
theorem, and the density version holds by Szemer\'edi's theorem.
\item Schur's theorem says that if the positive integers are finitely colored,
then there is a monochromatic solution of $x+y=z$. The density version does not
hold by taking all the odd integers. The constant/1-1 version does not hold by
coloring each $x$ with the highest power of 2 dividing $x$.
\item Kevin O'Bryant showed me this example: If the positive integers are finitely
colored, then there is a monochromatic 3-term geometric progression (a set of the
form $\{a,ad,ad^2\}$). To get the constant/1-1 version, let a coloring $g$ of the
positive integers be given. Define a new coloring $h$ by setting $h(x) = g(2^x)$.
Then, by the Erd\H{o}s-Graham theorem, there is a set $\{a,a+d,a+2d\}$ on which
the coloring $h$ is either constant or 1-1, so the coloring $g$ is either constant
or 1-1 on the set $\{2^a,2^a2^d,2^a(2^d)^2\}$. The density version does not hold,
since the set of square-free numbers has positive density.
\item It seems natural to ask for a collection $P$ of 3-element sets (if such a
collection exists!) for which:
\begin{enumerate}
\item Every set of positive integers with positive upper density contains an
element of $P$.
\item It's not the case that for every coloring of the positive integers, there
is an element of $P$ on which the coloring is either constant or 1-1. Allen R.
Freedman communicated the following example to me, involving infinite sets. Here
instead of considering those collections of triples $\{x,y,z\}$ for which $x+z=2y$,
or $x+y=z$, or $xz = y^2$, one considers the collection $P$ of all subsets of
$\omega$ which have positive density. Then trivially every set of positive density
contains an element of $P$. However, any coloring which is constant on each
interval $[2^{n-1},2^n]$, with different colors for different $n$, shows that the
constant/1-1 version does not hold.
\end{enumerate}
\end{enumerate}
\item We have used a particular partition of $\omega$ into infinitely many
translates of an infinite set. Perhaps it's possible to describe \emph{all}
partitions of $\omega$ into infinitely many translates of an infinite set.
\end{enumerate}


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