Author |
Topic: Abelian subgroup of S_n (Read 5421 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Abelian subgroup of S_n
« on: Mar 15th, 2005, 5:20pm » |
 Quote  Modify
|
What is the largest abelian subgroup of Sn (the group of permutations on n pies)?
How many are there? How many up to conjugacy? Up to isomorphism?
|
| « Last Edit: Mar 15th, 2005, 5:21pm by Eigenray » |
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Abelian subgroup of S_n
« Reply #1 on: Mar 16th, 2005, 5:13am » |
Quote Modify
|
IMHO number e plays an important role in the first question, and integer partitions in the last. 
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Abelian subgroup of S_n
« Reply #2 on: Mar 24th, 2005, 2:43am » |
Quote Modify
|
I don't know if this is the maximum but the obvious thing to do (once you know that 3 is the most efficient multiplier) is to generate the group using lots of 3-cycles. This gives the following answers:
n = 3k: 3^n elements
The number of choices is (3k)!/(6^k * k!). They're all conjugate and isomorphic.
n = 3k+1: 4*3^(n-1) elements
There are three ways to get the 4 from the last four elements: use (1234), or (12) and (34), or (12)(34) and (13)(24) as generators, or conjugations of the above. This gives 2 + 3 + 1 choices in total. Including the 3-cycles, we have
(3k+1)! / [6^k * 24 * k!] * 6 = (3k+1)! / [6^k * 4 * k!] choices.
That's 3 conjugates, and 2 isomorphism classes (either Z_4 or Z_2^2)
n = 3k+2: 2*3^n elements.
There are (3k+2)!/(6^k *2 * k!) such groups, all conjugate and isomorphic.
I'm not sure how to go about proving these are maximal.
|
| « Last Edit: Mar 24th, 2005, 2:54am by Deedlit » |
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Abelian subgroup of S_n
« Reply #3 on: Mar 24th, 2005, 2:49am » |
Quote Modify
|
Sorry, made a couple mistakes in the original.
|
| « Last Edit: Mar 24th, 2005, 2:53am by Deedlit » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Abelian subgroup of S_n
« Reply #4 on: Mar 24th, 2005, 6:50am » |
Quote Modify
|
Nicely done, Deedlit! And welcome to the forum (with a grace start). 
After you posted the solution, I understood that I misinterpreted the last question: I thought Eigenray was asking about the total number of abelian subgroups, not necessarily maximal.
on Mar 24th, 2005, 2:43am, Deedlit wrote:| I'm not sure how to go about proving these are maximal. |
|
What follows is not rigorous: IMHO the way to prove this is to show that the generators of any abelian subgroup must be disjoint cycles. This in turn follows from the fact that any permutation may be represented as a product of transpositions (2-cycles), and that (ij)(jk) [ne] (jk)(ij) unless i [ne] k.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Abelian subgroup of S_n
« Reply #5 on: Mar 24th, 2005, 9:09am » |
Quote Modify
|
Good job, Deedlit. You've apparently discovered that the answer is the maximum value of the product n1n2...nr subject to n1+...+nr=n, in positive integers.
The easiest way to prove this might be to first suppose A is an abelian subgroup of Sn that acts transitively, and figure out what |A| must be.
I did intend to just ask about the maximal abelian subgroups, but you're certainly welcome to count all of them 
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Abelian subgroup of S_n
« Reply #6 on: Mar 26th, 2005, 10:30pm » |
Quote Modify
|
I managed to figure it out!
Take any generator of the group, with a cycle we label T = (T1, T2, ...,Tn). Suppose some other generator S takes Ti to Tj, tehn commutativity implies that Ti+k will map to Tj+k for all k = 1..n. (Take the indices modulo n) The cycle generated is just a power of T, so we could eliminate it from the second generator by multiplying by T-k.
What if S hops in and out of T - for example, S takes U1 to T1 to V1. By commutativity again, we can apply powers of T to the above, and get S: Ui to Ti to Vi, where the Ui and the Vi are each T-generated n-cycles. We could have {Ui} and {Vi} be the same set; this is one possibility. Otherwise, keep applying S to {Vi} to generate more and more n-cycles of T, until eventually it must loop.
In the end, you will have an n by m array Xi,j where T takes Xi+1,j and S takes Xi,j to Xi,j+1 for 1 <= j < m. (But we do not necessarily have Sm = 1 - it could be some power of T). As above, another generator taking one element of the array to another will have to be some combination of T and S, by commutativity. And if another generator hops in and out, it will map X to copies of X, that must eventually create a loop. So in the end we have an arrray Xx1,x2,...,xa and generators T1, T2, ..., Ta such that
T1 takes Xx1,x2,...,xa to Xx1+1,x2,...,xa for 1 <= x1 <= c1 (i.e. it wraps around)
Ti takes Xx1,x2,...,xi,...,xa to Xx1,x2,...,xi+1,...,xa for 1 <= xi < ci (i.e. no wrap around)
All the other permutations of the group must act as some combination of the above, and the combinations are in one-to-one correspondence with the elements, as a single map from X1,1,...,1 to Xx1,x2,...,xa generates all the remaining maps. So the number of permutations is precisely c1 c2... cn, same as the number of elements.
The permutations of the group are determined by their actions on X and [n]-X, so the total number of permutations can't be more than the product of the number of permutations restricted to each set. Letting A(n) be the maximum order of an abelian group on n elements, we have
A(n) <= m * A(n-m) for some m.
So as Eigenray said, we want the maximum product of x1,x2,... ,xm subject to x1+x2+... +xm = n. For those who haven't seen this before, it's straightforward:
Given x1,x2,... ,xm with x1+x2+... +xm = n. We make modifications to the xi that keep the sum the same and either increase the product or keep it the same - so our original product must have been less than or equal to our final result. The modifications are:
If there is a 1, replace 1 and some number i with i+1.
If there is an i with i >= 4, replace i with 2 and i-2.
If there are three 2's, replace the three 2's with two 3's.
It's easy to see that the product can only increase with these modifications. When no more modifications can be done, there won't be any more 1's, numbers greater than 3, or more than two 2's. So must be zero, one, or two 2's and the rest 3's, yielding the maximum I gave in the previous post.
QED
Eigenray's suggestion may yield to a different solution, as
A(n) = max {the maximum order of a transitive abelian permutation group on [n], max {A(i), A(n-i) | 1 <= i < n} }
so if we could prove that the first term is never greater than the second, we'd be done. It's true if we have an n-cycle (see the first part of the above proof), and we must have one if n is prime, by Lagrange's theorem. But I don't see what to do about the n composite case.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Abelian subgroup of S_n
« Reply #7 on: Apr 5th, 2005, 4:16pm » |
Quote Modify
|
I'm not sure if I followed that completely, but it sounds right...
What I had in mind:
First, if A acts transitively, the orbit of 1 has size n, so to find |A| we compute the stabilizer of 1. But if S(1)=1, then for any i, by transitivity, pick T with T(1)=i, and by commutivity,
i=T(1)=TS(1)=ST(1)=S(i),
so S is the identity. Thus the stabilizer of 1 has order 1, so |A|=n.
Now let the orbits of A have sizes n1,...,nk, and let Ai be the restriction of A to the i-th orbit, viewing Ai <= Sn_i <= Sn. But by the above, |Ai|=ni, and A is a subgroup of (but not necessarily equal to) the (internal direct) product A1...Ak, which has order n1...nk.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Abelian subgroup of S_n
« Reply #8 on: Apr 6th, 2005, 2:22am » |
Quote Modify
|
Yes, that's a lot simpler. Still, I found my analysis enlightening - it shows in an abelian permutation group, each orbit can be represented as a hierarchy of cycle levels such that each level cycles the lower levels. Or, to put it less confusingly (maybe), each orbit can "almost" be represented as Zi_1 x ... x Zi_n, where each permutation acts on the orbit by translation. The "almost" is because I that I can't be sure that it "wraps around" properly - if Pj is the permutation that increments Zi_j by 1, I can't be sure that Pji_j({0,0,...,0}) = {0,0,...,0}, only that Pji_j({0,0,...,0}) = {x1,...,xj-1,0,...,0}. Or can I?
In other words, can each orbit of an abelian permutation group by represented as Zi_1 x ... x Zi_n, where the permutation group restricted to the orbit is simply the group of translations?
|
| « Last Edit: Apr 6th, 2005, 2:24am by Deedlit » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print