Tag Archives: random group

## Introduction to random groups

26 Apr Last summer, I participated in an awesome research program which ended up with a good handful of original research projects all having to do with random groups.  Random group theory is rather modern- the first definition of a random group came about in the 1980s (just like me!)  It’s a very rich field with lots and lots of open problems, since you can dive into most properties of groups and ask if they apply to random groups. [Here’s the post defining groups if you forgot.]

Some brief motivation: sometimes you want to say things about a “typical” group.  Like, if you picked a group at random out of all possible groups, it very likely has property A.  Example: if you pick an alumna from Mount Holyoke at random, she very likely is/was a woman.  If you ask me to name a random private college in the United States, I will very likely say “Mount Holyoke”.  Instead of having to say “very likely” all the time, we say “random groups have property P” if the probability that they have property P approaches 1 (this will be more precise below).

So, to build our intuition in the example above: if I pick one person who’s graduated from Mt. Holyoke, maybe he’s transgender and is not a woman.  But if I pick, say, 1000 alums, chances are that fewer than 10 identify as men (I do not know any research on incidence of trans but I think 10 is a safe bet here).  And if I pick 10000, probably there’s very very few [also maybe there aren’t this many alums in all time?].  So I’ll say a random alum is a woman, even if there are a few edge cases. Probability of being a man in first 5: 20%
in first 25: 8%
in first 100: 3%
in first 1000: 0.3%

Of course, the massive issue with this example is that the number of Mt. Holyoke alums is finite, and the probability of being a woman is a fixed number between 0 and 100%.  Hopefully this example illustrated the idea though- we want to look at the probability of having property A as the number of cases goes to infinity.

Let’s add some more precision to this idea.  First, we need a good way to describe groups- I (secretly) claimed that there are infinitely many, but how do we know that?  Well, we’ve already seen the group of integers, $latex \mathbb{Z}$.  And you can also have ordered pairs or triples of integers, $\mathbb{Z}^2, \mathbb{Z}^3$.  So there’s already infinitely many groups:n-tuples of integers, a.k.a. $\mathbb{Z}^n$.  But not all groups are copies of the integers (and I didn’t prove that these all aren’t the same group, but I’ll let you convince yourself of that)- for instance, we’ve thought about homeomorphisms of the torus.  We’re going to use group presentations to describe our groups- every element will be written as a word in the alphabet of generators.  So we’ll use letters like a,b,c… to represent generators, and we’ll put them together like aba, aa, babb as words to represent group elements.  Let’s do an example that we’ve seen before.

In the group of symmetries of a square, we have two generators, which we named (for the clockwise rotation by 90 degrees) and (for flipping over the horizontal axis).  And we wrote all of our group elements as words in the letters and s, above.  One presentation for this group is $\langle r, s | \ r^4=s^2=1, sr^2=r^2s \rangle$.

So for a group presentation we have < letters of the generating alphabet | relations >.  A relation is an equation in the letters which is true in the group.  And if you list enough relations, you’ll be able to characterize a finitely presented group.  There are some groups which can’t ever be finitely presented: no matter how many relations you write down, there’ll still be more relations which aren’t derived from the ones you wrote down.  Wikipedia has a good list of examples of group presentations.  Also, there are groups which aren’t even finitely generated: that means the generating alphabet is infinite.  If you aren’t finitely generated, you’re definitely not finitely presented.

So when we talk about random groups, we’re *only* going to talk about finitely presented groups.  This is just something that happens when you try to make things precise: you might cut out other cases that you wanted to talk about.  Anyways.

In the few-relators model of random groups, we fix a number K ahead of time, like K=4.  And we fix the size of our alphabet ahead of time too, like m=2.  So we’re looking at two-generator groups with four relations.  Our relations will be in the form word=1.  Pick a length for the words, so the word abbab has length 5, and so does the word $latex b^{-1}a^{-1}b^2a$.  Out of all possible words of length l, choose four at random: in our example, we have 324 possible words of length 5 in the letters a,b and their inverses.  [Note that the word $aa^{-1}b = b$, so it has length 1, not 3.]  We say a random group has property P in the few-relators model if the probability that a group with m generators and relators has property P goes to 1 as approaches infinity- so as the length of the relators goes to infinity.

How’d I get 324 in the previous paragraph?  Well, we have four choices for the first letter: a, b, $a^{-1},b^{-1}$.  The second letter only has three options: it can’t be the inverse of the first letter.  And the third letter can’t be the inverse of the second, so it also has three options.  Same deal for the fourth and fifth letters.  So I have 4*3*3*3*3 options, which is 324.  Instead of picking exactly five of those as relations, I could pick some proportion of them.  This is called the density model of random groups: instead of fixing K as the number of relations ahead of time, we fix d, a number between 0 and 1.  Then we say a random group has property P in the density model if the probability that a group with generators and $latex 2m(2m-1)^{dl}$ relators has property P goes to 1 as approaches infinity.

The density model is pretty common, and when people talk about random groups they often mean the density model.

Here’s a cartoon I drew because there aren’t enough pictures in this post: