MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is the following true?

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}$.

Definition of an $(M,N)$-expander:

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 \begin{equation} \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 \end{equation} or \begin{equation} \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 \end{equation}

Is this an open question?

This is a question that was asked (formulated a little differently) in the following paper, of which I am one of the authors:

‘Relative ranks of Lipschitz mappings on countable discrete metric spaces’, Topology and its Applications 158 (2011) 412-423;

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.


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):


If $\mathfrak{X}$ is any countable subset of the real numbers, then

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}$;

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).

share|cite|improve this question

If I have understood the question correctly, I believe this is false.

Construct an infinite, increasing, unbounded sequence using the following two definitions for the next term

x_i+1 = x_i + 1/x_i

x_i+1 = x_i^2

Starting with 1 as the first term, use the first definition once, then the second definition once, then the first definition twice, then the second definition twice, then the first definition thrice, then the second thrice, ect.

This would create arbitrarily long sections where the differences were very small or very large. No matter what N and M were, you could choose k to be large enough that it would run into a section longer than length M where the differences would be arbitrarily large and another where they would be arbitrarily small.

Hope my reasoning is clear and correct.

share|cite|improve this answer
Nice example. As I understand things, one can switch to having very large or very small ratios, and it can began with any term. I do not see this as a counterexample. I recommend leaving it as a source to inspire others. – The Masked Avenger Feb 20 '15 at 2:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.