Black box recognition of sporadic simple groups

[alias_sqbr]

Since the server is down until who knows when, and I very occasionally find it useful to link to: a description of what my Phd thesis is about, much the same as the link I posted here last January. I tried to make it as accessible as possible but I will understand if the math phobic of you choose not to click :D Sorry for all the tables.


Part of my thesis was on "The black box recognition of sporadic simple groups". But what does "The black box recognition of sporadic simple groups" mean?

---

Transcript:
Me: Are you the Lyons group?
Black box group: Nope
Me: How about Higman-Sims?
Black box group: Maaaybe
(Lyons and Higman-Sims are two of the sporadic simple groups
we wrote recognition algorithms for)

First off, what's a "group"?

Basically, a group is a set of mathematical objects (like numbers or matrices) plus an operation (something like addition or multiplication) which "makes sense". Specifically, a group under the operation * satisfies the following properties:

• If a and b are in the group then so is a*b.
  
• (a* b)* c = a*(b*c) for all a, b, and c in the group.
  
• There is an "identity" element I such that a*I = a and
  I*a = a for any a in the group.
  
• For every group element a there is an "inverse" a^-1 such that a*a^-1 = I and a^-1*a = I.
  

A simpler explanation with no algebra and more examples.

Recognising groups

Group recognition is when someone gives you a group and you have to work out which group it is.

For example, consider the group H you get by multiplying these two matrices together in any order, any number of times:

-1 1 0 1

and

1 0 1 -1

(The fact that H is a group is pretty easy to check)

Two elements of H are:

-1 1 0 1

*

1 0 1 -1

=

0 -1 1 -1

and

0 -1 1 -1

*

-1 1 0 1

=

0 -1 -1 0

How big is H? What does it look like? Are there any other smaller groups inside H?

These sorts of questions are all a part of group recognition. My research was into writing algorithms to recognise specific groups which are given in an especially tricky format called a black box group.

Black box groups

With a matrix group like H in the previous example, you can figure out a lot about an element of the group by looking at it. You can calculate matrix functions like the characteristic polynomial and determinant and see what it does when you apply it to vectors and other things outside H. This can really help when you're trying to recognise the group.

But with a black box group you don't know any of that stuff. You're effectively given a list of names a, b, c etc for the elements of the group and all you can calculate is group operations like a*b=c or a^-1=d.

This makes recognising a black box group really hard, but any algorithm which works for a black box group will work for any other group, so they're very useful.

"Recognising" a black box group G means finding another group H which acts the same way as G if we rename all the elements the right way. For example, suppose we have a group black box group G={a, b, c...} and we think it's a renaming of the matrix group H above. If we set

a

=

-1 1 0 1

,

b

=

1 0 1 -1

and

c

=

0 -1 1 -1

then for our renaming to be correct it needs to be true that a*b=c inside G, since this is true inside H.

Figuring out and proving your renaming (called an isomorphism) is what group recognition is all about.

The sporadic simple groups

A set of 26 hard-to-recognise groups whose sizes range from a few thousand to more than 10⁵⁰ elements.
We developed a technique for recognising black box groups called "subset sifting", and used this technique to create recognition algorithms for six of the smaller sporadic simple groups.



Transcript:
Me: Aw, it's the baby monster!
In front of me is the "tiny" baby monster with only 4*10³³ elements. Behind me is the much larger Monster group, with 8*10⁵⁴ elements.

We didn't actually make recognition algorithms for the monster or baby monster groups because they're huge.

Black box recognition of sporadic simple groups

So in summary, we were trying to figure out the nature of (recognise) some particularly tricky (black box) mathematical objects (sporadic simple groups).

How we did this is a whole nother topic for another day :) But if you're interested in this stuff, you could have a look at the Wikipedia page on Sporadic Simple Groups.

Comments

[sanguinity]

Oo! Math cartoons. I like the baby monster! :-D

Oh, it's been a long time. I don't even have any gut sense any more about why associativity is a "makes sense" condition, and I'm pretty sure I used to. ;-)

[sqbr]

I don't even remember what all of this means any more! I just checked it for html errors and trusted that past!me knew what she was talking about :)

[fred_mouse]

I think it should terrify me that everything that you wrote makes perfect sense. Or maybe it is just that it is late at night, and I just think that I understand what you have written.

And I love the cartoons!

[alias_sqbr]

Well I was trying to make it accessible to a generic vaguely geeky audience and you're not exactly a math-o-phobe :) Thanks.

[fred_mouse]

true. but group theory is the only unit I've ever failed. I blame serious tonsillitis, and TP's teaching style (after lunch)