Monday, May 01, 2006

High dimensions are tricky

I was bothered by a claim that seems to be trivial to argue. But I was stuck for a couple of days. It states:

If a d-dimensional convex body P does not contain a (k+1)-dimensional ball of radius r, then P can be enclosed in a k-dimensional flat with width (k+1)r.

This sounds intutively trivial. However when I try to write down the proof it is not easy. This also motivates me to read things about high dimensional space and polytopes etc. The thing is that high dimensional geometry is hard to visualize, and sometimes the results are counter-intuitive.

I have later been trying to use an old theorem called John's theorem to prove it. Though the theorem is very nice to know. My trials ended up in vain so far.

Anyway, here is the nice John's theorem (proved in 1938 or sth).

A convex body P in d-dimension contains an ellipsoid E such that E \subseteq P \subseteq dE, where dE is a factor d blowup of E. If P is symmetric, then P is enclosed in \sqrt{d}E. Both bounds are tight in the worst case. Examples are simplex and cube.

No comments: