# When does a metric space have “infinite metric dimension”? (Definition of metric dimension)

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.

• @Eric: no, the point is that the failure has to be in the whole (otherwise, the definition would make no sense at all). For the definition to make sense, it has to be read as $$[\forall b \in B,\,d(x,b)=d(y,b)] \implies x = y \,.$$ – Martin Argerami Jul 15 '17 at 19:44
• @MartinArgerami : Ah. Yes. Thanks for being patient with my slowness today. – Eric Towers Jul 15 '17 at 20:22
• Don't worry. I've been on the "other side" many times ;) – Martin Argerami Jul 15 '17 at 20:30
• The concept is quite interesting, but the question a bit vague. If you have some precise goal in mind, could you say more about the kind of properties you would be interested in? Are there some classes of space you want to consider in particular? – Benoît Kloeckner Jul 16 '17 at 12:28
• Concerning compact Riemannian manifolds, they are of finite metric dimension (take the $0$-skeleton of a fine enough triangulation). I would suspect that their metric dimension is always equal to their topological dimension, and would try to show that a Baire-generic subset of $n+1$ points does the job. – Benoît Kloeckner Jul 17 '17 at 8:16

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 metric dimension makes sense only for a somewhat limited class of, rather then 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)

• I definitely agree with what you've written so far. I took the definition from Professor Murphy's paper, assuming that they might have some justification for the choice of terminology that was omitted from the paper. (But maybe there isn't? I don't know.) – Chill2Macht Jul 19 '17 at 5:25
• Also, for a vector space, one has to show that all basises have the same number of elements, before the notion of dimension is well-defined. But I don't actually know whether each (minimal-cardinality) metric basis is actually guaranteed to have the same number of elements (or more generally cardinality), and if it isn't, then metric dimension wouldn't be well-defined. But I don't know how to verify it either way. Is this what you were referring to when you mentioned logical problems in the definitions? – Chill2Macht Jul 22 '17 at 18:23
• I'm sorry about the late reply -- I didn't even notice that you had edited your answer to add more content -- I really like how you bring in matroid theory to this (since I had been working with/thinking about matroids for a completely unrelated reason). Anyway, do I understand your examples correctly? Is there a 3-element "basis" for the first example ($\{1, 2, 3 \}$) and a 2-element "basis" for the second example ($\{ x_1, x_2 \}$ for any $x_1, x_2 > 1$)? Thus "metric dimension" isn't well-defined since not all metric generating sets of minimal cardinality have the same cardinality? – Chill2Macht Aug 2 '17 at 23:39
• I have added "ALSO" x 2 (one per Example). It's not hard to add more sophisticated examples. However, I feel that it's time to concentrate on better definitions, I guess. – Wlod AA Aug 3 '17 at 5:31
• It seems there is some confusion between minimality with respect to inclusion, and with respect to cardinality. – Benoît Kloeckner Aug 3 '17 at 20:04

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}$.

• The injection is not only continuous, it is Lipschitz. Matt F's answers shows that having a Lipschitz injection into $\mathbb{R}^{n+1}$ is not a sufficient condition to be finite-dimensional. It begs the question whether this injection has additional properties that could characterize finite-dimensionality. – Benoît Kloeckner Jul 16 '17 at 12:34
• @BenoîtKloeckner I don't think Lipschitz properties are going to be enough here. I gave an example in my answer to show that something finer is needed. – Joonas Ilmavirta Jul 16 '17 at 14:40

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.

• ... showing that there are "infinite-dimensional" (in this sense) spaces which continuously inject into $\mathbb{R}^2$. – Nik Weaver Jul 15 '17 at 17:39

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.

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)$.

• Note that the definition of metric dimension in the question can obviously be extended to infinite cardinals. Matt F's answer and mine provide examples of $\aleph_0$-dimensional spaces, while the metric dimension of an infinite-dimensional Banach space probably depend on itsseparability. – Benoît Kloeckner Jul 16 '17 at 12:38
• Note that this space is not convex -- if you take points p and q which are far apart, there is no r with d(p,r)+d(r,q)=d(p,q). So it's a good example for this question, but is outside the paper's focus on convex spaces. – Matt F. Jul 16 '17 at 17:11

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.

• The second example tells us that a space can be bi-Lipschitz embeddable in the Euclidean plane but have infinite metric dimension (take a tree which looks like an infinite comb), further confirming that the metric dimension is very sensitive to Lipschitz modifications. – Benoît Kloeckner Jul 18 '17 at 7:48

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.