You're reading: Posts Tagged: group theory

“Pariah Moonshine” Part I: The Happy Family and the Pariah Groups

Being a mathematician, I often get asked if I’m good at calculating tips. I’m not. In fact, mathematicians study lots of other things besides numbers. As most people know, if they stop to think about it, one of the other things mathematicians study is shapes. Some of us are especially interested in the symmetries of those shapes, and a few of us are interested in both numbers and symmetries.

HLF Blogs: Efim Zelmanov’s Desert Island Maths

In September, Katie and Paul spent a week blogging from the Heidelberg Laureate Forum – a week-long maths conference where current young researchers in maths and computer science can meet and hear talks by top-level prize-winning researchers. For more information about the HLF, visit the Heidelberg Laureate Forum website.

At the start of his HLF lecture on Asymptotic Group Theory on Thursday morning, Fields medalist Efim Zelmanov described the ‘group’ as: “the great unifying concept in mathematics,” remarking “if you go for a trip, and you are allowed to take only two or three mathematical concepts with you, give serious consideration to this one.” Very loosely defined, a group is a set of things (its ‘elements’) that you can ‘multiply’ together, with this multiplication behaving in certain helpful ways. Think of numbers being added, functions composed together or rotations and reflections of a shape being carried out one after the other. I doubt any mathematician would accuse Zelmanov of overstating their importance in mathematics.

In his talk he discussed residually finite groups. These are groups which are infinite in size but still just a little bit finite-y. In technical terms, the group has a set of homomorphisms with finite kernels having trivial intersection. Although the group is too large to see all at once, as Zelmanov put it, we have “photos from all sides of the group”. He contrasted this to “hopelessly infinite groups”, for which no such photo album is possible.

A common way to look at a group is to find a set of ‘generators’: these are elements of the group which you can multiply together to create any element of a group (the elements ‘generate’ the entire group). Some infinite groups can’t be generated from a finite set — consider trying to find a set of rational numbers that you can multiply together to create any rational number. Those that can be generated from a finite set are unexcitingly called ‘finitely generated’. Of course, finite groups are also finitely generated.

Zelmanov considered under what circumstances finitely generated groups can be proved to be finite. One immediate way this won’t happen is if one of the generators is not periodic: if you keep multiplying it by itself you keep getting new elements forever, never ‘looping back’ to the original generator. (Imagine starting with 1 and continually adding 1…) The Burnside problem asks whether there are any other ways to make a finitely-generated, yet infinite, group. In 1991, Zelmanov proved that for residually finite groups, there aren’t. However, this isn’t the case for the ‘hopelessly infinite’ groups.

In his lecture Zelmanov, accompanied by his excellent hand-drawn slides, discussed this before moving on to related topics such as the growth of groups (if you start with a generating set, and create new elements by multiplying them together, how quickly does the set grow?) and ‘approximate groups’ (which, as the name suggests, are things that are like, but not quite, groups).

Christmas Symme-tree

Christmas wrapping paper is sold in thousands of different variations, including plain, coloured, patterned, foiled and even flock, but one thing it’ll have in common is that it will repeat whatever pattern it has, regularly across the design.

I’m interested in symmetry, and was intrigued to find a curious fact about the symmetries of such repeating patterns – their symmetries are quite limited.

László Babai reckons he can decide if two graphs are isomorphic in quasipolynomial time

László Babai in Chicago. Photo by Gabe Gaster, used with permission.

We’ve been slow to cover this, but if this week has taught us anything, it’s that taking your time over Important Maths News is always a good idea.

A couple of weeks ago, rumours started circulating around the cooler parts of the internet that László “Laci” Babai had come up with an algorithm to decide if two graphs are isomorphic in quasipolynomial time. A trio of mathematicians including Tim Gowers were on BBC Radio 4’s In Our Time discussing P vs NP while these rumours were circulating and made a big impression on Melvyn Bragg as they talked so excitedly about the prospect of something big being announced.

If Babai had done what the rumours were saying, this would be a huge advance – graph isomorphism is known to be an NP problem, so each step closer to a polynomial-time algorithm raises the P=NP excite-o-meter another notch.