Small Cancellation Theory: A Preview
2022-04-24
Introduction
Max Dehn was a German mathematician of Jewish origin who made significant contributions in group theory and topology in the early 1900s. He was the first person to resolve one of Hilbert's problems. After emigrating to the United States, he taught college math courses that connected math with philosophy, linguistics, art, and nature and that he often held in the outdoors. That is the way that math should be taught.
In the 1910s, Dehn posed two problems which would lead to several breakthroughs in group theory.
- Word problem: Given two elements in a group, do the two represent the same element?
- Conjugacy problem: Given two elements in a group, are the two conjugate?
Informally, small cancellation theory is concerned with groups whose relators have small overlaps. The study of small cancellation theory gives insight into the solvability of the word and conjugacy problems for groups meeting sufficiently strong conditions. The study of these conditions is often done geometrically in the Euclidean plane \(\mathbb{E}^2\), allowing us to visually understand the problems.
In order to begin understanding small cancellation theory, we first need to visit a few (informal and formal) definitions.
Preliminaries
A subset of a group is a generating set for that group if every group element can be expressed as a product of elements in the subset. In terms of linear algebra, we can think of a generating set as a set of basis vectors.
Continuing from generating sets, we reach free groups. We can think of a free group with respect to a set \(X\) as the group of all elements that can be built from elements of \(X\).
Free groups lead us to the concept of words. A word in a set \(X\) is a finite sequence of elements in \(X \cup X^{-1}\). Some finite subsequences in a word can be made of consecutive elements which are inverses of each other. The replacement of two such "bad" elements with the identity is called a reduction. Further, a word is freely reduced if no such reductions are possible [3].
Definitions
So far, we have revisited terms from abstract algebra and group theory. Now, we turn to terms from small cancellation theory proper that require formal definitions. The definitions follow Lyndon and Schupp [1].
Definition 1 (region).
A region is a bounded set which is homeomorphic to the unit disk. That is, a set \(R\) is said to be a region if and only if \(R\) is bounded and there exists some function \(\phi:R \xrightarrow{}\mathscr{U}\), where \(\mathscr{U}\) is the unit disk, such that \(\phi\) is bijective and both \(\phi\) and \(\phi^{-1}\) are continuous.
Definition 2 (map).
A map \(M\) is a finite collection of pairwise disjoint vertices, regions, and edges which satisfy the following conditions:
The first condition effectively means that an edge in a map must have two (not necessarily distinct) endpoints. The second condition means that the boundary of any region in a map can be represented as a set of edges and their endpoints.
Definition 3 (diagram).
A diagram \(D\) over some group \(G\) is an oriented map \(M\) and a function \(\phi\) such that for every edge \(e\in M\), \(\phi\) assigns some \(\phi(e) \in G\) as a label for \(e\). In particular, if \(e\) is an oriented edge of of \(M\) and \(e^{-1}\) is oppositely oriented, then \(\phi(e^{-1})=\phi(e)^{-1}\).
Definition 4 (symmetrized).
A subset \(R\) of a free group \(F\) is symmetrized if, for all \(r \in R\),
Definition 5 (piece).
For a symmetrized set \(R\), \(b\) is a piece relative to \(R\) if some distinct elements \(r, s \in R\) are multiples of \(b\).
A piece in a group is basically a path contained in the boundary of two different regions in the group.
There are many more interesting geometric notions in small cancellation theory, such as spurs, ladders, and wheels.
Cancellation Conditions
The crux of small cancellation theory lies in the cancellation conditions. When these conditions are met with respect to particular constants, we can use methods such as Dehn's algorithm to solve the word and conjugacy problems. The cancellation conditions have to do with the relative sizes of the regions known as pieces.
There are three such cancellation conditions. A group with presentation \(\langle X \mid R\rangle\) meeting the following conditions for certain values of \(\lambda \in \mathbb{R}, p \in \mathbb{N},\) and \(q \in \mathbb{N}\) has a solvable word problem.
Condition \(C'(\lambda)\).
There is some relator \(r\in R\) so that whenever \(b\) is a piece relative to \(R\), \(r \equiv bc\) implies \(|b|< \lambda |r|\).
Condition \(C(p)\).
No relator \(r \in R\) can be expressed as a reduced product of fewer than \(p\) pieces.
Condition \(T(q)\).
Fixing \(h, q\) so that \(3 \leq h < q\) and letting \(r_1,...,r_h \in R\) so that \(r_i^{-1} \neq r_{i+1}\) for any \(i = 1,...,h\), at least one of the successive products formed by the sequence \(r_1r_2,r_2r_3,...,r_{h-1}r_h,r_hr_1\) is freely reduced.
Note that if a group satisfies the \(C'(\lambda)\) condition, then it will also satisfy the \(C(p)\) condition as song as \(\lambda \leq \frac{1}{p-1}\).
Intuitively, a group satisfies the cancellation conditions when pieces in the relators are relatively "small" [1]. A simple example of a group satisfying certain values for the cancellation conditions is the surface group with presentation $$G=\langle a,b,c,d \mid aba^{-1}b^{-1}cdc^{-1}d^{-1}\rangle$$ Recall that in order to satisfy condition \(C(p)\), a relator cannot be expressible by fewer than \(p\) pieces. For $G$, the pieces of any relator are all words of length 1. Thus, any relator is expressible by 8 pieces. Therefore, this group will satisfy \(C(p\leq 8)\).
Dehn's Algorithm
Dehn gave a recursive solution to the word problem for certain groups associated with 2-manifolds. His resulting algorithm can determine whether a word in a group represents the identity, for a group whose set of relators satisfies some of the conditions \(C'(\frac{1}{6})\), \(C(\frac{1}{4})\), or \(T(4)\). The following overview is modified from Lyndon and Schupp [1].
Consider a word \(w\) on a group \(G = \langle X \mid R \rangle\), where \(R\) is symmetrized. The algorithm is recursive: at each stage, \(w\) is reduced by a subword satisfying certain factorization and length conditions on \(R\). The strategy lies in finding words of length no more than \(2\lvert w \rvert\); if \(w\) is the identity, then there are only finitely many such words. If a finite number of such reductions does not lead to the identity, the algorithm has proven that \(w\) is not the identity in \(G\).
Applications
Small cancellation theory sits at an interesting intersection of algebra and geometry. It is closely connected with computational algebra, and combinatorics. GAP provides a programming language and library of algebraic algorithms, which can be used to implement methods to study Dehn functions, hyperbolicity of groups, and more using small cancellation theory.
References
- Lyndon, Roger C., and Paul E. Schupp. Combinatorial Group Theory. Berlin: Springer, 2001.
- Mccammond, Jonathan P., and Daniel T. Wise. ”Fans and Ladders in Small Cancellation Theory.” Proceedings of the London Mathematical Society 84, no. 3 (2002): 599-644. doi:10.1112/s0024611502013424.
- Meier, John. Groups, Graphs and Trees: An Introduction to the Geometry of Infinite Groups. Cambridge, U.K.: Cambridge University Press, 2008.