Order-finding problem: Difference between revisions

Revision as of 08:06, 23 February 2007

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

Template: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.

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)} \dots \geq G^{(n - 1)} = e$

where $G^{(i)} = G \cap S t a b_{1, 2, 3, . . ., i} (S y m (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^{t h}$ step of the algorithm:

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

Do the following:

Finding coset representatives: Using a breadth-first search, find a minimal Schreier system of coset representatives for $G^{(i + 1)}$ in $G^{(i)}$
Finding the index: From this, obtain $[G^{(i)} : G^{(i + 1)}]$
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
Filtering the generating set: Apply a filter to trim the size, and call the filtered generating set $A_{i + 1}$ .

Analysis of running time

Finding coset representatives: This takes time $| A_{i} | n$ since that is the number of edges in the graph.
Finding the index: This comes for free
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).
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} | < / m a t h . i s p o l y n o m i a l l y b o u n d e d . T h u s : T o t a l t i m e = T i m e t a k e n t o a p p l y f i l t e r a t t h e s t a r t + < m a t h > 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})$

@@ Line 27: / Line 27: @@
 ==Solution==
-===Outline===
+===Basic idea===
-For the case of permutation groups, the order-finding problem can be solved by appealing to the [[Schreier-Sims algorithm]]. The idea is as follows:
-First, use the original generating set <math>A</math> to obtain a [[strong generating set]], call that <math>A_0</math>.
+The idea behind solving the order-finding problem for <math>G</math> comes from the following descending chain of subgroups:
-Do the following for each <math>i</math> (inductively):
+<math>G= G^{(0)} \geq G^{(1)} \geq G^{(2)} \ldots \geq G^{(n-1)} = e</math>
-* Define <math>G^{(i)}</math> as the subgroup of <math>G</math> comprising those permutations that fix the elements from 1 to <math>i</math>. Assume inductively that a [[strong generating set]] <math>A_i</math> has been constructed for <math>G^{(i)}</math>.
+where <math>G^{(i)} = G \cap Stab_{1,2,3,...,i}(Sym(n)</math>.
-* Determine the orbit of <math>i+1</math> under the action of <math>G^{(i)}</math>, and, for each element <math>j</math> in the orbit, an element of <math>G^{(i)}</math> that sends <math>i+1</math> to <math>j</math>. This is achieved by doing a breadth-first or depth-first search in the graph with vertices numbers from <math>i + 1</math> to <math>n</math> and where two vertices are joined by an edge if their [[left quotient]] is an element in
-<math>A_i</math>.
-* The size of this orbit is the index <math>[G^{(i)}:G^{(i + 1)}]</math> and the elements of <math>G^{(i)}</math> which take <math>i + 1</math> to the respective <math>j</math>s form a [[left transversal]] (viz a system of coset representatives)
-* Use [[Schreier's lemma]] to obtain a generating set for <math>G^{i+1}</math> using <math>A_i</math> and the system of coset representatives
-* Trim this to a small generating set for <math>G^{(i+1)}</math> by appealing to the [[strong generating set-finding problem]], using either [[Sims filter]] or [[Jerrum's filter]].
-Note that these steps (except the last one) are a very particular case of the general problem of [[finding a generating set from a membership test]].
+By an easy coset counting argument:
+<math>[G^{(i)}:G^{(i+1)}] \leq n - i</math>
+Also, we have:
+<math>|G| = [G^{(0)}:G^{(1)}][G^{(1)}:G^{(2)}]...[G^{(n-2)}:G^{(n-1)}]</math>
+Thus, if we have an algorithm to compute each of the indices <math>[G^{(i)}:G^{(i+1)}]</math>, then we can compute the order of <math>G</math>.
+===Obstacles and overcoming them===
+The cardinality <math>[G^{(i)}:G^{(i+1)}]</math> equals the size of the orbit of <math>i+1</math> under the action of <math>G^{(i)}</math> 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 <math>G^{(i+1)}</math> in <math>G^{(i)}</math> by using the breadth-first search. {{further|[[minimal Schreier system]]}}
+The problem, however, is: how do we get a generating set for <math>G^{(i+1)}</math> starting from a generating set for <math>G^{(i)}</math>, 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 <math>n</math> (because the index of the subgroup is <math>O(n)</math>). 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 <math>i^{th}</math> step of the algorithm:
+'''Start with''': a generating set <math>A_i</math> for <math>G^{(i)}</math>
+'''Do the following''':
+# '''Finding coset representatives''': Using a breadth-first search, find a [[minimal Schreier system]] of coset representatives for <math>G^{(i+1)}</math> in <math>G^{(i)}</math>
+# '''Finding the index''': From this, obtain <math>[G^{(i)}:G^{(i+1)}]</math>
+# '''Finding a generating set''': Using the coset representatives and the generating set <math>A_i</math>, obtain a (possibly larger) generating set for <math>G^{(i+1)}</math>. This uses [[Schreier's lemma]]
+# '''Filtering the generating set''': Apply a filter to trim the size, and call the filtered generating set <math>A_{i+1}</math>.
 ===Analysis of running time===
-We need to analyze the running time at the <math>i^{(th}}</math> stage of the algorithm, that is, the stage where we pass from a generating set of <math>G^{(i)}</math> to a generating set of <math>G^{(i+1)}</math>.
+# '''Finding coset representatives''': This takes time <math>|A_i|n</math> since that is the number of edges in the graph.
+# '''Finding the index''': This comes for free
+# '''Finding a generating set''': This takes time <math>|A_i|n^2</math> since <math>A_i|n</math> terms need to be computed and the computation of each requires multiplication operations (which take <math>O(n)</math> time).
+# '''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 <math>O(|A_i|n^5)</math> because the new generating set with which we start is itself of size <math>|A_i|n</math>. Similarly a naive analysis of the [[Sims filter]] reveals that the time it takes is <math>O(|A_i|n^2)</math>.
+Now, if we apply the filter right at the start, then at every step, <math>|A_i|</math. is polynomially bounded. Thus:
-Let's see how we can do this. We first need to determine the orbit of <math>i+1</math>. Since it is a breadth-first search, the time taken to locate all elements is bounded above by the number of edges, which is <math>|A_i|n</math>. The time taken to find their corresponding coset representatives is bounded above by <math>|A_i}n^2</math> (the extra factor of <math>n</math> comes because multiplication takes linear time).
+Total time = Time taken to apply filter at the start + <math>n \times</math> Time taken at each stage
-Now, computing the new generating set again takes roughly <math>|A_i|n</math> multiplications, and hence <math>|A_i|n^2</math> time.
+Thus:
-Since the size of the new generating set is <math>|A_i|n</math>, we need to use that as generating set size for computing the running times of the Sims filter or Jerrum's filter.gpedit Order-
+* In the case of Jerrum's filter: <math>n^5|A| + O(n^7)</math>
+* In the case of Sims filter: <math>n^2|A| + O(n^6)</math>