9

I've found a very nice problem and I don't know how to go about solving it.

Let $(E, || \cdot ||)$ be an inner product space, $x_1, ..., x_n \in E$.

Prove that if for $i \neq j$ we have $||x_i - x_j|| \ge 2$, then the points $x_1, ..., x_n$ cannot be placed inside a ball of radius less than $\sqrt{\frac{2(n-1)}{n}}$.

$B(x_0, r) = \{y \in E \ \ | \ \ ||x_0-y||<r\}$

The smallest ball containig two points such that $||x_1 - x_2|| \ge 2$ would have radius $=1$ and $\sqrt{\frac{2 \cdot 1}{2}}=1$ So it works for 2 points.

In order to place three such points inside a ball we need to construct an equilateral triangle, and then the radius $= \frac{2 \sqrt{3}}{3}=\sqrt{\frac{2 \cdot 2}{3}}$. So it works for three points.

However in case of four points we don't get a square but a rhombus (mistake - it's a tetrahedron). I was hoping I could use induction, but I can't figure out how to estimate the radius of the ball.

Martin
  • 113
  • 1
    It appears $\dim E$ also plays a part, as the unit ball of $l^1(\mathbb{N})$ contains infinitely many points at distance $2$ from each other (namely, the standard basis), and there exists $n$ such that $1<\sqrt{\frac{2(n-1)}{n}}$. – Jonathan Y. Oct 19 '13 at 20:57
  • Yes, I also thought of that while writing my question last night. And I'm very sorry for the mistake, but $E$ is supposed to be inner product space. I'll correct that right away. – Martin Oct 20 '13 at 05:32

1 Answers1

3

I think there is a mistake in the example. For $n=4$ the shape is not a Rhombus but a tetrahedron. Imagine $4$ points with equal distance with each other. The resulting geometric shape must be a tetrahedron. Similarly the $n=k$ case should give us a $k$-dimensional simplex.

The question now is to deduce the ball which can contain a $k$-dimensional simplex with side length $2$. The calculation seems to be already done at here, which I am not going to replicate. This should be enough to solve the problem.

Community
  • 1
Bombyx mori
  • 19,638
  • 6
  • 52
  • 112
  • 1
    A reference for Jung's theorem: Marcel Berger, Geometry I (theorem 11.5.8). – Seirios Oct 20 '13 at 08:06
  • Thank you very much. However, there are some things I do not quite understand in that proof. Firstly, what point does the author mean here : "The remaining point of $S$ is collinear with $c_S$ and $c_R$. " (the line above Pythagorean triple). Secondly, could you give me a hint on how to adapt this to general inner product spaces? Jung's theorem works for compact subsets of $\mathbb{R}^n$, doesn't it? – Martin Oct 20 '13 at 09:09
  • 1
    @Martin: For a general metric space, if a subset is closed and bounded, then it is compact. So the simplex must be compact. You can always give the metric by $d(x,y)=|x-y|$. I think you can try to work out the case when $k=2$ the simplex is a triangle, and see how it generates from the case $k=1$ when the simplex is a line segment. The general argument is very similar. – Bombyx mori Oct 20 '13 at 17:50
  • Ok, thank you. I think that's what I wanted to know. One more question. In my problem we are dealing with an inner product space, whereas in the linked question they are considering $\mathbb{R}^n$, which is quite specific. Could you help me apply that proof to my situation? – Martin Oct 20 '13 at 18:55
  • 1
    @Martin: There is really little difference because all the theorems are the same. For example the equality $r_{k}^{2}=r_{k-1}^{2}+h_{k}^{2}$ still holds. But I think you need the assumption that $E$ is finite dimensional and choose an orthonormal basis to ease the computation. Otherwise for $l^{2}$ this is obviously not true. – Bombyx mori Oct 20 '13 at 19:10
  • I understand why we need $E$ to be finite dimensional. However I still have trouble proving that the linked question can be adapted here. I've found an article about generalization of Jung's theorem in Hilbert spaces http://link.springer.com/article/10.1007%2Fs11006-006-0131-6#page-1 . Do you think it's useful here? – Martin Oct 21 '13 at 06:35
  • 1
    I think you can give a basis to $E$ and since you have the inner product $|x|=\sqrt{\langle x,x\rangle}$ available, all the arguments one had in $\mathbb{R}^{n}$ can be carried to $E$, because as an $\mathbb{R}$ vector space endowed with an inner product properly normalized it is isomorphic to $\mathbb{R}^{n}$ as Hilbert spaces. I am too poor to read that article, but I suspect the author found some ways to generalize it to infinite dimensional spaces, which is not useful at here. – Bombyx mori Oct 21 '13 at 06:44
  • Ok, I'll think about that. Thank you very much. – Martin Oct 21 '13 at 06:51