# Randomized black-box group algorithm for normality testing has false positive rate of at most three-fourths

From Groupprops

## Statement

Suppose is a finite group and is a subgroup of that is *not* normal in . In other words, there exist and such that . Then, suppose is the set:

Then we have:

In other words, the probability that a randomly selected pair from is in is at most .

## Related facts

### Applications

The fact has applications for the normality testing problem, and forms the basis of the randomized black-box group algorithm for normality testing.

### Similar facts

- 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

## Facts used

- Lagrange's theorem in the special form subgroup of size more than half is whole group

## Proof

**Given**: A finite group , subgroup that is not normal in .

**To prove**:

**Proof**:

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 . |