Subgroup Algorithm

Sekky · 2007-05-17 09:53:43

Can anyone help in suggesting a low cost algorithm for finding all subgroups of a given group? and before anybody makes the joke, yes I was stupid enough to try the cartesian product and then first filter out by order, one hundred and thirty million subsets later my computer broke. So what tips and tricks can I use to find all subgroups without testing individually, and there is no guarantee that I can attribute any properties (normality, simplicity, cyclicity) to the group.

IF there's no possible method then is it possible to do given a specific property of the group? But I would love a method for all possible groups, but I doubt that's feasible. Can this be done in polynomial time?

Ricky · 2007-05-17 10:58:11

I don't quite understand your method of using a cartesian product. Hopefully this is different:

Starting with single elements, find the group generated by an element. Simply do this by calculating the cayley tables until you get closure. Then move on to groups generated by two elements, and so on. This will be in exponential time*, but it should be feasible, if you use a table. Lets say you start off with:

{a}

And after calculations you find you end up with the group:

{a, b, c, d, e}

Later on, you wish to find the group generated by:

{a, b}

But you already know the answer to this is {a, b, c, d, e} since <a> = {a, b, c, d, e}. So if you store this information in a table, you can look it up later and thus, not have to solve an already solved problem.

I don't believe there is a polynomial time solution because there may be an exponential amount of subgroups. But I'm not certain of this, I'll see if I can come up with some better reasoning or a faster algorithm.

*Edit: Actually, it probably isn't, but I'm not quite sure how to show this.

Ricky · 2007-05-17 11:02:51

You could also try to simply create subsets of order d, where d | n, n being the order of your group. Then test for closure, again by cayley table. Each cayley table can be made in polynomial time, so the run time is entirely dependent on sigma(n), which of course is linear.

Ricky · 2007-05-17 11:44:07

It appears as if I was wrong, and originally was right (it helps when you say all possibilities to cover all the bases). I did some mathematica testing, and these are the number of checks you would have to do. The first column is the order of the group:

        {"1", "1"},
        {"2", "2"},
        {"3", "2"},
        {"4", "8"},
        {"5", "2"},
        {"6", "37"},
        {"7", "2"},
        {"8", "100"},
        {"9", "86"},
        {"10", "299"},
        {"11", "2"},
        {"12", "1707"},
        {"13", "2"},
        {"14", "3525"},
        {"15", "3460"},
        {"16", "14812"},
        {"17", "2"},
        {"18", "68155"},
        {"19", "2"},
        {"20", "205297"},
        {"21", "117612"},
        {"22", "705665"},
        {"23", "2"},
        {"24", "3587151"},
        {"25", "53132"},
        {"26", "10400927"},
        {"27", "4689752"},
        {"28", "41321495"},
        {"29", "2"},
        {"30", "185903313"}

That's pasted from mathematica, I have no intention of taking the time to format it. Here are the function I used to get this:

nextDivisor[n_, k_] := (Do[If[FractionalPart[n/i] == 0, Return[i]], {i, k + 1, n}])
nCr[n_, r_] := n!/(r!*(n - r)!)
SumDivisorCombinations[n_] := (s = 1; k = 1; While[k ≠ n, k = nextDivisor[n,k]; s += nCr[n, k]]; Return[s])
Table[{i, SumDivisorCombinations[i]}, {i, 1, 30}] // TableForm

Sekky · 2007-05-17 11:45:20

Ricky wrote:

You could also try to simply create subsets of order d, where d | n, n being the order of your group. Then test for closure, again by cayley table. Each cayley table can be made in polynomial time, so the run time is entirely dependent on sigma(n), which of course is linear.

Gah, cartesian product, that's me being tired, I meant to say power set.

I'm gonna have a bash at trying to find subsets based on their order being a divisor, but I still think I'm going to end up with way too many to check.

Sekky · 2007-05-17 11:53:47

Is that list the list of the number of subgroups?

I don't get it, what about groups that are direct products of groups, do they still have the same number of subgroups?

Ricky · 2007-05-17 12:09:19

Is that list the list of the number of subgroups?

No, that list is the number of checks you would have to do if you only tried all possible combinations of sets which divide the order of the group.

I don't get it, what about groups that are direct products of groups, do they still have the same number of subgroups?

They behave exactly like any other group would. Do they still have the same number of subgroups as what?

Math Is Fun Forum

#1 2007-05-17 09:53:43

Subgroup Algorithm

#2 2007-05-17 10:58:11

Re: Subgroup Algorithm

#3 2007-05-17 11:02:51

Re: Subgroup Algorithm

#4 2007-05-17 11:44:07

Re: Subgroup Algorithm

#5 2007-05-17 11:45:20

Re: Subgroup Algorithm

#6 2007-05-17 11:53:47

Re: Subgroup Algorithm

#7 2007-05-17 12:09:19

Re: Subgroup Algorithm

Board footer