Erdős-Szekeres for first differences - MathOverflow

Erdős-Szekeres for first differences

2012-03-03T17:27:53Z

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.

Answer by Boris Bukh for Erdős-Szekeres for first differences

2012-03-04T10:11:37Z

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.

Answer by Sergey Norin for Erdős-Szekeres for first differences

2012-03-13T22:04:57Z

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.