The classical [Erdős-Szekeres theorem](http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_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.



Erdős-Szekeres for first differences
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](http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem).) 


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.


