Group Theory lessons

What is a group?

A group is a set of things together with a way to combine any two of them. We write it as (G,\ *), where G is the set and * is the way of combining.

For the square, G is its eight symmetries and * means "do this, then that". For numbers, G could be the integers and * could be +.

For symmetries we write ab to mean a, then b. Some books read it the other way round, so always check.

The four rules

Not every set with an operation is a group. It must follow four rules, called the group axioms.

1. a * b \in G (closure: the answer is always in the set)
2. (a * b) * c = a * (b * c) (associativity: brackets do not matter)
3. e * a = a * e = a (identity: one element changes nothing)
4. a * a^{-1} = a^{-1} * a = e (inverses: every element can be undone)

On the square, the identity e is the move that does nothing. The inverse of a quarter turn is three more quarter turns, because together they make a full turn.

Notice that order is not one of the rules. In a group, a * b and b * a can be different.

Testing the rules

To show something is a group, check all four rules. To show it is not, one example that breaks a rule is enough.

Steps through five sets and operations, ticking each rule or showing a counterexample that breaks it.

An example that breaks a rule is called a counterexample. The integers under multiplication fail because 2 has no whole number inverse.

Practice: Check the four rules

Mark each of the four rules as holding or breaking for a set and operation; counterexamples in the explanation.

Cayley tables

A Cayley table shows every combination in a group. The entry in row a and column b is ab.

The table of the four turns of a square fills in cell by cell, then picks out the identity row, the inverses and a full row.

The row for e copies the column headings, because e does nothing. Wherever e appears inside the table, its row and column are inverses.

In a group, every row and every column contains each element exactly once. That makes a Cayley table a kind of sudoku.

Practice: Complete the table

Fill the blank cells of a small Cayley table using the rule that each row and column holds every element once.

Clock arithmetic

On a 12 hour clock, 5 hours after 9 o'clock is 2 o'clock. You wrap round when you pass the top.

Modular arithmetic works the same way for any number n. To add mod n, add as normal, then keep the remainder after dividing by n.

1. 4 + 5 = 9 (add as normal)
2. 9 = 6 + 3 (take away one lap of 6)
3. 4 + 5 = 3 \text{ (mod } 6\text{)} (keep the remainder)

A clock with n positions adds two numbers by stepping round, wrapping past the top; tap two numbers to add your own.

The integers mod n

The numbers 0 to n-1 under addition mod n form a group called \Z_n. Every sum lands back on the clock, so closure holds.

The integers mod 6: \Z_6 = \lbrace 0,\ 1,\ 2,\ 3,\ 4,\ 5\rbrace

The identity is 0, because adding 0 changes nothing. The inverse of a is n-a, because together they make n, which wraps to 0.

In \Z_6, the inverse of 2 is 4, since 2+4 wraps to 0. The inverse of 3 is 3 itself.

Practice: Sums and inverses

Type a sum or an inverse in Z_n; random clean values, with hints for forgetting to wrap round.

The order of an element

Keep combining an element with itself and you eventually get back to the identity. The number of steps that takes is the element's order.

On a 12 position clock, each element steps round from 0 until it lands on 0 again, counting the steps.

In \Z_{12}, adding 3 goes 3,\ 6,\ 9,\ 0. That takes four steps, so 3 has order 4.

For a symmetry, the order is how many times you repeat it to get back to the start. A quarter turn has order 4, and every flip has order 2.

Practice: Find the order

Type the order of an element of Z_n or of a square symmetry; random rounds with targeted hints.

Cyclic groups and generators

Some elements reach every element of the group if you keep adding them. Such an element is a generator, and a group with a generator is cyclic.

For each element of Z_n, a star is drawn by stepping round the clock; generators visit every point.

In \Z_8, the element 3 is a generator. It visits 3,\ 6,\ 1,\ 4,\ 7,\ 2,\ 5,\ 0, but 2 only reaches 2,\ 4,\ 6,\ 0.

An element of \Z_n is a generator when it shares no factor with n except 1. The four turns of a square also form a cyclic group, generated by r.

Practice: Pick the generators

Tap every generator of Z_n on a clock; random n, with each element's order in the explanation.

Dihedral groups

The symmetries of a regular polygon form a dihedral group. An equilateral triangle has six: three turns and three flips.

A numbered triangle performs each of its six symmetries in turn, with its name and mirror line.

The triangle's group is written D_3 and the square's is D_4. A regular polygon with n sides always has 2n symmetries.

Each flip of the triangle has a mirror line through one corner. Flip twice across the same line and you are back where you started.

Order matters

With numbers, 2+3 and 3+2 are equal. With symmetries, the order you do them in can change the answer.

Two squares do the same two moves in opposite orders, side by side, and end in different places.

On the square, rh = d_2 but hr = d_1. A group where order never matters is called abelian, so D_4 is not abelian.

Turns still agree with other turns. Doing r then r^2 gives the same result as r^2 then r.

Practice: Combine symmetries

Type the single square symmetry equal to two moves, or an inverse such as r^{-1}, as a name like r^2 or d_1.

Subgroups

A subgroup is a smaller group inside a bigger one, using the same operation. The four turns of the square form a subgroup of all eight symmetries.

Tap points on a Z_n clock to build a subset; ticks show whether it has 0, is closed and has its inverses.

To test a subset, check that it contains the identity, is closed, and contains every inverse. Associativity comes free from the bigger group.

In \Z_6, the set \lbrace 0,\ 2,\ 4\rbrace is a subgroup. The set \lbrace 0,\ 1,\ 2\rbrace is not, because 1+2=3 is missing.

Practice: Spot the subgroups

Sort subsets of Z_n into subgroups and not subgroups.

Lagrange's theorem

The number of elements in a group is also called its order. Lagrange's theorem says the order of a subgroup always divides the order of the group.

Lagrange's theorem: |H| \text{ divides } |G|

The 12 elements of Z_12 rearrange into rows, one shifted copy of a subgroup per row, so the subgroup size divides 12.

Shifting a subgroup makes copies of it, and the copies cover the group without overlapping. So the group splits into equal rows.

The same goes for elements. An element's order divides the group's order, because its powers form a subgroup of that size.

Practice: Use Lagrange's theorem

Multiple choice: which subgroup or element orders are possible for a group of a given order.

Permutations

A permutation is a shuffle of a list of objects. All the shuffles of n objects form a group called the symmetric group S_n.

Three numbered cards are shuffled by each permutation of S_3 in turn, with arrows and cycle notation.

Cycle notation writes a shuffle compactly. (1\ 2\ 3) means 1 moves to 2, 2 moves to 3, and 3 moves back to 1.

There are 3 \times 2 \times 1 = 6 ways to shuffle three objects, so S_3 has six elements. Each triangle symmetry shuffles its corners, so D_3 and S_3 are really the same group.

Practice: Match the shuffles

Match each triangle symmetry picture to the cycle notation for how it shuffles the corners.

Groups everywhere

The moves of a Rubik's Cube form a group with about 43 quintillion elements. Each scramble is one element, and solving it means finding its inverse.

Chemists sort crystals by their symmetry groups, and there are 230 possible patterns in three dimensions. Physicists describe particles with groups too.

Groups also protect your data online. Elliptic curve cryptography uses a group where combining is easy but working backwards is very hard.