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.



The number of relevant scales for a finite metric space
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).


