Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a finite group $G$ and a positive integer $k$ that divides the order of $G$, is there some sort of algorithm or other systematic method for constructing a subgroup of $G$ of order $k$?

In particular, I am trying to find a subgroup of order 8 (a Sylow 2-subgroup) of $S_4$. However, I am most interested in a general method of constructing subgroups of a given order.

share|improve this question
4  
Since such subgroups do not always exist, it seems hard to give a general construction. –  Dylan Moreland Feb 2 '12 at 23:44
2  
In your particular case, you can view the dihedral group $D_8$ (symmetries of the square) as a subgroup of $S_4$. –  Dylan Moreland Feb 2 '12 at 23:54
1  
This obviously doesn't apply to $S_4$, but if you have an abelian group, it's easy to construct a subgroup of any order. Just express the group as a product of cyclic groups, and choose elements from each factor so that the product of their orders is $k$. –  Dane Feb 3 '12 at 0:25
    
@Dylan: Yes, the book then asks the reader to describe an isomorphism from the subgroup to $D_4$ (same group, different notation). Of course this gives the number of elements of orders 1, 2, and 4, but does this really help all that much? –  Alex Petzke Feb 3 '12 at 0:26
    
@Alex What do you mean? Are you asking how to write down $D_8$ inside of $S_4$? Sorry for the confusion. –  Dylan Moreland Feb 3 '12 at 0:39

2 Answers 2

up vote 2 down vote accepted

As noted in Dylan's comment, such a subgroup may not exist. The smallest example is the non-existence of a 6-element subgroup of $A_4$.

There is a systematic method for deciding whether there is such a subgroup, and constructing one if one exists, but it's rather trivial. First, see if there is an element of order $k$. If so, you know what to do. If not, pick two elements of order dividing $k$, and see whether they generate a subgroup of order $k$. If they do, you win. If not, pick a different pair of elements of order dividing $k$. Continue, systematically, if necessary until you have tested all pairs of elements (your group is finite, so this terminates). Then, if necessary, start on all sets of three elements, each of order dividing $k$, then all sets of four elements, etc. By this exhaustive and systematic procedure you will either find a subgroup or prove that there isn't one.

I make no claim for efficiency. In practice, you will find shortcuts. E.g., if $\lbrace a,b\rbrace$ generates a group of order not dividing $k$, then you don't have to test $\lbrace a,b,c\rbrace$. Also, you never have to test a set of more than $k$ elements.

Come to think of it, you could just go through the subsets of size $k$, testing each in turn to see whether it's a subgroup, stopping either when you find one that is or when you've eliminated all of them. Highly inefficient, but unarguably systematic.

share|improve this answer
    
May be, you could add that, we need to look at only subsets of size $k$ having the identity element. And, algorithm to see if a subset is a subgroup could be mentioned as a passing remark in case OP is not aware of it. –  user21436 Feb 3 '12 at 0:30
    
Yes, there is always process of elimination... I didn't feel very confident in the idea in the first place. I guess construction is too much to hope for. Thanks. @Kannappan: I'm fine with testing for subgroups, but if there's an actual algorithm I wouldn't mind seeing it. –  Alex Petzke Feb 3 '12 at 1:39
    
It is not a big algorithm. Given a subset, pick a non-identity element and see if its inverse is in the same set.Pick two non-identity elements and see if their product is in the same set. @AlexPetzke –  user21436 Feb 3 '12 at 3:09
    
Yes, that's the test that I know. I just haven't thought of it as an algorithm really, since it's so simple. Thanks. –  Alex Petzke Feb 3 '12 at 3:18

There are three copies of $D_8$, the dihedral group of symmetries of the square, inside of $S_4$. If you label the vertices of a square as 1, 2, 3, 4 as in the diagram here, an element of $D_8$ gives a permutation of these four numbers, i.e. an element of $S_4$. Moreover, the associated permutation completely determines the motion of the square.

You know that $D_8$ is generated by a rotation of order $4$ and a reflection. So let's see what these become in $S_4$. Rotating the square 90 degrees counterclockwise corresponds to the permutation $[1234]$, and flipping it over the horizontal axis yields $[14][23]$.

share|improve this answer
    
Very nice. Thanks. And I can see it going similarly for $D_n$ in $S_n$. –  Alex Petzke Feb 3 '12 at 2:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.