%%%% 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, ÓÈÎïÊÓƵ, 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}