# How many small cancellation groups are there?

It is known that there are uncountably many groups with two generators. But what about the restriction to small cancellation groups?

Are there countably or uncountably many small cancellation groups?

-
What's a small cancellation group? – Rasmus Aug 9 '12 at 9:38
@Rasmus: A group admitting a presentation whose relations can only cancel in a controlled manner (that is to say: the relations don't overlap too much). Small cancellation theory is a very well-developed part of combinatorial and geometric group theory, for example there's Dehn's algorithm to solve the word-problem, they are an important sources for examples of Gromov hyperbolic groups, etc. – t.b. Aug 9 '12 at 10:12
Of course, there are only countably many finitely presented groups, though... – user641 Aug 9 '12 at 10:16
@SteveD: Can all small cancellation groups necessarily be made finitely presented though? They aren't all hyperbolic (for example $C(4)-T(4)$ and $C(3)-T(6)$ are both flat), so finitely presented isn't a given... – user1729 Aug 9 '12 at 10:37
@SteveD: Lyndon and Schupp talks about "recursive" presentations in their book (every theorem is about a recursively presented group with $C^{\prime}(1/6)$ or whatever). I haven't looked why in detail, and is perhaps just because the small cancellation presentation might not be finite. – user1729 Aug 9 '12 at 17:00

Your question can be solved without appealing to any fancy result. But it is ambiguous, so I give 2 answers:

if you define "small cancelation" as finitely presented, then there are countably many such groups, just because you have countably many group presentations. (And there are infinitely many small cancelation groups on 2 generators and 1 relator, see Lyndon-Schupp)

if you allow infinite presentations, then start from a single small cancelation infinite presentation $\langle x,y|(R_n)\rangle$. For any subset $I$ of the integers, you get a group $G_I=\langle x,y|(R_n)_{i\in I}\rangle$. Thus get continuum many small cancelation presentations.

Actually it also gives countinuum many non-isomorphic groups: the argument is as follows: because of small cancelation, the $G_I$ are pairwise non-isomorphic as marked groups (a marked isomorphism is by definition required to map $(x,y)$ to $(x,y)$). And a given f.g. group has at most countably many pairs of generators. So the equivalence relation "being isomorphic" among the $G_I$ has at most countable classes, and thus they include continuum many non-isomorphic groups.

-
Nice answer, thank you! – Seirios Aug 21 '12 at 9:59
To obtain $G_I$, you extract a sequence of relations from $\langle x,y | (R_n)_{n \in \mathbb{N}} \rangle$, that is $G_I= \langle x,y | (R_n)_{n \in I} \rangle$ if $I \subset \mathbb{N}$. – Seirios Aug 22 '12 at 14:45
For $i \geq 1$, let $w_i$ denote the word $ab^{2^{i-1}}ab^{2^{i-1}+1}...ab^{2^i}$. For all $i,j \geq 1$, $w_i$ and $w_j^{-1}$ don't have any commun subword; the largest commun piece between two cyclic permutations of $w_i$ is $b^{2^i-2}ab^{2^i-1}$; the largest commun piece between two cyclic permutations of $w_i$ and $w_j$ ($j >i$) is also $b^{2^i-1}ab^{2^i-1}$. On the other hand, $\ell g(w_i)= (2^{i-1}+1)(1+3.2^{i-1})$. So the family $\{w_i,i \geq 3\}$ satisfies the condition $C'(1/6)$. – Seirios Aug 22 '12 at 15:43
For example, math.utah.edu/~bestvina/eprints/questions-updated.pdf mentions a 2-generator infinitely presented $C'(1/6)$ small cancellation group. So in your result, $C'(1/6)$ small cancellation groups are supposed finitely presented. – Seirios Aug 23 '12 at 11:27

There is a famous result of Ol'shanskii which says that "almost all" finitely presented groups are small cancellation (indeed, are $C^{\prime}(1/6)$). However, I cannot access the paper I believe this result is in ("Almost every group is hyperbolic", Internat. J. Algebra Comput. $\mathbf{2}$ (1992), 1-17).

Instead, I will mention a paper I have on the desk in front of me. It is a paper of Ilya Kapovich and Paul Schupp, entitled "Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups". Before mentioning their result, I should give the notion of genericity that they use:

Let $N(m, n, t)$ be the number of all possible presentations of the form $\langle a_1, \ldots, a_n; r_1, \ldots, r_n\rangle$ where the $r_i$ are cyclically reduced non-trivial words from $F(a_1, \ldots, a_n)$ and where $|r_i|\leq t$ for $i=1, \ldots, n$. Let $N_p(m, n, t)$ be the number of presentations which these restrictions which define a group with property $P$. Then the property $P$ is $(m, n)$-generic if $$\displaystyle\lim_{t\rightarrow\infty}\frac{N_P(m, n, t)}{N(m, n, t)}=1.$$ If, moreoever, there is $0\leq c-c(m, n)<1$ such that for all sufficiently large $t$ we have $$1-\frac{N_P(m, n, t)}{N(m, n, t)}\leq c^t$$ we say that $P$ is exponentially $(m, n)$-generic.

Their main theorem is as follows,

Theorem: Let $m>1$ and $n>0$ be integers. There exists an exponentially (m, n)-generic class $P_{m, n}$ of $m$-generator $n$-relator presentations $$\langle a_1, \ldots, a_m; r_1, \ldots, r_n$$ with the following properties:

• Every group defined by a presentation from $P_{m, n}$ is torsion-free, one-ended and word-hyperbolic (They actually prove $C^{\prime}(1/6)$). Moreover, every subgroup of $G$ generated by at most $m-1$ elements is free.

• There is an algorithm which, given an arbitrary $m$-tuple of cyclically reduced words $r_1, \ldots, r_n \in F(a_1, \ldots, a_m)$, decides in at most exponential time (in the sum of the lengths of $r_i$) whether or not a presentation $\langle a_1, \ldots, a_n; r_1, \ldots, r_n\rangle$ belongs to $P_{m, n}$.

• For any presentation $\langle a_1, \ldots, a_n; r_1, \ldots, r_n\rangle$from $P_{m, n}$, for the group $G=\langle a_1, \ldots, a_n; r_1, \ldots, r_n\rangle$ any $m$-tuple, generating a non-free subgroup of $G$, is Nielsen-equivalent in $G$ to the $m$-tuple $(a_1, \ldots, a_m)$.

Their title talks about the isomorphism problem for one-relator groups because if you have a class of a one-relator presentations, $S=\{\langle x_1, \ldots, x_n; R\rangle\}$, and every presentation from $S$ has a single Nielsen equivalence class then two presentations $\langle a_1, \ldots, a_p; R_2\rangle$ and $a_1, \ldots, a_q; R_2\rangle$ are isomorphic if and only if $p=q$ and there exists a Nielsen transformation of the $a_i$, $\phi$ say, which maps $R_1$ to $R_2$: $R_1(a_1\phi)=R_2$. You can look up the paper for the definition of Nielsen equivalence class though! I think I have typed enough now...

EDIT: Primer on small cancellation. (This was originally a comment, but it got a bit long...)

A small cancellation group is a group given in terms of generators and relators such that only a small amount of cancellation happens between the relators (so really we should talk about small cancellation presentations). If $R=\langle X; \mathbf{r}\rangle$ then let $\mathbf{r}^{\ast}$ consist of the set of all cyclic shifts and inverses and inverses of all cyclic shifts (etc!) of elements from $\mathbf{r}$. Note that if $\mathbf{r}$ is finite then so is $\mathbf{r}^{\ast}$. Then, if $R$ and $S$ are in $\mathbf{r}^{\ast}$ such that $R=\hat{R}p$ and $S=\hat{S}p$ then $p$ is called a piece. A presentation has $C^{\prime}(1/\lambda)$ if every piece of every relator is $<1/6$ of the relator, and it has $C(m)$ if every relator is a product of no fewer that $m$ pieces. There is also the $T(m)$-condition, which I will explain in the next paragraph...

If you have ever heard of van Kampen diagrams, these are very much related. Draw a circle for each of your relators, and then partition the circle into the pieces of the relator. Essentially, small cancellation forces the tilings of these van Kampen diagrams to be "nice". For example, the $C(m)$ condition implies that every diagram is at least an $m$-gon, and the $T(m)$-condition implies that every vertex is the join of no more that $m$-diagrams. So, for example, if you have $C(4)-T(4)$ or $C(3)-T(6)$ then your diagram is flat. This yields, with a lot of work, a solution to the word and conjugacy problems for such groups.

However, the $C(4)-T(4)$ are kinda uninteresting - the $C^{\prime}(\lambda)$ one is the biggie. This is because if you have $C^{\prime}(1/6)$ the your diagrams are negatively curved! and so your group is hyperbolic. The result which gives you this is Greendlinger's Lemma. The standard reference for all this is the last chapter of Lyndon and Schupp's fine text "Combinatorial Group Theory" (which is not to be confused with Magnus Karrass and Solitar's book of the same name, which is differently excellent!).

Small cancellation theory has wound its way throughout combinatorial and geometric group theory. For example, Rips construction uses small cancellation theory, and a variation on this construction was used by Dani Wise and Inna Bumagin to construct finitely generated groups with a given outer automorphism group (as in, you give them a group $G$ and they can construct a finitely generated group $H$ such that $\operatorname{Out}(H)\cong G$).

Small cancellation can also be applied to other things, such as graphs (which is what the paper of Kapovich and Schupp does) as well as things called "cubical complexes". The cubical complex stuff is very powerful, and was engineered by Dani Wise. It has come to a head in the last couple of years, leading to a proof of the virtually Haken conjecture. Which is massive. Ian Agol then improved on this result. Again, this is massive. (the cubical complex stuff also proves that every one-relator group with torsion is residually finite, which ahs been open since 1967. So that is pretty big too!)

-
I haven't checked, but I believe Champetier's work on the Chabauty topology also includes some results on small cancellation groups. E.g. in L’espace des groupes de type fini. – t.b. Aug 9 '12 at 10:14
Also: Yann Ollivier has a few results on Small cancelation and random groups. e.g. here – t.b. Aug 9 '12 at 10:21
As far as the Wise stuff goes: you can find all the lectures, videos of the lectures, etc. on one website: comet.lehman.cuny.edu/behrstock/cbms/program.html . It is incredibly interesting! – user641 Aug 9 '12 at 16:26
I spent a week at a workshop he was doing recently. Fascinating, but only locally understandable. However, that link should be very helpful - thanks! – user1729 Aug 9 '12 at 16:57