%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-12/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{defn}[thrm]{Definition}

\title{On the canonical version of a theorem in Ramsey Theory}
\author{Tom C. Brown \\
Department of Mathematics\\
Simon Fraser University\\
Burnaby, BC Canada V5A 1S6\\
tbrown@sfu.ca}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{On the canonical version of a theorem in Ramsey theory}, Special
  Issue on Ramsey Theory, Combinatorics, Probability and Computing \textbf{12}
  (2003), 513--514.}\bigskip\end{center}

\begin{abstract}
We show that the constant colorings and the one-to-one colorings are
insufficient for a canonical version of a certain theorem in Ramsey theory.\\
~\\
Key phrases: van der Waerden's theorem, arithmetic progression, piecewise syndetic, Ramsey Theory
\end{abstract}

\section{Results}

\begin{defn}
If $A=\{a_{1}<a_{2}<...<a_{n}\}\subset \omega =\{0,1,2,...\},$ $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 coloured, there exist a \emph{\ }fixed $d\geq 1$ ($d
$ depends only on the colouring) and arbitrarily large monochromatic sets $A$
with $gs(A)=d.$
\end{thrm}

This fact first appeared in \cite{brown1968}. Various applications appear in
\cite{brown1971-1,deluca+varricchio1998,hindman+strauss1998,lallement1979,
straubing1982}.

\begin{defn}
The colouring $f:\omega \rightarrow \omega $ is defined by writing each
number $n$ in binary and then projecting onto the odd powers of two.
Explicitly, if $n=\sum\limits_{i\text{ odd}}\epsilon _{i}2^{i}$ $+$ $
\sum\limits_{j\text{ even}}\epsilon _{j}2^{j}$ , then $f(n)=\sum\limits_{i%
\text{ odd}}\epsilon _{i}2^{i}.$ (By default, $f(0)=0.$)
\end{defn}

\begin{thrm}\label{eee}
For every $A\subset \omega $ (with $f$ as above),
\[
\sqrt{|A|/8gs(A)}<|f(A)|<\sqrt{8|A|gs(A)}.
\]
\end{thrm}

According to Theorem \ref{eee}, there clearly do not exist a fixed $d$ and
arbitrarily large sets $A$ with $gs(A)=d$ such that either $|f(A)|=1$ or $%
|f(A)|=|A|.$

\begin{defn}
For $k\geq 0,$ an \emph{aligned block }of size\emph{\ }$2^{k}$ (respectively
$4^{k}$) is a set of $2^{k}$ (respectively $4^{k}$) consecutive non-negative
integers whose smallest element is $m2^{k}$ (respectively $m4^{k}$), for
some $m\geq 0.$
\end{defn}

\textbf{Proof of Theorem \ref{eee}} The following facts follow directly from the
definition of the colouring $f.$

Each aligned block of size $4^{k}$ has exactly $2^{k}$ colours, each
appearing $2^{k}$ times.

Consecutive aligned blocks of size $4^{k}$ are either identical or have no
colour in common.

Every set of $4^{s}$ consecutive non-negative integers has at least $2^{s}$
colours. Hence every set of $4^{s}$ consecutive aligned blocks of size $%
2^{k} $ has at least $2^{s}$ aligned blocks of size $2^{k}$, no two of which
have a common colour.

Now let $A\subset \omega .$

Choose $s$ minimal so that $A$ is contained in the union of two aligned
blocks of size $4^{s}.$ (Two blocks are needed in case $A$ contains $4^{k}-1$
and $4^{k}.$) Then $4^{s-1}<|A|gs(A)$, hence $|f(A)|\leq 2\cdot 2^{s}<2\sqrt{%
2|A|gs(A)}$.

Next, given $A\subset \omega $, choose $k$ so that $2^{k-1}<gs(A)\leq 2^{k}$
, and choose $t$ minimal so that $A$ is contained in the union of $t$
consecutive aligned blocks of size $2^{k}$. By the choice of $k,$ $A$
intersects each of these $t$ blocks. Let $4^{s}\leq t<4^{s+1}$. Since $2^{s}$
of these blocks have no colours in common, $2^{s}\leq |f(A)|.$ Hence $%
|A|\leq t2^{k}<4\cdot 4^{s}\cdot 2\cdot 2^{k-1}<8|f(A)|^{2}gs(A)$, or $\sqrt{%
|A|/8gs(A)}<|f(A)|$.

\section{Acknowledgement}

The author thanks the referee for substantial improvements in the bounds and
the proofs.


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

