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?

No comments: