Group theory discussion

[arfa brane]

After one semester of ring and group theory, I've been trying to think of a good example that can be used to help people with the abstract side of it.

I think it's one of the biggest problems most students have with it, and most teachers, especially busy professors have teaching it. So one of the subjects we touched on was the symmetry of some of the Platonic solids, and how because of Cayley's Theorem any finite group has a map to S_n.

One other example that was covered when we did Burnside's Theorem was the number of ways to number dices with the usual 6 sides, smallish cubes, in other words. But for dice with each face or side a different number of dots. So that's already a subset of the total number of ways to number the dice, so we have a group action that sends elements of this total set to the subset, right? It's just an abstract function that maps all the dice with no sides the same to this set, so what is it (otherwise called)?

I didn't think about this myself during the course or ask the lecturer if they thought it was something that showed (some kind of connection between groups), wasn't that hard to think about. Or what?

[arfa brane]

Fot instance, something really abstract like the set of 2x2 real matrices with determinant 1.
This is easily shown to ba a group and the map from G to itself is an automorphism.

But in counting problems we have permutations on n different letters. However, freeing up this restriction that tuples have n different characters, you get (a+b+c+...)ⁿ, a regular expression.

This is like making necklaces with different colored beads. If you're free to choose one of n colors each time you get a string that is in the "language" over {a,b,c,...}. If you have to make all the beads different that's a subset which is the set of permutations of n letters.
So the dice-numbering example is just a way to compose some arrangement of different symbols, which we can assign numbers to, or letters.

With dice or cubes, you have the number of ways you can rotate them after identifying each (or some) of the faces. But cubes have edges and vertices too, so you can permute these the same way.

So you get asked to solve problems like: find the number of ways to make different necklaces of six beads using beads of three different colors. Well, isn't that the same as (a+b+c)⁶?
There are only three necklaces you can make so all the beads are the same color, because there are only three colors, what's the "action" that decides this?

[arfa brane]

Here's a previous exam:

(a) State Burnside's counting theorem.

(b) You are making bracelets by putting six coloured beads on a loop of string. There are three colours available. How many distinct necklaces can you make?

Now I interpret "available" as meaning there is a large enough supply of beads so I can make all the "distinct" ones.

Burnside"s thm. says that I should think about which symmetry group the bracelets are "in" and then which elements of this group "fix" elements in the set of possible bracelets. And obviously, if the beads in any bracelet are all the same color (identical!), then every element in the group acts to fix it.
But that isn't true once you introduce more than one color, it gets harder to think about too.

[arfa brane]

Since I took a formal language course last year, I guess I can't help but try to connect some of the dots.

Obviously, making a necklace out of different colored beads is equivalent to constructing a string of characters ("letters"). The alphabet is the (set of) beads, and the operation is concatenation. Then when you have n beads you turn the string into a loop, giving it rotational symmetry. Two kinds of rotation exist, about a central point (so all the beads in the necklace lie in a plane), and about a line that passes through the central point, and there are two kinds of line which are axes of symmetry: 'diagonal' from one bead to another which is opposite, and 'edge' from the centre of one edge to the centre of its opposite, or lines which divide the necklace in two. These diagonal and edge symmetries are called reflections ("in the plane", if you stay in the one all the beads lie on).

So what you're doing is considering all possible combinations of say, n colors over k beads. In the above problem, n = 3 and k = 6. There are n^k combinations. But what "takes" colored beads to necklaces of length k? We know the symmetry group that acts on the necklaces (when they've been constructed) is D₆, the same as for a regular hexagon.

And fairly obviously it's about counting how many necklaces are acted on by the different elements of D₆.

Well, I found this: http://en.wikipedia.org/wiki/Combina...d_permutations
. . .which seems to do a passable job confirming my "suspicions". A set (of letters, an alphabet) under concatenation (a language L) to construct finite strings, is a semigroup. Concatenation is associative since abc = (ab)c = a(bc), has an identity , the empty string, but no inverses, since a string can be decomposed into substrings in more than one way, concatenation is many to one. Because of the identity it's also a monoid.

[arfa brane]

Another big idea that I found seemed to be straightforward at first was the idea of a group also being just a set of elements, and that for a group G and a set X, X is a G-set if g ∈ G takes elements of X to X. So if G acts on itself then G is the G-set.

But "passive" elements like beads or letters in a string only exhibit symmetry when you compose various combinations and compare them to each other. The one-colour necklaces have the most symmetry because, whichever group G they're in, every element fixes each necklace, so formally:

S = { x ∈ X | g·x = x, ∀g ∈ G}, where X is the set of all distinct necklaces, says S is the set for which all elements of G fix x (act like the identity). These are the 1-color necklaces.

The counting problem is about partitioning X into subsets that are fixed by different elements of G. So you have to consider the symmetry of combinations of two and three colours (for the exam question) and which elements of G fix them. So its easier to count the whole of X by doing that, rather than considering all the possibilities. But each (unique) combination of beads reveals something about the way an element of G acts on X, because any g either fixes the element or it doesn't.

[arfa brane]

And last but not least:

In music there's the symmetry of scales. Western music adopts the diatonic scale (why is it so named?), and because there are 12 notes, the symmetry is 12-fold.

We (or me and a few others) know that there are symmetry groups in music (for the diatonic scale): the T/I and PLR groups, which act on elements of a scale. Note, a major scale is one of several different scales--if you play the scale of Cmaj you play 8 notes in that scale, if you transpose your hands (not the scale) by one white key so you start on D and play the same pattern (8 white keys), that's a Dorian scale. Repeating the shift so you start on E and play 8 white keys is another kind of scale, and so on. Each scale has a different structure.

So if we consider combinations of the keys of a piano, or the fretboard of a guitar, these are a G-set if there is a function (a map) which we can call composition of elements (i.e. up to say, k notes in some scale) that looks like · : G×X→ X, where X is the set of combinations of notes (and so, there is another function that takes single notes--the alphabet--to combinations of notes, in music these are called intervals for two-note combinations, or chords for combinations of three or more notes--i.e. "strings of notes") such that:

1, there is an identity e ∈ G, where e·x = x (e fixes x ∈ X).

2. for elements g,h ∈ G, (gh)x = g(hx) where g,h are any elements in G

For k, the "size" of any chord, you have 10 digits with which to combine the different notes. You're allowed to "cheat" and use any digit to play more than one key (on a piano) simultaneously, or on a fretboard.
With practice, you can play up to 10 notes with each hand, but the combination won't sound very "musical". Anyway, you certainly permute combinations of notes (chords) with your k = 10 digits. So you can consider that doing this is similar to permuting/combining letters in a string, or beads on a necklace.

But in music, there are two ways to combine notes: at the same time or in a "run" of individual notes. Really there isn't a lot of difference, since runs normally follow a time signature, so you play say, four notes in a sequence all within a single beat. This is another permutation of a combination of notes (because a "string" can be decomposed in more than one way, recall).

It seems to be the case that permutation groups are fundamental components of group theory, so I think having a heuristic that you can use to "descend" into some underlying algebraic structure is a good thing to be able to get one's head around. Using everyday or at least familiar examples is also a good idea (something concrete rather than wholly abstract!). But this seemed to be something the course material glossed over or left up to the students.
Then again, by year 3 most students are expected to be able to work things out for themselves.

But I think heuristics are important, perhaps what I've been going over isn't something everyone will find is a "good" model for them, perhaps to each his own--we each need to develop our own rules of thumb. Talking about the concepts involved when you're learning them seems also a kind of backroom deal, because most students don't, which I think is a bit of a shame.

I may have made some mistakes in the above, incidentally.

[arfa brane]

Here's one correction.

Necklaces of 6 beads are equivalent to hexagons in the plane. There are two kinds of reflection axis in the plane, vertex to vertex and edge to edge, about a line that passes through the centre of the hexagon. But if instead the figure has an odd number of vertices, only one kind of reflection exists, about a line from vertex to edge through the centre.

But for an n-sided regular polygon there are n-1 rotations (adding the identity rotation gives n), and n reflections. The difference between even and odd n is just whether the number of kinds of reflections is even or odd. This number is either 2 or 1 for n even, or respectively odd. Note that 2 is the same as the number of dimensions in the plane.

Now that's what I call abstract.

[arfa brane]

I thought about how to explain to someone who hasn't heard of it, what symmetry is really about.
Well, groups are just sets of elements which act on other sets. Symmetry is about actions on sets, where the actions preserve something.

Rotations preserve the 'structure' of regular polygons and solids. Labeling or 'identifying' regular features such as vertices or edges also identifies which of the group elements preserve orientations.
Group homomorphisms preserve group operations; every morphism preserves some aspect of overall symmetry. Obviously, rotating a regular solid about an axis of symmetry preserves the structure or "shape". Cyclic permutations of a string are equivalent to rotations of a regular polyhedron (with identifications) in the plane; you can reflect a string by dividing it equally and reversing the two substrings (if the string has odd length then a single character at the 'axis' is fixed by this operation).

Something I wanted to ask about language theory is: is there a way to turn an alphabet plus concatenation into a group? It isn't a group because it doesn't have unique inverses for strings of arbitrary length.
But what if the language contains only strings of length 2? In that case there is a unique ordered set of substrings of length 1 (following "deconcatenation").

[arfa brane]

Well, after some thought the answer seems to be no. You can't take a string apart without losing information, which is the order of the characters in any string.
But if a string is composed of identical characters the order is invariant.

Another reason you can't make a set of characters under concatenation into a group is that characters (passive elements) don't have inverses, so you can't get the identity by composing or decomposing such elements. But once you have a set of finite strings, cyclic permutations preserve their order, and reflections don't. This is the symmetry group D_n acting on strings of length n.

So ain't that cool?