Rebooting...

Time for a reboot, now with +Infinity more Haskell.

Hang on a second!

Haven't I just said that there are essentially 4 multiplication tables for Z2xZ2 and 12 for Z4? 16 in total? Shouldn't be 2 questions with 4 different answers each be enough?

Sadly, no.

It's not fair!

Let's start with "muliplication tables". Or at least, things which look like them.

In Greg and Kathleen's current case this would come down to 4 by 4 arrays of numbers between 1 and 4. For each of the 16 spaces, there are 4 choices, so there are a total of 4^16 tables to consider. That's about 4.2 billion, if you didn't know already. Greg could interpret 'pick a group at random of a given size' as 'generate a random multiplication table of a given size, check if it's a group otherwise try again'.

I'm not going to get the entire argument written down now (although it's quite interesting, and I probably should, see the hint below) here's the gist of it:

Given that a group of size 4 is either Z4 or Z2xZ2
- if it is Z2xZ2, there are only 4 possible tables, one for each choice of identity.
- if it is Z4, there are 4 possibilities for the identity element, and 3 remaining for the element of order two. Twelve in total.

Not completely coincidentally, 4!/|Aut(Z2xZ2)| = 24/6 = 4 and 4!/|Aut(Z4)| = 12.

So, for groups of order 4, it seems quite reasonable to posit a distribution of 1/4(Z2xZ2) + 3/4(Z4). This in turn tells Kathleen something about her strategy (at least for the case n=4!), but also makes the arguments much more complicated above a certain number; 4096 comes to mind again. How is Greg to make a reasonable random choice of groups when he first needs to spend his enire lifetime (and then some!) finding a suitable group?

[ 4096^(4096^2) is a large number. A 1 with 60 million zeroes, give or take, in decimal notation. In binary it would be a 1 with 12*2^24 zeroes (take exactly minus one). ]

So we have to frame our question more precisely: given that Greg draws a group from the multiplication tables uniformly, what is Kathleen's best strategy? And what is additional information about Greg's group worth? Things I'm thinking about here are:
- being abelian
- having a generating set of a specified size
- being simple

Given a choice between the 5 groups of size 8 (with fixed but undetermined (by me!) probability distribution), what question would you like to ask first, and what's it worth to you?

Things I don't know about and don't want to get into just yet

I don't know much about Nash-like game-theory, except that - at this stage - I don't want to know more about it.

The way I see it, when considering the 4-element game, Greg has one continuous strategy parameter (is that even a word?), namely the probability p with which to choose the (plausibly more profitable) group Z4. Kathleen has considerably more leeway (I think) varying from using the correct algorithm outlined before, via calling out a group at probability q_i at any of the branching points in her algorithm to just saying Z4 or Z2xZ2 at random (read: at a fixed probability q_0).

So I think I should just fix Greg's choice to a given distribution of groups for a given size (let's say uniform over isomorphism type) and let Kathleen do her best. Of course, this is evading difficult questions! What if Greg says 4096? Reasonable number, right? Nobody has any precise idea how many different isomorphism types of groups there are for that size of group, but I can tell you one thing: it is huge!

This leads us to the next question: when is a given distribution of groups fair?

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