Casual Introduction to Group Theory (3)

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<S\right> = \bigcap \{ H : H \supset S, H \le G\}.

Thus, one often says that \left<S\right> 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<g\right> 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 = eIn short, the order of the subgroup generated by g is the order of g.
  2. Suppose S = {xy}. Things become much trickier: now \left<x, y\right> 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<S\right>?

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<g\right> 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.
About these ads
This entry was posted in Notes and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s