Element enumeration

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

Definition

Setup

A group $G$ equipped with an encoding $C$. An abstract subgroup $H$ of $G$.

Definition part

An element enumeration for $H$ is an algorithm that outputs a sequence of elements of $G$ such that:

• Every element in the sequence lies inside $H$
• The sequence contains every element of $H$

Note that because of repetitions of elements, the enumeration may itself be much longer and take more time to compute than the size of $H$.

Relation with other subgroup description rules

Stronger subgroup description rules

• generating set gives an element enumeration if we consider all the generators, all the products of length two of generators and so on.
• Membership test uses an element enumeration of the whole group to obtain an element enumeration of the subgroup, by filtering in only those elements which are in the subgroup