%%%% 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<x_2< \cdots <x_k$ will be called a \emph{$k$-term quasi-progression of diameter $d$} (abbreviated $k -QP(d)$) if 
\[ \diam \{x_{i + 1} - x_i: 1 \leq i\leq k - 1\} \leq d, \]
i.e.,
\[ \exists N \textup{ such that } N \leq x_{i + 1} - x_i \leq N + d \textup{ for } 1 \leq i \leq k - 1. \]
A set of positive integers has property $QP$ if, for some fixed $d$, the set contains a $k-QP(d)$ for each $k \geq 1$. Noting that a $k$-term arithmetic progression is just a $k-QP(0)$ we get immediately that $AP \Rightarrow QP$.

The sequence $x_1 < x_2 < \cdots < x_k$ will be called a \emph{$k$-term combinatorial progression of order $d$} (abbreviated $k-CP(d)$) if 
\[ | \{[x_{i + 1} - x_i]: 1 \leq i \leq k - 1\}| \leq d. \]
(The integer function is present for the cases, mentioned below, when the $x_i$ may not be integers.) A set of positive integers has property $CP$ if, for some fixed $d$, the set contains a $k-CP(d)$ for each $k \geq 1$. Cleraly, when the $x_i$ are integers, a $k-QP(d)$ is a $k-CP(d + 1)$ and so $QP \Rightarrow CP$.

Finally, a sequence $x_1 < x_2 < \cdots < x_k$ is called a \emph{$k$-term descending wave} ($k-DW$) if the difference sequence is non-increasing, i.e.,
\[ x_{j + 1} - x_j \geq x_{j + 2} - x_{j + 1} , \quad \textup{for } 1 \leq j \leq k - 2. \]
If a set of positive integers contains arbitrarily large descending waves then we say that it has property $DW$.

We observe that the definitions of $k-QP(d)$, $k-CP(d)$, and $k-DW$ can be applied to a sequence $x_1<x_2<\cdots <x_k$ even if the terms of this sequence are not integer valued. Thus a countable set of real numbers $R = \{r_1 < r_2 < \cdots \}$ can be said to have properties $QP,CP,$ or $DW$. However, it is easy to prove that, if $R$ satisfies the reasonable condition that $r_{i + 1} - r_i \geq 1$ for sufficiently large $i$, then $R$ has property $QP,CP,DW$ exactly when the corresponding set of integers $A = \{[r_i]: i \geq 1\}$ has the same property.

\section{Relations between \emph{AP, QP, CP, C, DW}} \label{sec: 2}

Let us restate our claim in the form of a theorem. The proof will occupy the remainder of this section.

\begin{thm} \label{thm: 1}
$AP \Rightarrow QP \Rightarrow CP \Rightarrow C \Rightarrow DW$, and none of these implications is reversible.
\end{thm}

\begin{proof} We have already seen that $AP \Rightarrow QP \Rightarrow CP$. The implication $C \Rightarrow DW$ is also easy to see: If a set $A$ contains the $m$-cube~(\ref{eq: 1}) above, where we may assume that $y_1 \geq y_2 \geq \cdots \geq y_m$, then $A$ also contains the $(m + 1)-DW$
\[ a, a + y_1, a + y_1 + y_2, \cdots a + y_1 + y_2 + \cdots + y_m. \]
We proceed to prove $CP \Rightarrow C$. This easily follows from the statement: For all $m,d \geq 1$, there exists $r = r(d,m)$ such that, if $x_1,x_2,\dots,x_r$ is an $r-CP(d)$, then $\{x_1,x_2,\dots,x_r\}$ contains an $m$-cube. The proof of this is by inductinon on $m$. For $m = 1$ we let $r = 2$. Any $2-CP(d)$ is a 1-cube. For $m + 1$ we take $r = r(d,m + 1) = t \cdot r(d,m)$, where $t$ is determined presently. Let $r' = r(d,m)$ and let $x_1,x_2,\dots,x_{tr'}$ be a $tr'-CP(d)$. Each block
\[ x_{kr' + 1}, x_{kr' + 2}, \dots, x_{(k + 1)r'} \quad \textup{for }0 \leq k \leq t - 1, \]
is an $r'-CP(d)$ with the same set $\{f_1,f_2,\dots,f_d\}$ of possible differences. By the inductive hypothesis, each of these blocks contains an $m$-cube. Any generator $y_i$ of an $m$-cube in a block is of the form
\[ f_{i_1} + f_{i_2} + \cdots + f_{i_j}, \]
where $j < r'$. Here there are less than $(d + 1)^{r'}$ different generators and so less than $(d + 1)^{r'm}$ $m$-tuples of generators. Hence, if $t = (d + 1)^{r'm}$, then two of the blocks in $x_1,x_2,\dots,x_{tr'}$ will have $m$-cubes with the same set of generators. If these two are $\langle x_i,y_1,y_2,\dots,y_m \rangle$ and $\langle x_j,y_1, y_2,\dots,y_m \rangle$ with $x_i < x_j$, then 
\[ \langle x_i, y_1,y_2,\dots,y_m,x_{j - x_i} \rangle \]
is an $(m + 1)$-cube in $\{x_1,x_2,\dots,x_r\}$.

We now proceed to show that none of the reverse implications hold. First $DW \not\Rightarrow C$. Rearrange the sequence $1,2,4,8,\dots,$ of powers of two, forming a sequence $d_0,d_1,d_2, \dots,$ which has arbitrarily long decreasing blocks (e.g., 1,4,2,32,16,8,512,256,$\dots$). Next define
\[ a_0 = 1, \quad a_{i + 1} = a_i + d_i \]
and let $A = \{a_i: i \geq 0\}$. Clearly $A$ has $DW$. If $A$ contains a 2-cube $\langle b,y_1,y_2 \rangle$, then $y_1 = b + y_1 - b = a_j - a_i = d_i + d_{i + 1} + \cdots + d_{j - 1}$ and $y_1 = b + y_1 + y_2 - (b + y_2) = a_t - a_s = d_s + d_{s + 1} + \cdots + d_{t - 1}$. Sums of distinct powers of two are unique and so $j = t$ which contradicts $a_t > 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_2<b_3<\cdots <b_n$ be an increasing sequence in $A$ and suppose $b_{i + 1} - b_i = b_{r + 1} - b_r$, where $i < r$. It follows that there exists $j$, $i < j < r$, such that $b_{j + 1} - b_j > b_{i + 1} - b_i$. Now assume that $A$ has property $CP$ for order $d$. If $b_1<b_2<b_3<\cdots<b_n$ is an $n-CP(d)$ in $A$, then by assumption $b_{i + 1} - b_i$ can take on at most $d$ different values. But if $n$ is very large, say $n = d^{(d + 1)}$, we can find $d^d$ indices $i$ with the same $b_{i + 1} - b_i$ and in between these indices $d^{(d-1)}$ other indices $j$ with a larger $b_{j + 1} - b_j$, and so on. In this way we get more than $d$ differences appearing in the sequence $\{b_i\}$ contrary to our supposition.

Next $CP \not\Rightarrow QP$. We will make use of remarkable sequence of zeros and ones, $\{z_1,z_2,z_3,\dots\}$, which has the property that there do not exist five adjacent blocks of equal composition. (This means that, for any $a \geq 0$ and $d \geq 1$, not all of the five numbers 
\[ \sum_{i = 1}^d z_{a + kd + i}, \quad 0 \leq k \leq 4, \]
are the same.) The existence of such a sequence is due to J. Justin~\cite{justin1972-1}. For each $t \geq 1$ let $S(t)$ be the following set of $t$ positive integers,
\[ S(t) = \{5^t + t + z_1, 5^t + 2t + z_1 + z_2, \dots, 5^t + t^2 + z_1 + z_2 + \cdots + z_t\}. \]
Let $B(t)$ be the set $tS(t) = \{tx: x \in S(t)\}$. One easily checks that the first member of $S(t + 1)$ (resp. $B(t + 1)$) is more than twice as large as the greatest member of $S(t)$ (resp. $B(t)$). Each $B(t)$ is a $t-CP(2)$ since a difference is 
\begin{align*} t5^t + &(k + 1)t^2 + t(z_1 + \cdots +z_{k + 1}) - (t5^t + kt^2 + t(z_1 + \cdots +z_k)) \\
&= t^2 + tz_{k + 1} = t^2 \textup{ or }t^2 + t. \end{align*}
We define $A = B(1) \cup B(2) \cup \cdots $. Clearly $A$ has property $CP$. Now suppose that $A$ has property $QP$ for diameter $d$. Let $t_0 > d$. Let $P = \{b_1 < b_2 < b_3 < \cdots <b_n\}$ be an $n-QP(d)$ in $A$. Suppose $\{b_i\}$ intersects $B(t_1), B(t_2),$ and $B(t_3)$, where $t_0 \leq t_1<t_2<t_3$. Let $b_i$ be a member of $P \cap B(t_1)$ and $b_j$ be the largest member of $P \cap B(t_2)$. Then $(b_{j + 1} - b_j) - (b_{i + 1} - b_i) > 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<b_2<b_3<\cdots <b_n\}$, in $A$ were sufficiently long, then $P$ would have to contain six terms in some $S(t)$. This, in turn, would again produce five adjacent blocks of $\{z_i\}$ which have the same composition.
\end{proof}

\section{Sets with Infinite Reciprocal Sum} \label{sec: 3}

Here we prove the two results on sets with infinite reciprocal sum mentioned in the Introduction (Some other results on sets with infinite reciprocal sum can be found in~\cite{brown+freedman1987}.)

\begin{thm} \label{thm: 2}
The following two statements are equivalent:
\begin{enumerate}
\item (Erd\H{o}s' conjecture). If $A$ is any set of positive integers such that the sum of the reciprocals of the elements of $A$ is infinite, then $A$ property $AP$.

\item If $A$ is any set of positive integers such that the sum of the reciprocals of the elements of $A$ is infinite, then $A$ has property $QP$.
\end{enumerate}
\end{thm}

\begin{proof} Clearly $1 \Rightarrow 2$. We show that ``not 1" implies ``not 2." Assume that $A$ is a set of positive integers with $\sum_{i \in A} 1/i = \infty$ and which contains no $k$-term arithmetic progression for a fixed $k$. We will construct a set $B$ with infinite reciprocal sum, which does not have property $QP$. We note that, for each $n \geq 1$, $g \geq 0$, the set $nA + g = \{na_i + g: i\geq 1\}$ does not contain any $k-QP(n - 1)$. For otherwise we have elements $a_1,a_2,\dots,a_k$ in $A$ with 
\[ N \leq (na_{j + 1} + g) - (na_j + g) \leq N + (n -1), \quad 1 \leq j \leq k - 1, \]
which implies that all $a_{j + 1} - a_j$ are equal, contrary to assumption.

We construct finite sets $B_1,B_2,B_3,\dots,$ as follows. Let $B_1$ consist of enough terms of $A$ so that $\sum_{i \in B_1} 1/i > 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<a_2<\cdots<a_t\}$, $A \subseteq \{1,2,\dots,n\}$, and $t \geq \lambda(k)$, then $A$ contains a $k$-cube. Thus, if $A = \{a_1,a_2,a_3,\dots\}$ is any set of positive integers which does not contain any $k$-cube, we get, for $n \geq 1$, $A(n) < \lambda(k)$, where $A(n) = |A \cap \{1,2,\dots,n\}|$. Hence
\[ n = A(a_n) < \alpha \cdot a_n^{1 - (1/2^k)}, \]
so that $a_n \geq cn^{1 + \varepsilon}$, where $c$ and $\varepsilon$ are positive constants. This implies that $\sum_n 1/a_n < \infty$.
\end{proof}

\section{Descending Waves} \label{sec: 4}

We shall approach the problem of descending waves from several points of view. Our first is analogous to a result of van der Waerden. Let $f(k)$ be the smallest positive integer such that, if $\{1,2,\dots,f(k)\}$ is 2-colored, then there must be a monochromatic $k-DW$. Our first result bounds $f(k)$ above and below.

\begin{thm} \label{thm: 4}
$k^2 - k + 1 \leq f(k) \leq k^3/3 - 4k/3 + 3.$
\end{thm}

\begin{proof} For the lower bound, we need only observe that the 2-coloring
\[ \underbrace{00 \cdots 0}_{k - 1}\underbrace{11 \cdots 1}_{k - 1}\underbrace{00 \cdots 0}_{k - 2} \underbrace{11 \cdots 1}_{k - 2} \cdots \underbrace{00}_{2}\underbrace{11}_{2}\underbrace{0}_{1}\underbrace{1}_{1} \]
of $\{1,2,\dots,k^2 - k\}$ has no monochromatic $k-DW$.

For the upper bound we first prove a simple lemma: If $B_1,B_2,\dots,B_t$ are consecutive blocks of integers (i.e., $0 \leq b_1 < b_2 < \cdots < b_{t + 1}$, $B_i = [b_i + 1,b_{i + 1}]$), $|B_1| \geq |B_2| \geq \cdots \geq |B_t|$, $t \geq s^2 - s + 1$, and $x_i \in B_i$ for $1 \leq i\leq t$, then the set $\{x_1,x_2,\dots,x_t\}$ contains an $s-DW$ $\{x_{i_1},x_{i_2},\dots,x_{i_s}\}$ with $x_{i_s} = x_t$ and $x_{i_s} - x_{i_{s - 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<b$, then $\{1,a,b\}$ would be a $3-DW$). Hence
\[ |S| \leq n + 1 \leq 2n = 2\binom{n}{1}, \]
provided that $n \geq 1$ (i.e., $k = 3 \leq n + 2$).

Now fix $k \geq 3$ and let $\subseteq \{1 ,2,\dots,2^n\}$ be a set which contains no $(k + 1)-DW$. Then, as before, $I_t \cap S$ cannot contain any $k-DW$ (since adjoining 1 to such a $DW$ would give a $(k+1)-DW$ in $S$). Thus by the induction hypothesis we have, for $k \leq t + 2$,
\[ |S \cap \{2^t + 1, 2^t + 2,\dots, 2^{t + 1}\}| \leq 2^{k-2} \binom{t}{k - 2}. \]
For $k + 1 \leq n + 2$ we write
\[ \{1,\dots,2^n\} = \{1,\dots,2^{k-2}\} \cup \bigcup_{t = k-2}^{n-1} \{2^t + 1, \dots, 2^{t + 1}\}. \]
Thus we obtain
\begin{align*} 
|S| &\leq 2^{k-2} + \sum_{t = k - 2}^{n-1} 2^{k-2} \binom{t}{k-2} \\
&= 2^{k-2} \left( 1 + \binom{n}{k-1} \right) \leq 2^{k-1} \binom{n}{k-1}. \end{align*}
\end{proof}

Three corollaries follow from Theorem~\ref{thm: 5}.

\begin{cor} \label{cor: 1}
If $m \geq 2^{k-2}$ and $S$ is a subset of $\{1,2,\dots,m\}$ which contains no $k-DW$, then 
\[ |S| \leq \frac{2^{k-1}}{(k-2)!} (\log_2m)^{k-2}. \]
\end{cor}

\begin{cor} \label{cor: 2}
If an infinite sequence $S = \{a_1<a_2<a_3<\cdots\}$ contains no $k-DW$, then there is a constant $c>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<a_2<a_3<\cdots\}$ where the $a_n$ are real numbers and $a_{n + 1} - a_n \geq 1$ for all large $n$ (see Section~\ref{sec: 1}). The remarks following Corollary~\ref{cor: 2} above show that if $a_n$ increases slowly then $\{a_n\}$ has $DW$. On the other hand, the next theorem shows that $a_n$ cannot grow as an exponential and still have that property.

\begin{thm} \label{thm: 6}
For each real $\varepsilon > 0$, let $k(\varepsilon)$ be the maximum, over all sequences $A = \{a_1<a_2<a_3<\cdots\}$ with $a_{n + 1}/a_n \geq 1 + \varepsilon$ for all $n$, of the length of the longest descending wave in $A$. Then 
\[ [1/\varepsilon] + 1 \leq k(\varepsilon) \leq (1/\varepsilon) + 2. \]
\end{thm}

\begin{proof} Let $0 < b_0 < b_1 < \cdots < b_t$ be a $DW$ in such a sequence $A$. Then $b_t = (b_t - b_{t - 1}) + \cdots + (b_1 - b_0) + b_0 \geq t(b_t - b_{t -1}) + b_0$, so that 
\[ 1 \geq t\left( 1 - \frac{b_{t-1}}{b_t} \right) + \frac{b_0}{b_t} \geq t\left( 1 - \frac{1}{1 + \varepsilon} \right) + \frac{b_0}{b_t} > 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<b_2<b_3<\cdots\}$ be a set with the following property: For each $t > 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}