Nested powers and their retracts

It is common to consider vector spaces {{\mathbb R}}, {{\mathbb R}^2}, {{\mathbb R}^3}, … as a nested sequence with inclusion maps

\displaystyle    \iota \colon {\mathbb R}^n\rightarrow{\mathbb R}^{n+1}, \quad (x_1, \dots, x_n) \mapsto (x_1,\dots,x_n,0)

To define these inclusion maps we did not need any structure of {{\mathbb R}} other than the existence of a distinguished element {0\in{\mathbb R}}. The same could be done for any pointed set, i.e., a set {X} with a distinguished element {x_0\in X}. Each inclusion {\iota\colon X^n\rightarrow X^{n+1}} is split, because we can retract {X^{n+1}} onto {X^n} by deleting the last coordinate. This works in the category of sets, and also in every other category I can think of.

However, many naturally occurring manifolds (more generally, metric spaces) do not have any distinguished elements: spheres, hyperbolic spaces, tori, … indeed, such spaces are called homogeneous because all their points look alike (the group of isometries is transitive). The line did not have a distinguished element until we gave it the group structure of {{\mathbb R}}, and to introduce such a structure we had to make an arbitrary choice of a point to be called {0}.

Is there a way to have a nested sequence of powers of a space {X} without distinguished points? Yes, but it will not be the Cartesian product {X\times \dots \times X}. Instead, we consider the symmetric product {X^{(n)}} whose elements are nonempty subsets of {X} with cardinality at most {n}. This product (really a power, but the name “symmetric product” is more common) is naturally related to {X^n}:

  • There is a canonical surjection {q\colon X^{n}\rightarrow X^{(n)}} which sends {(x_1,\dots,x_n)} to {\{x_1,\dots,x_n\}}.
  • If {A_1,\dots,A_n} are disjoint subsets of {X}, then the restriction of {q} to {A_1\times \dots \times A_n} is injective.

The symmetric products are nested by virtue of the obvious inclusion {\iota \colon X^{(n)}\rightarrow X^{(n+1)}}: each set stays as it is, nothing needs to be added.

If {X} is a topological or metric space, we can give the same structure to {X^{(n)}} by declaring {q} to be a quotient map. In the metric case there is a more direct and explicit definition of a metric on {X^{(n)}}: the Hausdorff metric. First, introduce {\delta}-neighborhood of a set {A}: this is the set of all points at distance at most {\delta} from {A}, denoted {A(\delta)}. Given two sets {A,B\in X^{(n)}}, define

\displaystyle d_H(A,B)=\inf\{\delta\colon A\subset B(\delta) \text{ and } B\subset A(\delta) \}

To better relate this metric to {X^n}, we use the maximum metric {d_\infty} on {X^n}: the distance between {(x_j),(y_j)\in X^n} is {d_\infty= \max_j d_X(x_j,y_j)}. It is clear that the forgetful surjection {q} is {1}-Lipschitz. Unfortunately, it is not a submetry: for example, the points {\{1,2,5\}} and {\{1,4,5\}} are at unit distance in {{\mathbb R}^{(3)}} but any pair of their preimages under {q} has distance at least {2} in {{\mathbb R}^3}. Oh well.

Recalling that the inclusions of Cartesian products are split, we ask if the same holds for symmetric products: is there always a retraction {r\colon X^{(n)}\rightarrow X^{(m)}} when {n>m}? A retraction is a Lipschitz map (in topological setting, continuous) which agrees with the identity on {X^{(m)}}.

For example, is the circle {\mathbb T} a retract of {\mathbb T^{(2)}}? The first idea may be to appeal to non-existence of continuous single-valued square root, but then we recall that a retraction need not send {\{a,b\}} into either {\{a\}} or {\{b\}}. The following argument works, though: supposing that {r\colon \mathbb{T}^{(2)}\rightarrow\mathbb{T}} is a retraction, for each fixed {t\in [0,\pi]} we define the map {f_t\colon \mathbb{T}\rightarrow\mathbb{T}} so that {f_t(e^{i \theta})} is the sole element of {r(\{e^{i\theta}, e^{i\theta+it}\})}. Then {f_0} is the identity, {f_{\pi}} is an even map (hence of even degree), but they are homotopic via {\{f_t\}}, which is a contradiction.

In the positive direction, {{\mathbb R}^{(m)}} is a Lipschitz retract of {{\mathbb R}^{(n)}} whenever {m<n}. The idea is simple: given a set of cardinality {n}, label its elements as {a_1<\dots<a_n} and define {a_j'=a_j-(j-1)\delta} where {\delta=\min \{ a_{j+1}-a_j \colon j=1,\dots,n-1\}}. This can even be promoted to a deformation retraction via {a_j^t=a_j-t(j-1)\delta}, {0\le t\le 1}. Geometrically, this map deflates all gaps in the set at the same rate, until the smallest one collapses.

Reducing the gaps
Reducing the gaps

For a slightly more general version, see Lemma 4.2 here.

I got stuck on the case when {X} is {\mathbb{P}}, the Euclidean plane {{\mathbb R}^2}. It is easy to retract {\mathbb{P}^{(2)}} onto {\mathbb{P}^{(1)}}: just send each two-point set into its center of mass (midpoint). I also have a Lipschitz retraction of {\mathbb{P}^{(3)}} onto {\mathbb{P}^{(2)}}, but it is not as simple. Given a {3}-point set {\{a,b,c\}} in the plane, let {o} be the center of the circle inscribed in the triangle with vertices {abc}; if the points are collinear, let {o} be the one that lies between two others. Equivalently, {o} is the center of mass of the vertices where each vertex is given weight equal to the length of opposite side. One can check that the map {\{a,b,c\}\mapsto o} is Lipschitz. By relabeling vertices, we may assume that {|a-o|\ge |b-o|\ge |c-o|}. Let {a'} be the point on the segment {ao} at distance {|b-o|} from {a}. The map {\{a,b,c\}\mapsto \{a',o\}} is the desired retraction. Again, we can make it into a deformation retraction in an obvious way.

From a 3-point set to a 2-point set
From a 3-point set to a 2-point set

In both cases, the idea is to pretend that the original set lives on a tree, and pull all of its elements toward some vertex of the tree. The incenter of triangle enters the game once one recalls the tripod representation of a {3}-point set. However, with sets of greater cardinality the non-hyperbolicity of {\mathbb{P}} becomes apparent, making it hard to pretend that we work with a tree. I do not know if there is a Lipschitz retract from {\mathbb{P}^{(n+1)}} to {\mathbb{P}^{(n)}} for every {n}.

3 thoughts on “Nested powers and their retracts”

  1. Sorry I didn’t understand the non-hyperbolicity part.. You can form a tight span of the n-point space P^n, and pull every point toward the “center” right?

  2. Define a point, so that the sum of the pairwise distances from all points in the set to this point is minimized. Then pull every point simultaneously toward that point until the first 2 of them arrive.
    Intuitively the path should be stable. Consider points on the convex hull of the set of points, and leave out the interior points for now. In this case that optimal point is the center of mass inside the hull. Adding one interior point at a time should only move that optimal point inside the convex hull, and the rate of movement depends on the distance between that point to the optimal point.

  3. Let’s see if the following works. Build a hierarchical clustering tree on the given n points with euclidean distance. Imagine hypothetical edges exist among nodes with the same parents, which makes the tree a composition of several triangles. Now shrink the edges of the triangles with a uniform speed, until one of the edges completely disappear. For nodes that contain more than one points, we shrink the edges by moving the center of mass of the points, which is done by moving points in this node uniformly in the same direction.

    As an illustration, consider the example you gave. \{(0,0) (1,0) (0, \epsilon) (1, \epsilon)\} becomes:
    layer 1: \{(0,0) (0, \epsilon)\},  \{(1,0) (1, \epsilon)\}
    layer 2: left: \{(0,0)\}, \{(0, \epsilon)\} right: \{(1,0)\}, \{(1, \epsilon)\}
    the center of the left node of layer 1 is \{ (0,\frac{\epsilon}{2})\}, right \{ (1,\frac{\epsilon}{2})\}. Let them move together with unit speed.
    Meanwhile, the left and right branches themselves move together with unit speed.
    The net effect is, after t unit of time, the points become
    \{(t,t)\}, \{(t, \epsilon-t)\}, \{(1-t,t)\}, \{(1-t, \epsilon-t)\}
    So they will meet at t=\frac{\epsilon}{2}
    \{(\frac{\epsilon}{2},\frac{\epsilon}{2})\}, \{(1-\frac{\epsilon}{2}, \frac{\epsilon}{2})\}.
    Now consider the other configuration \{(0,0) (1,0) (0, \epsilon) (0, -\epsilon)\} :
    layer 1: \{(0,0) (0, \epsilon) (0, -\epsilon)\},  \{(1,0)\}
    layer 2: left: \{(0,0) (0, \epsilon)\}, \{(0, -\epsilon)\} right: \{(1,0)\}
    layer 3: left: \{(0,0)\} \{(0, \epsilon)\} As always, everything moves with unit speed. After t unit of time, points become latex \{(t,0)\}, \{(t, \epsilon-2t)\}, \{(t,t-\epsilon)\}, \{(1-t, 0)\}$
    They also meet at t=\frac{\epsilon}{2}
    \{(\frac{\epsilon}{2},0)\}, \{(\frac{\epsilon}{2}, -\frac{\epsilon}{2})\}, \{(1-\frac{\epsilon}{2}, 0)\}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s