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 $G$ equipped with an encoding $C$. An abstract subgroup $H$ of $G$.

Definition part

A coset-separating function for $H$ in $G$ is a description of the map $G\to G/H$ (viz the map that sends each element in $G$ to its right coset). More specifically, let $X=G/H$. Then a coset-separating function is the following:

• An encoding of the elements of $X$ as words over some finite alphabet
• An algorithm that takes as input (the encoding of) an element $g\in G$ and outputs (the encoding of) its right coset with respect to $H$ (as an element of $X$).

Another way of looking at it is that we describe algorithmically a function $f:G\to X$ whose fibres are the right cosets of $H$ in $G$.

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 $(H,f)$ where $H$ is a subgroup of $G$ and $f$ is a coset-separating function for $H$ in $G$ (we assume $K=G$).

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 $H_{1}$ and $H_{2}$ with coset-separating functions $f_{1}$ and $f_{2}$, we can obtain a coset-separating function for $H_{1}\cap H_{2}$. This is simply $f_{1}\times f_{2}$, viz $g\mapsto (f_{1}(g),f_{2}(g))$.

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 $H$ in $K$ and for $K$ in $G$, we can naturally obtain a coset-separating function for $H$ in $G$.

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

Transfer operator

Template:Transfer-closed sdr A coset-separating function $f$ for $H$ in $G$ gives rise to a coset-separating function for $H\cap K$ in $K$. The idea is simply to restrict the function $f$ to $K$.