The number of relevant scales for a finite metric space For an $n$-element metric space $X=\{x_1,\dots,x_n\}$ with metric
$d$ we introduce an array containing $\frac{n(n-1)}2$ numbers
$d(x_i,x_j)$, $i<j$. We assume that all distances are at least
$1$. The number of relevant scales for the metric space $X$
is defined as the number of intervals $[2^{i-1},2^{i})$
$i=1,2,\dots$ containing some elements of the array $d(x_i,x_j)$,
$i<j$. Let $RS(n)$ be the maximal number of relevant scales which
an $n$-element metric space may have.
Problems: (1) What is the rate of growth of $RS(n)$? (2) What
about exact evaluation of $RS(n)$ for all $n\in \mathbb{N}$?
Comments: (1) In Exercise 3.37 of my book "Metric Embeddings" I
suggest readers to prove the following two statements as exercises
(hints are given):
(i) $RS(n)\ge 2n-3$.
(ii) $RS(n)\le \frac{n(n-1)}2-(n-4)$.
So for nontrivially large $n$ the number $RS(n)$ is strictly
between $n$ and $\frac{n(n-1)}2$.
(2) One can replace $2$ by another number in the definition of
$RS(n)$, and it may change the answer.
 A: First here is an $O(n\log n)$ upper bound. Make a complete graph whose vertex set is $X$ and the weights on its edges are the distances, $d(x_i,x_j)$. Consider a minimum weight spanning tree $T$ in this graph. Denote the weights/distances of the edges of the tree by $d_1,\ldots, d_{n-1}$. We claim that for every edgedistance $d$ of the graph we have an $i$ for which $d_i\le d\le (n-1)d_i$, which proves the upper bound.
For an edge $uv$ with weight $d$, take the path in $T$ between $u$ and $v$. Let the longest edge of this path be $d_i$. We have $d_i\le d$, otherwise replacing the edge of weight $d_i$ with $uv$ would give a spanning tree with a smaller weight. On the other hand, from the triangle inequality we have that $d$ is less than the sum of the weights of the edges of the path, which is at most $(n-1)d_i$.
Now, we can further improve this to $O(n)$ with a more detailed analysis, checking how the weights of the tree are distributed. This follows by applying the following lemma instead of the estimate of the previous paragraph.
Lemma. Denote by $RS'(n)$ the maximum possible number of intervals of the form $[2^k,2^{k-1})$ that contain at least one number of the form $x+\sum_{i\in I} d_i$ where $0\le x\le d_1$ and $\emptyset\ne I\subset \{1,\ldots,n\} $ and the maximum is taken over all $0\le d_1\le \ldots\le d_{n}$ numbers. Then $RS'(n)\le 2n$.
Proof. The proof is by induction. If for every $j$ we have $d_j\le d_1+\sum_{i<j} d_i$, then we have $d_j\le 2^{j-1} d_1$ and thus $\sum_j d_j\le (2^{n}-1)d_1$, so all the numbers of the form $x+\sum_{i\in I} d_i$ are between $d_1$ and $2^nd_1$, in this case $RS'(n)\le n+1$. On the other hand, if there is a $j$ for which $d_j> d_1+\sum_{i<j} d_i$, then divide the $d_i$ numbers into two groups, depending on whether their index is less than $j$ or not. For those whose index is less than $j$, by induction we have that they give at most $2j$ intervals. For those whose index is at least $j$, notice that we can again apply induction, since now $x$ ``grows'' to $d_j$ from $d_1$, so these give at most $2(n-j)$ intervals. In total we get at most $2n$ intervals, we are done.
Note that because we have changed $n-1$ to $n$ to make the lemma nicer, we got a $2n-2$ upper bound for the original problem, and if we remove the ``x'' from the lemma, then by induction we get an upper bound of $2n-3$, which matches the lower bound of (i).
