%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-14/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{On the history of van der Waerden's theorem on arithmetic progressions}
\author{Tom C. Brown\footnote{Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada V3G 1G4. \texttt{tbrown@sfu.ca}}
and Peter Jau-Shyong Shiue\footnote{Department of Mathematical Sciences, University of Nevada, Las Vegas, NV, USA 89154-4020. \texttt{shiue@nevada.edu}}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown} and P.J.-S. {Shiue}, \emph{On the history of van der Waerden's theorem on arithmetic
progressions}, Tamkang J. Math. \textbf{32} (2001), no.~4, 335--341.}\bigskip\end{center}
\begin{abstract}In this expository note, we discuss the celebrated theorem
known as ``van der Waerden's theorem on arithemetic progressions,''
the history of work on upper and lower bounds for the function
associated with this theorem, a number of generalizations, and some
open problems.
\end{abstract}
\section{van der Waerden's theorem, and the function $w(k)$}
The famous theorem of van der Waerden on arithmetic progressions is usually
stated in the following way.
\begin{thrm} (van der Waerden 1927 \cite{vanderwaerden1927}). For every
positive integer $k$, there exists a positive integer $n$ such that if
the set $[1,n = \{1,2,\ldots,n\}]$ is partitioned into two subsets, then
at least one of the subsets must contain an arithmetic progression of
size $k$.\end{thrm}
(Recall that an arithmetic progression of size $k$ is a set of the form
$\{a,a+d,a+2d,\ldots,a~+~(k~-~1)d\}$, where $d>0$.)
This latter statement (with $r$ subsets instead of two subsets) is the
statement given in van der Waerden's original proof, which used a double
induction on $k$ and $r$. Van der Waerden's original proof was found with
the help of Artin and Schrier. See \cite{vanderwaerden1971} for a nice
description of how the proof was found, and of the proof itself.
Good expositions of this proof are given in the charming book by Khinchin
\cite{khinchin1998}, and in the book by Graham, Rothschild, and Spencer
\cite{graham+rothschild+spencer1990}. Other proofs of this statement can
be found in \cite{deuber1982,mills1983,taylor1982,anderson1976}. Perhaps
the easiest of these to read is \cite{mills1983}. A very short proof is
in \cite{graham+rothschild+spencer1990}. A topological proof is in
\cite{furstenberg+weiss1978}. An algebraic proof is in
\cite{bergelson+furstenberg+hindman+katznelson1989}.
For each positive integer $k$, we let $w(k)$ denote the \emph{smallest}
positive integer such that if the set $[1,w(k)]$ is partitioned into
two subsets, then at least one of the subsets must contain an arithmetic
progression of size $k$. The function $w(k)$ is often called the
\emph{van der Waerden function}.
One can use a simple backtrack procedure to find the exact value $w(k)$
for small values of $k$. The idea is, first of all, to replace a
partition of $[1,n]$ by a binary sequence of length $n$. The sequence 00110011,
for example, corresponds to the partition $\{1,2,5,6\},\{3,4,7,8\}$, as
illustrated in this diagram:
\[ \begin{array}{cccccccc} 1&2&3&4&5&6&7&8\\0&0&1&1&0&0&1&1 \end{array} \]
An arithmetic progression of size $k$ which is contained in one of the sets
of the partition then corresponds to $k$ equally space 0's or $k$ equally
spaced 1's. One then ``grows'' a maximal (i.e., non-extendable) binary
sequence which does not contain $k$ equally spaced 0's or 1's, by starting
with a 0, then at each stage adding a 0 at the end of the sequence if
possible (that is, if the addition of this 0 does not produce $k$ equally
spaced 0's). If adding a 0 is not possible, then one adds a 1, if possible.
If neither 0 nor 1 are possible, the given sequence is maximal. In this
case, one goes back and changes the latest 0 to a 1 (if this produces 3 equally
spaced 1's, then one goes back to the next preceding 0 and changes that
to a 1), and then continues to form another maximal sequence. This is
repeated, until the procedure requires the initial 0 to be changed to a
1; by symmetry, one can stop at this point. The length of the longest
binary sequence obtained in this way will be $w(k) - 1$.
For example, with $k = 3$ the first few maximal binary strings obtained
in this way are listed below. Each line ends when neither a 0 nor a 1
can be added to the string. Then the latest 0 is changed to a 1, and the
process continues on the next line. In the first line, a 0 cannot be
added because of the 0's in positions 2 and 5. (Adding a 0 would produce
3 equally spaced 0's in positions 2,5,8.) A 1 cannot be added in the first
line because of the 1's in positions 6 and 7. (Adding a 1 would produce
3 equally spaced 1's in the positions 6,7,8.) Then, the 0 in position 5
is changed to a 1, to begin the second line.
\[ \begin{array}{cccccccc} 1&2&3&4&5&6&7&8\\0&0&1&0&0&1&1\\0&0&1&0&1&1\\0&0&1&1&0&0&1&1\\\cdots \end{array} \]
This process will terminate in less than a page, to show that $w(3) = 9$.
a computer will find in a few seconds that $w(4) = 35$. Unfortunately,
this simple backtrack procedure takes far too long even for the case
$k=5$. A refinement \cite{stevens+shantaram1978} was used to show $w(5) = 178$;
the CPU time used was about 6 months. These values, together with $w(2) = 3$,
are the only known values of $w(k)$. G. Mills has pointed out that for these
known values, $w(k)$ is very close to $(3/2)k!$.
\section{Upper bounds on the van der Waerden function}
Every known proof of van der Waerden's theorem gives, at least implicitly,
an upper bound for the function $w(k)$. For example, if we let $w(k,r)$
denote the smallest value of $n$ such that in every partition of the interval
$[1,n]$ into $r$ subsets, at least one subset must contain an arithmetic
progression of size $k$, then the proof found in Khinchin's book gives $w(3)
= w(3,2) < 5\cdot(2\cdot2^5 + 1)$, $w(3,3) < 7\cdot(2\cdot3^7 + 1)(2\cdot
3^{7\cdot(2\cdot3^7 + 1)} + 1)$, \ldots, and then $w(4) = w(4,2) < 14\cdot(\frac32
w(3,2^{14})+\cdots)$.
We can see from the pattern of these bounds that the bound on $w(3,2^{14})$,
and hence the bound on $w(4)$, will involve a tower of exponents of height
$2^{14}$, very much larger indeed than $w(4) = 35$.
These bounds (and the bounds given by all other proofs prior to 1987) are
in fact so large that it was not known until 1987 whether or not $w(k)$
was a primitive recursive function. R. L. Graham for many years had a
standing offer of US \$1000 for a proof or disproof of the bound $w(k)
< 2^{2^{\cdot^{\cdot^{\cdot^2}}}}$, where there are $k$ 2's in this tower
of exponents.
In 1987 S. Shelah \cite{shelah1988} gave a completely new combinatorial
proof of van der Waerden's theorem which gave an upper bound for $w(k)$
which was tiny in comparison with earlier proofs. To describe the Shelah
upper bound, first define the sequence of numbers $n_1,n_2,\ldots$ by
$n_1 = 2$, $n_2 = 2^2 = 4$, $n_3 = 2^{2^{2^2}} = 2^{16} = 65536$,
$n_4 = 2^{2^{\cdot^{\cdot^{\cdot^2}}}}$, where this is a tower of 65536
2's, $n_5 = 2^{2^{\cdot^{\cdot^{\cdot^2}}}}$ where this is a tower of
$n_4$ 2's, and so on. Shelah showed that $w(k) < n_{k+2}$. Although
this was far weaker than $w(k) < 2^{2^{\cdot^{\cdot^{\cdot^2}}}}$,
Graham awarded him US \$500, and the original prize was still available.
In 1999, at a meeting in Budapest, on ``The Mathematics of Paul Er\H{o}s,''
Graham handed over a check for the full amount of US \$1000 to W. Timothy
Gowers, who had proved that $w(k) < 2^{2^{2^{2^{2^{k+9}}}}}$. At the same
time, Graham announced that he would now give US \$1000 for a proof or
disproof of the bound $w(k) < 2^{k^2}$.
Brown \cite{brown1999-1} showed that if one chooses a \emph{random} partition
of the interval $[1,(\log k)^22^k]$ into two subsets, then the probability
that at least one of these subsets contains an arithmetic progression of
size $k$ goes to 1 as $k\to\infty$. It is likely that this remains true for
the interval $[1,2^k]$.
\section{Lower bounds on the function $w(k)$}
A straightforward application of the ``probabilistic method,'' using also
the Lov\'asz Local Lemma, gives a lower bound of $(1 + o(1))(2^k/2ek) <
w(k)$, where $e = 2.718\ldots$. Here $o(1)$ is a function on $k$ which
converges to 0 as $k\to\infty$. For details see \cite{graham+rothschild+spencer1990}.
Zolt\'an Szab\'o \cite{szabo1990} improved this to: for every $\epsilon>0$,
$2^k/k^\epsilon < w(k)$ for all sufficiently large $k$.
By a constructive argument, Berlekamp \cite{berlekamp1968} showed that
for primes $p$, $p\cdot2^p < w(p+1)$.
It follows from Berlekamp's result that $\limsup w(k)/2^k = \infty$ as
$k\to\infty$. Paul Erd\H{o}s offered US \$25 for a proof that $\lim w(k)/2^k
= \infty$ as $k\to\infty$. This remains an attractive open question, and
the US \$25 prize still stands.
\section{Szemer\'edi's Theorem}
Szemer\'edi's theorem is the following statement:
\begin{thrm} (Szemer\'edi 1974 \cite{szemeredi1975}). For every $k\geq1$
and every $\epsilon>0$ there exists $n$ such that
\[ \left[\begin{array}{c} A\subseteq [1,n]\\|A|/n\geq\epsilon\end{array}\right] \implies
\left[\begin{array}{c}\text{$A$ contains an arithmetic}\\\text{progression of size $k$}\end{array}\right] \]
\end{thrm}
This clearly implies van der Waerden's theorem, for if $k$ is given and
we partition $[1,n]$ into two subsets, then at least one of them, call
it $A$, will have the property that $|A|/n \geq 1/2$. Taking $\epsilon
= 1/2$ in the above statement, if $n$ is large enough then $A$ must
contain an arithmetic progression of size $k$.
This statement was conjectured by Paul Erd\H{o}s and Paul Tur\'an in
1936. It was first proved for the case $k=3$ by Klaus Roth in 1952
\cite{roth1952}, using trigonometric sums. Then in 1974, Erd\H{o}s
offered US \$1000 for a proof of the general case. A proof for the
general case was found by Szemer\'edi in 1974 \cite{szemeredi1975}.
(This proof was called ``a masterpiece of combinatorial reasoning''
by Graham, Rothschild, and Spencer \cite{graham+rothschild+spencer1990}.)
The US \$1000 awarded to Szemer\'edi is the largest prize every collected
for an Erd\H{o}s problem.
In 1977 Furstenberg \cite{furstenberg1977} found an entirely different
proof, using ergodic theory.
In 1998 W. Timothy Gowers found another proof which (as mentioned above),
resulted in a sensational improvement of Shelah's upper bound for the
van der Waerden function $w(k)$. Gowers' proof used Fourier analysis
and probability theory, as well as combinatorics. His proof for the case
$k = 4$ is in \cite{gowers1998}. The proof for the general case has not
yet appeared.
Now for each positive integer $k$ and each positive real number $\epsilon$,
we let $Sz(k,\epsilon)$ denote the \emph{smallest} positive integer
such that
\[ \left[\begin{array}{c} A\subseteq [1,n]\\|A|/n\geq\epsilon\end{array}\right] \implies
\left[\begin{array}{c}\text{$A$ contains an arithmetic}\\\text{progression of size $k$}\end{array}\right] \]
The function $Sz(k,\epsilon)$ is called the \emph{Szemer\'edi function}.
\begin{thrm} (Gowers 1998). For every positive integer $k$ and every
positive real number $\epsilon$, $Sz(k,\epsilon) < 2^{2^{(1/\epsilon)^{2^{2^{k+9}}}}}$.
\label{t3}
\end{thrm}
Since for every partition of $[1,n]$ into two subsets, at least one of
the subsets, call it $A$, has $|A|/n \geq 1/2$, it follows from Theorem
\ref{t3} that $w(k) \leq Sz(k,1/2) < 2^{2^{2^{2^{2^{k+9}}}}}$.
\section{Other results and open questions}
Erd\H{o}s and Graham \cite{erdos+graham1980} observed that Szemer\'edi's
theorem implies the following result: If the set of all positive integers
is partitioned into arbitrarily many subsets (perhaps infinitely many),
then for every $k$ there is an arithmetic progression $P$ of size $k$
with the property that either $P$ is completely contained in one of
the subsets, or else $P$ intersects each subset in at most one element.
This result (called the \emph{canonical form of van der Waerden's theorem})
is often stated in the following way: If $f$ is an arbitrary function from
the positive integers to the positive integers, then there are arbitrarily
large arithmetic progressions $P$ such that the restriction of $f$ to $P$
is either constant or one-to-one.
Deuber, Graham, Pr\"omel and Voigt \cite{deuber+graham+promel+voigt1983}
proved the ``multi-dimensional version'' of the canonical version of van
der Waerden's theorem. Their proof makes use of Furstenberg and Katznelson's
multi-dimensional generalization of Szemer\'edi's theorem \cite{furstenberg+katznelson1978},
for which no elementary proof is yet known. (Furstenberg and Katznelson's
proof uses heavy ergodic tools.) Later, a combinatorial proof (of the
multi-dimensional version of the canonical form of van der Waerden's theorem)
was given by Pr\"omel and R\"odl \cite{promel+rodl1986} which did not use
Szemer\'edi's theorem.
One of Erd\H{o}s's most famous conjectures, for which he offered US \$3000,
and later US \$5000, is the following. Let $A$ be a set of positive integers
such that $\sum_{n\in A} \frac1n = \infty$. Then for every $k$, $A$ must contain
an arithmetic progression of size $k$. This statement, if true, is stronger
than Szemer\'edi's theorem. It still remains open, even for $k = 3$.
Erd\H{o}s offered US \$10,000 for an explicit asymptotic formula for the
function $g(n)$, where $g(n) = \max\{|A|:A\subseteq [1,n] \text{ and $A$
contains no arithmetic progression of size $k$}\}$. Again, Szemer\'edi's
theorem implies that $g(n,k)/n\to 0$ as $n\to\infty$.
One can also allow $k$ to depend on $n$, and Erd\H{o}s offered US \$100
to settle the question of whether or not $g(n,\log n)/n\to1$ as $n\to\infty$.
This was settled in the affirmative by Brown and Freedman \cite{brown+freedman1989-1},
who proved that for all $k\geq4$, $g(n,k)\geq n - (12n\log n)/(k\log k)$.
With $k = \log n$, this gives $g(n,\log n) \geq n - (12n)/(\log\log n)$.
They also noted that the statement $g(n, \log\log n)/n\to1$ as $n\to\infty$
implies Szemer\'edi's theorem, and showed that $Sz(p,1/e) > p^p$ for every
prime number $p\geq7$.
It would be interesting to know the exact value of $g(n^2,n)$ It is known
(see \cite{brown+freedman1989-1,truss1991} that $n^2 - n(1 + o(1)) <
g(n^2,n) < n^2 - 2n(1 + o(1))$).
See also
\begin{itemize}
\item \url{http://www.mathsoft.com/asolve} (an excellent site with many interesting links)
\item \url{http://math.ucsd.edu/\~fan} (Fan Chung Graham's web page)
\item \url{http://www.integers-ejcnt.org} (Integers: the Electronic Journal of Combinatorial Number Theory)
\item \url{http://www.combinatorics.org} (The Electronic Journal of Combinatorics)
\item \url{http://can.dpmms.cam.ac.uk/\~wtg10} (W. T. Gowers' home page)
\item \url{http://www-groups.dcs.st-andrews.ac.uk/\~history/Mathematicians/Erdos.html} (biography of Paul Erd\H{o}s and links to other Erd\H{o}s sites)
\end{itemize}
\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}