Randomized black-box group algorithm for normality testing has false positive rate of at most three-fourths
Then we have:
In other words, the probability that a randomly selected pair from is in is at most .
The fact has applications for the normality testing problem, and forms the basis of the randomized black-box group algorithm for normality testing.
- Subgroup of size more than half is whole group
- Commuting fraction more than five-eighths implies abelian plays a similar role for the abelianness testing problem as this fact plays for the normality testing problem
- Commuting fraction more than half implies nilpotent
Given: A finite group , subgroup that is not normal in .
|Step no.||Assertion/construction||Facts used||Given data used||Previous steps used||Explanation|
|1||Let be the set of elements in that do not normalize . Then, .||Fact (1)||is not normal in , is finite||The normalizer is a subgroup of . Since is not normal, it is a proper subgroup of . Hence, by Fact (1), it has size at most half the size of . Therefore, its complement, , has size at least half the size of .|
|2||For , let be the set of elements such that . Then, .||Fact (1)||Step (1)||Since does not normalize , we have that is not contained in . Thus, is a proper subgroup of . By Fact (1), it has size at most half the size of . Therefore, its complement in , which is , has size at least half the size of .|
|3||Steps (1), (2)||Direct combination of steps|
|4||Steps (1), (2), (3)||The complement of in is precisely the set of pairs where and . By Step (3), the number of such pairs is at least , so the size of the complement is at most .|