Permutation Loops

Suppose  a,b,c,d,e  are elements of a group.  We'll call a circular
arrangement of such elements a "loop".  For example, we might choose 
to arrange those elements in alphabetical order, giving the loop 
{abcde}, where the last element is understood to wrap around to the 
first.  Note that {abcde} and {eabcd} are both valid representations 
of the same loop, since they are just rotations of each other.

For any given loop, a "cycle" consists of the sequence of elements 
going once around the loop from any specific starting point.  Thus, 
a loop of length N has N cycles.  For example, the five cycles of 
the loop {abcde} are [abcde], [eabcd], [deabc], [cdeab], and [bcdea].

Using the group operation we can evaluate each cycle of a given 
loop.  (A group operation is associative, so there's no ambiguity 
about how to evaluate the composition of each cycle.)  The resulting 
sequence of elements constitutes another loop, which we will call 
the "successor" of the original loop.  Of course, if the group 
operation is commutative, each cycle of a given loop will evaluate 
to the same element, so a successor loop is not very interesting.  
However, if the group operation is NOT commutative, then successor 
loops will typically be non-trivial.

Even if the group operation is not commutative, it's clear that the 
elements of a successor loop must all belong to a single conjugacy
class.  To see why, suppose the cycle [abcde] evaluates to the group
element x.  The next cycle is [eabcd], which can be written as e x e^-1,
so it is conjugate to x.  If we call this new element y, then the next
element is [deabc], which can be written as d y d^-1, so it too is in
the conjugacy class of x and y.  And so on.

It's interesting to see how the successor operation affects loops 
consisting of elements of the symmetric group S_n.  I'll represent 
the elements of S_n by the permutations of n objects, and accordingly 
I'll refer to these loops as "permutation loops".  Also, I'll focus 
on the effects of the successor operation on *complete* permutation 
loops, consisting of some arrangement of all n! elements in a loop 
of length n!.

The elements of S_2 are just the two permutations represented by I=[12]
and A=[21].  There's only one complete permutation loop of order 2,
namely, {IA}, which is the same loop as {AI}.  The first successor of 
this loop is {AA}, and the next successor is {II}.  All subsequent
successors are simply {II}.

For a slightly less trivial example, consider the symmetric group S_3,
whose sixe elements are

                  I = 123         C = 231
                  A = 132         D = 312
                  B = 213         E = 321

One possible loop of these elements is {IDEACB}.  The six cycles of
this loop are evaluated as

                  IDEACB = A
                  DEACBI = A
                  EACBID = B
                  ACBIDE = A
                  CBIDEA = A
                  BIDEAC = E

Therefore, the successor of {IDEACB} is {AABAAE}.  Continuing in
this way we can generate the sequence of successors as shown below:

   {IDEACB},  {AABAAE},  {DCDCDC},  {IIIIII},  {IIIIII}, ...

After three applications of the successor operation, we arrive at
the "null loop", i.e., the loop consisting entirely of identity 
elements.  (All subsequent successors are obviously null loops.)
Therefore, we say the original loop {IDEACB} has a "persistence" 
of 3.  Of the 120 complete cycles that can be formed from S_3, 
72 have a persistence of 3, and 48 have a persistence of just 2.

If we go on to consider the group S_4, the total number of complete 
permutation loops is very large (23!), but evidently every such loop 
has persistence of 1, 2, 3, or 4.  (It's interesting to trace the 
sequence of conjugacy classes followed in each of these cases.)  
Thus, every complete loop of the symmetric group S_n for n less 
than 5 has persistence less than or equal to n.

However, for n=5 and above the behavior is suddenly quite different.  
In these cases the persistence T of a randomly chosen complete 
permutation loop of order n has essentially an exponential 
                  dens(T) = L exp(-LT)  

where L = 2/(n!).  It's clear that since the total number of 
transpositions in all the elements of S_n (n>4) is even, each 
successor must represent an "even" conjugacy class, of which
there are n!/2 possible representatives.  Exactly one of those 
is the null class, so on each iteration the probability of reaching 
null is 2/n!.  This is a Poisson process leading to (approximately) 
the exponential distribution with rate parameter 2/(n!).  (It's
interesting that random permutation loops under the successor
operation exhibit a "half-life" identical to radio-active decay.)

Of course, the distribution cannot really be perfectly exponential,
because there is only a finite (although huge) number of distinct
complete loops, so only a finite number of persistences can occur.
Still, it's remarkable how accurately the distribution of persistences
for S_5 matches the exponential density, even out to extremes.  The
average persistence for a loop of S_5 is 2/(5!) = 60, but rare 
persistences in the range of several hundreds occur at just the 
rates predicted by the exponential density.  

After much computer searching I've found two permutation loops of 
order 5 with persistences greater than 1000.  These are extremely
rare, considering that the mean persistence is only 60.  Here is a 
loop with persistence 1009 (read by rows):

25134 13254 12354 13245 42153 53124 45123 45213 24153 24135
23541 21543 13524 25431 52134 14352 14253 21453 53412 21534
15243 24351 31452 32415 31542 45321 42135 51432 21435 34512
54321 31425 12543 45312 41325 34215 43215 53421 35421 34125
23451 41532 52314 43521 31245 41352 31524 25143 53241 12453
43152 31254 42513 51234 43125 54123 32514 54132 54312 23514
52341 34521 23154 43512 32541 34152 42531 24315 45132 15342
32451 41235 51243 52431 24531 15324 25413 15234 24513 54231
14523 14532 13425 14235 42315 52143 15432 25314 51324 51423
35124 23145 35241 12345 21354 43251 13542 32154 12435 41523
34251 42351 52413 53142 13452 23415 45231 32145 35142 54213
14325 21345 12534 53214 51342 15423 35412 35214 41253 25341

Here is the Methuselah of permutation loops of order 5, having a
persistence of 1203 (read by rows):

12453 45231 52341 31254 53421 32514 12435 52413 23154 15243
13254 35214 24135 45123 45132 25143 12543 42513 54321 51423
32541 42153 14532 32154 32451 41325 25431 24513 51324 13245
51243 21453 15234 32145 24531 14253 43215 12534 15342 23541
52431 24351 34152 31524 12354 25413 54132 52314 13425 43125
54213 14523 14325 31542 43251 52134 42135 45321 41235 34512
35142 23415 51342 25314 54123 45312 54312 41352 42315 35124
13542 41532 53142 52143 21543 23145 43152 21534 35421 15432
34521 25341 53241 51432 31425 34251 21345 23451 34215 45213
35241 53214 23514 51234 31452 43521 53412 24153 14352 13524
21354 15423 41523 42531 35412 32415 31245 42351 53124 24315
43512 21435 14235 54231 12345 34125 25134 41253 13452 15324

Finding this 1203 loop seems to have been a remarkable stroke of 
luck, because a loop of order 5 with a persistence of 1203 is 
expected to be about a "1-in-500 million" loop, whereas I had only
generated less than 20 million "random" loops.  I've never found 
another one close to this.

It's interesting that for any given initial loop there is normally 
a (small) set of transpositions that leave the persistence unchanged,
whereas any other single transposition generally results in a
completely uncorrelated persistence.  It's also worth noting that 
if an odd number of components is removed from a complete permutation 
loop, it appears that the successors never degenerate to the null 
string.  (By the way, the greatest persistence for a complete 
permutation loop of order 6 that I've found is 3952, but I haven't 
searched very much.)

Regarding S_5 loops, one of two things must be true: either there is 
an S_5 loop with the absolute maxiumum persistence, or there is an 
S_5 loop that NEVER reaches null, and instead goes periodic.  I suspect
the former is true. I believe every complete loop of a symmetric group 
eventually decomposes to a null loop, but I don't know how to prove it.

If true, this is an interesting higher-order analog to "solveability"
of groups in Galois theory.  In fact, the successor sequences for S_3
and S_4 leading to the null loop parallel the normal sub-group chains
of solvability for the groups related to cubics and quartics.  I find
it very interesting that, although the behavior is very different for
S_5 and above, it is apparently always possible to reduce any group to 
the null loop by repeated applications of the successor operation.

By the way, two elements of S_n are in the same conjugacy class if 
and only if they have the same cyclic structure, so the number of
conjugacy classes of S_n is p(n), the number of partitions of n.  
Also, the number of members of a given conjugacy class can be 
computed from the corresponding partition.  If we let a_k denote 
the number of k's in a given partition of n, then the number of 
members of the conjugacy class corresponding to that partition is 
given by the multinomial coefficient

      (1^a_1)(a_1)! (2^a_2)(a_2)! ... (n^a_n)(a_n)!

These coefficients are called M2 in Abramowitz and Stegun's "Handbook 
of Mathematical Functions", tabulated for all the permutations of the 
numbers n = 1 to 10.

For example, with n=5 we have p(5) = 7 partitions, so there are 7 
conjugacy classes of S_5.  The numbers of elements in each of these 
classes are given by the multinomial coefficients as shown below

               Number of
   Cyclic      Conjugacy      number of
   Structure   Classes (M2)   transpositions    Order
   ---------   ------------   --------------    -----
    5              24              4              5              
    4+1            30              3              4
    3+2            20              3              6
    3+1+1          20              2              3
    2+2+1          15              2              2
    2+1+1+1        10              1              2
    1+1+1+1+1       1              0              1
         total    120

As mentioned previously, a loop cycle of order 5 or above must 
always give an "even" conjugacy class, i.e., a class whose cyclic 
structure has an even number of transpositions.  This is confirmed 
by examining the elements of the successor loops to various complete
loops of S_5, which always consist of one of the following conjugacy

               Number of
   Cyclic      Conjugacy      number of
   Structure   Classes (M2)   transpositions    Order
   ---------   ------------   --------------    -----
    5              24              4              5              
    3+1+1          20              2              3
    2+2+1          15              2              2
    1+1+1+1+1       1              0              1
           total   60

Evidently a cycle of random loop of S_5 has an equal chance of 
evaluating to any of these 60 even permutations (which fixes 
the conjugacy class for that generation), so the sequence of 
successors typically jumps between the conjugacy classes {5},
{3+1+1}, and {2+2+1}, with only a 1/60 chance of hitting the
identity class {1+1+1+1+1} on each generation.  This makes the
successor operation a Poisson process, and explains why the
persistences have essentially an exponential distribution with
a "rate" of 2/n!.  Figure 1 shows the sequence of conjugacy
classes for the Methuselah sequence of persistence 1203.  Each
small vertical stripe represents a loop, and the color denotes
the conjugacy class, with blue={5}, red={3+1+1}, and green=
{2+2+1}.  The initial white loop on the top row represents the
initial Methuselah arrangement, and thereafter each row shows
200 loops, except for the last row, which shows 203 loops to
give the total 1203.  All the loops subsequent to the 1203rd
are the null loop {1+1+1+1+1}.

    Figure 1: The Methuselah Sequence

Return to MathPages Main Menu