Tuesday, October 31, 2006

Games and groups: Introduction

Here's a simple game two people that know group theory can play:

The first player picks a finite group G. He tells the second player the size of the group, let's call it N, and labels the elements a, b, c and so on.

The second player now asks questions of player 1 of the form: "What is element x times element y?" repeatedly. The game ends when the second player can name the isomorphism type of G. The second player is allowed access to resources such as computers, group theory texts she's read, group theory texts she's heard of but didn't understand, and so on. Only mindreaders and spies are not allowed!

Let's call the first player Greg and the second player Kathleen.

To make things interesting, suppose Kathleen has to pay one euro for each question. If she guesses the isomorphism type of the group wrong, she has to pay 1+n^2 euros. What's her best strategy, and what is her expected loss? (If she really has no clue, she 's still better off by asking for the entire multiplication table and saying 'It's the group with multiplication table equal to this')

Here's a few games:
Greg: 1!
Kathleen: Trivial group. Duh!

Greg: 2!
Kathleen: Cyclic group of order 2. Not that hard!

Greg: 3!
Kathleen: Cyclic group of order 3. I'm still breaking even!

Greg: 4!
Kathleen: Oh dear...

Here's where it gets interesting! There are two groups of order four, the cyclic group of order four and the direct product of two cyclic groups of order 2, and Kathleen is going to have to distinguish between them somehow. The former group has two elements of order 4, one of order 2 and the identity, whereas all non-identity elements in the latter group have order 2. So one strategy for her could be to go hunting for elements with order 4. Let's have her have a shot:

Kathleen: What element a times element a?
Greg: Ha ha! It's element a! Congratulations! You've found out that every group has an identity!
Kathleen: Well, what's element b times element b?
Greg: Ummm, it's element c.
Kathleen: Gotcha! Element b has order 2 or 4 (it's not the identity, because that's element a), but by what you've just told me, it's not 2, because then element b times element b would've been element a. Cyclic group of order 4!
Greg: That'll be two euros, please.

Let's rewind the conversation to Greg's last answer. What would have happened if he said: "Element a, as well!"? In that case, Kathleen still would have had to decide between the two groups, but she's already found the identity element(being a) and an element of order two(that's b). If any of the remaing elements has order 4, then both have order 4 and G is the cyclic group of order 4. Otherwise, if either of the remaining elements also has order two, it's the direct product she's looking at. In any case, her next question ought to be (she's getting bored with saying element all the time)
Kathleen: what's c times c?
If Greg says a (the identity), c also has order 2 - so the group is a direct product of two copies of the group of order two; if he says b then c has order 4- so the group is cyclic of order four, and if he says c or d he's cheating!

But we can rewind farther than that. What if Greg's first answer had been element b (or c or d, for that matter)? Kathleen could have got lucky and picked an element of order 4 on the first try, and when she asks for the product of b and b and gets c or d as an answer, she knows she's dealing with the cyclic group of order four. On the other hand, the answer could be b and she would be none the wiser - only now, element a has order 2, element b is the identity. All Kathleen needs to know now is whether element c has order 2 as well (when c times c is b, the identity), or that c times c is a.

Confused yet? I know I am! Has Kathleen covered all her bases? Is her strategy optimal?
What's Greg's part in all of this? What can he do to confuse Kathleen?

A teaser for the next episode:

Greg: 5!
Kathleen: Cyclic group of order 5. Phew, another easy one!

Greg: 6!
Kathleen: Can I ask you a question?
Greg: Element times element products! One euro, only! Get them while they're hot! Or are you talking about something else?
Kathleen: Is the group abelian?
Greg, Well, that's the 37 dollar question, now isn't it?
Kathleen: Well, the value of that question is...