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

From Groupprops
Jump to: navigation, search

Statement

Suppose G is a finite group and H is a subgroup of G that is not normal in G. In other words, there exist g \in G and h \in H such that ghg^{-1} \notin H. Then, suppose C is the set:

C = \{(g,h) \mid g \in G, h \in H, ghg^{-1} \in H \}

Then we have:

\! |C| \le \frac{3}{4} |G||H|

In other words, the probability that a randomly selected pair from G \times H is in C is at most 3/4.

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

Facts used

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

Proof

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

C = \{(g,h) \mid g \in G, h \in H, ghg^{-1} \in H \}

To prove: |C| \le \frac{3}{4}|G||H|

Proof:

Step no. Assertion/construction Facts used Given data used Previous steps used Explanation
1 Let A be the set of elements in G that do not normalize H. Then, |A| \ge \frac{1}{2}|G|. Fact (1) H is not normal in G, G is finite The normalizer N_G(H) is a subgroup of G. Since H is not normal, it is a proper subgroup of G. Hence, by Fact (1), it has size at most half the size of G. Therefore, its complement, A, has size at least half the size of G.
2 For g \in A, let D(g) be the set of elements h \in H such that ghg^{-1} \notin H. Then, |D(g)| \ge \frac{1}{2}|H|. Fact (1) Step (1) Since g does not normalize H, we have that g^{-1}Hg is not contained in H. Thus, g^{-1}Hg \cap H is a proper subgroup of H. By Fact (1), it has size at most half the size of H. Therefore, its complement in H, which is D(g), has size at least half the size of H.
3 \sum_{g \in A} |D(g)| \ge \frac{1}{4} |G||H| Steps (1), (2) Direct combination of steps
4 |C| \le \frac{3}{4}|G||H| Steps (1), (2), (3) The complement of C in G \times H is precisely the set of pairs (g,h) where g \in A and h \in D(g). By Step (3), the number of such pairs is at least \frac{1}{4}|G||H|, so the size of the complement is at most \frac{3}{4}|G||H|.