Enumerating distinct sets of k-faces of n-cubes

A recent 3blue1brown video "Exploration & Epiphany" talks about leveraging group theory to find configurations of edges of cubes, unique up to rotation. I’d call this, “distinct subsets of the set of edges of the cube,” but here’s a plot of a few different edge configurations:

In[]:=

Row[Show[cubeplt[#],ImageSize->Small]&/@{16,37,65}]

Out[]=

To be honest, I clicked on the video, paused it at 20 seconds, and said “say no more, let me do this myself in Mathematica.” A few hours later, this was the result! My result considers configurations that are mirror images of each other to be the same. Here’s all 144 distinct edge configurations (including choosing no edges at all) and 10 distinct face configurations (including choosing no faces at all).

Out[]=

Actually, in theory my approach allows us to do the same thing for any k-dimensional faces of n-dimensional hypercubes! In practice, my brute force approach only works for

n<=3

. A four dimensional cube has

edges (thirty two

-faces), and my approach tries to find orbits of

configurations! Needless to say I’m not waiting for that code to finish, and it only gets worse for higher dimensions. In the “edges of a hypercube” case there are something like

distinct configurations which is much more manageable, so the problem is definitely doable for k-faces of 4D cubes, but we can’t get that using this exact code.

I wrote a little bit about my approach to this problem below. A few notes before that though:

◼

The goal is to list all configurations in a plot-friendly format. So Burnside’s lemma falls short of our needs and is more of a sanity check for us! Stuff like checking the group order, checking that the number of k-faces of the cube goes like {8,12,6,1}, and even finding the number 144, these are just the icing on the cake of finding all the configurations in a plot friendly format.

◼

That said, this is a brute force approach, so there are certainly optimizations staring us in the face. Sometimes it’s fun to just write the simple and silly algorithm!

◼

The Mathematica heroes of this story are

GraphAutomorphismGroup

and

GroupOrbits

! They are super useful functions.

◼

Even though we can’t run the heavy part of my code for dim>3, that’s only the function

distinctKFaceConfigs

. There’s other fun code here which might be useful to you, including the

hyperOctahedralGroup

and

kFaces[k]

commands, which work just fine up to d=10.

Here are my notes explaining pieces of my code. Enjoy!

N-Faces of K-cubes

Building k-faces of n-cubes.

Take the cube in n-dimensions. We can label the vertices with indices

0,...,

-1

In[]:=

vertices[dim_]:=Range[0,2^dim-1];vertices[3]

Out[]=

{0,1,2,3,4,5,6,7}

It’s convenient to convert each vertex index to coordinates by looking at its binary digits. I also like to center the cube at the origin. So the vertices of the 3 dimensional cube with indices 0 through 7 have vertex coordinates:

In[]:=

toCoordinates[vertex_,dim_]:=(2#-1)&/@IntegerDigits[vertex,2,dim];MatrixForm[toCoordinates[#,3]]&/@vertices[3]

Out[]=



-1



To find all the edges of a cube, we look at adjacent indices that differ by one bit flip. So in 3D, the index

010

is connected to the indices

011

000

, and

110

where we flip the first, second, and then third bit. Because we’re brute forcing things at this stage, we can just enumerate all possible edges (so, we don’t mind if we list {0,1} and then also list {1,0}) and just delete duplicates later using Union.

In[]:=

bitflip[n_,i_Integer]:=BitXor[n,BitShiftLeft[1,i]];edges[dim_]:=Union[Union/@Flatten[Table[Table[{n,bitflip[n,i]},{i,0,dim-1}],{n,vertices[dim]}],1]];edges[3]

Out[]=

{{0,1},{0,2},{0,4},{1,3},{1,5},{2,3},{2,6},{3,7},{4,5},{4,6},{5,7},{6,7}}

So using this, it’s easy to, say, get the edges of a 6 dimensional hypercube.
Actually, the faces can be generated in a similar way. For edges we chose 1 bit to flip. In general for k-dimensional faces, we choose k bits of our index. Let’s take an example where we want to enumerate 2-faces of the 3-cube.
We’ll loop through every vertex. Take vertex=

010

for example, supposing we’re in 3 dimensions.

In[]:=

vertex=2;

For each vertex, there are (dim choose k) = 3 possible ways to flip two bits. We can flip the first and the second, the first and the third, or the second and the third.

In[]:=

Subsets[Range[3]-1,{2}]

Out[]=

{{0,1},{0,2},{1,2}}

Let’s say we want to represent the face found from starting at vertex, and flipping the first and third bits.

In[]:=

axisSet={0,2};

The face that this corresponds to will have

vertices, and I want to find the indices of all the vertices in this face. The number

showing up should tell us that we want to look at all subsets of the list axisSet.

In[]:=

Subsets[axisSet]

Out[]=

{{},{0},{2},{0,2}}

The face has indices: {Flip no bits of the vertex index, flip the first bit, flip the third bit, flip the first and third bits}.

In[]:=

Table[bitflip[vertex,pattern],{pattern,Subsets[axisSet,2]}]

Out[]=

{bitflip[2,{}],bitflip[2,{0}],bitflip[2,{2}],bitflip[2,{0,2}]}

I’m cheating a little bit because we have to let bitflip[] take a list in its second argument, which I haven’t coded yet. My implementation is here, and it relies on the fact that BitOr[] (with empty argument) is zero, which happens to be the behavior we want!

In[]:=

bitflip[n_,i_List]:=BitXor[n,BitOr@@(BitShiftLeft[1,#]&/@i)];

Then we do the same trick of removing duplicates with Union. So in fact this is all we need to get k-faces of n-cubes, and despite the fact that we brute forced it and removed duplicates, it’s still fast enough to work up to 10 dimensions which is way more than we need.

In[]:=

vertices[dim_]:=Range[0,2^dim-1];bitflip[n_,i_List]:=BitXor[n,BitOr@@(BitShiftLeft[1,#]&/@i)];kFaces[k_,dim_]:=Union[Union/@Flatten[(*Foreachvertex*)Table[(*Foreachpossiblek-facetouchingthisvertex*)Table[(*Foreachpossiblebitflippattern*)Table[bitflip[vertex,pattern],{pattern,Subsets[axisSet,k]}],{axisSet,Subsets[Range[dim]-1,{k}]}],{vertex,vertices[dim]}],1]];

As a sanity check, we can check that a cube has eight vertices, 12 edges, 6 faces, and one 3-face.

In[]:=

Table[Length[kFaces[k,3]],{k,0,3}]

Out[]=

{8,12,6,1}

And for higher cubes? We get OEIS A038207!

In[]:=

Table[Length[kFaces[k,4]],{k,0,4}]Table[Length[kFaces[k,5]],{k,0,5}]

Out[]=

{16,32,24,8,1}

Out[]=

{32,80,80,40,10,1}

Of course keep in mind that the point isn’t to count k-faces, the point is to get all of the explicit faces.

A really annoying thing about indices

Our interpretation of our indices and bit flipping only really works if we index from 0. However Mathematica’s powerful permutation group functions really want to work with indices starting at 1. Therefore we’ll have to relabel stuff. Here is the indexing that I actually use:

In[]:=

vertices[dim_]:=Range[1,2^dim];bitflip[n_,i_List]:=BitXor[n,BitOr@@(BitShiftLeft[1,#]&/@i)];toCoordinates[vertex_,dim_]:=(2#-1)&/@IntegerDigits[vertex-1,2,dim];kFaces[k_,dim_]:=Union[Union/@Flatten[(*Foreachvertex*)Table[(*Foreachpossiblek-facetouchingthisvertex*)Table[(*Foreachpossiblebitflippattern*)Table[1+bitflip[vertex-1,pattern],{pattern,Subsets[axisSet,k]}],{axisSet,Subsets[Range[dim]-1,{k}]}],{vertex,vertices[dim]}],1]];

In[]:=

kFaces[0,3]kFaces[1,3]kFaces[2,3]kFaces[3,3]

N-Cube automorphism group.

Mathematica has really good built-in permutation group handling. So we’re going to leverage that to the fullest extent we can! First, we can construct the graph of edges of our n-cube.

We can plot a hypercube for free here, so let’s not resist the temptation:

Quick check, for 3 dimensions we should have 48 group elements, which we do:

Note that this automorphism group includes reflections! So we’d have to do some extra work to remove them.

NB: At first I thought we could just take the odd order permutations to get the group of rotations, but this is incorrect. For example consider a permutation that mirrors things and sends the face (1,2,3,4) to (5,6,7,8). One permutation that does this is, in cycle notation, (1 5) (2 6) (3 7) (4 8), which is an even permutation.

Distinct (up to automorphisms) subsets of edges

The set of subsets of edges can be enumerated via brute force. For example, here are some possible subsets of the faces of the cube:

Our brute force strategy is this:
1. Keep a list of representative elements of each distinct set of faces.
2. For each potential new representative element, check if the rep. element lives in the orbit of any previously found representative element.
3. If it hasn’t been found before, add it to the list of representatives. Also add its entire orbit to a dictionary, so that we can easily check whether new potential representatives have already been found before.

Unfortunately this brute force algorithm dooms us for trying to do 4 dimensions. There are 32 edges of the 4-cube, and so there are 2^(32) subsets of edges. Doing a loop over 2^32 elements is not out of the question, but doing 2^32 AppendTo’s, Unions, and set comparisons is out of the question! So this approach won’t work for 4D (at least without more elbow grease than this.)

Plotting

Plotting the distinct configs:

CITE THIS NOTEBOOK

Enumerating distinct sets of k-faces of n-cubes
by David Moore
Wolfram Community, STAFF PICKS, September 9, 2025
https://community.wolfram.com/groups/-/m/t/3543108