Maximality testing problem

From Groupprops
Jump to: navigation, search
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