Order-finding problem - Revision history

Vipul: 4 revisions

2008-05-07T23:59:00Z

4 revisions

← Older revision	Revision as of 23:59, 7 May 2008
(No difference)

Vipul at 08:10, 23 February 2007

2007-02-23T08:10:25Z

← Older revision		Revision as of 08:10, 23 February 2007
Line 25:		Line 25:
	Incidentally, this may not actually solve the problem of finding a word in the generators for the given element.		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==		==Solution==

Vipul: /* Analysis of running time */

2007-02-23T08:06:58Z

Analysis of running time

← Older revision		Revision as of 08:06, 23 February 2007
Line 73:		Line 73:
	# '''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>.		# '''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:		Now, if we apply the filter right at the start, then at every step, <math>\|A_i\|</math> is polynomially bounded. Thus:

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

Vipul at 08:06, 23 February 2007

2007-02-23T08:06:25Z

← Older revision		Revision as of 08:06, 23 February 2007
Line 27:		Line 27:
	==Solution==		==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===		===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>

Vipul at 05:23, 23 February 2007

2007-02-23T05:23:16Z

New page

{{basic computational problem}}

{{embedding-setup problem}}

{{presentation-setup at|[[Order-finding problem for presentations]]}}

==Description==

===Given data===

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

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

===Goal===

Determine the [[order of a group|order]] of <math>G</math>.

==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 <math>A</math> be a generating set for <math>G</math> and <math>x</math> be an element which we want to test for membership in <math>G</math>. Find the order of <math>G</math> (as the subgroup generated by <math>A</math>) and the order of the subgroup generated by <math>A</math> along with <math>x</math>. The two orders are equal if and only if <math>G</math> contains <math>x</math>.

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

==Solution==

===Outline===
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>.

Do the following for each <math>i</math> (inductively):

* 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>.
* 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]].

===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>.

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).

Now, computing the new generating set again takes roughly <math>|A_i|n</math> multiplications, and hence <math>|A_i|n^2</math> time.

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-