Order-finding problem

From Groupprops
Jump to: navigation, search

Template:Basic computational problem

This article describes a problem in the setup where the group(s) involved is/are defined by means of an embedding in a suitable universe group (such as a linear or a permutation group) -- viz in terms of generators described as elements sitting inside this universe groupTemplate:Presentation-setup at

Description

Given data

There is a universe group U in which multiplication and inverse operations can be readily performed.

A subgroup G of U is specified by means of a generating set A for G where the elements of A are specified using some standard format for elements in U.

Goal

Determine the order of G.

Relation with other problems

Problems that reduce to it

  • Membership testing problem: Suppose we can solve the order-finding problem. Then, to solve the membership testing problem using it, do the following. Let A be a generating set for G and x be an element which we want to test for membership in G. Find the order of G (as the subgroup generated by A) and the order of the subgroup generated by A along with x. The two orders are equal if and only if G contains x.

Incidentally, this may not actually solve the problem of finding a word in the generators for the given element.

Problems it reduces to

Solution

Basic idea

The idea behind solving the order-finding problem for G comes from the following descending chain of subgroups:

G= G^{(0)} \geq G^{(1)} \geq G^{(2)} \ldots \geq G^{(n-1)} = e

where G^{(i)} = G \cap Stab_{1,2,3,...,i}(Sym(n).

By an easy coset counting argument:

[G^{(i)}:G^{(i+1)}] \leq n - i

Also, we have:

|G| = [G^{(0)}:G^{(1)}][G^{(1)}:G^{(2)}]...[G^{(n-2)}:G^{(n-1)}]

Thus, if we have an algorithm to compute each of the indices [G^{(i)}:G^{(i+1)}], then we can compute the order of G.

Obstacles and overcoming them

The cardinality [G^{(i)}:G^{(i+1)}] equals the size of the orbit of i+1 under the action of G^{(i)} and this orbit can be easily computed by a breadth-first search in the graph for the action. In fact, we can even compute a system of coset representatives for G^{(i+1)} in G^{(i)} by using the breadth-first search. Further information: minimal Schreier system

The problem, however, is: how do we get a generating set for G^{(i+1)} starting from a generating set for G^{(i)}, To solve this problem, we can use Schreier's lemma which provides a constructive approach to obtaining a generating set for the subgroup from a generating set for the whole group and a system of coset representatives (the more general problem is finding a generating set from a membership test).

This still leaves another problem: Each time we go downward on the chain, the size of the generating set may go up by a factor of n (because the index of the subgroup is O(n)). Thus, we need to keep the size of the subset small at every stage. This can be done using a small generating set-finding algorithm, such as the Sims filter or the Jerrum's filter.

Flow of the algorithm

Description of the i^{th} step of the algorithm:

Start with: a generating set A_i for G^{(i)}

Do the following:

  1. Finding coset representatives: Using a breadth-first search, find a minimal Schreier system of coset representatives for G^{(i+1)} in G^{(i)}
  2. Finding the index: From this, obtain [G^{(i)}:G^{(i+1)}]
  3. Finding a generating set: Using the coset representatives and the generating set A_i, obtain a (possibly larger) generating set for G^{(i+1)}. This uses Schreier's lemma
  4. Filtering the generating set: Apply a filter to trim the size, and call the filtered generating set A_{i+1}.

Analysis of running time

  1. Finding coset representatives: This takes time |A_i|n since that is the number of edges in the graph.
  2. Finding the index: This comes for free
  3. Finding a generating set: This takes time |A_i|n^2 since A_i|n terms need to be computed and the computation of each requires multiplication operations (which take O(n) time).
  4. Filtering the generating set: This takes time dependent on the choice of filter. A naive analysis on Jerrum's filter reveals that the time taken is O(|A_i|n^5) because the new generating set with which we start is itself of size |A_i|n. Similarly a naive analysis of the Sims filter reveals that the time it takes is O(|A_i|n^2).

Now, if we apply the filter right at the start, then at every step, |A_i| is polynomially bounded. Thus:

Total time = Time taken to apply filter at the start + n \times Time taken at each stage

Thus:

  • In the case of Jerrum's filter: n^5|A| + O(n^7)
  • In the case of Sims filter: n^2|A| + O(n^6)