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

subgroupif the following hold:

- ;
- if , then ;
- 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 : *

*Find a subset of some group G which satisfies conditions 1 & 3 but not 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

subgroupif the following hold:

- ;
- if , then .

## Examples

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

**Z**has subgroups*m***Z**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.**Q**has subgroup**Z**.**Q*** has subgroups**Q***^{2}<**Q**^{>0}<**Q**, where**Q***^{2}is the set of rational squares and**Q**^{>0}is the set of positive rational numbers.**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}.

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

- If
*m*≤*n*, we can think of*S*as a subgroup of_{m}*S*, if we let_{n}*f*(*x*) =*x*for . - In the case of
*A*_{4}, 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). - 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. - 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. - 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.

**Intersections**are ok. In order words if we have a collection {*H*} of subgroups of of_{i}*G*, then the intersection ∩*H*is also a subgroup. The proof is easy so we’ll skip it._{i}**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*

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

*p*, where

^{r}*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 ofxsuch that , wherep>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 3*k*, where*k*= (*p*-1)/3. If we pick a generator*g*mod*p*, then {1,*g*,*g*^{2}} 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 integern, 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*

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