Introduction to Group Theory

maximios

Imagine a square of paper lying flat on your desk. I ask you to close your eyes. You hear the paper shift. When you open your eyes the paper doesn’t appear to have changed. What could I have done to it while you weren’t looking?

It’s obvious that I haven’t rotated the paper by 30 degrees, because then the paper would look different.

I also did not flip it over across a line connecting, say, one of the corners to the midpoint of another edge. The paper would look different if I had.

What I could have done, however, was rotate the paper clockwise or counterclockwise by any multiple of 90 degrees, or flipped it across either of the diagonal lines or the horizontal and vertical lines.

Flipping across any dashed line will not change the square.

A helpful way to visualize the transformations is to mark the corners of the square.

The last option is that to do nothing. This is called the identity transformation. Together, these are all called the symmetry transformations of the square.

I can combine symmetry transformations to make other symmetry transformations. For example, two flips across the line segment BD produces the identity, as do four successive 90 degree counterclockwise rotations. A flip about the vertical line followed by a flip about the horizontal line has the safe effect as a 180 degree rotation. In general, any combination of symmetry transformations will produce a symmetry transformation. The following table gives the rules for composing symmetry transformations:

We use “e” for the identity transformation.

In this table, R with subscripts 90, 180, and 270 denote counterclockwise rotations by 90, 180, and 270 degrees, H means a flip about the horizontal line, V is a flip about the vertical line, MD is a flip about the diagonal from the top left to the bottom right, and OD means a flip over the other diagonal. To find the product of A and B, go to the row of A and then over to the column of B. For example, H∘MD=R₉₀.

There are a few things you may notice by looking at the table:

  • The operation ∘ is associative, meaning that A∘(B∘C) = (A∘B)∘C for any transformations A, B, and C.
  • For any pair of symmetry transformations A and B, the composition A∘B is also a symmetry transformation
  • There is one element e such that A∘e=e∘A for every A
  • For every symmetry transformation A, there is a unique symmetry transformation A⁻¹ such that A∘A⁻¹=A⁻¹∘A=e

We therefore say that the collection of symmetry transformations of a square, combined with composition, forms a mathematical structure called a group. This group is called D₄, the dihedral group for the square. These structures are the subject of this article.

Definition of a group

A group ⟨G,*⟩ is a set G with a rule * for combining any two elements in G that satisfies the group axioms:

  • Associativity: (a*b)*c = a*(b*c) for all a,b,c∈G
  • Closure: a*b∈G all a,b∈G
  • Unique identity: There is exactly one element e∈G such that a*e=e*a=a for all a∈G
  • Unique inverses: For each a∈G there is exactly one a⁻¹∈G for which a*a⁻¹=a⁻¹*a=e.

In the abstract we often suppress * and write a*b as ab and refer to * as multiplication.

An example of a group from everyday life is the set of “moves” that can be made on a Rubik’s cube under composition. Source.

It is not necessary for * to be commutative, meaning that a*b=b*a. You can see this by looking at the table of D₄, where H∘MD=R₉₀ but MD∘H=R₂₇₀. Groups where * is commutative are called abelian groups after Neils Abel.

Abelian groups are the exception rather than the rule. Another example of a non-abelian group is the symmetry transformations of a cube. Consider just rotations about the axes:

Source: Chegg

If I first rotate 90 degrees counterclockwise about the y-axis and then 90 degrees counterclockwise about the z-axis then his will have a different result than if I were to rotate 90 degrees about the z-axis and then 90 degrees about the y-axis.

Top row: Rotation 90 degrees about y followed by 90 degrees about z. Bottom row: 90 degree rotation about z followed by 90 degree rotation about y.

It is possible for an element to be its own inverse. Consider the group which consists of 0 and 1 with the operation of binary addition. Its table is:

Clearly 1 is its own inverse. This is also an abelian group. Don’t worry, most groups aren’t this boring.

Some more examples of groups include:

  • The set of integers with addition.
  • The set of rational numbers not including 0 with multiplication.
  • The set of solutions to the polynomial equation xⁿ-1=0, called the nth roots of unity, with multiplication.

The 5th roots of unity, which solve x⁵-1=0

Here are some examples that are not groups:

  • The set of natural numbers under addition is not a group because there are no inverses, which would be the negative numbers.
  • The set of all rational numbers including 0 with multiplication is not a group because there is no rational number q for which 0/q=1, so not every element has an inverse.

Group structure

A group is a lot more than just a blob that satisfies the four axioms. A group can have internal structure, and this structure can be very intricate. One of the basic problems in abstract algebra is to determine what the internal structure of a group looks like, since in the real world the groups that are actually studied are much larger and more complicated than the simple examples we’ve given here.

One of the basic types of internal structure is a subgroup. A group G has a subgroup H when H is a subset of G and:

  • For a,b∈H, a*b∈H and b*a∈H
  • For a∈H, a⁻¹∈H
  • The identity is an element of H

If H≠G then H is said to be a proper subgroup. The subgroup of G consisting only of the identity is called the trivial subgroup.

A group of n elements where every element is obtained by raising one element to an integer power, {e, a, a², …, aⁿ⁻¹}, where e=a⁰=aⁿ, is called a cyclic group of order n generated by a. Consider the cyclic subgroup of order 6, {e,a,a²,a³,a⁴,a⁵}. Its proper subgroups are {e,a³} and {e,a²,a⁴}.

A non-abelian group may have commutative subgroups. Consider the square dihedral group that we discussed in the introduction. This group is not abelian but the subgroup of rotations is abelian and cyclic:

We now give two examples of group structure.

Even if a group G is not abelian, it may still be the case that there is a collection of elements of G that commute with everything in G. This collection is called the center of G. The center C is a subgroup of G. Proof:

  • Identity: eg=ge for all g∈G so e∈G.
  • Closure: Let a,b∈C. By definition, ag=ga and bg=gb for all g∈G. So (ab)g=agb=g(ab), therefore ab commutes with all g∈G so ab∈C.
  • Inverses: If a∈C then ga=ag for all g∈G, so a⁻¹(ga)a⁻¹=a⁻¹(ag)a⁻¹. By associativity, this means that a⁻¹g(aa⁻¹)=(a⁻¹a)ga⁻¹. Since aa⁻¹=a⁻¹a=e it follows that a⁻¹g=ga⁻¹ so a⁻¹∈C. QED.

Now suppose that f is a function whose domain and range are both G. A period of fis an element a∈G such that f(x)=f(ax) for all x∈G. The set P of periods of f is a subgroup of G. Proof:

  • Identity: x=ex so f(x)=f(ex) for all x∈G therefore e∈P
  • Closure: Let a,b∈P. Since bx∈G and f(x)=f(ax) for all elements of G, it follows that f(bx)=f(abx). But f(bx)=f(x) so f(x)=f(abx) therefore ab∈P.
  • Inverses: Let a∈P. Then f(x)=f(ex)=f(a(a⁻¹x))=f(a⁻¹x) so a⁻¹∈P for. QED.

Finite groups are finitely generated

We saw that cyclic groups are generated by a single element. When it’s possible to write every element of a group G as products of a (not necessarily proper) subset A of G then we say that A generates G and write this as G=⟨A⟩. The most “well, duh” proof you’ll ever see is the proof that all finite groups are generated by a finite generating set:

  • Let G be finite. Every element of G is a product of two other elements of G so G=⟨G⟩. QED.

Every finite group is trivially generated by itself but it may also be generated by a proper subset. For example, the group G={e, a, b, b², ab, ab²} with the constraints a²=e, b³=e, ba=ab² is is generated by a and b so G=⟨{a,b}⟩.

We will finish off this article with an application.

Error-resistant communication

The simplest way to transmit digital information is to encode it into binary strings of fixed length. No communication scheme is completely free from interference so there is always a possibility that the wrong data will be received. The method of maximum-likelihood decoding is a simple and effective approach to detecting and correcting transmission errors.

Let 𝔹ⁿ be the set of binary strings, or words, of length n. It is straightforward to show that 𝔹ⁿ is an abelian group under binary addition without carrying (so that for example 010+011=001). Note that every element is its own inverse. A code C is a subset of 𝔹ⁿ. The following is an example of a code in 𝔹⁶:

C = {000000, 001011, 010110, 011101, 100101, 101110, 110011, 111000}

The elements of a code are called codewords. Only codewords will be transmitted. An error is said to occur when interference changes a bit in a transmitted word. The distance d(a,b) between two codewords a and b is the number of digits in which two codewords differ. The minimum distance of a code is the smallest distance between any two of its codewords. For the example code just above, the minimum distance is three.

In the method of maximum-likelihood decoding, if we receive a word x, which may contain errors, the receiver should interpret x as the codeword a such that d(a,x) is a minimum. I will show that for a code of minimum distance m this can always (1) detect errors that change fewer than m bits and (2) correct errors that change ½(m-1) or fewer bits.

  • 1: Suppose that the transmitter sends codeword p and that the codeword experiences an error that flips fewer than m bits, producing codeword q. Since d(p,q)