Saturday, September 22, 2007

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?