%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-6/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
\newcounter{c1}
\newcounter{c2}
\newcounter{c3}
\newcounter{c4}
\newtheorem{thrm}[c1]{Theorem}
\newtheorem{corl}[c2]{Corollary}
\newtheorem{lmma}[c3]{Lemma}
\newtheorem{defn}[c4]{Definition}
\title{A coloring of the non-negative integers, with applications}
\author{Tom C. Brown
~\\~\\
\small Department of Mathematics\\
\small Simon Fraser University\\
\small Burnaby, BC\\
\small Canada V5A 1S6\\
\small \texttt{tbrown@sfu.ca}
}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{A partition of the non-negative integers, with applications},
INTEGERS - Elect. J. Combin. Number Theory \textbf{5} (2005), no. 2, A2,
(Proceedings of the Integers Conference 2003 in Honor of Tom Brown's
Birthday).}\bigskip\end{center}
\begin{abstract}We describe a particular partition of the non-negative integers
which consists of infinitely many translates of an infinite set. This partition
is used to show that a certain van der Waerden-like theorem has no simple
canonical version. The partition is also used to give a lower bound for one
of the classical van der Waerden functions, namely $w(3;m)$, the smallest
positive integer such that every $m$-coloring of $[1, w(3;m)]$ produces a
monochromatic 3-term arithmetic progression. Several open questions are
mentioned.
\end{abstract}
\section*{Introduction}
Let $S$ denote the set of all distinct sums of odd 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$, 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, and its canonical version}
We need the following definition.
\begin{defn} If $A = \{ a_1 < a_2 < \cdots < a_n\} \subset \omega = \{0,1,2,\ldots\}$,
$n \geq 2$, 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 exist a fixed $d\geq 1$ ($d$
depends only on the coloring) and arbitrarily large (finite) monochromatic sets
$A$ with $\gs(A) = d$.\label{vanhal}\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{vanhal} is somewhat similar in form to van der Waerden's theorem on
arithmetic progressions \cite{vanderwaerden1927}. (Van der Waerden's theorem says that for
every $k$, every finite coloring of the positive integers produces a monochromatic
$k$-term arithmetic progression.) However, Theorem \ref{vanhal} differs in a
number of ways:
Van der Waerden's theorem does not imply Theorem~\ref{vanhal}, since the $d$ in
the conclusion of Theorem~\ref{vanhal} 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{vanhal}. 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{vanhal} (which has a simple proof) does not imply van der Waerden's
theorem in a simple way. (In Chapter 14 of \cite{hindman+strauss1998}, Hindman and Strauss give
a proof that Fact 1 does in fact imply van der Waerden's theorem -- and at this
point in their book, the proof \emph{does} seem simple -- however, a fair amount
of machinery has been developed by this point.)
Theorem \ref{vanhal} 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 \emph{not} exist a fixed $d \geq 1$ and arbitrarily
large sets $A = \{ a_1 < a_2 < \cdots < a_n \} \subset X$ with $\gs(A) = d$. For
an example of such a set $X$, see \cite{bergelson+hindman+mccutcheon1998}.
Finally, no ``canonical version'' of this result is known. 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{vanhal}. This
is Corollary \ref{cologne} below.
A very brief sketch of an outline of a proof of the following result has
appeared in \cite{brown2003}. It seems worthwhile to fill in some of the missing
details.
\begin{thrm} For every $A\subset\omega$ (with $f$ as described in the introduction),
\[ \frac14\sqrt{|A|/\gs(A)} < |f(A)| < 4\sqrt{|A|\gs(A)} \]
\label{tewinkel}\end{thrm}
\begin{corl} 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.\label{cologne}\end{corl}
\begin{proof}[Proof of Corollary \ref{cologne}] If $16\gs(A) \leq |A|$, then
by Theorem \ref{tewinkel}, $1 < |f(A)| < |A|$.\end{proof}
To prove Theorem \ref{tewinkel}, we need the following definition.
\begin{defn} For $k\geq 0$, an \emph{aligned block} of size $4^k$ is a set
of $4^k$ consecutive non-negative integers whose smallest element is $m4^k$,
for some $m\geq 0$.\end{defn}
\begin{proof}[Proof of Theorem \ref{tewinkel}] 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{tewinkel}. 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 necessary 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^s$ has $2^s$ 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} For each $k \geq 0$, an two aligned blocks of size $4^k$
(consecutive or not) are either colored identically, or have no color
in common.\label{wuttke}\end{lmma}
\begin{proof}[Proof of Lemma \ref{wuttke}] 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\leq4^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 than each power of 2 which occurs
in $p4^k$. Thus the blocks $[p4^k, p4^k + 4^k - 1]$ and $[q4^k, 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{tewinkel}, we note that for
$k \geq 1$, 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{wuttke}, 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 so $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 \geq 1$, $k\geq 1$, 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
$p^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{wuttke} 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}\qedhere
\end{proof}
\section*{A bound for a van der Waerden function}
\begin{defn}For $m\geq 1$, 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) > \frac12m^2$.\end{thrm}
\begin{proof} For $k\geq1$, the coloring $f$ described in the introduction
colors the interval $[0,2^{2k+1} - 1]$ with $2^k$ colors. The colors are the
sums (including 0 as the empty sum) of distinct elements of the set $\{2^1,
2^3,2^5,\ldots,2^{2k-1}\}$. The color classes are subsets of the translates
(by the $2^k$ colors) of the set $S_k$ of sums (including 0 as the empty sum)
of distinct elements of the set $\{2^0,2^2,2^4,\ldots,2^{2k}\} = \{4^0,4^1,
4^2,\ldots,4^k\}$. It is easy to see that $S_k$ contains no 3-term arithmetic
progression. Hence, with respect to the coloring $f$, there is no monochromatic
3-term arithmetic progression in $[0,2^{2k+1}-1]$. The coloring $f$ shows that
for $k\geq1$, $w(3;2^k) > 2^{2k+1}$. 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+1} = \frac122^{2k+2}
< \frac12m^2$.
\end{proof}
\section*{Remarks}
\begin{enumerate}
\item The lower bound in Theorem 3 is not the best possible. Indeed, in the
standard reference Ramsey Theory (by R. L. Graham, B. L. Rothschild, and J. H.
Spencer, 2nd edition, 1990, John Wiley \& Sons, New York), the authors show
that for some positive constant $c$, $w(3;m) > m^{(c\log m)}$.
\item Of course, one would like to have an upper bound for the function $w(3;m)$.
The only bound known to me is $w(3;m) < \left(\frac{m}4\right)^{3^m}$ for $m>4$.
This bound comes from \cite{huang+yang2000}, and is mentioned in \cite{landman+robertson2004}. The coloring
$f$ on $[0,2^{2k+1}-1]$, with $2^k$ colors, is perhaps ``efficient'' in stopping
all monochromatic 3-term arithmetic progressions. Cutting the number of colors
in half would seem to leave too few colors. If this were in fact true, then
$w(3;2^{k-1}) \leq2^{2k+1}$ would follow, and for general $m$ one would then
have $\frac12m^2 < w(3;m) < 8m^2$.
\item Corollary \ref{cologne} shows that a constant/1-1 canonical version of
Theorem \ref{vanhal} is not true. We also know by the Bergelson/Hindman/McCutcheon
example that a density version of Theorem \ref{vanhal} is not true.
The following three simple examples, involving only 3-element sets, illustrate
various combinations of the truth or falsity of the ``constant/1-1 versions''
and the ``density versions.''
\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 this reselt 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 At the meeting, 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. 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: (i) Every set of positive integers with positive upper
density contains an element of $P$; (ii) 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.
\end{enumerate}
\item It would be nice to be able to say \emph{something} about general colorings
along the lines of Theorem \ref{vanhal}. Perhaps the following is true: if $\omega\to
\omega$ is an arbitrary coloring of $\omega$, then there exist a fixed $d\geq 1$ and
arbitrarily large (finite) sets $A$ with $\gs(A) = d$ such that either
\begin{enumerate}
\item at most $\sqrt{|A|}$ distinct colors appear in $g|_A$; or
\item each color appears in $g|_A$ at most $\sqrt{|A|}$ times.
\end{enumerate}
Note that for the particular coloring $f$, if we take $d = 1$, and let $A = [0,4^k-1]$,
then exactly $\sqrt{|A|}$ distinct colors appear in $f|_A$, and each color appears in
$f|_A$ exactly $\sqrt{|A|}$ times.
\item We have used a particular partition of $\omega$. We would get another partition
of $\omega$ (into infinitely many translates of an infinite set) by replacing the odd
powers of 2 and the even powers of 2 by arbitrary $A$ and $B$, where $\{A,B\}$ is
any partition of $\{1,2,3,\ldots\}$ into two infinite sets. Perhaps it's possible to
describe \emph{all} of the partitions of $\omega$ into infinitely many translates of
an infinite set.
\end{enumerate}
\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}