Subgroups

[ This article approximately corresponds to chapter III of the group theory blog. ]

Let G be a group under operation *. If H is a subset of G, we wish to turn H into a group by inheriting the operation from G. Clearly, associativity follows for free, so it only remains to check the following.

Definition. Let H be a subset of group G. We say H is a subgroup if the following hold:

1. ;
2. if , then ;
3. if , then .

When that happens, we write H ≤ G.

One can check that if H satisfies these 3 properties, then (H, *) inherits a group structure from (G, *).

Note: it would seem as if we can drop the second axiom; indeed, we can just pick , and by third axiom, , so by first axiom, we get . Thus, the second axiom follows from the first and third axioms and seems superfluous… or does it?

Actually, no: the empty set satisfies the first and third axioms but not the second. This causes a problem in the first line of proof since we can’t pick any element x from H. So the empty set is really the odd case out.

Exercise :

1. Find a subset of some group G which satisfies conditions 1 & 3 but not 2.
2. Prove that if G is finite, then conditions 1 & 3 imply 2.

Sometimes, it’s more convenient to replace the above three conditions by two:

Alternate Definition. Let H be a subset of group G. We say H is a subgroup if the following hold:

1. ;
2. if , then .

Examples

Let’s look at subgroups of the examples in the previous post.

1. Z has subgroups mZ for m>0, which is the set of multiples of m. Together with the trivial subgroup {0}, these are the only possible subgroups which can arise.
2. Q has subgroup Z.
3. Q* has subgroups Q*² < Q^>0 < Q, where Q*² is the set of rational squares and Q^>0 is the set of positive rational numbers.
4. Z/m has subgroup k·(Z/m) for any positive divisor k of m, of order m/k. E.g. when m=12, k=3, we have Z/12 = {0, 1, …, 11} under addition mod 12, and the subgroup is {0, 3, 6, 9}. 
   
5. The group (Z/m)* has subgroup comprising of the squares, e.g. if m = 21, then (Z/m)* = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20} under multiplication mod 12, and the subgroup is {1, 4, 16}.

Exercise : find the order of the subgroup of squares of (Z/m)*, where .

Next, the non-abelian cases.

1. If m ≤ n, we can think of S_m as a subgroup of S_n, if we let f(x) = x for .
2. In the case of A₄, we have a subgroup V = {e, (1,2)(3,4), (1,3)(2,4), (1,4)(2,3)} which is abelian and isomorphic to (Z/2) × (Z/2).
3. If G denotes the group of symmetries of a shape A, then the set of symmetries of A fixing a vertex (or an edge, or a face) forms a subgroup.
4. For the group S_R comprising of all bijections R → R, the affine transformations f(x) = ax+b, (for a, b in R) form a subgroup.
5. In GL_n(R), the subset of matrices of determinant 1 forms a subgroup SL_n(R).

Properties of Subgroups

Naturally we wonder if the usual operations on subsets carry over here.

1. Intersections are ok. In order words if we have a collection { H_i } of subgroups of of G, then the intersection ∩ H_i is also a subgroup. The proof is easy so we’ll skip it.
2. Unions are not ok. In fact, if the union of two subgroups is a subgroup, then one is contained in the other. This is not really important but a curious fact to know.

In particular, if we have any subset S of G, then we consider the class of all subgroups of G containing S. The intersection of all these subgroups is then a subgroup which contain S. We call this the subgroup of G generated by S and write:

.

Thus, one often says that is the smallest subgroup of G which contains S, even though the term “smallest” reminds one of cardinality but that’s not what we mean. Let’s look at two small examples.

Examples of Generated Subgroups

1. Suppose S = {g}. We just write it as for short. Then clearly this subgroup comprises of all powers of g : i.e. . If g is infinite, then so is this subgroup; otherwise, the order is precisely the smallest positive m for which . In short, the order of the subgroup generated by g is the order of g.
2. Suppose S = {x, y}. Things become much trickier: now contains all products of the form: . On the other hand, the set of all such products is clearly closed under multiplication and inverse. In short, the subgroup generated by {x, y} comprises of all word expressions in x, y and their inverses.

Application

For example, to express the group of transformations of the Rubik’s cube, one can consider the various moves which comprise of 90-degree rotations of the respective faces. Each such rotation can be written as a permutation of degree 54, so we get a set S of six such permutations. The question is: what do we know about ?

The Schreier-Sims algorithm is useful for answering such questions. For example, GAP implements this algorithm to compute the exact order of the group within a split second.

Cyclic Groups

Finally, we consider a group G such that for some element g. Thus, the group comprises of all powers of some fixed generator g. It’s (isomorphic to) either Z or Z/m. If we wish to pick a generator g of such a group, how many possible g are there?

• Z : clearly +1 or -1, so 2 possibilities;
• Z/m : we want g mod m such that gx = y always has a solution mod m, i.e. g is coprime to m. The number of such g is thus the Euler totient function φ(m).

So Z/m is cyclic. But what about (Z/m)*? It’s a classical result that this is cyclic iff m = 1, 2, 4, p^r or 2p^r, where p is an odd prime. For example:

• (Z/11)* is generated by 2 since the powers of 2 are 1, 2, 4, 8, 5, 10, 9, 7, 3, 6, then 1.
• (Z/18)* is generated by 5 since we get 1, 5, 7, 17, 13, 11, then 1.
• (Z/15)* is not cyclic since the subgroup {1, 4, 11, 14} is not cyclic. [ Every subgroup of a cyclic group must be cyclic. ]

Number Theoretic Applications

These elementary group theory concepts can cast a new light on classical number theory problems.

Example 1.  Find the number of x such that , where p>3 is a prime.

We already know that (Z/p)* is cyclic of order p-1. Now, since p can’t be divisible by 3, we have .

• If , (Z/3)* is cyclic of order 3k, where k = (p-1)/3. If we pick a generator g mod p, then {1, g, g²} are the only possible solutions for .
• If , then (Z/3)* is cyclic of order coprime to 3, so the only possible solution is x=1.

Let’s look at some concrete examples.

• p = 19: let’s pick generator 2. Since o(2) = 18, the solutions are . Check that if we had picked the generator 11, we’d still get the same solutions. 🙂
• p = 11: you can check by brute-force that x=1 is the only solution.

Example 2.  Prove that for any positive integer n, we have , where is the Euler-totient function above.

Consider the group Z/n, which is cyclic of order n. Each element g generates a cyclic subgroup of order d, where d divides n. On the other hand, if d|n, then Z/n has a unique subgroup of order d (since it comprises of all multiples of n/d). This subgroup has generators as we saw above. Thus the result follows.

Exercises

1. Let p>2 be prime. Find the number of solutions to . [ Hint: consider 1 (mod 4) and 3 (mod 4). ]
2. Find the number of solutions to , where
   • m = 5 × 7 × 11 × 17 × 19 × 29;
   • m = 5² × 7³.