Reword your resolutions

I had various degrees of (lack of?) success setting goals. Most of the goals I had were pretty standard and dryly worded: "one tweet per day", "finish reading data viz books", etc. Even though these are things I really want to do, just reading the list was a little draining.

But one goal was different. It was written:

Meet Colbert.

This was in reference to the Hacking Education contest. Entering the contest was really an excuse to practise playing with data and writing about the results in my new data blog. Colbert wasn't even relevant. Even then, those two words made me smile. It excited me, so much that I just had to work on it... Although I didn't end up meeting Colbert, I accomplished what I was really after.

It's so much easier to stick to goals that make you smile, that motivate you, and that capture the desired result rather than the hard work required (even though the hard work is just as important). So if you're setting goals, make them interesting. Make them playful. Make them funny. Figure out what excites you, then use that as a proxy for what you actually want to accomplish (e.g. "meeting colbert" as a proxy for "start a data blog and write stuff in it").

Happy 2012 and if you have some resolutions in mind, good luck!

End of Entry

Galois Theory in 1500 Words

[This is a very brief overview of Galois theory. It's not meant to be rigorous, so apologies in advance for leaving out a lot of details and avoiding some delicacies. It was meant to be intuitive and light on math, but it turned out to be neither. If you aren’t familiar with field and group theory, well... proceed at your own risk...]

For a long time, people wondered whether it is possible to write down something like the "quadratic formula" for cubic, quartic and quintic polynomials with integer coefficients. We now know that for cubic and quartic polynomials, this is possible. But for degree 5 polynomials and beyond, it isn't. A proof of this was scribbled down hastily by Galois the night before his duel. Galois linked together field theory and group theory in a beautiful way to answer this very question.

Galois’s Approach: The Big Idea

What does writing down a “formula” for roots of a polynomial really mean? For one, we’d be writing down the roots in terms of rational numbers and a combination of +, -, x, ÷, and radicals (taking n-th roots). This is a very limited set of operations, and certainly not all real numbers can be written this way -- π, for example, can’t be written this way. We say that π is not solvable in radicals.

Are the roots of polynomials with integer coefficients solvable in radicals? Those roots aren’t just any real number, and certainly π is not a root of any polynomial with integer coefficients. Yet Galois showed that there are some degree-5 polynomials with roots that are not solvable in radicals. To see how he did this, we first need some terminology about fields, field extensions, and groups.

Fields

The set of rational numbers Q is an example of a field: a set of things you can add, subtract, multiply and divide. We can “extend” Q into bigger fields by adjoining things to it. For example, L=Q(√2) -- pronounced "Q adjoined root two" -- is defined to be the smallest field that contains both Q and √2, and is closed under +, -, x, and ÷. Here elements of Q(√2) are exactly numbers that can be written in the form (a+b√2)/(c+d√2) where a, b, c, d are integers. We call such a field L a (field) extension over Q (written L/Q).

When we're adjoining √2 to Q to construct Q(√2), what we're really doing is adjoining to Q a root of the polynomial f(x)=x² -2. We could do this with other higher-degree polynomials. Let p(x) be a polynomial with integer coefficients (and no repeating roots). We define the splitting field K of p(x) to be the smallest field containing both Q and all the roots of p(x). For example, the splitting field of p(x)=x²+1 has roots i and -i so a splitting field K of p(x) is K=Q(i,-i)=Q(i). (The last equality is true because 0 and i are in Q(i), so -i=0-i is also in Q(i)).

Conversely, we call an extension K/Q a Galois extension if it is the splitting field of some polynomial p(x). From before, Q(i)/Q is a Galois extension.

Q-Fixing Automorphisms

An automorphism F of a field K is an isomorphism from K to itself, where the algebraic structure is preserved -- specifically, F(a+b)=F(a)+F(b), F(ab)=F(a)F(b). In the case that K is an extension of Q, we’re more interested in automorphisms of K that has F(x)=x for all x in Q (or that F fixes elements of Q). An automorphism F of K is a Q-fixing automorphism if it has this property.

There are two Q-fixing automorphisms of L=Q(√2): the identity automorphism (call it e) that takes each element of Q(√2) to itself, and an automorphism (call it t) that takes anything from Q to itself, and √2 to -√2. It is possible to show that there is exactly one such automorphism t.

Groups

A group is a set with a "composition" operation • with an identity element. From above, the set of Q-fixing automorphisms of K, denoted G(K/Q) is a group with • being function composition, and e being the identity element. Observe that we do not require • to be commutative (so a•b may not be the same as b•a in this case).

Two groups are isomorphic if they have the same algebraic structure -- i.e. they’re essentially the same group except the elements have different names. It is useful to see whether G(K/Q) is isomorphic to a group that we know and understand. Two important classes of groups that are well understood are cyclic groups and permutation groups.

Examples of Groups

The cyclic group C(n) of order n is the set {0,1,2,3,..,n-1}, with • being addition mod n. From the example of L=Q(√2), L has G(L/Q)={e,t} with • being function composition. This is actually isomorphic to C(2)={0, 1}.

Permutation groups consist of functions that permute some "letters". We'll use S(n) to denote the group of permutations of n letters. For example, S(3) is all the permutations of letters {a, b, c}. A function F that takes a→b, b→a, c→c is one such permutation (and hence an element of S(3)).

The Fundamental Theorem of Galois Theory

Galois noticed that for a Galois extension K/Q, there is a link between "subfields" of K containing Q, and "subgroups" of  G=G(K/Q). The quoted words mean exactly what you might think -- a subfield of K is a field L that is contained in K (and is closed under +, -, x, ÷). For example, Q is a subfield of R, and Q is a subfield of Q(√2). A subgroup of G is a group H that is contained in G (that is closed under • and contains the identity element).  For example, the subset {0,2,4} is a subgroup of C(6) = {0,1,2,3,4,5}.

More concretely, there is a 1-1 correspondence between subfields of L and subgroups of H:

• For a subfield L of K containing Q, there is a subgroup H of G corresponding exactly to the automorphisms that fix all of L -- i.e. f(x)=x for all x in L, not just Q.
• The reverse is true as well: if H is a subgroup of G, then there is some subfield L of K containing Q that is fixed by all of H.

In particular, whenever L/Q is itself a Galois extension, H is a normal subgroup of G. Think of H being normal as H being well-behaved enough that the quotient G/H is another group. We won't get into what this means, but this group G/H turns out to be isomorphic to G(L/Q).

For a concrete example, let’s take K=Q(i, ∛2). It’s possible to show that K/Q is a Galois extension, and that G=G(K/Q) is isomorphic to S(3). In particular, the subfields of K are Q(i) and Q(∛2), and they correspond to subgroups of S(3) isomorphic to C(3) and S(2). We saw before that Q(i) is a Galois extension, and C(3) happens to be normal in S(3).

Linking Back to the Big Idea

Suppose p(x) is a degree 5 polynomial, and that it has a root x that is solvable in radicals. Then really, x is in some field K containing Q, where K can be "built up" from Q by successively adjoining (n√α), the n-th root of α, for some n and α. For example, take  x=√(2+ √5). We set L=Q(√5) and K=L(√(2+√5)) to "build up" K in this manner.

Solvable Fields

In general, we call an extension K/Q solvable if K=K0⊇K1⊇K2⊇...⊇Q, where each K(i-1)=Ki(n√α) for some n and α. This is exactly the construction we had a paragraph ago. As another example, K=Q(i, ∛2) is a solvable extension since Q(i, ∛2)=Q(i)(∛2)⊇Q(i)⊇Q is in the desired form (recall i=√(-1)).

For a polynomial p(x) in Q, the splitting field K of p(x) is the smallest field containing all the roots of p(x), so the roots of p(x) are solvable in radicals if and only if K is solvable.

Solvable Groups

We can actually assume (ignoring some subtleties) that each K(i-1)/Ki from above is a Galois extension. In this case each G(K(i-1)/Ki) is actually isomorphic to C(n) for some n.

Thus in order for a field extension K/Q to be solvable, G=G(K/Q) must be in a particular form: there has to be a chain of subgroups,  G=G0⊇G1⊇G2⊇...⊇{e}, where each Gi is a normal subgroup of G(i-1) and Gi/G(i-1)=C(n) for some n, and {e} is the trivial group with just the identity element. In the case of K=Q(i, ∛2), the chain of subgroups looks like G(K/Q)=S(3)⊇C(3)⊇{e}.

A Quintic Formula Cannot Exist

To recap, roots of p(x) being solvable in radicals requires the splitting field K of p(x) to be a solvable field, which in turn requires G(K/Q) to be a solvable group.

But with a little group theory, we can show that S(5) is not solvable. Further, any quintic polynomial with two non-real roots has Galois group S(5). These last facts require some more concepts to develop, but in any case -- not all roots of quintic polynomials are solvable in radicals.

End of Entry

Visualizing 4+ Dimensions

When people realize that I study pure math, they often ask about how to visualize four or more dimensions. I guess it's a natural question to ask, since mathematicians often have to deal with very high (and sometimes infinite) dimensional objects. Yet people in pure math never really have this problem.

Pure mathematicians might like you to think that they're just that much smarter. But frankly, I've never had to visualize anything high-dimensional in my pure math classes. Working things out algebraically is much nicer, and using a lower-dimensional object as an example or source of intuition usually works out -- at least at the undergrad level.

But that's not a really satisfying answer, for two reasons. One is that it is possible to visualize high-dimensional objects, and people have developed many ways of doing so. Dimension Math has on its website a neat series of videos for visualizing high-dimensional geometric objects using stereographic projection. The other reason is that while pure mathematicians do not have a need for visualizing high-dimensions, statisticians do. Methods of visualizing high dimensional data can give useful insights when analyzing data.

"But there aren't any more direction to draw the fourth axis..."

A professor would draw the usual x, y and z-axis on the 2D chalkboard, then announce that there aren't any more directions remaining to draw another axis until someone invents a 3D chalkboard. Then I would die a little.

Of course there is! How did we pick the direction to draw the z-axis on a 2D surface? We picked a direction not parallel to the x and y-axis, kind of at random (because any such direction would work). In doing so, we decided on a projection of the 3D space onto the 2D surface, like this:

There are some ambiguities as to which points in the 3D space these black points actually represent. In fact, each point above has an entire line projecting to it. Sometimes, authors would disambiguate points by dropping a line parallel to the z-axis down to the x-y plane, like this.

So, as we said before, we add a 4th dimension by drawing a t-axis not parallel to any existing axis. Here each point have an entire plane projecting to it, so we drop down another a line parallel to the t-axis to disambiguate. We get this.

So voila, we get a projection of 4D space onto the 2D surface of your screen. The following image from Wikipedia showing hypercubes of dimensions 1-4 uses the same method as above:

Technically speaking, this method can work for any number of dimensions, but things gets messy and confusing very quickly. Even in the 4D plot above it's challenging to wrap your head around what's happening -- dropping verticals parallel to all the other axes might help a bit, but even in 5D this would get pretty messy. Perhaps that's why the images of the hypercube stopped at dimension 4. 

So, are there nicer ways of visualizing even higher dimensional data?

Parallel Coordinates, star plots, etc

Yes, there are many, and they are often used in statistics. One simple technique is to map certain dimensions to other features of each "point" -- its shape, colour, size, etc. This is so often done that you probably wouldn't even think of it as a visualization technique, but it works for visualizing a few more dimensions. There are other techniques, too:

Radial plots have all the axes in a circle, like below, with each "point" or observation drawn as a polygon with vertices determined by its value along each axes. Sometimes it is better to make separate plots for each "point", since overlapping lines can make the chart messy. Again this works well for visualizing a handful of dimensions, and small number of "points" or observations.

Parallel coordinate plots are like unwrappings of the above. A "point" becomes a series of line segments connecting its values along each dimension. This chart is considerably less messy, so a larger number of "points" can be plotted on a singe graph.

Then there are goofier things like Chernoff's faces, which maps dimensions to features of faces. The idea is that since we are biologically hardwired to tell apart faces, we'd be able to easily tell which data points are similar to each other and which ones are different.

All of these plots make it relatively easy to find clusters within the data. However, it is difficult to find geometric properties: Can you imagine what points on a tetrahedron in 3D would look like here? A sphere? Thus from a mathematical standpoint, these graphics do not preserve anything that is usually of geometrical importance (angels, lengths, etc) -- stereographic projection fare better, but algebraic techniques are often quite powerful.

Visualizing High Dimensional Data is a Statistician's Problem, not a Mathematician's

To conclude, it is possible to visualize high dimensional objects. However, from the point of view of a pure mathematician, such visualizations are usually less helpful compared to algebraic techniques and intuitions on how low-dimensional object behave. Thus the problem of visualizing high-dimensions is a statistician's problem. Statisticians have much more to gain from visualizing their high-dimensional data.

So if you ever want to ask this question to a pure mathematician, ask a statistician instead. They'll be able to give you a better answer.

[PS: As @chlalanne pointed out, statisticians have built pretty good tools for visualizing high dimensional data. GGobi is a pretty powerful one. It interfaces with R through the rggobi package.]

End of Entry