Subgroup description rule

Description

A subgroup description rule is a rule that takes as input a group, an encoding of the group, and an abstract subgroup of the group, and outputs a collection of descriptions (each description being some string) such that:

• Every subgroup has at least one description as per the rule
• Every description corresponds to at most one subgroup
• We can construct a machine that takes as input a description of the subgroup, and outputs all the elements of the subgroup. Similarly, we can construct a machine that takes as input all the elements of the subgroup, and constructs the set of all possible descriptions as per that rule.

For examples, refer subgroup descriptions.

Properties of subgroup description rules

Note that for every property that we describe for a subgroup description rule, we can also consider the corresponding property with reference to only particular kinds of groups and their encodings.

Log-size subgroup description rule

A subgroup description rule is said to be log-size if whenever we have a log-size encoding of the whole group, every subgroup of the group possesses a description satisfying the rule, with there being a uniform bound which is polynomial in the logarithm. For instance, the generating set gives a log-size description rule because every subgroup has a generating set of logarithmic size, and each generator in turn requires logarithmic space to store.

Log-trimmable subgroup description rule

A subgroup description rule is said to be 'log-trimmable if whenever we have a log-size encoding of the whole group, then, given any subgroup of the group and a description of the subgroup as per the subgroup description rule, we can obtain another description as per the rule whose size is bounded by some (uniformly determined) polynomial in the logarithm, using an algorithm whose running time is polynomial in the size of the original description and the logarithm of the size of the group.

Intersection-closed subgroup description rule

Further information: Intersection-closed subgroup description rule

A subgroup description rule is said to be intersection-closed if given the descriptions of any two subgroups as per the subgroup description, we can output a description for their intersection such that:

• The size of the description for their intersection is bounded by a polynomial in their sizes and the log-size.
• The time taken by the algorithm to output this description is again bounded by a polynomial in their sizes and the log-size

Closure with respect to any subgroup operator

More generally, given any subgroup operator, the subgroup description rule is said to be closed with respect to that operator if:

• The size of the subgroup description for the output subgroup is bounded by a uniformly chosen polynomial in the sizes of the input subgroups and the log-size
• The time taken for the algorithm to output this subgroup description is also bounded by a uniformly chosen polynomial in the sizes of the input subgroups and the log-size

Thus, we can talk of a:

• transitive subgroup description rule: This notion makes sense for any subgroup description rule that is stronger than a membership test. The idea is that given $H\leq K\leq G$ and a subgroup description of $H$ relative to $K$ and a subgroup description of $K$ relative to $G$, we can obtain a subgroup description of $H$ relative to $G$
• normal core-closed subgroup description rule: This means that given the subgroup description for a subgroup as per the rule, we can output a subgroup description for its normal core as per the rule.