## 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. $e\in H$;
2. if $x \in H$, then $x^{-1} \in H$;
3. if $x, y \in H$, then $x*y \in H$.

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 $x \in H$, and by third axiom, $x^{-1} \in H$, so by first axiom, we get $e = x*x^{-1} \in H$. 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. $H \ne \emptyset$;
2. if $x,y \in H$, then $xy^{-1} \in H$.

## 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*2Q>0Q, where Q*2 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 $m = 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19$.

Next, the non-abelian cases.

1. If m ≤ n, we can think of Sm as a subgroup of Sn, if we let f(x) = x for $f\in S_m, x>m$.
2. In the case of A4, 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 SR comprising of all bijections R → R, the affine transformations f(x) = ax+b, (for ab in R) form a subgroup.
5. In GLn(R), the subset of matrices of determinant 1 forms a subgroup SLn(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 { Hi } of subgroups of of G, then the intersection ∩ Hi 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:

$\left = \bigcap \{ H : H \supset S, H \le G\}$.

Thus, one often says that $\left$ 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 $\left$ for short. Then clearly this subgroup comprises of all powers of g : i.e. $\ldots g^{-2}, g^{-1}, e, g, g^2, \ldots$. If g is infinite, then so is this subgroup; otherwise, the order is precisely the smallest positive m for which $g^m = e$In short, the order of the subgroup generated by g is the order of g.
2. Suppose S = {xy}. Things become much trickier: now $\left$ contains all products of the form: $e, x, y, xy, x^{-1}y, \ldots, x^{-1}y^2 x y^{-3},\ldots$. 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 $R, R^{-1}, L, L^{-1}, U, U^{-1}, D, D^{-1}, F, F^{-1}, B, B^{-1}$ 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 $\left$?

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 $G = \left$ 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 gxy 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, pr or 2pr, 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 $x^3 \equiv 1 \pmod p$, 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 $p \equiv 1, 2 \pmod 3$.

• If $p\equiv 1 \pmod 3$, (Z/3)* is cyclic of order 3k, where k = (p-1)/3. If we pick a generator g mod p, then {1, gg2} are the only possible solutions for $x^3 \equiv 1 \pmod p$.
• If $p\equiv 2 \pmod 3$, 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 $1, 2^6 = 7, 2^{12} = 11$. 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 $\sum_{d|n, d>0} \phi(d) = n$, where $\phi(m)$ 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 $\phi(d)$ generators as we saw above. Thus the result follows.

Exercises

1. Let p>2 be prime. Find the number of solutions to $x^2 \equiv -1 \pmod p$. [ Hint: consider 1 (mod 4) and 3 (mod 4). ]
2. Find the number of solutions to $x^3 \equiv 1 \pmod m$, where
• m = 5 × 7 × 11 × 17 × 19 × 29;
• m = 52 × 73.
This entry was posted in Notes and tagged , , , , , , . Bookmark the permalink.