Generating set (subgroup description)

This article defines a subgroup description rule, viz a rule that allows us to describe subgroups of a group in terms of encodings of the whole group

Description

Setup

Let $G$ be a group with an encoding $C$. That is, $C$ associates to each element of $G$ a string over a fixed (say, binary) alphabet, along with algorithms for testing validity of a code-word, for multiplying group elements, and for finding the inverse of a group element.

Let $H\leq G$ be an abstract subgroup.

Definition part

A generating set for $H$ in $G$ is a collection of code-words for elements in $G$ such that the subgroup generated by them is precisely $H$.

We tyipcally make smallness assumptions on the size of the generating set; for instance, the generating set should be at most logarithmic in the size of the group. As we shall note below, these smallness assumptions are not unjustified.

Relation with other subgroup description rules

Weaker subgroup description rules

• Element enumeration