Randomized black-box group algorithm for normality testing

Summary

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$ given by means of an encoding. A subgroup $H$ of $G$. A membership test for $H$ in $G$. An algorithm to sample uniformly at random from $G$ (possibly also an algorithm to sample uniformly at random from $H$).
Output format	Maybe/no with Maybe indicating that the subgroup may be normal (but we're not sure) and No indicating that the subgroup is not normal (along with an explicit choice of $g\in G$ and $h\in H$ such that $ghg^{-1}\notin H$.
Running time	Assuming we have random oracles for both $G$ and $H$: (Order of the time taken for random element generation) + (Order of the time taken for group operations) + (Order of the time taken for the membership test in $H$).

Idea and outline

Assuming random oracles for both the group and the subgroup

• Use the random oracle for $G$ to pick an element $g\in G$ uniformly at random.
• Use the random oracle for $H$ to pick an element $h\in H$ uniformly at random.
• Use the membership test to determine whether the element $ghg^{-1}$ is an element of $H$. If No, declare the answer to be No and output $g,h$ as proof. If Yes, then this particular choice did not disprove the hypothesis of normality.

If $H$ is not normal in $G$, the probability that the test would show Yes for $H$ is at most $3/4$ (for a proof, see randomized black-box group algorithm for normality testing has false positive rate of at most three-fourths). Thus, if we run the test $k$ times, the probability of getting a false "Yes" each time is at most $(3/4)^{k}$. We can thus obtain an arbitrarily high degree of certainty.

Assuming a random oracle only for the group

If $H$ has index at most $d$ in $G$, we can simulate the random oracle in $H$ using a random oracle in $G$ as follows: use the oracle in $G$ along with the membership test in $H$ to generate the random element of $H$ with probability at least $1/d$ per attempt, and keep repeating the attempts until you get an element of $H$.