A look at a few Tripos questions X

Since time is short, I am going to discuss a couple of Groups questions but in slightly less detail than I have been giving up to now: instead of working through the questions completely, I’ll try to zero in on the most important points. Because there wasn’t a separate Groups course until 2008, I am taking my questions from that year.

5E. For a normal subgroup H of a group G, explain carefully how to make the set of (left) cosets of H into a group.

For a subgroup H of a group G, show that the following are equivalent:

(i) H is a normal subgroup of G;

(ii) there exist a group K and a homomorphism \theta:G\rightarrow K such that H is the kernel of \theta.

Let G be a finite group that has a proper subgroup H of index n (in other words, |H|=|G|/n). Show that if |G|>n!, then G cannot be simple. [Hint: Let G act on the set of left cosets of H by left multiplication.]

The first part of this is bookwork, so I shan’t go through it. However, let me remark that there is one how-much-to-write decision to make here. Is it enough to say that we define the product of g_1H and g_2H to be g_1g_2H, or do we need to prove that that operation is well-defined (meaning that if g_1H=g_1'H and g_2H=g_2'H then g_1g_2H=g_1'g_2'H)? There is a simple principle that determines the answer to this question: if you are in doubt, and the question says “explain carefully”, then that word “carefully” is telling you to go for the more careful option. So it’s pretty clear here that you are intended to prove that the operation is well-defined, rather than merely stating it or, worse still, failing to mention the issue at all.

Next, we’re asked to prove that kernels of homomorphisms and normal subgroups are the same thing. The proof that kernels of homomorphisms are normal subgroups is easy, but the reverse is rather less so (I discussed this result in detail in this blog post). The rough answer is that if H is a normal subgroup, then it is the kernel of the quotient map from G to G/H. So we need to prove that that map is a homomorphism, but that follows directly from the definition of multiplication of cosets.

Now for the non-bookwork part of the question (though this little problem is often on examples sheets). If you are not comfortable with group actions, you may wonder how defining an action can help you prove that a group is not simple. But the answer to that question is simple (if you’ll excuse the very feeble pun).

1. G is not simple if and only if G has a non-trivial normal subgroup. [Definition of “simple”.]

2. So we want a non-trivial normal subgroup.

3. The question is begging us to find a homomorphism with non-trivial kernel, by which I mean a kernel that is not the identity and not the whole of G. [Remark: even if the question were not begging us to do that, defining homomorphisms and taking their kernels is still a very good way of coming up with normal subgroups.]

4. We’re given a group action.

5. But group actions are homomorphisms (or, if you prefer, naturally associated with homomorphisms). So let’s think about the kernel of the group action we are given. [Remark: similarly, it is a good general rule that group actions give us a nice big supply of homomorphisms.]

What does G do to the left cosets? It permutes them. Since H has index n, there are n left cosets. The axioms for group actions tell us that the action on G is a homomorphism from G to the group of permutations of the n left cosets of H, which is isomorphic to the permutation group S_n. The action is non-trivial, in the sense that at least some elements of G do not perform the identity permutation on the left cosets (proof — pick g\notin H and observe that gH\ne H).

Now where is this condition that |G|>n! going to come in? Ah, the relevance of that n! is that it is the size of the group S_n. So we have a non-trivial homomorphism from G to S_n, and G is strictly larger than S_n. Therefore, it has a non-trivial kernel. And we’re done.

The eventual proof can be written concisely as follows.

There are n left cosets of H, so the group of permutations of these left cosets has size n!. The left-multiplication action is a homomorphism from G to this group, and since |G|>n!, this action must contain elements other than the identity in its kernel. On the other hand, the kernel is not the whole of G, since any element g\notin H permutes the left cosets of H non-trivially. Therefore, the action of G has a non-trivial kernel, which is a non-trivial normal subgroup, so G is not simple.

I have already said that you’ll get more out of these posts if you try the questions first. That is particularly true of this next question: if you solve it for yourself you’ll have really learnt something.

7E. Show that every Möbius map may be expressed as a composition of maps of the form z\mapsto z+a, z\mapsto \lambda z and z\mapsto 1/z (where a and \lambda are complex numbers).

Which of the following statements are true and which are false? Justify your answers.

(i) Every Möbius map that fixes \infty may be expressed as a composition of maps of the form z\mapsto z+a and z\mapsto\lambda z (where a and \lambda are complex numbers).

(ii) Every Möbius map that fixes 0 may be expressed as a composition of maps of the form z\mapsto\lambda z and z\mapsto 1/z (where \lambda is a complex number).

(ii) Every Möbius map may be expressed as a composition of maps of the form z\mapsto z+a and z\mapsto 1/z (where a is a complex number).

A quickish way of doing the first part is to observe that the class of maps we are allowed to use is closed under inversion: the first is inverted by z\mapsto z-a, the second by z\mapsto\lambda^{-1}z (since we will not take \lambda=0), and the third by itself. So if we can convert (az+b)/cz+d) into z by applying maps of the three kinds, then doing the inverses of those maps in the reverse order will convert z into (az+b)/(cz+d).

How can we simplify (az+b)/(cz+d)? It’s tempting to subtract a/c, because that looks as though it will simplify the fraction. And indeed,

\displaystyle \frac{az+b}{cz+d}-\frac ac=\frac{c(az+b)-a(cz+d)}{c(cz+d)}=\frac{bc-ad}{c(cz+d)}

We don’t want to carry too many complicated expressions around, so we might as well rewrite this as e/(fz+g), remarking that e\ne 0, by the definition of a Möbius map. To simplify this, an obvious move is to turn it upside down. That gives us (fz+g)/e, which we can write as hz+k. And now it’s obvious that we can get to z by subtracting k and dividing by h. Or is it? We need h not to be zero. That’s a problem, because it is conceivable that h is zero. I’ve overlooked the possibility that c might be zero. Probably the easiest way of dealing with that is to observe that when c=0 the problem is easy.

OK, let’s move to the three true-or-false problems.

(i) Under what circumstances does a Möbius map fix \infty? The limit as z\to\infty of (az+b)/(cz+d) is a/c, so we need c=0, which implies that a\ne 0. It also implies that d\ne 0, so we have a map of the form ez+f, which can obviously be expressed in the desired way. So that’s one TRUE.

(ii) A Möbius map (az+b)/(cz+d) fixes 0 if and only if b=0, which implies that implies that neither a nor d is 0. Since we’re allowed the transformation 1/z, let’s think about (cz+d)/az rather than about az/(cz+d). Can we express (cz+d)/az using a combination of scalar multiplication and reciprocals? It looks a bit difficult because of that plus sign.

There are two natural ways that one might think of proceeding from here. We suspect that the result is false, so we could either try to understand which maps can be expressed as combinations of scalar multiplication and reciprocals, or we could try to find some property that distinguishes all such maps from the map (cz+d)/az (for suitably chosen a,c,d). Let’s try both approaches.

A little experimentation suggests that the only maps you can make out of z\mapsto\lambda z and z\mapsto 1/z are of the form z\mapsto\mu z or z\mapsto \mu/z. Indeed, we can make all these maps, and if you multiply one of them by \lambda or take its reciprocal you get another one. But the map (z+1)/z is not of that form, so we’re done.

But why am I so confident that it is not of that form? After all, the representation of a Möbius map is not unique. It’s not hard to be sure about this, but in the end I think the nicest way of doing it is to go for the second approach. And a natural thing to think about when you’re trying to distinguish between Möbius maps is fixed points, or more generally fixed sets of points. What can we say about the two maps we’re allowed to use? Multiplying by \lambda fixes 0 and \infty< while taking the reciprocal swaps 0 and \infty. So either way, the set \{0,\infty\} maps to itself. Since (z+1)/z takes \infty to 1, it can't be expressed in the desired way. So that's a FALSE.

(iii) This looks like a FALSE as well, since when we started the question we certainly made use of scalar multiplication. So let’s try to find a special property that compositions of translation and reciprocation have that a general Möbius map does not need to have.

Another thought is this. If some Möbius map is not going to have the property, then some scalar multiplication won’t have the property, assuming, that is, that the property is closed under composition, which it more or less has to be if it is going to be at all natural. So maybe we should look for a property that the map z\mapsto 2z fails to have that all compositions of translations and reciprocation have.

What might this property be? It’s difficult to see where fixed points might come in, because translations fix just \infty and once you start composing with 1/z there is no obvious pattern. But one thing we can say is that translations don’t stretch the complex plane. Could that help? Might there be some sense in which every composition of translations and 1/z is either “on average” like a translation or “on average” like a translation of 1/z?

It seems difficult to come up with a pithy definition, so let’s switch to the other kind of approach: just getting a feel for what kinds of maps we can generate.

And here is a general and very useful group theory tip: think about conjugations. Almost always, a conjugation will be more informative than some arbitrary composition. So in a spirit of experimentation, let’s conjugate z+a by 1/z and see what we get. And later we might conjugate 1/z by z+a.

The first conjugation takes z to 1/z to a+1/z to 1/(a+1/z). That last map can be rewritten as z/(az+1). That’s interesting: it doesn’t look much like a translation. Can we simplify it? We could take the reciprocal, but that’s just undoing what we’ve done. Another possibility would be to subtract 1/a: at the moment the limit as z\to\infty is 1/a, so doing this subtraction would move it to 0, which ought to make things look nicer. And indeed,

\displaystyle \frac z{az+1}-\frac 1a=\frac{az-(az+1)}{a(az+1)}=\frac{-1}{a(az+1)}.

It’s looking awfully as though we’ve managed to get scalar multiplication in here. Let’s take the reciprocal. That gets us to -a^2z-a. Adding a simplifies this to -a^2z. Which complex numbers \lambda can be written as -a^2 for some complex number a. Er … all of them. So we’ve managed to generate all maps of the form z\to\lambda z, and therefore, by the introductory result, we get all Möbius maps.

I confess that I remember being told by the examiner that year that the answer was TRUE and that almost nobody got it. However, they would have got it if they had followed two basic principles, one general and one slightly more specific. The general one is to do a bit of experimentation: if you want to get a feel for what you can generate, then see what you can generate! The more specific one is that a great start in this process is to look at what you get if you conjugate some of your generators by other generators.

That more specific tip can be generalized: if you are doing a question about Möbius maps, there is a strong chance that conjugation will make things easier. Here’s a quick example. Suppose you are asked to find a non-trivial Möbius map that fixes the complex numbers 1 and 1+i. You could just define the map to be (az+b)/(cz+d), get some equations for a,b,c,d and find a non-trivial solution. But the calculations would be fairly unpleasant.

How much less unpleasant they would be if only the fixed points were something nice like 0 and \infty. Then we could just write down an example: the map z\mapsto 2z. Let’s call this map \phi. Is there some way of “transferring” this example to the one we’re actually asked for? Yes there is — conjugation. What we do is find a Möbius map \theta that takes 0 to 1 and \infty to 1+i. Then what does \theta\phi\theta^{-1} do to the point 1? It takes it first to \theta^{-1}(1)=0, where it remains fixed before returning to \theta(0)=1. Similarly, 1+i goes to \infty, stays still, then comes back again. Since \phi fixes no other points, \theta\phi\theta^{-1} fixes no points other than 1 and 1+i.

How easy is it to find a map that takes 0 to 1 and \infty to 1+i? The first condition tells us that b=d, and the second that a/c=1+i. So we can just write down an answer: ((1+i)z+1)/(z+1). That will be our \theta.

The remaining calculations are slightly tedious but basically easy. We need to work out the inverse of \theta (which is easy enough — just set that expression to be w and solve for z in terms of w). We then need to work out what happens to z if we apply \theta^{-1}, multiply by 2, and apply \theta.

You may question whether that was easier than the brute-force approach. So perhaps I should add that in theoretical questions it really is much easier. Suppose the question were to prove that for any two distinct complex numbers u and v there is a non-trivial Möbius map that fixes u and v and that gives you the identity after you do it four times. (That is, it has order 4 in the group of Möbius maps.) That would be truly horrible if you did it by brute force. However, if you use conjugation, you can observe that multiplication by i has the desired property, but with the fixed points 0 and \infty instead. Then you prove that there exists a Möbius map \theta that takes 0 to u and \infty to v. And then the conjugation does the job. And since the question merely asked you to prove that the map exists, you don’t even have to work out the conjugation, though it wouldn’t be too unpleasant if you did want to.

In general, conjugation can be thought of as what you do when you want to move the “centre of activity” to a nice place. You find a map \theta that takes the nice place to the place you’ve actually been given. Then you do \theta^{-1} to get to the nice place, followed by a nice transformation (which exists because the place is nice) followed by \theta to get back to the place you were given. It’s this basic idea that explains why expressions of the form aba^{-1} occur so frequently in mathematics. Less importantly, but more urgently, it also explains why conjugation occurs so frequently in Tripos questions.

6 Responses to “A look at a few Tripos questions X”

  1. Gareth Says:

    The general waffle I often use at the start of the n! part of the Groups question is as follows. Since my supervisees have found it useful, I thought I’d add it here.

    Suppose the group G acts on the set X, and that there are more elements in G than there are things we can actually do to X. Then, by the pigeonhole principle, some two things in G must have exactly the same effect on X. So doing one followed by the inverse of the other does nothing to X.

    Aha, something does nothing – so there is a non-trivial kernel (to some homomorphism). Now, is the kernel all of G? If not, then we have a non-trivial proper normal subgroup.

    So, if G does anything at all, and if G is bigger than |X|!, then G can’t be simple.

  2. Monday/Tuesday Highlights | Pseudo-Polymath Says:

    […] test approaches, fun with […]

  3. Stones Cry Out - If they keep silent… » Things Heard: e223v1n2 Says:

    […] The test approaches, fun with groups. […]

  4. robin harte Says:

    talking about “normal subgroups” of groups leads me to the idea of “normal” subgroups of semigroups – start with “generalized exponentials” in Banach algebras, they form the connected component of the identity in the invertible group: so what can you say about their left and right cosets in the larger semigroups of left and of right invertibles ? you can still multiply

    I am being uncareful here and not checking what I have looked at elsewhere, but the idea is a very simple extension of the usual quotient group idea, and is involved in a discussion of “spectral pictures”

  5. Groups and Group Actions: Lecture 16 | Theorem of the week Says:

    […] Tim Gowers writing about a couple of past Cambridge exam questions, including one with a rather nice […]

  6. Groups and Group Actions: Lecture 16 | Theorem of the week Says:

    […] Tim Gowers writing about a couple of past Cambridge exam questions, including one with a rather nice […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: