# Erdős-Szekeres for first differences

The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$ real numbers contains a monotonic $(n+1)$-term subsequence. Suppose, however, that we want to find a subsequence which is not necessarily monotonic itself, but has the sequence of its first differences monotonic. How long has the original sequence to be to ensure that such an $(n+1)$-term subsequence can be found?

For positive integer $n$, what is the smallest integer $N=N(n)$ such that every $N$-element sequence of real numbers contains an $n$-element subsequence $(a_1,\ldots,a_n)$ with either $a_2-a_1\le\dotsb\le a_n-a_{n-1}$, or $a_2-a_1\ge\dotsb\ge a_n-a_{n-1}$?

Trivially, we have $N(1)=1$, $N(2)=2$, and $N(3)=3$. However, I do not know the value of $N(4)$.

The state of the art as of 05.03.12. The nice argument of Boris Bukh (below) shows that $N(n)$ is exponential in $n$. Still, this does not completely settle the problem.

Updated 16.03.12: the absolutely beautiful, must-upvote solution by Sergey Norin is posted below.

-
The correct theorem is that, for $n \ge 1$, a sequence of length $n^2+1=M(n,n)$ contains a monotonic sub-sequence of length $n+1$ and, slightly more generally, that a sequence of length $rs+1=M(r,s)$ has an increasing sequence of length $r+1$ or a decreasing sequence of length $s+1$. (It is not hard to discover an example showing that this is best possible). There is also no reason to mention real numbers, just the integers (or any total order except that you want to consider differences later). –  Aaron Meyerowitz Mar 3 '12 at 23:18
I replaced $n$ with $n+1$ -- thanks for the correction. As to your second point -- there is no reason to confine to integers as the result is true in the more general settings of real numbers. (Nobody argues that the two statements are in essence equivalent, but formally, the "real version" is stronger.) –  Seva Mar 4 '12 at 7:54
The theorem for integers actually implies the coresponding one for any total order : any sequence of $n^2+1$ objects, considered as a set, is order isomorphic to some finite set of integers. –  js21 Mar 4 '12 at 10:06
Is it even clear that $N(n) < \infty$ for all $n$? –  Noam D. Elkies Mar 5 '12 at 7:25
@Noam: The easiest way to see this is to apply the hypergraph Ramsey theorem. Given a sequence $(a_1,\ldots, a_N)$, consider the complete $3$-uniform hypergraph with the vertex set $[N]$, and color every edge red or blue according to whether the corresponding triple of elements is in a convex or concave position. (More precisely, the edge $\{i,j,k\}$ with $1\le i<j<k\le N$ is colored red if $a_j-a_i\le a_k-a_j$ and blue otherwise.) Now, every vertex set inducing a monochromatic subgraph corresponds to a subsequence with monotonic first differences. –  Seva Mar 5 '12 at 8:42

For brevity let me call a sequence with non-decreasing first differences convex, and a sequence with non-increasing first differences concave.

Let $M(r,s)$ denote the minimum integer $N$ so that every $N$-element sequence of real numbers contains a convex subsequence of length $r+1$ or a concave subsequence of length $s+1$. Below I attempt to show that

$$M(r,s)=\binom{r+s-2}{r-1}+1.$$

The lower bound: Let $[m]$ denote the set $\{1,\ldots,m\}$.

For $S \subseteq [r+s-2]$, let $x_S := \sum_{i \in S}3^i$. Consider the sequence $(x_S\;|\; S \subseteq [r+s-2], |S|=s-1)$ with elements in increasing order. It has $\binom{r+s-2}{r-1}$ elements. We will show that this sequence contains no convex subsequence of length $r+1$ and no concave subsequence of length $s+1$.

Let $x_{S_1},x_{S_2}, \ldots,x_{S_n}$ be a convex subsequence. Let $d_i$ be the maximum element of $S_{i+1} \setminus S_{i}$. Then $3^{d_i}/2 < x_{S_{i+1}}-x_{S_i}< 3^{d_i+1}/2.$ It follows that $(d_1,d_2,\ldots,d_{n-1})$ is a strictly increasing sequence, and that $d_i \not \in S_1$ for $i \in [n-1]$. Therefore $n \leq r$ as desired.

The proof showing that there is no concave subsequence of length $s+1$ is symmetric. (One can replace $x_{S_i}$ by $x_{[r+s-2]}-x_{S_i}$.)

The upper bound: The goal is to imitate the elegant pigeonhole argument of Seidenberg for Erdős-Szekeres theorem. (See e.g. Wikipedia.)

Let $N = \binom{r+s-2}{r-1}+1$. Let ${\bf a}=(a_1,\ldots, a_N)$ be a sequence.

For $i \in [N]$ and $k \in [r-1]$ let $\alpha_i(k)$ be the minimum real number so that a $(k+1)$-term convex subsequence of ${\bf a}$ ending with $a_i$ has $\alpha_i(k)$ as the difference of the last two terms. Set $\alpha_i(k)=+\infty$ if no such subsequence exists. Note that for fixed $i$ the sequence $\alpha_i(\cdot)$ is non-decreasing.

Analogously, for $k \in [s-1]$ we define $\beta_i(k)$ to be the maximum real number so that a $(k+1)$-term concave subsequence of ${\bf a}$ ending with $a_i$ has $\beta_i(k)$ as the difference of the last two terms. Set $\beta_i(k)=-\infty$ if no such subsequence exists. The sequence $\beta_i(\cdot)$ is non-increasing.

For given $i$ arrange the elements of the multiset $\{\alpha_i(1),\ldots, \alpha_i(r-1),\beta_i(1),\ldots,\beta_i(s-1)\}$ in increasing order, with alphas preceding betas, when the values are the same. Now we consider the resulting sequence as a sequence of $r+s-2$ symbols each of which is either $\alpha$ or $\beta$, ignoring the indexing. Call this sequence $\bf \chi_i$. For example, we always have $${\bf \chi_1}=(\beta, \ldots,\beta, \alpha, \ldots, \alpha),$$ $${\bf \chi_2}=(\beta,\ldots,\beta, \alpha, \beta, \alpha, \ldots, \alpha),$$ and ${\bf \chi_3}$ depends on $a_1$, $a_2$ and $a_3$.

There are $N-1$ possible sequences and by pigeonhole principle we have ${\bf \chi_i}={\bf \chi_j}$ for some $1 \leq i < j \leq N$. Let $z=a_j-a_i$. Let $r'$ be chosen to be maximum so that $\alpha_{i}(r') \leq z$, and let $r'=0$ if no such $r'$ exists. Let $s'$ be chosen to be maximum so that $\beta_{i}(s') \geq z$, and let $s'=0$ if no such $s'$ exists. Note that $\alpha_{j}(r'+1) \leq z$ and $\beta_{j}(s'+1) \geq z$. If $r'=r-1$ or $s'=s-1$ then $\bf{a}$ contains a convex subsequence of length $r+1$ or a concave subsequence of length $s+1$ as desired. Otherwise, $r'+1$ alphas precede $s'+1$ betas in $\chi_j$, while in $\chi_i$ after the first $r'+1$ alphas we encounter only $\leq s'$ betas. This contradiction finishes the proof.

-
I do not follow the conclusion of the proof: how do you use that $r'\neq r-1$ and $s'\neq s-1$ to deduce the penultimate sentence? –  Boris Bukh Mar 14 '12 at 10:28
@Boris: If $r'=r-1$ then $\alpha_i(r'+1)$ is not in the sequence. –  Sergey Norin Mar 14 '12 at 12:58
@Sergey: I still do not follow. At the beginning of the "Otherwise,..." sentence we know that $r'\leq r-2$ and $s'\leq s-2$. The definition of $s'$ and $r'$ gives $\alpha_i(r')\leq z$, $\alpha_i(r'+1)>z$ and $\beta_i(s')\geq z$, $\beta_i(s'+1)<z$. This means that to the left $z$ there are precisely $r'$ alphas, and to the right there are $s'$ betas. This is different from what the penultimate sentence says. –  Boris Bukh Mar 14 '12 at 14:17
@Boris: I have changed the penultimate sentence slightly after your first comment. (The original version was unnecessarily strong and false.) As $\alpha_i(r'+1)>z$ and $\beta_i(s'+1)< z$, using the monotonicity of the $\alpha$ and $\beta$ sequences we see that to the right of the first $r'+1$ alphas there are at most $s'$ betas. –  Sergey Norin Mar 14 '12 at 19:00

The $N(n)$ is exponential in $n$. First, I present a lower bound. The construction is recursive. Call a sequence whose first differences are monotone, $1$-monotone. Suppose $\mathbf{a}=a_1,\dotsc,a_M$ is a sequence that contains no $1$-monotone $N$-term subsequence. Pick an number $R$ that is larger than $\max_{i,j}(a_i-a_j)$. Then the sequence $\mathbf{b}=a_1,\dotsc,a_M,a_1+R,\dotsc,a_M+R$ contains no $1$-monotone subsequence of length $N+1$. Indeed, the subsequence cannot contain $N$ elements from the same half of $\mathbf{b}$. Hence, it must contain at least $2$ elements from each of the halves, which is impossible by the choice of $R$.

The upper bound is also recursive. We will find a monotone increasing subsequence with a stronger property that either $a_i-a_1\leq a_{i+1}-a_i$ (fast-increasing) or $a_{last}-a_i\leq a_i-a_{i-1}$ (fast-decreasing). It suffices to only work with the sequences that are monotone increasing (by losing only a square, and reversing the sequence if necessary). Let $N(I,D)$ be the length of the longest monotone sequence without a fast-increasing subsequence of length $I$, and without fast-decreasing subsequence of length $D$. I claim that $N(I,D)\leq N(I-1,D)+N(I,D-1)$ (and so $N(n,n)$ is bounded by an exponential function). Suppose $\mathbf{a}$ is a monotone increasing sequence. Let $X$ be the median of $\mathbf{a}$. The median splits $\mathbf{a}$ into two equally long sequences $\mathbf{b}$ and $\mathbf{c}$. By induction applied to $\mathbf{b}$ we can find either fast-increasing sequence of length $I-1$ or fast-decreasing sequence of length $D$. In the latter case, we are done. Else, let $\mathbf{b}'$ be the fast-increasing subsequence of $\mathbf{b}$. Similarly, there is $\mathbf{c}'$ in $\mathbf{c}$ that is fast-decreasing. If $X-a_1\leq a_{last}-X$, then the concatenation of $\mathbf{b}'$ with $a_{last}$ is the desired sequence. If $X-a_1\geq a_{last}-X$ then the concatenation of $a_1$ with $\mathbf{c}'$ is a desired subsequence.

-
I wonder whether the proof of the lower bound is correct. First of all, you probably want to replace $R$ by $N$ in its fourth and fifth occurences. But then, take the sequence $0,10,0$ which does not contain a $1$-monotone subsequence of size $N=3$. But the sequence $0,10,0,5,15,5$ contains a $1$-monotone subsequence of size $N+1=4$: $0,0,5,15$. –  Pascal Maillard Mar 4 '12 at 10:36
Thanks for spotting typos. R must be larger than all the possible differences. –  Boris Bukh Mar 4 '12 at 10:38
The lower bound seems fine to me, but I do not quite understand the proof of the upper bound - specifically, not sure exactly how the assertion in the last sentence follows. –  Seva Mar 4 '12 at 10:40
@Boris: right. Nice argument. –  Pascal Maillard Mar 4 '12 at 10:55
@Seva: I made the upper bound argument clearer. –  Boris Bukh Mar 4 '12 at 10:59