# Constructing a subgroup of a given order

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.

-
Since such subgroups do not always exist, it seems hard to give a general construction. –  Dylan Moreland Feb 2 '12 at 23:44
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
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

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.

-
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]$.

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