Black-box group algorithm for small generating set-finding problem

From Groupprops
Jump to: navigation, search

Summary

Item Value
Problem being solved small generating set-finding problem for black-box groups: given an encoding of a group of order N, find a generating set for the group of size at most \log_2 N.
Max-length version: it finds a generating set whose size is at most the max-length of the group.
Minimal generating set version: we can make sure we output a minimal generating set (this need not be a minimum size generating set, but has the property that no proper subset of it is a generating set for the whole group.
Input format An encoding of a group G where G is a finite group (i.e., G is to be treated as a black-box group).
Output format A subset of G, given as a list of encodings of elements.
Guaranteed (general) properties of output generating set As noted, it is a generating set
If using the untweaked version, then size at most the max-length of the group.
If using the tweaked version, then size at most the maximum size of minimal generating set for the group.
Mode of input processing Makes queries to the black-box group operations throughout the algorithm.
Competing algorithms Black-box group algorithm for minimum size generating set-finding problem
Running time Max-length version: If the order of the group is N, and the max-length is \ell, then (O(N\ell^2) times the time taken for group operations), plus the time taken for enumeration of all elements of the group. Note that \ell \le \log_2N, so this is (O(N\log_2^2N) times the time for group operations), plus the time taken for enumeration of all elements of the group.
Minimal generating set version: If the order of the group is N, and the max-length is \ell, then O(N\ell^2) times the time taken for group operations, plus the time taken for enumeration of all elements of the group. Note that \ell \le \log_2N, so this is O(N\log_2^2N) times the time taken for group operations. Note that even though the final size of generating set is bounded by maximum size of minimal generating set, intermediate choices of the set may be bigger.
In particular, with the log-size assumption, i.e., if we assume that all the group operations take polylog time, then the time taken is O(N\operatorname{polylog}N).

Groups for which this gives a generating set of minimum size

A group with fixed size of minimal generating set is a group with the property that all its minimal generating sets have the same size. For a finite group with this property, the minimum size of generating set equals the size of any minimal generating set, and thus, any minimal generating set has minimum size. In particular, for such groups, the minimal generating set version of the algorithm outputs a generating set of minimum size.

Any group of prime power order is a group with fixed size of minimal generating set, and in fact the minimum size of generating set equals the dimension of the Frattini quotient as a vector space over the prime field. For more, see Burnside's basis theorem. Thus, the minimal generating set version of the algorithm here outputs a generating set of minimum size if the group is a group of prime power order.

Idea and outline

Max-length version

The idea is as follows: we construct the generating set by adding one element at a time, and we keep proceeding until the subset generates the whole group. Denote by S_i the set :

Step What we do
initialization (zeroth step) Set S_0 to be the empty subset of G.
i^{th} step (starts i = 1) Use the black-box group algorithm for finding the subgroup generated by a subset to find the subgroup generated by S_{i-1}. If this is the whole of G, then quit the loop. Otherwise, find x outside the subgroup and set S_i = S_{i-1} \cup \{ x \}.
after quitting the loop The value of S_{i-1} at the time of quitting the loop is the generating set we desire.

Every time we add an element, the subgroup generated becomes strictly bigger. In other words, the inclusions of subgroups:

\langle S_0 \rangle < \langle S_1 \rangle < \dots

are all strict inclusions as long as we are within the group. The length of this chain of subgroups is at most equal to the max-length of the group. Thus, the number of elements we need to add to get to the whole group is at most equal to the max-length of the whole group. Further, it is possible to make a series of choices of elements corresponding to a chain of subgroups of maximum length, so the max-length bound is a tight bound.

We now compute the running time. The running time at step i is O(Ni) times the time taken for group operations. The worst case total time is thus O(N(1 + 2 + \dots + \ell)) times the time for group operations, where \ell denotes the max-length of the group. This is O(N\ell^2) times the time taken for group operations.

Minimal generating set version

This is similar to the previous algorithm, with the following slight modification: at the end, we check for every element whether it can be removed from the generating set for the group we have obtained. This is done through a sequential traversal of the elements. This takes additional time of O(N\ell^2) times the time for group operations, and does not affect the total time taken.

We could also remove redundant elements from the generating set while building the generating set. However, redundancy needs to be checked at the end again anyway, so this does not yield an improvement as far as the big-oh notation is concerned.