# Convex hull in CAT(0)

Let $X$ be complete $\mathop{CAT}(0)$-space and $K\subset X$ be a compact subset. Is it true that convex hull of $K$ is compact?

• Convex hull of $K$ = intersection of all closed convex sets containing $K$.

• The space is NOT assumed to be locally compact

• This is an old folklore problem. In print it was first(?) time mentioned by Kopecká's and Reich's in Nonexpansive retracts in Banach spaces, published in 2008. (Thanks to Greg Kuperberg for this ref.)

• I believe there is a counterexample, maybe even in case of negatively pinched curvature (in the sense of Alexandrov).

• One answer is accepted, BUT it only provides a reference that the question is really open.

-
Maybe it's worth pointing out that it seems difficult even if $K$ contains only 3 points. –  Richard Kent Nov 24 '09 at 2:47
Yes, I think that is pretty much the same question. (If one wants to construct a counterexample then my question is easier.) –  Anton Petrunin Nov 24 '09 at 17:50
Anton, do you have a proof when X is a Hilbert space? –  Igor Belegradek Dec 9 '09 at 20:30
Sure --- it is nearly trivial –  Anton Petrunin Dec 10 '09 at 2:56
Would you care to explain how the proof works for the Hilbert space case? There are lots of compact subsets there. –  Igor Belegradek Dec 10 '09 at 3:49

It is on my mind that a related region in $X$ constructed from $K$ is always compact, I think. Any measure $\mu$ on $K$ has a center of gravity $c$, defined as the minimum $x$ of the average value of $d(x,y)^2$ with $y$ sampled from $\mu$. The set of Borel measures on $K$ is compact by the Banach-Alaoglu theorem in the weak-* topology, and my intuition is that the position of the center of gravity is continuous with respect to this topology. (If this intuition is wrong, then the rest of this post is not all that interesting.) This is not the same as the convex hull, but it seems interesting as a possible approximation.

Any point in the strict convex hull of $K$ (not its closure) is reached by a sequence of binary operations on pairs of points from a finite list. The initial list of points is in $K$, and then certain pairs $x$ and $y$ to make new points $z$. By definition, $z$ is at distance $p$ along the way from $x$ to $y$. This description induces a measure on the initial set of points. For instance suppose that we start with $x_1, x_2, x_3, x_4 \in K$, then take the point $y_1$ that is $p_1$ along the geodesic from $x_1$ to $x_2$ and the point $y_2$ that is $p_2$ along the geodesic from $x_3$ to $x_4$. Then finally the point $z$ is $q$ along the way from $y_1$ to $y_2$. The induced measure on the original list of points is then $qp_1[x_1]+q(1-p_1)[x_2]+(1-q)p_2[x_3]+(1-q)(1-p_2)[x_4]$. This measure has a center of gravity $c$, and I am wondering how far away $c$ can be from $z$. If $X$ happens to be a vector space, then $c=z$, but in general they are not equal.

There is a mutual generalization of points in the convex hull and centers of gravity. Starting with a base list of points $x_1,\ldots,x_n \in K$, there is a $k$-ary operation with weights that replaces $k$ of the points with their center of gravity. If these operations are repeated in the pattern of a weighted tree $T$, then the computation produces a point $z$ which could be in the convex hull (if $T$ is binary), or could be a center of gravity (if $T$ is a shrub), or could be various things in between. Now suppose that $T$ is a complicated tree. We can flatten it to make it a shrub $T_1$ that yields a point $z_1$. Then in various ways we can unflatten $T_1$, step by step, to approach $T = T_n$. Assuming the first paragraph, the points that can be reached by trees of bounded depth are a compact set. I do not know enough about $\text{CAT}(0)$ spaces to draw any conclusions, but it seems possible that the points $z_k$ approach the final point $z = z_n$ quickly enough to establish compactness. Or if this does not happen, then that could be evidence against compactness of the convex hull.

(To be clear, this is just a proposal and not a solution.)

Here another way to state the proposal without any direct use of center of mass, although it is still suggested by the fact that the set of centers of mass is compact.

For any $0 \le p \le 1$, there is a binary operation $x \heartsuit_p y$ on points in $X$. By defintion, $x \heartsuit_p y$ is the point $z$ such that $d(x,z) = pd(x,y)$ and $d(y,z) = (1-p)d(x,y)$. Let $x_1,\ldots,x_n$ be a list of points in $K$, possibly with repetitions. Then every word $w$ in the points of $K$ written in this notation defines a point $z \in X$. We can also compute the same word in the vertices of a Euclidean simplex $\Delta_{n-1}$. We thus obtain a continuous map $f_T:\Delta_{n-1} \to X$ that only depends on the tree structure $T$ of $w$. How far away are these maps from each other for two different trees? (There are $(2n-3)!!$ distinct trees.) If you have enough control over the distance, then the closed convex hull of $K$ is compact. More precisely, the hope is to find a compactification of the space of words such that the evaluation map extends continuously.

For example, if $n=3$, we can define three tree centers of three points $x,y,z$, namely $x \heartsuit_{1/3} (y \heartsuit_{1/2} z)$ and its cyclic permutations. How far apart can they be in a $\text{CAT}(0)$ space? For instance, in a tree, which is one kind of opposite to a Euclidean space, the tree centers of a unit equilateral triangle are at most 1/3 away from each other.

In the comments to my other post on possible counterexamples, Anton also asks for references. I found the paper Nonexpansive retracts in Banach spaces, by Kopecká and Reich. They say,

This proof of Theorem 2.10 works equally well in any Hadamard space in which the closed convex hull of a finite number of points is compact. It follows then that the Plateau problem can be solved in such spaces. Unfortunately, it is not known which Hadamard spaces have this property. However, it is shown in [We, Theorem 1.6] that Plateau’s problem can be solved in every Hadamard space (regardless of whether it has this property or not)."

Their theorem 2.10 is an interesting, stronger property that they show follows from Anton's property: Every compact set $K$ is contained in a compact, 1-Lipschitz retract of the space $X$. Clearly such a retract is also convex, so the convex hull of $K$ inside is compact. Moreover, the subject of their Theorem 2.10 is exactly my example 2, so that example does not work. Moreover, Anton's property already has a name in the literature, what they call CNEP, and they reduce to the case that $K$ is finite. Finally, as of 2006, these authors describe it as an open problem.

-
I doubt that it works, but it is interesting. If I understand right given set $K$ you want to consider a sequence of sets $K_n$ where $K_{n+1}$ is the set of centers of mass of probability measures with support in $K_n$. Indeed all $K_n$ are compact. Let $\epsilon_n$ be the Hausdorff distance from $K_n$ to $K_{n+1}$. Then it is sufficient to show that $\sum\epsilon_n<\infty$. BUT so far I do not see any way to estimate $\epsilon_n$, I can not even show that Unknown control sequence $\epsilon_n\to0$... (I might also miss something in your answer) –  Anton Petrunin Dec 6 '09 at 20:55
BTW, there is a nice way to think about convex hull in metric spaces described in Lang--Schroeder paper on Kirszbraun theorem. In particular, they consider measure you described (well, only in case when K is finite, but it does not matter). –  Anton Petrunin Dec 6 '09 at 20:56
At first glance, your remark is a very nice summary of the point that I was trying to make. Of course, proposals are never entirely rigorous and I am not sure either whether there is anything more in my picture with trees than in your set version. –  Greg Kuperberg Dec 6 '09 at 21:06
(1) It is easy to see that $\epsilon_n$ is non-increasing. (2) For $\mathop{CAT}(-1)$, we get even more $\epsilon_{n+1}\le\epsilon_n-C\cdot\epsilon_n^2$. (3) You can also define $K_{n+1}$ as above or as union of all geodesics with ends in $K_n$. --- Maybe one can make someting out of this... –  Anton Petrunin Dec 9 '09 at 17:01
I imagine you realized this, but here goes anyway. You have shown that for $\text{CAT}(-1)$ spaces, you do not have all that much wiggle room for the sum of $\epsilon_n$ to diverge. Your upper bound diverges harmonically. –  Greg Kuperberg Dec 10 '09 at 17:46

It follows quickly from the definition that closed balls are convex.

[Proof: Let p,q be in the ball of radius R about o, and let x lie on the geodesic from p to q. Then $d(o,x)\leq d(\bar{o},\bar{x})$, where the second quantity is in the comparison triangle in Euclidean space. But now $d(\bar{o},\bar{x})\leq \max(d(\bar{o},\bar{p}),d(\bar{o},\bar{q}))\leq R$ as required.]

Therefore, if you assume that your CAT(0) space is proper (as one often does), meaning that closed balls are compact, the property you want follows.

Perhaps this isn't the case you're interested in. I'm not sure what happens in the non-proper (improper?) case.

-
I seem to be getting wildly varying ratings for this answer! Perhaps I should comment that, when I wrote it, Anton had not specifically stated that he isn't interested in the proper case. –  HJRW Nov 23 '09 at 22:50

It is a little absurd to offer a one-week bounty for an open problem, but it can be taken as a request for ideas. So here are some possible constructions of $\text{CAT}(0)$ spaces that are not locally compact from which one might learn something.

1. Let $X$ be a $\text{CAT}(0)$ space and let $A$ be a compact topological space with a finite Borel measure $\mu$. Then the space of continuous functions $C(A,X)$ has a distance defined by $$d(f,g)^2 = \int_A d(f(t),g(t))^2 d\mu.$$ In general $C(A,X)$ is not complete, but we can take its completion. I suppose that its completion can be called $L^2(A,X)$, and I suppose that it is $\text{CAT}(0)$.

2. If $H$ is a complex Hilbert space, then there is an indefinite inner product on $H' = \mathbb{C} \oplus H$ given by $$\langle \alpha \oplus v, \beta \oplus w \rangle = \langle \alpha,\beta \rangle - \langle v,w \rangle.$$ We can consider the vectors in $H'$ with positive self inner product and with positive first component, divided by complex phase. This is a Hilbert space version of $\mathbb{C}H^\infty$, with a natural Fubini-Study metric. I suppose that it is just the metric completion of the direct limit of $\mathbb{C}H^n$.

3. A $C^*$-algebra $A$ has both a general linear group $\text{GL}(A)$ of invertible operators and a unitary group $\text{U}(A)$ of unitary operators. You can look at the coset space $\text{GL}(A)/\text{U}(A)$, which is an infinite-dimensional analogue of the $\text{CAT}(0)$ homogeneous space $\text{GL}(n,\mathbb{C})/\text{U}(n)$. Suppose also that $A$ has a finite faithful trace $\tau$. Then I think that $\tau$ gives you a Riemannian metric on $\text{GL}(A)/\text{U}(A)$. Again, you have to take a completion because this includes special cases of the first construction. I suppose, although in this case I really don't understand things well, that the metric is $\text{CAT}(0)$.

In any of these cases you could ask whether the closed convex hull of a compact set is compact. I thought at first that the answer might already be no in the construction 1. The hope was that you could make a convex hull that includes $L^2(A,R)$ for some small region $R \subset X$. If that happens, then it is not compact. But I am not sure that it does happen.

These analytic constructions are really just fancy ways to take infinite limits of finite-dimensional manifolds, as Anton says in his proposed answer. I suppose that that is where the intuition comes from that there might be a counterexample. So to be concrete, let's take $\text{GL}(n,\mathbb{C})/\text{U}(n)$, the homogeneous space of positive $n \times n$ Hermitian matrices. (Or the real version would be fine too.) As Anton says, you can take three points $x, y, z$ and look at the inradius of their convex hull. You might as well let $x$ be the identity matrix, and then in interesting cases $y$ and $z$ are two other matrices that badly fail to commute. It isn't difficult to find lots of points in the convex hull with a computer, but at the moment I don't have much intuition.

Even if the inradius is small, if there is a disk inside with radius bounded below and increasing dimension, that could be good enough.

-
I just wanted to attract attension to this quesion (I do not see what else one can do with points). –  Anton Petrunin Dec 8 '09 at 4:37
I agree that it's a great question. I think that the open-problem tag may be the best that you can do. Bounty points make more sense for a question that you can consider answered in one week. For instance you could ask what is known about an open problem, and get a good answer within a week. (Maybe the one-week limit is bad, but at the moment they can't change it.) –  Greg Kuperberg Dec 8 '09 at 5:02
Also, Anton, what the authors of the software think you are supposed to usually "do" with points is keep them, as a rating of your "reputation". But of course that's just a game. –  Greg Kuperberg Dec 8 '09 at 18:33
BTW, I would be more than happy if someone would give me a reference to something with this question :) –  Anton Petrunin Dec 8 '09 at 23:42
If any such reference exists, it is not easy to find. Possibly the right conclusion is that you have a new definition of a compactness property of a unique geodesic space. –  Greg Kuperberg Dec 9 '09 at 0:47

On possible counterexample.

Let $M$ be a Riemannian manifold and $x,y,z\in M$. One can measure the maximal radus of ball inside of convex hull of $\{x,y,z\}$, let it be $r(M,x,y,z)$.

Is it possible to find a a sequence $M_n$ of negatively curved $n$-dimensional manifolds with points $x_n,y_n,z_n\in M_n$ such that $|x_ny_n|=|y_nz_n|=|z_nx_n|=1$ and $r(M_n,x_n,y_n,z_n)$ stays bounded away from zero as $n\to\infty$?

-

Here is a quote from the paper "Schauder Fixed Point Theorem in Spaces with Global Nonpositive Curvature" by Niculescu and Rovenţa, http://www.hindawi.com/journals/fpta/2009/906727.html

[In a CAT(0) space] "the convex hull of a finite subset is not necessarily closed, but we can mention two important cases when this happens. The first one is that of Hilbert spaces. In fact, in any locally convex Hausdorff space, if are compact convex subsets, then the convex hull of their union is compact too. See the monograph of Day [9]."

Two conclusions: 1) for Hilbert spaces the result holds. 2) they claim the convex hull of a finite set is not necessarily closed, hence not necessarily compact.

-
Anton asks whether the closed convex hull is compact, not whether the convex hull is closed. –  Greg Kuperberg Dec 9 '09 at 22:13
In a Hausdorff space if a subset is not closed, it is not compact. –  Igor Belegradek Dec 9 '09 at 22:34
Well, look in def of convex hull above –  Anton Petrunin Dec 9 '09 at 23:07
Oh, you are considering closed convex hull. Sorry, I misunderstood. –  Igor Belegradek Dec 9 '09 at 23:16

Ok here is one example, why the convex hull (not the "convex closed hull") of a compact set needn't be compact. Hence this does not contribute to the original question, but it is quite close, so i'll leave it here (if sb. wants me to delete this, I could also do this).

Consider the space $X=[0;1]^\mathbb{N}=Map(\mathbb{N},[0;1])$ equipped with the metric $d(f,g):=\sqrt{\sum_{n\in \mathbb{N}} (\frac{|f(n)-g(n)|}{2^n})^2}$. I would think of this space as $\prod_{i\in\mathbb{N}}[0;2^{-i}]$. I would like to claim the following things:

1) The topology induced by this metric is the product topology.

2) Convex combinations are taken pointwise. i.e. the geodesic from $f$ to $g$ is $t\mapsto(1-t)f+tg$ (not parametrized by arc length).

3) $X$ is a locally compact and complete CAT(0)-space.

4) The subset $K=Map(\mathbb{N},\{ 0;1\})$ is compact (Tychonoff). Especially the product topology agrees with the subspace topology.

5) Its convex Hull is given by the set of all maps $f:\mathbb{N}\rightarrow [0;1]$, such that Im$(f)$ is finite. (Clearly this set is closed under convex combinations, so it remains to show, that every element in this set can be written as a convex combination of elements of $K$).

6) Hence its convex hull is not closed and cannot be compact (as $X$ is Hausdorff).

-
Everything is correct BUT, "my convex hull" is closed by definition. –  Anton Petrunin Feb 18 '10 at 18:42
ah tnx. I corrected my post. –  HenrikRüping Feb 18 '10 at 23:12