# Double coset membership testing 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 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.