%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-35/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{cor}{Corollary}
\newtheorem{corn}{Corollary to Lemma 1}
\newtheorem{lemma}{Lemma}
\newtheorem*{sub}{Sublemma}
\newtheorem{thm}{Theorem}
\newtheorem*{prop}{Proposition}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{fact}{Fact}
\newtheorem*{claim}{Claim}
\newtheorem*{remark}{Remarks}
\newtheorem*{app}{Applications}
\newtheorem*{conj}{Conjecture}
\newcommand{\diam}[1]{\textup{Diam} #1}
\title{Quasi-Progressions and Descending Waves}
\author{T. C. Brown, P Erd\H{o}s, and A. R. Freedman}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown, P.~Erd\H{o}s, and A.R. Freedman, \emph{Quasi-progressions and
descending waves}, J. Combin. Theory Ser. A \textbf{53} (1990), 81--95.}\bigskip\end{center}
\section{Introduction and Definitions} \label{sec: 1}
If $A$ is a set of positive integers with positive upper uniform density, then $A$ must contain arbitrarily large cubes, i.e., sets of the form
\begin{equation} \langle a,y_1,y_2,\dots,y_m \rangle = \{a + \varepsilon_1 y_1 + \cdots + \varepsilon_my_m: \varepsilon_j = 0\textup{ or } 1,1 \leq j \leq m \} \label{eq: 1} \end{equation}
This fact is an essential step in Szemer\'{e}di's proof that any set with positive upper uniform density contains arbitrarily large arithmetic progressions.
In this paper we consider several other properties of a set of positive integers, each of which generalizes the notion of having arbitrarily long arithmetic progresssions. We call these properties $QP$ (having arbitrarily large ``quasi-progressions"), $CP$ (having arbitrarily large ``combinatorial progressions"), and $DW$ (having arbitrarily large ``descending waves"). The definitions of these properties will appear at the end of this section.
Let us denote by $AP$ and $C$ the properties of having arbitrarily long arithmetic progressions and arbitrarily large cubes, respectively. Then, in Section~\ref{sec: 2}, we will show that
\[ AP \Rightarrow QP \Rightarrow CP \Rightarrow C \Rightarrow DW, \]
and that none of these implications is reversible.
By using Szemer\'{e}di's method for obtaining cubes, we can show that, if the sum of the reciprocals of the elements of a set $A$ is infinite, then $A$ has property $C$. While we cannot, at present, show that a set with infinite reciprocal sum must have properties $CP$ or $QP$, we have a good excuse for the last failure: we show that Erd\H{o}s' famous conjecture (that every set of positive integers with infinite reciprocal sum has property $AP$) is equivalent to the statement that every set with infinite reciprocal sum has property $QP$. These are done in Section~\ref{sec: 3}.
In Section~\ref{sec: 4} we consider descending waves. We obtain upper and lower bounds for $f(k)$, the smallest integer such that, if $\{1,2,\dots,f(k)\} = A \cup B$, then $A$ or $B$ contains a $k$-term descending wave. We also obtain an upper bound for
\[\max \{ |S|: S\subseteq\{1,2,\dots,m\} \textup{ and $S$ contains no $k$-term descending wave}\}. \]
(The upper bound is $c_k(\log m)^{k-2}.$ )
We also consider in Section~\ref{sec: 4} how the growth rate of a sequence $\{a_n\}$ influences the presence of descending waves in the set $\{a_n\}$. We show that arbitrarily long descending waves must be present even in certain sets with rather large growth rates, but that sets $\{a_n\}$ with $a_{n + 1}/a_n \geq 1 + \varepsilon$ for all $n$ have descending waves of bounded length.
We conclude the paper with some remarsk and questions in Section~\ref{sec: 5}.
We now define the properties $QP,CP$ and $DW$. A finite sequence $x_1 a_j$.
Proof that $C \not\Rightarrow CP$. Let $A$ be the set of all positive integers whose decimal representation uses only zeros and ones, i.e.,
\[ A = \left\{ k: k = \sum_{i=1}^N \varepsilon_i 10^i, \varepsilon_i = 0\textup{ or }1, N \geq 0, k > 0 \right\}. \]
It is clear from this definition that $A$ has property $C$. Let $b_1 b_{i + 1} - b_i$. Now assume that $A$ has property $CP$ for order $d$. If $b_1 d$. Let $P = \{b_1 < b_2 < b_3 < \cdots b_j - (b_{i + 1} - b_i) \geq b_i > t_15^{t_1} > d$ and this contradicts $P$ being a $QP(d)$. Hence, if $n$ is sufficiently large, we may assume that $P$ contains six terms, $b_i,b_{i + 1},\dots,b_{i + 5}$ in some $B(t)$, where $t \geq t_0$. Now, for a suitable $u>v>w$,
\begin{align*}
|b_{j + 2} &- b_{j + 1} - (b_{j + 1} - b_j)| \\
&= |t5^t + ut^2 + t(z_1 + \cdots + z_u) - 2 (t5^t + vt^2 + t(z_1 + \cdots + z_v)) \\
&+t5^t + wt^2 + t(z_1 + \cdots + z_w)| \\
&= |(u + w - 2v)t^2 + t((z_{v + 1} + \cdots +z_u) - (z_{w + 1} + \cdots + z_v))| \leq d < t. \end{align*}
It follows that $u - v = v -w$ and $z_{v + 1} + \cdots + z_u = z_{w + 1} + \cdots + z_v$ so that the above six members of $P$ determine five adjacent blocks of $\{z_i\}$ which have the same composition, a contradiction.
Finally we show that $QP \not\Rightarrow AP$. Here let $A = S(1) \cup S(2) \cup S(3) \cup \cdots$ where $S(t)$ is defined above. Clearly $A$ has $QP$ since each $S(t)$ is a $t-QP(1)$. An argument similar to the above would show that, if an arithmetic progression $P = \{b_1 1$. Having chosen $B_1,B_2,\dots,B_{n - 1}$, we let $g \geq 3 \cdot \max(B_{n - 1})$ and $B_n$ consist of enough terms of $nA + g$ so that
\[ \sum_{i \in B_n} 1/i > 1. \]
We set $B = B_1 \cup B_2 \cup B_3 \cup \cdots$, and note that $B_n$ does not contain any $k-QP(n-1)$ and that $B$ has infinite reciprocal sum. We need only show that, for each $d \geq 0$, $B$ does not contain arbitrarily long $QP(d)$. Let $S = \{b_1,b_2,\dots,b_t\}$ be a $t-QP(d)$ in $B$ where, for some $N \geq 1$,
\[ N \leq b_{j + 1} - b_j \leq N + d, \quad 1 \leq j \leq t - 1. \]
If $i \geq 2$ and $b_i,b_{i + 1}$ belong to different sets $B_n$, then, for $j < i$,
\[ N + d \geq b_{i + 1} - b_i \geq 2b_i \geq 2(b_{j + 1} - b_j) \geq 2N. \]
It follows that, if $S$ intersects with $h + 1$ different sets $B_n$, then we would obtain $N +d \geq 2^hN$, which implies $h \leq \log_2(d + 1)$. Hence, if $B$ has property $QP$ for diameter $d$ then no $t-QP(d)$ in $B$ can meet more than $\log_2(d + 1) + 1$ different sets $B_n$. Hence, by choosing $t$ sufficiently large, we may assure that $S$ has at least $k$ consecutive terms in some $B_n$ where $n \geq d + 1$. But these $k$ terms are a $k-QP(d)$ which is a $k-QP(n-1)$ in $B_n$. This contradiction completes the proof.
\end{proof}
\begin{thm} \label{thm: 3}
If $A$ is a set of positive integers with infinite reciprocal sum, then $A$ has property $C$ (and therefore also property $DW$).
\end{thm}
\begin{proof} It is shown in~\cite[p.~19]{graham1981} that, if
\[ \alpha = 2 + \sqrt{3}, \quad \lambda(k) = \alpha \cdot n^{1 - (1/2^k)}, \]
$A = \{a_1 |B_{t -1}|$.
To see this, just let $i_j = t - (s - j)(s - j + 1)$ for $1 \leq j\leq s$. Then $x_{i_1},x_{i_2},\dots,x_{i_s}$ is an $s-DW$ with the last term $=x_t$. This is easily shown by the following calculations:
\begin{align*}
i_{j + 1} - i_j &= 2(s - j); \\
x_{i_{j + 1}} - x_{i_j} &> |B_{i_{j + 1}}| + |B_{i_{j + 2}}| + \cdots + |B_{i_{j +1} - 1}| \geq (2(s - j) - 1)|B_{i_{j + 1}}| \\
&\geq |B_{i_{j + 1}}| + |B_{i_{j + 1}} + 1| + |B_{i_{j + 1} + 2}| + \cdots + |B_{i_{j +2}}| \geq x_{i_{j + 2}} - x_{i_{j + 1}}. \end{align*}
Since $i_{s - 1} = t - 2$, we obtain $x_{i_s} - x_{i_{s - 1}} > |B_{t- 1}|$.
Next we suppose that $n \geq k^3/3 - 4k/3 + 3 = d$ and that $\{1,2,\dots,n\}$ is 2-colored such that there is no monochromatic $k-DW$. We partition the first $d$ integers of this set into consecutive blocks of decreasing order, $B_1,B_2,\dots,B_t$, where $t = k^2 - 3k + 4$, as follows: $|B_1| = k$; $|B_2| = |B_3| = k-1$; $\dots$; $|B_t| = 1$. Here, in general, there will be $2j$ blocks of length $k - j$ for $ 1\leq j \leq k - 2$ (only one block, the first, of length $k$ and one block, the last, of length one.) Hence the number of blocks is $1 + 2 + 4 + 6 + \cdots + 2(k-2) + 1 = t$. Also, the number of consecutive integers contained in the union of all these blocks is, as stated,
\[ k + 1 + \sum_{j=1}^{k - 2} 2j(k - j) = \frac{k^3}{3} - \frac{4k}{3} + 3. \]
If $B_u$ is of length $k - s$ $(s \geq 1)$ then $u > 1 + 2 + 4 + \cdots + 2(s - 1) = s^2 - s + 1$. It follows from the assumption about the coloring and the above lemma that no block of our partition can be monochromatic. For, supposing $B_u$ to be the first monochromatic block (say all 1's), if $u=1$, then the $k$ integers of $B_1$ form a $k-DW$. On the other hand, if $1 < u \leq t$, then each block which comes before $B_u$ must contain an integer colored 1 and, if $|B_u| = k-s$, the lemma implies that there is an $s-DW$, $x_1,x_2,\dots,x_s$, of integers colored 1 such that $x_s \in B_{u - 1}$. Let $x_{s + 1}, x_{s + 2}, \dots, x_k$ be the $k - s$ elements of $B_u$. From the construction used in the proof of the lemma, we see that $x_s - x_{s - 1} > |B_{u - 2}| \geq |B_{u - 1}| \geq x_{ s + 1} - x_s$. Hence $x_1,x_2,\dots,x_k$ is a monochromatic $k-DW$ contrary to assumption. The theorem is proved by observing that $B_t$ is necessarily monochromatic.
\end{proof}
If one defines $f(k)$ requiring a monochromatic \emph{strict} descending wave (i.e., the differences form a strictly decreasing sequence $d_1 > d_2 > \cdots > d_{k - 1}$), then the above method will yield lower and upper bounds $c_1k^3$ and $c_2k^4$ respectively.
Further, if we consider the above method but use intervals each of length $k$, then we obtain the result: If $\{1,2,\dots,k^3 - 3k^2 + 4k\}$ is 2-colored, then there are either $k$ consecutive monochrome integers or there is a monochromatic $k-DW$.
Next we proceed to find an upper bound on the order of a subset of $\{1,2,\dots,n\}$ which has no $k-DW$.
\begin{thm} \label{thm: 5}
Let $S \subseteq \{1,2,\dots,2^n\}$ and suppose that $S$ contains no $k-DW$ where $3 \leq k \leq n + 2$. Then
\[ |S| \leq 2^{k-2} \binom{n}{k - 2}. \]
\end{thm}
\begin{proof}
Since descending waves are invariant under translation we may assume that $\min(S) = 1$. We begin an induction at $k = 3$ by observing that, if $S$ contains no $3-DW$, then each interval $I_t = \{2^t + 1, \dots, 2^{t + 1}\}$, $0 \leq t \leq n - 1$, contains no more than one element of $S$ (for, if $a,b \in I_t$, $a**1$ (in fact, $c = 2^{((k-2)!/2^{k-1})^{1/k - 2}}$) such that, for $a_t \geq 2^{k-2}$,
\[ a_t \geq c^{t^{1/(k-2)}}. \]
\end{cor}
Hence, if for each $\varepsilon > 0$,
\[ a_n < e^{n^\varepsilon} \]
for all sufficiently large $n$, then $\{a_n\}$ has $DW$. For example, if
\[ a_n \leq e^{n^{1/\log\log n}} \]
then $\{a_n\}$ has $DW$. Consequently, if $\{a_n\}$ is a sequence such that $a_n \leq p(n)$ for infinitely many $n$, where $p(x)$ is a fixed polynomial, then $\{a_n\}$ has property $DW$. This last remark gives a proof, independent of Theorem~\ref{thm: 3}, that $\sum_A = 1/a = \infty$ implies that $A$ contains arbitrarily long descending waves.
\begin{cor} \label{cor: 3}
Define $g(\varepsilon, k)$ to be the smallest $n$ such that $A \subseteq \{1,2,\dots,n\}$ and $|A| > \varepsilon n$ imply that $A$ has a $k-DW$. Then for $k \geq 4$ and $\varepsilon \leq 0.9$ we have
\[ \frac{k^2 - k}{2\varepsilon} \leq g(\varepsilon , k) \leq \left( \frac{6e}{\varepsilon} \right)^{k-2}. \]
\end{cor}
\begin{proof} The left-hand inequality follows by taking the set colored ``1" in the construction at the beginning of the proof of Theorem~\ref{thm: 4} as a subset of $\{1,2,\dots,[(k^2 - k)/2\varepsilon]\}$. For the right-hand inequality we proceed as follows: Let $n = [(6e/\varepsilon)^{k-2}]$, $A \subseteq \{
1,2,\dots,n\}$, $|A| > \varepsilon n$, and suppose that $A$ has no $k-DW$. From Corollary~\ref{cor: 1} above we get
\[ \varepsilon_n < |A| \leq \frac{2^{k-1}}{(k-2)!} (\log_2n)^{k-2}, \]
\[ \frac{n}{(\log_2n)^{k-2}} < \frac{2^{k-1}}{\varepsilon(k-2)!}, \]
which, using $k^k e^{-k} \sqrt{2\pi k} e^{1/(12k + 1)} \leq k!$, implies
\[ \sqrt{2\pi (k-2)} (1 - (\varepsilon/6e)^{k-2}) < \frac{2}{3} \left( \frac{2\varepsilon}{6} \log_2\frac{6e}{\varepsilon} \right)^{k-2}. \]
But this inequality is false if $k \geq 4$ and $\varepsilon \leq 0.9$.
\end{proof}
For $k = 3$ and any $\varepsilon$, the beginning of the proof of Theorem~\ref{thm: 5} shows that if $\varepsilon 2^t \geq t + 1$, then $g(\varepsilon,3) \leq 2^t$.
We shall consider below the existence of descending waves contained in sequences $\{a_1 0$, let $k(\varepsilon)$ be the maximum, over all sequences $A = \{a_1 t\left( \frac{\varepsilon}{1 + \varepsilon} \right). \]
Therefore $t < 1 + 1/\varepsilon$, whence $k(\varepsilon) < 1/\varepsilon + 2$.
For the lower bound, given $\varepsilon < 1$, define $a_i = i$ for $i= 1,2,\dots,t$, where $t = [1/\varepsilon]$ and $a_{t + k} = t(1 + \varepsilon)^k$ for $k \geq 1$. Then $A$ satisfies the condition of the theorem and $1,2,\dots,t,t(1 + \varepsilon)$ is a $DW$ in $A$ of length $[1/\varepsilon] + 1$. Hence $k(\varepsilon) \geq [1/\varepsilon] + 1$.
\end{proof}
The case where $\{a_n\}$ is an exponential sequence is special.
\begin{thm} \label{thm: 7}
Let $p(\varepsilon)$ be the length of the longest $DW$ in the sequence $a_n = c^n$, where $c = 1 + \varepsilon$. Then there exist constants $A$ and $B$ such that
\[ A/\sqrt{\varepsilon} \leq p(\varepsilon) \leq B/\sqrt{\varepsilon}. \]
\end{thm}
\begin{proof} For the lower bound consider the sequence (with $t + 2$ terms)
\[ 1,c^{t + 1}, c^{(t + 1) + t}, \dots, c^{(t + 1) + t + (t-1) + \cdots + 1}. \]
This is a $DW$ if and only if, for each $s$, $1 \leq s \leq t$, we have
\[ 2 \geq c^s + \frac{1}{c^{s + 1}}. \]
These inequalities all hold if and only if
\[ 2 \geq c^t + \frac{1}{c^{t + 1}} \]
and this inequality is equivalent to $c^t \leq 1 + \sqrt{\varepsilon/c}$. (For $t = 1$ this inequality requires that $\varepsilon \leq \frac{1}{2} (\sqrt{5} - 1) \sim 0.61$ and that $\varepsilon$ be smaller for larger values of $t$.) Hence, for given $\varepsilon$, say $\varepsilon < 0.6$, we may take $t = [\log(1 + \sqrt{\varepsilon/c})/\log(c)]$. This last quantity is asymptotic with $1/\sqrt{\varepsilon}$. For $\varepsilon < 0.6$ we may let $A = 0.787$.
For the upper bound we proceed as follows. First note that if $c^{r_1},c^{r_2}, c^{r_3}$ is a $3-DW$, then $r_3 - r_2 < r_2 -r_1$. Let $R = 1/\sqrt{\varepsilon}$ and let $a_1,a_2,\dots,a_k$ be a $DW$ in $\{c^s\}$. Letting $t = [R] + 1$ we get $a_t - a_{t -1} < a_t/R$. Write $a_t = c^{r_1}$ and $a_{t + 1} = c^{r_2}$. Clearly $c^{r_2 - r_1} < (1/R) + 1$ so that
\[ r_2 - r_1 < \frac{\log((1/R) + 1)}{\log c} \sim R. \]
It follows that $k$ is less than, approximately, twice $R$.
\end{proof}
The sequences $a_n = \exp(n^\varepsilon)$ of Corollary~\ref{cor: 2}, as we shall see below, all have property $DW$ even though they are upper bounds for sequences which do not have $DW$. More precisely, we prove the following.
\begin{thm} \label{thm: 8}
For any $\varepsilon > 0$, there exists a sequence $A = \{a_n\}$ of positive integers such that $A$ does not have property $DW$ and, for all large $n$, $a_n < \exp(n^\varepsilon)$. (Compare the remarks following Corollary~\ref{cor: 2}.)
\end{thm}
\begin{proof}
The sequence $\{2^n\}$ does not contain a $3-DW$ and $2^n < \exp(n^\varepsilon)$ for all $\varepsilon \geq 1$. Let $N > 1$ and put
\[ A = A^N = \{2^{i(1)} + 2^{i(2)} + \cdots + 2^{i(N)}: i(1) > i(2) > \cdots > i(N) \geq 0\}. \]
We first prove that if $A = \{a_n\}$ then $a_n < \exp(n^\delta)$ for all large $n$, where $\delta > 1/N$. Let $a_n = 2^{i(1)} + 2^{i(2)} + \cdots +2^{i(N)} > 2^{i(1)}$. Then
\[ n = A(a_n) > A(2^{i(1)}) = \binom{i(1) - 1}{N} > C(i(1))^N. \]
Hence $i(1) < Dn^{1/N}$ and
\[ a_n < 2^{i(1) + 1} = 2\cdot 2^{i(1)} < 2 \cdot 2^{Dn^{1/N}} < e^{n^\delta} \]
for suitable constants $C,D$ and all large $n$. Thus we choose $N$ such that $1/N <\varepsilon$. We can assume inductively that $A^{N-1}$ does not have property $DW$. Suppose $A^N$ has $DW$ and let $a_1,a_2,\dots,a_w$ be a descending wave in $A^N$. Write
\[ a_t = \sum_{s=1}^N 2^{i(s,t)} \quad (t = 1,2,\dots,w). \]
Note that $i(1,t) \leq i(1,t + 1)$. If equality holds for arbitrarily long blocks, then these blocks determine long $DW$s in $A^{N-1}$ contrary to the inductive hypothesis. Hence we may assume (by taking $w$ large enough) that $i(1,t) < i(1, t + 1)$ occurs at least $N + 2$ times. Clearly then we have $i(1,t + 1) - N > i(1,2)$ for some $t$. Then
\begin{align*} a_{t + 1} - a_t &> 2^{i(1,t + 1)} - (2^{i(1,t)} + 2^{i(1,t) - 1} + \cdots + 2^{i(1,t) - N + 1}) \\
&= 2^{i(1, t+ 1)} - (2^{i(1,t) + 1} - 2^{i(1,t) - N + 1}) \\
&\geq 2^{i(1,t) - N +1} > 2^{i(1,2) + 1} > a_2 - a_1. \end{align*}
This proves that $A^N$ does not have property $DW$.
\end{proof}
The sets $A^N$ have rather irregular growth. The next theorem shows that if the growth pattern is sufficiently regular, then the sequence has property $DW$. First note the following remarks: Let $\alpha_i = 1 + (1/2^i)$. Then for all $i \geq 1$ we have $(1/\alpha_i) + \alpha_{i + 1} < 2$. If $\varepsilon$ is small, then there exists a maximal $q(\varepsilon)$ such that, for $i = 1,2,\dots,q(\varepsilon)$, $(1/a) + b \leq 2$ whenever $\alpha_i - \varepsilon \leq a \leq \alpha_i$ and $\alpha_{i + 1} - \varepsilon \leq b \leq \alpha_i$. It is clear that $q(\varepsilon) \to \infty$ as $\varepsilon \to 0^+$.
\begin{thm} \label{thm: 9}
Let $B = \{b_1 1$ there exist integers $i,k,s$ such that
(i) $b_{j + 1}/b_j \leq \alpha_{s + t}$ for $i \leq j \leq i + k$,
(ii) $b_{i + k}/b_i \geq \prod \alpha_r$ where the product is taken over $s + 1 \leq r \leq s + t$, and
(iii) $s + t \leq q(\varepsilon)$, where $\varepsilon = 2\max\{(b_{j + 1}/b_j) - 1:i \leq j \leq i + k\}$.
Then $B$ has property $DW$.
\end{thm}
\begin{proof} Let $t>1$. Take $i,k,$ and $s$ to satisfy the above three properties. Let $a_1 = b_{i + n(1)}$, where $n(1)$ is the largest integer $>0$ such that $b_{i + n(1)}/b_i \leq \alpha_{s + 1}$. Next take $a_2 = b_{i + n(2)}$, where $n(2)$ is the largest integer $>n(1)$ such that $b_{i + n(2)}/b_{i + n(1)} \leq \alpha_{s + 2}$. Continue in this manner forming the subsequence $\{a_1,a_2,\dots,a_t\}$ of $B$. Condition (i) assures us that each $n(g)$ exists as long as $n(g) \leq k$. But condition (ii) implies that $n(t) \leq k$ for, otherwise,
\begin{align*}
b_{i + k}/b_i < b_{i + n(t)}/b_i &= (b_{i + n(1)}/b_i)(b_{i + n(2)}/b_{i + n(1)}) \cdots (b_{i + n(t)}/b_{i + n(t - 1)}) \\
&\leq \prod_{s + 1\leq r \leq s + t} \alpha_r.
\end{align*}
Now we show $a_1,a_2,\dots,a_t$ is a $DW$. For this we need only show that $2a_{j + 1} \geq a_j +a_{j + 2}$ for each $j = 1,2,\dots,t - 2$. This is equivalent to
\[ \frac{1}{a_{j + 1}/a_j} + \frac{a_{j + 2}}{a_{j + 1}} \leq 2. \]
By the remarks preceding the theorem and condition (iii), it will suffice to show that
\[ \alpha_{s + j} - \varepsilon \leq b_{i + n(j)}/b_{i + n(j - 1)} \leq \alpha_{s + j} \]
for each $j = 1,2,\dots,t$ (where $n_0 = 0$). This follows easily:
\begin{align*}
\alpha_{s + j}- \frac{b_{i + n(j)}}{b_{i + n(j-1)}} &< \frac{b_{i + n(j) + 1} }{b_{i + n(j-1)}} - \frac{b_{i + n(j)}}{b_{i + n(j-1)}} \\
&= \frac{b_{i + n(j)}}{b_{i + n(j-1)}} \left( \frac{b_{i + n(j) + 1}}{b_{i + n(j)}} - 1 \right) \\
&\leq \alpha_{s + j} (0.5\varepsilon) < \varepsilon. \end{align*}
\end{proof}
\begin{cor} \label{cor: 4}
If $b_{i + 1}/b_i \to 1$ ($i \to \infty$), then $B$ has property $DW$.
\end{cor}
\begin{proof} We show that $B$ satisfies the conditions of the Theorem. Let $t > 1$. Choose $s = 0$. Next choose $i$ large enough so that (i) holds (for \emph{all} $j \geq i$) and $ t \leq q(\varepsilon)$, where $\varepsilon = 2\sup_{j \geq i} \{(b_{j + 1}/b_j) - 1\}$. Finally choose $k$ so that $b_{i + k}/b_i \geq \prod_{1 \leq r \leq t} \alpha_r$.
\end{proof}
From Corollary~\ref{cor: 4} it follows that a sequence of the form $a_n = \exp(n^\varepsilon)$ has $DW$. Conditions which are both necessary and sufficient for a set to possess property $DW$ appear to be difficult to state.
\section{Remarks} \label{sec: 5}
It would be nice to prove either Theorem~\ref{thm: 2}, replacing $QP$ by $CP$, or Theorem~\ref{thm: 3}, replacing $C$ by $CP$. (It is, of course, very unlikely that would prove both of these modified theorems as that would give us Erd\H{o}s' Conjecture.)
It is known that the sequence of squares $\{n^2\}$ does not have property $AP$. Does it have preoprty $QP, CP,$ or $C$?
Professors Joel Spencer and Noga Alon have announced that, in Theorem~\ref{thm: 4}, $ck^3 \leq f(k)$ for a suitable constant $c$. They have, evidently, also sigificantly improved both bounds for $g(\varepsilon, k)$ in Corollary~\ref{cor: 3}: For suitable constants $c$ and $d$ (depending only on $\varepsilon$)
\[ c^{k^{1/2}} \leq g(\varepsilon , k) \leq d^{k^{1/2}\log k}. \]
Besides descending waves, one can also consider ascending waves. A sequence $\{a_1 < \cdots < a_k\}$ will be a $k-AW$ if $a_{i + 1} - a_i \leq a_{i + 2} - a_{i + 1}$ for $1 \leq i \leq k - 2$. There are arbitrarily large finite sets with no $3-AW$ and yet every infinite set has property $AW$, in fact, any infinite set will contain an infinite subsequence which is an ascending wave. We can show that for each $k$ there is a smallest number $h(k)$ such that for $n \geq h(k)$ any set $\{a_1 < \cdots < a_n\}$ of integers has a $k-AW$ or a $k-DW$. In fact, P. Erd\H{o}s and Gy. Szekeres~\cite{erdos+szekeres1935} showed that, if $f(k,t)$ denotes the smallest positive integer such that any set $\{a_1 < a_2 < \cdots < a_{f(k,t)}\}$ contains either a $k-AW$ or a $t-DW$, then $f(k,t) = f(k-1,t) + f(k,t -1) - 1$ $(k \geq 2, t \geq 2)$. This immediately gives
\[ f(k,t) = \binom{k + t - 4}{k - 2} + 1 \quad (k \geq 2, t \geq 2), \]
so that $h(k) = f(k,k) \sim 4^{k-2} /\sqrt{\pi k}$.
\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}
**