Double coset membership testing problem

This article describes a basic decision problem in computational group theory

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 double coset membership testing 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 double coset membership testing problem and studied a whole class of problems 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. Elements $g$ and $h$ in $G$ are given (described as elements of $U$).

Goal

We are required to determine whether $h$ is in the double coset $HgK$, or equivalently, if $HgK = HhK$.

Because the goal can be formulated in terms of equality of double cosets, it is also termed the double coset equality problem.

Default

By default, when we refer to the membership testing problem, we refer to the membership testing problem in permutation groups, viz $U$ is the symmetric group on a finite set. For a study of the problem on linear groups, refer membership testing problem for linear groups.

In this problem, $G$ plays no particular role, and we might as well consider $H$ and $K$ directly as subgroups of $U$ and $g$, $h$ as elements of $U$.

Relation with other problems

Equivalent decision problems

• Group factorization problem: A priori, this is a special case of the double coset membership testing problem. The group factorization problem takes as input subgroups $H$ and $K$ (described by generating sets) and an element $h$ in $G$, and outputs whether $h$ is in $HK$. Clearly, the group factorization problem reduces to the double coset membership problem by setting $g$ as the identity element.

It also turns out that double coset membership testing reduces to group factorization. Template:Fill-proof

• Coset intersection problem: This is clearly equivalent to the group factorization problem. It takes as input two subgroups $H$ and $K$ and an element $g$ and asks whether $Hg$ ∩ $K$ is nonempty.

References

• Group-theoretic algorithms and graph isomorphism by C. Hoffmann, Lecture Notes in Computer Science No. 136, Springer, 1982
• Graph Isomorphism is Low for PP by Johannes Kobler, Uwe Schoning, and Jacobo Toran, Journal of Computational Complexity, 2, 1992, 301-310

External links

• PS file for the paper by Kobler, Schoning and Toran
• The complexity of NP-problems over finite groups (PS file)