Multi-encoding of a group: Difference between revisions

Latest revision as of 23:51, 7 May 2008

Definition

Basic definition

Let $G$ be a group. A multi-encoding of $G$ over a binary alphabet (or equivalently, over any constant-sized alphabet) is the following data:

A multivalued injective mapping from the group to the set of words in that alphabet. In other words, each element of the group is expressed as a word over the alphabet, in possibly more ways than one. This is called the code-word for that element of the group and the mapping itself is termed the encoding.
An algorithm that takes in codes for $g,h\in G$ and outputs one of the codes for $gh$ .
An algorithm that takes in one of the codes for $g\in G$ and outputs the code for $g^{-1}$ .
An algorithm that takes in any string and outputs whether or not it is a valid codeword (that is, whether it arises as the encoding of some group element). This is termed a membership test or a recognition algorithm.
An algorithm that takes as input two code-words and outputs whether they represent the same group element. This is called an equality test.

If the mapping is single-valued, viz every group element has a unique code-word, then we simply call it an encoding of the group.

Properties

Size of fibers

To measure the extent to which a multi-encoding is like an encoding, we look at the sizes of the image of every point. Ideally we want this size to be bounded by a small constant.

Relation of encoding and multi-encoding

Passing from a multi-encoding to an encoding

Further information: Obtaining an encoding from a multi-encoding

An encoding is obtained as a section of a multi-encoding if, for every group element, it simply picks one of the code-words for it. This code-word is called the representative code-word.

To make the encoding work, we need the following:

The section should be picked in such a way that we have an efficient algorithm to find the representative code-word for the product of two representative code-words (representative code-words may not in general be closed under multiplication)
The section should be picked in such a way that we have an efficient algorithm to find the representative code-word for the inverse of a representative code-word
There should be an algorithm to check whether a given code-word is representative.

Normal form to obtain equality test

PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]

There exists a rewriting system for which the elements (which already lie in the whole group) to which no rewrite can be applied are precisely the same as the representative code-words, and such that the reduction process using this rewriting system is confluent and finitely terminating for every element, with the termination time bounded as a polynomial function of the length of the original code-word

Any normal form encoding gives an equality test for the original multi-encoding -- simply

Subgroups and quotients

Subgroups

Given a group with a multi-encoding, any subgroup also gets the multi-encoding provided that we have a membership test for the subgroup inside the group.

We can also choose to describe the subgroup by means of its generating set.

Quotients

Given a group with a multi-encoding, we can obtain a multi-encoding for its quotient by a normal subgroup provided there is a membership test for that normal subgroup.

@@ Line 1: / Line 1: @@
+{{group description rule}}
 ==Definition==
@@ Line 5: / Line 7: @@
 * A multivalued injective mapping from the group to the set of words in that alphabet. In other words, each element of the group is expressed as a word over the alphabet, in possibly more ways than one. This is called the ''code-word'' for that element of the group and the mapping itself is termed the encoding.
-* An algorithm that takes in the codes for <math>g, h \in G</math> and outputs the code for <math>gh</math>.
+* An algorithm that takes in codes for <math>g, h \in G</math> and outputs one of the codes for <math>gh</math>.
-* An algorithm that takes in the code for <math>g \in G</math> and outputs the code for <math>g^{-1}</math>.
+* An algorithm that takes in one of the codes for <math>g \in G</math> and outputs the code for <math>g^{-1}</math>.
-* An algorithm that takes in any string and outputs whether or not it is a valid codeword (that is, whether it arises as the encoding of some group element).
+* An algorithm that takes in any string and outputs whether or not it is a valid codeword (that is, whether it arises as the encoding of some group element). This is termed a '''membership test''' or a '''recognition algorithm'''.
-* An algorithm that takes as unput two code-words and outputs whether they represent the same group element.
+* An algorithm that takes as input two code-words and outputs whether they represent the same group element. This is called an '''equality test'''.
 If the mapping is single-valued, viz every group element has a unique code-word, then we simply call it an [[encoding of a group|encoding]] of the group.