# The Universe of Discourse

Mon, 20 Feb 2023

(Previously)

A couple of days ago I discussed a Math Stack Exchange question where OP, observing that a square has four sides, a cube has six faces, and !!6=\binom 42!!, asked if there was some way to understand this as a real structural property and not a coincidence. They did not put it that way, but I think that is partly what they were after:

I was thinking maybe there exists some bijective map from any 2 given edges of a square to faces of a cube but I'm not really getting anywhere.

I provided a different approach, and OP declared themselves satisfied, but I kept thinking about it. My approach did provide a combinatorial description of the cube that related its various parts to the square's corresponding parts. But it didn't produce the requested map from pairs of objects (the !!\binom 42!! part) to the six faces.

Looking around for something that a cube has four of, I considered the four body diagonals. A cube does have six interior bisecting planes, and they do correspond naturally with the pairs of body diagonals. But there's no natural way to assign each of the six faces a distinct pair of body diagonals; the mapping isn't one-to-one but two-to-two. So that seemed like a dead end.

But then I had a happy thought. A cube has eight vertices, which, if we think of them as points in 3-space, have coordinates !!\langle 0,0,0\rangle, \langle 0,0,1\rangle, \dots, \langle 1,1,1\rangle!!. The vertices fall naturally two groups of four, according to whether the sum of their coordinates is even or odd.

In this picture the even vertices are solid red, and the odd vertices are hollow. (Or maybe it's the other way around; it doesn't matter.)

The set of the four even vertices, red in the picture above, are a geometrically natural subset to focus on. They form a regular tetrahedron, for example, and no two share an edge.

And, crucially for this question, every face of the cube contains exactly two of the four even vertices, and every pair of even vertices resides in a single common face. This is the !!6=\binom 42!! correspondence we were looking for. Except that the !!4!! here isn't anything related to the square; instead the !!4!! is actually !!\frac122^3!!, half the total number of vertices.

In this diagram I've connected every pair of even vertices with a different-colored line. There are six colored lines, and each one is a diagonal of one of the six faces of the cube.

Six faces, six pairs of even vertices. Perfect!

This works just fine for lower dimensions. In two dimensions there are !!\frac122^2 = 2!! even vertices (namely !!\langle0,0\rangle!! and !!\langle1,1\rangle!!) so exactly one pair of even vertices, and this corresponds to the one “face” of a square. In one dimension there is only one even vertex, so there are no pairs, and no faces either.

But in extending this upward to four dimensions there is a complication. There are !!16!! vertices total, and !!8!! of these are even. There are !!\binom82 = 28!! pairs of even vertices, but only !!24!! faces, so you know something must have gone wrong. But what?

Let's focus on one vertex in particular, say !!\langle 0,0,0,0\rangle!!. This vertex shares a face with only six of the seven other even vertices. But its relationship with the last even vertex, !!\langle 1,1,1,1\rangle!!, is special — that vertex is all the way on the opposite corner, too far from !!\langle 0,0,0,0\rangle!! to share a face with it. Nothing like that happened in the three-dimensional case, where the vertex opposite an even vertex was an odd one.

The faces of the 4-cube correspond to pairs of even vertices, except that there are four pairs of opposite even vertices that are too far apart to share a face, and instead of $$\binom 82$$ faces there are only $$\binom 82 - 4 = 24;$$ that's the !!\binom82!! pairs of even vertices, minus the four pairs that are opposite.

We can fix this. Another way to look at it is that two even vertices are on the same face of an !!n!!-cube if they differ in exactly two coordinates. The even vertices in the 3-cube are:

$$\langle0,0,0\rangle \\ \langle0,1,1\rangle \\ \langle1,0,1\rangle \\ \langle1,1,0\rangle$$

and notice that any two differ in exactly two of the three positions. In the !!4!!-cube this was usually the case, but then we had some antipodal pairs like !!\langle 0,0,0,0\rangle!! and !!\langle 1,1,1,1\rangle!! that differed in four coordinate positions instead of the required two.

Let !!E!! be an even vertex in an !!n!!-cube. We will change two of its coordinates, to obtain another even vertex, and call other vertex !!E'!!. The point !!E!! has !!n!! coordinates, and there are !!\binom n2!! ways to choose the two coordinate positions to switch to obtain !!E'!!. We have !!\frac122^n!! choices for !!E!!, then !!\binom n2!! choices of which pair of coordinates to switch to get !!E'!!, and then !!E!! and !!E'!! together determine a single face of the !!n!!-cube. But that double-counts the faces, since pair !!\{ E, E'\}!! determines the same face as !!\{ E', E\}!!. So to count the faces we need to divide the final answer by !!2!!. Counting by this method tells us that the number of faces in an !!n!!-cube is is:

$$\frac122^n\cdot \binom n2 \cdot \frac12$$

where the !!\frac122^n!! counts the number of ways to choose an even vertex !!E!!, the !!\binom n2!! counts the number of ways to choose an even vertex !!E'!! that shares a face with !!E!!, and the extra !!\frac12!! adjusts for the double-counting in the orderof !!E!! and !!E'!!. We can simplify this to $$2^{n-2}\binom n2.$$

When !!n=3!! we get $$2^{3-2}\binom 32 = 2\cdot 3 = 6$$

and it is correct for all !!n!!, since !!\binom n2 = 0!! when !!n<2!!:

$$\begin{array}{r|rrrrr} n& 0&1&2&3&4&5 \\ \text{faces} = 2^{n-2}\binom n2 & 0 & 0 & 1 & 6 & 24 & 80 \\ \end{array}$$

That's not quite the !!\binom{2^{n-1}}2!! or the !!\left({{(n-1)2^{n-2}}\atop 2}\right)!! we were looking for, but it at least does produce a bijective map between faces and pairs of something.