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 slightlyless 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.)
Anyway, regarding S_5 loops, I think 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 in a previous message, 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
Сайт управляется системой
uCoz