%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-22/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{Arithmetic Progressions in Sequences With Bounded Gaps}
\author{Tom C. Brown \footnote{Department of Mathematics and Statistics, ¶¡ÏãÔ°AV, Burnaby, B.C., Canada V5A 1S6. \texttt{tbrown@sfu.ca}.} \and
Donovan R. Hare \footnote{Department of Mathematics and Statistics, Okanagan University College, 3333 College Way, Kelowna, B.C. Canada V1V 1V7 \texttt{dhare@okanagan.bc.ca}.}
\footnote{Both authors gratefully acknowledge the support of the National Science and Engineering Research Council of Canada.}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown and D.R. Hare, \emph{Arithmetic progressions in sequences with
  bounded gaps}, J. Combin. Theory Ser. A \textbf{77} (1997), 222--227.}\bigskip\end{center}

\begin{abstract}
Let $G(k,r)$ denote the smallest positive integer $g$ such that if
$1=a_1, a_2, \dots, a_g$ is a strictly increasing sequence of integers with
bounded gaps $a_{j+1}-a_j \le r$, $1\le j\le g-1$, then $\{a_1, a_2, \ldots, a_g\}$
contains a $k$-term arithmetic progression. It is shown that $G(k,2) >
\sqrt{\frac{k-1}{2}}\left(\frac{4}{3}\right)^{\frac{k-1}{2}}$, $G(k,3) >
\frac{2^{k-2}}{ek}(1+o(1))$, $G(k,2r-1) > \frac{r^{k-2}}{ek}(1+o(1))$, $r\ge 2$.
\end{abstract}

For positive integers $k$, $r$, the van der Waerden number $W(k,r)$ is the
least integer such that if $w\ge W(k,r)$, then any partition of $[1,w]$ into
$r$ parts has a part that contains a $k$-term arithmetic progression. The
celebrated theorem of van der Waerden \cite{vanderwaerden1927} proves the
existence of $W(k,r)$. The best known upper bound for $W(k,2)$ is enormous
whereas the best known lower bound for $W(k,2)$ (see~\cite{graham+rothschild+spencer1990}) is
\begin{equation} W(k,2) > \frac{2^k}{2ek} (1+o(1)) \label{vanderlb} \end{equation}
where $e$ is the base of the natural logarithm.

Let $G(k,r)$ denote the smallest positive integer $g$ such that if $1=a_1, a_2, \dots, a_g$
is a strictly increasing sequence of integers with bounded gaps $a_{j+1}-a_j \le r$, $1\le j\le g-1$,
then $\{a_1, a_2, \ldots, a_g\}$ contains a $k$-term arithmetic progression.
In \cite{rabung1975}, Rabung notes that van der Waerden's theorem implies the
existence of $G(k,r)$ for all $k$, $r$ and conversely.

Nathanson makes the following quantitative connection between $W(k,r)$ and
$G(k,r)$ \cite[Theorem~4]{nathanson1980}:
\begin{equation} G(k,r) \le W(k,r) \le G((k-1)r+1,2r-1). \label{nathineq} \end{equation}

In particular, $W(k,2)\le G(2k -1,3)$, which suggests that it is no easier
to find a reasonable upper bound for $G(k,3)$ than it is for $W(k,2)$.

However, $G(k,2)$ ``escapes'' Nathanson's inequalities in the sense that an
upper bound for $G(k,2)$ does not immediately give an upper bound for $W(k,2)$.

Setting $r=2$ and combining \eqref{vanderlb} and \eqref{nathineq} gives
\[ G(k,3) > \frac{2^{\frac{k+1}{2}}}{e(k+1)} (1+o(1)), \]
but again $G(k,2)$ ``escapes'' in that no lower bound for $G(k,2)$ can be
deduced from Nathanson's inequalities.

In this note we obtain an exponential lower bound for $G(k,2)$ and improved
lower bounds for $G(k,r)$, $r>2$. The Lov\'{a}sz Local Lemma is used when $r>2$.
However when $r=2$ this method fails, and elementary counting arguments are used.

\begin{thrm}For all $k\ge 1$,
\[ G(k,2) > \sqrt{\frac{k-1}{2}} \left(\frac{4}{3}\right)^{\frac{k-1}{2}}.\]
\label{thmr=2}
\end{thrm}

\begin{proof} We use the following notation. For each positive integer $n$, let
\[ \Omega_n = \{ \alpha = a_1, a_2, \ldots, a_n : a_1 = 1,\ 1\le a_{j+1} - a_j \le 2,\ 1\le j \le n-1\},\]
and let ${\cal S}_n$ be the set of all $k$-term arithmetic progressions
contained in $[1, 2n-1]$.

Let $i \in [1, 2n-1]$ and $\alpha\in\Omega_n$. We say that $i$ occurs in
$\alpha=a_1, a_2, \ldots, a_n$ if $i\in\{a_1, a_2,\ldots, a_n\}$.
Similarly, for any subset $I$ of $[1, 2n-1]$, we say that $I$ occurs in
$\alpha$ if $I\subseteq\{a_1, a_2,\ldots, a_n\}$ and will write $I\subseteq\alpha$.

Let $k \ge 3$ be fixed and give $\Omega_n$ the uniform probability distribution.
The idea of the proof is to show that for any $k$-term arithmetic progression
$S \in {\cal S}_n$, $\Pr( S\subseteq \alpha) \le \left(\frac{3}{4}\right)^{k-1}$.

For each $i$, $1 \le i \le 2n-1$, let $A_i =\{\alpha \in \Omega_n : \mbox{$i$
occurs in $\alpha$}\}$. Then $\Pr(A_1)=1$, $\Pr(A_2)=1/2$ and $\Pr(A_3)=\frac{3}{4}$.

To show that $\Pr(A_i) \le 3/4$ for $i > 3$, partition $A_i$ so that it is the
disjoint union $A_i = A_i^0\cup A_i^1 \cup A_i^2$ where $A^0_i = \{\alpha\in A_i:
a_n = i\}$ and for $m=1,2$, $A^m_i=\{\alpha\in A_i : a_j= i \Longrightarrow
a_{j+1} = i+m\}$. Now $|A^1_i|=|A^2_i|$ and so $\Pr(A_i^m) \le \frac{1}{2}
\Pr(A_i)$, $1\le m\le 2$. Moreover, $A_{i+2}$ is the disjoint union of $A^1_{i+1}$
and $A^2_{i}$, and thus
\begin{eqnarray*}
\Pr(A_{i+2}) & = & \Pr(A^1_{i+1}) + \Pr(A^2_i)\\
&\le& \frac{1}{2}\left( \Pr(A_{i+1}) + \Pr(A_i)\right).
\end{eqnarray*}
It follows by induction that for $i =2, 3, \ldots, 2n-1$,
\begin{equation}
\Pr(A_i) \le \frac{3}{4}.
\label{ineqp}
\end{equation}

Note that inequality \eqref{ineqp} is independent of $n$. That is, for every
$n\ge 1$ and every $i= 2, 3, \ldots, 2n-1$,
\begin{equation}
|\left\{\alpha\in \Omega_n : \mbox{$i$ occurs in $\alpha$}\right\}|
\le \frac{3}{4} |\Omega_n| = \frac{3}{4} \cdot 2^{n-1}.
\label{ineqomega}
\end{equation}

Let $n$ be fixed and let $I$ be a non-empty subset of $\{2, 3, \ldots, 2n-1\}$.
Let $m$ be the largest element of $I$ and define $A_I = \bigcap_{i\in I} A_i$.
We proceed to show that $\Pr(A_I) \le \left(\frac{3}{4}\right)^{|I|}$.

Define $\tilde{{A}_I}=\{\tilde{\alpha}=a_1, a_2, \ldots, a_s: a_1=1, a_s=m,
s\le n, \mbox{$I$ occurs in $\alpha$}\}$ and for each $\tilde{\alpha}\in \tilde{{A}_I}$,
$\tilde\alpha = a_1, a_2, \ldots, a_s$, define $B_{\tilde\alpha}$ to be the
set of all $2^{n-s}$ ``continuations'' of $a_1, a_2, \ldots, a_s$. That is,
let $B_{\tilde\alpha} = \{\alpha\in \Omega_n: \alpha=a_1, a_2, \ldots, a_k,
b_{k+1}, \ldots, b_n\}$. Then $A_I$ is the disjoint union
\begin{equation}
A_I = \bigcup_{\tilde\alpha\in \tilde A_I} B_{\tilde\alpha}
\label{disunion}
\end{equation}

Let $j$ be such that $m < j \le 2n-1$. We now want to estimate the number of
sequences in $B_{\tilde\alpha}$ in which $j$ occurs. For each $\tilde{\alpha}\in
\tilde{{A}_I}$, $\tilde\alpha = a_1, a_2, \ldots, a_s$, we can map
$B_{\tilde\alpha}$ onto $\Omega_{n-s+1}$ by dropping $a_1, a_2, \ldots, a_{s-1}$
and then shifting $m-1$ units to the left. That is, we map $\alpha \in B_{\tilde\alpha}$,
$\alpha=a_1, a_2, \ldots, a_k, b_{k+1}, \ldots, b_n$, into $\beta = 1, b_{k+1}
-(m-1), \ldots, b_n -(m-1)$. Clearly $j$ occurs in $\alpha$ if and only if
$j-(m-1)$ occurs in $\beta$.

Using \eqref{ineqomega} we therefore have
\begin{eqnarray}
|\{\alpha \in B_{\tilde\alpha} : \mbox{$j$ occurs in $\alpha$}\}|
& = & |\{\beta \in \Omega_{n-s+1} : \mbox{$j-(m-1)$ occurs in
$\beta$}\}|\nonumber\\
& \le & \frac{3}{4}|\Omega_{n-s+1}|\nonumber\\
& = & \frac{3}{4} \cdot 2^{n-s}\nonumber\\
& = & \frac{3}{4} |B_{\tilde\alpha}| \label{independ}.
\end{eqnarray}

Combining \eqref{disunion} and \eqref{independ} we obtain
\begin{eqnarray}
|A_I \cap A_j| & = & \sum_{\tilde\alpha\in \tilde A_I} |B_{\tilde\alpha}\cap
A_j| \nonumber\\
& \le & \sum_{\tilde\alpha\in \tilde A_I} \frac{3}{4}
|B_{\tilde\alpha}|\nonumber\\
& = & \frac{3}{4} |A_I| \label{induct}
\end{eqnarray}

Hence by induction (using \eqref{ineqp} and \eqref{induct}),
$\Pr(A_I \cap A_j) \le \frac{3}{4} \Pr(A_I) \le
\left(\frac{3}{4}\right)^{|I|+1}$.
Note also that $\Pr(A_{I\cup\lbrace1\rbrace}) \le \left(\frac{3}{4}\right)^{|I|}$.
In particular, for all $S \in {\cal S}_n$, $\Pr(S\subseteq \alpha) \le
\left(\frac{3}{4}\right)^{k-1}$.

For each $S$ in ${\cal S}_n$, let $E_S$ denote the event ``$S\subseteq\alpha$''.
The probability that some $S$ in ${\cal S}_n$ occurs in $\alpha$ satisfies
\begin{eqnarray*}
\Pr(\bigcup_{S\in {\cal S}_n} E_S) &\le & \sum_{S\in {\cal S}_n} \Pr(E_S)\\
& \le & |{\cal S}_n| \left(\frac{3}{4}\right)^{k-1} \\
& \le & \frac{(2n-1)^2}{2(k-1)} \left(\frac{3}{4}\right)^{k-1}.
\end{eqnarray*}

If $n < \frac{1}{2}+\sqrt{\frac{k-1}{2}}\left(\frac{4}{3}\right)^{\frac{k-1}{2}}$,
then $\frac{(2n-1)^2}{2(k-1)} \left(\frac{3}{4}\right)^{k-1} < 1$ and hence
$\Pr(\bigcap_{S\in {\cal S}_n} \overline{E_S}) >0$. That is, there exists
$\alpha \in \Omega_n$ that does not contain a $k$-term arithmetic progression.
Therefore $G(k,2) > \sqrt{\frac{k-1}{2}} \left(\frac{4}{3}\right)^{\frac{k-1}{2}}$.
\end{proof}

The proof of Theorem~\ref{thmr=2} can easily be modified to show that
$G(k,r) > \sqrt{\frac{k-1}{2}} \left(\frac{1}{p}\right)^{\frac{k-1}{2}}$
where $p=p(r) = \frac{1}{r}\left(1+\frac{1}{r}\right)^{r-1}$, for all $k\ge 3$,
$r\ge 2$. But this is much weaker than the following result.

\begin{thrm} For all $k\ge 1$, $r\ge 2$,
\[ G(k,2r-1) > \frac{r^{k-2}}{e k}(1+o(1)).\]
\label{thmr>2}
\end{thrm}

Before proving Theorem~\ref{thmr>2}, we state the form of the Lov\'{a}sz Local
Lemma we use(\cite{graham+rothschild+spencer1990}).

\paragraph{Lov\'{a}sz Local Lemma.} Let $A_1,\ldots,A_m$ be events with
$\Pr(A_i)\le p$ for all $i$. Suppose that each $A_i$ is mutually independent
of all but at most $d$ of the other $A_j$'s. If $ep(d+1) < 1$, then
$\Pr(\cap \overline{A}_i)>0$.

\begin{proof}[Proof of Theorem~\ref{thmr>2}] To simplify the notation, we carry
out the proof only in the case $r=2$. The proof for the general case is
essentially the same.

Fix $k\ge 1$ and fix $n$. Let $\mathcal{M}$ be the set of all sequences
$\alpha=a_1, a_2,\ldots, a_n$ such that $a_i\in \{2i-1,2i\}$, $1\le i\le n$.
Thus $\alpha$ contains exactly one of the two elements in each of the
\emph{blocks} $[1,2]$, $[3,4]$, \ldots, $[2n-1,2n]$.

Let the symbols $S$, $T$ denote $k$-term arithmetic progressions contained
in $[1,2n]$ with common differences at least two. Give $\mathcal{M}$ the uniform
probability distribution and again let $E_S$ denote the event ``$S\subseteq\alpha$''.
Then $|{\cal M}|=2^n$ and $|\{\alpha\in {\cal M}:S\subseteq\alpha\}|=2^{n-k}$,
so $\Pr(E_S)= 2^{-k}$.

The event $E_S$ is mutually independent of all the other events $E_T$ for all
$T$ that have no blocks in common with $S$ (that is, for no $i$, $1\le i\le n$,
is it true that $[2i-1,2i]\cap S\ne \emptyset$ and $[2i-1,2i]\cap T\ne \emptyset$).
To see this, note that a random $\alpha\in\mathcal{M}$ can be constructed by
randomly and independently choosing each element $a_i$ from $[2i-1,2i]$
with uniform probability. Thus even if we know the chosen element of $\alpha$
for each block besides those of $S$, the probability of $E_S$ remains unchanged,
and any assumption on the events $E_T$ for $T$ that have no blocks in common
with $S$ is determined by these chosen elements.

For each $S$, the number of $T$ such that $S$ and $T$ do have a block in common
is bounded above by $4nk$. (To see this note that the number of $k$-term
arithmetic progressions in $[1,2n]$ which contain any given element of $[1,2n]$
is bounded above by $2n$ (in fact, by about $(\log 2)(2n)$). Since $S$ meets
$k$ blocks, $T$ will have a block in common with $S$ only if $T$ contains one
of the $2k$ elements of these $k$ blocks.)

Now we can apply the Lov\'asz Local Lemma with $p=2^{-k}$, $d=4nk$.
If $n < \frac{2^{k-2}}{ek}(1-\epsilon)$, then $ep(d+1)<1$, so $\Pr(\cap \overline{E_S}) > 0$.
Therefore if $n < \frac{2^{k-2}}{ek}(1-\epsilon)$, there is $\alpha\in\mathcal{M}$,
$\alpha = a_1, a_2, \ldots, a_n$, which contains no $k$-term arithmetic
progression. Since $a_{j+1}-a_j\le 3$ for all $j$, this shows that
$G(k,3) > \frac{2^{k-2}}{ek}(1+o(1))$.\end{proof}


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