Erdős-Szekeres for first differences - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T02:18:39Z http://mathoverflow.net/feeds/question/90128 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90128/erds-szekeres-for-first-differences Erdős-Szekeres for first differences Seva 2012-03-03T17:27:53Z 2012-03-16T13:21:44Z <p>The classical <a href="http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem" rel="nofollow">Erdős-Szekeres theorem</a> 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 <em>first differences</em> monotonic. How long has the original sequence to be to ensure that such an $(n+1)$-term subsequence can be found?</p> <blockquote> <p>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}$?</p> </blockquote> <p>Trivially, we have $N(1)=1$, $N(2)=2$, and $N(3)=3$. However, I do not know the value of $N(4)$.</p> <hr> <p>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.</p> <p>Updated 16.03.12: the absolutely beautiful, must-upvote solution by Sergey Norin is posted below.</p> http://mathoverflow.net/questions/90128/erds-szekeres-for-first-differences/90188#90188 Answer by Boris Bukh for Erdős-Szekeres for first differences Boris Bukh 2012-03-04T10:11:37Z 2012-03-04T12:15:22Z <p>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, <em>$1$-monotone</em>. 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$.</p> <p>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.</p> http://mathoverflow.net/questions/90128/erds-szekeres-for-first-differences/91128#91128 Answer by Sergey Norin for Erdős-Szekeres for first differences Sergey Norin 2012-03-13T22:04:57Z 2012-03-14T13:04:24Z <p>For brevity let me call a sequence with non-decreasing first differences <em>convex</em>, and a sequence with non-increasing first differences <em>concave</em>.</p> <p>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</p> <blockquote> <p>$$M(r,s)=\binom{r+s-2}{r-1}+1.$$</p> </blockquote> <p><strong>The lower bound</strong>: Let $[m]$ denote the set $\{1,\ldots,m\}$. </p> <p>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$.</p> <p>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 &lt; x_{S_{i+1}}-x_{S_i}&lt; 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. </p> <p>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}$.)</p> <p><strong>The upper bound</strong>: The goal is to imitate the elegant pigeonhole argument of Seidenberg for Erdős-Szekeres theorem. (See e.g. <a href="http://en.wikipedia.org/wiki/Erd%25C5%2591s%25E2%2580%2593Szekeres_theorem" rel="nofollow">Wikipedia</a>.) </p> <p>Let $N = \binom{r+s-2}{r-1}+1$. Let ${\bf a}=(a_1,\ldots, a_N)$ be a sequence. </p> <p>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.</p> <p>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.</p> <p>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$. </p> <p>There are $N-1$ possible sequences and by pigeonhole principle we have ${\bf \chi_i}={\bf \chi_j}$ for some $1 \leq i &lt; 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.</p>