The Math Thread

[lpetrich]

I find the theory of finite fields very elegant.

The simplest of them are Z(p), where p is a prime number.

The rest are constructed as polynomials sum over k from 0 to n-1 of a_k*x^k of a variable x, where the a_k are in Z(p).

The variable x is interpreted as satisfying a nth-degree monic polynomial P(x) with coefficients in Z(p). When one multiples two elements, one divides out P(x) and uses the remainder. P(x) should be a "irreducible polynomial", one that cannot be factored.

Monic polynomial: its highest-degree coefficient is 1. If it is some other value, then one can multiply the polynomial by that value's multiplicative inverse to make the polynomial monic. Unlike the situation with rational-number coefficients.

Finite fields are often called GF(p^n) ("Galois Field"). GF(p) = Z(p). Every field GF(p^n) has subfields GF(p^m) where m evenly divides n.

To within isomorphisms, there is only one field with order p^n. That means that one can choose whatever primitive polynomial one wants for P(x) above.

The field's addition group is Z(p)^n, while its multiplication group is Z(p^n-1).

The number of irreducible polynomials in GF(p^n) is
(1/n) * sum over m that evenly divides n of μ(m) * p^n/m

μ is the Moebius mu function:
If n contains a square of a prime, 0
Otherwise, (-1)^(number of prime factors of n)

Also, μ = sum over k where gcd(k,n) = 1 of exp(2*pi*i*k/n) -- the primitive nth roots of unity

-

Some examples:
GF(p) -- irreducible polynomials x + k (0 <= k < p)
GF(4): 0, 1, x, x+1 -- irreducible polynomial x² + x + 1
GF(8): 0, 1, x, x+1, x², x²+1, x²+x, x²+x+1 -- irreducible polynomials x³+x+1, x³+x²+1
GF(9): 0, 1, 2, x, x+1, x+2, 2x, 2x+1, 2x+2 -- irreducible polynomials x²+1, x²+x+2, x²+2x+2

-

Do any of you know of any properties of fields GF(2^n) that make them especially suited for computer implementation?

 

[lpetrich]

Here goes. In a computer, polynomials can be handled implicitly, complete with doing arithmetic on them in implicit fashion, by manipulating their coefficients. Elements of GF(2^n) can be expressed as polynomials with coefficients in GF(2): 0 and 1. This has an obvious implementation as a bit, and the bits for a GF(2^n) element can be stored in packed fashion in a byte or a multibyte word, like a 16-bit integer.

GF(2) addition and subtraction have this operation table:
0 1
1 0
This is clearly the exclusive-or (xor) operation, and it can be done on several bits at once by most common CPU's. I checked on Intel-x86, PowerPC, Motorola-68K, SPARC, MIPS, ARM, and they all have it.

Multiplication is done by shifting and adding, though one has to divide out one's irreducible polynomial and use the remainder. That is done by shifting and subtracting.

One can find the irreducible polynomials for GF(2^n) by making all the candidates and then dividing out the irreducible polynomials for all GF(2^m) where m < n, though one can speed it up by doing only m <= n/2. Those fields' ones can be found in the same way.

One can speed up multiplication by creating a table of discrete logarithms. One does that by finding an element that generates the multiplicative group. All powers of it from 1 to 2^n-2 are elements other than 1. The power corresponding to each element is thus the discrete logarithm. One can also take reciprocals with that table.

 

[lpetrich]

One can find the smallest groups by listing their possible multiplication tables (or Cayley tables). There is a theorem that helps here: cancellation. a*b = a*c is equivalent to b = c. Multiply on the left by inv(a), and by associativity, it cancels with a. Thus every element enters only once in every row and every column.

The order-1 group is the identity group or the trivial group. Its table has only one element: e.

Now the order-2 groups. Start by filling in the identity operation:
e a
a .

By row and column uniqueness, the remaining entry must be e:
e a
a e
Thus getting Z2.

Now the order-3 groups.
e a b
a . .
b . .

The missing entries in the second row must be b and e, but the third column cannot contain another be. Thus,
e a b
a . e
b e .

It is easy to fill in the remaining ones:
e a b
a b e
b e a
Thus getting Z3.

For the order-4 groups, we start with
e a b c
a . . .
b . . .
c . . .

Let's try doing several possibilities at once.

e a b c   e a b c
a . . e   a . . b
b . . .   b . . .
c . . .   c . . .

The first one has only one possible fill-in, while the second one has two:

e a b c   e a b c   e a b c
a b c e   a e c b   a c e b
b . . .   b . . .   b . . .
c . . .   c . . .   c . . .

Now the second column. Each one has only one fill-in:

e a b c   e a b c   e a b c
a b c e   a e c b   a c e b
b c . .   b c . .   b e . .
c e . .   c b . .   c b . .

Now the third row. The first one has only one fill-in, while the second one has two fill-ins:

e a b c   e a b c   e a b c   e a b c
a b c e   a e c b   a e c b   a c e b
b c e a   b c e a   b c a e   b e c a
c e . .   c b . .   c b . .   c b . .

The fourth row is easy.

e a b c   e a b c   e a b c   e a b c
a b c e   a e c b   a e c b   a c e b
b c e a   b c e a   b c a e   b e c a
c e a b   c b a e   c b e a   c b a e

The first one is Z4, generated by a or c.
The second one is Z2*Z2, generated by any two of a, b, and c.
The third one is Z4, generated by b or c.
The fourth one is Z4, generated by a or b.

Thus, the only order-4 groups are Z4 and Z2*Z2.

It gets difficult to use this method for order-5 and higher, so one has to use some other techniques.

 

[lpetrich]

I've found this mathematics resource: ProofWiki, with the oo turned into the infinity symbol. Its description:

ProofWiki is an online compendium of mathematical proofs! Our goal is the collection, collaboration and classification of mathematical proofs. If you are interested in helping create an online resource for math proofs feel free to register for an account to contribute. Thanks and enjoy!

Now to finding what finite groups there are. If it has prime order p, then it is only Z(p). Proof:

The order of a group element is the order of the cyclic group that it generates. It evenly divides the order of the main group. But if the group's order is a prime, then the only non-unity divisor possible is the order itself. Thus, every non-identity element of a prime-order group will generate the group, making the group Z(p).

Now for all the groups with order p² for prime p. If an element has that order, then it makes the group Z(p²), so we consider the case of all nonidentity elements having order p. Can the group be nonabelian? If so, then its only possible conjugacy-class sizes are p and 1. Since the identity's class has size 1, then there must be some other elements with size-1 classes. Let's consider one, a. It commutes with all the other elements and it generates an order-p cyclic group. All the a^k also commute with all the other elements.

Now consider an element outside that cyclic group, b. If b^k = a^m, then there exists some r such that k*r = 1 mod p, and b = a^r*m, contrary to the premise. Now consider elements with the form b^k*a^m. There are p² of them, and thus every group element can be expressed in that form. It is easy to show that any two of them commute, and thus that the group is a product of the a-generated subgroup and the b-generated one. Thus giving Z(p)*Z(p).

Thus, if a group's order is p², then it can only be Z(p²) or Z(p)*Z(p).

But if a group's order is some higher power of p, then it may be nonabelian.

 

[lpetrich]

Here are some theorems about finite groups that I find rather interesting.


Cauchy's theorem. For every prime factor of a group's order, there is at least one element with that order. Thus, a group with order 30 has at least one element with order 2, at least one with order 3, and at least one with order 5.


The fundamental theorem of finite Abelian groups, as it's sometimes called. Every one breaks down into a product of cyclic groups with prime-power orders.

As to cyclic groups in general, Z = Z(n1)*Z(n2) where n = n1*n2 if and only if n1 and n2 are relatively prime (or coprime).


A bit of terminology. A p-group is a group with power-of-prime order. A group's center is all its elements that commute with every element in the group. A subgroup's centralizer is all the main group's elements that commute with it. A subgroup's normalizer is all the main group's elements that make conjugates of the subgroup's elements that stay in the subgroup.

A group's center has an interesting property of its representation matrices. For an irrep, recall that D(a).X = X.D(a) for all a implies that X is proportional to the identity matrix. If c is in the center, then D(a).D(c) = D(c).D(a), meaning that D(c) must be proportional to the identity matrix: D(c) = d(c)*I. Thus, the character of that element is χ(c) = d(c)*χ(e).

Every element in a group's center is the only element in its conjugacy class. Thus, a group being abelian is equivalent to the group's center being the entire group.


Now the Sylow theorems, named after mathematician Ludwig Sylow. There are different numberings of them in different places.

1. If a group has order pⁿ*m for some prime number p, then it has at least one Sylow p-subgroup, a subgroup with order pⁿ.

2. All of the main group's Sylow p-subgroups are conjugate, and every p-subgroup of the main group is a subgroup of some Sylow p-subgroup.

3. The number of Sylow p-subgroups is k*p+1, and that number evenly divides m, the index of a Sylow p-subgroup.

The Sylow theorems can be used to find what possible groups there are with their order being the product of two distinct primes.


Now for composition series. Consider the commutator subgroup of a group generated by two of its subgroups. The commutator of two group elements a and b is [a,b] = a*b*a^-1*b^-1. If a belongs to subgroup A and b to subgroup B, then all their possible commutators is not, in general, a group, but it generates the commutator subgroup [A,B].

The commutator [G,G] of group G is a normal subgroup of G, and its quotient group is the maximal abelian group for quotient groups of G, the largest one possible.

One can repeat this operation in two ways.

G1 = [G,G], G2 = [G1,G1], G3 = [G2,G2], ...
This gives the "derived series", and if it ends at the identity group, then G is "solvable".

G1 = [G,G], G2 = [G,G1], G3 = [G,G2], ...
This gives the "lower central ceries", and if it ends at the identity group, then G is "nilpotent".

I once wrote some group-theory code for Mathematica where I calculate the derived series for a group.

 

[lpetrich]

If a group is solvable, that means that neither it nor its subgroups is either a simple nonabelian group or else has a simple nonabelian group as a quotient group of one of its subgroups. A "simple" group is one with no nontrivial normal subgroups, none other than itself and the identity group. The only simple finite abelian groups are the prime-order cyclic groups. The others are several infinite families and 26 "sporadic" groups, including the huge "Monster" group. The proof of this result was a major collaborative effort, one that is spread over some 10,000 journal pages.

Here are some more solvability theorems.

The Feit-Thompson Theorem states that all odd-order groups are solvable.

Burnside's Theorem states that all groups with order p1ⁿ¹*p2[/sup]n2[/sup] for primes p1 and p2 are solvable. This includes all p-groups.

As to a group's commutator series, one can prove that the commutator of two normal subgroups is also a normal subgroup. Here goes.

Take a commutator element for a in A and b in B. Now take element g of the main group and find the conjugate of the commutator element with respect to it:
g * (a*b*a^-1*b^-1) * g<sup>-1 = a'*b'*a'-1*b'-1
where a' = g*a*g-1 and b' = g*b*g-1
Since both A and B are normal, a' is in A and b' is in B. Thus, this commutator element becomes another one for A and B, and as a result, [A,B] is a normal subgroup.

That means that both kinds of commutator series are series of normal subgroups of the original one. They thus have quotient groups relative to the original one.

Here is a derived series for some 3D rotation groups:

Octahedral group - Z2 -> Tetrahedral group - Z3 -> 3D dihedral rotation group D2 - Z2*Z2 -> Identity group</sup>

 

[lpetrich]

Oops. Pressed the wrong button.

 

[lpetrich]

Now for groups with order p*q where p and q are two distinct primes, with q > p.

Sylow's theorems provide essential clues.

The group's Sylow p-groups all have order p, and are thus Z(p). Since those subgroups are generated by any non-identity element, two conjugate ones either share all their non-identity elements, or else share none of them. Since there are k*p+1 of these subgroups, they thus have a total of (k*p+1)*(p-1) non-identity elements.

So if there is more than one Sylow p-subgroup for q, there must be at least (q+1) of them, and (q+1)*(q-1) non-identity elements in them. That's q² - 1, and that's greater than the number of non-identity elements in the group, p*q - 1.

So there is only one Sylow p-subgroup for q, making it a normal subgroup. It accounts for q-1 elements of the group.

Now for the Sylow p-subgroups for p.

If there is only one of them, then it is also normal, and it accounts for p-1 elements in the group. The remaining p*q-p-q+1 elements must have order p*q, and the group is thus Z(p*q) ~ Z(p)*Z(q).

But if there is more than one Sylow p-subgroup for p, then the number of them must evenly divide q. Since q is a prime, thus there must be q of those subgroups. This number must equal k*p+1 for some k, and thus we have a constraint on nonabelian groups with order p*q: q = k*p+1.

This also means that there are q*(p-1) order-p elements. Adding the (q-1) order-q elements and the identity, we thus account for all the group elements.


Let's see what nonabelian groups there are with this sort of order.

Since the Sylow p-subgroup for q is normal, we can take order-p element a and order-q element b and find
a*b*a^-1 = b^r

Going to power m of a gives
a^m*b*a^-m = b^{r^m}

With m = p, we find b = b^{r^p} where r != 1.
Thus, r^p = 1 mod q.

This also means that b, b^r, b^{r^2}, ..., b^{r^(p-1)} are in the same conjugacy class. So the powers of b get split into k conjugacy classes, each with size p.

Likewise, for each m, a^m*bⁿ for n = 0 to q-1 is a conjugacy class with size q. These classes are all cosets of the order-q subgroup, and that subgroup thus has quotient group Z(p).


For p = 2, r = 1 or -1, with the latter being nonabelian. Thus, Dih(q) is the only nonabelian group with order 2*q.

The smallest odd one has p = 3 and q = 7 with order 21. With r = 2 or 4, b's split into conjugacy classes {b, b², b⁴} and {b³, b⁵, b⁶}, while the remaining non-identity elements get split into 2 conjugacy classes with size 7.

I will now work out the character table for this group. The order-5 conjugacy classes I will call a1 and a2, and the order-7 ones b1 and b2. That means 5 irreps.

e(1) b1(3) b2(3) a1(7) a2(7)
1 1 1 1 1
1 1 1 w1 w2
1 1 1 w2 w1
3 c1 c2 0 0
3 c2 c1 0 0
where
w1 = (-1+sqrt(-3))/2, w2 = (-1-sqrt(-3))/2 -- cube roots of unity: x, x³
c1 = (-1+sqrt(-7))/2, c2 = (-1-sqrt(-7))/2 -- sums of seventh roots of unity: x+x²+x⁴, x³+x⁵+x⁶

 

[lpetrich]

Some more group-theory results. Every group element can expressed as a permutation: a . {a, b, c, ...} = {a*a, a*b, a*c, ...}

Thus for group order n, a permutation of n symbols, making the group a subgroup of Sym, the "symmetric group", the group of all permutations with length n. Furthermore, an element's permutation is composed of cycles of length m, where m is the element's order in the group.

Sym has order n!

It has a subgroup, Alt, the "alternating group", with all even permutations of length n. Even permutations can be built from an even number of permutations of only two symbols, odd permutations are likewise, for an odd number. For more than one symbol, the number of even permutations and the number of odd permutations are equal: n!/2. Thus for n > 1, Alt is a subgroup of Sym with index 2, and that makes it a normal one.

All the conjugacy classes of Sym are sets of permutations having the same set of cycle lengths. The irreps of Sym are associated with these classes in a rather complicated way, but their character values are all integers.

In Alt, all of the classes are of even permutations, of course, and some of the classes are split into two equal-sized ones. Looking at its irreps, some merge, and some get split.

For a pair 1 and 2 with χ2(even) = χ1(even) and χ2(odd) = - χ1(even) (at least one value nonzero), the merged one has the χ1(even) values.

For a single one with χ(odd) = 0, we get a split. χ(even, unsplit) gets χ(even)/2, and χ(even, split) gets (χ(even) +- w)/2 where w is sqrt(some integer).

This merging and splitting is general for index-2 subgroups, even if the forms of the w's are different.

-

Let's see about the smallest symmetric and alternating groups.

Sym(1) = {1} and Alt(1) = {1} -- both identity groups

Sym(2) = {12, 21} and Alt(2) = {12} -- Z2 and the identity group

Sym(3) = {123, 132, 213, 231, 312, 321} and Alt (3) = {123, 231, 312} -- Dih(3) and Z3

Character table for Sym(3):
111 (1), 12 (3), 3 (2)
1, 1, 1
1, -1, 1
2, 0, -1

The class 12 drops out because it is an odd-permutation class, and of the remaining classes, 3 splits into 3a and 3b, both with size 1.

The first two irreps merge, while the third one gets split.

Character table for Alt(3):
111 (1), 3a (1), 3b (1)
1, 1, 1
1, (1/2)(1+w), (1/2)(1-w)
1, (1/2)(1-w), (1/2)(1+w)

where w = sqrt(-3)

 

[lpetrich]

Of the spatial-symmetry groups, Dih(3) ~ Sym(3), Tetrahedral ~ Alt(4), Octahedral ~ Sym(4), Icosahedral ~ Alt(5)

Let's see some more about small groups -- what possible ones are there of them?

Order 5: Z5 only

Order 6: Z6 ~ Z2*Z3 -- any others?

Element orders must evenly divide 6, so the non-identity ones must be 2, 3, and 6. An element with order 6 generates Z6, and we already have that.

Do all non-identity elements have order 2? Take two of them, a and b. One can compose a product, a*b. Since it is equal to its inverse, it is equal to b*a. THus, a and b generate the 4-group, Z2*Z2. This subgroup's order does not evenly divide 6, so some elements must have order 3.

More generally, every group where all the non-identity elements have order 2 are abelian, and are thus equivalent to (Z2)^something.

-

So there is at least one element with order 3: a. It generates e, a, and a², and with a remaining element b, it generates b, a*b, and a²*b, or alternatively, b, b*a, and b*a².

Consider what values b² might have. If a or a², then b has order 6, giving Z6. If b*(some power of a), then b = (that power of a), contrary to the premise that it is a distinct element. Thus, b² = e, giving it order 2.

Now we consider left-side b vs. right-size b. If a*b = b*a, then we get Z6 again. That leaves us with the remaining order-6 group. It has a*b = b*a², making it the lowest-order nonabelian group. It is Dih(3) and Sym(3).

 

[lpetrich]

Order 7 is easy: Z7

Order 8 is interesting. An order-8 element gives Z7, while all order 2 gives Z2*Z2*Z2 or (Z2)³. So for some elements having order 4, the group is either Z2*Z4 or some nonabelian group.

Let a have order 4 and b be one of the remaining elements: e, a, a², a³, b, a*b, a²*b, a³*b.

It is evident that b² can be either e or a², giving b order 2 and 4, respectively.

We now consider a*b = b*a^r. a*b² = b²*a^{r^2} or r² = 1 mod 4.

a*b = b*a -- abelian -- or a*b = b*a³ -- nonabelian.

So there are two nonabelian groups of order 8: a⁴ = e, b² = e or a², and a*b = b*a³. These are Dih(4) and QD(2).

Let's consider a generalized dihedral group where a^m = e, bⁿ = a^s, and a*b = b*a^r.

Then we get constraints rⁿ = 1 mod m and r*s = s mod m

-

Moving on to order 9, it has only Z9 and Z3*Z3.

Order 10 has Z2*Z5 (Z10) and Dih(5)

Order 11 has Z11

Order 12 gets complicated. Its abelian ones are Z4*Z3 (Z12) and Z2*Z2*Z3 (Z2*Z6). Its nonabelian groups are Dih(6), QD(3), the tetrahedral group, and maybe others.

Order 13 has Z13

Order 14 has Z2*Z7 (Z14) and Dih(7)

Order 15 has Z3*Z5 (Z15) and no nonabelian ones

Order 16 has Z16, Z2*Z8, Z4*Z4, Z2*Z2*Z4, (Z2)⁴, and some nonabelian ones: Dih(8), QD(4), and maybe others. All the nonabelian ones have a maximum element order of at least 4 and at most 8.

I think I'll leave off here.

 

[lpetrich]

For order 12, let us not forget about Z2 * (the order-6 nonabelian group): Z2 * Dih(3)

Likewise for order 16, let us not forget about Z2 * (the order-8 nonabelian groups): Z2 * Dih(4) and Z2 * QD(2).

Back to order 12, we can use Sylow's theorems. There is at least one Sylow 2-subgroup, either Z4 or Z2*Z2, and either 1 or 3 of them. There is also at least one Sylow 3-subgroup, Z3, and either 1 or 4 of them.

If there is only one each, then there are 12 - (3 - 1) - (4 - 1) - 1 = 6 non-identity elements remaining, elements with order 6 or 12. If there are four of the 3, then there are 12 - 4*(3 - 1) = 4 remaining, and there is only one Sylow 2-subgroup. Likewise if there are three of the 4, then there are 12 - 3*(4 - 1) = 3 remaining, and there is only one Sylow 3-subgroup.

Let's now consider various cases.

Let's say that all elements' orders are either 2 or 3, and that there is only one Sylow 3-subgroup. {e, c, c²}. Then elements a and b have order 2 and their product commutes. (a*c)^-1 = c²*a, (b*c)² = c²*b, so a*c = c²*a and b*c = c²*b. But a*b*c = a*c²*b = c²*a*c*b = c*a*b, and not c²*a*b. That means that this case cannot happen. If the highest even order is 2, then it must be the Sylow 2-subgroup that is the normal one.

The order-3 elements are c, c*a, c*b, c²*a, etc., and conjugation on {e, a, b, a*b} produces permutations of {a, b, a*b}. Since c has order 3, its permutation on {a, b, a*b} will also have order 3, being {a, b, a*b} - {b, a*b, a} - {a*b, a, b} or {a, b, a*b} - {a*b, a, b} - {b, a*b, a}.

This is the tetrahedral group.

On the other side, if there is an order-12 element, then it generates Z12 = Z4 * Z3. If there is an order-6 one but no order-12 one, then it generates Z6. The remaining element then either generates Z2 or the generalized dihedral group.

Element a has order 6, element b satisfies a*b = b*a^-1 in the nonabelian case.So 2*s = 0 mod 6 or s = 0 or 3. The s = 0 case is Dih(6), while the s = 3 case is QD(3).

The remaining cases have an order-4 element and an order-3 element but no higher orders of element. If the Sylow 2-subgroup is the normal one, then {e, a, a², a³} exhausts all the elements whose orders are powers of 2. Conjugation by an order-3 element would permute a and a³, and since there are only two of those, repeating that conjugation 3 times would give us those two in reverse order. Thus, the Sylow 2-subgroup cannot be normal. Now for the Sylow 3-subgroup being normal. It's {e, c, c²}. The elements c and c² can be permuted by an order-4 element, but they commute with every order-2 one. A commuting order-2 and order-3 element can make an order-6 one, violating that condition.

Wikipedia's article  List of small groups claims that Dih(6) ~ Dih(3) * Z2. I decided to check on that. It's an order-6 element a and an order-2 one b with a*b = b*a⁵. The element a³ can be shown to commute with b. Thus,
it is {e, a³} * ({e, a², a⁴} . {e, b})

 

[lpetrich]

Some more on how to find group characters.

Some of the irreducible χ(group rep)'s are irreducible χ(quotient-group rep)'s.

There's also an interesting theorem that states how to get a group's characters from a subgroup's characters, without the subgroup having to be a normal one.

χ(group class A) = (N/N') * (sum over subgroup classes A' in A of n(A')/n(A) * χ(A') )

N is the order of the group, N' is the order of the subgroup, n(A) is the order of class A, and n(A') is the order of class A'. If A has no elements in the subgroup, then the corresponding character value is zero.

In general, this will be reducible, but one can subtract out those characters already found.

Another interesting theorem connects characters' values with products of conjugacy classes: M(A,B,C) is how many times class C appears in the product of classes A and B. It is always a nonnegative integer, of course. One can show that
η(A)*η(B) = sum over C of M(A,B,C) * η(C)
where
η(A) = n(A)*χ(A)/χ(e)

-

Let's return to our symmetrized product reps. D_{i1i2i3,j1j2j3}(a) = sum over permutations P of c(P) * D_i1,j1'(a) * D_i2,j2'(a) * D_i3,j3'(a) where (j1'j2'j3') is permutation P of (j1j2j3).

To be consistent, the coefficients c(P) must satisfy c(P) = sum over P1 and P2 where P = P1.P2 of c(P1)*c(P2)

One can imagine the c(P)'s combined with the P's in the fashion C = sum over p of c(P) * P -- P is a sort of basis set. This consistency condition implies "idempotence": C = C.C

This equation has a very interesting solution:
c(P) = sum over irreps of (0 or 1) * χ(e)*χ(P)/N

where e is the identity permutation.

If the (0 or 1) coefficients are all 1, then we get c(e) = 1, and all other c's = 0. This is for a straight outer product without any index interchanges.

 

[lpetrich]

I'll now demonstrate some of these methods for finding character tables. I'll do so on Sym(3) ~ S3 ~ Dih(3) ~ D3, Alt(4) ~ A4 ~ Tetrahedral, and Sym(4) ~ S4 ~ Octahedral, using some common one-letter shorthands for their names. I'll denote the elements by their permutation values: 111, 12, 3, etc.

S3's classes (sizes): 111 (1), 3 (2), 12 (3) -- total 6
A4's classes (sizes): 1111 (1), 22 (3), 13' (4), 13'' (4) -- total 12
S4's classes (sizes): 1111 (1), 22 (3), 13 (8), 112 (6), 4 (6) -- total 24

Normal subgroups, the cosets, and their quotient groups:
S3: {111, 3}: A3 ~ Z3, {12} / Z2
A4: {1111, 22}: Z2*Z2, {13'}, {13''} / Z3
S4: {1111, 22, 13}: A4, {112, 4} / Z2

So in addition to the identity character, all 1's, these groups also have characters
S3: 1, 1, -1
A4: 1, 1, w, w² and 1, 1, w², w where w = (1/2)*(1 + sqrt(-3)) is a cube root of unity
S4: 1, 1, 1, -1, -1

For S3 and A4, one can find the remaining ones by character-table orthogonality, but for S4, it is more difficult.
S3:
111, 3, 112
1, 1, 1
1, 1, -1
2, -1, 0
A4:
1111, 22, 13', 13''
1, 1, 1, 1
1, 1, w, w²
1, 1, w², w
3, -1, 0, 0

Let's now use the ordinary-subgroup method.

For S3, we try first {111, one 12}: Z2. We get
(6/2) * {(1/1) * (1*1), 0, (1/3) * (1*1)} = {3, 0, 1} = #1 + #3
(6/2) * {(1/1) * (1*1), 0, (1/3) * (1*(-1)), 0} = {3, 0, -1} = #2 + #3
Let us also try {111, 3}: Z3. We get
(6/3) * {(1/1) * (1*1), (1/2) * (1*1 + 1*1), 0} = {2, 2, 0} = #1 + #2
(6/3) * {(1/1) * (1*1), (1/2) * (1*w + 1*w²), 0} = {2, -1, 0} = #3

For A4, we try first {111, 22}: Z2 * Z2. We get
(12/4) * {(1/1) * (1*1), (1/3) * (1*1 + 1*1 + 1*1), 0} = {3, 3, 0} = #1 + #2 + #3
(12/4) * {(1/1) * (1*1), (1/3) * (1*1 - 1*1 - 1*1), 0} = {3, -1, 0} = #4
Let us also try {111, one 13', one 13''}: Z3. We get
(12/3) * {(1/1) * (1*1), 0, (1/4)*(1*1), (1/4)*(1*1)} = {4, 0, 1, 1} = #1 + #4
(12/3) * {(1/1) * (1*1), 0, (1/4)*(1*w), (1/4)*(1*w²)} = {4, 0, w, w²} = #2 + #4
(12/3) * {(1/1) * (1*1), 0, (1/4)*(1*w²), (1/4)*(1*w)} = {4, 0, w², w} = #3 + #4

We can now try S4. Let's try A4 first. We get
(24/12) * {(1/1) * (1*1), + (3/3) * (1*1), (1/8) * (4*1 + 4*1), 0, 0} = {2, 2, 2, 0, 0} -- reducible: square = 2
(24/12) * {(1/1) * (1*1), + (3/3) * (1*1), (1/8) * (4*w + 4*w²), 0, 0} = {2, 2, -1, 0, 0} -- irreducible: square = 1
(24/12) * {(1/1) * (1*3), + (3/3) * (1*(-1)), (1/8) * (4*0 + 4*0), 0, 0} = {6, -2, 0, 0, 0} -- reducible: square = 2
I'll do another subgroup: {1111, one 22, two 4}: Z4. We get
(24/4) * {(1/1) * (1*1), (1/3) * (1*1), 0, 0, (1/6)*(1*1 + 1*1)} = {6, 2, 0, 0, 2} -- reducible: square = 3
(24/4) * {(1/1) * (1*1), (1/3) * (1*1), 0, 0, (1/6)*(1*(-1) + 1*(-1))} = {6, 2, 0, 0, -2} -- reducible: square = 3
(24/4) * {(1/1) * (1*1), (1/3) * (1*(-1)), 0, 0, (1/6)*(1*i + 1*(-i))} = {6, -2, 0, 0, 0} -- reducible: square = 2

The first one of these, {2,2,2,0,0} has the identity character in it: {1,1,1,1,1}. Subtracting that out gives {1,1,1,-1,-1}, the remaining A4 quotient-group character. So we have two of them so far. The next one is irreducible right off the bat. So we look at {6,2,0,0,2}. It has 3 irreducible characters in it: {1,1,1,1,1} and {2,2,-1,0,0}, and subtracting that one out gives us {3,-1,0,-1,1}. Forming a product rep by multiplying by {1,1,1,-1,-1} gives {3,-1,0,1,-1}. Thus, we get

S4:
1111, 22, 13, 112, 4
1, 1, 1, 1, 1
1, 1, 1, -1, -1
2, 2, -1, 0, 0
3, -1, 0, 1, -1
3, -1, 0, -1, 1

It is evident from this table that {1111, 22} is a normal subgroup of S4 with quotient group S3.

 

[lpetrich]

Let's now consider product reps and powers of reps. Start with S3 and suppose that all one knew of its characters are
111, 3, 12
1, 1, 1
2, -1, 0

Could one deduce the third one? Let's see
Square of 2nd character: {4, 1, 0}
2nd character with squares of elements: {111, 3, 111} = {2, -1, 2}
Symmetrized: (#1 + #2)/2 = {3,0,1} -- reducible: square = 2, contains {1,1,1} and {2,-1,0}
Antisymmetrized: (#1 - #2)/2 = {1,1,-1} -- irreducible.
So we got a third one: {1,1,-1}

Let's try S4 and suppose that we only know of these two:
1111, 22, 13, 112, 4
1, 1, 1, 1, 1
3, -1, 0, 1, -1

Square of 2nd character: {9, 1, 0, 1, 1}
2nd character, element squares {1111, 1111, 13, 1111, 22}: {3, 3, 0, 3, -1}
Symmetrized: {6, 2, 0, 2, 0} -- reducible, square = 3
Antisymmetrized: {3, -1, 0, -1, 1} -- irreducible, square = 1

So we have
1111, 22, 13, 112, 4
1, 1, 1, 1, 1
3, -1, 0, 1, -1
3, -1, 0, -1, 1

The symmetrized one {6, 2, 0, 2, 0} = {1, 1, 1, 1, 1} + {3, -1, 0, 1, -1} + {2, 2, -1, 0, 0}. So we get another irreducible one: {2, 2, -1, 0, 0}, giving us

1111, 22, 13, 112, 4
1, 1, 1, 1, 1
2, 2, -1, 0, 0
3, -1, 0, 1, -1
3, -1, 0, -1, 1

Now try the product of the second and third ones: {6, -2, 0, 0, 0} That's the sum of the last two.

The product of the last two: {9, 1, 0, -1, -1} -- that's {3, -1, 0, 1, -1} + {3, -1, 0, 1, -1} + {2, 2, -1, 0, 0} + {1, 1, 1, -1, -1}, giving the final irreducible character: {1, 1, 1, -1 ,-1}:

1111, 22, 13, 112, 4
1, 1, 1, 1, 1
1, 1, 1, -1, -1
2, 2, -1, 0, 0
3, -1, 0, 1, -1
3, -1, 0, -1, 1

For S4, let us see what symmetrized and antisymmetrized cubes give us. Take our starting irrep again.

Cube: {27, -1, 0, 1, -1}
Elements cubed {1111, 22, 1111, 112, 4}: {3, -1, 3, 1, -1}
Irrep * elements squared: {3, -1, 0, 1, -1} * {3, 3, 0, 3, -1} = {9, -3, 0, 3, 1}

Symmetric: multiply each one by each one of (1/6)*{1*1, 2*1, 3*1} = (1/6) * {1, 2, 3} and add:
{10, -2, 1, 2, 0} -- #1 + 2*#4 + #5

Antisymmetric: multiply each one by each one of (1/6)*{1*1, 2*1, 3*(-1)} = (1/6) * {1, 2, -3} and add:
{1, 1, 1, -1, -1} -- #2

Mixed: multiply each one by each one of (2/6)*{1*2, 2*(-1), 3*0} = (2/3) * {1, -1, 0} and add:
{16, 0, -2, 0, 0} -- 2*#3 + 2*#4 + 2*#5

 

[lpetrich]

I'll now do equations for the characters using products of conjugacy classes. For S3, I'll abbreviate the characters values' names:
η(111) = y1, η(3) = y3, η(12) = y2

y1*y1 = y1
y1*y3 = y2
y1*y2 = y2
y3*y3 = 2*y1 + y3
y2*y3 = 2*y2
y2*y2 = 3*y1 + 3*y3

y1 = 0 or 1, so it must be 1.
We must solve y3² = y3 + 2. This gives us y3 = 2 and y3 = -1
For y3 = -1, y2 = 0
For y3 = 2, y2 = 3 or -3

So,
y1, y3, y2
1, 2, 3
1, 2, -3
1, -1, 0

Dividing by the class sizes and taking their squares:
1, 1, 1 -- 1
1, 1, -1 -- 1
1, -1/2, 0 -- 1/4
That gives us irrep sizes 1, 1, 2, and thus
1, 1, 1
1, 1, -1
2, -1, 0
as expected

 

[lpetrich]

Let's put all this math stuff to work by looking at molecular vibration spectra and seeing what we can predict of them. Some small molecules have some rather rather nontrivial symmetries.

I'll consider ammonia. It has its 3 hydrogen atoms in an equilaterial triangle with its nitrogen atom offset from the center of them.

Its rotoreflection symmetry group is, not surprisingly, Dih(3) or D3 (Schoenflies notation C3v). Its three conjugacy classes are identity (1), 120d rotations (2), and reflections (3). The number in ()'s is the multiplicity of each class. As the symmetric group Sym(3) or S3, the classes are 111, 3, 12.

To find out how its spectrum splits, we take the product of (interchanges of atoms) and (displacement). This makes a product rep, and we want to see what irreps it contains. That can easily be done with group characters. For D3 / C3v:
1, 2, 3
#1: 1, 1, 1
#2: 1, 1, -1
#3: 2, -1, 0

For the atoms, the character is the number of atoms that stay put in each operation:
3, 0, 1
= #1 + #3

For the displacement, the character is the trace of the 3D rotorefleciton matrix
3, 0, 1
= #1 + #3

The product rep is (#1 + #2)* (#1 + #3) = #1 + 2(#3) + #3 * #3
So we need to find #3 * #3 = 4, 1, 0.
It is #1 + #2 + #3.
So we get
2(#1) + 1(#2) +3(#3)

So we get 6 spectral lines, with degeneracies 1, 1, 1, 2, 2, 2 (the dimensions of the irreps)

There are three rotations, and they take a 1 and a 2, giving 1, 1, 2, 2. Detailed calculations show that we do indeed get those degeneracies, though the vibration-frequency values are rather complicated.

 

[lpetrich]

Having succeeded with ammonia, I move on to methane. Its symmetry is the tetrahedral group with reflections, Td. It is isomorphic to the octahedral group and Sym(4) or S4. Its classes are identity (1), 180d rotation (3), 120d rotation (8), pure reflection (6), rotoreflection (6)
and its character table is
1, 3, 8, 6, 6'
#1: 1, 1, 1, 1, 1
#2: 1, 1, 1, -1, -1
#3: 2, 2, -1, 0, 0
#4: 3, -1, 0, 1, -1
#5: 3, -1, 0, -1, 1

We need the atom interchanges and the rotorflections. The interchanges leave these numbers of atoms fixed:
4, 0, 1, 2, 0
This is #1 + #4

The rotation matrices have traces 3, -1, 0, 1, -1 or #4.

So we must find (#1 + #4) * #4 = #4 + #4 * #4
I find #1 + #3 + #4 + #5
I thus get #1 + #3 + 2(#4) + #5, or degeneracies 1, 2, 3, 3, 3

One of the 3's is for overall rotations, leaving 1, 2, 3, 3. This also agrees with detailed calculations.

-

I'll now move on to fullerene, C60. Its rotational symmetry group is the icosahedral group I, or Alt(5) or A5. Its rotoreflection group is (inversions: {I,-I}) * (pure rotation group) and I'll skip that one. The icosahedral group has classes identity (1), 180d angles (15), 120d angles (20), 72d angles (12), and 144d angles (12). Its character table
1, 15, 20, 12, 12'
#1: 1, 1, 1, 1, 1
#2: 3, -1, 0, w1, w2
#3: 3, -1, 0, w2, w1
#4: 4, 0, 1, -1, -1
#5: 5, 1, -1, 0, 0
where w1 = (1+sqrt(5))/2 and w2 = (1-sqrt(5))/2

The atom interchanges have no atoms fixed except for the identity: 60, 0, 0, 0, 0. That gives us #1 + 3(#2) + 3(#3) + 4(#4) + 5(#5)

The rotation matrices have traces #2. So we get #2 + 3(#2 * #2) + 3(#2 * #3) + 4(#2 * #4) + 5(#2 * #5)
#2 * #2 = #1 + #2 + #5
#2 * #3 = #4 + #5
#2 * #4 = #3 + #4 + #5
#2 * #5 = #2 + #3 + #4 + #5
Giving a grand total of 3(#1) + 9(#2) + 9(#3) + 12(#4) + 15(#5)

One of the #2's is for overall rotation, and one for overall translation, giving us 3(#1) + 7(#2) + 9(#3) + 12(#4) + 15(#5), or degeneracies 3(1), 16(3), 12(4), 15(5).

These numbers agree with what's in C60 vibrations, put together from observations and fancy calculations.

 

[lpetrich]

Vibrations of Water -- with its three vibrational modes. That site also does ammonia and methane and several others.

Vibrational Modes, a list for several molecules. Ammonia and methane are both mentioned, along with carbon tetrachloride (methane-like symmetry). My group-theory calculations agree with observation: ammonia has degeneracies 1,1,2,2 and methane and carbon tet degeneracies 1,2,3,3.

Molecules like methyl chloride, CH3Cl, and benzene, C6H6, have axial symmetry, as ammonia does. Axial-symmetry rotation and rotoreflection groups have maximum irrep dimension 2, thus these molecules' degeneracy is at most 2. Some of them have abelian symmetry groups, as water does (twofold axial rotation), making their maximum degeneracy 1.

I found an example in that infrared-spectrum list that piqued my curiosity enough for me to want to examine it further: sulfur hexafluoride. Its fluorine atoms are at the vertices of an octahedron, giving the molecule octahedral-group symmetry. I'll do the pure-rotation one, O, instead of the rotoreflection one, Oh, because Oh = {I,-I} * O.

Here are the octahedral group's conjugacy classes: the identity (1), 180d rotation around octa vertex / cube face (3), 120d rotation around octa face / cube vertex (8), 180d rotation around octa / cube edge (6), 90d rotation around octa vertex / cube face (6).

So for the flourine atoms, I get these numbers that are fixed:
1, 3, 8, 6, 6
6, 2, 0, 0, 2
This is #1 + #3 + #5

Combining with displacement, #5, gives #5 + (#3 * #5) + (#5 * #5).
#3 * #5 = #4 + #5
#5 * #5 = #1 + #3 + #4 + #5

Overall, we get #1 + #3 + 2(#4) + 3(#5). One of the #4's is overall rotation, so we get #1 + #3 + 2(#4) + 2(#5) = degeneracies 1, 2, 4(3)

Which agrees with the observed spectrum of sulfur hexafluoride.

Trying with Oh, it has 10 classes and 10 irreps. The classes are (rotations), and (rotations * inversion). The + irreps (my notion) are {O irreps, O irreps}, while the - ones are {O irreps, - O irreps}.

Fluorine-atom rearrangements have these numbers of fixed atoms:
(rotation) / (rotation * inversion)
6, 2, 0, 0, 2 / 0, 4, 0, 2, 0
This is (#1+) + (#3+) + (#5-)

Displacements are (#5-), and combined with the the atom rearrangements gives (#5-) + ((#3+) * (#5-)) + ((#5-) * (#5-))
(#3+) * (#5-) = (#4-) + (#5-)
(#5-) * (#5-) = (#1+) + (#3+) + (#4+) + (#5+)
giving a grand total of (#1+) + (#3+) + (#4+) + (#4-) + (#5+) + 2(#5-). One of the (#5-)'s is overall rotation, and we get

(#1+) + (#3+) + (#4+) + (#4-) + (#5+) + (#5-) with degeneracies 1, 2, 4(3), as derived earlier.

 

[lpetrich]

I tried doing this calculation for fullerene with Ih -- icosahedral rotations and reflections. I won't go into detail, but I got the same numbers of degeneracies as with plain I -- icosahedral rotations.

-

There is a connection between the tetrahedral, octahedral, and icosahedral groups and the five Platonic solids.

The tetrahedral group is the symmetry group of the regular tetrahedron.

T: rotations:
1 -- identity
3 -- rotate 180d at an edge and at its opposite-side edge
4 -- rotate clockwise 120d at a vertex and counterclockwise 120d at its opposite-side face
4 -- rotate counterclockwise 120d at a vertex and clockwise 120d at its opposite-side face

Td merges the two 4's and adds these rotoreflections:
6 -- reflect by a plane going through one edge and splitting the opposite-side edge in two
6 -- reflect by a plane halfway between opposite-side edges, and parallel to them and then rotate 90d

The octahedral group is the symmetry group of the regular octahedron and the cube (the regular hexahedron).

O: rotations
1 -- identity
3 -- rotate 180d at an octahedron vertex or a cube face, and its opposite-side one
8 -- rotate 120d at an octahedron face or a cube vertex, and its opposite-side one
6 -- rotate 180d at an edge and its opposite-side edge
6 -- rotate 90d at an octahedron vertex or a cube face, and its opposite-side one

Oh adds these rotoreflections:
1' -- reflect by any plane then rotate 180d perpendicular to it
3' -- reflect by a plane perpendicular to the line between opposite-side octahedron vertices or cube faces
8' -- reflect by a plane perpendicular to the line between opposite-side octahedron faces or cube vertices, then rotate 60d perpendicular to that line
6' -- reflect by a plane halfway between opposite-side edges, and parallel to them
6' -- reflect by a plane perpendicular to the line between opposite-side octahedron vertices or cube faces, then rotate 90d

The icosahedral group is the symmetry group of the regular icosahedron and the regular dodecahedron.

I: rotations
1 -- identity
15 -- rotate 180d at an edge and its opposite-side one
20 -- rotate 120d at an icosahedron face or a dodecahedron vertex, and its opposite-side one
12 -- rotate 72d at an icosahedron vertex or a dodecahedron face, and its opposite-side one
12 -- rotate 144d at an icosahedron vertex or a dodecahedron face, and its opposite-side one

Ih adds these rotoreflections:
1' -- reflect by any plane then rotate 180d perpendicular to it
15' -- reflect by a plane halfway between opposite-side edges, and parallel to them
20' -- reflect by a plane perpendicular to the line between opposite-side icosahedron faces or dodecahedron vertices, then rotate 60d
12' -- reflect by a plane perpendicular to the line between opposite-side icosahedron vertices or dodecahedron faces, then rotate 108d
12' -- reflect by a plane perpendicular to the line between opposite-side icosahedron vertices or dodecahedron faces, then rotate 36d