Membership test-based black-box group algorithm for normality testing

From Groupprops
Jump to: navigation, search


Item Value
Problem being solved normality testing problem: test whether a given subgroup of a given group is normal
Input format A finite group G with an encoding, a subgroup H of G specified by a membership test
Assume it is possible to enumerate all elements of G
Output format Yes/No depending on whether H is normal in G
Optionally, if the subgroup is not normal, elements g \in G, h \in H such that ghg^{-1} \notin H.
Running time (Time taken for enumeration of all group elements)+ (Time taken to do membership test on all group elements) + (O(N \log_2^2N) \times (Time for group operations))

Idea and outline

The idea is to first use the black-box group algorithm for small generating set-finding problem to separately compute small generating sets for G,H. Note that for H, we can enumerate all elements by first enumerating all elements of G and then filtering the set using the membership test for H.

Once we have small generating sets for both, we can use the generating set-cum-membership test-based black-box group algorithm for normality testing. Note that the actual normality testing takes negligible time compared to the time spent computing the generating sets.