Quasi-encoding of a group

Contents

BEWARE! This term is nonstandard and is being used locally within the wiki. [SHOW MORE]

Definition

Basic definition

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

• An 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. This is called the code for that element of the group.
• An algorithm that takes in the codes for $g, h \in G$ and outputs the code for $gh$.
• An algorithm that takes in the code for $g \in G$ and outputs the code for $g^{-1}$.

A quasi-encoding becomes an encoding if we further have an algorithm that takes as input a word in the language and outputs whether or not it is a valid code-word.

Properties

Subgroups

Any quasi-encoding of a group naturally gives a quasi-encoding of any subgroup. Namely, we simply restrict the encoding function (the injective map from the group to the language) to the subgroup.