朝花夕拾

轻飘飘的旧时光就这么溜走 转头回去看看时已匆匆数年

Todd - Coxeter Algorithm and Uniform Polytopes


This project renders various kinds of 3d/4d convex uniform polytopes using Python and POV-Ray, the code is here.

Requirements: numpy and the free raytracer POV-Ray.

Examples

All images and videos below are created by this program. The data of the polytopes are computed in Python and then exported to POV-Ray for rendering. There are also some CSG computations in the POV-Ray part, but that's not the main focus of this document.

  1. The five Platonic Solids:

  2. The thirteen Archimedean solids:

  3. Prisms and antiprisms:

  4. The six 4d regular polychora:

  5. Uniform polychora obtained by truncating the above six regular ones (there are more than one way to truncate a polytope, here we only list one for each of the six):

  6. 4d prisms and duoprisms:

  7. The four Kepler-Poinsot solids:

The following video shows the omnitruncated dodecahedron:

I also made a video that tries to reproduce the scene in the wonderful math movie Dimensions: it shows the mose intriguing 4d regular polytope 120-cell, which has 600 vertices, 1200 edges, 720 faces and 120 cells. All the vertices/edges/faces/cells are congruent in 4d space, but are distorted when projected to 3d space under stereographic projection.

NEW UPDATE: I have added a new script for making animations of polytopes rotating in 4d, here are some examples, you can click on the image to see the video:

Video Animations

5-cell tesseract 16-cell
24-cell 120-cell 600-cell
truncated tesseract 3-20 duoprism great 120-cell
grand 120-cell icosahedral 120-cell great icosahedron
truncated dodecahedron prism grand stellated 120-cell snub 24-cell

Now we explain the math behind this program.

What are these images about?

Strictly speaking, all these images are about convex/non-convex, uniform polytopes in 3d/4d Euclidean spaces. Here we note the keywords: convex/non-convex, Euclidean and uniform.

"converx" is quite easy to understand, it means that any line segment that joins two points on the polytope lies entirely in the enclosure of the polytope. Of course there are also "non-convex" polytopes, for example the small stellated dodecahedron:

In the 3d Euclidean space there are 18 different convex uniform polytopes (excluding the two infinite classes prisms and antiprisms) and 57 different non-convex uniform polytopes. Currently this program can only render the convex ones and a few non-convex ones and I still need to figure out the right way to make it work for all uniform polytopes in the future.

"Euclidean" is also easy to understand, it's emphasized here because one can also define other metrics on the 3d/4d real vector space (for example the hyperbolic metric), which bends the space and makes the polytoes look like "deformed". The most famous example is the logo "Spikey" of mathematica, it's a dodecahedron in the hyperbolic 3-space:

The word "uniform" requires some math subtleties. Roughly it means

  1. all vertices are the same.
  2. all faces are regular polygons.
  3. all cells are uniform polyhedron.

To explain what is "the same", we need the language in group theory: it means that the symmetry group \(G\) of the polytope acts transitively on the set of vertices, that is, for any pair of vertices \(u, v\), there is some \(g\in G\) that transforms \(v\) to \(u\): \(g\cdot v=u\).

How to compute the data of a polytope

Though these polytopes look quite different in appearance, all of them can be constructed in one uniform apprach called Wythonff construction (also called kaleidoscope construction). In principal it's the same with the way how a kaleidoscope works: we place some reflection planes (called mirrors) in the space, where all these mirrors pass through the origin and the angles between them are carefully chosen (these angles must be of the form \(\pi-\pi/p\) for some rational \(p\)). These mirrors partitioned the space into "rooms". Choose any room and an initial vertex \(v_0\) in it, we then repeatly reflect \(v_0\) about the mirrors to get the set of virtual images. All these virtual images together with \(v_0\) form the vertices of our polytope, and if two vertices \(v,v'\) are symmetric about the \(i\)-th mirror, then \((v,v')\) is an edge of type \(i\) and we color it with the \(i\)-th color in the palette. If a virual image \(v\) is firstly reflected about mirror \(i\) and then reflected about mirrot \(j\), then since the composition of two reflections is a rotation, \(v\) is rotated about the axis which connects the origin and the center of some face \(f\) by an angle of \(2\pi/m\) (assuming the angle between mirror \(i\) and mirror \(j\) is \(\pi-\pi/m\)). One can recover \(f\) by applying this rotation \(m\) times.

To implement the above strategy into a pratical program we have two main problems to solve:

  1. For a given convex unifom polytope, how should we place the mirrors and choose the initial vertex \(v_0\)?

  2. When the mirrors and \(v_0\) are ready for use, how can we get all virtual images of \(v_0\)?

The answer to the first question is called Coxeter-Dynkin diagram, which is a labelled undirected graph that "encodes" all the information we need. Each uniform polytope has a corresponding Coxeter-Dynkin diagram, but different Coxeter-Dynkin diagrams may represent the same polytope.

For example the Coxeter-Dynkin diagram of the cube is

we explain this diagram in detail:

In a Coxeter-Dynkin diagram, each node represents one mirror in the kaleidoscope. The above diagram has three nodes, so there are three mirrors in the case of cube. We label the corresponding mirrors from left to right as \(m_0, m_1, m_2\). For a pair of nodes the labelled edge between them records the angle between their mirrors:

  1. Two nodes are not connected if the angle between their mirrors is \(\pi/2\).
  2. Two nodes are connected by an unlabelled edge if the angle between their mirrors is \(\pi-\pi/3\).
  3. Two nodes are connected by an edge labelled \(m>3\) if the angle between their mirrors is \(\pi-\pi/m\).

Also we use "circled" nodes to indicate which mirrors are "active": a mirror is called "active" if and only if it does not contain the initial vertex \(v_0\), or in other words, if and only if reflecting \(v_0\) about this mirror gives a virtual image.

So in the above example \(\langle m_0,m_1\rangle=\pi-\pi/4\)\(\langle m_1,m_2\rangle=\pi-\pi/3\)\(\langle m_0,m_2\rangle=\pi/2\). \(m_0\) is active but \(m_1\) and \(m_2\) are not.

Hence we can place these three mirrors in the 3d space as follows: (we use \(n_i\) to denote the unit normal vector of \(m_i\))

  1. The normal of \(m_0\) can be arbitrary, for example \(n_0=(1, 0, 0)\).
  2. The angle between \(n_1\) and \(n_0\) is \(3\pi/4\), we can simply choose \(n_1\) to be \(n_1=(\cos\dfrac{3\pi}{4}, \sin\dfrac{3\pi}{4}, 0)\).
  3. The normal of \(m_2\) is perpendicular to \(n_0\), so \(n_2\) is of the form \((0,y_3,z_3)\). By \(\langle n_1,n_2\rangle= 2\pi/3\) we have \(y_3 \sin\dfrac{3\pi}{4}=\cos\dfrac{2\pi}{3}\) and \(z_3=\sqrt{1-y_3^2}\). Solve these two equations to get \(y_3,z_3\).

To choose an initial vertex \(v_0\) which lies on \(m_1,m_2\) but not on \(m_0\), we can let \(v_0\) has distance 1 to \(m_0\) and distance 0 to both \(m_1\) and \(m_2\):

\[\begin{align*}\langle v_0, n_0\rangle=1,\\\langle v_0, n_1\rangle=0,\\\langle v_0, n_2\rangle=0.\\\end{align*}\]

Simply solve this linear system to get \(v_0\).

I mentioned before that the angles between the mirrors must be carefully chosen to ensure that \(v_0\) and its virtual images form the vertices of an uniform polytope, this restricts us to only finitely many choices, you can refer to this wiki page for the complete list.

The answer to the second question is Todd-Coxeter algorithm, I'll discuss it in the next section.

Finitely presented groups and Todd-Coxeter algorithm

How can one get all virtual images of the initial vertex \(v_0\) in the mirrors? An obvious (and also crude) way to do this is simply repeatly reflecting \(v_0\) abut those mirrors, and after each reflection compare the result with the set of virtual images obtained so far (within a predefined rounding error bound), until no more new virtual images can occcur. This approach is easy to program and has the merit that it's almost the unique choice to implement Wythoff constrution in shaders, for example see this great shadertoy program by Matt Zucker. But this approach is ugly from a mathematician's aesthetic: it did not use the plenty of symmetries inherent in the polytope!

This program took another "symbolic computation" way by solving the word problem in the symmetric group. It has the advantage that one can get all exact information of the polytope without using any rounding errors or approximating procedure. The price is the math invovled here is a bit complicated (and so is the code) and the reader needs to have some preliminary knowledge in group theory.

Firstly let's recall the "orbit-stabilizer" theorem in group theory:

Theorem: If a group \(G\) acts transitively on a set \(S\) and for some \(x\in S\) the stabilizing subgroup of \(x\) is \(H\leq G\), then there is a one-to-one correspondence between \(S\) and the right cosets in \(G/H\): \(x\cdot g\to Hg\).

Note the action of \(G\) on \(S\) is written as "acting on the right", this is mainly for programming convenience and there is no significant difference with "acting on the left".

The theorem tells us that if a group \(G\) acts transitively on a set \(S\) and for some \(x\in S\) we know its stabilizing subgroup in \(G\) is \(H\), then we can recover the whole \(S\) by acting a set of coset representatives of \(G/H\) on \(x\).

So for a given uniform polytope \(P\), we can compute all its vertices as follows:

  1. Get a presentation of its symmetric group \(G\) and an initial vertex \(v_0\) from the Coxeter-Dynkin diagram.

  2. Get a presentation of \(v_0\)'s stabilizing subgroup \(H\) and compute a set of right coset representatives of \(G/H\).

  3. Apply these representatives on \(v_0\) to get all vertices.

Again we use the cube as an example to show this procedure: recall the Coxeter-Dynkin diagram of the cube is

The mirrors are \(m_0,m_1,m_2\), their normals are \(n_0,n_1,n_2\), the reflection transformations about these mirrors are \(\rho_0,\rho_1,\rho_2\), and the matrix of \(\rho_i\) is \(M_i=I - 2n_in_i^T\) (see Householder transformation).

The symmetry group \(G\) of the cube is generated by three "fundamental reflections" \(\rho_0,\rho_1,\rho_2\), a presentation is

\[G = \langle\rho_0,\rho_1,\rho_2\ |\ \rho_0^2=\rho_1^2=\rho_2^2=(\rho_0\rho_1)^4=(\rho_1\rho_2)^3=(\rho_0\rho_2)^2=1\rangle.\]

This is because a reflection is always involutionay, i.e. has order 2, and since \(\rho_0, \rho_1\) are two reflections with angle \(3\pi/4\) between their mirrors \(m_0\) and \(m_1\), \(\rho_0\rho_1\) is a rotation about the intersection line of their mirrors with angle \(3\pi/2\), hence \((\rho_0\rho_1)^4=1\). Similarily one has the relations for \(\rho_1\rho_2\) and \(\rho_0\rho_2\).

One can use Todd-Coxeter algorithm (to be explained later) to compute a complete list of the elements in \(G\):

\[\begin{array}{lll}e&\rho_{0}&\rho_{0}\rho_{1}\\\rho_{0}\rho_{1}\rho_{0}&\rho_{0}\rho_{1}\rho_{0}\rho_{1}&\rho_{1}\rho_{0}\rho_{1}\\\rho_{1}\rho_{0}&\rho_{1}&\rho_{0}\rho_{2}\\\rho_{2}&\rho_{1}\rho_{2}&\rho_{1}\rho_{2}\rho_{1}\\\rho_{2}\rho_{1}&\rho_{0}\rho_{1}\rho_{2}&\rho_{0}\rho_{1}\rho_{2}\rho_{1}\\\rho_{0}\rho_{2}\rho_{1}&\rho_{0}\rho_{1}\rho_{0}\rho_{2}&\rho_{0}\rho_{1}\rho_{0}\rho_{1}\rho_{2}\\\rho_{0}\rho_{1}\rho_{0}\rho_{1}\rho_{2}\rho_{1}&\rho_{0}\rho_{1}\rho_{0}\rho_{2}\rho_{1}&\rho_{1}\rho_{0}\rho_{1}\rho_{2}\\\rho_{1}\rho_{0}\rho_{2}&\rho_{1}\rho_{0}\rho_{2}\rho_{1}&\rho_{1}\rho_{0}\rho_{1}\rho_{2}\rho_{1}\\\rho_{2}\rho_{1}\rho_{0}&\rho_{2}\rho_{1}\rho_{0}\rho_{1}&\rho_{0}\rho_{2}\rho_{1}\rho_{0}\rho_{1}\\\rho_{0}\rho_{2}\rho_{1}\rho_{0}&\rho_{1}\rho_{0}\rho_{2}\rho_{1}\rho_{0}&\rho_{1}\rho_{0}\rho_{2}\rho_{1}\rho_{0}\rho_{1}\\\rho_{1}\rho_{2}\rho_{1}\rho_{0}\rho_{1}&\rho_{1}\rho_{2}\rho_{1}\rho_{0}&\rho_{0}\rho_{1}\rho_{0}\rho_{2}\rho_{1}\rho_{0}\\\rho_{0}\rho_{1}\rho_{0}\rho_{2}\rho_{1}\rho_{0}\rho_{1}&\rho_{0}\rho_{1}\rho_{2}\rho_{1}\rho_{0}\rho_{1}&\rho_{0}\rho_{1}\rho_{2}\rho_{1}\rho_{0}\\\rho_{1}\rho_{0}\rho_{1}\rho_{2}\rho_{1}\rho_{0}&\rho_{1}\rho_{0}\rho_{1}\rho_{2}\rho_{1}\rho_{0}\rho_{1}&\rho_{0}\rho_{1}\rho_{0}\rho_{1}\rho_{2}\rho_{1}\rho_{0}\rho_{1}\\\rho_{0}\rho_{1}\rho_{0}\rho_{1}\rho_{2}\rho_{1}\rho_{0}&\rho_{2}\rho_{1}\rho_{0}\rho_{1}\rho_{2}&\rho_{1}\rho_{2}\rho_{1}\rho_{0}\rho_{1}\rho_{2}\\\rho_{0}\rho_{2}\rho_{1}\rho_{0}\rho_{1}\rho_{2}&\rho_{0}\rho_{1}\rho_{2}\rho_{1}\rho_{0}\rho_{1}\rho_{2}&\rho_{1}\rho_{0}\rho_{2}\rho_{1}\rho_{0}\rho_{1}\rho_{2}\\\rho_{1}\rho_{0}\rho_{1}\rho_{2}\rho_{1}\rho_{0}\rho_{1}\rho_{2}&\rho_{0}\rho_{1}\rho_{0}\rho_{2}\rho_{1}\rho_{0}\rho_{1}\rho_{2}&\rho_{0}\rho_{1}\rho_{0}\rho_{1}\rho_{2}\rho_{1}\rho_{0}\rho_{1}\rho_{2}\end{array} \]

Since in the Coxeter-Dynkin diagram only the mirror \(m_0\) is active, i.e. the initial vertex \(v_0\) is on \(m_1,m_2\) but not on \(m_0\), both \(\rho_1\) and \(\rho_2\) map \(v_0\) to itself while \(\rho_0\) maps \(v_0\) to its mirror image about \(m_0\), hence the stabilizing subgroup of \(v_0\) is 1 \[H=\langle \rho_1, \rho_2\ |\ \rho_1^2=\rho_2^2=(\rho_1\rho_2)^3=e\rangle.\] Obviously \(H\) is the dihedral group \(D_3\) hence \(|H|=6\) and \(|G/H|=8\). Again by applying Todd-Coxeter algorithm one can get a list of coset representatives of \(G/H\): \[\begin{array}{llll}e&\rho_{0}&\rho_{0}\rho_{1}&\rho_{0}\rho_{1}\rho_{0}\\\rho_{0}\rho_{1}\rho_{2}&\rho_{0}\rho_{1}\rho_{0}\rho_{2}&\rho_{0}\rho_{1}\rho_{0}\rho_{2}\rho_{1}&\rho_{0}\rho_{1}\rho_{0}\rho_{2}\rho_{1}\rho_{0}\end{array} \] Apply them on \(v_0\) one gets the 8 vertices of the cube. For example the action of \(\rho_0\rho_1\) on \(v_0\) is given by \[v_0(\rho_0\rho_1)=(v_0\rho_0)\rho_1=(v_0M_0)\rho_1=v_0M_0M_1.\] Here \(v_0\) is written as a row vector and all \(M_i\)'s are symmetric matrices.

The above procedure also works for edges and faces. For example if we want to find all edges of type \(i\), we can go as follows:

  1. Check if \(v_0\) is on the mirror \(m_i\). If the answer is yes, then the reflection \(\rho_i\) fixes \(v_0\) and there are no edges of type \(i\), else let \(v_1=\rho_i(v_0)\), then \((v_0, v_1)\) form an edge \(e\) of type \(i\).

  2. \(\rho_i\) fixes \(e\) by interchanging \(v_0\) and \(v_1\), hence is the generator of the stabilizing subgroup of \(e\): \(H=\langle \rho_i \rangle\). 2

  3. Find a set of coset representatives of \(G/H\) and apply them on \(e\) to get all edges of type \(i\). (need to remove duplicates like \((u,v)\), \((v,u\)))

Finding all faces requires more subtle work but the principals are still the same. For a pair \(i\ne j\), if at least one of \(m_i\) and \(m_j\) is active then the rotation \(r_{ij}=\rho_i\rho_j\) generates a face \(f\) of type \((i,j)\) and \(f\) is invariant under \(r_{ij}\). Here we need to consider some cases like whether \(v_0\) is on exactly one of the two mirrors and whether \(m_i\) and \(m_j\) are perpendicular to each other. Anyway the stabilizing subgroup of \(f\) is either \(H=\langle \rho_i\rho_j \rangle\) or \(H=\langle \rho_i,\rho_j \rangle\) 3. Again we compute a set of coset representatives of \(G/H\) and apply them on \(f\) to get all faces of type \((i,j)\).

Now the key step reduces to computing a set of coset representatives of \(G/H\) for a finitely presented group \(G\) and its subgroup \(H\), this is exactly what Todd-Coxeter algorithm does.

Todd-Coxeter algorithm is very much like playing a sudoku game, in which the table to complete is a dynamically growing 2d array \(T\), the rows of \(T\) are labelled by the right cosets in \(G/H\) and the columns of \(T\) are labelled by the generators of \(G\). \(T[i][j]\) records the right coset obtained by multiplicating the \(j\)-th generator on the right of the \(i\)-th coset. The algorithm repeatly uses the defining relations in the presentation of \(G\) and \(H\) as "guidelines" to find new cosets and fill their corresponding entries in \(T\). The "game" is over once all entries in \(T\) are filled, the coset in each entry has a row in \(T\) and all relations are satisfied by each row. Such \(T\) obtained is nothing but the adjacent matrix of the schreier graph of \(G/H\) and one can easily get a word representation for each coset representative of \(G/H\).

For a complete treatment of Todd-Coxeter algorithm the reader should refer to (also referred as HCGT in this document)

Chapter 5, Handbook of Computational Group Theory, Holt, D., Eick, B., O'Brien, E.

I will demonstrate below how the algorithm goes using the cube as an example:

Example: let \(G\) by the symmetric group of the cube: \[G = \langle\rho_0,\rho_1,\rho_2\ |\ \rho_0^2=\rho_1^2=\rho_2^2=(\rho_0\rho_1)^4=(\rho_1\rho_2)^3=(\rho_0\rho_2)^2=1\rangle\] and subgroup \(H=\langle \rho_1, \rho_2\rangle\). Find a set of coset representatives of \(G/H\).

Let's list down all known relations for this "sudoku game" first:

Our known relations:

  1. For each generating word of \(H\) it holds \(Hw=H\), i.e. \(H\rho_1=H\) and \(H\rho_2=H\).
  2. For any coset \(K\) and any generating relation \(r\) of \(G\) it holds \(Kr=K\), i.e. \[K\rho_i^2=K,\quad i=0,1,2. \\ K(\rho_0\rho_1)^4=K(\rho_1\rho_2)^3=K(\rho_0\rho_2)^2=K.\]

These relations can be stored in two lists, one for the relations in \(H\) and one for the relations in \(G\), each relation can be stored as an array of int type.

The first list stores the generating words of \(H\):

  1. (1,) // \(\rho_1\)
  2. (2,) // \(\rho_2\)

The second list stores the defining relations of \(G\):

  1. (0, 0) // \(\rho_0^2=1\)
  2. (1, 1) // \(\rho_1^2=1\)
  3. (2, 2) // \(\rho_2^2=1\)
  4. (0, 1, 0, 1, 0, 1, 0, 1) // (\(\rho_0\rho_1)^4=1\)
  5. (1, 2, 1, 2, 1, 2) // (\(\rho_1\rho_2)^3=1\)
  6. (0, 2, 0, 2) // (\(\rho_0\rho_2)^2=1\)

The relations are numbered from 0-7 so later we can refer to them quickly.

Note: when \(G\) is not in the form of a Coxeter group (for example the case of snub polytopes) we should also account the inverse of the generators and they too occupy their columns in \(T\), so the actual number of columns in \(T\) is 2 \(\times\) (number of generators). But for Coxeter groups all generators are involutions so there is no need to insert the columns for their inverse.

Initially the table \(T\) has only one row in it:

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\)

where \(H_0=H\).

The algorithm firstly checks \(H_0\) satisfies all relations in the first list (once this is done the first list can be discarded) and then scans all cosets of \(T\) from top to bottom and make sure the current coset satisfies all relations in the second list. In this process new cosets are defined and their rows are appended at the end of \(T\), and it may also happen that we found some cosets in the table indeed represent the same coset.


Let's begin by scanning \(H_0\) and check the relations in the first list are satisfied by it:

(1). For relation 0 we have \(H_0\rho_1=H_0\), i.e. \(T[0][1]=0\), for relation 1 we have \(H_0\rho_2=H_0\), i.e. \(T[0][2]=0\). \(T\) becomes

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\) 0 0

Now \(H_0\) satisfies all relations in the first list so this list can be discarded. From now on we only check relations in the second list.

we move on to check the relations in the second list are satisfied by \(H_0\):

(2). Relation 2 says \(H_0\rho_0^2=H_0\), since we do not know \(H_0\rho_0\) yet, we define it to be \(H_1\), fill 1 in its entry \(T[0][0]\) and also append a new row for \(H_1\):

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\) 1 0 0
\(H_1\) 0

Note each time we define or find \(H_i\rho_j=H_k\) for some \(i,j,k\) we automatically get the "paired" relation \(H_k\rho_j=H_i\), so we always fill in a pair of entries \(T[i][j]=k\) and \(T[k][j]=i\) at a time.

(3). Relations 3, 4 are already satisfied, continue.

(4). Relation 5 says \(H_0\rho_0\rho_1\rho_0\rho_1\rho_0\rho_1\rho_0\rho_1=H_0\). We already know \(H_0\rho_0=H_1\) but \(H_1\rho_1\) is unknown, so we define it to be \(H_2\), fill in the two entries and append a new row for \(H_2\):

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\) 1 0 0
\(H_1\) 0 2
\(H_2\) 1

\(H_2\rho_0\) is again unknown, so we define \(H_2\rho_0=H_3\) and \(T\) becomes

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\) 1 0 0
\(H_1\) 0 2
\(H_2\) 3 1
\(H_3\) 2

Continuing the scanning we find \(H_3\rho_1\) is again unknown, you may think that we can define it to be a new coset \(H_4\) as we did before and then move on. This strategy works in principal, but in practice it creates many redundant cosets and the table \(T\) grows very rapidly. Instead we scan the relation "backward" to try to fill the gaps without defining new cosets. Remember we have scanned from the left to the following position: \[H_0\rho_0\rho_1\rho_0(=H_3)\rho_1\rho_0\rho_1\rho_0\rho_1=H_0.\] Scanning the above relation from right to left we have \(H_0\rho_1\rho_0\rho_1\rho_0=H_3\), that is, \[H_0\rho_0\rho_1\rho_0(=H_3)\rho_1 =H_0\rho_1\rho_0\rho_1\rho_0=H_3.\] Hence \(H_3\rho_1=H_3\) and we have inferred the coset \(H_3\rho_1\) without defining it to be a new coset. We call this a deduction according to the book HCGT, and \(T\) becomes

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\) 1 0 0
\(H_1\) 0 2
\(H_2\) 3 1
\(H_3\) 2 3

So in the actual program we always scan a relation from both ends and define new cosets if necessary until they meet.

(5). Relation 6 is already satisfied, continue.

(6). Relation 7 says \(H_0\rho_0\rho_2\rho_0\rho_2=H_0\), scanning from both ends gives \[H_0\rho_0(=H_1)\rho_2=H_0\rho_2\rho_0=H_1,\] hence \(H_1\rho_2=H_1\) and we found another deduction. \(T\) becomes

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\) 1 0 0
\(H_1\) 0 2 1
\(H_2\) 3 1
\(H_3\) 2 3

Now \(H_0\) satisfies all relations in the two lists so the scanning of the first row is completed. We move on and begin the scanning of \(H_1\).

(1). Relations 2, 3, 4, 5 are already satisfied, continue.

(2). Relation 6 says \(H_1\rho_1\rho_2\rho_1\rho_2\rho_1\rho_2=H_1\), in which \(H_1\rho_1=H_2\) is known but \(H_2\rho_2\) is unknown. The backward scanning also got stuck here: \[H_1\rho_1(=H_2)\rho_2\rho_1=H_1\rho_2\rho_1\rho_2=H_2\rho_2.\] So we define \(H_2\rho_2=H_4\), then \(H_4\rho_1=H_4\) and \(T\) becomes

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\) 1 0 0
\(H_1\) 0 2 1
\(H_2\) 3 1 4
\(H_3\) 2 3
\(H_4\) 4 2
  1. One can check relation 7 is already satisfied so the scanning of \(H_1\) is completed and we move on to scan the row for \(H_2\).

I'll leave the scanning of \(H_2,H_3,H_4,H_5\) to you as easy exercises. When \(H_2\) is completed your \(T\) should be

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\) 1 0 0
\(H_1\) 0 2 1
\(H_2\) 3 1 4
\(H_3\) 2 3 5
\(H_4\) 5 4 2
\(H_5\) 4 3

After \(H_3\) is completed your \(T\) should be

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\) 1 0 0
\(H_1\) 0 2 1
\(H_2\) 3 1 4
\(H_3\) 2 3 5
\(H_4\) 5 4 2
\(H_5\) 4 6 3
\(H_6\) 5 6

After \(H_4\) is completed your \(T\) should be

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\) 1 0 0
\(H_1\) 0 2 1
\(H_2\) 3 1 4
\(H_3\) 2 3 5
\(H_4\) 5 4 2
\(H_5\) 4 6 3
\(H_6\) 7 5 6
\(H_7\) 6 7

And the scanning of \(H_5\) gives no more information.

When scanning \(H_6\) we found that relations 2-6 are already satisfied, from relation 7 \(H_6\rho_0\rho_2\rho_0\rho_2=H_6\) we get a deduction \(H_7\rho_2=H_7\) and \(T\) becomes

\(\rho_0\) \(\rho_1\) \(\rho_2\)
\(H_0\) 1 0 0
\(H_1\) 0 2 1
\(H_2\) 3 1 4
\(H_3\) 2 3 5
\(H_4\) 5 4 2
\(H_5\) 4 6 3
\(H_6\) 7 5 6
\(H_7\) 6 7 7

One can check that \(H_7\) satisfies all relations in the list now, so no more cosets could be found and the game is over.

Using breadth-first search one can get the multiplication relations between these cosets:

\[\begin{array}{l}H_0 = H_0\cdot e,\\ H_1=H_0\cdot\rho_0,\\H_2=H_1\cdot\rho_1=H_0\cdot\rho_0\rho_1,\\H_3=H_2\cdot\rho_0=H_0\cdot\rho_0\rho_1\rho_0,\\ H_4=H_2\cdot\rho_2=H_0\cdot\rho_0\rho_1\rho_2,\\ H_5=H_3\cdot\rho_2=H_0\cdot \rho_0\rho_1\rho_0\rho_2,\\ H_6=H_5\cdot\rho_1=H_0\cdot \rho_0\rho_1\rho_0\rho_2\rho_1,\\ H_7=H_6\cdot\rho_0=H_0\cdot \rho_0\rho_1\rho_0\rho_2\rho_1\rho_0.\end{array}\]

So a set of representatives can be chosen as

\[\begin{array}{llll}e&\rho_{0}&\rho_{0}\rho_{1}&\rho_{0}\rho_{1}\rho_{0}\\\rho_{0}\rho_{1}\rho_{2}&\rho_{0}\rho_{1}\rho_{0}\rho_{2}&\rho_{0}\rho_{1}\rho_{0}\rho_{2}\rho_{1}&\rho_{0}\rho_{1}\rho_{0}\rho_{2}\rho_{1}\rho_{0}\end{array} \]

This is exactly what we have seen before.

Note: this example is a bit tedious but is still a simple one because we didn't encounter the case that two cosets in the table are found to be the same one (in the book HCGT this is called a coincidence). When this is encountered the scanning must be paused and the control flow is jumped to handling this coincidence: open a new stack \(q\) and push this pair of coincidence into \(q\), then we pop one pair of coincidence in \(q\) at a time, merge their rows and push new coincidences occurred in the merging process into \(q\).

The case of snub polytopes

Snub polytopes can be constructed by only applying rotations in the full symmetry group to the initial vertex \(v_0\). We have seen that in the case of the cube the full symmetry group \(G\) is \[G = \langle\rho_0,\rho_1,\rho_2\ |\ \rho_0^2=\rho_1^2=\rho_2^2=(\rho_0\rho_1)^4=(\rho_1\rho_2)^3=(\rho_0\rho_2)^2=1\rangle.\] \(G\) has 48 elements in it and exactly half of them are rotations, so we have 24 rotations here. These 24 rotations form the symmetry group \(\widetilde{G}\) of the snub cube and can be generated by three "fundamental rotations" \[r_0=\rho_0\rho_1, r_1=\rho_1\rho_2,r_2=\rho_0\rho_2.\] Note since \(r_0r_1=r_2\) hence \(\widetilde{G}\) can be in fact generated by only \(r_0\) and \(r_1\).

A presentation of \(\widetilde{G}\) is \[\widetilde{G}=\langle r_0,r_1\ |\ r_0^4=r_1^3=(r_0r_1)^2=1\rangle.\] Using Todd-Coxeter algorithm we get a complete list of word representations of \(\widetilde{G}\):

\[\begin{array}{lll}e&r_{0}&r_{0}r_{0}\\r_{0}r_{0}r_{0}&r_{1}&r_{1}r_{1}\\r_{0}r_{1}&r_{0}r_{1}r_{1}&r_{0}r_{0}r_{1}\\r_{0}r_{0}r_{1}r_{1}&r_{0}r_{0}r_{0}r_{1}&r_{1}r_{0}\\r_{1}r_{0}r_{0}&r_{1}r_{0}r_{0}r_{0}&r_{1}r_{1}r_{0}\\r_{1}r_{1}r_{0}r_{0}&r_{0}r_{1}r_{1}r_{0}&r_{0}r_{1}r_{1}r_{0}r_{0}\\r_{0}r_{0}r_{1}r_{1}r_{0}&r_{1}r_{0}r_{0}r_{1}&r_{1}r_{0}r_{0}r_{1}r_{1}\\r_{1}r_{0}r_{0}r_{0}r_{1}&r_{1}r_{1}r_{0}r_{0}r_{1}&r_{0}r_{1}r_{1}r_{0}r_{0}r_{1}\end{array} \]

Choose \(v_0\) so that it's not on any of the three mirrors \(m_0,m_1,m_2\) and apply these words to \(v_0\) one gets the complete set of 24 vertices of the snub cube.

The edges can be obtained as follows: firstly we apply \(r_i(i=0,1,2)\) to \(v_0\) to form an initial edge \(e=(v_0, r_i(v_0))\) which is of type \(i\), we then use the whole \(\widetilde{G}\) to transform \(e\) to get all other edges of type \(i\) and remove duplicates in the result.

For the faces since \(r_0^4=1\), the array \(\{v_0, r_0(v_0), r_0^2(v_0), r_0^3(v_0)\}\) generates a square face, similarily \(r_1^3=1\) and \(\{v_0,r_1(v_0),r_1^2(v_0)\}\) generates a triangular face. Another type of triangular face can be generated by \(\{v_0, r_1(v_0), r_2(v_0)\}\). We then use \(\widetilde{G}\) to transform these "fundamental faces" to get all faces of this snub polytope.

Appendix

I also added a script example_coset_enumeration.py for showing how to compute the coset table of \(G/H\) for a finitely presented group \(G\) and its subgroup \(H\) (necessarily \(|G/H|<\infty\)). It assumes an input yaml file which depicts the presentation of \(G\) and \(H\). An example format is

name: G8723
relators:
  - aaaaaaaa
  - bbbbbbb
  - abab
  - AbAbAb
subgroup-generators:
  - aa
  - Ab

By convention uppercase letters are the inverse of lowercase letters, i.e. \(A=a^{-1},B=b^{-1}\).

So the presentation of this group is \[G = \langle a, b\ |\ a^8=b^7=(ab)^2=(a^{-1}b)^3=1\rangle\] and \(H=\langle a^2, a^{-1}b\rangle\).

Save this file as G8723.yaml and run

python example_coset_enumeration.py G8723.yaml

The output should be (I have omitted some output here)

           a    A    b    B
------------------------------
    1:     2    2    3    2
    2:     1    1    1    4
    3:     4    5    6    1
    4:     7    3    2    8
  ...    ...  ...  ...  ...
  ...    ...  ...  ...  ...
  ...    ...  ...  ...  ...
  446:   444  444  441  430
  447:   438  433  432  443
  448:   445  445  440  445

so \(G/H\) has 448 cosets.

Finally the image below is my current github favicon made with this program: (a runcinated 120-cell)


Update

You can also render a polyhedra on the unit sphere by doing the computations in 4d and then projecting it back to 3d:


  1. It seems that we can only say \(H\) is contained in the stabilizing subgroup of \(v_0\) and may not be exactly equal to it. This is in fact a property of Coxeter groups: in the geometric realization of a Coxeter group \(W\) (that is, represent \(W\) as a set of reflections about hyperplanes in \(\mathbb{R}^n\)), for any point \(v\) in the fundamental domain, the stabilizing subgroup of \(v\) is a standard parabolic subgroup which is generated by those simple reflections whose hyperplanes contain \(v\). This "obvious" geometric intuition requires a quite non-trivial proof, see Humphreys's book "reflection groups and Coxeter groups", chapter 1.

  2. Similar with footnote 1. The stabilizing subgroup of the edge \(e\) fixes its middle point so is contained in the standard parabolic subgroup \(\langle\rho_i\rangle\), hence is exactly \(\langle\rho_i\rangle\).

  3. Similar with footnote 1, 2.