## Return to Answer

2 added 616 characters in body

Well, here's a start. Suppose we have n points, and let k = n(n-1)/2. Thus there are k distances we have to pick. Let's take all of our distances to lie in the set {k+1, k+2, ..., 2k}, so that we don't have to worry about the triangle inequality. Now, the collection of open balls depends on how many times each distance is repeated. However, translating the set by an integer doesn't affect the collection of open balls. That is, if D is the multiset of distances, and CD is the collection of open balls induced by D, then CD+1 = CD, where by D+1 I mean add 1 to each element of D. This is true because of what javier says: to find the collection of open balls at a point, we just start at that point and increase the radius of the ball by 1 at each step, writing down each open ball we get and stopping when we get the whole set.

The upshot of this is that if k+1 is not the smallest element of D, we can translate D such that k+1 is the smallest element, without affecting the open ball structure. In fact, I'm pretty sure a stronger statement is true: if D has a gap, we can slide down the upper part of D to close that gap without affecting the open ball structure. That is, if r and s are elements of D such that r < s-1 and there are no elements of D strictly between r and s, then we can translate s and everything above it down by 1. If D has r distinct values, then by doing such translations, we can get D to be a multiset with values in {k+1, ..., k+r}.

Thus, if we have a particular open ball structure C on n points, we can find a multiset D with the above properties such that C = CD. So the number of such multisets provides an upper bound on the number of (unlabeled) metric spaces. I have no idea how good this bound is, but let's calculate it.

Let fr(k) = # of multisets with k elements taking values from {k+1, ..., k+r}, and taking each value at least once. So we essentially have k-r free slots in D, and r different values, so the number of such multisets is the binomial coefficient B((k-r)-(r-1), r-1) = B(k-1, r-1). Then the total number of multisets is f1(k) + ... + fk(k) = 2^{k-1}.

Now, that looks pretty huge: 2^{(n+1)(n-2)/2}. On the other hand, there are 2^{2^n} collections of subsets of X, and even when you account for the fact that you have to include all the singletons and the whole set, 2^{2^n - (n+1)} is hardly an improvement. For n=3, our new upper bound is 4, and the true value is 3, since the multisets {3, 4, 5} and {3, 3, 4} give the same open ball structure.

Can anyone expand on this?

Edit: On further reflection, there are multiple different open ball structures induced by a multiset. For example, if n=4 and D = {7, 7, 7, 7, 8, 8}, then we get different structures if we assign the two distances of 8 to the same vertex or to different vertices. So it seems we should look at ordered k-tuples instead of multisets, which makes our upper bound much larger (bigger than k factorial). So maybe this is less useful than I thought. But at least after thinking about it like this, I might have simplified the problem enough that I can write a program to calculate the next few values of the sequence.

1

Well, here's a start. Suppose we have n points, and let k = n(n-1)/2. Thus there are k distances we have to pick. Let's take all of our distances to lie in the set {k+1, k+2, ..., 2k}, so that we don't have to worry about the triangle inequality. Now, the collection of open balls depends on how many times each distance is repeated. However, translating the set by an integer doesn't affect the collection of open balls. That is, if D is the multiset of distances, and CD is the collection of open balls induced by D, then CD+1 = CD, where by D+1 I mean add 1 to each element of D. This is true because of what javier says: to find the collection of open balls at a point, we just start at that point and increase the radius of the ball by 1 at each step, writing down each open ball we get and stopping when we get the whole set.

The upshot of this is that if k+1 is not the smallest element of D, we can translate D such that k+1 is the smallest element, without affecting the open ball structure. In fact, I'm pretty sure a stronger statement is true: if D has a gap, we can slide down the upper part of D to close that gap without affecting the open ball structure. That is, if r and s are elements of D such that r < s-1 and there are no elements of D strictly between r and s, then we can translate s and everything above it down by 1. If D has r distinct values, then by doing such translations, we can get D to be a multiset with values in {k+1, ..., k+r}.

Thus, if we have a particular open ball structure C on n points, we can find a multiset D with the above properties such that C = CD. So the number of such multisets provides an upper bound on the number of (unlabeled) metric spaces. I have no idea how good this bound is, but let's calculate it.

Let fr(k) = # of multisets with k elements taking values from {k+1, ..., k+r}, and taking each value at least once. So we essentially have k-r free slots in D, and r different values, so the number of such multisets is the binomial coefficient B((k-r)-(r-1), r-1) = B(k-1, r-1). Then the total number of multisets is f1(k) + ... + fk(k) = 2^{k-1}.

Now, that looks pretty huge: 2^{(n+1)(n-2)/2}. On the other hand, there are 2^{2^n} collections of subsets of X, and even when you account for the fact that you have to include all the singletons and the whole set, 2^{2^n - (n+1)} is hardly an improvement. For n=3, our new upper bound is 4, and the true value is 3, since the multisets {3, 4, 5} and {3, 3, 4} give the same open ball structure.

Can anyone expand on this?