%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-52/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{cor}{Corollary}
\newtheorem*{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{fact}{Fact}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem*{remark}{Remark}
\newtheorem*{ack}{Acknowledgements}


\title{Common Transversals}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{On van der Waerden's theorem and a theorem of Paris and
  {Harrington}}, J. Combin. Theory Ser. A \textbf{30} (1981), 108--111.}\bigskip\end{center}

\begin{abstract}
A $2$-coloring of the non-negative integers and a function $h$ are given such that if $P$ is any monochromatic arithmetic progression with first term $a$ and common difference $d$ then $|P| \leq h(a)$ and $|P| \leq h(d)$. In contrast to this the following result is noted. For any $k$, $f$ there is $n = n(k,f)$ such that whenever $n$ is $k$-colored there is a monochromatic subset $A$ of $n$ with $|A| > f(d)$, where $d$ is the maximum of the differences between consecutive elements of $A$.
\end{abstract}

\section{Introduction} \label{sec: 1}

Paris and Harrington~\cite{paris+harrington1978} have shown that the following simple modification of the finite version of Ramsey's theorem, which can be deduced from the infinite version by a diagonalization argument, is not provable in Peano's first order axioms, even in the case where $f$ is the identity function: Let $r,k \in \omega$, $f \in \omega^\omega$ be given. Then there is $n = n(k,r,f)$ such that whenver $[n]^r$ is $k$-colored there is a subset $A$ of $n$ with $[A]^r$ monochromatic and $|A| > f(a_0)$, where $a_0$ is the smallest element of $A$.

It seems natural to ask whether van der Waerden's theorem on arithmetic progressions can be modified in the sam way. That is, given $k \in \omega$, $f \in \omega^\omega$, must there exist $n = n(k,f)$ such that whenever $n$ is $k$-colored there is a monochromatic arithmetic progression $P = \{a,a + d, a + 2d, \dots\}$ contained in $n$ such that $|P| > f(a)$ or $|P| > f(d)$?

Fact~\ref{fact 1} below shows that this question has a negative answer. In contrast to this we quote a result (Fact~\ref{fact 3}) which shows that if ``arithmetic progression with common difference $d$" is replaced by ``set with maximum difference between consecutive elements equal to $d$" then the corresponding question has an affirmative answer (Furthermore, this result has a simple inductive proof.)

\section{The nagative result concerning arithmetic progressions} \label{sec: 2}

\begin{fact} \label{fact 1}
There is a $2$-coloring of $\omega$ and a function $h$ such that if $P = \{a, a+d,\dots\}$ is any monochromatic arithmetic progression then $|P| \leq h(a)$ and $|P| \leq h(d)$.
\end{fact}

In what follows, the notation $\bar{z}$ will be used for the fractional part of $z$, i.e., $\bar{z} = z - \lfloor z \rfloor$ for real numbers $z$. Intervals in $\omega$ of the form $[2^k,2^{k + 1})$ (as well as the set $\{0\}$) will be referred to as ``blocks." Three obvious lemmas will be used.

\begin{lemma} \label{lemma: 1}
If $n$ multiples of $d'$ are contained in $[2^k,2^{k + 1})$ then at least $2n - 1$ multiples of $d'$ are contained in $[2^{k + 1}, 2^{k + 2})$.
\end{lemma}

\begin{lemma} \label{lemma: 2}
Given integers $a \geq 0$ and $d \geq 2$, let $d' = 2^{p + 1} d$ if $a \in [2^p, 2^{p + 1})$, $d' = d$ if $a = 0$. Then for each $m \in \omega$, both $md'$ and $a + md'$ belong to the same block.
\end{lemma}

\begin{lemma} \label{lemma: 3}
Let $x,y$ be real with $y$ irrational. Let $n,s,t \in \omega$ with $n \geq 2$, $s \geq 2n-1$, $t \geq 2s - 1$. Let $S_1 = \{\overline{x + my}: m \in [0,n)\}$, $S_2 = \{\overline{x + my}: m \in [n, n + s)\}$, $S_3 = \{\overline{x + my}: m \in [n + s, n + s + t)\}$. Then it is impossible to have simultaneously $S_1 \subset [0,1/2)$, $S_2 \subset [1/2,1)$, $S_3 \subset [0,1/2)$. (The same conclusion hods if $[0,1/2)$ and $[1/2,1)$ are interchanged.)
\end{lemma}

Now we define a ``preliminary $2$-coloring of $\omega$. Let $\alpha > 0$ be fixed and irrational, and define $c_1: \omega \mapsto \{0,1\}$ by $c_1(n) = 0$ if $\overline{n\alpha} \in [0,1/2)$, $c_1(n) = 1$ if $\overline{n\alpha} \in [1/2,1)$. Suppose that $P = \{a,a+d,\dots\}$ is a monochromatic (with respect to $c_1$) arithmetic progression with common difference $d$ (and first term $a$). It follows immediately from the density in $[0,1]$ of the set $\{\overline{md\alpha}: m \in \omega\}$ (and from the density in $[0,1]$ of any translate of this set by $\overline{a\alpha}$ (modulo 1)) that there is $f(d)$ such that $|P| \leq f(d)$, independent of $a$.

We are now ready to define the 2-coloring $c: \omega \mapsto \{0,1\}$ whose existence is asserted in Fact~\ref{fact 1}. The colroing $c$ is obtained by starting out with the coloring $c_1$ and then ``reversing" this coloring on alternate blocks. That is, let $c_2(n) = 1 - c_1(n)$ and define, for $n \in [2^k,2^{k + 1})$, $c(n) = c_1(n)$ if $k$ is odd, $c(n) = c_2(n)$ is $k$ is even. (Set $c(0) = c_1(0) = 0$.)

Let $P = \{a, a + d,\dots\}$ be any arithmetic progression which is monochromatic with respect to the coloring $c$. We show first that $|P|$ is bounded by a function of $d$, and then that $|P|$ is bounded by a function of $a$. 

To show that $|P|$ is bounded by a function of $d$, let $f(d)$ be as above and choose $k$ so that $2^k \leq df(d) < 2^{k + 1}$. If $P$ intersects both $[0,2^{k + 1})$ and $[2^{k + 2}, \infty)$, the block $[2^{k + 1}, 2^{k + 2})$ will contain more than $f(d)$ consecutive terms of $P$. (This follows from Lemma~\ref{lemma: 1} and $f(d) \geq 2$.) Since $c$ agrees on $[2^{k + 1}, 2^{k + 2})$ with either $c_1$ or $c_2$, this contradicts the definition of $f(d)$. Hence either $P \subset [2^{k + 1}, \infty)$ or $P \subset [0,2^{k + 2})$. In the first case one gets $|P| \leq 2f(d)$, and in the second case $|P| \leq 2^{k + 2}/d + 1\leq 4f(d) + 1$.

Next, to show that $|P|$ is bounded by a function of $a$, we shall derive a contradiction by assuming that $|P| \geq 32 \cdot 2^{p + 1} + 1$ if $a \in [2^p, 2^{p + 1})$ and $|P| \geq 33$ if $a = 0$.

Let $d'$ be as in Lemma~\ref{lemma: 2}, and consider the progressions $P' = \{a + d', a + 2d', \dots,a + 32d'\}$, $P'' = \{d', 2d', \dots,32d'\}$. Choose $k$ so that $2^k \leq 4d' < 2^{k + 1}$, and let $A = [2^, 2^{k + 1})$, $B = [2^{k + 1}, 2^{k + 2})$, $C = [2^{k + 2}, 2^{k + 3})$. We say that $4d'$ belongs to ``block $A$." Now $2d' \in [2^{k -1}, 2^k)$, hence (applying Lemma~\ref{lemma: 1} if necessary) it is clear that block $A$ contains $n$ consecutive elements of $P''$, where $n \geq 2$. Since by Lemma~\ref{lemma: 2} the elements of $P'$ are distributed among the various blocks in exactly the same way as are the corresponding elements of $P''$, we obtain that the blocks $A,B,C$ contain respectively $n,s,t$ elements of $P'$, where $n \geq 2$, $s \geq 2n - 1$, $t \geq 2s - 1$. (Note that the progression $P'$ extends beyond block $C$ since $2^{k + 3} \leq 32d'$.)

Now let $a + ud'$ be the first element of $P' \cap (A \cup B \cup C)$, and let $x = (a + ud')\alpha$, $y = d'\alpha$. Since $P'$ is monochromatic with respect to $c$, the first $n$ terms, next $s$ terms, next $t$ terms, of the sequence $(\overline{x}, \overline{x + y}, \overline{x + 2y}, \dots)$ must be contained respectively in the intervals $[0,\frac{1}{2})$, $[\frac{1}{2}, 1), [0,\frac{1}{2})$ (or in $[\frac{1}{2},1)$, $[0,\frac{1}{2})$, $[\frac{1}{2}, 1)$), finally contradicting Lemma~\ref{lemma: 3}.

This completes the proof of Fact~\ref{fact 1}; for the function $h$ we can take $h(x) = \max\{4f(x) + 1, 64x\}$.

\section{The positive result concerning sets with given gap size} \label{sec: 3}

Although the results noted here are not new, Fact~\ref{fact 3} provides an interesting contrast to the negative result above. The proofs are omitted. Fact~\ref{fact 3}, the finite version of Fact~\ref{fact 2}, can be proved by a simple induction on the number of colors. 

Let $A = \{a_1,\dots,a_m\}$ be a finite subset of $\omega$, with $a_1< \cdots < a_m$. Define $gs(A)$, the ``gap size" of $A$, by $gs(A) = \max\{a_{j + 1} - a_j: 1 \leq j < m\}$ if $|A| > 1$ and $gs(A) = 1$ if $|A| = 1$.

\begin{fact} \label{fact 2}
Let $k \in \omega$ and a $k$-coloring of $\omega$ be given. Then there exist $d \in \omega$ and arbitrarily large (finite) monochromatic sets $A$ with $gs(A) = d$.
\end{fact} 

\begin{fact} \label{fact 3}
Let $k \in \omega$, $f\in \omega^\omega$ be given. Then there is $n$ such that if $n$ is $k$-colored there is a monochromatic subset $A$ of $n$ with $|A| > f(gs(a))$.
\end{fact}

We remark that if $n(k,f)$ is the smallest such $n$, then $n(1,f) \leq 1 + f(1)$ and $n(k,f) \leq 1 + kf(n(k-1,f))$. (Letting $e$ denote the identity function, this gives $n(k,e) \leq k!(1 + 1/1! + \cdots + 1/k!)$, while in fact $n(k,e) = k^2 + 1$; hence the above bound is far from best possible.) 

\begin{ack} The author is grateful to Paul Erd\H{o}s and Bruce Rothschild for suggesting the present 2-coloring or $\omega$, which greatly improved his original 4-coloring, which in turn was based on an idea of I. Connell and N. Mendelsohn~\cite{mendelsohn1974}. Fact~\ref{fact 3} was first noted by J. Justin~\cite{justin1971} as the finite version of Fact~\ref{fact 2}~\cite{brown1969}.
\end{ack}

\emph{Note added in proof.} The author completely overlooked Justin's very different construction (\cite{justin1971}--long before the Paris and Harrington result) of a 2-coloring of $\omega$ such that any arithmetic progression $P$ with common difference $d$ has $|P|$ bounded by a function of $d$, namely, for each $n \geq 1$, let $n! = 2^tq$, $q$ odd, and define $c(n) = 0$ if $t$ is even, $c(n) = 1$ if $t$ is odd.

\nocite{graham+rothschild1974,vanderwaerden1927}


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