Skip to main content

What’s a pregroup?

I’ll just start with a quicky lot of definitions basically copied wholesale out of Rimlinger, then talk about the idea behind them and what they’re useful for, and stuff like that.

Definitions

Start with a pree, which is a set and a partial multiplication table. So we have a set P, DP×P, and m:DP is the partial multiplication. Write down the pree as (P,D), or just P if you’re cool and don’t need the Man’s rules. Note we haven’t yet got any rules about associativity or inverses or what have you.


Now some words and notation: (I’m really not being any more terse than Rimlinger here, if you can believe!)

  1. A P-word X of length n is an element X=(x1,,xn \in P^n$
  2. X is P-reduced if no pair of adjacent elements in X is in D, that is, their multiplication is not defined, so you can’t write X as a shorter word.
  3. (x1,,xn)D : this means that every adjacent pair in the word is in D. Or: 1in1,(xi,xi+1)D.
  4. (w,x,y) associates if (i) (w,x,y) is a P-word, and (ii) (w,x,y)D, (w,xy)D, (wx,y)D.

For any pree (P,D), you can define its universal group U(P) as the group generated by P, with the relations given by the multiplication table D. So, a presentation might look like P{xy=z|x,y,zP,z=m(x,y)}.

OK, so that’s a pree. Now for a pregroup, make a pree that has a unique element 1P, an inverse function i:PP, so i(x)=x1 and which agrees with the following axioms for all w,x,y,zP :

  1. (1,x)D,(x,1)D and 1x=x=x1.
  2. (x1,x)D, (x,x1)D, and xx1=1=x1x.
  3. Suppose (w,x,y)D. Then if (wx,y)D or (w,xy)D, then (w,x,y) associates and (wx,y)=(w,xy).
  4. If (w,x,y,z)D, then one or both of (w,xy)D or (xy,z)D.

The first two axioms are the same as for groups, giving you an identity and inverses. Axiom three says that there is associativity wherever it makes sense. Axiom four is the only one that looks a bit weird, and it ties into the order tree stuff we’ll look at later. Andrew said something about axiom four making word reductions nice, but I can’t remember what it was.

So that’s a pregroup.

Discussion

Really wobbly hand-wavey history

First of all, there are a few different kinds of pregroups. The one to do with grammars is rather popular, but this isn’t it. I’m talking about pregroups as defined by John Stallings, sometimes called S-pregroups by unimaginative people.

Stallings introduced pregroups as a reduced word structure for a group, the idea being that you just write down the bits of a group that don’t act nicely as a partial multiplication table, and then analyse that. His major result was that up to a process called interleaving, all the pregroups representing a particular group have the same form, so the idea was a goer.

His student, Rimlinger, then simultaneously advanced the field enormously and wrote one of the worst maths books ever, “Pregroups and Bass-Serre Theory”. He showed that every pregroup represents the fundamental group of a graph of groups, and vice versa.

The fundamental group of a graph of groups is obtained by starting with a graph, then attaching groups to each edge and vertex, with homomorphisms between each vertex group to the groups of the edges coming out of it. HNN extensions and free products with amalgamation are described nicely by graphs of groups.

I’m interested in pregroups because (i) Andrew is, (ii) by talking about a group as the fundamental group of a graph of groups, and hence a lot of HNN extensions and free products with amalgamation, you can say some thing about how complicated it is for the purposes of computation.

I’ll talk about the technicalities of working with pregroups as presented here in another post, this one has blown my mind.

References

My Mendeley reading list about pregroups.

Pregroups and Bass-Serre Theory, by Frank Rimlinger

Final thoughts

I’m going to abbreviate ‘fundamental group of a graph of groups’ as fgoagog from now on. Seriously. Far too long.