Group factorization problem

From Groupprops
Jump to: navigation, search

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

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

Relation with other problems

Equivalent decision problems

  • Coset intersection 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 Hx intersects K nontrivially.

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

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 Hx_2K if and only iff x_2^{-1}x_1 \in H^{x_2}K, which is a group factorization.