Quasi-encoding of a group

From Groupprops
Jump to: navigation, search
BEWARE! This term is nonstandard and is being used locally within the wiki. [SHOW MORE]


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.



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.