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 distribution 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 n! --------------------------------------------- (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 classes: 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