01.02.20 · foundations / groups

Free group, free product, group presentation

shipped3 tiersLean: none

Anchor (Master): Dyck 1882 Math. Ann. 20; Nielsen 1921 Math. Ann. 94; Schreier 1927 Abh. Hamburg 5; Magnus-Karrass-Solitar Combinatorial Group Theory; Serre Trees 1980

Intuition [Beginner]

Imagine you have an alphabet of letters, say and , and you form words by stringing them together: , , , and so on. You can also use inverses and , and you cancel whenever a letter meets its inverse. With no further rules, this system of words is a free group. The word "free" means free of any extra relations beyond the minimum needed to have a group.

A group presentation adds rules. You start with a free group, then declare certain words equal to the identity. Requiring and adds constraints that reduce the set of distinct words. The presentation produces a group with exactly elements, the symmetries of a triangle.

Why does this concept exist? Free groups and presentations give a universal way to describe any group: every group is a quotient of a free group, so presentations encode group structure as generators plus relations.

Visual [Beginner]

The diagram shows the Cayley graph of the free group on two generators and . Each vertex is a group element (a reduced word), and edges labeled and connect each word to its extensions. The graph is an infinite tree with four branches at every vertex — no cycles, because there are no relations to create loops.

Cayley graph of the free group F2 as an infinite 4-regular tree

Adding a relation like would collapse pairs of vertices and introduce cycles, breaking the tree structure.

Worked example [Beginner]

Consider the dihedral group (symmetries of an equilateral triangle) given by the presentation .

Step 1. The generators are (rotation by degrees) and (a reflection). The relations and bound the powers of each generator. The third relation lets us move past at the cost of inverting : applying it gives and .

Step 2. Every word in and reduces to the form or for , using to eliminate adjacent reflections and to push all reflections to the left.

Step 3. The six distinct elements are , , , , , . Any other word collapses into one of these by the reduction rules.

What this tells us: two generators and three relations capture all six symmetries of the triangle. The presentation is a compact encoding of the entire group.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Definition (Free group, universal property). Let be a set. The free group on is a group equipped with a map satisfying the following universal property: for every group and every set map , there exists a unique group homomorphism such that .

The free group admits a concrete construction. Let be a disjoint copy of . A word in is a finite sequence with each . A word is reduced if no adjacent pair has the form or . Every word reduces to a unique reduced word by iteratively deleting cancelling pairs. The elements of are reduced words, with multiplication given by concatenation followed by reduction to canonical form [Dummit-Foote §6.3].

When , write and call the rank. The group is the identity group; .

Definition (Group presentation). A group presentation specifies a set of generators and a set of words in called relators. The group it defines is the quotient , where is the smallest normal subgroup of containing .

Definition (Free product). Let and be groups. The free product is the group satisfying the universal property: for every group and every pair of homomorphisms and , there exists a unique homomorphism extending both. Concretely, elements of are reduced words with alternating factors from and , multiplied by concatenation and cancellation.

Counterexamples to common slips [Intermediate+]

  • Free group vs. free abelian group. The free group is not abelian when . The free abelian group on is the quotient , which imposes commutativity that does not have.
  • Presentations can be deceptive. The presentations and define groups of different orders (infinite vs. ), but it is undecidable in general whether two presentations define isomorphic groups (Novikov 1955, Boone 1958).
  • Subgroup rank can exceed the ambient rank. Every subgroup of a free group is free (Nielsen-Schreier), but a subgroup of can have rank larger than . A subgroup of index in is free of rank .

Key theorem with proof [Intermediate+]

Theorem (Existence of presentations). Every group is isomorphic to a quotient of a free group. Equivalently, every group admits a presentation.

Proof. Let be any generating set for (for instance, ). The set inclusion extends by the universal property to a unique homomorphism .

The map is surjective. Every element is a product with and , since generates . The corresponding word in maps to under .

By the first isomorphism theorem, . Setting , which is normal in , the quotient is isomorphic to .

A presentation for is where is any set of words whose normal closure equals . A word belongs to if and only if the corresponding product in equals the identity.

Bridge. This theorem is the foundational reason that group presentations are universal: this is exactly the statement that any group can be described by generators and relations. The central insight is that the kernel of the canonical surjection captures all internal constraints of the group as relators, and this identifies the study of arbitrary groups with the study of quotients of free groups. The bridge is between combinatorial data (a list of generators and relators) and algebraic structure (the group up to isomorphism). This result builds toward 01.02.02 where the isomorphism theorems supply the quotient machinery, and appears again in 01.02.19 where the tensor algebra satisfies an analogous universal property for modules over a ring, with the free group construction as the prototypical free-forgetful adjunction.

Exercises [Intermediate+]

Advanced results [Master]

Theorem 1 (Nielsen-Schreier). Every subgroup of a free group is free. If has index , then where (the Schreier index formula) [Schreier 1927]. The formula shows that a subgroup of finite index in has strictly larger rank whenever and .

Theorem 2 (Normal form for free products). Let be the free product. Every element has a unique expression as or with , , and ; or as the identity. This normal form theorem implies is infinite whenever both and are non-identity groups.

Theorem 3 (Grushko-Neumann). The rank of the free product satisfies when both groups are free. This means free product is additive on rank, analogous to dimension additivity for direct sums of vector spaces.

Theorem 4 (Kurosh subgroup theorem). Every subgroup of a free product is itself a free product of a free group with conjugates of subgroups of the factors . This generalises Nielsen-Schreier: when each , the free product is a free group, and the theorem recovers the statement that subgroups of free groups are free [Magnus-Karrass-Solitar].

Theorem 5 (Tietze transformations). Two finite presentations define isomorphic groups if and only if one can be obtained from the other by a finite sequence of Tietze transformations: adding a redundant relator, removing a relator that follows from others, adding a new generator together with a relation defining it, or removing a generator that can be expressed in terms of the others. Tietze transformations give a computational method for manipulating presentations [Lyndon-Schupp].

Theorem 6 (Word problem, undecidability). There exists a finitely presented group for which the word problem is undecidable: no algorithm can determine, given an arbitrary word in the generators, whether equals the identity in the group (Novikov 1955 Doklady Akad. Nauk SSSR 107; Boone 1958 Ann. Math. 68). The uniform word problem — deciding, given an arbitrary presentation and a word, whether the word is the identity — is also undecidable.

Theorem 7 (Free product with amalgamation). Let and be groups with a common subgroup and via embeddings and . The free product with amalgamation is the quotient where is the normal closure of . The universal property: a homomorphism from to is a pair of homomorphisms and that agree on .

Theorem 8 (Bass-Serre theory, statement). A group acts without inversions on a tree without edge inversions if and only if is either a free group (when acts freely) or a free product with amalgamation or HNN extension (when the action has edge stabilisers). The fundamental group of a graph of groups decomposes as an iterated free product with amalgamation. Conversely, every such decomposition determines a tree on which acts, the Bass-Serre tree [Serre 1980].

Synthesis. The free group is the foundational reason that combinatorial group theory exists as a coherent subject: this is exactly the universal construction encoding all groups as quotients of letter-strings modulo relators. The central insight is that the Nielsen-Schreier theorem identifies subgroups of free groups with free groups of computable rank, and this is dual to the Kurosh theorem which describes subgroups of free products. Putting these together with the Grushko-Neumann rank formula, the rank of a free group becomes a well-defined invariant analogous to dimension for vector spaces. The bridge is between combinatorial presentations and geometric group actions on trees via Bass-Serre theory, and the pattern generalises to free products with amalgamation and HNN extensions as the fundamental building blocks in the decomposition of groups.

Full proof set [Master]

Proposition 1 (Free groups are torsion-free, detailed). Let be a non-identity reduced word. Then for all positive integers .

Proof. Write in reduced form with . Define the cyclic reductions of : iteratively remove matching first and last letters until either the word is empty or the first and last letters do not cancel. Call the result , the cyclically reduced form of .

If , then for some , but is reduced, so , meaning unless . Since , we have .

Write for some word (this is the reduction process). Then . Since is cyclically reduced, is reduced for all (no cancellation occurs between consecutive copies of ). Therefore , where is non-empty. The concatenation reduces at most letters from each end, but has letters, so the result is non-empty for all .

Proposition 2 (Schreier index formula). Let be the free group of rank and a subgroup of finite index . Then is free of rank .

Proof (sketch). Choose a Schreier transversal for in : a set of right coset representatives such that every initial segment of a representative is again a representative. For each and each generator , define , where denotes the unique representative of . The element lies in .

The Schreier generators form a free generating set for . To count them, observe: there are pairs with and . Among these, exactly give (one for each non-identity coset, since for the representative of the identity coset, for all ). The number of non-identity Schreier generators is , giving rank .

Connections [Master]

  • Group 01.02.01. The free group on a set is the most general group that can be built from : it adds no relations beyond those forced by the group axioms. The foundational reason this matters is that every group arises as a quotient of a free group, making free groups the universal building blocks in the category of groups. The bridge is between the categorical universal property of free objects and the concrete word-reduction construction that makes the free group computable.

  • Subgroup, coset, quotient group, isomorphism theorems 01.02.02. The isomorphism theorems underpin the theory of group presentations: the first isomorphism theorem produces the presentation , and the correspondence between subgroups of and subgroups of containing relies on the lattice isomorphism theorem. Normal subgroups of free groups correspond to relator sets, and the quotient construction from that unit appears again here as the mechanism converting a free group and a normal subgroup into an arbitrary group.

  • Tensor algebra, exterior algebra, symmetric algebra 01.02.19. The free group and the tensor algebra satisfy formally analogous universal properties: both are free objects in their respective categories (groups and associative algebras), both are constructed as quotients of word monoids, and both serve as the starting point for further quotient constructions (group presentations for the free group, exterior and symmetric algebras for the tensor algebra). The free functor from sets to groups is the group-theoretic parallel of the tensor algebra functor from modules to algebras.

Historical & philosophical context [Master]

Walther von Dyck 1882 introduced group presentations in Gruppentheoretische Studien (Math. Ann. 20), establishing that a group can be specified by generators and defining relations [Dyck 1882]. Dyck's work made precise the informal practice, going back to Cayley, of describing groups by symbols and rules.

Jakob Nielsen 1921 developed the theory of free groups in Die Isomorphismen der allgemeinen unendlichen Gruppe mit zwei Erzeugenden (Math. Ann. 94), proving that the automorphism group of is generated by Nielsen transformations (analogues of elementary row operations) and that rank is an invariant of free groups [Nielsen 1921].

Otto Schreier 1927 proved the subgroup theorem in Die Untergruppen der freien Gruppen (Abh. Hamburg 5), showing that every subgroup of a free group is free and deriving the index-rank formula [Schreier 1927]. The modern geometric viewpoint — free groups as fundamental groups of graphs, and Bass-Serre theory as the study of groups acting on trees — crystallised with Serre's Arbres, amalgames, SL2 (1977, English translation Trees 1980), which unified the algebraic theory of free products with amalgamation with the topological theory of covering spaces and group actions.

Bibliography [Master]

@article{Dyck1882,
  author = {Dyck, Walther von},
  title = {Gruppentheoretische Studien},
  journal = {Mathematische Annalen},
  volume = {20},
  year = {1882},
  pages = {1--44},
}

@article{Nielsen1921,
  author = {Nielsen, Jakob},
  title = {Die Isomorphismen der allgemeinen unendlichen Gruppe mit zwei Erzeugenden},
  journal = {Mathematische Annalen},
  volume = {94},
  year = {1921},
  pages = {249--272},
}

@article{Schreier1927,
  author = {Schreier, Otto},
  title = {Die Untergruppen der freien Gruppen},
  journal = {Abhandlungen aus dem Mathematischen Seminar der Universit\"at Hamburg},
  volume = {5},
  year = {1927},
  pages = {161--183},
}

@article{Novikov1955,
  author = {Novikov, Petr S.},
  title = {Ob algoritmi\v{c}esko\u{i} nerazre\v{s}imosti problemy to\v{z}destva slov v teorii grupp},
  journal = {Doklady Akademii Nauk SSSR},
  volume = {107},
  year = {1955},
  pages = {954--956},
}

@article{Boone1958,
  author = {Boone, William W.},
  title = {The word problem},
  journal = {Annals of Mathematics},
  volume = {68},
  year = {1958},
  pages = {794--812},
}

@book{MagnusKarrassSolitar,
  author = {Magnus, Wilhelm and Karrass, Abraham and Solitar, Donald},
  title = {Combinatorial Group Theory},
  publisher = {Dover Publications},
  year = {2004},
  note = {Reprint of the 1976 Interscience edition},
}

@book{SerreTrees,
  author = {Serre, Jean-Pierre},
  title = {Trees},
  publisher = {Springer-Verlag},
  year = {1980},
}

@book{LyndonSchupp,
  author = {Lyndon, Roger C. and Schupp, Paul E.},
  title = {Combinatorial Group Theory},
  publisher = {Springer-Verlag},
  year = {1977},
}

@book{DummitFooteGroups,
  author = {Dummit, David S. and Foote, Richard M.},
  title = {Abstract Algebra},
  publisher = {John Wiley \& Sons},
  year = {2004},
  edition = {3rd},
}