[MathJax on]

1 Small Cancellation Theory: the classical conditions

1.1 Introduction

The standard reference for Small Cancellation Theory is Lyndon-Schupp [LS01, Chapter V]. We review here some definitions and results.

A subset R of a free group F is called symmetrized if all elements of R are cyclically reduced and for each r in R all cyclically reduced conjugates of r and r^-1 are also in R. If the set R is not symmetrized we may work instead with the symmetrization R^* of R (the smallest symmetrized set containing R).

A piece of R is a word that is a common prefix of two different words in the symmetrized set R^*.

We say that a presentation P=⟨ X ∣ R⟩ satisfies the small cancellation condition C(p) if no relator r in R^* is a product of fewer than p pieces.

We say that P satisfies the small cancellation condition C'(λ) if for all r in R^*, if r=bc and b is a piece then |b| < λ |r|.

We say that P satisfies the small cancellation condition T(q) if for all h such that 3≤ h < q and for all elements r_1,..., r_h in R^*, if no succesive elements r_i,r_i+1 is an inverse pair, then at least one of the products r_1r_2,... r_h-1r_h, r_hr_1 is reduced without cancellation. Condition T(q) may be rephrased in terms of the Whitehead graph of the presentation P.

If a group G=⟨ X ∣ R⟩ satisfies C'(1/6) then Dehn's algorithm (see [LS01, Chapter V, Section 4]) solves the word problem for G.

If a group G=⟨ X ∣ R⟩ satisfies C(6) or C(4)–T(4) or C(3)–T(6) then G has solvable word problem and solvable conjugacy problem (see [LS01, Chapter V, Sections 5 and 6]).

If a presentation P=⟨ X ∣ R⟩ satisfies C(6) and no relator of P is a proper power then the presentation complex of P is aspherical.

1.2 Pieces

1.2-1 PiecesOfGroup

Returns the set of pieces of the FpGroup G.

gap> F:=FreeGroup(["a","b"]);;
gap> AssignGeneratorVariables(F);;
#I  Assigned the global variables [ a, b ]
gap> r:=a*b*a*b^2*a*b^3;;
gap> G:=F/[r];;
gap> PiecesOfGroup(G);
[ a^-1, a, b^-1, b, a^-1*b^-1, a*b, b^-1*a^-1, b^-2, b*a, b^2, a^-1*b^-2, 
  a*b^2, b^-1*a^-1*b^-1, b^-2*a^-1, b*a*b, b^2*a, b^-1*a^-1*b^-2, 
  b^-2*a^-1*b^-1, b*a*b^2, b^2*a*b ]

1.2-2 PiecesOfPresentation

Returns the set of pieces of the presentation P.

1.3 Metric small cancellation conditions

1.3-1 GroupSatisfiesCPrime

Returns true if the FpGroup G satisfies the small cancellation condition C'(lambda), false otherwise. If the optional argument explain is true instead of returning false returns an explanation of this result.

gap> F:=FreeGroup(["a1","b1","a2","b2","a3","b3"]);;
gap> AssignGeneratorVariables(F);;
#I  Assigned the global variables [ a1, b1, a2, b2, a3, b3 ]
gap> r:=Comm(a1,b1)*Comm(a2,b2)*Comm(a3,b3);;
gap> G:=F/[r];;
gap> GroupSatisfiesCPrime(G,1/11);
true
gap> GroupSatisfiesCPrime(G,1/12);
false
gap> GroupSatisfiesCPrime(G,1/12,true);
[ false, a1^-1*b1^-1*a1*b1*a2^-1*b2^-1*a2*b2*a3^-1*b3^-1*a3*b3, 
  " starts with a piece of length ", 1 ]

1.3-2 PresentationSatisfiesCPrime

Returns true if the presentation P satisfies the small cancellation condition C'(lambda), false otherwise. If the optional argument explain is true instead of returning false returns an explanation of this result.

1.4 Non-metric small cancellation conditions

1.4-1 GroupSatisfiesC

Returns true if the FpGroup G satisfies the small cancellation condition C(p), false otherwise. If the optional argument explain is true instead of returning false returns an explanation of this result.

gap> GroupSatisfiesC(G,12);
true
gap> GroupSatisfiesC(G,13);
false
gap> GroupSatisfiesC(G,13,true);
[ false, a1^-1*b1^-1*a1*b1*a2^-1*b2^-1*a2*b2*a3^-1*b3^-1*a3*b3, 
  " is the product of pieces of the following lengths: ", 
  [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] ]

1.4-2 PresentationSatisfiesC

Returns true if the presentation P satisfies the small cancellation condition C(p), false otherwise. If the optional argument explain is true instead of returning false returns an explanation of this result.

1.4-3 GroupSatisfiesT

Returns true if the FpGroup G satisfies the small cancellation condition T(q), false otherwise.

gap> GroupSatisfiesT(G,12);
true
gap> GroupSatisfiesT(G,13);
false

1.4-4 PresentationSatisfiesT

Returns true if the presentation P satisfies the small cancellation condition T(q), false otherwise.

1.5 Implementation details

Relators and their prefixes are stored in a data structure called trie [Wik19]. This provides an efficient way to write a word as a product of pieces using the minimum possible number of pieces.

generated by GAPDoc2HTML