Randomized black-box group algorithm for normality testing
From Groupprops
Contents
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 given by means of an encoding. A subgroup of . A membership test for in . An algorithm to sample uniformly at random from (possibly also an algorithm to sample uniformly at random from ). |
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 and such that . |
Running time | Assuming we have random oracles for both and : (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 ). |
Idea and outline
Assuming random oracles for both the group and the subgroup
- Use the random oracle for to pick an element uniformly at random.
- Use the random oracle for to pick an element uniformly at random.
- Use the membership test to determine whether the element is an element of . If No, declare the answer to be No and output as proof. If Yes, then this particular choice did not disprove the hypothesis of normality.
If is not normal in , the probability that the test would show Yes for is at most (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 times, the probability of getting a false "Yes" each time is at most . We can thus obtain an arbitrarily high degree of certainty.
Assuming a random oracle only for the group
If has index at most in , we can simulate the random oracle in using a random oracle in as follows: use the oracle in along with the membership test in to generate the random element of with probability at least per attempt, and keep repeating the attempts until you get an element of .