Free groups are a wonderful source of examples, counterexamples, and play a crucial role in some pretty slick constructions. For instance, the famous Banach-Tarski paradox utilizes a construction which, at its heart, boils down to a fact about free groups, and that you can find a subgroup of the symmetries of which is isomorphic to a free group.

We’ll begin the process of defining a free group. Let be some set. We define a word on as follows. Concatenate a finite sequence of elements of , formally raised to integral powers. For example if we may form the words , and so on. Note we are really adding in the formal inverse of everything in , which can be neatly encapsulated in the expression . Now we might have the feeling that these objects, namely the words on , could benefit from extra structure. For instance, the expression looks a little clumsy, we would rather see this as . We will say that consecutive powers of the same sign can just be summed together for notational convenience. Furthermore, if we have the construction of a group as our end goal, then we want to collapse to some identity element. To this end we define the empty word, which is denoted , and which has the property that whenever it is concatenated to another word, it leaves that word unchanged.

We may now establish some rules governing equivalence among the words formed from . We allow ourselves to sum the powers of a single generator which appears in two consecutive positions in the string, where for all . We define a word to be freely reduced if it contains no sub strings for any , and observe that every word can be simplified to a freely reduced word by sequentially cancelling substrings of this form. For instance the word reduces to the empty word after we cancel until there are no more strings available. It is a subtle point but the integrity of the group we are forming rests on the fact that every word reduces to a unique word regardless of which order available cancellations are made. Finally, we say two words are equivalent under if they each reduce to the same freely reduced word. We may now take the set of words on and form the equivalence classes , which will be the ground set of our soon to be group.

**Definition: **The free group on some set is the ground set with the operation of concatenation.

The closure and associativity properties of this group can be verified by inspection. The existence and good behavior of our identity elements can also be relatively checked. It is important to note here that the formation of equivalence classes modulo free reduction is absolutely essential for the group structure, since it is what guarantees that there are inverses for every element, following only from the definition that for all . One can compute said inverses by reversing the order of multiplication and negating powers, as is usually done.

Now that we have defined a free group, we should describe the simplest free group that really looks like a free group, namely the free group on the generators , or any other set of cardinality , which is often denoted . The freely reduced words here take the form , where the are integers such that are nonzero, and and may be zero to allow for every possible word shape. We’ll use this group as a running example to explain the definitions and theorems to follow.

The next step in our journey is to characterize the way in which the isomorphism class of a free group depends only on the cardinality of its generating set. We won’t be able to complete this project in this blog post alone, but it begins with the following definition.

**Definition: **A basis for a free group is a set of elements that generate such that no non-trivial word on the basis elements is trivial in .

Let’s unpack the second part of this definition. We will show that the sets and are NOT bases for while the sets and are. Both the non examples illustrate how a non-trivial word on some basis elements can be trivial in . For the first non basis, consider the relabelling , the word is non trivial with respect to this labelling, but when substituting to compute the value in , this word becomes . The second basis has this issue as well as the issue that it doesn’t generate since there is no way to write alone using only these elements.

We will state without proof a fact which will probably come up in later posts.

**Theorem: **Every basis of has elements. More generally, if , then for sets of any cardinality.

Now we can get closer (at least I suspect) to the heart of what a geometric group theorist thinks about when they think about free groups.

**Theorem: **The free group acts freely on some true .

To prove this theorem we take and note that for some basis we have that the underlying graph of is and note that groups act freely on their cayley graphs.

To back up the claim that does indeed have undirected graph , we can note that elements of define paths through the Cayley graph, where reduced elements correspond to reduced paths, and furthermore we have defined to be precisely a graph which is regular and contains no cycles, meaning unique reduced paths between every pair of vertices.

For example, we pose the following outstanding drawing of the Cayley graph of . Note that unlike the graph for , the smaller blue edges do not meet up.

To see this graph in slightly more of its full glory.

With this image you can visualize how the group action of translates the Cayley graph. For instance, multiplication by takes the identity to the vertex at the end of the path specified below, where all the branches of the tree are along for the ride.

This is an opportunity to observe a subtle detail about how this group action works, namely that completing the action by successive actions does NOT drag the identity element along the specified path as one might inspect. Instead, the group action is defined by right multiplication so we can break down the action by as follows:

Here we can track the identity vertex as it gets mapped to the vertex and note that it doesn’t follow the indicated path, instead moving first to , next to and finally to .

If you want to hear some cool facts and constructions that involve free groups ask me after class some time because I have a few tucked away.

When MurphyKate talked about the ‘black magic’ that related the entire shifting of the graph to the action on the graph itself, remembering that the graph itself was infinite really helped me. To elaborate, the fact that the edge lengths were technically not shorter really really helped me.

Also, I’d love to hear any of the cool facts and/or constructions if they can fit inside a comment.

This is a really great post, Horace! I especially appreciated your explanation of how the identity vertex moves when the graph moves. I agree with Akash, that I need to remember that the edge lengths are all the same so that things work out.

Really great post Horace! Quite a pleasure to read. The graphs especially were top notch. One thing I’ve been thinking about is the statement MurphyKate said in class about how Free groups are not isomorphic to Free Abelian groups. It’s interesting to think of the two group categories. It’s cool that they are both possible to represent in different ways and have entirely different properties while also being so important.

Excellent post! Like folks have said, your graphs are wonderful, the color-coding makes it very readable. I agree with your point that it feels like now that we’re past some review and definitions, we’re moving toward the heart of geometric group theory.

I might take you (and MurphyKate) up on some cool free group constructions. This feels like a very powerful tool and I’d love to know more!

Nice write-up Horace!

I remember MurphyKate mentioned in class that free groups have decidable word problem. In other words, there exists an algorithm that, given a string s of generators (and their inverses) of a free group F_n:

1) Always halts, returning “yes” or “no”

2) Returns yes if and only if s is equal to the identity element in F_n.

This is because one can search s for an instance of a generator adjacent to its inverse, remove them, and repeat.

There was some question as to whether the above algorithm could be performed in linear time (in other words, is the number of steps performed by the algorithm upper-bounded by a linear function with respect to the length of s?). I’ve looked into it, and I’m about ~80% sure the following is true:

1) This algorithm cannot be implemented in linear time on a single-tape Turing machine [1]. This is because the tapehead of a Turing machine cannot move from one cell to another without traversing every cell between them.

2) This algorithm can be implemented in linear time using a more sophisticated form of computation, like a random access machine. I don’t really know much about how they work, but I believe random access machines can access a spot in memory in constant time given a pointer. This allows one to construct a linked list representing the letters of a word in the group, which allows for constant-time removal of elements of the list during the process of freely reducing the word. The entire process can be performed with only one traversal of the word.

Notes:

[1] A Turing machine is a model of computation devised by Alan Turing to resolve Hilbert’s Entdeischungsproblem. It consists of an infinitely long piece of tape, along with a “tapehead,” which can read and write symbols on cells of the tape, eventually returning yes or no. Although a Turing machine is very simple, the Church-Turing thesis postulates that any physically realizable algorithm can be implemented by a Turing machine. However, a Turing machine may require longer runtime than other more realistic forms of computation.