Does every strictly increasing, unbounded sequence of positive real numbers contain arbitrarily long, finite subsequences which are "sort of increasing" or "sort of decreasing" (as defined below)? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T08:07:45Z http://mathoverflow.net/feeds/question/95244 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95244/does-every-strictly-increasing-unbounded-sequence-of-positive-real-numbers-conta Does every strictly increasing, unbounded sequence of positive real numbers contain arbitrarily long, finite subsequences which are "sort of increasing" or "sort of decreasing" (as defined below)? Yann Peresse 2012-04-26T10:50:50Z 2012-04-26T10:50:50Z <h3>Is the following true?</h3> <p>If $(x_0, x_1, \dots)$ is a strictly increasing, unbounded sequence of positive real numbers, then there exist fixed $M,N \geq 1$ such that the sequence $(x_0, x_1, \dots)$ contains an ($M,N$)-expander of length $k$ for every $k\in \mathbb{N}$.</p> <h3>Definition of an $(M,N)$-expander:</h3> <p>If $M,N \geq 1$ are integers, then an $(M, N)$-expander of length $k$ of $(x_0, x_1, \dots)$ is a subsequence $(x_{i[1]},x_{i[2]},\cdots,x_{i[k]})$ of $\mathfrak{X}$ such that $i[j+1]-i[j]\leq M$ for all $1\leq j\leq k-1$ and either $$\frac{x_{i[n+1]}-x_{i[n]}}{x_{i[m+1]}-x_{i[m]}}\leq N \textrm{ for all }1\leq m\leq n\leq k-1$$ or $$\frac{x_{i[m+1]}-x_{i[m]}}{x_{i[n+1]}-x_{i[n]}}\leq N \textrm{ for all }1\leq m\leq n\leq k-1$$</p> <h3> Is this an open question?</h3> <p>This is a question that was asked (formulated a little differently) in the following paper, of which I am one of the authors:</p> <p>‘Relative ranks of Lipschitz mappings on countable discrete metric spaces’, Topology and its Applications 158 (2011) 412-423;</p> <p>In that sense, it is an open problem. However, as far as I know, this question has been not been widely considered, and so it is not a well-known open problem that is known to be difficult. If, nevertheless, this question is inappropriate for this forum, then I appologise.</p> <h3>Motivation </h3> <p>If the answer is "yes, it is true", then the results in the the paper mentioned above prove the following conjecture about the semigroup $\mathfrak{L}_{\mathfrak{X}}$ of all Lipschitz functions from a countable subset $\mathfrak{X}$ of $\mathbb{R}$ to itself (where the semigroup operation is composition of functions):</p> Conjecture: <p>If $\mathfrak{X}$ is any countable subset of the real numbers, then</p> <p>either $\mathfrak{X}$ contains a Cauchy sequence and there exists a single function from $\mathfrak{X}$ to $\mathfrak{X}$ that together with $\mathfrak{L}_{\mathfrak{X}}$ generates all functions from $\mathfrak{X}$ to $\mathfrak{X}$;</p> <p>or $\mathfrak{X}$ contains no Cauchy sequences and the least number of functions from $\mathfrak{X}$ to $\mathfrak{X}$ that together with $\mathfrak{L}_{\mathfrak{X}}$ generate all functions from $\mathfrak{X}$ to $\mathfrak{X}$ is the uncountable cardinal $\mathfrak{d}$ (the dominating number).</p>