The cross polytope

There are five regular solids in three dimensions:

• tetrahedron
• octahedron (pictured above)
• hexahedron (cube)
• dodecahedron
• icosahedron.

I give a proof here that these are the only five.

The first three of these regular solids generalize to all dimensions, and these generalizations are the only regular solids in dimensions 5 and higher. (There are six regular solids in dimension 4.)

I've mentioned generalizations of the cube, the hypercube, lately. I suppose you could call the generalization of a octahedron a "hyperoctahedron" by analogy with the hypercube, though I've never heard anybody use that term. Instead, the most common name is cross polytope.

This post will focus on the cross polytope. In particular, we're going to look at the relative volume of a ball inside a cross polytope.

The cross polytope in n dimensions is the convex hull of all n-dimensional vectors that are 1 in one coordinate and 0 in all the rest. It is the "plus or minus" part that gives the cross polyhedron its name, i.e. the vertices are in pairs across the origin.

In analysis, the cross polytope is the unit ball in a₁ ("little ell one"), the set of points (x₁, x₁, ", x_n) such that

|x₁| + |x₂| + " + |x_n| = 1.

The a₁ norm, and hence the a₁ ball, comes up frequently in compressed sensing and in sparse regression.

In recent blog posts we've looked at how the relative volume in a ball inscribed in a hypercube drops quickly as dimension increases. What about the cross polytope? The relative volume of a ball inscribed in a cross polytope decreases rapidly with dimension as well. But does it decreases faster or slower than the relative volume of a ball inscribed in a hypercube? To answer this, we need to compute

Let's gather what we need to evaluate this. We need the volume of a ball of radius r in n dimensions, and as mentioned before this is

A ball sitting inside an n-dimensional unit cross polytope will have radius 1/an. This is because if n positive numbers sum to 1, the sum of their squares is minimized by making them all equal, and the point (1/n, 1/n, ", 1/n) has norm 1/a n. A ball inside a unit hypercube will have radius 1/2.

The cross polytope has volume 2ⁿ / n! and the hypercube has volume 1.

Putting this all together, the relative volume of a ball in a cross polytope divided by the relative volume of a ball inside a hypercube is

which fortunately reduces to just

But how do we compare n! and n^n/2? That's a job for Stirling's approximation. It tells us that for large n, the ratio is approximately

and so the ratio diverges for large n, i.e. the ball in the cross polytope takes up increasingly more relative volume.

Looking back at just the relative volume of the ball inside the cross polytope, and applying Stirling's approximation again, we see that the relative volume of the ball inside the cross polytope is approximately

and so the relative volume decreases geometrically as n increases, decreasing much slower than the relative volume of a ball in a hypercube.