Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Galois Theory and Finite Permutation Groups

Date: 06/01/2007 at 15:18:35
From: Rolando
Subject: finite permutation groups

Do the elements (123456)(78) and (17) generate the symmetric group of 
order eight?

It is apparently a problem difficult to answer without the aid of a 
computer: the symmetric group of order eight consists of 
1x2x3x4x5x6x7x8 = 40320 permutations.

I know a cycle of order 7 like (1234567) and a cycle of order two 
like (18) do generate the symmetric group.  The method is to take the 
products (1234567)^t(18)(1234567)^(-t), that is, the elements 
conjugate to (18) with respect to the powers of the cycle (1234567). 
You get: (18),(28),(38),(48),(58),(68),(78).  Take now (18)(28)(18) = 
(12) and similarly get (ij) and so, the complete symmetric group.

I think the answer in the present case is not, and I guess it should 
not be very difficult to prove it.  For example, if I get the 
transposition (12) it is yes, else it is not.  I've tried to get (12) 
but I've failed.  Yet I don't have a proof.

I can get the transpositions (13),(15),(17),(35),(37),(57) and also 
(24),(26),(28),(46),(48),(68) by the method just described at the 
beginning; that is, (ij) with i and j of the same parity.  I've failed 
for one like (12).  This would decide the question.




Date: 06/02/2007 at 04:30:44
From: Doctor Jacques
Subject: Re: finite permutation groups

Hi Rolando,

You are closer to the solution than you think: you have noticed that 
you can make transpositions (i,j) if i and j have the same parity, 
but not otherwise.

Look at the action of the generators on the sets O and E of odd and 
even points, respectively.

Notice that the first generator (1,2,3,4,5,6)(7,8) interchanges O and 
E as sets; under its action, *all* odd points become even, and 
conversely.  On the other hand, the second generator (1,7) leaves O 
and E invariant as sets; *all* odd points remain odd and the same 
holds for even points.

This means that, in any case, either the sets O and E are preserved, 
or they are exchanged.  (In technical terms, we say that the sets O 
and E constitute a block system.)

Can you finish from here?  Please feel free to write back if you 
require further help.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 




Date: 06/05/2007 at 09:20:06
From: Rolando
Subject: Thank you (finite permutation groups)

Many thanks for your answer, Dr. Jacques.  A second part of the 
problem comes to me at once.

The elements (123456)(78) and (17) do not generate the symmetric group
of order eight S8.  Do they generate H?

Call H the proper subgroup of S8 whose elements are all those
permutations which preserve the set O or else exchange the sets O and
E (O = {1,3,5,7}, E = {2,4,6,8}).  I just put down what comes right
now to my head.




Date: 06/06/2007 at 03:14:00
From: Doctor Jacques
Subject: Re: Thank you (finite permutation groups)

Hi again Rolando,

The short answer is yes.

Any permutation of H can be decomposed as:

  (a) A permutation that exchanges O and E, if required
  (b) A permutation of the odd elements, that leaves the even elements
      fixed
  (c) A permutation of the even elements, that leaves the odd elements
      fixed.

If you only use one permutation for (a) (like the first generator of 
the group), this decomposition is unique.  As there are two choices 
for (a) and 24 choices for each of (b) and (c), the size of the group 
is:

  2 * 24 * 24 = 1152

Using the GAP software, it is possible to confirm that this is the 
size of G (the size can also be computed manually, using something 
called the Schreier-Sims algorithm--this is rather tedious).  We 
should try to prove this directly.

As shown before, G is a subgroup of H.  All that remains to prove is 
that G contains a generating set of H.

Now, you can generate H with the following permutations:

  (a) The first generator of the group : (1,2,3,4,5,6)(7,8). This
      permutation exchanges O and E.
  (b) All transpositions (x,y) with x and y odd. One such
      transposition is (1,7), the second generator. You should be
      able to express the others from the generators of G.

Note that, when you have this, you also have the transpositions of 
even elements (by conjugating with (a)), and this allows you to 
express any element of H.

Please feel free to write back if you require further assistance.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
College Modern Algebra
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/