finding the order of a group

1 Group order and Membership

Problem 1 (Find Group Order). Given a finite groupMathworldPlanetmath G, and a subset S of G, determine the order of the subgroupMathworldPlanetmathPlanetmath H=S.

Problem 2 (Membership Test). Given a finite group G, and a subset S of G and an element gG, determine if gH=S.

Of course both problems have a simple solution: list all the elements of H by repeated multiplicationPlanetmathPlanetmath. However, if G=S100, S is some arbitrary subset, it is possible for S to have order up to 100!, far in excess of any reasonable computation. So the problems are actually feasiblity questions.

At first glance the two problems seem unrelated, but indeed, often they are two versions of the same problem. For example, if we can determine the order of the group S for any subset S, then given any gG, compute the order of S and S,g. If they are equal then gS, otherwise gS.

If instead we are able to test membership, then we may sometimes build up to the group H by locating a subgroup of H, testing if the elements of S lie in this subgroup, if not, extend to a larger group building a transversal for the resulting cosets as we go. In the end we have a list of subgroups


and a set of transversals Ti for Hi/Hi-1 (as cosets not as quotient groupsMathworldPlanetmath as Hi-1 need not be normal). The size of each Ti is the index [Hi:Hi-1] and so we can compute the order of H as


Notice this required we build |T0|+|T1|++|Tk| many elements of H. To make this process efficient requires |Ti| and k be small enough. Part of this is handled in the next basic, yet powerful, result.

Proposition 1.

For every finite group G and every set of generatorsPlanetmathPlanetmathPlanetmath S of G, there exists a subset of T of S of size no more than log2|G| which also generates G. Furthermore, every chain of subgroups has length no more than log2|G|.


Given S={s1,,sk} build the subgroup chain Gi=s1,,si. Notice then that


We create T as the subset of sirS such that GirGir-1, that is, we remove elements the generate the same subgroups in the chain. So now




and 2[Gir:Gir-1] so jlog2|G|. ∎

We now outline the known state of these problems in various computational domains.

2 Permutation Groups

Given G=Sn, then both finding the group order and the membership test problem have polynomial timesMathworldPlanetmath solutions, polynomial in n. The first algorithmsMathworldPlanetmath of this sort where developed by Charles C. Sims and the computational complexity established by Frust Hopcroft and Luks. These are now known collectively as the Schreier-Sims algorithms because their principle theoretical tool is Schreier’s lemma.

To solve use G(i)={gG:1g=1,,ig=i} which gives a chain of subgroups


Applying a careful use of Schreier’s lemma to establish transversals of each sectionPlanetmathPlanetmath of the chain produce the order of G. Moreover, this also implicitly factors every gG uniquely into g1g2gn-1 where giG(i-1) but giG(i). If some gSn cannot be factored through the algorithm (a process usually called sifting) then gG. Thus memberhsip is also solved.

3 Polycyclic Presentations

A polycyclic presentationMathworldPlanetmath by its very design exhibits a chain of subgroups of known prime indices. The order of the group is therefore a produce of the primes. Membership testing can be handled in various ways including sifting the element of the generators of the presentation.

4 Matrix groups

Here the process of computing orders and testing membership collapses to basic problems in number theoryMathworldPlanetmath: discrete logarithmsMathworldPlanetmath, and large integer factorization. Unfortunately, these problems have unknown computational complexity and their complexity is the backbone of many cryptographic systems.

For example, given a subgroup H of GL(2,q) for some q=pi, i sufficiently large, it may be that H is a cyclic groupMathworldPlanetmath, for example a subgroup of the multiplication of the field GF(q)×. For instance


It is a well known hard problem to factor q-1 for q=pi a large power of a prime. Thus it is often the case that we cannot determine subgroups of H as there may be none of small order. Indeed H may be isomorphicPlanetmathPlanetmathPlanetmath to r for r a very large prime. For example, is 2127-1 a prime? To determine for a given gGL(2,2127) what |g|=|g| is can require a test of this sort in general.

For membership testing the same number theoretic problems arrise. To test if gH=h=GF(q)× would require we find out if g=hi in GF(q). This is a problem known as the discrete logarithm.

5 General presentations of groups

Given an arbitrary presentation of a group, Boone demonstrates it is impossible even to know if the group is the trivial group. Thus the problem of knowning if the order is non-zero is impossible. Membership testing is therefore also impossible.

Title finding the order of a group
Canonical name FindingTheOrderOfAGroup
Date of creation 2013-03-22 15:54:06
Last modified on 2013-03-22 15:54:06
Owner Algeboy (12884)
Last modified by Algeboy (12884)
Numerical id 6
Author Algeboy (12884)
Entry type Algorithm
Classification msc 20B40
Related topic SchreiersLemma