When is a group not a group?

Open any algebra textbook, and you will be told that a group consists of a set of elements with a binary function defined on it and satisfying a few axioms. But if you assume that is always the case, you may occasionally be in for a surprise.

A lot of my recent work involves graphs defined on groups. The vertex set of one of these graphs is typically the set of elements of a group, and the edges (or arcs, in a directed graph) reflect some property of the group.

Recently I was struck by a conjecture in a preprint by some of my coauthors, and decided to write a program to test it. My engine of choice for building examples and testing conjectures is the algebraic computing system GAP, which has a package GRAPE for constructing and studying graphs.

The particular digraphs I was interested in required computing the set of elements of the group G (a single GAP command does this, presumably just forgetting the group operation) and the endomorphisms of G (not quite built in but a short program finds these). Then we construct the arcs of the graph by applying endomorphisms to group elements. So I wrote a program to do all this, and tried it out on a couple of specific groups (including the symmetric group on 3 letters); it worked fine.

So I decided to test all groups of a given order.

Now GAP has an extensive SmallGroups library, so I read in the groups of order n one at a time and fed them to the program. It had no trouble with finding the set of elements of each group, and finding all its endomorphisms; but when I tried applying an endomorphism to a group element, it said “I can’t do that”.

On investigation, it appeared that what is stored in the SmallGroups library are not groups, but recipes for constructing groups. These recipes allow you to find the element sets, and the endomorphisms, but not to apply endomorphisms to elements!

I am not quite sure what the recipe entails, but it includes generators for the group, which are given abstract names f1, f2, etc. When it computes the endomorphisms, it finds what they do to the generators, but is unable to extend their action to arbitrary elements of the group. I don’t know whether this is a bug or a feature.

But I am happy to say that I found a fix, courtesy of the nineteenth-century mathematician Cayley. He tells us that any group (even one defined by an unknown recipe) is isomorphic to a group of permutations. Moreover, GAP gives a simple way to write down this group of permutations. One extra line of code is all that is required. Having done this, all worked fine.

The program ran. It found counterexamples to the conjecture; but, more than that, it suggested where to look to find a doubly infinite family of counterexamples.