Order-finding 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 group

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

• Strong generating set-finding problem: In fact, the algorithm that we describe here is, in essence, the same as the Schreier-Sims algorithm for computing a strong generating set.

Solution

Basic idea

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

$G=G^{(0)}\ge G^{(1)}\ge G^{(2)}\dots \ge G^{(n-1)}=e$

where $G^{(i)}=G\cap Sta{b}_{1,2,3,...,i}(Sym(n)$.

By an easy coset counting argument:

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

Also, we have:

$\left|G\right|=[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 $\left|A_i\right|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 $\left|A_i\right|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 $\left|A_i\right|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, $\left|A_i\right|$ 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\left|A\right|+O(n^7)$
• In the case of Sims filter: $n^2\left|A\right|+O(n^6)$