# 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*

## Contents

## Description

### Given data

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

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

### Goal

We are required to determine whether is maximal in , or equivalently, whether the action of on the coset space 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`