Maximality testing problem

This article describes the subgroup property testing problem for the subgroup property: {{{property}}}Property "Specific information about" (as page type) with input value "{{{property}}}" contains invalid characters or is incomplete and therefore can cause unexpected results during a query or annotation process.
View other subgroup property testing problems

This article describes a problem in the setup where the group(s) involved is/are defined by means of an embedding in a suitable universe group (such as a linear or a permutation group) -- viz in terms of generators described as elements sitting inside this universe group

Description

Given data

Our universe is some group $U$ (such as a linear group or a permutation group) in which products and inverses can be readily computed.

A group $G$ in $U$ is specified by a generating set $A$, and a subgroup $H$ of $G$ is specified by a generating set $B$. (We are given a guarantee that $H$ is a subgroup of $G$, if not, we can test it using the algorithm for the subgroup testing problem).

Goal

We are required to determine whether $H$ is maximal in $G$, or equivalently, whether the action of $G$ on the coset space $G/H$ is a primitive group action.

Solution

There is in fact an algorithm that will do either of the following things:

• If the subgroup is indeed maximal, it will output that the subgroup is maximal
• Otherwise, it will output a subgroup that is minimal with respect to the property of strictly containing the given subgroup

This algorithm clearly also solves the maximality testing problem.

Further information: minimal block-finding problem