Encoding of a group

This term is related to: computational group theory
View other terms related to computational group theory | View facts related to computational group theory

Definition

Basic definition

Let $G$ be a group. An encoding of $G$ over a binary alphabet (or equivalently, over any constant-sized alphabet) is 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 codeword for that element of the group. The following algorithms are provided:

Shorthand for algorithm	Input	Output
identity element	--	the codeword for the identity element
group multiplication	codewords for elements $g,h \in G$ (possibly equal, possibly distinct elements)	codeword for $gh$
inverse map	codeword for $g \in G$	codeword for $g^{-1}$
membership testing	any word	yes/no depending on whether it is the codeword for an element of the group.

If we allow for multi-valued functions (that is, multiple possible code-words for the same group element) but also put in an equality test for checking whether two codewords represent the same group element, we get what is called a multi-encoding of a group.

If we remove the condition of having an algorithm that outputs whether or not any given word is a valid codeword, we get what is called a quasi-encoding of a group.

What we are given computationally

Computationally, all that we are given are the four algorithms above. We are not given the group or the injective map explicitly.

An encoding of a group is a group description rule because it fixes the isomorphism type of the group uniquely, viz., given an encoding, any two groups having that encoding are isomorphic and this isomorphism essentially preserves the corresponding code-word.

Other common algorithms

Depending on the nature of the encoding, we may desire that there be explicit algorithms for the following in the case that we are encoding a finite group:

Shorthand for algorithm	Input	Output	How it could be achieved from the four basic algorithms
list all group elements (also called an enumeration algorithm)	--	list of all the elements of the group	This works if we know the maximum possible codeword length: list all the possible codewords (this is exponential in terms of the maximum possible codeword length). For each of these, do a membership test to determine if it is in the group.
order of the whole group	--	a number that equals the order of the group
uniform random sampling from the whole group		outputs an element picked uniformly at random from the group	This works if we know the maximum possible length for coded words: pick uniformly at random from all codewords of length up to the maximum. Do a membership test to check if this gives an element of the group. If yes, that's the element. Otherwise, pick randomly again.
algorithm for the power computation problem: computing a given power of a given element	element of the group, integer	outputs codeword for the power of that element	repeated squaring algorithm for power computation problem
algorithm for the element order-finding problem: computing the order of an element	element of the group	order of that element as a nonnegative integer	brute-force black-box group algorithm for element order-finding problem, square root-based black-box group algorithm for element order-finding problem

Properties

Properties of the injective map

Clearly, $G$ must be either finite or countable. If $G$ is a finite group, then a simple counting tells us that we will have codewords of size at least $\log (|G|)$. If the maximum length of a codeword is something around $\log (|G|)$, then we are in very good shape.

For countable groups, we cannot talk of the maximum length among all valid codewords. However, we can consider the growth function of the code, viz the function that sends $n$ to the number of valid codewords of length upto $n$. We can then study the rate at which this function grows. If the function grows exponentially in $n$, then we are in very good shape.

Properties of the algorithms

We say that the encoding is a:

• finite-time encoding if all the algorithms (the one to compute product, inverse and test membership) terminate in finite time
• bounded-time encoding if there is a uniform bound on the time taken for all algorithms (The one to compute product, inverse, and test membership)
• log-size encoding if the maximum possible length of a code-word is bounded by a constant times the logarithm of the order of the group, and all the algorithms are polynomial in this maximum possible length of a code-word

Particular encodings

Encoding of an IAPS of groups

BEWARE! This section of the article uses terminology local to the wiki, possibly without giving a full explanation of the terminology used (though efforts have been made to clarify terminology as much as possible within the particular context)

Further information: Encoding of an IAPS of groups

Let $(G,\Phi)$ be an IAPS of groups. In other words, for each natural number $n$, we have a group $G_n$, and for every ordered pair $(m,n)$ of natural numbers, we have an injective homomorphism $\Phi_{m,n}: G_m \times G_n \to G_{m+n}$.

An encoding of this IAPS gives an encoding of each $G_m$ along with an algorithm that can take as input an encoding of a word $g \in G_m$ and a word for $G_n$, outputs the code for $\Phi_{m,n}(g,h)$.

We have the following terminology:

• A dense encoding of an IAPS of groups is an encoding where the maximum code length for $G_n$ is logarithmic in the size of $G_n$.
• A polynomial-time encoding of an IAPS of groups is an encoding where the time taken for all the operations on $G_n$ is bounded by a polynomial in the maximum code length for elements in $G_n$, and the map $\phi_{m,n}$ is computable in time polynomial in $(m+n)$. (That is, the polynomial is independent of $n$).

Interestingly, for the permutation IAPS and the general linear IAPS, we have dense polynomial-time encodings. Check out:

• Encoding of symmetric groups
• Encoding of general linear groups

Encoding of free groups

Consider a finitely generated free group with a generating set. Then, every element in the free group can be expressed uniquely as a reduced word in the generators and their inverses, and this describes an encoding over the alphabet comprising the free generators and their inverses.

In this encoding, the multiplication operation is simply word concatenation, followed by reducing the word.

Checking whether a word is reduced is also easy -- simply check whether an element and its inverse ever occur as consecutive letters.

Further information: Encoding of free groups

Subgroup and quotient descriptions in terms of group encoding

Subgroup descriptions

Further information: Subgroup descriptions

Let us say we have an encoding of a group $G$. Then we automatically have an encoding for any subgroup $H$ of $G$, by resticting the encoding map from $G$ to $H$, provided that we have a membership test for $H$ in $G$.

However, we need to keep in mind the following:

• The maximum possible length of a codeword may be very large with respect to the size of $H$ (that is, much bigger than logarithmic)
• Thus, the times required to multiply elements may also be very large with respect to size of $H$ (that is, much bigger than polylogarithmic) and hence this encoding may not be efficient for $H$.

As an alternative to using a membership test to describe the subgroup, we may also use a generating set for it, where the elements of the generating set are described by their code-words for the encoding of the bigger group.

Both the generating set and the membership test description are closely related.

Quotient descriptions

Further information: Quotient descriptions

Let us say we have an encoding of a group $G$. Then, what can we say about a group $G/N$ where $N$ is a normal subgroup of $G$? One way is that, for each element of $G/N$, we pick a coset representative of $G/N$ and consider the code for that. The problem is that different coset representatives can give different code-words.

• One way is to associate to each coset the set of code-words for all the elements in that coset. We thus get a multi-map from the set $G/N$ to the set of strings. For this to be a multi-encoding we need to be able to check, by looking at the code-words for two elements, whether they come from the same coset. This reduces to finding a membership test for the normal subgroup $N$.

• Another way is to make a natural choice of representative for each coset, in such a way that: Given the code words for the coset representatives of two elements of $G/N$, we can find the coset representative for their product (that is, we can reduce their product to the normal form).

On a related note, a presentation of a group is a description of that group as a quotient of a free group, and we may be interested in trying to use that presentation to obtain an encoding of the quotient.

Encoding direct products and extensions

Encoding the direct product

It is possible to encode the direct product of two groups, in terms of the encodings of the two groups. The idea is to simply, using some extra symbols, encode elements of the direct products as ordered pairs over elements from the first group and elements from the second group, in such a way that each of the components can be retrieved from the direct product in a linear pass. Then, we can perform the operations on the direct product by retrieving the coordinates, performing the operations coordinate-wise, and then stringing together the outcomes.

Encoding an extension

Suppose $N \triangleleft G$ is a normal subgroup and $H = G/N$ is the quotient group. Then, we can try obtaining an encoding of $G$ using encodings of $N$ and $H$, and a coset representative function for $N$ in $G$. The idea is to store, for any $g \in G$, the ordered pair $(n,h)$ where $h$ is the element of $H$ via the quotient map and $n$ is the ratio between $g$ and its coset representative.

History

Origin

This term was introduced by: Babai

This term was introduced by: Szemeredi

The notion of encoding of a group was introduced by Babai and Szemeredi in their paper On the complexity of matrix group problems. It is closely related to the notion of black-box group.

However, the definition and exact details as presented in the wiki are somewhat different from the way the notions are described and developed in the paper.

References

• On the complexity of matrix group problems, I by Laszlo Babai and Endre Szemeredi, Foundations of Computer Science, 1984. 25th Annual Symposium on Volume , Issue , 24-26 Oct 1984 Page(s): 229 - 240^{WeblinkMore info}
• A polyomial-time theory of black-box groups I by Laszlo Babai and Robert Beals,  : ^{Ungated copy (PDF)More info}

External links

• IEEXplore link for On the complexity of matrix group problems by Babai and Szemeredi