finding the order of a group
1 Group order and Membership
Problem 2 (Membership Test). Given a finite group , and a subset of and an element , determine if .
Of course both problems have a simple solution: list all the elements of by repeated multiplication. However, if , is some arbitrary subset, it is possible for to have order up to , 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 for any subset , then given any , compute the order of and . If they are equal then , otherwise .
If instead we are able to test membership, then we may sometimes build up to the group by locating a subgroup of , testing if the elements of 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 for (as cosets not as quotient groups as need not be normal). The size of each is the index and so we can compute the order of as
Notice this required we build many elements of . To make this process efficient requires and be small enough. Part of this is handled in the next basic, yet powerful, result.
For every finite group and every set of generators of , there exists a subset of of of size no more than which also generates . Furthermore, every chain of subgroups has length no more than .
Given build the subgroup chain . Notice then that
We create as the subset of such that , that is, we remove elements the generate the same subgroups in the chain. So now
and so . ∎
We now outline the known state of these problems in various computational domains.
2 Permutation Groups
Given , then both finding the group order and the membership test problem have polynomial times solutions, polynomial in . The first algorithms 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 which gives a chain of subgroups
Applying a careful use of Schreier’s lemma to establish transversals of each section of the chain produce the order of . Moreover, this also implicitly factors every uniquely into where but . If some cannot be factored through the algorithm (a process usually called sifting) then . Thus memberhsip is also solved.
3 Polycyclic Presentations
4 Matrix groups
Here the process of computing orders and testing membership collapses to basic problems in number theory: discrete logarithms, and large integer factorization. Unfortunately, these problems have unknown computational complexity and their complexity is the backbone of many cryptographic systems.
It is a well known hard problem to factor for a large power of a prime. Thus it is often the case that we cannot determine subgroups of as there may be none of small order. Indeed may be isomorphic to for a very large prime. For example, is a prime? To determine for a given what is can require a test of this sort in general.
For membership testing the same number theoretic problems arrise. To test if would require we find out if in . 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|
|Date of creation||2013-03-22 15:54:06|
|Last modified on||2013-03-22 15:54:06|
|Last modified by||Algeboy (12884)|