Group factorization problem: Difference between revisions

Revision as of 09:11, 27 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

History

The group factorization problem was introduced by Hoffmann in his paper Group-theoretic methods in graph isomorphism published in 1982. Hoffmann showed that graph isomorphism was a special case of a problem called the double coset membership testing problem and studied a whole class of problems (including the group factorization problem) that are Turing-equivalent to the double coset membership testing problem.

Description

Given data

Our universe is some group $U$ (such as a linear group or a permutation group) in which products and inverses can be readily computed.

A group $G$ in $U$ is specified by a generating set $A$ , and subgroups $H$ and $K$ of $G$ are specified by means of generating sets $B$ and $C$ respectively. An elements $h$ in $G$ is given (described as an element of $U$ ).

Goal

Determine whether $h$ is in $H K$ .

Relation with other problems

Equivalent decision problems

Coset intrsection problem: Here, two subgroups $H$ and $K$ are specified by means of generating sets. An element $x$ in $G$ is given, and we need to determine whether $H x$ intersects $K$ nontrivially.

The coset equality problem is equivalent to the group factorization problem because saying that $H x$ intersects $K$ nontrivially is equivalent to saying that $x^{- 1}$ is in $K H$ .

Double coset membership testing problem: Here, two subgroups $H$ and $K$ are specified by means of generating sets, and elements $g$ and $h$ are given. We need to check whether $h$ is in $H g K$ .

The group factorization problem reduces to double coset membership testing simply by setting $g$ to be the identity element. The reduction the other way is a little more tricky: it uses the fact that $x_{1} \in H x_{2} K$ if and only iff $x_{2}^{- 1} x_{1} \in H^{x_{2}} K$ , which is a group factorization.

@@ Line 23: / Line 23: @@
 ===Equivalent decision problems===
-* [[Coset itnersection problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets. An element <math>x</math> in <math>G</math> is given, and we need to determine whether <math>Hx</math> intersects <math>K</math> nontrivially.
+* [[Coset intrsection problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets. An element <math>x</math> in <math>G</math> is given, and we need to determine whether <math>Hx</math> intersects <math>K</math> nontrivially.
 The coset equality problem is equivalent to the group factorization problem because saying that <math>Hx</math> intersects <math>K</math> nontrivially is equivalent to saying that <math>x^{-1}</math> is in <math>KH</math>.