The Unapologetic Mathematician

Mathematics for the interested outsider

More things that annoy me on the job hunt

Someone I know at one of the schools I applied to let me know that my application packet doesn’t have a teaching or research statement. Did I do something wrong? I went back to MathJobs and checked the application status form. It didn’t request them. I checked the job ad. Also didn’t request them.

Is this standard operating procedure, to tacitly require application materials not requested in the job ad? I’d noticed others that seemed to have rather thin requests for documents. Am I not hearing from them because I didn’t send them documents they didn’t ask for? Was I supposed to use telepathy to determine what they really wanted me to send?

March 26, 2007 Posted by | rants | 1 Comment

R.I.P., Dr. Cohen

From Alexandre Borovik I hear that Paul Cohen passed yesterday. He was probably best known for showing that the continuum hypothesis and the axiom of choice are independent of Zermelo-Fraenkel set theory. If I find an actual news article about it I’ll update here.

March 24, 2007 Posted by | Uncategorized | Leave a comment

Ring exercises

As spring break comes to an end, it’s another travel day. As I head back to New Haven, I think I’ll leave a few basic theorems about rings that can be shown pretty much straight from the definitions. The first three hold in any ring, while the last two require the ring to have a unit (multiplicative identity).

  • For any element a, 0a=a0=0.
  • For any elements a and b, (-a)b=a(-b)=-(ab). Remember that -a is the inverse of a in the underlying abelian group of the ring.
  • For any elements a and b, (-a)(-b)=ab.
  • For any invertible elements a and b, (ab)^{-1}=b^{-1}a^{-1}.
  • The multiplicative identity is unique. That is, if there is another element \bar{1} so that \bar{1}a=a\bar{1}=a for all a, then 1=\bar{1}.

March 24, 2007 Posted by | Ring theory | Leave a comment

This Week’s Finds #247

The latest “week” of John Baez’ This Week’s Finds in Mathematical Physics is up. Partly inspired by the E_8 news, it’s all about symmetry.

March 23, 2007 Posted by | Uncategorized | Leave a comment

How do you communicate a 60GB answer?

There’s evidently now a wiki for the Atlas project. On one page I found some very helpful advice:

The atlas project has computed Kazhdan-Lusztig polynomials for E8. (That is, the large block of the split real form of E8). The answer consists of two files, totalling 60 Gigabytes. This is too large to download conveniently over the internet. The files have been put on a portable usb/firewire drive (never underestimate the bandwidth of a truck).

Sage advice, that parenthetical.

March 23, 2007 Posted by | Atlas of Lie Groups | 1 Comment

Rings

Okay, I know I’ve been doing a lot more high-level stuff this week because of the E_8 thing, but it’s getting about time to break some new ground.

A ring is another very well-known kind of mathematical structure, and we’re going to build it from parts we already know about. First we start with an abelian group, writing this group operation as +. Of course that means we have an identity element {}0, and inverses (negatives).

To this base we’re going to add a semigroup structure. That is, we can also “multiply” elements of the ring by using the semigroup structure, and I’ll write this as we usually write multiplication in algebra. Often the semigroup will actually be a monoid — there will be an identity element 1. We call this a “ring with unit” or a “unital ring”. Some authors only ever use rings with units, and there are good cases to be made on each side.

Of course, it’s one thing to just have these two structures floating around. It’s another thing entirely to make them interact. So I’ll add one more rule to make them play nicely together:
(a+b)(c+d) = ac+ad+bc+bd
This is the familiar distributive law from high school algebra.

Notice that I’m not assuming the multiplication in a ring to be invertible. In fact, a lot of interesting structure comes from elements that have no multiplicative inverse. I’m also not assuming that the multiplication is commutative. If it is, we say the ring is commutative.

The fundamental example of a ring is the integers \mathbb{Z}. I’ll soon show its ring structure in my thread of posts directly about them. Actually, the integers have a lot of special properties we’ll talk about in more detail. The whole area of number theory basically grew out of studying this ring, and much of ring theory is an attempt to generalize those properties.

March 23, 2007 Posted by | Algebra, Ring theory, Structure of Rings | 3 Comments

The Carnival is back

This time those carnys are setting up shop over at Jason Rosenhouse’s place.

March 23, 2007 Posted by | Uncategorized | Leave a comment

Real and complex groups

Okay, another thing to make clear is that there’s not just one group we could mean by E_8. There’s one complex group, and a bunch of “real forms” of the group.

The difference between a real group and a complex group is pretty simply stated: implicitly what I’ve been talking about are real groups. Complex Lie groups are group structures on complex manifolds. That is, they “locally look like” complex n-dimensional space. You may remember that the complex numbers look like a plane with the real numbers sitting inside on a line. A complex n-manifold looks like a real 2n-manifold, but there’s some extra structure floating around I’ll try to ignore. Basically it deals with how we can “scale” shapes in the manifold by imaginary amounts — how to “multiply by i” — but that’s really horribly oversimplifying.

If we’ve got the complex plane, how do we find the real numbers? You might think we can just read off which points have zero imaginary part, but this actually sort of begs the question: it assumes you already know what the real line in the complex plane is.

What we can do is think of the complex plane as a 1-dimensional complex manifold. Now there’s a “reflection” of the plane to itself that plays nice with the complex structure: complex conjugation, z\mapsto \bar{z}. The points that are their own conjugates make up the real line. But there’s another reflection that plays nice: z\mapsto 1/\bar{z}. The fixed points here are the circle of radius one!

Now we can see the nonzero complex numbers as a group with multiplication as its operation. Similarly we can see the nonzero real numbers with multiplication and the circle with addition of angles as groups. These are all one-dimensional Lie groups. Each of the latter two is a real form of the first one, and together they make up all the simple real and complex commutative Lie groups.

In general, real forms work something like this. There’s a “reflection” in the complex n-manifold whose fixed points form a real n-manifold. The technical details of how to find these things are more than I want to go into right now, but this is the visual geometric intuition I use.

As another more interesting example, consider the group SL(2,\mathbb{C}). This consists of all 2\times 2 matrices with complex entries:
\left(\begin{array}{cc}a&b\\c&d\end{array}\right)
with the property that ad-bc=1. This is a complex Lie group of dimension 3. It has two real forms. One you might be able to guess is SL(2,\mathbb{R}), where all the entries in the matrix are real. The other is SU(2), which is a subgroup of SL(2,\mathbb{C}) satisfying the requirement
\left(\begin{array}{cc}a&b\\c&d\end{array}\right)\left(\begin{array}{cc}\bar{a}&\bar{c}\\\bar{b}&\bar{d}\end{array}\right)=\left(\begin{array}{cc}1& 0\\ 0&1\end{array}\right)
Both SL(2,\mathbb{R}) and SU(2) are 3-dimensional real Lie groups.

Another interesting thing about them is looking for the biggest subgroup of either that can be made from the two 1-dimensional real groups above. You can only fit one copy of the nonzero real numbers into SL(2,\mathbb{R}) and no copies of the circle. On the other hand, you can fit one copy of the circle into SU(2) and no copies of the nonzero reals. At the complex level, we see this in the fact that you can only fit one copy of the nonzero complex numbers into SL(2,\mathbb{C}). Since these are the biggest commutative Lie groups we can find inside these groups, we say in each case that the group has “rank 1“. In fact, SL(2,\mathbb{C}) is the group A_1. The subscript tells the rank of the group — the biggest product of copies of the nonzero complex numbers you can fit inside.

Okay, so what about E_8? We see that it has rank 8, so there’s a product of eight copies of the nonzero complex numbers sitting inside. When we break E_8 down to a real form, each of these will collapse either into a circle or a copy of the nonzero complex numbers. If each one becomes a circle, the whole real form is called “compact” and things are actually pretty fantastically well-behaved. If we collapse each to a copy of the nonzero real numbers we get the “split” real form of E_8, and things are actually pretty fantastically evil. That’s the real Lie group that Adams’ team was working on.

[EDIT: Okay, as I've found I have to say, I've pretty drastically oversimplified things. More info in the link]

March 22, 2007 Posted by | Atlas of Lie Groups | 2 Comments

A rough overview

I’ve had a flood of incoming people in the past couple days, and have even been linked from the article in The New York Times (or at least in their list of blogs commenting on the news). As I said before, their coverage is pretty superficial, and I’ve counted half a dozen errors in their picture captions alone.

One of the main reasons I write this weblog is because I believe anyone can follow the basic ideas of even the most bleeding-edge mathematics. Few mathematicians write towards the generally interested lay audience (“GILA”) the way physicists tend to do, and when mathematics does make it into the popular press the journalists don’t even make the effort they do in physics to get what they do say right.

My uncle, no mathematician he but definitely a GILA member, emailed me to mention he’d read that mathematicians had “solved E8″, but had no idea what it meant. Mostly he was asking if I knew Adams (I do), but I responded with a high-level overview of what they were doing and why. I’m going to post here what I told him. It’s designed to be pretty self-contained, and has been refined from a few days of explaining the ideas to other nonmathematicians.

Oh, and I’m not above link-baiting. If you find this coherent and illuminating, please pass the link to this post around. If there’s something that I’ve horribly screwed up in here, please let me know and I’ll try to smooth it over while keeping it accessible. I’m also trying to explain the ideas at a somewhat higher level (though not in full technicality) within the category “Atlas of Lie Groups”. If you want to know more, please keep watching there.

[UPDATE: I now also have another post trying to answer the "what's it good for?" question. That response starts at the fourth paragraph: "I also want to...".]


I understand not knowing what the news reports mean, because most of them are pretty horrible. It’s possible to give a stripped-down explanation, but the popular press doesn’t seem to want to bother.

A group is a collection of symmetries. A nice one is all the transformations of a square. You can flip it over left-to-right, flip it up-to-down, or rotate it by quarter turns. This group isn’t “simple” because there are smaller groups sitting inside it [yes, it's a bit more than that as readers here should know. --ed] — you could forget the flips and just consider the group of rotations. All groups can be built up from simple groups that have no smaller ones sitting inside them, so those are the ones we really want to understand. Think of it sort of like breaking a number into its prime factors.

The kinds of groups this project is concerned with are called Lie groups (pronounced “lee”) after the Norwegian mathematician Sophus Lie. They’re made up of continuous transformations like rotations of an object in 3-dimensional space. Again, the Lie groups we’re really interested in are the simple ones that can’t be broken down into smaller ones.

A hundred years ago, Élie Cartan and others came up with a classification of all these simple Lie groups. There are four infinite families like rotations in spaces of various dimensions or square matrices of various sizes with determinant 1 (if you remember any matrix algebra). These are called A_n, B_n, C_n, and D_n. There are also five extras that don’t fit into those four families, called G_2, F_4, E_6, E_7, and E_8. That last one is the biggest. It takes three numbers to describe a rotation in 3-D space, but 248 numbers to describe an element of E_8.

Classifying the groups is all well and good, but they’re still hard to work with. We want to know how these groups can act as symmetries of various objects. In particular, we want to find ways of assigning a matrix to each element of a group so that if you take two transformations in the group and do them one after the other, the matrix corresponding to that combination is the product of the matrices corresponding to the two transformations. We call this a “matrix representation” of the group. Again, some representations can be broken into simpler pieces, and we’re concerned with the simple ones that can’t be broken down anymore.

What the Atlas project is trying to do is build up a classification of all the simple representations of all the simple Lie groups, and the hardest chunk is E_8, which has now been solved.

March 22, 2007 Posted by | Atlas of Lie Groups | 7 Comments

Rubik’s Group and the solution to the cube

Okay, we’re ready to find the structure of Rubik’s group. We’ve established the restrictions stated in my first post. Now we have to show that everything else is possible.

The main technical point here is that we can move any three edge cubies to any three edge cubicles, and the same for corners. I don’t mean that we can do this without affecting the rest of the cube. Just take any three cubies and pick three places you want them to be, and there’s a maneuver that puts them there, possibly doing a bunch of other stuff to other cubies. I’ll let you play with your cubes and justify this assertion yourself.

A slightly less important point is that we only need to consider even permutations of corners or edges. We know that the edge and corner permutations are either both even or both odd. If they’re odd, twist one side and now they’re both even.

Now, let’s solve the edge group. The maneuver
e_F=RUD^{-1}FUD^{-1}LUD^{-1}BUD^{-1}R^{-1}U^{-1}DB^{-1}U^{-1}DL^{-1}U^{-1}DF^{-1}U^{-1}D
has effect (+fr)(+br), flipping two edge cubies, while the maneuver
e_3=R^2UD^{-1}F^2U^{-1}D
has effect (fr\,br\,fl), performing a cycle of three edges. This is all we need, because 3-cycles are enough to generate all even permutations, and one 3-cycle gives us all of them. Similarly, being able to flip two edges gives us all edge flips with zero total flipping.

How does this work? First, forget the orientation of the edges and just consider which places around the cube they’re in. This is some even permutation from the solved state, so it’s made up of a bunch of cycles of odd length and pairs of cycles of even length. Consider an odd-length cycle (a_1\,a_2\,...\,a_k). If we compose this with the 3-cycle (a_k\,a_{k-1}\,a_{k-2}), we get (a_1\,a_2\,...\,a_{k-2}). This is again an odd-length cycle, but two shorter. If we keep doing this we can shrink any odd cycle down to a 3-cycle. On the other hand, we have the composition (a_1\,a_2\,a_3)(a_2\,a_3\,a_4)=(a_1\,a_2)(a_3\,a_4), so we can build a pair of 2-cycles from 3-cycles. We can use these to shrink a pair of even-length cycles into a pair of odd-length cycles, and then shrink those into 3-cycles. In the end, every even permutation can be written as a product of 3-cycles.

And now since we can move any three cubies anywhere we want, one 3-cycle gives us all of them. Let’s pick three — say ub, br, and df — and a maneuver m that sends ub to fr, leaves br alone, and sends df to fl. Such a maneuver will always exist, though it may mess up other parts of the cube. Now conjugate e_3 by M. We know what conjugation in symmetric groups does: it replaces the entries in the cycle notation. So the maneuver me_3m^{-1} has the effect (ub\,br\,df), and we can do something similar to make any 3-cycle we might want. So we can make any even edge permutation we want, and adding a twist makes the odd permutations.

The same sort of thing works for edge flips. Take any pair of edges you want to flip, move them to fr and br, flip them with e_F, and move them back where they started. We can make any flips we need like this.

Together what this says is that the edge group of the Rubik’s cube lives in the wreath product of S_{12} and \mathbb{Z}_2: twelve copies of \mathbb{Z}_2 for the flips, permuted by the action of S_{12}. Specifically, the edge group is the subgroup with total flip zero. We call this group E, and we know E\subseteq S_{12}\wr\mathbb{Z}_2 as a subgroup of order 2.

A very similar argument gives us the corner group. The maneuver
c_T=R^{-1}D^2RB^{-1}U^2BR^{-1}D^2RB^{-1}U^2B
has the effect (+urf)(-dlb), twisting two corners in opposite directions, while
c_3=R^{-1}DRUR^{-1}D^{-1}RU^{-1}
has the effect (urf\,ubr\,lfd), performing a 3-cycle on the corners. Conjugations now give us all 3-cycles, and these make all even corner permutations, and turning one more face makes all corner permutations. Conjugations also can give us all corner twists with zero total twist. This gives the corner group C\subseteq S_8\wr\mathbb{Z}_3 as a subgroup of order 3.

Putting these two together we get the entire Rubik’s Group G\subseteq E\times C as a subgroup of order 2. Here it’s a subgroup because we can only use maneuvers with the edge and corner permutations either both even or both odd, not one of each.

This result gives us an algorithm to solve the cube!

  • First, pick the colors of the face cubies to be on each side.
  • Then write out the maneuver that will take the scrambled cube to the solved one in cycle notation. If the edge and corner permutations are odd, twist one side and start again — now they’ll both be even.
  • Now write the edge permutation as a product of 3-cycles, and make each 3-cycle by conjugating e_3 by an apropriate maneuver.
  • Do the same for the corner permutation, using c_3 as the basic piece.
  • Write down how each edge and each corner needs to be flipped or twisted. Make these flips and twists by conjugating e_F and c_T.

That’s all there is to it. It’s far from the most efficient algorithm, but it exploits to the hilt the group theory running through the Rubik’s Cube. You should be able to apply the same sort of analysis to all sorts of similar puzzles. For example, the 2\times2\times2 cube is just the corner group on its own. The Pyraminx uses a simpler, but similar group. The Megaminx is more complicated, but not really that different. It’s just group theory underneath the surface.

March 21, 2007 Posted by | Group theory, Rubik\'s Cube | 4 Comments

Follow

Get every new post delivered to your Inbox.

Join 393 other followers