When does a metric space have "infinite metric dimension"? (Definition of metric dimension)

Question

Definition 1 A subset $B$ of a metric space $(M,d)$ is called a metric basis for $M$ if and only if $$[\forall b \in B,\,d(x,b)=d(y,b)] \implies x = y \,.$$

Definition 2 A metric space $(M,d)$ has "metric dimension" $n \in \mathbb{N}$ if there exists a minimal (in terms of cardinality) metric basis consisting of $n+1$ points. If $M$ does not have metric dimension $n$ for any $n \in \mathbb{N}$, then it has "infinite metric dimension".

Question: What general characteristics or properties of a metric space would automatically force it to have infinite metric dimension? (Perhaps any infinite set with the discrete metric?)

At the very least, are there any straightforward, but perhaps non-representative, examples of metric spaces which obviously must have infinite metric dimension?

(Perhaps unsurprisingly, Euclidean spaces have been shown to have finite metric dimension.)

Note: The definition 1 comes from the paper A Metric Basis Characterization of Euclidean Space by Grattan P. Murphy, Pacific Journal of Mathematics Vol.60, No. 2, 1975. Definition 2 is based on my (possibly faulty) understanding/interpretation of the following results in that paper.

Answer 1

I'll try to make a couple of remarks. it'll be easier for me to write only a bit at a time.

The metric category of metric spaces and metric maps (i.e. Lipschitz with constant $1$, i.e. never stretching) has a certain rigidity to it so that the idea of a metric base seems attractive. However, I feel that the metric dimension makes sense only for a somewhat limited class of, rather than for all, metric spaces. (Possibly, more than one of several competing definitions can make sense).

Consider (see the Question above):

Property G   A subset $B$ of a metric space $(M,d)$ is called a metric g-set for $M$ if and only if $$ \forall_{b \in B}\ d(x,b)=d(y,b)\ \ \implies\ \ x = y $$

Every such set $B$ was called a metric basis above. Let $B$ be one, and let $\ B\subseteq C\subseteq M.\ $ Then $$ \forall_{c \in C}\ d(x,c)=d(y,c)\ \ \implies\ \ x = y $$

Thus, $\ C\ $ has the metric g-set property too. We see that declaring Property G as a definition of metric basis goes against the spirit of basis in general. Instead, Property G corresponds to the general notion of a generating set.

 

It took quite a long time to arrive at the topological definition of a curve and of the topological dimension (from Cantor's curves in $\ \mathbb R^2,\ $ to Brouwers-Urysohn-Menger, then to the algebraic topological dimensions, etc.).

It took also considerable time to arrive at a general definition of basis which ultimately led to matroids.

In this thread, the topic is rather something like the metric variations of the independent sets and of a basis. Perhaps one should eye matroids for a comparison. These days things go much faster than in the past but the process of obtaining one or more of such sound metric notions may still take some tries and patience.

Thus let's examine the property of a basis, and more generally, of independent sets for matroids: let $X$ be a matroid; then

1. if $\ A\subseteq X\ $ is an independent set, and $\ b\in X,\ $ then there exists $\ a\in A\ $ such that $\ (A\setminus\{a\})\cup\{b\}\ $ is independent;

2. if $\ A\subseteq X\ $ is an independent set (resp. basis), and $\ b\in X\ $ depends on $\ A\ $ (resp. $\ b\in X\ $ is arbitrary), then there exists $\ a\in A\ $ such that $\ (A\setminus\{a\})\cup\{b\}\ $ generates the same set as $\ A\ $ (resp. $\ (A\setminus\{a\})\cup\{b\}\ $ is a basis).

Now let's look at some metric spaces.

EXAMPLE 1   Let $\ X:=\{0\ 1\ 2\ 3\},\ $ and let $\ d\ $ be a metric (thus, symmetric, etc) in $\ X,\ $ such that: \begin{eqnarray} d(0\ n) &:=& 2-\frac 1n&\qquad \mbox{for }\ \ n=1\ 2\ 3\\ d(k\ n) &:=& 2&\qquad \mbox{for every}\ \ 0<k<n\le3 \end{eqnarray} We see that there is a $1$-element basis $\ \{0\}\ $ in $\ (X\ d)\ $ in the sense of Question while there is no other $1$-element basis. However, in the spirit of matroids (see the above properties 1. and 2.), every $1$-element subset of $X$ should be a basis. Well, this is not so.

ALSO:   Every $2$-element set $\ X\subset\{0\ 1\ 2\}\ $ is a minimal G-set (basis). These three $2$-element sets and $\ \{0\}\ $ are the only minimal G-sets; thus, there are four of them altogether.

 

Turning to continuous spaces will not help:

EXAMPLE 2   Let $\ X:=[1;\infty)\ $ be a closed half-line, and let $\ d\ $ be a metric (thus, symmetric, etc) in $\ X,\ $ such that: \begin{eqnarray} d(1\ x) &:=& 2-\frac 1x&\qquad \mbox{for every}\ \ x > 1\\ d(x\ y) &:=& 2&\qquad \mbox{for every}\ \ 1<x<y \end{eqnarray} We see that there is a $1$-element basis $\ \{1\}\ $ in $\ (X\ d)\ $ in the sense of Question while there is no other $1$-element basis. Again, in the spirit of matroids, every $1$-element subset of $X$ should be a basis.

Thus, continuity didn't help.

ALSO:   In addition to $\ \{0\},\ $ the only other minimal G-sets are sets $\ X\subset[0;\infty)\ $ such that $\ |[0;\infty)\setminus X|=1$.

 

CONCLUSION If (a big if) we had to continue with the definition of basis from Question then we would have to restrict the class of the metric spaces under consideration. The first candidate which comes to mind would be the class of transitive space (i.e. such that for every two points there is an isometry of the space onto itself, which sends one of the points onto the other one).

(I might continue later on)

Answer 2

Well, if $M$ has a metric basis $\{b_1, \ldots, b_{n+1}\}$ then the map $$x \mapsto (d(x,b_1), \ldots, d(x,b_{n+1}))$$ is a continuous injection from $M$ into $\mathbb{R}^{n+1}$. So, for example, no infinite dimensional Banach space $E$ could have this property for any $n \in \mathbb{N}$: letting $K$ be the closed unit ball of an $n+2$ dimensional subspace of $E$, we restrict to a continuous injection from $K$ into $\mathbb{R}^{n+1}$, which since $K$ is compact must be a homeomorphism, and I think topologists know that an $n+2$ dimensional ball cannot be homeomorphic to a subset of $\mathbb{R}^{n+1}$.

Answer 3

Consider $(\mathbf{Z}\times[0,1])/(\mathbf{Z}\times\{0\})$, infinitely many spokes attached at a single point. Given a finite basis, the only points uniquely characterized by distances from it are the points on the same spokes as the basis. So this space is infinite-dimensional.

Answer 4

Having infinite metric dimension is not bi-Lipschitz-invariant. On the real line, consider the two metrics $$ d(x,y)=\min(|x-y|,1)\quad\text{and}\\ \delta(x,y)=\arctan(|x-y|). $$ The two metrics both give the usual topology, they are bi-Lipschitz to each other, but $\dim(\mathbb R,d)=\infty$ (as observed by Benoît Kloeckner) and $\dim(\mathbb R,\delta)=1$ (the $\delta$-distances from any two points uniquely determine the point).

Usually one might argue that if two metric spaces are bi-Lipschitz, they are essentially the same. However, this does not guarantee that the metric dimensions coincide. I don't know what would characterize infinite metric dimension, but it has to be "finer than Lipschitz properties" of the metric. As Benoît Kloeckner's new answer indicates, it does not help if we restrict ourselves to length metrics.

On a tangential end note, consider the metric $d_\epsilon(x,y)=\min(|x-y|,\epsilon)$ on $S^1$ for any $\epsilon>0$. Here the absolute value can be the metric inherited from $\mathbb R^2$ or $\mathbb R/2\pi\mathbb Z$, it doesn't really matter. All these are bi-Lipschitz to each other, but the dimension for $d_\epsilon$ is roughly $2\pi/\epsilon$. You can adjust the metric dimension of $S^1$ to be any positive integer with bi-Lipschitz changes.

Answer 5

As yet another example, there is a metric on the real line which induces the usual topology but is metrically infinite-dimensional.

Simply take the distance function $\rho(x,y) = \min(|x-y|,1)$. For any finite subset of $\mathbb{R}$, all points at Euclidean distance more than $1$ from the subset have the same distance vector $(1,1,\dots,1)$.

Answer 6

Let me add two other examples showing that diverse spaces have infinite metric dimension.

First, take any infinite ultrametric space, i.e. such that $d(x,z)\le \min(d(x,y),d(y,z))$ for all $x,y,z$. Knowing the distances to a finite set of points does not give more information than knowing the smallest one of these distances, if this distance is small enough (for concreteness, one can consider the case $X=\{0,1\}^\mathbb{N}$ with the distance $d(x, y) = 2^{i(x,y)}$ where if $x=(x_k), y=(y_k)$ we set $i(x,y)=\min\{k : x_k\neq y_k\}$; then if $S$ is finite subset, leting $\varepsilon$ be the smallest distance between two points of $S$, all points in the ball of radius $\varepsilon$ around any element of $S$ share the same distances to all points of $S$).

Second, consider a regular tree of valence $k\ge 3$, with all edges of length $1$ say. For any point outside the convex hull of a finite subset $S$, the distances to elements of $S$ are entirely determined by the connected component of the complement and the distance to $S$, and distances to $S$ cannot determine the point. Again the space has infinite metric dimension while it has topological and Hausdorff dimension $1$. Note that this example is a length space, but we need infinitely many branching point to ensure infinite-dimensionality.

Answer 7

Ok, yet another example prompted by previous ones and comments.

Consider $\ell_\infty^2$, the plane with the $\ell_\infty$ metric. Given any finite set $S$, all points on a given vertical line far enough at the right of $S$ have the same distances to all elements of $S$, since only their largest component will matter in the distance. So $\ell_\infty^2$ has infinite metric dimension.

Answer 8

As Benoit mentioned in one of his answers, ultrametric spaces are a class of metric spaces that can be analyzed, and there is a paper recently put on the arxiv, https://arxiv.org/abs/2003.10239, that carefully investigates when ultrametric spaces have finite metric dimension.

It also cites a considerable amount of literature where this concept appears in graphs with their distance metric.