%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-20/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}

\title{A Pseudo Upper Bound for the van der Waerden Function
\footnote{Research supported in part by NSERC.}}
\author{Tom C. Brown\footnote{Department of Mathematics and Statistics,
¶¡ÏãÔ°AV, Burnaby, British Columbia, V5A 1S6, Canada.
\texttt{tbrown@sfu.ca}}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{A pseudo upper bound for the van der {Waerden} function}, J.
  Combin. Theory Ser. A \textbf{87} (1999), 233--238.}\bigskip\end{center}

\newcommand{\A}{\mathbf{A}}
\newcommand{\B}{\mathbf{B}}

\begin{abstract}For each positive integer $n$, let the set of all 2-colorings
of the interval $[1,n] = \{1,2,\ldots,n\}$ be given the uniform probability
distribution, that is, each of the $2^n$ colorings is assigned probability
$2^{-n}$. Let $f$ be any function such that $f(k)/\log k\to\infty$ as
$k\to\infty$. For convenience we assume that $f(k)2^k$ is always a positive
integer. We show that the probability that a random 2-coloring of $[1,f(k)2^k]$
produces a monochromatic $k$-term arithmetic progression tends to 1 as
$k\to\infty$. We call $f(k)2^k$ a \emph{pseudo upper bound} for the van der
Waerden function. We also prove the ``density version'' of this result.
\end{abstract}

\section{Introduction}

Let $w$ denote the van der Waerden function. By definition, for each integer
$k\geq1$, $w(k)$ is the smallest positive integer such that every 2-coloring
of the interval $[1,w(k)] = \{1,2,\ldots,w(k)\}$ produces a monochromatic
$k$-term arithmetic progression. (Equivalently, for every partition of
$[1,w(k)]$ into at most two parts, at least one part contains a $k$-term
arithmetic progression.)

The existence of $w(k)$, $k\geq1$, was proved by van der Waerden in 1927
\cite{vanderwaerden1927}. The best known lower bound for $w(k)$ is $w(k)
> (2^k/2ek)(1 + o(1))$ (see \cite{graham+rothschild+spencer1990}). For
$p$ prime, Berlekamp \cite{berlekamp1968} showed that $w(p+1)\geq p2^p$.
(For some related lower bounds, see \cite{alon+zaks1998,brown+hare1997,
nathanson1980}.) The best known upper bound (a ``wowzer'' function, as
described in \cite{graham+rothschild+spencer1990}) is due to Shelah
\cite{shelah1988}. R. L. Graham has offered \$1000 (see
\cite{graham+rothschild+spencer1990}) for a proof that
$w(k)<2^{2^{\cdot^{\cdot^{\cdot^2}}}}$, a tower of height $k$.

Let $f$ be any function such that $f(k)/\log k\to\infty$ as $k\to\infty$.
For convenience we assume that $f(k)2^k$ is always a positive integer.

In this note we show that ``almost all`` of the 2-colorings of $[1,
f(k)2^k]$ produce a monochromatic $k$-term arithmetic progression.

This means that if $S_k$ is the set of ``exceptional'' colorings, that
is, if $n_k = f(k)2^k$ and $S_k$ is the set of all 2-colorings of $[1,
n_k]$ for which there is no monochromatic $k$-term arithmetic
progression, then $|S_k|\cdot 2^{-n_k}\to0$ as $k\to\infty$.

We then say that $f(k)2^k$ is a \emph{pseudo upper bound} for the van der
Waerden function.

To illustrate the method, consider 2-colorings of the interval $[1,tk]$,
where $t = k2^k$, and let $T_k$ denote the set of all those 2-colorings
of $[1,tk]$ for which none of the $t$ intervals $[1,k]$, $[k+1,2k]$,
\ldots, $[(t-1)k+1,tk]$ is monochromatic. Then
\[ |T_k|\cdot2^{-tk} = (2^k - 2)^t\cdot2^{-tk} = \left(1 - \frac1{2^{k-1}}
\right) < e^{-2k}\to0 \text{ as } k\to\infty. \]

Therefore ``almost all'' of the 2-colorings of $[1,k^22^k]$ produce a
monochromatic $k$-term arithmetic progression; moreover, this monochromatic
progression is one the intervals $[1,k]$, $[k+1,2k]$,\ldots, $[(t-1)k+1,tk]$.

The proof of Theorem \ref{t1} below consists of a refinement of the above
simple argument, in order to reduce $k^22^k$ to $f(k)2^k$.

In the argument above, we used certain (pairwise disjoint) arithmetic
progressions with common difference 1. In the proofs of Theorems \ref{t1}
and \ref{t2}, we use certain progressions with common differences $1,k,
k^2,\ldots,k^s$, any two of which have at most one point in common.

Theorem \ref{t2} is the ``density version'' of Theorem \ref{t1}. (Note
that Theorem \ref{t1} follows from the case $\epsilon = 1/2$ of Theorem
\ref{t2}.)

\section{Results}

\begin{thrm}\label{t1} Let $f$ be any function such that $f(k)/\log k\to\infty$
as $k\to\infty$. For convenience we assume that $f(k)2^k$ is always a positive
integer. For each positive integer $n$, let the set of all 2-colorings of
$[1,n] = \{1,2,\ldots,n\}$ be given the uniform probability distribution, that
is, each of the $2^n$ colorings is assigned probability $2^{-n}$. Then the
probability that a random 2-coloring of $[1,f(k)2^k]$ produces a monochromatic
$k$-term arithmetic progression, tends to 1 as $k\to\infty$.\end{thrm}
\begin{proof} For each positive integer $k\geq2$, let $n_k=f(k)2^k$. Let $S_k$
denote the set of all those 2-colorings of $[1,n_k]$ which do \emph{not}
produce any monochromatic $k$-term arithmetic progression. We will show that
$\lim_{k\to\infty}|S_k|\cdot2^{-n_k}=0$.

Let $n=n_k=f(k)2^k$. Define the integer $s = s_k$ by $k^{2s}\leq n< k^{2s+2}$.
Let $n=k^sq + r$, $0\leq r<k^s\leq \sqrt{n}$.

Let us assume without loss of generality that $f(k)<k^2$. (The previous
discussion has already handled the case $f(k)\geq k^2$.)

Some easy calculations show that, as $k\to\infty$,
\[ \frac{s}k\frac{k^s}{2^k}\to0 \text{ and } \frac{s}k\frac{k^sq}{2^k}\to\infty. \]
These facts are used later in the proof.

The interval $[1,n]$ consists of $q$ consecutive intervals, $B_1,B_2,\ldots,B_q$,
each of length $k^s$, followed by a single interval of length $r$, $r<k^s$.

We wish to examine 2-colorings of the interval $B_1$. Let us identify $B_1$ (by
shifting it one unit to the left) with the interval $[0,k^s-1]$, and further
identify the interval $[0,k^s-1]$ with the set of $s$-tuples
\[ C = \{ x_0x_1\cdots x_{s-1} : 0\leq x_i\leq k - 1 \}, \]
under the correspondence $x_0x_1\cdots x_{s-1} \leftrightarrow\sum_{i=1}^{s-1} x_ik^i$.
That is, we identify each integer in $[0,k^s-1]$ with the $s$-tuple of the digits
in its $k$-ary expansion.

Under this identification, $B_1$ may be visualized as the $s$-dimensional
\emph{cube} $C$, $k$ units on a side. For our purposes, we say that a \emph{line}
in the cube $C$ is a set of the form
\[ \{x_0\cdots x_{j-1}yx_{j+1}\cdots x_{s-1}:0\leq y \leq k-1\}, \]
where the $x_i$'s are fixed. If the $j$th coordinate is the ``moving'' coordinate,
then the $k$ points in this line correspond to $k$ integers in $B_1$ which form
an arithmetic progression with common difference $k^j$.

There are $sk^{s-1}$ lines in the cube $C$. For each line $u$ in $C$, let $A_i$
denote the set of 2-colorings of $C$ for which the line $u$ is monochromatic. Then
$|A_u| = 2\cdot2^{k^s-k}$. Given any two distinct lines $u$ and $v$, $u$ and $v$
are either disjoint or meet in 1 point. In either case, $|A_u\cap A_v|=4\cdot
2^{k^s-2k}$. Therefore
\begin{align*}
\left|\bigcup_u A_u\right|
&\geq \sum_u |A_u| - \sum_{u,v}|A_u\cap A_v| \\
&= sk^{s-1}\cdot2\cdot2^{k^s-k} - \binom{sk^{s-1}}2\cdot4\cdot2^{k^s-2k} \\
&> 2^{k^s}\frac{s}k\frac{k^s}{2^k}
\end{align*}
for sufficiently large $k$, since $(s/k)(k^s/2^k)\to0$.

Let $z$ denote the number of colorings of the cube $C$ for which none of the
$sk^{s-1}$ lines in $C$ are monochromatic. Then (for sufficiently large $k$)
\[ z = 2^{k^s} - \left|\bigcup_u A_u\right| < 2^{k^s}\left(1 - \frac{s}k\frac{k^s}{2^k}\right). \]
The set $S_k$ defined at the beginning of the proof has $|S_k|\leq z^q2^r$,
so that
\[ |S_k|\cdot2^{-n} < \left(1 - \frac{s}k\frac{k^s}{2^k}\right)^q < e^{-(s/k)(k^sq/2^k)}. \]
Since $(s/k)(k^sq/2^k)\to\infty$ as $k\to\infty$, the proof is complete.
\end{proof}

\begin{thrm}\label{t2} Let $\epsilon$ be fixed, $0<\epsilon<1$. Let $f$ be any
function such that $f(k)/\log k\to\infty$ as $k\to\infty$. Let $n = f(k)\epsilon^{-k}$
(we assume that this is always an integer), and let $\A$ be a ``random $\epsilon n$-element
subset of $[1,n]$,'' which means that each element of $[1,n]$ belongs to $\A$ with
probability $\epsilon$. Then the probability that $\A$ contains a $k$-term arithmetic
progression, tends to 1 as $k\to\infty$.\end{thrm}
\begin{proof} The numbers $s$ and $r$ are defined as in the proof of Theorem \ref{t1}
(with $n$ now defined by $n = f(k)\epsilon^{-k}$), and again we write $n = k^sq + r$,
$0\leq r<k^s\leq\sqrt{n}$. Next, as $k\to\infty$,
\[ \frac{s}k k^s\epsilon^k\to0\text{ and } \frac{s}kk^s\epsilon^kq\to\infty. \]

(To see this it is convenient to show first that for any $\eta>0$, the inequalities
\[ \left(\frac12\log(1/\epsilon)-\eta\right)\frac1{\log k} < \frac{s}k < \left(\frac12\log(1/\epsilon) + \eta\right)\frac1{\log k} \]
hold for all sufficiently large $k$. For the right-hand inequality, one again needs
to assume that $f(k)<k^2$, and handle the case $f(k)>k^2$ by a separate argument,
as in the discussion in the Introduction.)

The cube $C$ is defined as before. Let $\B$ denote a random $\epsilon|C|$-element
subset of $C$, where each element of $C$ belongs to $\B$ with probability
$\epsilon$. Let $p_u = \Pr[u\subseteq\B] = \epsilon^k$, where $u$ is any one of
the $sk^{s-1}$ lines in $C$, and let $p_{uv} = \Pr[u\subseteq\B\text{ and }v
\subseteq\B]$, where $u$ and $v$ are distinct lines in $C$. Then $\Pr[u\subseteq
\B\text{ for some }u]\geq\sum_u p_u - \sum_{u,v}p_{uv}$.

Through each of the $k^s$ points of $C$ there are $s$ lines, and hence of the
$\binom{sk^s-1}2$ pairs of lines $\{u,v\}$, exactly $k^s\binom{s}2$ pairs meet,
and the other pairs are disjoint. Then
\begin{align*}
\sum_up_u - \sum_{u,v}p_{u,v}
&= \frac{s}kk^s\epsilon^k - k^s\binom{s}2\epsilon^{2k-1} - \left[\binom{sk^{s-1}}2 - k^s\binom{s}2\right]\epsilon^{2k} \\
&= \frac{s}kk^s\epsilon^k - k^s\binom{s}2\epsilon^{2k-1} - \frac12\frac{s}kk^s\epsilon^k\left(\frac{s}kk^s\epsilon^k-\epsilon^k\right) + k^s\binom{s}2\epsilon^k.
\end{align*}

The remaining inequalities hold for sufficiently large $k$.

Since $(s/k)k^s\epsilon^k-\epsilon^k<1/2$, we get
\[ \sum_up_u - \sum_{u,v}p_{u,v}>\frac34\frac{s}kk^s\epsilon^k - k^s\binom{s}2\epsilon^{2k-1}(1-\epsilon). \]

Since $\frac14(s/k)k^s\epsilon^k - k^s\binom{s}2\epsilon^{2k-1}(1-\epsilon)>0$, we get
\[ \sum_up_u - \sum_{u,v}p_{u,v}>\frac12\frac{s}kk^s\epsilon^k. \]

Finally, with $n = k^sq+ r$, if each element of $[1,n]$ belongs to $\A$ with
probability $\epsilon$, then
\[ \Pr[\text{no }u\subseteq\A] < \left(1 - \frac12\frac{s}kk^s\epsilon^k\right)^q < e^{-(1/2)(s/k)k^se^kq} \to 0. \]
\end{proof}

\section{Remarks}

Note that in the proofs, the only $k$-term progressions considered are (some of)
those whose common differences have the form $k^j$, where $0\leq j\leq s < 1 + (k\log2)
/(2\log k)$.

It would be desirable to get rid of the factor $f(k)$, if possible. To accomplish this,
evidently one needs to use a larger collection of $k$-term progressions. (Using all of
the $(s+1)^k-s^k$ combinatorial lines in the cube $C$, instead of just the $sk^{s-1}$
lines with one moving coordinate, does not lead us to an improvement in $f(k)$.)

Perhaps, by using a sufficiently large set of progressions, one could show that
$(1+\alpha)^k$ is a pseudo upper bound for the van der Waerden function, for every
$\alpha>0$.


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