Games and Groups: Part 2

A bit of notation: Z4 is the cyclic group with four elements, Z2xZ2 is the direct product of (you guessed it!) two cyclic groups of order 2. Z4 has one element of order 2 and two of order 4, whilst Z2xZ2 has three elements of order 2.

When we last left Greg and Kathleen, Kathleen had devised a strategy for guessing the group Greg had in mind.
Kathleen's strategy was (a snippet of my test implementation and sorry about the indentation):

int a00 = greg.ask(0, 0);
if (a00 == 0) {
// el. 0 is identity
if (greg.ask(1, 1) == 0) {
// el. 1 has order 2
if (greg.ask(2, 2) == 0) {
// el. 2 has order 2
return z2z2;
} else {
// el. 2 has order 4
return z4;
}
} else {
// el. 1 has order 4
return z4;
}
} else {
// el. 0 has order 2 or 4.
if (greg.ask(a00,a00) != a00) {
// el. 0 has order 4
return z4;
} else {
// a00 is the identity, 0 has order 2
int other;
if (a00 == 1) {
other = 2;
} else if (a00 == 2) {
other = 3;
} else {
other = 1;
}
if (greg.ask(other, other) == a00) {
return z2z2;
} else {
return z4;
}
}
}

If Greg has Z4 in mind, Kathleen needs 2+1/3 guesses on average, while if Greg has Z2xZ2 in mind, she needs 3 (not even on average, always!). I got these numbers by running the game repeatedly, but they seem reasonable. The "return z2z2" statement is always three 'if's down, as you need the identity and two elements of order two to get to Z2xZ2. In some cases, Z4 can be settled on more quickly.

So if Greg chooses randomly, Kathleen will need 2 + 2/3 guesses.

Greg, being the greedy bastard that he is, will however seek to maximize his gains. He could choose the more expensive Z2xZ2 more often. Not too often, though, as Kathleen could just blindly guess Z2xZ2 if Greg always chooses Z2xZ2 in the hope of getting 3 EUR from Kate every time. (This all depends on the penalty Kathleen has to pay when she guesses wrong).

Suppose Greg chooses Z2xZ2 with probabilty p, and Z4 only with probability (1-p). This ups Greg's revenue to p*3 + (1-p)*(7/3) = 7/3 + 2p/3.

So Kathleen had better come up with a strategy that costs her at most 7/3 in both cases! Does such a strategy exist? I don't know (yet!)....

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...