Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.