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, 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 g. The next cycle is [eabcd], which can be written as ege^–1, so it is conjugate to g. If we call this new element h, then the next element is [deabc], which can be written as dhd^–1, so it too is in the conjugacy class of g and h. 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₂ 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₃, whose six elements are

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

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

Thus 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₃, 72 have a persistence of 3, and 48 have a persistence of just 2.

If we go on to consider the group S₄, the total number of complete permutation loops is very large (23!). To give some examples, let us assign letters to each of the permutations in S₄ in reverse lexicographical order, i.e.,

The sequence of successors of this Lexi loop is

Thus it has a persistence of 2.For another example of a loop with persistent 2, we can apply the permutations (I,J), (G,L), and (E,W) to give

If, instead, we begin with the Lexi loop and make the transpositions (D,J) and (Q,S) we get a loop with the three successors shown below:

On the other hand, if we begin with the Lexi loop and make the transpositions (M,R) and (U,J), we find that the resulting loop has persistence of 4, as shown below:

If we begin with the Lexi loop and make the transpositions (M,R) and (H,W) we get the loop with persistence 1:

Based on an externsive evaluation it appears that every complete loop of S₄ has persistence of 1, 2, 3, or 4. (It's interesting to trace the sequence of conjugacy classes followed in each of these cases.) Roughly speaking, the fraction of loops with these persistences appears to be about .09, .13, .33, and .45 respectively.

Based on the preceding results, we can say that 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 distribution

where λ = 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.) The figure below shows the fraction of loops of S₅ with various persistences in a pseudo-random sample of loops.

The solid line shows the exponential distribution with λ = 1/60. 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₅ matches the exponential density, even out to extremes. The average persistence for a loop of S₅ is 2/(5!) = 60, but rare persistences in the range of several hundred 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₅ loops, one of two things must be true: either there is an S₅ loop with the absolute maximum persistence, or there is an S₅ loop that never reaches null, and instead goes periodic.

The contrast between the behavior of S_n for n < 5 and for n ≥ 5 is reminiscent of the "solveability" of groups in Galois theory. In fact, the successor sequences for S₃ and S₄ leading to the null loop are quite analogous to the normal sub-group chains of solvability for the groups related to cubics and quartics. It is very interesting that, although the behavior of permutation loops is very different for S₅ and above, it is apparently always possible to reduce any group to the null loop by repeated applications of the successor operation (unless one goes periodic).

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

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

In the case n=4 we have p(4) = 5 partitions, so there are 5 conjugacy classes of S₄. The numbers of elements in each of these classes are listed below.

Successors are evidently limited to “even” conjugacy classes, i.e., classes for which the number of transpositions is even.  Thus the only possible classes are the ones listed below.

This is why successor loops for S₄ consist only of elements of one of the three sets {D,E,I,L,M,P,T,U}, {A,H,Q}, or {X}. It seems the successors in S₄ can proceed in only one direction, and they reach the identity class {X} in no more than 4 steps.

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

7

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₅, which always consist of one of the following conjugacy classes:

Evidently a cycle of random loop of S₅ 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!. The figure below 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 1203^rd are the null loop {1+1+1+1+1}.

The Methuselah Sequence

Return to MathPages Main Menu