Basic High-dimensional Geometry

I’m not informed about too many of the applications, but apparently high-dimensional geometry is a relevant topic these days. I think it’s pretty fun to think about though, so I’ll talk about some of the basic properties of d-dimensional spheres and some of their counter-intuitive properties.

We’re going to say that a unit hypersphere is the set of points in \mathbb{R}^d, say (x_1, x_2, \cdots, x_d) where \sum_{i=1}^{d}{x_i^2} = 1. This sounds pretty obvious but some strange things happen when the dimension increases, so we’ll be a little careful.

Visualizing a hypersphere is unfortunately beyond my ability, so we’ll have to show a lot of “geometric” results with algebra. We’ll start with the surface area of the unit hypersphere in d dimensions. First we’ll talk about a relevant trick to evaluate a common integral; suppose we wanted to evaluate the following

\begin{array}{ccc}  \displaystyle\int_{-\infty}^{\infty}{e^{-x^2} dx}\\  \end{array}

One way to go about this is to consider the square of the integral and then convert to polar. It’s kind of a strange idea since usually we’re trying to take apart separable integrals, but here it works well.

\begin{array}{lcl}  \int_{-\infty}^{\infty}{e^{-x^2} dx} \int_{-\infty}^{\infty}{e^{-y^2} dy} &=& \int_{-\infty}^{\infty}{\int_{\infty}^{\infty}{e^{-(x^2+y^2)}dx}dy} \\  &=& \int_{0}^{2\pi}{\int_{0}^{\infty}{re^{-r^2} dr d\theta}} \\  &=& \frac{1}{2} \int_{0}^{2\pi}{\int_{0}^{\infty}{e^{-u} du d\theta}} \\  &=& \pi  \end{array}

I skipped a few steps at the end there, but the rest of the math is clear I think. So our original integral is equal to \sqrt{\pi} (positive since e^{-x^2} is always positive).

Now the trick to determining the surface area of a hypersphere is to evaluate a similar integral in two ways, with cartesian and polar coordinates. Evaluating in cartesian coordinates goes like this:

\begin{array}{lcl}  \int_{-\infty}^{\infty}{} \cdots \int_{-\infty}^{\infty}{e^{-(x_1^2 + \cdots + x_d^2)} dx_d \cdots dx_1} &=& (\int_{-\infty}^{\infty}{e^{-x^2}dx})^d \\  &=& \pi^{\tfrac{d}{2}}  \end{array}

Evaluating in polar coordinates is a little bit harder, especially if you’ve forgotten how to apply change of coordinates like me. The important thing to see is that the differential after the change is just r^{d-1}d\Omega dr where d\Omega is the infinitesimal piece of surface area of the solid angle on the unit sphere. I basically try to visualize in three dimensions. Failing at that, I’ll try two dimensions. Failing at that … well, you get the idea.

Anyway, after the change of coordinates we get the following:

\begin{array}{lcl}  \int_{-\infty}^{\infty}{} \cdots \int_{-\infty}^{\infty}{e^{-(x_1^2 + \cdots + x_d^2)} dx_d \cdots dx_1} &=& \int_{S^d}{d\Omega}\int_{0}^{\infty}{r^{d-1}e^{-r^2}dr} \\  &=& A_d \int_{0}^{\infty}{r^{d-1}e^{-r^2}dr} \\  &=& A_d \int_{0}^{\infty}{u^{(d-1)/2}e^{-u} (\tfrac{du}{2\sqrt{u}})} \\  &=& \frac{1}{2} A_d \int_{0}^{\infty}{u^{d/2} e^{-u} du}  \end{array}

where A_d is the surface area of the unit sphere. You might recognize the integral as the gamma function, more specifically \Gamma(d/2) (or in my case, have it pointed out by Bishop in [2]). Either way, we can finally equate the two to see that the surface area of the unit sphere in d dimensions is

\begin{array}{ccc}  A_d = \frac{2 \pi^{d/2}}{\Gamma(d/2)}  \end{array}

Knowing this, finding the volume is easy since V_d = \int_{0}^{1}{A_d r^{d-1} dr}, so V_d = \tfrac{A_d}{d}. Some of the calculus might be sketchy here, but we can at least see that the expressions check out for d=2 and d=3. So the volume of the unit sphere is

\begin{array}{lcl}  V_d = \frac{2 \pi^{d/2}}{(d) (\Gamma(d/2))}  \end{array}

Interestingly enough, this approaches zero as d approaches infinity.

As nice as these formulas are, they don’t actually tell us that much about what the hypersphere “looks” like. There are a couple of properties shown by Hopcroft and Kannan in [1], but the easiest to see is that most of the volume is near the very edge of the sphere. This is clear when we fix \epsilon > 0 and consider the ratio of the volume of a sphere with radius 1-\epsilon to the volume of the unit sphere: \tfrac{(1-\epsilon)^d V_d}{V_d} = (1-\epsilon)^d, which goes to zero as d gets large. Less obvious is that most of the volume is concentrated near the equator, as is the surface area.

We’ll finish up by leaving the realm of all practical application (at least to my knowledge). Consider the Euler Characteristic \chi of a cube. For those who don’t remember (or read about it in The Number Devil and are suspicious of any names you’ve heard there), the Euler Characteristic is (classically) defined as \chi = V-E+F which represent the vertices, edges, and faces of a convex polyhedron. For any such convex polyhedron this always comes out to 2, and the cube is no exception, since 8-12+6=2. How does this extend to higher dimensions?

We’ll keep considering cubes, more specifically the set of points \vec{x} \in \mathbb{R}^n such that 0 \leq x_i \leq 1 for all i. How many vertices does this cube have? Considered coordinate-wise each could be 0 or 1 independently, so there are 2^n vertices. How many edges are there? Well, an edge connects two vertices with exactly one coordinate different (Hamming distance one is another way to think about it, of course). A given vertex therefore has n adjacent vertices and so has n edges. Summing over the entire cube we get \tfrac{n2^n}{2} = n2^{n-1} where we have divided by two because we counted each edge twice, once from each end. Finally, a face can be defined by its vertices which are diagonally opposite. Algebraically this means we can generate all the faces by finding all vertices that differ from a a given vertex in exactly two places and summing over the entire cube. This gives us \tfrac{\binom{n}{2}2^n}{2^2} = \binom{n}{2}2^{n-2}, since each face was generated four times.

Applying Euler’s formula to this does not give us anything interesting in my opinion, but stopping at “faces” in this case seems arbitrary for n-dimensional cubes. We stop at “faces” (or two dimensional cubes) in this particular case because we are working in three dimensions. In the n-dimensional case, wouldn’t it make sense to continue to (n-1)-dimensional objects?

In general we are looking to ask how many i-dimensional cubes does an n-dimensional cube contain on its boundaries. It’s not hard to see from the 3-dimensional reasoning that this is actually just \binom{n}{i}2^{n-i}. If we put these in an alternating series (as Euler does), we’ll get \sum_{i=0}^{n}{(-1)^i\binom{n}{i}2^{n-i}}. Looking at this carefully we recognize that this is just the binomial expansion of (2-1)^n, or 1. In other words, applying a slightly generalized Euler’s formula to an n-dimensional cube will yield 1, regardless of dimension. I’m unsure whether to include the last term since Euler does not in the 3-dimensional case (also it’s always 1, since we are asking “how many n-dimensional cubes does this n-dimensional cube contain”). Leaving that out gives us 1+(-1)^{n-1}, which I suppose is still a nice result but not quite as pretty.

It would be interesting but probably much more difficult to look into a more general case of this. Perhaps regular convex polyhedra wouldn’t be so bad since we probably would be able to exploit similar counting techniques, but in the most general case I have no idea how to go about this. I might try to look into the literature at some point, since I’m sure someone has done it.

If you find any errors or typos, please let me know! I’ll even thank you so that this blog’s vast readership will know of your contribution.

Sources:
[1] Foundations of Data Science by Hopcroft and Kannan.
A draft can be found here: http://www.cs.cornell.edu/jeh/book112013.pdf
Contains a more extensive discussion of hyperspheres.
[2] Neutral Networks for Pattern Recognition by Bishop.
Outlines the proof of the surface area and volume of a hypersphere in Exercises 1.1-1.4.

Advertisements