Ringing of the Changes (The Shape of 4!) 

At cathedrals around the world there is a tradition known as the "ringing of the changes", which consists of ringing the N bells in every one of the N! permutations. This has led bellringers to consider the various possible orderings of N numbers. Often the patterns used in bellringing consist of simple swaps and shifts of bell positions between adjacent peels, so that they are simple to play. It's interesting to visualize geometrically the shape of the patterns as they are being played. If we take each of the N! permutations of the numbers (1, 2,..., N) as the coordinates of a point in Nspace, then obviously all the N! points are equidistant from the origin. For N = 4, the "shape" made by joining each point to its nearest neighbors is called a "truncated octahedron", one of the 13 Archimedean solids. It has six square faces and eight hexagonal faces, making a total of 14 faces. The number of edges is 36, as required by Euler's formula F + V − E = 2. This solid is shown below, and a Java applet showing a rotating image of this solid can be seen here. 



To determine the 3D coordinates of the "4! solid" given in 4D space by the permutations of [1,2,3,4] it’s convenient to subtract 5/2 from each coordinate so as to center the solid at the origin. Then for each of the 4D vertices [W,X,Y,Z] we have W+X+Y+Z = 0, which of course is the condition that ensures us we are really dealing with a 3D solid that happens to be rotated into 4D space. We know the 4D coordinates of the vertices are the permutations of 



so each vertex is a distance of d = √5 from the origin. We want to find a rotation that brings all these points into the form [x,y,z,0]. We're free to place the point V_{1} on the x axis at V_{1}ʹ = [d, 0, 0, 0], and we can place the perpendicular point 



on the y axis at V_{2}ʹ = [0, d, 0, 0]. (We can confirm that V_{1} and V_{2} are orthogonal by computing the dot product V_{1}∙V_{2} = 0.) Now let's consider the vertex given by permuting the last two coordinates of V_{1}, i.e., 



From the known distances of this vertex to V_{1}, V_{2}, and the origin, we know the 3D coordinates of V_{3} satisfy the conditions 



which implies that x = 4/d, y = 2/d, and z = ±1, so after the rotation we can assign it the 3D coordinates V_{3}ʹ = [4/d, 2/d, 1, 0]. This is our third independent vector in our 3D space. We'll need something in 4D to complete the conditions. 

Let's say the 4D vector V_{4} = [0, 0, 0, 1] goes to V_{4}ʹ = [x,y,z,w] when subjected to our rotation. To ensure the determinant of our rotation matrix is 1 we need w = 1/2, and then preservation of the distances to V_{4} leads to the conditions 



which implies x = 3/(2d), y = −1/(2d), and z = ±1/2. Combining all these conditions we can solve for the rotation matrix R using the equation 



Applying this transformation to the original 4D "permutation points" (and noting that we need consider only 12 points because they come in opposite pairs), we have the 3D coordinates 



The other 12 points are just the negatives of these (x,y,z) vectors. As mentioned above, these 24 points constitute the vertices of a truncated octahedron. 

One way of characterizing the (n−1) dimensional polytopes is in terms of the distribution of distances between vertices. For example, with n = 4 there are 24 vertices, and the number of vertices at each squared distance from any given vertex are as listed below: 



With n = 5 there are 120 vertices, and the number of vertices at each squared distance from any given vertex are as listed below: 



In general the n! squared distances from any given vertex in the npermutation polytope are even integers and symmetrically distributed about the squared radius R^{2} = n(n^{2} − 1)/12. Thus we really only need to list the squared distances up to R^{2}/2, as shown below for the case n = 6: 



As n increases the "valency" of the squared distances approaches a continuous distribution, with a maximum valence that seems to increase at roughly the same rate as C(m,m/2) with m = 3(n−4). A plot of the distribution of distances for the npermutation polytope with n = 7, 8, 9, and 10 is shown below, with each normalized to the same width and height. 



The actual max squared distances and corresponding values of C(m,m/2) are listed below: 



As n increases the density evidently approaches a normal distribution 



where m = n(n^{2} − 1)/12 and empirically the parameters σ and A seem to be roughly given by 



where m = 3(n4). Comparisons of the normal distribution and the distribution of squared distances for n = 8, 9, 10, and 11 are shown below 











