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 bell-ringers to
consider the various possible orderings of N numbers.  Often the
patterns used in bell-ringing 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 N-space, then obviously all the N! points are equi-distant
from the origin.  For N=4, the "shape" made by joining each point 
to its nearest neighbours is what's called a "truncated octahedron", 
one of the 13 Archimedian 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.  If your web
browser supports Java applets, you can see a rotating image of this
solid here.

To determine the 3D coordinates of the "4! solid" given in 4D space 
by the permutations of [1,2,3,4] it might be easiest 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

      V1  =  [-3/2, -1/2, +1/2, +3/2]

so each vertex is a distance of d = sqrt(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 V1 on the x axis 
at [d, 0, 0, 0], and we can place the perpindicular point

      V2  =  [+1/2, -3/2, +3/2, -1/2]

on the y axis at [0, d, 0, 0].  (Note that V1 and V2 are
orthogonal, as can be seen by computing V1 dot V2 = 0.)

Then, for lack of any better ideas, let's consider the vertex
given by permuting the last two coordinates of V1, i.e.,

       V3  =  [-3/2, -1/2, +3/2, +1/2]

From the known distances of this vertex to V1, V2, and the origin, 
we know the 3D coordinates of V3 satisfy the conditions

            x^2 + y^2 + z^2  =  5

          (x-d)^2 + y^2 + z^2  =  2

           x^2 + (y-d)^2 + z^2  =  6

which implies that

           x = 4/d     y = 2/d    z = +-1

so we can assign it the 3D coordinates [4/d, 2/d, 1, 0].  This is
our third independent vector in our 3D space, so we'll need something 
in 4D to complete the conditions.  Let's say the 4D vector 

              V4 = [0, 0, 0, 1] 

goes to [x,y,z,w] when it is 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 V4 leads to the conditions

           x^2 + y^2 + z^2  =  1 - (1/2)^2

         (x-d)^2 + y^2 + z^2  =  3 - (1/2)^2

          x^2 + (y-d)^2 + z^2  =  7 - (1/2)^2

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
          _                      _  _                     _
         |  d   0   4/d   3/(2d)  ||  -3/2  1/2 -3/2   0   |-1
   R =   |  0   d   2/d  -1/(2d)  ||  -1/2 -3/2 -1/2   0   |
         |  0   0    1     1/2    ||   1/2  3/2  3/2   0   |
         |_ 0   0    0     1/2   _||_  3/2 -1/2  1/2   1  _|

                        _                        _
                       |  -3/d  -1/d   1/d   3/d  |
               =  (1/2)|   1/d  -3/d   3/d  -1/d  |
                       |    1     3     3     1   |
                       |_   1     1     1     1  _|

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

       2W  2X  2Y  2Z        x      y      z
       --- --- --- ---     -----  -----  -----
       -3  -1  +1  +3        d      0      0
       -3  -1  +3  +1       4/d    2/d     1
       -3  +3  -1  +1       2/d   -4/d     1
       -3  +3  +1  -1       1/d   -2/d     2
       -3  +1  -1  +3       4/d   -3/d     0
       -3  +1  +3  -1       2/d    1/d     2
       -1  -3  +1  +3       4/d    2/d    -1
       -1  -3  +3  +1       3/d    4/d     0
       -1  +1  -3  +3       2/d   -4/d    -1
       -1  +1  +3  -3      -1/d    2/d     2
       -1  +3  +1  -3      -2/d   -1/d     2
       -1  +3  -3  +1        0     -d      0

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 we have the 24 vertices are at following squared distances
from any given vertex

d^2:   0  2  4  6  8 10 12 14 16 18 20
  #:   1  3  1  4  2  2  2  4  1  3  1

With n=5, the 120 distances relative to any given vertex are

d^2: 0  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40
  #: 1  4  3  6  7  6  4 10  6 10  6 10  6 10  4  6  7  6  3  4  1

In general the n! squared distances from any given vertex in the
n-permutation 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:

d^2:  0  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30 32 34
  #:  1  5  6  9 16 12 14 24 20 21 23 28 24 34 20 32 42 29

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) whith m=3(n-4).  A plot of the 
distribution of distances for the n-permutation 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:

               max
          n  valence  C(m,m/2)
         --- ------- ---------
          7     184     126      0.6848
          8    1066     924      0.8668
          9    6688    6435      0.9622
         10   49062   48620      0.9910

As n increases the density evidently approaches a normal distribution

                      / ((x-u)/s)^2 \
         V(x) = A exp( ------------- )
                      \       2     /

where u = n(n^2 - 1)/12 and empirically the parameters s and A seem 
to be roughly given by
     
        s  ~  2u sqrt(n/3)
        A  ~  C(m,m/2)   with    m = 3(n-4)

Comparisons of the normal distribution and the distribution of 
squared distances for n=8, 9, 10, and 11 are shown below









Return to MathPages Main Menu