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
- 1 Definition
- 2 Relation with other descriptions
- 3 Effect of subgroup operators
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
- 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.
- 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
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.
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.
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 .