%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-11/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}{Definition}
\newtheorem{conj}{Conjecture}

\title{Monochromatic structures in colorings of the positive integers and the finite subsets of the positive integers}
\author{Tom Brown\footnote{Department of Mathematics, ΄σΟσ΄«Γ½, Burnaby, BC, Canada V5A 1S6. \texttt{tbrown@sfu.ca}.}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Monochromatic structures in colorings of the positive integers
  and the finite subsets of the positive integers}, 15th MCCCC (Las Vegas, NV,
  2001). J. Combin. Math. Combin. Comput. \textbf{46} (2003), 141--153.}\bigskip\end{center}

\begin{abstract}We discuss van der Waerden's theorem on arithmetic progressions
and an extension using Ramsey's theorem, and the canonical versions. We
then turn to a result (Theorem \ref{t11-6} below) similar in character
to van der Waerden's theorem, applications of Theorem \ref{t11-6}, and
possible canonical versions of Theorem \ref{t11-6}. We mention several
open questions involving arithmetic progressions and other types of
progressions.
\end{abstract}

\section{van der Waerden's theorem on arithmetic progressions}

One of the great results in combinatorics is the following theorem.

\begin{thrm}\label{t11-1} (van der Waerden's theorem on arithmetic
progressions) If $N$ is finitely colored (= finitely partitioned)
then some color class (= cell of the partition) contains arbitrarily
large arithmetic progressions $P = \{ a,a+d,a+2d,\ldots,a+(n-1)d\}$.
\end{thrm}

Van der Waerden's original proof is in \cite{vanderwaerden1927}. The most famous proof
(essentially van der Waerden's own proof) is in \cite{khinchin1998}. See also
\cite{vanderwaerden1971}. The shortest proof is in \cite{graham+rothschild+spencer1990}. The clearest proof is
probably in \cite{mills1983}. A topological proof can be found in \cite{furstenberg+weiss1978}.
For other proofs, see \cite{anderson1976,bergelson+furstenberg+hindman+katznelson1989,
compton1999,deuber1982,promel+rodl1986,promel+rothschild1987,shelah1988,taylor1982,walters2000}.

The ''canonical'' version of van der Waerden's theorem is the following,
due to Erd\H{o}s and Graham \cite{erdos+graham1980}.

\begin{thrm}\label{t11-2} Given $f:N\to\omega = \{0,1,2,\ldots\}$,
there exist arbitrarily large arithmetic progressions $P$ such that
$f|_P$ is either constant or 1-1.\end{thrm}

An equivalent form of van der Waerden's theorem is the following.

\begin{thrm}\label{t11-3} For all $k\geq1$ there exists a (smallest)
$\omega(k)$ such that every 2-coloring of $[1,\omega(k)]$ produces a
monochromatic $k$-term arithmetic progression.\end{thrm}

Using the definition of $\omega(k)$ from the preceding theorem, the
only known values of $\omega(k)$ are $\omega(1) = 1$, $\omega(2) = 3$,
$\omega(3) = 9$, $\omega(4) = 35$, $\omega(5) = 178$. For values involving
more than two colors, see \cite{bate+skillicorn1981,beeler+oneil1971,
chvatal1970,huang+yang2000,stevens+shantaram1978}.

Berlekamp \cite{berlekamp1968} showed in 1961 that $k2^k<\omega(k+1)$ if $k$ is prime.

Erd\H{o}s asked in 1961 whether or not $\lim_{k\to\infty}\frac{\omega(k)}{2^k}
=\infty$, and offered US \$25 for an answer. This question is still open,
and the prize is still available.

Szabo \cite{szabo1990} showed in 1990 that $\frac{2^k}{k^\epsilon} < \omega(k)$,
$k>k(\epsilon)$.

Gowers showed in 1998 \cite{gowers1998,gowers2001} that $\omega(k) < 2^{2^{2^{2^{2^{k+9}}}}}$.

Graham asked in 1998 whether $\omega(k) < 2^{k^2}$, and offers US \$1000 for
an answer.

Using Ramsey's theorem, the following ``extended'' van der Waerden's theorem
can be proved.

\begin{thrm}\label{t11-4} (Extended van der Waerden's theorem) If $P_f(\mathbb{N})$
(the collection of all finite subsets of $\mathbb{N}$) is finitely colored,
then for every $n\geq1$ there exist an infinite set $Y\subseteq\mathbb{N}$ ($Y$
depends on $n$) and an arithmetic progression $\{a,a+d,a+2d,\ldots,a+(n-1)d\}$
such that the set $[Y]^a\cup[Y]^{a+d}\cup[Y]^{a+2d}\cup\cdots\cup[Y]^{a+(n-1)d}$
is monochromatic. (Here $[Y]^k$ denotes the set of all $k$-element subsets of
$Y$.)\end{thrm}

\begin{proof}Let $g:P_f(\mathbb{N})\to[1,r]$ be an $r$-coloring of $P_f(\mathbb{N})$.
Let $n$ be given. By van der Waerden's theorem, choose $m$ large enough that
every $r$-coloring of $[1,m]$ produces a monochromatic $n$-term arithmetic
progression. Using Ramsey's theorem, choose infinite sets $X_1,X_2,\ldots,X_m$
in turn so that $Y = X_m\subseteq X_{m-1}\subseteq\cdots\subseteq X_2\subseteq X_1
\subseteq\mathbb{N}$ and $g$ is constant on each of $[X_k]^k$, $1\leq k\leq m$.
($[X_k]^k$ denotes the set of all $k$-element subsets of $X_k$.) Let us suppose
that (for each $k$) $g(A) = a_k$ for all $A$ in $[X_k]^k$.

Let $h:[1,m]\to[1,r]$ be defined by setting $h(k)=a_k$, $1\leq k\leq m$. By the
choice of $m$, there exist positive integers $a,d$ such that $h(a) = h(a+d)
= h(a+2d) = \cdots = h(a + (n-1)d)$. This means that $g$ is constant on the
set $[Y]^a\cup[Y]^{a+d}\cup[Y]^{a+2d}\cup\cdots\cup[Y]^{a+(n-1)d}$, and the
proof is complete.\end{proof}

The following was pointed out by Shi Lingsheng, a student of Hans Juergen
Proemel: Suppose $X$ is any finite collection of subsets of $\mathbb{N}$
such that every finite coloring of $\mathbb{N}$ produces arbitrarily large
monochromatic elements of $X$. Then for every finite coloring of $P_f(\mathbb{N})$
and every $n$, there exists an infinite set $Y$ ($Y$ depends on $n$) and an
element $A$ of $X$ of size $n$, such that $\bigcup [Y]^x$ is monochromatic,
where the union is over all $x$ in $A$. The proof is exactly as above. Thus
for example, using Folkman's theorem, for every finite coloring of $P_f(\mathbb{N})$
and every $n$, there exists an infinite set $Y$ ($Y$ depends on $n$) and
distinct positive integers $a_1,a_2,\ldots,a_n$ such that $\bigcup [Y]^x$ is
monochromatic, where the union is over all $x$ such that $x$ is a sum of
distinct $a_1,a_2,\ldots,a_n$.

It would be of interest to find a canonical version of Theorem \ref{t11-4}.
(One would likely need to use the canonical version of van der Waerden's theorem
above, as well as the canonical version of Ramsey's theorem.)

This has not yet been done. However, one can get a canonical theorem (Theorem
\ref{t11-5} below) for a structure somewhat smaller (but still very large!)
than $[Y]^a\cup[Y]^{a+d}\cup[Y]^{a+2d}\cup\cdots\cup[Y]^{a+(n-1)d}$.

From the set $[Y]^a\cup[Y]^{a+d}\cup[Y]^{a+2d}\cup\cdots\cup[Y]^{a+(n-1)d}$
one can easily construct a forest $F$ with the following properties:
\begin{enumerate}
\item Each vertex of $F$ is a finite subset of $Y$.
\item $F$ has $n$ levels, and each vertex at a level $i$ has $a+id$ elements,
$0\leq i\leq n-1$.
\item Vertex $y$ at level $i+1$ covers vertex $x$ at level $i$ iff $x\subset
y$.
\item If $y,z$ cover $x$ then $y\cap z = x$.
\item Each element of $Y$ appears in at most one tree of the forest $F$.
\item Each vertex not at level $n-1$ has infinitely many immediate successors.
\item $F$ is the union of infinitely many non-empty trees.
\end{enumerate}
Let us call such a structure an ``arithmetic $\omega$-forest of height $n$.''

Diana Piguetova, a student of Jarik Ne\u{s}et\u{r}il, has proved the following
result.

\begin{thrm}\label{t11-5} If $g:P_f(\mathbb{N})\to\omega$ is an arbitrary
coloring, then for every $n\geq 1$ there exists an arithmetic $\omega$-forest
$F$ of height $n$ on which the coloring $g$ has one of the following patterns:
\begin{enumerate}
\item $g|_F$ is constant.
\item Each tree is monochromatic, and different trees have different colors.
\item Each level in the whole forest is monochromatic, all of different colors.
\item Each level in each tree is monochromatic, all of different colors.
\item $g|_F$ is 1-1.
\end{enumerate}\end{thrm}

\section{A theorem involving ``almost arithmetic progressions''}

Van der Waerden's theorem guarantees large arithmetic progressions, but says
nothing about the common difference of these progressions. In fact, Beck
\cite{beck1980} showed that there exists a 2-coloring of $\mathbb{N}$ such that
for all large $d$, there do not exist large monochromatic arithmetic progressions
with common difference $d$ --- in fact if $P$ is a monochromatic arithmetic
progression with common difference $d$, then $|P|<2\log d$.

In the opposite direction, there exists a 2-coloring of $\mathbb{N}$ for which
there does not even exist a monochromatic 4-term arithmetic progression $\{a,
a+d,a+2d,a+3d\}$ with $d>a/3$. (The 1/3 here cannot be replaced by 1/32.)
See \cite{brown+landman1999}.

The next theorem, first proved in \cite{brown1968} (see also \cite{brown1971-1}), shows
that one can control the common difference, but at the expense of not
insisting on an arithmetic progression.

\begin{thrm}\label{t11-6} for every finite coloring of $N$, there exist a
fixed $d$ and arbitrarily large monochromatic sets $A=\{a_1<a_2<a_3<\cdots<
a_n\}$ with $\max\{a_{j+1}-a_j|j=1,2,\ldots,n-1\} = d$.\end{thrm}

Note that when $A$ is very large compared to $d$, then the elements of $A$
are approximately equally spaced, so we might call $A$ an ``almost arithmetic
progression.''

Theorem \ref{t11-6} differs from van der Waerden's theorem in a number of
ways:
\begin{enumerate}
\item It does not directly imply, and is not directly implied by, van
der Waerden's theorem.
\item It does not have a ``density version.'' (See \cite{bergelson+hindman+mccutcheon1998} for example.)
\item It has an extremely simple proof, by induction on the number of colors.
\item The $d$ in the conclusion is fixed.
\item No canonical version is known.
\end{enumerate}
An application of Theorem \ref{t11-6} is the following result, proved in
\cite{brown1968,brown1971-1}.

\begin{thrm}\label{t11-7} Let $S$,$T$ be semigroups and let $\varphi:S\to T$
be a homomorphism. Assume that $T$ is locally finite, and that for every
idempotent $e$ in $T$, $\varphi^{-1}(e)$ is locally finite. Then $S$ is
locally finite.\end{thrm}

(For groups, this is an old theorem of O. Schmidt: A locally finite
extension of a locally finite group is locally finite.)

\begin{proof}[Sketch of proof] Some simple considerations reduce the proof
to the following case. Let $\varphi:S\to G$, where $G$ is a finite group,
and assume that $\varphi^{-1}(e)$ is locally finite. Assume that $S$ is
generated by $W = \{ w_1,w_2,\ldots,w_t \}$. It is necessary to show
that $S$ is finite. It suffices for this (by a simple compactness argument)
to show that every \emph{sequence} $s=x_1x_2x_3\ldots$ of elements of $W$
contains a ``contractible'' factor $x_{j+1}x_{j+2}\cdots x_{j+k}$, that
is, a factor $x_{j+1}x_{j+2}\cdots x_{j+k}$ which equals the product of
fewer than $k$ elements of $W$.

Define the finite coloring $f$ of $\mathbb{N}$ by $f(m)=\varphi(x_1x_2\cdots
x_m)$ for all $m\in\mathbb{N}$. Then, by Theorem \ref{t11-6}, we have a
\emph{fixed} $d$ and, for every $n$, a monochromatic set $A=\{a_1<a_2<a_3<
\cdots<a_n\}$ with $\max\{a_{j+1}-a_j|j=1,2,\ldots,n-1\} = d$.

Define $g_1 = x_1\cdots a_1$, $g_2=x_{a_1+1}\cdots x_{a_2}$, $g_3=
x_{a_2+1}\cdots x_{a_3},\ldots,x_{a_{n-1}}\cdots x_{a_n}$.

Then $f(a_1) = f(a_2) = \cdots = f(a_n)$ means $\varphi(g_1) = \varphi(g_1g_2)
= \varphi(g_1g_2g_3) = \cdots = \varphi(g_1g_2g_3\cdots g_n)$, so $e=\varphi
(g_2) = \varphi(g_3) = \varphi(g_4) = \cdots = \varphi(g_n)$, or $g_2,g_3,
g_4,\ldots,g_n\in\varphi^{-1}(e)$, and $|g_i|\leq d$. Since $\varphi^{-1}(e)$
is locally finite, and there are only finitely many possibilities for
$g_2,g_3,\ldots,g_n$ (independent of $n$), when $n$ is large enough the
factor $g_2g_3\cdots g_n$ of $s$ will be contractible. Hence $S$ is finite.
\end{proof}

Theorem \ref{t11-6}, together with some algebra, also implies \cite{straubing1982}
that every torsion semigroup of matrices over an arbitrary field $F$ is
locally finite \cite{mcnaughton+zalcstein1975}.

The historical results here are:

\begin{itemize}
\item 1911 Schur -- Every torsion group of matrices over $\mathbb{C}$ is
locally finite.
\item 1965 Kaplansky -- Every torsion group of matrices over an arbitrary
field $F$ is locally finite.
\item 1971 Brzowski, Culik II \& Gabrielian -- There is an infinite semigroup
$S$ on two generators satisfying the identity $x^2 = x^3$ for all $x\in S$.
\item 1975 McNaughton \& Zalcstin -- Every torsion semigroup of matrices
over $F$ is locally finite.
\end{itemize}
The questions on groups of matrices were inspired by ``Burnside's Problem:''
\begin{itemize}
\item 1902 Burnside: Is every torsion group $G$ locally finite? Yes, in the
case $x^2 = 1$, and in the case $x^3 = 1$.
\item 1940 Sanov -- Yes, if $x^4 = 1$.
\item 1952 Green \& Rees -- [Every group with $x^n = 1$ is locally finite]
$\Leftrightarrow$ [Every semigroup with $x^{n+1} = x$ is locally finite.]
\item 1957 M. Hall Jr. -- Yes, if $x^6 = 1$.
\item 1964 Golod \& Shafarevich -- No, if $x^{n(x)} = 1$. (6 pages. See the
book \emph{Noncommutative Rings}, by I. N. Herstein, Mathematical Association
of America, Washington, DC, 1994.)
\item 1965 Novikov \& Adian -- No, if $x^n = 1$, for odd $n\geq4381$. (300+ pages.)
\item 1975 Adian -- No, if $x^n = 1$, for odd $n\geq 665$.
\item 1992 Lysionok -- No, if $x^n = 1$, for all $n\geq 213$.
\end{itemize}
(See the book \emph{Around Burnside}, by A. I. Kostrikin, Springer-Verlag,
Berlin, 1990.)

\section{On the canonical version of Theorem \ref{t11-6}}

In this section we describe a 2-coloring $f$ of $\omega$ which shows that the
constant colorings and the 1-1 colorings are not sufficient for a canonical
version of Theorem \ref{t11-6}. That is, there does not exist a fixed $d$ and
arbitrarily large sets $A = \{ a_1<a_2<a_3<\cdots<a_n\}$ with
$\max\{a_{j+1}-a_j|j=1,2,\ldots,n-1\} = d$, such that $f|_A$ is either constant
or 1-1. In fact, even the ``almost constant'' colorings ($c$ colors are allowed,
where $c$ is a constant) and the ``almost 1-1'' colorings (at most $c$-to-1,
where $c$ is a constant) are not enough. (See Theorem \ref{t11-9} below.)
We omit the proofs.

Let $S$ denote the set of all sums of distinct even powers of 2, including
0 as the empty sum. Thus $S = \{ 0,1,4,5,16,17,20,21,64,\ldots\}$.

Let $T$ denote the set of all sums of distinct odd powers of 2, including
0 as the empty sum. Thus $T = \{ 0,2,8,10,32,34,40,42,\ldots\}$.

Order the elements of $S$ and $T$ so that $S = \{ s_0<s_1<\cdots\}$ and
$T = \{ t_0<t_1<\cdots\}$.

Then, for each $j$, $f^{-1}(j)$ is defined by $f^{-1}(j) = S + t_j
= \{ s + t_j|s\in S\}$. Then
\[\begin{array}{ccccccccccc}
0 &= &f(0) &= &f(1) &= &f(4) &= &f(5) &= &\cdots \\
1 &= &f(2) &= &f(3) &= &f(6) &= &f(7) &= &\cdots \\
2 &= &f(8) &= &f(9) &= &f(12) &= &f(13) &= &\cdots \\
3 &= &f(10) &= &f(11) &= &f(14) &= &f(15) &= &\cdots \\
&\ldots
\end{array}\]

(Note that in \cite{deuber1982}, 4 colors are used, 4 times each. In general,
in $[0,4^k-1]$, $2^k$ colors are used, $2^k$ times each.)

Since for all $n\geq 0$, $f^{-1}(n)$ is a translate of $f^{-1}(0) = S$,
we have a partition of $\omega$ into infinitely many translates of the
infinite set $S$. Other such partitions of $\omega$ could be obtained
by partitioning the powers of 2 differently. For example, we could let
$S$ be the set of all sums of distinct prime powers of 2 including $2^0$
and $2^1$, and let $T$ be the set of all sums of distinct composite
powers of 2.

The set $S$ above ($S$ = set of sums of distinct even powers of 2) is
the ``Moser-de Bruijn sequence.'' (Neil Sloane's sequence \#A000695.
See \url{http://www.oeis.org}.) Setting $f = f(0)f(1)f(2)f(3)\cdots$,
we have $f = [(0011001122332233)^2(4455445566776677)^2]^2\cdots$.

\begin{defn}\label{t11-8} For $A = \{ a_1<a_2<a_3<\cdots<a_n\}$ with
$\max\{a_{j+1}-a_j|j=1,2,\ldots,n-1\} = d$, we say that the gap size
of $A$ is $d$, and write $gs(A) = d$. If $|A| = 1$, we set $gs(A) = 1$.
\end{defn}

\begin{thrm}\label{t11-9} With $f$ defined as above, and any $A\subset
\omega$, $\sqrt{|A|/8gs(A)}<|f(a)|<\sqrt{8|A|gs(a)}$.\end{thrm}

\section{Some open questions}

\begin{conj} if $g$ is an arbitrary coloring of $\omega$, then there
exists a fixed $d$ and arbitrarily large sets $A$ with $gs(A) = d$,
such that either
\begin{enumerate}
\item[(i)] at most $\sqrt{|A|}$ colors appear in $A$; or
\item[(ii)] each color appears at most $\sqrt{|A|}$ times in $A$.
\end{enumerate}
(For the coloring $f$ above, with $d=1$ and $A = [0,4^k-1]$, exactly
$\sqrt{|A|}$ colors appear in $A$, and each color appears exactly
$\sqrt{|A|}$ times.)\end{conj}

\paragraph{Question 1.} The total number of 3-term arithmetic progressions
in $[1,n]$ is $(1+o(1))(n^2/4)$. For each $n\geq1$, let $d(n)$ denote the
largest possible size of a collection of 3-term arithmetic progressions
in $[1,n]$ such that each two of the intersect in at most one point. There
should be a constant $d$ such that $d(n)=(d+o(1))(n^2/4)$. Find the value
of $d$. (Hayri Ardal, a student at Bo\u{g}azi\c{c}i University in Istanbul,
has shown that $d$, if it exists, satisfies $.47<d<43/84$.)

\paragraph{Question 2.} Color the interval $[1,3n]$ with 3 colors, each
color appearing exactly $n$ times. Is it true that there must exist a
3-term arithmetic progression in $[1,3n]$ which has received all three
colors? (This problem is due to Rado\c{s} Radoi\u{c}i\'c, a student at
MIT. He has shown that if $\omega$ is 3-colored, and each color class
has density at least 1/6, then there must exist a 3-term arithmetic
progression in $\omega$ which has received all three colors.)

\paragraph{Question 3.} Let $g(K)$ denote the smallest positive integer
$n$ such that if the interval $[1,n]$ is partitioned into two parts, then
at least one of these parts must contain a $k$-term increasing set
each of whose consecutive differences belongs to the set $\{d, 2d\}$,
for some positive integer $d$.

Let $h(k)$ denote the smallest positive integer $n$ such that if $A$ is
any $n$-element set of positive integers, each of whose consecutive
differences belongs to the set $\{1,2\}$, then $A$ must contain a
$k$-term arithmetic progression.

Can one find reasonable upper bounds on $g(k)$ and $h(k)$? If so,
this might give a reasonable upper bound on the van der Waerden function
$w(k)$, since $w(k)\leq g(h(k))$.

\paragraph{Question 4.} Is it not hard to show that if $\{1,2,\ldots,n^2\}$
is 2-colored, then there exists a monochromatic set $\{a_1,a_2,\ldots,a_n\}$
such that the set of consecutive differences $\{a_{j+1}-a_j|1\leq j\leq n-1\}$
has at most $\sqrt{n}$ elements? Can one find a ``small'' $g(n)$ such that if
$\{1,2,\ldots,g(n)\}$ is 2-colored, then there is a monochromatic set $\{a_1,
a_2,\ldots,a_n\}$ such that the set of consecutive differences $\{a_{j+1}-a_j
|1\leq j\leq n - 1\}$ has at most $\log n$ elements? For each $k$ can one find (for arbitrarily
large $n$) $a_1<a_2<\cdots<a_n$ with $a_{j+1}-a_j\leq\log n,1\leq j\leq n-1$,
such that $\{a_1,a_2,\ldots,a_n\}$ contains no $k$-term arithmetic progression?


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