Coset-separating function

From Groupprops
Jump to: navigation, search

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.