24
$\begingroup$

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.

$\endgroup$
13
  • 2
    $\begingroup$ @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 \,.$$ $\endgroup$ Jul 15, 2017 at 19:44
  • 1
    $\begingroup$ @MartinArgerami : Ah. Yes. Thanks for being patient with my slowness today. $\endgroup$ Jul 15, 2017 at 20:22
  • 1
    $\begingroup$ Don't worry. I've been on the "other side" many times ;) $\endgroup$ Jul 15, 2017 at 20:30
  • 1
    $\begingroup$ 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? $\endgroup$ Jul 16, 2017 at 12:28
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 17, 2017 at 8:16

8 Answers 8

5
$\begingroup$

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)

$\endgroup$
9
  • 1
    $\begingroup$ 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.) $\endgroup$ Jul 19, 2017 at 5:25
  • 1
    $\begingroup$ 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? $\endgroup$ Jul 22, 2017 at 18:23
  • 1
    $\begingroup$ 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? $\endgroup$ Aug 2, 2017 at 23:39
  • 2
    $\begingroup$ 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. $\endgroup$
    – Wlod AA
    Aug 3, 2017 at 5:31
  • 2
    $\begingroup$ It seems there is some confusion between minimality with respect to inclusion, and with respect to cardinality. $\endgroup$ Aug 3, 2017 at 20:04
23
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Jul 16, 2017 at 12:34
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 16, 2017 at 14:40
16
$\begingroup$

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.

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

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 16, 2017 at 12:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – user44143
    Jul 16, 2017 at 17:11
5
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 18, 2017 at 7:48
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.