Randomized black-box group algorithm for normality testing

From Groupprops
Jump to: navigation, search

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.