The Universe of Disco

Uniform descriptions of subspaces of the n-cube

This must be well-known, but I don't remember seeing it before. Consider a !!3!!-cube. It has !!8!! vertices, which we can name !!000, 001, 010, \ldots, 111!! in the obvious and natural way:

Two vertices share an edge exactly when they agree in two of the three components. For example, !!001!! and !!011!! have a common edge. We can call this common edge !!0X1!!, where the !!X!! means “don't care”.

The other edges can be named similarly:

$$ \begin{array}{} 00X & 0X0 & X00 \\ 01X & 0X1 & X01 \\ 10X & 1X0 & X10 \\ 11X & 1X1 & X11 \end{array} $$

A vertex !!abc!! is contained in three of the !!12!! edges, namely !!Xbc, aXc,!! and !!abX!!. For example, here's vertex !!001!!, which is incident to edges !!X01, 0X1, !! and !!00X!!.

Each edge contains two vertices, obtained by replacing its single !!X!! with either !!0!! or !!1!!. For example, in the picture above, edge !!00X!! is incident to vertices !!000!! and !!001!!.

We can label the faces similarly. Each face has a label with two !!X!!es:

$$ \begin{array}{} 0XX & 1XX \\ X0X & X0X \\ XX0 & XX1 \\ \end{array} $$

The front face in the diagram contains vertices !!000, 001, 100, !! and !!101!! and is labeled with !!X0X!!:

• Each vertex !!abc!! is contained in three of the !!6!! faces, namely !!XXc, XbX,!! and !!aXX!!. For example, vertex !!100!! is in face !!X0X!!, as shown above but also face !!1XX!! (the right side face) and !!XX0!! (the top face).
• A face contains four vertices, obtained by replacing its two !!X!!es with zeroes and ones in four different ways. The illustration above shows how this works with face !!X0X!!.
• An edge is contained in two faces, obtained by replacing one of the edge's two non-!!X!! components with an !!X!!. For example the edge !!X00!! lies in faces !!X0X!! (shown) and !!XX0!! (the top face).
• A face contains four edges, obtained by first selecting one of its two !!X!!es and then by replacing that !!X!! with either a zero or a one.

The entire cube itself can be labeled with !!XXX!!. Here's a cube with all the vertices and edges labeled. (I left out the face and body labelings because the picture was already very cluttered.)

But here's the frontmost face of that cube, detached and displayed head-on:

Every one of the nine labels has a !!0!! in the middle component. The back face is labeled exactly the same, but all the middle zeroes are changed to ones.

Here's the right-side face; every label has a !!1!! in the first component:

If any of those faces was an independent square, not part of a cube, we would just drop the redundant components, dropping the leading !!1!! from the subspaces of the !!1XX!! face, or the middle !!0!! from the subspaces of the !!X0X!! face. The result is the same in any case:

What's with those !!X!!es

In a 3-cube, every edge is parallel to one of the three coordinate axes. There are four edges parallel to each axis, that is four pointing in each of three directions. The edges whose labels have !!X!! in the first component are the ones that are parallel to the !!x!!-axis. Labels with an !!X!! in the second or third component are those that are parallel to the !!y!!- or !!z!!-axes, respectively.

Faces have two !!X!!es because they are parallel to two of the three coordinate axes. The faces !!X0X!! and !!X1X!! are parallel to both the !!x!!- and !!z!!-axes.

Vertices have no !!X!!es because they are points, and don't have a direction.

Higher dimensions

None of this would be very interesting if it didn't generalize flawlessly to !!n!! dimensions.

• A subspace of an !!n!!-cube (such as an edge, a face, etc.) is described by an !!n!!-tuple of !!\{0, 1, X\}!!.

• A subspace's dimension is equal to the number of !!X!!es in its label. (The number of zeroes and ones is often called the codimension.)

• Subspace !!A!! is contained in subspace !!B!! if every component of !!B!!'s label is either an !!X!! or matches the corresponding component of !!A!!'s label.

• Two labels designate parallel subspaces if the !!X!!es of one are a subset of the !!X!!es of the other. (‘Parallel’ here has exactly its ordinary geometric meaning.)

Subspace intersections

Two subspaces intersect if their labels agree in all the components where neither one has an !!X!!.

If they do intersect, the label of the intersection can be obtained by combining the corresponding letters in their labels with the following operator:

$$\begin{array}{c|ccc} & 0 & 1 & X \\ \hline 0 & 0 & – & 0 \\ 1 & – & 1 & 1 \\ X & 0 & 1 & X \end{array}$$

where !!–!! means that the labels are incompatible and the two subspaces don't intersect at all.

For example, in a !!3!!-cube, edges !!1X0!! and !!X00!! have the common vertex !!100!!. Faces !!0XX!! and !!X0X!! share the common edge !!00X!!.

Face !!0XX!! contains edge !!01X!!, because the intersection is all of !!01X!!. But face !!0XX!! intersects edge !!X11!! without containing it; the intersection is the vertex !!011!!.

Face !!0XX!! and vertex !!101!! don't intersect, because the first components don't match.

Counting the labels tells us that in an !!n!!-cube, every !!k!!-dimensional subspace contains !!2^i \binom ki!! subspaces of dimension !!k-i!!, and belongs to !!\binom{n-k}{j}!! super-subspaces of dimension !!k+j!!. For example, in the !!n=3!!-cube, each edge (dimension !!k=1!!) contains !!2^1\binom 11 = 2!! vertices and belongs to !!\binom{3-1}{1} = 2!! faces; each face (dimension !!k=2!!) contains !!2^1\binom 21 = 4!! edges and belongs to !!\binom{3-2}{1} =1 !! cube.

For the !!3!!-cube this is easy to visualize. Where I find it useful is in thinking about the higher-dimensional cubes. This table of the subspaces of a !!4!!-cube shows how any subspaces of each type are included in each subspace of a higher dimension. For example, the !!3!! in the !!E!! row and !!C!! column says that each edge inhabits three of the cubical cells.

$$ \begin{array}{c|ccccc} & V & E & F & C & T \\ \hline V & 1 & 4 & 6 & 4 & 1 \\ E & & 1 & 3 & 3 & 1 \\ F & & & 1 & 2 & 1 \\ C & & & & 1 & 1 \\ T & & & & & 1 \end{array} $$

The other half of the table shows how many edges inhabit each cubical cell of a !!4!!-cube: twelve, because the cubical cells of a !!4!!-cube are just ordinary cubes, each with !!12!! edges.

$$ \begin{array}{c|ccccc} & V & E & F & C & T \\ \hline V & 1 & & & & \\ E & 2 & 1 & & & \\ F & 4 & 4 & 1 & & \\ C & 8 & 12& 6 & 1 & \\ T & 16& 32& 24& 8 & 1 \end{array} $$

In a !!4!!-cube, the main polytope contains a total of !!8!! cubical cells.

More properties

Two subspaces of the same dimension are opposite if their components are the same, but with all the zeroes and ones switched. For example, in a !!4!!-cube, the face opposite to !!0XX1!! is !!1XX0!!, and the vertex opposite to !!1011!! is !!0100!!.

In a previous article, we needed to see when two vertices of the !!4!!-cube shared a face. The pair !!0000!! and !!1100!! is prototypical here: the two vertices have two matching components and two mismatching, and the shared face replaces the mismatches with !!X!!es: !!XX00!!. How many vertices share a face with some vertex !!v!!? We can pick two of the components of !!v!! to flip, creating two mismatches with !!v!!; there are !!4!! components, so !!\binom42 = 6!! ways to pick, and so !!6!! vertices sharing a face with !!v!!.

We can use this notation to observe a fascinating phenomenon of four-dimensional geometry. In three dimensions, two intersecting polyhedral faces always share an edge. In four dimensions this doesn't always happen. In the !!4!!-cube, the faces !!XX00!! and !!00XX!! intersect, but don't share an edge! Their intersection is the single vertex !!0000!!. This is analogous to the way, in three dimensions, a line and a plane can intersect in a single point, but the Flatlanders can't imagine a plane intersecting a line without containing the whole line.

Finally, the total number of subspaces in an !!n!!-cube is seen to be !!3^n!!, because the subspaces are in correspondence with elements of !!\{0, 1, X\}^n!!. For example, a square has !!3^2 = 9!! subspaces: !!4!! vertices, !!4!! edges, and !!1!! square.

[ Previously related: standard analytic polyhedra ]

[Other articles in category /math] permanent link

More about the seventh root of a 14-digit number

I recently explained how to quickly figure out the seventh root of the number !!19203908986159!! without a calculator, or even without paper if you happen to know a few things.

The key insight is that the answer has only two digits. To get the tens digit, I just estimated the size. But Roger Crew pointed out that there is another way. Suppose the number we want to find, !!n!!, is written as !!10p+q!!. We already know that !!q=9!!, so write this as !!n = 10(p+1)-1!! as in the previous article. Then expanding with the binomial theorem as before:

$$ \begin{align} n^7 & = \sum_{k=0}^7 \binom 7k\; (10(p+1))^{7-k}\; (-1)^k \\ & = (10(p+1))^ 7 + \ldots + \binom71 (10(p+1)) - 1 \\ \end{align} $$

All the terms except the last two are multiples of 100, because they are divisible by !!(10(p+1))^i!! for !!i\ge 2!!. So if we consider this equation mod-!!100!!, those terms all vanish, leaving:

$$ \begin{align} 19203908986159 & \equiv \binom71 (10(p+1)) - 1 & \pmod{100} \\ 59 & \equiv 70(p+1) - 1 & \pmod{100} \\ 90 & \equiv 70p & \pmod{100} \\ 9 & \equiv 7p & \pmod{10} \\ \end{align} $$

and the (only, because !!\gcd(7, 10) = 1!!) solution to this has !!p=7!! since !!7\cdot 7=49!!.

This does seem cleaner somehow, and my original way seems to depend on a lucky coincidence between the original number being close to !!2\cdot 10^{14}!! and my being able to estimate !!8^7 = 2^{21} \approx 2000000!! because !!2^{10}!! is luckily close to !!1000!!. On the other hand, I did it the way I did it, so in some sense it was good enough. As longtime Gentle Readers know already, I am a mathematical pig-slaughterer.

[Other articles in category /math] permanent link