wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Abelian subgroup of S_n
        
(Message started by: Eigenray on Mar 15^th, 2005, 5:20pm)

Title: Abelian subgroup of S_n
Post by Eigenray on Mar 15^th, 2005, 5:20pm

What is the largest abelian subgroup of S_n (the group of permutations on n pies)?
How many are there? How many up to conjugacy? Up to isomorphism?

Title: Re: Abelian subgroup of S_n
Post by Barukh on Mar 16^th, 2005, 5:13am

IMHO number e plays an important role in the first question, and integer partitions in the last. ;)

Title: Re: Abelian subgroup of S_n
Post by Deedlit on Mar 24^th, 2005, 2:43am

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.

Title: Re: Abelian subgroup of S_n
Post by Deedlit on Mar 24^th, 2005, 2:49am

Sorry, made a couple mistakes in the original.

Title: Re: Abelian subgroup of S_n
Post by Barukh on Mar 24^th, 2005, 6:50am

Nicely done, Deedlit! And welcome to the forum (with a grace start). :D

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 03/24/05 at 02:43:30, 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.

:-/

Title: Re: Abelian subgroup of S_n
Post by Eigenray on Mar 24^th, 2005, 9:09am

Good job, Deedlit. You've apparently discovered that the answer is the maximum value of the product n₁n₂...n_r subject to n₁+...+n_r=n, in positive integers.

The easiest way to prove this might be to first suppose A is an abelian subgroup of S_n 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 ;D

Title: Re: Abelian subgroup of S_n
Post by Deedlit on Mar 26^th, 2005, 10:30pm

I managed to figure it out!

Take any generator of the group, with a cycle we label T = (T₁, T₂, ...,T_n). Suppose some other generator S takes T_i to T_j, tehn commutativity implies that T_i+k will map to T_j+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 U₁ to T₁ to V₁. By commutativity again, we can apply powers of T to the above, and get S: U_i to T_i to V_i, where the U_i and the V_i are each T-generated n-cycles. We could have {U_i} and {V_i} be the same set; this is one possibility. Otherwise, keep applying S to {V_i} 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 X_i,j where T takes X_i+1,j and S takes X_i,j to X_i,j+1 for 1 <= j < m. (But we do not necessarily have S^m = 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 X_x1,x2,...,xa and generators T₁, T₂, ..., T_a such that

T₁ takes X_x1,x2,...,xa to X_{x1+1,x2,...,xa} for 1 <= x₁ <= c₁ (i.e. it wraps around)
T_i takes X_{x1,x2,...,xi,...,xa} to X_{x1,x2,...,xi+1,...,xa} for 1 <= x_i < c_i (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 X_1,1,...,1 to X_x1,x2,...,xa generates all the remaining maps. So the number of permutations is precisely c₁ c₂... c_n, 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 x₁,x₂,... ,x_m subject to x₁+x₂+... +x_m = n. For those who haven't seen this before, it's straightforward:

Given x₁,x₂,... ,x_m with x₁+x₂+... +x_m = n. We make modifications to the x_i 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.

Title: Re: Abelian subgroup of S_n
Post by Eigenray on Apr 5^th, 2005, 4:16pm

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 n₁,...,n_k, and let A_i be the restriction of A to the i-th orbit, viewing A_i <= S_{n_i} <= S_n. But by the above, |A_i|=n_i, and A is a subgroup of (but not necessarily equal to) the (internal direct) product A₁...A_k, which has order n₁...n_k.

Title: Re: Abelian subgroup of S_n
Post by Deedlit on Apr 6^th, 2005, 2:22am

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 Z_{i_1} x ... x Z_{i_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 P_j is the permutation that increments Z_{i_j} by 1, I can't be sure that P_j^i_j({0,0,...,0}) = {0,0,...,0}, only that P_j^i_j({0,0,...,0}) = {x₁,...,x_j-1,0,...,0}. Or can I?

In other words, can each orbit of an abelian permutation group by represented as Z_{i_1} x ... x Z_{i_n}, where the permutation group restricted to the orbit is simply the group of translations?