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
Template:Group description rule
Contents
Definition
Basic definition
Let be a group. An encoding of 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 (possibly equal, possibly distinct elements) | codeword for |
inverse map | codeword for | codeword for |
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, must be either finite or countable. If is a finite group, then a simple counting tells us that we will have codewords of size at least . If the maximum length of a codeword is something around , 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 to the number of valid codewords of length upto . We can then study the rate at which this function grows. If the function grows exponentially in , 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 be an IAPS of groups. In other words, for each natural number , we have a group , and for every ordered pair of natural numbers, we have an injective homomorphism .
An encoding of this IAPS gives an encoding of each along with an algorithm that can take as input an encoding of a word and a word for , outputs the code for .
We have the following terminology:
- A dense encoding of an IAPS of groups is an encoding where the maximum code length for is logarithmic in the size of .
- A polynomial-time encoding of an IAPS of groups is an encoding where the time taken for all the operations on is bounded by a polynomial in the maximum code length for elements in , and the map is computable in time polynomial in . (That is, the polynomial is independent of ).
Interestingly, for the permutation IAPS and the general linear IAPS, we have dense polynomial-time encodings. Check out:
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 . Then we automatically have an encoding for any subgroup of , by resticting the encoding map from to , provided that we have a membership test for in .
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 (that is, much bigger than logarithmic)
- Thus, the times required to multiply elements may also be very large with respect to size of (that is, much bigger than polylogarithmic) and hence this encoding may not be efficient for .
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 . Then, what can we say about a group where is a normal subgroup of ? One way is that, for each element of , we pick a coset representative of 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 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 .
- 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 , 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 is a normal subgroup and is the quotient group. Then, we can try obtaining an encoding of using encodings of and , and a coset representative function for in . The idea is to store, for any , the ordered pair where is the element of via the quotient map and is the ratio between 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^{Weblink}^{More info}
- A polyomial-time theory of black-box groups I by Laszlo Babai and Robert Beals, : ^{Ungated copy (PDF)}^{More info}