alias_sqbr: me in a graduation outfit (doctor!)
[personal profile] 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?


black box group

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:

-11
01


 

and

 

10
1-1


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


Two elements of H are:


-11
01


*

10
1-1


=

0-1
1-1


 

and

 

0-1
1-1


*

-11
01


=

0-1
-10



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
=
-11
01


,
 
b
=
10
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 1050 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.

maths

Transcript:
Me: Aw, it's the baby monster!
In front of me is the "tiny" baby monster with only 4*1033 elements. Behind me is the much larger Monster group, with 8*1054 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.

Date: 2010-07-13 03:27 pm (UTC)
sanguinity: woodcut by M.C. Escher, "Snakes" (Default)
From: [personal profile] 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. ;-)

Date: 2010-07-18 06:46 am (UTC)
sqbr: me in a graduation outfit. Trust me, I'm a doctor (of maths) (doctor!)
From: [personal profile] 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 :)

Date: 2010-07-16 02:22 pm (UTC)
fred_mouse: line drawing of sheep coloured in queer flag colours with dream bubble reading 'dreamwidth' (Default)
From: [personal profile] 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!

Date: 2010-08-03 01:56 pm (UTC)
fred_mouse: line drawing of sheep coloured in queer flag colours with dream bubble reading 'dreamwidth' (Default)
From: [personal profile] 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)

Profile

alias_sqbr: the symbol pi on a pretty background (Default)
alias_sqbr

June 2025

S M T W T F S
1234567
8 91011121314
15161718192021
22232425262728
2930     

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 12th, 2025 03:19 pm
Powered by Dreamwidth Studios