Coset intersection problem: Difference between revisions

Revision as of 15:56, 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

History

The coset intersection 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 coset intersection 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 $x$ in $G$ is given (described as an element of $U$ ).

Goal

Determine whether $H x$ intersects $K$ .

Relation with other problems

Equivalent decision problems

Group factorization problem: This asks whether $x \in H K$ . The group factorization problem is clearly equivalent to the coset intersection problem, because $x \in H K ⟺ H x \cap K$ is nonempty.
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$ .

Clearly, the coset intersection problem reduces to the double coset membership problem, because asking if $H x \cap K$ is nonempty is the same as asking whether the double coset $H K$ contains $x$ .

@@ Line 23: / Line 23: @@
 ===Equivalent decision problems===
-* [[Group factorization problem]]: This asks whether <math>x \in HK</math>. The group factorization problem is clearly equivalent to the coset intersection problem, because <math>x in HK \iff Hx \cap K</math> is nonempty.
+* [[Group factorization problem]]: This asks whether <math>x \in HK</math>. The group factorization problem is clearly equivalent to the coset intersection problem, because <math>x \in HK \iff Hx \cap K</math> is nonempty.
 * [[Double coset membership testing problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets, and elements <math>g</math> and <math>h</math> are given. We need to check whether <math>h</math> is in <math>HgK</math>.
 Clearly, the coset intersection problem reduces to the double coset membership problem, because asking if <math>Hx \cap K</math> is nonempty is the same as asking whether the double coset <math>HK</math> contains <math>x</math>.