# Coset-separating function

*This article defines a subgroup description rule, viz a rule that allows us to describe subgroups of a group in terms of encodings of the whole group*

## Definition

### Setup

A group equipped with an encoding . An abstract subgroup of .

### Definition part

A **coset-separating function** for in is a description of the map (viz the map that sends each element in to its right coset). More specifically, let . Then a coset-separating function is the following:

- An encoding of the elements of as words over some finite alphabet
- An algorithm that takes as input (the encoding of) an element and outputs (the encoding of) its right coset with respect to (as an element of ).

Another way of looking at it is that we describe algorithmically a function whose fibres are the right cosets of in .

### Analogue for multi-encoding

The notion of a coset-separating function also makes sense for a multi-encoding. In fact, many known algorithms for the hidden subgroup problem start off with a coset-separating function corresponding to a multi-encoding which is particularly convenient for performing operations like a Fourier transform (for instance, one where the number of elements is a power of 2).

## Relation with other descriptions

### Weaker descriptions

- Membership test: Any coset-separating function gives a membership test. To check whether an element lies in the subgroup, we simply need to evaluate the coset-separating function at that element and compare with the value at the identity element.

### Stronger descriptions

- Coset enumeration: A coset enumeration trivially gives a coset-separating function by simply concentrating on the effect of the group action on the identity coset

### Relation with generating set

The problem of finding a generating set for a subgroup described by a coset-separating function is termed the hidden subgroup problem. The origin of the terminology is the fact that we can view the coset-separating function as *hiding* the subgroup.

## Effect of subgroup operators

We are interested in pairs where is a subgroup of and is a coset-separating function for in (we assume ).

### Intersection of subgroups

*This subgroup description rule is intersection-closed, viz a description of the subgroups can be used to obtain a description of their intersection*

Given two subgroups and with coset-separating functions and , we can obtain a coset-separating function for . This is simply , viz .

Note that this new coset-separating function can be both described and obtained in time polynomial in the two original coset-separating functions and the code-lengths, hence this subgroup description rule is intersection-closed.

### Composition operator

It is not very clear whether, given a coset-separating function for in and for in , we can naturally obtain a coset-separating function for in .

The problem is that while we can separate those cosets of which lie strictly inside , its rather hard to find this function that separates the cosets of outside in an *a priori* fashion.

### Transfer operator

Template:Transfer-closed sdr A coset-separating function for in gives rise to a coset-separating function for in . The idea is simply to restrict the function to .