By Clive Newstead on 15th December 2009
We live in a three-spatial-dimensional world. We can move forward and backward, upward and downward, and left and right. That is, it's possible to find three vectors in our vector space each of which is perpendicular to the other two... or, in more basic terms, I can arrange three sticks so that every stick makes a right-angle with every other stick. If we were living in a two-spatial-dimensional world, however (say if we were drawn on pieces of paper), we could go up and down, or left and right, but we couldn't come out of the page or go into it.
Imagine now that we could go left and right, up and down, forward and backward, and to and from another direction, in such a way that this other direction is at a right-angle to the other three. This would require a fourth spatial dimension. Note that I use the word "spatial" to distinguish it from any other kind of dimension, such as temporal (arguably, time is our 4th dimension, you see). Crazy physics aside, for all practical intents and purposes, this isn't possible... but that doesn't stop us from making a big deal out of it, does it?
A hypercube is essentially a generalisation of a cube, or a square, or a line, or a dot. To show how we construct it, it's best to go back to basics to see how we construct lines, squares, cubes and so on, from dots and suchlike. The following image is of a zero-dimensional cube, which we know as a dot (or a vertex).
It is not possible to move in any direction, so we're stuck on the dot forever. If we're allowed one dimension, though, then we can go to and from the given direction. As such, we can pull the dot in this direction in order to make a line joining the old dot (red) with the new dot (yellow), as shown below.
Now we can go to and fro in one direction. But we want to move in another direction now; we want a second dimension. So, if we pull the whole line through the new dimension (in the direction of the blue lines, perpendicular to the black ones), we achieve a square.
You can guess what comes next. We're bored of being able to move around the face of the square, and we want to be able to go through something. Pulling the whole square through another dimension in a direction perpendicular to all the back lines gives us, you guessed it, a cube!
But what happens now? This is the exciting bit. Imagine if we could pull a cube through another dimension; what would it look like then? Now, since our eyes, brains and suchlike are only equipped to deal with three dimensions and fewer, we can't actually envisage this. We can, however, see what a projection onto two dimensions would look like... in the same way that the picture of the cube above is a two-dimensional projection rather than actually being 3D (technology isn't quite that advanced yet). Anyway, don't let the following picture fool you, the 'outer' cube isn't any larger than the 'inner' cube. At any given vertex, the blue lines are, again, perpendicular to each of the black lines coming out of that vertex, and each face that you see is the same size as each other face. Here goes nothing!
This interesting creature of a shape is called a tesseract. The blue lines mark where the cube was pulled through a perpendicular direction in a 4th dimension. You'll notice an 'inner' cube (with red vertices) and an 'outer' cube (yellow), but also six strange gaps between each face of the inner cube and the corresponding face of the outer cube -- these gaps are indeed cubes themselves, but they appear distorted thanks to our lack of ability to project four dimensions onto two. As such, there are eight cubes that make up this tesseract.
Now, we can continue like this, but it soon gets tedious, not to mention rapidly more and more difficult to make any sense on a computer screen. This is where algebra comes in! Now, first, we need to pick out some patterns. We can see fairly easily that each hypercube is made up of a certain number of hypercubes of a lesser dimension than that hypercube. That is, you can count the number of lines (1-D hypercubes) in a cube (a 3-D hypercube), and the number of faces (squares, 2-D hypercubes) in a cube or tesseract, and so on. What we're interested in here is the number of $r$-dimensional hypercubes that make up an $n$-dimensional hypercube.
Some results are fairly obvious. Firstly, it is obvious that there is just one n-dimensional hypercube in an n-dimensional hypercube, and that there are no $r$-dimensional hypercubes in an $n$-dimensional hypercube if $r > n$. Also, notice that each time we go up a dimension, we 'copy' our current hypercube into the new dimension, and then join up the dots. This means that each time the number of vertices doubles. Given that in 0 dimensions the number of vertices is 1, we conclude that an $n$-dimensional hypercube has $2^n$ vertices.
I'll pause here to introduce some notation. I'll use $H(r,n)$ to denote the number of r-dimensional hypercubes in an n-dimensional hypercube. The results we have obtained so far are as follows: \[H(n,n) = 1\] \[H(r,n) = 0 \text{ if } r \ge n\] \[H(0,n) = 2^n\] What about lines? Well, we always duplicate the number of lines in an $(n-1)$-cube, and then join each (disjoint) pair of vertices in an $(n-1)$-cube, telling us that $H(1,n) = 2H(1,n-1) + H(0,n-1)$. This makes sense. When we go from a square to a cube, we double the number of lines in a square ($H(1,2)$), and then pull each vertex in a square ($H(0,2)$) through the third dimension, creating a new line for each one. This is a fact that generalises. Whenever we go from $(n-1)$ to $n$ dimensions, we duplicate the number of $r$-dimensional hypercubes and then connect them with a $(r-1)$-dimensional hypercube for each duplicated $r$-dimensional hypercube. For example, when we go from a square to a cube, we double the number of faces by superposing two squares, and then connect the two squares with lines at each of the four corners, creating four new faces, a total of 2 + 4 = 6 faces. Explicitly, this rule is: \[H(r,n) = 2H(r,n-1) + H(r-1,n-1)\] We have now found a recursive equation for the number of r-dimensional hypercubes that constitute an n-dimensional hypercube! But is this enough? What if we had, say, $r = 3 \times 10^{526}$ and $n = 2 \times 10^{839}$? For such large numbers, it would take even a ridiculously fast computer years and years to compute, however it would take a lot less time if we had a formula solely in terms of $r$ and $n$, rather than $H$.
It is worth noting that our definition $H(r,n) = 2H(r,n-1) + H(r-1,n-1)$ is very similar to our definition of binomial coefficients; that is,
\[ \binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1} \text{ for } r > 0 \text{ and } \binom{n}{0}=1 \]
It is therefore reasonable to expect that our resulting formula for $H(r,n) = 2H(r,n-1) + H(r-1,n-1)$ will involve binomial coefficients. Well, it turns out it does. I won't go through the tedious algebraic proof here, because that really isn't the scope of this essay; instead I will just state the result:
\[ H(r,n) = 2^{n-r} \binom{n}{r} \] where \[ \binom{n}{r} = \frac{n!}{r!(n-r)!} \]
For whatever reason pleases you, you can now say with confidence that there are, for example, 14,415,739,690,621,176,119,296 (about 14 and a half sextillion) fifty-five-dimensional hypercubes contained inside a seventy-three-dimensional hypercube!
If you have read this far into the article, chances are you're actually interested in this multidimensional malarky. If so, I certainly recommend that you try and go through the proof yourself (which is partly why I didn't put it all here). Discovery of things like this, where we can discover truths and properties about things which can't possibly exist in our world, is part of what makes mathematics beautiful. I hope you enjoyed reading this article!