Abstract Algebra and Discrete Mathematics

By Karl Dahlke and Kermit Rose, Copyright © 2014

Chapter 11, Groups Acting on Sets


Group Action Table of Contents Start of chapter

A group G acts on a set S if each element in G is associated with a permutation on the elements of S.  The group identity is mapped to the identity permutation, and the group element a*b drives the permutation of a followed by the permutation of b.  Since b/b = 1, the permutation of b inverse is the inverse of the permutation of b.

The image of G is a permutation group inside the symmetric group on n letters, and the action defines a homomorphism from G into Sn  The group elements that map to the identity permutation form the kernel.  G acts effectively on S if the homomorphism is injective; every member of G (other than 1) induces a nontrivial permutation on S.  This is also written "G embeds in S", which really means G embeds in the permutation group of S.

One can reverse the sense of group action, so that the action of a*b is the action of b followed by the action of a.  Note that G still maps (homomorphically) into the permutation group on S, provided the permutation group is defined in such a way that the composition of two permutations applies the second, and then the first.  This is convenient for certain applications.

Orbit, Stabilizer Table of Contents Start of chapter

The orbit of an element x in S is the set of elements that x can be mapped onto via the action of G.  Verify that orbit is symmetric and transitive, hence orbits partition the elements of S.

The stabilizing subgroup H(x) is the subgroup of G whose actions leave x fixed.

If a takes y to x, and 1/a takes x to y, and H stabilizes x, then a*H/a stabilizes y.  Reverse this map to show stabilizing members for x and y correspond 1 for 1.  The stabilizers for any two elements in the same orbit are isomorphic via an inner automorphism of G.  Conversely, the a-conjugate of the stabilizing subgroup of x stabilizes another element in the orbit of x, namely the action of 1/a on x.

H
x y z orbit

For finite groups, |H|讄x| = |G|, where |x| is the size of the orbit of x.

If the stabilizer H is a normal subgroup of G, it is not changed by conjugation, hence it stabilizes everything in the orbit of x.

Translation, Conjugation Table of Contents Start of chapter

Every group G is itself a set - why not let G act on its own members, or subgroups, or cosets, etc?

Right translation and conjugation are two actions in which G acts on its own members.  In the former, a moves x onto x*a.  In the latter, a moves x onto 1/a*x/a.

Left translation is also possible, wherein a maps x to a*x, but that requires the backwards convention, composing permutations right to left.  When ab acts on x by left translation, you have abx, which is the permutation of b followed by the permutation of a.  There's nothing wrong with that, but right translation is more intuitive.

Using translation, any finite group can be represented as a permutation group.  The induced homomorphism is injective, since only 1 produces the identity permutation on G.

When the action is conjugation, the stabilizer of x is the centralizer of x, or all elements that commute with x.  The conjugacy class of x is the orbit of x.  This is all the elements that you can reach by conjugating x.  Again, orbits partition the group.

The number of orbits, or the number of conjugacy classes, is the class number of the group.

The "class equation" states that the sum of the sizes of the conjugacy classes is |G|, and each class size divides |G|.  The former is a restatement of orbits partitioning the group.  The latter comes from |stabilizer|讄orbit| = |G|, as described in the previous section.  Note that the orbit has size 1 iff x is in the center of G.  We sometimes write the class equation as |G| = |center| plus the sum of the sizes of the nontrivial conjugacy classes.

Since conjugation is an inner automorphism, it maps subgroups to subgroups.  Thus a group can act on its own subgroups by conjugation.  The stabilizer of a subgroup is its normalizer.  This does not mean the group elements are fixed; only that the subgroup is mapped onto itself.  In other words, x*H/x = H, which is the definition of a normalizer.

Macay's Theorem Table of Contents Start of chapter

If p prime divides |G|, G contains a subgroup Z/p.  This is Macay's theorem, and it kickstarts the Sylow theorems.

Let the set S contain p-tuples of elements of G, such that the product of the p entries is always 1.  Thus |S| = |G|p-1.

The group Z/p acts on S by performing right circular shifts.  Remember that orbit length times stabilizer size is p, and since p is prime, the only choices are 1 and p.  The first tuple in S, [1,1,1,1…], has an orbit of 1.  If every other orbit in S has size p, then |S| is congruent to 1 mod p, which is impossible.  Therefore some nontrivial tuple is its own orbit, and is fixed by all circular shifts.  All elements in this tuple are equal, hence xp = 1.  In other words, x generates a cyclic subgroup of order p inside G.

11111
abcde
bcdea
cdeab
deabc
eabcd
xxxxx

In fact, the number of elements of order p is congruent to -1 mod p.  This could be satisfied by precisely one p subgroup having p-1 elements of order p, or you might have lots of elements of order p.

The Fixed Point Principle Table of Contents Start of chapter

Let G have order pk, and let G act on a finite set S.  Recall that orbit size times stabilizer size = |G|.  If the orbit is nontrivial its size is a power of p, hence p divides the number of elements that move about under G.

Write |S| equals |S0| mod p, where S0 is the subset of elements fixed by G.  This is the fixed point principle.

For example, Macay's theorem (previous section) has Z/p acting on a set S, where |S| is 0 mod p, hence |S0| is divisible by p, and S0 cannot be a single element.

Transitive, Doubly Transitive Table of Contents Start of chapter

A group action is transitive if there is only one orbit.  In other words, G maps every point in S to every other point.  Note that G must be at least as big as S.

The action is doubly transitive if some permutation takes any pair of elements to any other pair.

Assume the action of G on S is transitive, and |S| = p (prime).  If G has a kernel that maps to the identity permutation, mod out by the kernel and call the factor group H.  Now H acts effectively on S.

since the orbit has size p, |H| is divisible by p.  By Macay's theorem, H contains a subgroup Z/p.  The only possible permutation with period p is a p cycle.  Thus the action of G includes a p cycle on S.

If |S| is divisible by p, and G acts transitively, |H| is divisible by p, and G contains an element of order p whose action on S is one or more disjoint p cycles running in parallel in S.

The Equal Orbits Principle Table of Contents Start of chapter

Let a possibly infinite abelian group G act transitively on a finite set S.  Pick an element c in G and let it act on S.  Relabel the points of S if need be, so that c moves 0 to 1 to 2 to 3 to 4 to 5 and back around to 0, for example.  This is an orbit of length 6.

If there is more to S, let d move 0 to 6.  Since d induces a permutation, the images of 0 through 5, under d, are distinct.  If one of these images lies in the first orbit, say d maps i to j for j < 6, then c-id maps i to 6, while dc-i keeps i within the first cycle.  This is a contradiction.  So let d map the first cycle onto elements 6 through 11.

cd moves 0 to 7, so dc moves 0 to 7, which means c moves 6 to 7.  cd moves 1 to 8, so dc moves 1 to 8, which means c moves 7 to 8.  Continue this reasoning, and c pushes 6 through 11 around in a cycle, as it does with 0 through 5.

If there is more to S, let e map 0 to 12.  Again, the images of 0 through 5 are distinct under e, and none of these images lie in the first cycle, as per the above proof.  Suppose e maps i to j in the second cycle.  Then c-ie moves i to 12, while ec-i moves i into the second cycle.  This is a contradiction, hence e moves the first cycle onto a third, which is disjoint from the previous two.  This cycle, 12 through 17, is pushed around by c, just like the first two.

continue by induction until S is partitioned into cycles of length 6.  In other words, c moves S around in parallel cycles of the same length.

If c fixes anything in S, it fixes all of S.

[ circle with 0 through 5 around, 0 at the top, then another circle 6 through 11, and another circle 12 through 17, arrow labeled d connecting 0 to 6 and another arrow labeled e connecting 0 to 12 ]

This principle still holds if S is countably infinite, as long as one of the orbits induced by c is finite.  Establish an ordering on the elements of S, from 0 through the positive integers.  Let c move a finite subset about as described above.  This is the first orbit.  To illustrate, let the first element in this first orbit be 17.  Select d so that d moves 17 to the least member of S not included in this orbit.  Now d maps the first orbit of size 6, induced by c, onto another orbit of size 6 induced by c.  After this, select e so that e moves 17 to the leaste element of S not included in either of the first two orbits.  This seeds the third orbit.  Continue this process forever, and every element of S is caught up in some orbit of length 6 via the action of c.

If you like transfinite induction, we can do the same for any well ordered set.

Note that this fails if G is not abelian.  Let G = S3, and let G act on 3 elements by permuting them in all possible ways.  G acts transitively, yet one of the six actions swaps 1 and 2, and leaves 3 alone.

The Strong Cayley Theorem Table of Contents Start of chapter

Any group G with subgroup H acts on left cosets of H by right multiplication.  If Hx is the left coset represented by x, then the action of a takes Hx to Hxa.  This is a proper group action on a set whose size is the index of H in G.

Let f be the homomorphism defined by this action.  The quotient group is a permutation group on n letters, where n is the index of H.  The kernel is the set of elements affixing every coset.  Let a be in the kernel and let x be any cosrep, hence xa is in the same coset as x.  That is, xa = jx for some j in H.  Multiply by x inverse on the left and a = 1/x * jx.  This places a in some conjugate of H.  But this must hold for every x, hence a is in all the conjugates of H.  The kernel is the intersection of all the conjugates of H.  We know this is a normal subgroup, because it's the kernel of the action of G.  Call this normal subgroup K.  Thus G/K embeds in Sn, where n is the index of H in G.

The trivial conjugate of H is H, hence K is a subgroup of H.  In fact K is the largest normal subgroup of G contained in H.  If some other normal subgroup M is contained in H, x*M/x = M for all x, and the intersection of x*H/x would include all of M.

Let H be a subgroup of G with index n.  Let K be the largest normal subgroup of G contained in H.  By the strong Cayley theorem, K is the kernel of the homomorphism induced by right translation on the left cosets of H.  Thus G/K embeds in Sn, and the order of G/K divides n!.

Let q be a prime ≥ n, such that q divides |H|.  Now q either divides the order of K or the index of K in H.  If the latter then qn, the index of K in H times the index of H in G, divides n!, which is impossible.  Hence q, and every higher power of q for that matter, must divide |K|.

If we know that every prime q in |H| is at least as large as n, then K = H and H is normal.  I say at least as large as n because if q = n and q divides |H|, q2 cannot divide into q!.  This is a generalization of an earlier result; that H is normal in G if its index is 2.  Every prime in |H| is at least as large as 2.

G
H
K

Let G have order 49, hence it has a subgroup H of order 7.  Applying the above, n = 7, and q = 7, hence H is normal in G.  The same holds for a group of order 42.

If |G| cannot divide n!, then there is some normal subgroup K in H, possibly less than H, but certainly larger than 1.  If H has order 25, and index 7 in G, then H contains a normal subgroup K which is non trivial, but could be less than H.

It doesn't happen very often, but sometimes G/K implies permutations that go beyond divisibility.  Let H be Z/25, and have index 23 in G.  There's plenty of room to divide 25 into 23!, but not as a permutation of order 25.  Such a permutation requires 25 elements.  Again, H contains a nontrivial normal subgroup of G.

p Groups and p Sylow Subgroups Table of Contents Start of chapter

For p prime, G is a p group if the order of every element in G is a power of p.  Note that infinite groups can be p groups.  The infinite direct product of Z/p> is an example.

If |G| is a power of p then every subgroup, including the powers of x, has order dividing |G|, hence G is a p group.  Conversely, if some other prime q divides |G|, then G contains a q cycle, and is not a p group.  For finite groups, p group means |G| is a power of p.

A sylow subgroup is a maximal subgroup that is also a p group.  Use zorn's lemma to show such a group exists when the containing group is infinite.

Let the p group G have a normal subgroup H.  Since x*H/x is H, G acts on the set H by conjugation.  This action leaves the center of G fixed.  When restricted to H, it fixes H intersect the center of G.  By the fixed point principle, this fixed set has size n, where n = |H| mod p.  Of course H is a p group, so n = 0.  The center of G, intersected with H, is always divisible by p.

As a special case, set H = G, and p divides the number of elements in the center of G.  The center includes 1, so ratchet this up to a multiple of p, and the center of every p group is nontrivial.

The Congruent Index Principle Table of Contents Start of chapter

Let H be a p-subgroup of G, and let K be the normalizer of H in G.  What can we say about the index of H in K, or in G?

Let H act on left cosets of H by right translation.  The left coset Hx is fixed by H iff every y in H produces Hxy = Hx.  Multiply by x inverse on the right, and the conjugate of y has to map H onto H, hence the conjugate of y is something in H.  This has to happen for every y in H, so the x-conjugate of H becomes H.  In other words, x is in the normalizer of H, which is K.  Thus H fixes all the cosets of H in K.

The number of fixed cosets is the index of H in K.  By the fixed point principle, this index is congruent to the number of cosets in G, or the index of H in G.  The index of H in K = the index of H in G mod p.  Since the indexes are congruent mod p, this is called the congruent index principle.

If p divides the index of H in G, then p divides the index of H in K, and K properly contains H.

The First Sylow Theorem Table of Contents Start of chapter

Let |G| = mpn, where n is positive and p does not divide m.  For each i in [1,n] there is a subgroup of order pi, and if i < n, each subgroup of order pi is normal in a subgroup of order pi+1.

To start, Macay's theorem gives us Z/p.  Use any one of these p cycles to start the ascending chain.

By induction, assume H has order pi, where i < n.  Let K be the normalizer of H in G.  We haven't reached i = n yet, so p divides the index of H in G.  Use the congruent index principle to show that K properly contains H.  Every subgroup is normal in its normalizer, so H is normal in K.  The congruent index principle tells us p divides the index of H in K.  By Macay's theorem, the quotient group K/H contains Z/p.  Take its preimage in K to obtain a subgroup J somewhere between H and K.  Everything in J conjugates H onto itself, since J is contained in K, hence H is normal in J.  Furthermore, |J| = pi+1.  This completes the inductive step.
mp3 G
p3 sylow
p2
p macay

The sylow subgroups are the subgroups with order pn, The maximal p subgroups in G.  Conjugate any one of these sylow subgroups and obtain another group of order pn, another sylow subgroup.  If there is but one sylow subgroup it is normal in G.

Apply the sylow theorem to G when G is itself a p group.  Find a subgroup Z/p by Macay's theorem, then build an ascending chain culminating in G.  The penultimate subgroup is normal in G, with index p.  A p group (beyond the p cycle) is never simple.  There is no need to look for a simple group of order 125.

Let G have order mpn, and let the sylow subgroup H have order pn.  If |G| does not divide into m!, the strong cayley theorem tells us H contains a normal subgroup that is not trivial, hence G is not simple.  No need to look for a simple group of order 100.

The Second Sylow Theorem Table of Contents Start of chapter

All sylow subgroups are conjugate.

Let G have order mpn, where p does not divide m.  Let H and J be any two sylow subgroups of G.  Thus |H| = |J| = pn.

Let H act on the left cosets of J by right translation.  Review the reasoning used in the congruent index principle.  The coset Jx is fixed by H iff Jxy = Jx for all y in H, iff the conjugate of y maps J onto J, iff the conjugate of y is in J, iff xH/x lies in J.  Since |H| = |J|, this means H and J are conjugate through x.  Thus a coset of J, represented by x, is fixed by the action of H iff H and J are conjugate.

By the fixed point principle, the number of cosets of J fixed by H is congruent to m mod p.  This is nonzero, so some coset Jx is fixed by H.  This means H and J are conjugate through x.

The selection of J was arbitrary, so every sylow subgroup is a conjugate of H, and all sylow subgroups are conjugate.

All sylow subgroups are isomorphic.  Conjugation by the appropriate element implements the isomorphism.

A sylow subgroup is normal iff it is the only sylow subgroup in G.

H
x⇕
J
G

Sometimes the sylow subgroups map into the factor group.  Let a group G have a p sylow subgroup S.  Let C be a normal subgroup of G such that p does not divide |C|.  Let H be the quotient group G/C.  Map S into H, giving a subgroup T.

Nothing of order p can live in C, so S and C are disjoint.  Everything in S represents its own coset of C.  This means S maps injectively into H.  In other words, S and T are isomorphic, and T becomes a p sylow subgroup of H.

Suppose S1 and S2 map to the same sylow group T in H.  This means the C cosets of S1 contain S2.  If you know that S1 is normal in the group generated by C and S1, then S1 is the only sylow subgroup within this group.  There is no room for S2 here.  S2 cannot be different from S1 and still map to T.  The sylow subgroups of G and H correspond one for one.  This is the case when C is in the center of G, for S1 will be normal in C join S1.

You may be able to repeat this process, pulling out the center of H and so on, as long as the centers are not divisible by p.

The Third Sylow Theorem Table of Contents Start of chapter

Let G have order mpn, where p does not divide m.  The number of sylow subgroups divides m, and is equal to 1 mod p.

Let G move sylow subgroups about by conjugation.  By the second Sylow theorem, the action of conjugation on sylow subgroups is transitive.  Let H be any of these sylow subgroups.  The size of the orbit is the index of the stabilizer of H in G, and since the action is conjugation, the stabilizer is the normalizer, which is a subgroup somewhere between H and G.  The size of the orbit, which is the number of sylow subgroups, equals the index of the normalizer of H in G.  Therefore the number of sylow subgroups divides m.

Instead of G, let H act on sylow subgroups by conjugation.  The sylow subgroup J is fixed by H iff yJ/y = J for all y in H, iff H is contained in the normalizer of J.  Call this normalizer K.  Now K contains both sylow subgroups, H and J.  By the second sylow theorem, H and J are conjugate in K.  Since J is normal in K, it is the unique sylow subgroup in K, and H = J.

If H fixes J then H = J, so H is the only sylow subgroup fixed by H.  By the fixed point principle, the number of sylow subgroups is congruent to 1 mod p.

Here is a disjoint variation - assume there is an element z in H that cannot be in any other sylow subgroup.  Perhaps the sylow subgroups are disjoint, or perhaps they share some p cycles, but z has order p2.  In any case, z seeds a group Z whose order is some power of p, and Z acts on sylow subgroups by conjugation.  Since Z belongs to H Z fixes H, but suppose Z also fixes J.  Now Z belongs to the normalizer K of J.  J is a sylow subgroup of K, and by the first sylow theorem, Z belongs to a sylow subgroup of K, which cannot be J.  These two subgroups are conjugate, yet J is normal in K.  This is a contradiction, hence Z does not fix J after all.  Z moves every sylow subgroup (other than H) through an orbit that is a power of p.

In general, let z belong to several sylow subgroups, whence z fixes all of them by conjugation.  Assume J is not in this set and suppose z fixes J.  As above, z is in the normalizer K of J, and K also contains at least one sylow subgroup, H or one of her sisters, containing Z.  J is normal in K, yet J is conjugate to some other sylow group in K.  This is a contradiction, hence z fixes the sylow subgroups that contain z, and moves the others about in nontrivial orbits whose lengths are powers of p.  Typically z has order p, perhaps belonging to several sylow subgroups of order p2, whence z fixes those subgroups and moves the others about in orbits of size p.

These theorems can be used to deny the existence of various simple groups.  Suppose G is a simple group of order 350, with j sylow subgroups of order 25.  By the third sylow theorem, j = 1 mod 5, and j divides 14, hence j = 1.  The sylow subgroup is normal, and G is not simple.

If H is a sylow subgroup, and you have determined that there are t such subgroups in G, then the normalizer of H is the stabilizer of H under the action of conjugation.  The orbit has size t, all sylow groups being conjugate, and the normalizer has index t in G.  The Strong Cayley Theorem can then be used, mapping G mod some kernel into St.  Or G embeds if it is a simple group.

Sylow Intersection Table of Contents Start of chapter

If V is the intersection of all p sylow subgroups, V is normal in G.  Conjugating G by anything permutes the sylow subgroups about, and preserves the intersection.

If a sylow subgroup H contains a smaller p group V that is shared among 4 sylow subgroups, then apply a conjugation c that moves H to J.  This is a group automorphism, hence J contains a smaller p group c(V) that is shared among 4 sylow subgroups.  All sylow groups are isomorphic, and the pattern of intersection looks the same from any sylow subgroup.

If the sylow group is cyclic of order 9, there is one unique subgroup of order 3.  If this subgroup V is shared among 4 sylow groups, then wherever you go, 4 sylow groups are joined together by an intersection of Z/3.  Sylow groups clump together in sets of 4, and the number of sylow groups is a multiple of 4.  This causes the index of the sylow group to be divisible by 4.

Continuing this somewhat atypical example, let G act on groups of order 3 by conjugation.  There is one such group for every 4 sylow groups of order 9.  If there are t sylow groups there are t/4 groups of order 3.  Conjugation is transitive on sylow groups, hence it is transitive on these smaller p groups, each of which is unique in any sylow group that contains it.  The orbit has size t/4, and the stabilizer has index t/4 in G.

Another way to view this is to let G act on connected components, i.e. clumps of sylow subgroups that are connected by sharing smaller groups.

The Normalizer of the Normalizer Table of Contents Start of chapter

Let J be a sylow subgroup with H as its normalizer.  Since all sylow subgroups are conjugate, and J is normal in H, H contains no other sylow subgroups.

Now consider the normalizer of H, the set of elements x such that xH/x = H.  If x moves J somewhere else there would be two sylow subgroups in H.  Thus xJ/x = J, and x is already in H.  The normalizer of H is H.

The Structure of a Finite Abelian Group Table of Contents Start of chapter

Every finite abelian group is the direct product of cyclic groups, each cycle a prime power.

Let n be the order of G, and split n up into prime powers.  Let one of these powers be pk.  By the first sylow theorem, there is a subgroup of order pk.  Call this subgroup H1, and find a similar subgroup Hi for each prime power in n.  Since G is abelian, all these subgroups commute.  Together they span a subgroup H inside G.

Suppose a sum of elements xi, drawn from Hi, equals 0, the group identity.  Take the shortest sum, i.e. the sum with the fewest terms.  Now, minus the first element in the sum, say -x1, has order equal to some power of p, and is equal to the sum of the remaining elements.

-x1 = x3 + x5 + x9

Multiply through by pk, and the left side becomes 0.  Since p is relatively prime to the order of x3, that term is nonzero in H3.  The others are nonzero as well.  This gives a shorter sum of elements that is equal to 0, and that is a contradiction.  The subgroups Hi are disjoint, and H is equal to their direct product.

The order of H is n, and H lives in G, which also has order n, hence G is the direct product of its sylow subgroups.  Separate each Hi into a product of cycles, and the same is true of G.

Without loss of generality, concentrate on H1.  If it has order p, it is Z/p, and we're done. So proceed by induction on pk.  Let J be a subgroup of order pk-1, which exists inside H1 by the first sylow theorem.  By induction, J is one or more copies of cyclic groups running in parallel, where each cycle is a power of p; and their product has order pk-1.  The quotient H1/J is cyclic, with order p.  Let y be a cosrep that generates the quotient group.  Now py is something in J.  Suppose py = z within one of the cycles of J.  If z is divisible by p, say z = pv, replace y with y-v.  Now py lands on 0 in this particular cycle, and is independent of that cycle.  If v is not divisible by p, use v as the generator for that cycle, rather than 1.  Since v is coprime to p, it works just as well.  We're just renumbering the elements.  Do this across all of J, and py might equal 1,1,1; for 3 of the parallel cycles in J.  Arrange the cycles so the longest comes first.  Let 1,1,1 generate the first cycle, and let 0,1,0 and 0,0,1 generate the other two cycles.  They still run independently of one another, and the element y has made the first cycle longer by a factor of p.  Therefore H1 is, like J, one or more copies of cyclic groups running in parallel.  Make a similar assertion for each Hi, and this completely characterizes the finite abelian group G.

p p2 p2 p3 q2

Cyclic Multiplicative Group Table of Contents Start of chapter

A finite multiplicative group in a field is cyclic.

Let G be such a group, whence G is finite and abelian.  As above, G is a direct product of cycles.  If all the cycles are coprime, such as 7, 9, and 11, then G can be rewritten by the chinese remainder theorem as one long cycle of length 7󭘱1 = 693.  If two of the cycles are based on a prime p, then there are at least p2 elements of order p in G.  This provides p2 distinct solutions to the equation xp譸 - 1 = 0.  This is impossible, hence G is cyclic.

The powers of 2 (positive and negative exponents) cross the powers of 3 is a multiplicative group in the rationals that is not cyclic.  Thus G must be finite.

The group of 1, 眎, 眏, and 眐 in the quaternions is finite, but not cyclic.  Thus a division ring is not sufficient; we need a field.

Recall the proof that the field of order p, i.e. the integers mod p, has a primmitive root.  The reasoning was rather tedious, but now it's an immediate corollary.  The nonzero integers mod p form a finite multiplicative group in a field, which is cyclic, generated by some primitive root b.  The same holds for any finite field.

Groups of Order p2 and p3 Table of Contents Start of chapter

In this section we will look at groups of order p squared and p cubed.  The abelian groups were characterized above, so assume G is nonabelian.  Recall however that G has a nontrivial center.

Let G have order p2, and let H be its center.  If H = G then G is abelian.  If not then H = Z/p.  Let x be an element not in H.  Now x has order p in G/H, hence xp lies in H.  The powers of x represent all the cosets of H in G, and they commute with each other.  They also commute with H, since H is the center.  Therefore G is abelian.  It is either Z/p*Z/p or Z/p2.

Next let G have order p3 and let H be the center.  If H = G then G is abelian, and is either Z/p*Z/p*Z/p, Z/p2*Z/p, or Z/p3.

If H has order p2 then select x not in H and argue as above, whence G is abelian once again.

Let H have order p and let K = G/H.  Since K has order p2 it is abelian.  If K is cyclic, let x generate K, whence x and H generate G, x and H commute, and G is abelian.  So let K = Z/p*Z/p, and let x and y generate K.  If x and y commute than G is abelian, so assume they don't commute.

At this point I must apologize for the inconsistent notation that is coming up.  I'm going to use additive notation for H, which is cyclic, and multiplicative notation for the rest of G, which is not abelian.  Think of H as Z/p, i.e. the integers mod p.  Thus 0 is the additive identity in H, and also the identity element for G, while 1 is the generator of H, 1 2 3 4 etc, and is not the identity for G.  I hope this isn't too confusing.

Suppose xp = j for some nonzero j in H.  If j is not 1, let v be the inverse of j mod p and replace x with xv.  Raise the new x to the j power and combine with something from H to get the old x back again, hence G is still spanned.  Furthermore, xp = 1.

Do the same for y.  Hereinafter we may assume both generators, when raised to the p power, produce 0 or 1 in H.

If both generators produce 0, and yx = xyw, let w generate H.  In other words, yx = xy1.  This is the first nonabelian group of order p3, up to isomorphism.

This group is isomorphic to the 33 upper triangular matrices over Z/p with ones down the main diagonal.  When 1 is in the upper right we have w, the generator for the center of G.  Place 1 in the top middle and 1 in the middle right to get y and x respectively.  Verify that w commutes with x and y, and yx = xyw.  Also, each of x y and w, raised to the p, gives the identity matrix.

We can show that every element in this group has order p.  Raise a generic element xiyjwk to the p power and push the instances of y forward past the instances of x.  The number of swaps is i譲(1+2+3+…+p-1), or (p2-p)/2, which is divisible by p when p is odd.  (I'll deal with p = 2 later.)  The original instances of x y and w are raised to the p, and drop out as well.  The result is 0.

p = 3: xyxyxy = xxyyxyw = xxyxyyww = xxxyyywww = 0

What about p = 2?  The construction of the group is still valid, including its representation as 33 upper triangular matrices, but this time it contains an element of order 4, namely xy or xyw.  In fact this group is equal to the dihedral group D4, i.e. the reflections and rotations of the square.  The 180 rotation generates the center of the group, 1 in the above notation.  The vertical reflection is x and the reflection through the main diagonal is y.  Note that yx = xy1, and x2 and y2 are 0.

Next case: let both x and y lead to 1 in H.  Rescale y again, so that yp = -1.  Now use xy as a generator, instead of y.  Expand (xy)p, and push the instances of y forward.  Every time y and x commute we introduce a factor w from H.  Again, this happens 1+2+3+…+p-1 times, which drops to 0 when p is odd.  This leaves xpyp = 1-1 = 0.  Therefore the new generator produces 0 in H.

We may now assume xp = 1 and yp = 0.  Thus |x| = p2.  This is definitely a different group than we've seen before.

With p still odd, renormalize y as follows.  If yx = xyj, and v is the inverse of j mod p, replace y with yv.  Now yp is still 0, xp is still 1, and yx = xy1.  This is the second nonabelian group of order p3.

Return to p = 2.  Suppose x2 = 1 and y2 = 0.  Replace x with xy, and both generators lead to 0 in H.  We've already handled this case.

Finally both x2 and y2 are 1, and yx = xy1.  This is isomorphic to the quaternion group Q8.  To see the isomorphism, consider the quaternion units 1, 眎, 眏, and 眐, where i j and k squared give -1.  Also, ji = -ij etc.  Think of i as x, and j as y, and k as xy.  The multiplicative identity 1 corresponds to 0 in H, and -1 corresponds to 1, the involution in H.  These are indeed the same group, hence the nonabelian groups of order 8 are D4 and Q8.

Quaternion Groups of Order 8 and 24 Table of Contents Start of chapter

The quaternion group Q8, mentioned above, is the group of units in the quaternions, and consists of 1, 眎, 眏, and 眐.  This has a normal subgroup Z/4, generated by i, with index 2.  Everything in the "other" coset has order 4, not order 2, hence this is not a semidirect product.

The half quaternions has 24 units, giving a group of order 24, denoted Q24.  Of course Q8 is a subgroup of Q24, of index 3.

Let h = (1+i+j+k)/2, and verify that h3 = -1.  Thus -h has order 3.  Since h cannot live in Q8, it generates all 3 cosets of Q8 in Q24.

Show that hi/h = j, hj/h = k, and hk/h = i.  These generate Q8, hence the conjugate of Q8 = Q8, for h, for h2, and for all of Q24Q8 is normal in Q24, with a factor group of Z/3.  A copy of Z/3 lives in Q24, generated by -h, thus Q24 is a semidirect product of Q8 by Z/3.  The automorphism associated with -h, i.e. h*Q8/h, cycles i j and k.

Z/4 is not normal in Q24.  As shown above, h conjugates i onto j.  Yet Z/4 is normal in Q8, is normal in Q24.  A normal subgroup of a normal subgroup of G need not be normal in G.

Metacyclic Groups Table of Contents Start of chapter

There are at most two groups of order pq, where p and q are distinct primes.

Let |G| = pq, where p is the larger prime.  By the third sylow theorem, the number of subgroups of order p equals 1 mod p, and divides q, hence there is one such subgroup, and Z/p is normal in G, with factor group Z/q.

Since G contains an instance of Z/q, and q and p are relatively prime, G is a semidirect product.  The elements of Z/q in G accurately represent the factor group G/Z/p.

suppose q does not divide p-1.  The group automorphisms of Z/p carry one generator onto another.  There are p-1 such automorphisms, including the trivial automorphism that maps 1 to 1.  A semidirect product implies a group homomorphism from Z/q into the automorphisms of Z/p.  If the image of this map is nontrivial then it becomes a q-cycle inside the multiplicative group of order p-1, which is impossible.  Therefore Z/q induces trivial automorphisms on Z/p.  The semidirect product has become a direct product, namely Z/p * Z/q.

Now assume q divides p-1, and G is nonabelian.  It is now possible for the members of Z/q to induce nontrivial automorphisms on Z/p.

Since Z/p and Z/q are both cyclic, let's use additive notation.  Their identity elements are 0, and their generators are 1.  Now 1 (in Z/q) carries 1 to s in Z/p, where s is between 2 and p-1 inclusive.  This defines the entire map from Z/q into the automorphisms of Z/p.  If 1→s is applied q times, we are back to start; hence sq = 1 mod p.

Suppose a different nonabelian pq group maps 1 (in Z/q) to the automorphism 1→t.  Once again tq = 1 mod p.  Both s and t are qth roots of 1.

Remember that q is prime, and s and t are not trivial, not equal to 1.  They are both primitive qth roots of 1.  Either one generates all the qth roots of 1.  Some power of s is t, and some power of t is s.  For purposes of illustration, say s = t3.  Now 1 in Z/q leads to the automorphism that we call t.  This means 3 leads to the automorphism that we call s.  Yet 3 is a perfectly good generator for Z/q.  Relabel the elements so that 3 becomes 1.  Now both groups are semidirect products of Z/p by Z/q, and they are isomorphic.

In summary, a pq group could be the direct product Z/p*Z/q, or, if q divides p-1, it could be the semidirect product of Z/p by Z/q, where 1 in Z/q induces the automorphism 1→s, where s is some predesignated qth root of 1 mod p.  The latter nonabelian group is called the metacyclic group of order pq.  Since one prime is larger than the other, there is no ambiguity here.

When q = 2, the metacyclic group is the same as the dihedral group.  The only nontrivial automorphism of order 2 caries 1 to -1, and is a reflection of Z/p.  This gives the reflections and rotations of the p-gon, which is the dihedral group.

The metacyclic group is equivalent to lower triangular 22 matrices mod p, where each matrix has 1 in the upper left and a qth root of 1 mod p in the lower right.  There are indeed pq such matrices.  Since some of these matrices don't commute, the group is nonabelian, and it has to be metacyclic.  The bottom row is g1,h1 and g2,h2 in our original notation; you can see that the formulas are the same.

The above can be generalized to a group of order pm, where p does not divide m, and Z/p is normal in G, and G contains a cyclic subgroup Z/m.  If 1 is the only factor of m that is 1 mod p (third sylow theorem), or if pm does not divide m! (strong cayley theorem), then yes indeed Z/p is normal in G.

With p and m coprime, G is a semidirect product, and 1 in Z/m maps to 1→s in Z/p.  This map is trivial (making G a direct product), or s is a nontrivial mth root of 1 mod p.

The root need not be primitive.  Let s have multiplicative order d mod p, whence d divides m.  After d steps you are back to start, and after m steps you are back to start.  If t is another root of order d, then te = s, where e is coprime to d.  Again, let e = 3 for illustration.  Perhaps p = 5 and m = 12 and d = 4 and s = 2 and t = 3.  The first automorphism maps 1 to 2, the second maps 1 to 3.  Both 2 and 3 are primitive fourth roots of 1.  As before, t3 = s, but I can't make 3 the generator mod m, because 3 is not coprime to 12.  However, 7 is, so 7 can be the new 1 for Z/m.  We need e plus a multiple of d coprime to m.  Solve this for each qk dividing m and then apply the chinese remainder theorem.  If q does not divide e than we don't have to change e at all.  If q divides e, but not d, then add d to e.  If q divides both d and e, then e/q induces an automorphism of order dq; which is a contradiction, as both s and t have order d.  Put this all together and find a generator of Z/m that maps to t.  Thus the two groups are isomorphic.

In summary, there is a metacyclic group for each d > 1 dividing both m and p-1, while d = 1 gives the direct product.

As a special case, let m be the prime q, whence there is but one nontrivial factor, namely q, and that leads to the metacyclic group described above.

Apply this to the group G of order 20.  The sylow subgroup Z/5 is normal, and G also contains a sylow subgroup H of order 4.  Since 5 and 4 are coprime, G is a semidirect product of Z/5 by H.

Let H be cyclic, namely Z/4, and apply the results shown above.  There are three possible groups, according to the factors of 4.  One is the direct product, one mapps 1 to 1→2, and one maps 1 to 1→4.

If H is Z/2*Z/2, none of the elements of H, or 2 of the elements of H, could reflect Z/5.  If one generator of H reflects, the other leaves G alone, giving D5*Z/2, else we have the direct product Z/5*Z/2*Z/2.  That's another 2 groups, hence there are 5 groups of order 20, up to isomorphism.

The Burnside Counting Theorem Table of Contents Start of chapter

Let G act on S, and let χ(a) be the number of elements in S fixed by the permutation associated with a in G.  Count the number of pairs [a,b], where a is in G and b is in S, and the permutation of a fixes b.  Clearly this is the sum of χ(a).  It is also the sum of the size of the stabilizer of b, for all b in S.

Every orbit contributes orbit size times stabilizer size, or |G|.  Therefore the total is |G| times the number of orbits.  The sum of χ(a) is |G| times the number of orbits.  If G acts transitively, then the sum is |G|.

Another form of the Burnside counting theorem lets G act on S cross S by permuting the individual components as before.  The number of elements fixed by a is now χ(a)2.  The sum of χ(a)2 is equal to the number of orbits times |G|, as before.  If the action is doubly transitive, every pair is mapped to every other pair, so only two orbits are present, seeded by [x,x] and [x,y].  The sum of χ(a)2 = 2讄G|.

The Burnside Polya Theorem Table of Contents Start of chapter

Let G be a permutation group on points, and let each point have one of k colors assigned.  The number of distinct color assignments, relative to G, can often be calculated.  The Burnside Polya theorem gives us a formula, a polynomial in k.

Two assignments are distinct if no group operation transforms one assignment into the other.  For instance, we might wish to count the number of distinct cubes where each face is painted one of three colors.  Two patterns are not distinct if we can simply rotate the cube to flip between them.  All the patterns with 5 faces red and one face blue are essentially the same.

Let S be the set of all possible color assignments, in our example, 3 colors per face = 36.  Now each orbit in S is a distinct pattern.  One assignment in S is rrrrrb, for red red red red red blue.  A rotation in G turns this into rrrbrr, part of the same orbit, and the same colored cube.  The orbit has size 6, with a stabilizer of 4, i.e. rotation around the blue.  We want to count the orbits.

There are 24 rotations of the cube, hence |G| = 24.  Apply the burnside counting theorem, and the number of orbits, or distinct cubes, is the sum of χ(a) |G|.

The number of patterns preserved by a rotation is always some power of k, so the resulting expression is a polynomial in k.  For a given rotation of the cube, we only need know the cycles.  If a rotation leaves the top and bottom fixed, and spins the other 4 faces clockwise 90, we have two trivial cycles (top and bottom) and a 4 cycle.  This rotation fixes k3 color assignments, one color for the top, one for the bottom, and one for the four sides around.

Review the notation for describing permutations as cycles, then verify that the cubes 24 rotations have the following cycle decomposition.  Each rotation has an axis, so run an axis through opposite corners, edges, or faces, and spin the cube from there.

c16 + 8c32 + 6c12c4 + 3c12c22 + 6c23

Note that the coefficients sum to 24.

If a transformation has 3 cycles, like the 90 rotation through top and bottom described earlier, it fixes k3 color combinations.  In general, we only need count the number of cycles in a permutation.  Apply this to the decomposition above to get:

( k6 + 3k4 + 12k3 + 8k2 ) / 24

set k = 1, for 1 color, and the number of distinct cubes is 24/24, or 1.  There are 10 cubes with two colors, 57 cubes with three colors, and 240 cubes with four colors.  Enumerate the 10 cubes with two colors; it's not hard.

Consider another example, a necklace with 13 beads.  Beads can be any of k colors.  The group acting on the beads is the dihedral group D13.  Two necklaces aren't really different if you can spin one around or flip it over to make it look like the other.  Here is the cycle decomposition, followed by the formula for k colors.

c113 + 12c13 + 13c1c26

(k13 + 13k7 + 12k) / 26

There are 380 necklaces with just 2 colors, and you have to admit, it would take you quite a while to verify this by hand.  Colored necklaces will be analyzed in the next section.

When patterns have additional constraints, simple color polynomials p(k) may not suffice.  Still, the rotation group often provides the solution.

Imagine we are coloring the faces of a cube with three colors, but we must use all three colors.  Terms like c32 degenerate to 0, since they cannot accommodate three colors.  Terms like c16 cannot be replaced with 36, since some combinations do not use all three colors.  Use inclusion exclusion to compute:

c16 = 36 - 326 + 316 = 540

The number of three colored cubes with all three colors represented is therefore (540 + 336 + 126) / 24, or 30.  Other constraints can be incorporated in this manner.

Colored Necklaces Table of Contents Start of chapter

In the earlier necklace example, I chose a prime number for simplicity.  When n has factors, some of the rotations split into smaller cycles.

Let a necklace have n beads, each assigned one of k colors.  Let d divide n and rotate by d.  As you step from 0 to d to 2d to 3d etc, you eventually reach g, the gcd of d and n.  Ratchet d back down to g, a divisor of n.  This gives a cycle of length n/d, and there are d of them running in parallel.  The same thing happens for ud, where u is coprime to n/d.  There are φ(n/d) rotations, having d cycles, each of length n/d.  Reverse the roles of d and n/d and get the following formula.

∑ (d divides n) φ(d)譪dn/d

( ∑ (d divides n) φ(d)kn/d ) n

If we allow reflections, flipping the necklace over, the additional permutations depend on the parity of n.  Each flip spins about a diameter, passing through two opposite beads (even), or two connectors (even), or a bead and its opposite connector (odd).  A ring of length 2n contributes nc2n + nc12c2n-1, while a ring of length 2n+1 contributes (2n+1)c1c2n.  The latter formula was used when the necklace had 13 beads.

How many necklaces have 6 beads and 3 colors?  Substitute 3 in the following to get 92.

(k6 + k3 + 2k2 + 2k + 3k4 + 3k3) / 12

Regular / Platonic Solids Table of Contents Start of chapter

Plato felt that everything in this world was a mere shadow of perfection.  The tree you are looking at is not perfect, a broken branch here, peeling bark there, but it is a reflection of a perfect tree, a platonic tree, in the spiritual world.  We still retain the adjective platonic, though it is generally restricted to relationships.  A platonic relationship is pure love, like the gods, and is unsulleyed by lust and sex.

Hmm.  Not my idea of perfection, but oh well.

Platonic solids, or regular solids, are perfect in form.  Each face is a regular n-gon, and all faces look alike.  There are infinitely many n-gons, but there are only five regular solids.  If you want to hold them in your hand, buy the game Dungeons and Dragons.  The five dice are the five platonic solids.

At every vertex, three or more faces meet, and their angles must sum to something less than 360.  If the chosen n-gon is a hexagon or higher, three interior angles sum to 360 or more, hence they can't fit together to make a corner.  Platonic solids are based on the triangle, square, or pentagon.

Let's start with the triangle.  If three triangles meet at a corner then a fourth triangle completes the shape.  This is called a tetrahedron, 4 faces, 6 edges, 4 vertices.

Let four triangles meet at each corner.  This is called an octahedron, 8 faces, 12 edges, 6 vertices.

Let five triangles meet at each corner.  This is called an icosahedron, 20 faces, 30 edges, 12 vertices.

If 6 or more triangles meet at a point, the angles sum to 360 or more, so lets move on to squares.

Let three squares meet at each corner.  This is called a cube, 6 faces, 12 edges, 8 vertices.

Let three pentagons meet at each corner.  This is called a dodecahedron, 12 faces, 30 edges, 20 vertices.

[ Picture of the 5 regular solids ]

The cube generalizes to higher dimensions.  It is called a hypercube, and has coordinates running from 0 to 1 along all n axes.  There are 2n faces and 2n vertices.

The generalized octahedron has diameters running from -1 to 1 along each axis.  There are 2n faces and 2n vertices.

The tetrahedron is defined by 4 points, each one unit from the other 3 in 3-space.  Add a dimension, and there is now room for another vertex, 1 unit away from the other 4.  Continue up to n dimensions, where the tetrahedron has n+1 faces and n+1 vertices.

Euler's Formula Table of Contents Start of chapter

Draw a connected graph in the plane, consisting of vertices and edges, such that edges do not cross.  Whenever edges run around in a cycle, they enclose a region that is called a face.  For example, the square with one diagonal drawn in has 4 vertices, 5 edges, and 2 triangular faces.

To keep things simple, let the exterior of a graph also be a face.  This is the region that goes on forever, extending out to infinity.  Thus the outside of our square with a diagonal is another face, giving 4 vertices, 5 edges, and 3 faces.

Euler's formula asserts v - e + f = 2, where v is vertices, e is edges, and f is faces.  Verify this for the example sited above.

Prove this by induction on the number of edges.

If the graph has an endpoint, remove that point and its edge, which does not change v - e + f at all.

If there are no endpoints, then start at an edge, and walk around a cycle, always taking the edge immediately to your right at each vertex.  The graph is finite, so you have to return to start.  The region that you just walked around is a face.  There is nothing else inside the face, because our graph is connected.  Anything inside this face would be disconnected from the cycle that you just walked around.  Remove an edge, and the face to your right, that you just walked around, joins the face to your left to make one larger face.  Edges and faces both decrease by 1, and v - e + f is unchanged.

After all the edges have been removed, you are left with one point and one face in the plane, whence v - e + f = 2.

Close the plane up at the point of infinity to make a sphere.  The face that was the exterior of the graph is now a proper face on the sphere.  Once again, v - e + f = 2.

Euler's formula must be adjusted for other surfaces.  Consider the torus, which looks like an innertube or a doughnut.  This can be represented by a square.  Imagine curling up a piece of paper until the left and right edges meet, giving a tube.  Then curl the tube around (you can't really do this with paper) until the top and bottom circles meet; that is a torus.  So a torus is a square with wrap-around on the left and right edges, and wrap-around on the top and bottom edges.  In topological terms, these edges are sewn together.

Given such a square, or torus, place a vertex at the lower left corner and draw an edge from the lower left to the lower right, which is really a loop around the tube, a loop from the vertex back to itself.  Draw another edge, another loop, up the left edge.  You now have one vertex, two edges, and one face, giving v - e + f = 0.  The face that you see has been established by the two edges, and is effectively a square in the plane.  There is no wrap-around any more, because you can't cross an edge.  From here, edges and vertices can be added to build a larger graph, without changing v - e + f, as described above.  Therefore Euler's formula comes out 0 on the torus, as long as your graph takes advantage of both paths around.

Other surfaces are possible, but are beyond the scope of this book.

Returning to the sphere, Use Euler's formula to count the vertices, edges, and faces of a regular or semiregular polyhedron, even before it is constructed.  First, push the edges of a polyhedron outward until they touch the sphere.  I'll illustrate with the octahedron.  Balance an octahedron on its point, so that the bottom vertex is the south pole and the top vertex is the north pole.  The other four corners touch the equator at 90 intervals.  Now push the edges out towards the sphere.  The four horizontal edges become the equator and the vertical edges become lines of longitude that connect the equator with the north or south pole.  A face on the octahedron becomes a section of the sphere, like a piece of orange peel.

Once the solid is mapped onto the sphere, you can apply Euler's formula, which says v - e + f = 2.

Here's an example out of thin air.  Let each corner consist of a pentagon and two squares.  This adds up to less then 360, so we're ok.

Each vertex has three edges coming into it, and each edge is counted twice (two end points), so the number of edges is 3v/2.

Turning to faces, each vertex consumes one fifth of a pentagon and two quarters of a square.  Thus f = v/5 + 2v/4 = 7v/10.  Apply Euler's formula and get v - 3v/2 + 7v/10 = 2, thus v = 10.  There are ten corners, two pentagons, and 5 squares.  The shape has a pentagon floor and ceiling, and five square walls around.

You can count the faces edges and corners of any shape, as long as you know what each corner looks like, and all the corners are the same.  These shapes are analyzed below.

The Dual of a Polyhedron Table of Contents Start of chapter

When a polyhedron is mapped onto a sphere, it looks like a map of countries.  Replace each country with a dot and draw edges between the dots that represent neighboring countries.  A ring of dots and edges surrounds what use to be a vertex.  Thus corners have become faces and faces have become corners.  The new edges run perpendicular to the old edges, hence there are just as many edges as before.  With v and f swapped, v - e + f is still 2, as it should be.  This process creates the dual of a polyhedron.  It is called the dual because the dual of the dual resurrects the original graph.  I'll illustrate with the octahedron.

Stand the octahedron up on one corner as we did before.  Four faces are turned upward to the sky and for faces are slanted down.  Now place a dot in the center of each face.  Connect the four dots on top in a square, since those four faces form a ring.  Similarly connect the bottom four dots in a square.  Finally connect each top dot to its dot below.  You have drawn a cube.  Each face of the cube contains a vertex from the octahedron, just as each corner of the cube sits in the middle of a face of the octahedron.  As an exercise, draw the dual of the cube, placing a vertex in the middle of each square face, and get the octahedron back again.

The dodecahedron and icosahedron are dual, and the tetrahedron is its own dual.

Semiregular / Archimedean Solids Table of Contents Start of chapter

Archimedes appreciated the beauty and perfection of the platonic solids, but he grew tired of seeing the same old five shapes.  He wanted a bit more variety.  So he developed the Archimedean solids, also called the semiregular solids.

A semiregular solid consists of n-gons pasted together so that vertices are indistinguishable.  This means each corner consists of the same n-gons, in the same clockwise order.  The regular solids are semiregular, but there are many more.

Take two copies of an n-gon and make one the floor and one the ceiling.  Connect them via n square walls around.  This is called a gonal prism.  Each vertex joins an n-gon and two squares.  When n = 4 you have the cube.  When n = 5 you have the pentagonal room that was described earlier.

The dual of a semiregular solid need not be semiregular.  The dual of a gonal prism produces n triangles on top and n triangles below.  The top and bottom vertices each connect n triangles, while the ring of vertices at the equator each have four incident triangles.  However, the faces of the dual are indistinguishable, just as the vertices of the original shape were indistinguishable.

Take the aforementioned n-gons, floor and ceiling, and twist the ceiling just a bit, so that the points of the ceiling float above the edges of the floor.  Let equilateral triangles connect the edges on the floor with the points above.  Similarly, let equilateral triangles connect the edges above with the points below.  This is the anti-gonal prism.  Pull the floor and ceiling apart and it looks like the mouth of a wild animal.  The triangle teeth point up and down, and mesh perfectly.  Every corner joins an n-gon with three triangles, hence the shape is semiregular.

The soccer ball is a semiregular solid with formula [5,6,6].  If you have one in your house, go get it and look at it.  Every vertex joins a pentagon and two hexagons.  Compute the number of faces using Euler's formula.  There are v vertices, 3v/2 edges, and v/5+2v/6 faces.  This yields 60 vertices, 90 edges, and 32 faces - thus 12 pentagons and 20 hexagons.

Some semiregular solids come from regular solids.  Consider the process of truncation.  Given a regular solid, take a file and file down the corners until all edges have the same (shorter) length.  Let's illustrate with the cube.  A cube has 8 corners; file them down to make 8 triangles.  The six faces of the cube, which use to be square, have become octagons.  This is called a truncated cube.  Each vertex connects two octagons and one triangle.

[ picture of truncated cube ]

File a regular solid further, until the original edges disappear.  The original faces remain, preserving the structure of the regular solid, and the new faces, corresponding to the vertices, reflect the structure of the dual.  This is a hybrid shape, named for the regular solid and its dual.  File the corners of the cube down until the original edges shrink to zero.  Each corner has become a triangle and each face has become a square standing on its point.  This is the cuboctahedron.  Start with the octahedron and apply the same process, and get the cuboctahedron again.

[ picture of cuboctahedron ]

File the corners and edges down simultaneously to get a rounder, or rhombic form of the original shape.  File the corners of a cube down to triangles, and the edges of the cube to squares, whence the original faces become smaller squares.  This shape is [3,4,4,4], and is called the rhombic cuboctahedron.  It isn't called the rhombic cube, because you can perform the same operation to the octahedron and get the same shape, hence it is the rhombic cuboctahedron.

[ picture of rhombic cuboctahedron ]

You don't have to worry about the rhombictetrahedron; it is the same as the cuboctahedron.

Finally we have the snub operation.  Start with the cuboctahedron, which consists of squares and triangles.  Pull these faces apart, leaving gaps between.  Now turn all the faces clockwise just a bit.  In other words, each face turns clockwise as you look down on it from outside the shape.  If two squares and two triangles use to meet at a vertex, they turn in synchrony to create a diamond gap.  Fill this gap with two triangles.  The cuboctahedron had 12 vertices, and each creates a diamond gap, thus there are 24 new triangle faces.  The original shape had 14 faces, hence the snub cuboctahedron has 24+14 = 38 faces.  There is also a snub icosidodecahedron with 230+32 = 92 faces.  These are presented in the table below.

[ picture of snub cuboctahedron ]

The snub shapes are the only semiregular solids that exhibit chirality.  In other words, they come in left and right handed versions.  Turn the faces clockwise, as described above, and find the right handed version (an arbitrary convention).  Turn the faces counterclockwise and find the left handed version.  Reflect one version through a plane, or through the origin, to find the other.

Have we described all the semiregular solids?  Put various n-gons together at a corner and find out.  But first, a lemma.

Suppose each vertex joins a pentagon, a triangle, and two squares, in that order: [5,3,4,4].  Walk around the pentagon and the edges border a triangle, a square, a triangle, a square, a triangle, and then we're in trouble, because the sixth edge is the first edge, and it must border a triangle and a square simultaneously.  This is the walk around test, and it forces the two numbers on either side of an odd number to be the same.  Thus [5,3,4,4] is invalid, from the perspective of the pentagon or the triangle, but [5,4,3,4] is fine.

To get things started, assume each vertex meets something higher than an octagon.  The high shape x consumes 140 or more.  Note that x cannot join four other shapes at a vertex, and if it joins three other shapes, two of them must be triangles.  If the third is a triangle we have the anti-gonal prism.  If the third is a square, [x,3,4,3] and [x,4,3,3] both fail the walkaround test.  If the third is a pentagon the angles exceed 360.  Thus x meets two other shapes.

If one is a triangle the other must be x, which is valid for x < 12.  Yet if x is odd, and greater than 3, it fails the walk around test.  Therefore the semiregular solid [x,3,x] is valid for x = 3, 4, 6, 8, 10.  That takes care of x meeting a triangle.

Without a triangle, x meets squares or higher.  If x meets two squares we have the gonal prism.  The shape [x,4,5] fails the walkaround test, and [x,4,6] fails the walk around test when x = 9 or 11.  The pattern [10,4,6] is valid.  Finally, [x,5,5] fails the walk around test, and [x,5,6] is too big.  Hereinafter we can restrict attention to octagons and below.

If the octagon meets three other shapes, two of them are triangles.  Let the third be a square, to avoid the anti-gonal prism.  Yet [8,3,4,3] and [8,3,3,4] fail the walkaround test, so the octagon meets two other shapes.  If one of them is odd then the other is an octagon, and that only leaves room for a triangle.  This is [8,8,3], the truncated cube.  If the octagon meets two even shapes, one of them is a square.  To avoid the gonal prism, the other is a hexagon.  This is another valid shape.  That takes care of the octagon.

If a heptagon, 7 sides, meets three shapes, two of them are triangles.  (No room for a triangle and two squares.)  The third creates the anti-gonal prism, or fails the walkaround test, hence the heptagon meets two other shapes.  Since 7 is odd, these shapes are equal.  They must be even, else we fail the walkaround test.  Skip the squares (gonal prism) and move to hexagons, but that introduces too much angle.

If a pentagon meets two other shapes they too are pentagons, or they are copies of an even shape, a square (gonal prism) or a hexagon (soccer ball).  If the pentagon meets four other shapes they are triangles, and that is valid.  If the pentagon meets three other shapes, at least one is a triangle.  If the second is a triangle, the third should not be a triangle, else we have an anti-gonal prism.  Note that [5,3,3,4] [5,3,4,3] [5,3,3,5] [5,3,3,6] [5,3,6,3] all fail the walkaround test.  That leaves [5,3,5,3], which is valid.  If the second shape is a square then so is the third.  Since [5,3,4,4] fails, we are left with [5,4,3,4], which is valid.  That's it for the pentagon.

Join two hexagons with a triangle or a square; both are valid.  Hereinafter there is at most one hexagon; everything else being squares or triangles.

If a hexagon meets two shapes, one cannot be a triangle, so we're talking about two squares, the gonal prism.  If the hexagon meets 3 other shapes, the first two are triangles.  Make the third a square, avoiding the anti-gonal prism.  Yet [6,3,3,4] and [6,3,4,3] both fail the walkaround test.  That's it for the hexagon.

Three squares and a triangle - that works.  Two squares and two triangles makes the shape [4,3,4,3].  One square joins 4 triangles to make a snub solid.

Bring in the platonics, and that's all the semiregular solids.  They are presented in the table below.

Name Pattern Vertices Edges Faces
Gonal Prism [n,4,4] 2n 3n n+2
Anti-gonal Prism [n,3,3,3] 2n 4n 2n+2
Tetrahedron [3,3,3] 4 6 4
Cube [4,4,4] 8 12 6
Octahedron [3,3,3,3] 6 12 8
Dodecahedron [5,5,5] 20 30 12
Icosahedron [3,3,3,3,3] 12 30 20
Truncated Tetrahedron [6,6,3] 12 18 8
Truncated Cube [8,8,3] 24 36 14
Truncated Octahedron [6,6,4] 24 36 14
Truncated Dodecahedron [10,10,3] 60 90 32
Truncated Icosahedron [6,6,5] 60 90 32
Cuboctahedron [4,3,4,3] 12 24 14
Icosidodecahedron [5,3,5,3] 30 60 32
Truncated Cuboctahedron [8,6,4] 48 72 26
Truncated Icosidodecahedron [10,6,4] 120 180 62
Rhombic Cuboctahedron [4,4,4,3] 24 48 26
Rhombic Icosidodecahedron [5,4,3,4] 60 120 62
Snub Cuboctahedron [4,3,3,3,3] 24 60 38
Snub Icosidodecahedron [5,3,3,3,3] 60 150 92

Rotations and Reflections of the Semiregular Solids Table of Contents Start of chapter

How many ways can you color the faces of a semiregular solid with k colors, allowing for rotations?  How many ways allowing for rotations and reflections?  (Reflections are a bit impractical, since you can't reflect a solid object through a mirror.)  The following table lists the solids, the number of faces, the formula at each vertex, two permutations that generate the rotations, an additional permutation that implements reflection, The cycle decomposition for the rotation group, a polynomial in k for the number of k-color patterns, The cycle decomposition for the rotation / reflection group, and a polynomial in k for the number of k-color patterns.  I number the faces starting at 0, usually at the top, then going around in bands.  A rotation about one axis, and a rotation about another, is sufficient to generate the rotation group.  A computer program cranks out all the rotations, finds the cycles, and derives the polynomial.  One more permutation generates the reflections, and the computer once again cranks out the cycles and the polynomial.  This is an application of the Burnside Polya theorem, which was presented earlier in this chapter.

Each rotation spins the object about an axis, but a "reflection" is not always a simple reflection through a mirror; sometimes a follow-on rotation is required.  The anti-gonal prism is the perfect example.  A pure reflection has to exchange the floor and the ceiling.  This places the mirror parallel to, and midway between, the floor and the ceiling.  However, this reflection leaves the vertices misaligned.  The actual transformation is a vertical reflection followed by a rotation of 180/2n degrees.


name
the number of faces and a list of n-gons that meet at each vertex
a permutation determining a rotation about an axis
a second permutation determining a rotation about an independent axis
an additional permutation determining a reflection
the rotation group, in terms of cycles
the number of possible solids with k colors
the rotation / reflection group, in terms of cycles
the number of possible non-chyral shapes with k colors


tetrahedron
4: [3,3,3]
[1 2 0 3]
[0 3 1 2]
[1 0 2 3]
c14 + 8c1c3 + 3c22
(k4 + 11k2) / 12
c14 + 6c12c2 + 8c1c3 + 3c22 + 6c4
(k4 + 6k3 + 11k2 + 6k) / 24


cube
6: [4,4,4]
[0 2 3 4 1 5]
[1 5 2 0 4 3]
[5 1 2 3 4 0]
c16 + 3c12c22 + 6c12c4 + 6c23 + 8c32
(k6 + 3k4 + 12k3 + 8k2) / 24
c16 + 3c14c2 + 9c12c22 + 6c12c4 + 7c23 + 6c2c4 + 8c32 + 8c6
(k6 + 3k5 + 9k4 + 13k3 + 14k2 + 8k) / 48


octahedron
8: [3,3,3,3]
[1 2 3 0 5 6 7 4]
[4 5 1 0 7 6 2 3]
[1 0 3 2 5 4 7 6]
c18 + 8c12c32 + 9c24 + 6c42
(k8 + 17k4 + 6k2) / 24
c18 + 6c14c22 + 8c12c32 + 13c24 + 8c2c6 + 12c42
(k8 + 6k6 + 21k4 + 20k2) / 48


dodecahedron
12: [5,5,5]
[0 2 3 4 5 1 7 8 9 10 6 11]
[1 6 2 0 5 10 7 3 4 9 11 8]
[11 10 6 7 8 9 1 2 3 4 5 0]
c112 + 24c12c52 + 15c26 + 20c34
(k12 + 15k6 + 44k4) / 60
c112 + 15c14c24 + 24c12c52 + 16c26 + 24c2c10 + 20c34 + 20c62
(k12 + 15k8 + 16k6 + 44k4 + 44k2) / 120


icosahedron
20: [3,3,3,3,3]
[0 4 5 6 7 8 9 1 2 3 13 14 15 16 17 18 10 11 12 19]
[1 0 7 8 9 10 11 2 3 4 5 6 16 17 18 19 12 13 14 15]
[19 18 10 11 12 13 14 15 16 17 8 9 1 2 3 4 5 6 7 0]
c120 + 20c12c36 + 15c210 + 24c54
(k20 + 15k10 + 20k8 + 24k4) / 60
c120 + 15c14c28 + 20c12c36 + 16c210 + 20c2c63 + 24c54 + 24c102
(k20 + 15k12 + 16k10 + 20k8 + 44k4 + 24k2) / 120


truncated tetrahedron
8: [3,6,6]
[0 2 3 1 4 6 7 5]
[1 2 0 3 5 6 4 7]
[0 1 3 2 4 5 7 6]
c18 + 8c12c32 + 3c24
(k8 + 11k4) / 12
c18 + 6c14c22 + 8c12c32 + 3c24 + 6c42
(k8 + 6k6 + 11k4 + 6k2) / 24


truncated cube
14: [3,8,8]
[0 2 3 4 1 5 7 8 9 6 11 12 13 10]
[1 5 2 0 4 3 7 11 12 8 6 10 13 9]
[5 1 2 3 4 0 10 11 12 13 6 7 8 9]
c114 + 3c12c26 + 8c12c34 + 6c12c43 + 6c27
(k14 + 3k8 + 6k7 + 8k6 + 6k5) / 24
c114 + 6c16c24 + 3c14c25 + 3c12c26 + 8c12c34 + 6c12c43 + 7c27 + 6c2c43 + 8c2c62
(k14 + 6k10 + 3k9 + 3k8 + 7k7 + 8k6 + 6k5 + 6k4 + 8k3) / 48


truncated octahedron
14: [4,6,6]
[0 2 3 4 1 5 7 8 9 6 11 12 13 10]
[1 5 2 0 4 3 7 11 12 8 6 10 13 9]
[5 1 2 3 4 0 10 11 12 13 6 7 8 9]
c114 + 3c12c26 + 8c12c34 + 6c12c43 + 6c27
(k14 + 3k8 + 6k7 + 8k6 + 6k5) / 24
c114 + 6c16c24 + 3c14c25 + 3c12c26 + 8c12c34 + 6c12c43 + 7c27 + 6c2c43 + 8c2c62
(k14 + 6k10 + 3k9 + 3k8 + 7k7 + 8k6 + 6k5 + 6k4 + 8k3) / 48


truncated dodecahedron
32: [3,10,10]
[0 2 3 4 5 1 7 8 9 10 6 11 13 14 15 16 12 18 19 20 21 17 23 24 25 26 22 28 29 30 31 27]
[1 6 2 0 5 10 7 3 4 9 11 8 17 12 16 21 22 23 13 15 26 27 28 18 14 20 31 29 24 19 25 30]
[11 10 6 7 8 9 1 2 3 4 5 0 27 28 29 30 31 22 23 24 25 26 21 17 18 19 20 16 12 13 14 15]
c132 + 20c12c310 + 24c12c56 + 15c216
(k32 + 15k16 + 20k12 + 24k8) / 60
c132 + 15c18c212 + 20c12c310 + 24c12c56 + 16c216 + 20c2c65 + 24c2c103
(k32 + 15k20 + 16k16 + 20k12 + 24k8 + 20k6 + 24k4) / 120


truncated icosahedron (soccer ball)
32: [5,6,6]
[0 2 3 4 5 1 7 8 9 10 6 11 13 14 15 16 12 18 19 20 21 17 23 24 25 26 22 28 29 30 31 27]
[1 6 2 0 5 10 7 3 4 9 11 8 17 12 16 21 22 23 13 15 26 27 28 18 14 20 31 29 24 19 25 30]
[11 10 6 7 8 9 1 2 3 4 5 0 27 28 29 30 31 22 23 24 25 26 21 17 18 19 20 16 12 13 14 15]
c132 + 20c12c310 + 24c12c56 + 15c216
(k32 + 15k16 + 20k12 + 24k8) / 60
c132 + 15c18c212 + 20c12c310 + 24c12c56 + 16c216 + 20c2c65 + 24c2c103
(k32 + 15k20 + 16k16 + 20k12 + 24k8 + 20k6 + 24k4) / 120


cuboctahedron
14: [3,4,3,4]
[0 2 3 4 1 5 7 8 9 6 11 12 13 10]
[1 5 2 0 4 3 7 11 12 8 6 10 13 9]
[5 1 2 3 4 0 10 11 12 13 6 7 8 9]
c114 + 3c12c26 + 8c12c34 + 6c12c43 + 6c27
(k14 + 3k8 + 6k7 + 8k6 + 6k5) / 24
c114 + 6c16c24 + 3c14c25 + 3c12c26 + 8c12c34 + 6c12c43 + 7c27 + 6c2c43 + 8c2c62
(k14 + 6k10 + 3k9 + 3k8 + 7k7 + 8k6 + 6k5 + 6k4 + 8k3) / 48


icosidodecahedron
32: [3,5,3,5]
[0 2 3 4 5 1 7 8 9 10 6 11 13 14 15 16 12 18 19 20 21 17 23 24 25 26 22 28 29 30 31 27]
[1 6 2 0 5 10 7 3 4 9 11 8 17 12 16 21 22 23 13 15 26 27 28 18 14 20 31 29 24 19 25 30]
[11 10 6 7 8 9 1 2 3 4 5 0 27 28 29 30 31 22 23 24 25 26 21 17 18 19 20 16 12 13 14 15]
c132 + 20c12c310 + 24c12c56 + 15c216
(k32 + 15k16 + 20k12 + 24k8) / 60
c132 + 15c18c212 + 20c12c310 + 24c12c56 + 16c216 + 20c2c65 + 24c2c103
(k32 + 15k20 + 16k16 + 20k12 + 24k8 + 20k6 + 24k4) / 120


truncated cuboctahedron
26: [4,6,8]
[0 2 3 4 1 5 7 8 9 6 11 12 13 10 15 16 17 14 19 20 21 18 23 24 25 22]
[1 5 2 0 4 3 7 11 12 8 6 10 13 9 16 23 20 24 14 22 18 25 15 19 21 17]
[5 1 2 3 4 0 10 11 12 13 6 7 8 9 18 19 20 21 14 15 16 17 22 23 24 25]
c126 + 9c12c212 + 8c12c38 + 6c12c46
(k26 + 9k14 + 8k10 + 6k8) / 24
c126 + 9c18c29 + 9c12c212 + 8c12c38 + 6c12c46 + c213 + 6c2c46 + 8c2c64
(k26 + 9k17 + 9k14 + k13 + 8k10 + 6k8 + 6k7 + 8k5) / 48


truncated icosidodecahedron
62: [4,6,10]
[0 2 3 4 5 1 7 8 9 10 6 11 13 14 15 16 12 18 19 20 21 17 23 24 25 26 22 28 29 30 31 27 33 34 35 36 32 38 39 40 41 37 44 45 46 47 48 49 50 51 42 43 53 54 55 56 52 58 59 60 61 57]
[1 6 2 0 5 10 7 3 4 9 11 8 17 12 16 21 22 23 13 15 26 27 28 18 14 20 31 29 24 19 25 30 42 37 32 41 51 43 33 36 50 52 53 44 38 34 35 40 49 56 61 57 58 45 39 48 60 54 46 47 55 59]
[11 10 6 7 8 9 1 2 3 4 5 0 27 28 29 30 31 22 23 24 25 26 21 17 18 19 20 16 12 13 14 15 61 57 58 59 60 52 53 54 55 56 51 42 43 44 45 46 47 48 49 50 41 37 38 39 40 32 33 34 35 36]
c162 + 15c12c230 + 20c12c320 + 24c12c512
(k62 + 15k32 + 20k22 + 24k14) / 60
c162 + 15c112c225 + 15c12c230 + 20c12c320 + 24c12c512 + c231 + 20c2c610 + 24c2c106
(k62 + 15k37 + 15k32 + k31 + 20k22 + 24k14 + 20k11 + 24k7) / 120


rhombicuboctahedron
26: [3,4,4,4]
[0 2 3 4 1 5 7 8 9 6 11 12 13 10 15 16 17 14 19 20 21 18 23 24 25 22]
[1 5 2 0 4 3 7 11 12 8 6 10 13 9 16 23 20 24 14 22 18 25 15 19 21 17]
[5 1 2 3 4 0 10 11 12 13 6 7 8 9 18 19 20 21 14 15 16 17 22 23 24 25]
c126 + 9c12c212 + 8c12c38 + 6c12c46
(k26 + 9k14 + 8k10 + 6k8) / 24
c126 + 9c18c29 + 9c12c212 + 8c12c38 + 6c12c46 + c213 + 6c2c46 + 8c2c64
(k26 + 9k17 + 9k14 + k13 + 8k10 + 6k8 + 6k7 + 8k5) / 48


rhombicosidodecahedron
62: [3,4,5,4]
[0 2 3 4 5 1 7 8 9 10 6 11 13 14 15 16 12 18 19 20 21 17 23 24 25 26 22 28 29 30 31 27 33 34 35 36 32 38 39 40 41 37 44 45 46 47 48 49 50 51 42 43 53 54 55 56 52 58 59 60 61 57]
[1 6 2 0 5 10 7 3 4 9 11 8 17 12 16 21 22 23 13 15 26 27 28 18 14 20 31 29 24 19 25 30 42 37 32 41 51 43 33 36 50 52 53 44 38 34 35 40 49 56 61 57 58 45 39 48 60 54 46 47 55 59]
[11 10 6 7 8 9 1 2 3 4 5 0 27 28 29 30 31 22 23 24 25 26 21 17 18 19 20 16 12 13 14 15 61 57 58 59 60 52 53 54 55 56 51 42 43 44 45 46 47 48 49 50 41 37 38 39 40 32 33 34 35 36]
c162 + 15c12c230 + 20c12c320 + 24c12c512
(k62 + 15k32 + 20k22 + 24k14) / 60
c162 + 15c112c225 + 15c12c230 + 20c12c320 + 24c12c512 + c231 + 20c2c610 + 24c2c106
(k62 + 15k37 + 15k32 + k31 + 20k22 + 24k14 + 20k11 + 24k7) / 120


snub cuboctahedron
38: [4,3,3,3,3]
[0 2 3 4 1 5 7 8 9 6 11 12 13 10 15 16 17 14 19 20 21 18 23 24 25 22 27 28 29 26 31 32 33 30 35 36 37 34]
[1 5 2 0 4 3 7 11 12 8 6 10 13 9 30 26 22 34 32 36 24 28 18 35 14 29 19 23 17 33 20 27 16 37 21 31 15 25]
??? the reflection is a different polyhedron
c138 + 3c12c218 + 8c12c312 + 6c12c49 + 6c219
(k38 + 3k20 + 6k19 + 8k14 + 6k11) / 24


snub icosidodecahedron
92: [5,3,3,3,3]
[0 2 3 4 5 1 7 8 9 10 6 11 13 14 15 16 12 18 19 20 21 17 23 24 25 26 22 28 29 30 31 27 33 34 35 36 32 38 39 40 41 37 43 44 45 46 42 48 49 50 51 47 53 54 55 56 52 58 59 60 61 57 63 64 65 66 62 68 69 70 71 67 73 74 75 76 72 78 79 80 81 77 83 84 85 86 82 88 89 90 91 87]
[1 6 2 0 5 10 7 3 4 9 11 8 17 12 16 21 22 23 13 15 26 27 28 18 14 20 31 29 24 19 25 30 52 42 37 47 57 62 48 32 46 67 68 38 36 56 77 72 58 33 41 66 78 43 35 61 86 82 53 34 51 76 73 49 40 71 91 87 63 39 45 81 83 59 50 65 90 88 69 44 55 85 79 54 60 75 89 74 64 70 80 84]
??? the reflection is a different polyhedron
c192 + 20c12c330 + 24c12c518 + 15c246
(k92 + 15k46 + 20k32 + 24k20) / 60