arXiv:1605.06145v1 [math.GR] 19 May 2016

HNN EXTENSIONS AND STACKABLE GROUPS
SUSAN HERMILLER AND CONCHITA MARTÍNEZ-PÉREZ
Abstract. Stackability for finitely presented groups consists of a dynamical system that iteratively moves paths into a maximal tree in the
Cayley graph. Combining with formal language theoretic restrictions
yields auto- or algorithmic stackability, which implies solvability of the
word problem. In this paper we give two new characterizations of the
stackable property for groups, and use these to show that every HNN extension of a stackable group is stackable. We apply this to exhibit a wide
range of Dehn functions that are admitted by stackable and autostackable groups, as well as an example of a stackable group with unsolvable
word problem. We use similar methods to show that there exist finitely
presented metabelian groups that are non-constructible but admit an
autostackable structure.

1. Introduction
Autostackability of finitely generated groups is a topological property
of the Cayley graph combined with formal language theoretic restrictions,
which is an extension of the notions of automatic groups and groups with
finite complete rewriting systems, introduced by Brittenham, Hermiller and
Holt in [8]. An autostackable structure for a finitely generated group implies
a finite presentation, a solution to the word problem, and a recursive algorithm for building van Kampen diagrams [6]. Moreover, in contrast to automatic groups, Brittenham and Hermiller together with Susse have shown
that the class of autostackable groups includes all fundamental groups of
3-manifolds [9], with Holt they have shown autostackable examples of solvable groups that are not virtually nilpotent [7], and with Johnson they show
that Stallings’ non-F P3 group [8] is autostackable. In analogy with the relationship between automatic and combable groups, removing the formal
language theoretic restriction gives the stackable property for finitely generated groups, and stackability implies tame combability [5]. In this paper
we give two new characterizations of the stackability property, and determine closure of stackability under HNN extensions. We then apply these
results to a variety of examples to exhibit stackable groups that are not
algorithmically stackable and to explore the Dehn functions of stackable,
algorithmically stackable, and autostackable groups. In the last section we
also show that nonconstructible metabelian groups can be autostackable.
To make this more precise, let G be a group with a finite inverse-closed
generating set X, and let Γ = Γ(G, X) be the associated Cayley graph.
2010 Mathematics Subject Classification. 20F65; 20F10, 20F16, 68Q42.
1

2

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

~ and the set of directed edge
Denote the set of directed edges in Γ by E,
paths by P~ . For each g ∈ G and a ∈ X, let eg,a denote the directed
edge with initial vertex g, terminal vertex ga, and label a; we view the two
directed edges eg,a and ega,a−1 to have a single underlying undirected edge
in Γ.
~ →
A flow function associated to a maximal tree T in Γ is a function Φ : E
~
P satisfying the properties that:
~ the path Φ(e) has the same initial and terminal
(F1) For each edge e ∈ E,
vertices as e.
(F2d) If the undirected edge underlying e lies in the tree T , then Φ(e) = e.
~ defined by
(F2r) The transitive closure <Φ of the relation < on E
′
′
e < e whenever e lies on the path Φ(e) and the undirected
edges underlying both e and e′ do not lie in T ,
is a well-founded strict partial ordering.
~
The flow function is bounded if there is a constant k such that for all e ∈ E,
the path Φ(e) has length at most k. The map Φ fixes the edges lying in
the tree T and describes a “flow” of the non-tree edges toward the tree
(or toward the basepoint); starting from a non-tree edge and iterating this
function finitely many times results in a path in the tree.
For each element g ∈ G, let nf(g) denote the label of the unique geodesic
(i.e., without backtracking) path in the maximal tree T from the identity
element ε of G to g, and let N = NT := {nf(g) | g ∈ G} denote the set of
these (unique) normal forms. We use functions that pass between paths and
words by defining label : P~ → X ∗ to be the function that maps each directed
path to the word labeling that path and defining path : N × X ∗ → P~ to be
path(nf(g), w) := the path in Γ that starts at g and is labeled by w. Observe
~
that path(N × X) = E.
Definition 1.1. [6, 7] Let G be a group with a finite inverse-closed generating set X.
(i) The group G is stackable over X if there is a bounded flow function
on a maximal tree in the associated Cayley graph. The stacking
map is
φ := label ◦ Φ ◦ path : NT × X → X ∗ .
(ii) The group G is algorithmically stackable over X if G admits a
bounded flow function Φ for which the graph
graph(φ) := {(nf(g), a, φ(nf (g), a)) | g ∈ G, a ∈ X}
of the stacking map φ is decidable.
(iii) The group G is autostackable over X if G has a bounded flow function Φ for which the graph of the associated stacking map is synchronously regular.
A stackable group G over a finite generating set A is finitely presented,
with finite presentation RΦ = hX | {φ(y, a) = a | y ∈ NT , a ∈ X}i (called
the stacking presentation) associated to the flow function Φ.

HNN EXTENSIONS AND STACKABLE GROUPS

3

Each of these three stackability properties can also be stated in terms of
prefix-rewriting systems. A stackable structure is equivalent to a bounded
complete prefix-rewriting system for G over X, for which the irreducible
words are exactly the elements of the set NT . A group is algorithmically
stackable (respectively, autostackable) if and only if it admits a decidable
(respectively, synchronously regular) bounded complete prefix-rewriting system [7]. (See Section 2 for definitions of these terms.)
In Section 2, we begin with notation and definitions we will use throughout
the paper.
Section 3 contains several characterizations of stackability using properties
of their van Kampen diagrams, which we apply in our proofs in later sections
of this paper.
Section 4 contains the proof of the following closure property for the class
of stackable groups with respect to HNN extensions.
Theorem 4.4. Let H be a stackable group, let A, B ≤ H be finitely generated, and let ψ : A → B be an isomorphism. Then the HNN extension
G = H∗ψ is also stackable.
Corollary 4.6 addresses closure of auto- and algorithmic stackability of
HNN extensions with additional constraints. In the case of algorithmically
stackable groups, HNN extension closure can also be stated in terms of a
decision problem. For a group H with a finite inverse-closed generating set
Y and subgroup A, the subgroup membership problem is decidable if there
is an algorithm that, upon input of any word w over Y , determines whether
or not w represents an element of A.
Corollary 4.7. Let H be an algorithmically stackable group, let A, B ≤ H
be finitely generated, and let ψ : A → B be an isomorphism. Suppose further
that the subgroup membership problem is decidable for the subgroups A and B
in H. Then the HNN extension G = H∗ψ is also algorithmically stackable.
We give three applications of Theorem 4.4 in Section 5. In the first,
we apply Mihailova’s [17] construction of subgroups of direct products of
free groups with unsolvable subgroup membership problem, to show that
stackability and autostackability are not the same property.
Theorem 5.1. There exists a stackable group with unsolvable word problem,
and hence stackability does not imply algorithmic stackability.
Consequently the class of stackable groups includes groups whose Dehn
function is not computable. Our second application is a proof that the
hydra groups of Dison and Riley [12] are algorithmically stackable, and
consequently algorithmically stackable groups admit extremely large Dehn
functions.
Theorem 5.2. The class of algorithmically stackable groups includes groups
with Dehn functions in each level of the Grzegorczyk hierarchy of primitive
recursive functions.

4

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

For the third application in Section 5, we we study the nonmetabelian
Baumslag group [2] (also known as the Baumslag-Gersten group), which is
an HNN extension of a Baumslag-Solitar group (which is autostackable [7]).
Theorem 5.3. Baumslag’s nonmetabelian group ha, s | (sas−1 )a(sa−1 s−1 ) =
a2 i is autostackable.
Platonov [18] (and in the case of the lower bound, Gersten [13]) has
shown that the Dehn function of the Baumslag nonmetabelian group is
the nonelementary function n → tower 2 (log2 (n)), where tower 2 (1) = 2 and
tower 2 (k) = 2tower 2 (k−1) . Although it is an open question whether Baumslag’s nonmetabelian group, or any other group with nonelementary Dehn
function, can have a finite complete rewriting system, these results show that
groups with a bounded synchronously regular complete prefix-rewriting system admit such Dehn functions.
Corollary 5.4. The class of autostackable groups includes groups with
nonelementary Dehn functions.
Finally, in Section 6, we consider metabelian groups. Groves and Smith [14]
showed that a metabelian group G has a finite complete rewriting system
if and only if G has the homological finiteness condition F P∞ , and also if
and only if G is constructible (that is, G can be obtained from finite groups
by iteratively taking finite extensions, amalgamations, and finite rank HNN
extensions). Since synchronously regular bounded prefix-rewriting systems
(i.e., autostackable structures) are an extension of finite complete rewriting
systems, it is natural to ask whether autostackability is also equivalent to
F P∞ and constructibility in metabelian groups.
We consider Baumslag’s [3] example of a finitely presented metabelian
group whose commutator subgroup has infinite rank. This group is finitely
presented, and hence has homological type FP2 , but the rank of the commutator subgroup implies that the group is not constructible, and hence is not
of type FP∞ . For p < ∞, the p-torsion analog of Baumslag’s metabelian
group is the Diestel-Leader group Γ3 (p), whose Cayley graph with respect
to a certain finite generating set is the Diestel-Leader graph DL3 (p); for details and more information, see the paper of Stein, Taback, and Wong [19]
and the references there. The Diestel-Leader groups are finitely presented
metabelian groups that are not of type FP3 [1], and hence also are nonconstructible metabelian groups. Each of these groups can be realized as an
HNN extension, but since the base group of this extension is not finitely
generated, Theorem 4.4 of Section 4 does not apply in this case, and new
methods are developed in Section 6 to show the following.
Theorem 6.1. Baumslag’s metabelian group G∞ = ha, s, t | as = at a, [at , a] =
1, [s, t] = 1i is algorithmically stackable, and the Diestel-Leader torsion
analogs Gp = ha, s, t | as = at a, [at , a] = 1, [s, t] = 1, ap = 1i with p ≥ 2
are autostackable.
This shows that there exist nonconstructible metabelian groups that admit a synchronously regular bounded prefix-rewriting systems, giving a neagtive answer to the question above.

HNN EXTENSIONS AND STACKABLE GROUPS

5

Corollary 6.2. The class of autostackable groups contains nonconstructible
metabelian groups.
The authors thank Tim Susse for helpful discussions and useful suggestions during the course of this work.
2. Notation and background
Throughout this paper, let G be a group with a finite symmetric generating set X; that is, such that the generating set X is closed under inversion.
Throughout the paper we assume that no element of X represents the identity element of G.
Let X ∗ denote the set of all words over X, and let X + denote the set of
all words except the empty word 1. A set N of normal forms for G over
X is a subset of X ∗ such that the restriction of the canonical surjection
ρ : X ∗ → G to N is a bijection. As in Section 1, the symbol nf(g) denotes
the normal form for g ∈ G. By slight abuse of notation, we use the symbol
nf(w) to denote the normal form for ρ(w) whenever w ∈ X ∗ .
For a word w ∈ X ∗ , we write w−1 for the formal inverse of w in X ∗ , and
let l(w) denote the length of the word w. For words v, w ∈ X ∗ , we write
v = w if v and w are the same word in X ∗ , and write v =G w if v and w
represent the same element of G.
Let ε denote the identity of G. For g, h ∈ G, we use gh to denote the
conjugate hgh−1 of g.
A symmetrized presentation P = hX | Ri for G satisfies the properties
that the generating set X is symmetric and the set R of defining relations
is closed under inversion and cyclic conjugation. Let C be the Cayley 2complex corresponding to this presentation, whose 1-skeleton C 1 = Γ is the
Cayley graph of G over A. For g ∈ G and x ∈ X, let eg,x denote the edge
of Γ labeled by x with initial vertex g. We consider the two directed edges
eg,x and egx,x−1 to have the same underlying directed edge in Γ between the
vertices g and gx.
2.1. Diagrams. For an arbitrary word w in X ∗ that represents the trivial
element ε of G, there is a van Kampen diagram ∆ for w with respect to
P. That is, ∆ is a finite, planar, contractible combinatorial 2-complex with
edges directed and labeled by elements of X, satisfying the properties that
the boundary of ∆ is an edge path labeled by the word w starting at a
basepoint vertex ∗ and reading counterclockwise, and every 2-cell in ∆ has
boundary labeled by an element of R. (Note that we do not assume that
van Kampen diagrams in this paper are reduced; that is, we allow adjacent
2-cells in ∆ to be labeled by the same relator with opposite orientations.)
For any van Kampen diagram ∆ with basepoint ∗, let π∆ : ∆ → C denote
a cellular map such that π∆ (∗) = ε and π∆ maps edges to edges preserving
both label and direction. Given w ∈ X ∗ , we denote by w∆ the diagram
obtained by gluing the terminus of a path labeled by w to the basepoint ∗
of ∆.

6

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

2.2. Rewriting systems and languages. The regular languages over a
finite set X are the subsets of X ∗ obtained from the finite subsets of X ∗
using finitely many operations from among union, intersection, complement,
concatenation (S · T := {vw | v ∈ S and w ∈ T }), and Kleene star (S 0 :=
n
∗
{1}, S n := S n−1 · S and S ∗ := ∪∞
n=0 S ). Equivalently, a subset L ⊆ X
∗
is regular if there is a monoid homomorphism γ : X → M for some finite
monoid M , such that L is the preimage L = γ −1 (S) for a subset S of M .
Also equivalently, a language L ⊆ X ∗ is regular if L is the language accepted
by a finite state automaton.
A subset L ⊆ (X ∗ )n is called a synchronously regular language if the
padded extension set {pad(w) | w ∈ L} is a regular language over the finite
alphabet (X∪{$})n (with $ ∈
/ X) where pad(a1,1 · · · a1,m1 , ..., an,1 · · · an,mn ) :=
((a1,1 , ..., an,1 ), ..., (a1,N , ..., an,N )) for N = max{mi } whenever ai,j ∈ X for
all 1 ≤ i ≤ n and 1 ≤ j ≤ mi and ai,j = $ otherwise.
The class of regular languages is closed under both image and preimage via
monoid homomorphisms and under quotients, and the class of synchronously
regular languages is closed with respect to finite unions and intersections,
Cartesian products, and projection onto a single coordinate.
A language L ⊆ X ∗ is decidable, also known as recursive, if there is a Turing machine that, upon input of any word w over X, determines (in a finite
amount of time) whether or not w ∈ L. The class of decidable languages
is also closed under union, intersection, complement, concatenation, Kleene
star, and image via monoid homomorphisms (that map nonempty words to
nonempty words).
See [10] and [15] for more information about regular, synchronously regular, and decidable languages.
A complete prefix-rewriting system for a group G consists of a set X and
a set of rules R ⊆ X ∗ × X ∗ (with each (u, v) ∈ R written u → v) such that
G is presented (as a monoid) by G = M onhX | u = v whenever u → v ∈ Ri,
and the rewritings uy → vy for all y ∈ X ∗ and u → v in R satisfy:
(1) there is no infinite chain w → x1 → x2 → · · · of rewritings, and
(2) each g ∈ G is represented by exactly one irreducible word over X.
The prefix-rewriting system is bounded if X is finite and there is a constant k
such that for each pair (u, v) in R there are words s, t, w ∈ X ∗ such that u =
ws, v = wt, and l(s)+l(t) ≤ k. The prefix-rewriting system is synchronously
regular if the set X is finite and the set of rules R is synchronously regular.
A finite complete rewriting system for a group G is a finite set R′ ⊆
∗
X × X ∗ presenting G as a monoid, such that the rewritings xuy → xvy for
all x, y ∈ X ∗ and u → v in R′ satisfy (1) and (2) above. Any finite complete
rewriting system R′ has an associated synchronously regular bounded complete prefix-rewriting system given by R = {xu → xv | x ∈ X ∗ , (u, v) ∈ R′ }.
3. The fully N -triangular and N -labeled properties
In this section we develop several conditions that are equivalent to stackability, which will be used to simply proofs in later sections of this paper.

HNN EXTENSIONS AND STACKABLE GROUPS

7

Let G be a group with a finite presentation P = hX | Ri, where X is
inverse-closed and R is closed under inversion and cyclic conjugation. Let
N be a prefix-closed set of normal forms for G over X. For each element
g in G, let nf(g) denote the element of N representing g. Let TN denote
the tree in the Cayley graph Γ for G over A consisting of the underlying
undirected edges that lie along paths from the identity vertex ε labeled by
elements of N .
Definition 3.1. We say that a van Kampen diagram ∆ is N -triangular
if ∂∆ is labeled by a word of the form nf(g)xnf(gx)−1 with g ∈ G and
x ∈ X. We refer to the paths plower , px , pupper in ∂∆ labeled by nf(g), x,
and nf(gx) as the lower normal form, isolated edge, and upper normal form
of ∆, respectively.
Definition 3.2. A N -triangular van Kampen diagram ∆ is N -labeled if
for every vertex v in the 0-skeleton ∆(0) of ∆, there is a path in ∆ from
the basepoint to v labeled by the normal form nf(π∆ (v)). In this case ∆
determines a set of normal forms starting at the basepoint, namely
nf(∆) := {nf(π∆ (v)) | v ∈ ∆(0) }.
If G is stackable over the normal form set N , with stacking relations contained in R, then there is a recursive procedure for building van Kampen
diagrams for G over the presentation P; see [6] for details of this stacking procedure. In the following recursive definition we describe a similar
property.
Definition 3.3. Fully N -triangular diagrams are recursively defined as follows. A diagram ∆ is called
i) degenerate if ∆ has no 2-dimensional cells.
ii) minimal if ∆ has a single 2-dimensional cell σ and px ⊂ ∂σ.
iii) fully N -triangular if ∆ is either degenerate, minimal, or there is a
2-dimensional cell σ in ∆ with px ⊂ ∂σ, which we call the isolated
cell, satisfying the following property. If e1 , ..., et are the successive
edges of the path in ∂σ r px from the initial vertex to the terminus
of the edge px , then for each i = 1, ..., t there is a fully N -triangular
van Kampen diagram ∆i ⊆ ∆ having ei as isolated edge and the
same basepoint as ∆, such that
– for each i, ∆i ∩ ∆i+1 is both the upper normal form of ∆i and
the lower normal form of ∆i+1 , and
– ∆ is the disjoint union of the ∆i and σ, with the ∆i glued along
these successive normal forms, and σ glued to the ∆i along the
edges ei .
In this case, ∆ determines a set of fully N -triangular van Kampen diagrams,
namely, the ∆i together with the set of fully N -triangular van Kampen
diagrams determined by them; we denote this set by ft(∆).
We note that every fully N -triangular van Kampen diagram is also N labeled. Also note that if w ∈ X ∗ and ∆ is N -labeled or fully N -triangular,

8

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

and moreover if for every µ ∈ nf(∆) we have wµ ∈ N , then w∆ is also
N -labeled or fully N -triangular, respectively.
In the case that the group G is stackable with respect to N , let ∆g,x
denote the van Kampen diagram with boundary nf(g)xnf(gx)−1 obtained
using the stacking procedure. Given a directed edge eg,x of the Cayley
graph Γ, if eg,x lies in the tree TN , then ∆g,x is degenerate, and so is fully
N -triangular. To check that for any edge eg,x not in TN the diagram ∆g,x is
fully N -triangular, we note that the isolated cell has boundary Φ(eg,x ) and
px , and the recursive property in Definition 3.3 iii) holds true by induction
using the partial order <Φ on the set of recursive edges given by the stacking
system. In fact, if eh,y <Φ eg,x , then eh,y is an edge needed in the process to
transform nf(g)x into its normal form in the stacking reduction procedure,
and ∆h,y ∈ ft(∆g,x ).
Definition 3.4. A stackable system of fully N -triangular van Kampen diagrams (respect to P) is a set
S := {∆g,x | g ∈ G, x ∈ X}
of fully N -triangular diagrams such that for each g ∈ G and x ∈ X the
boundary of the diagram ∆g,x is labeled by nf(g)xnf(gx)−1 , the diagram
∆g,x is degenerate if and only if eg,x is in the tree TN , and whenever ∆g,x ∈ S
contains more than one 2-cell, the associated subdiagrams ∆i in Definition
3.3 iii) also belong to S.
Proposition 3.5. The following are equivalent for a finitely presented group
G = hX | Ri with a prefix-closed normal form set N over X:
i) G is stackable with respect to N .
ii) There is a stackable system of fully N -triangular van Kampen diagrams.
iii) For every g ∈ G and x ∈ X there is a fully N -triangular van
Kampen diagram ∆g,x with boundary nf(g)xnf(gx)−1 .
iv) For every w ∈ N and x ∈ X there is a N -labeled van Kampen
diagram ∆′w,x with boundary wxnf(wx)−1 .
Proof. The fact that i) implies ii) follows from the discussion above, and the
implications ii) ⇒ iii) and iii) ⇒ iv) are immediate. We prove the reverse
implications in the same order.
Let Γ denote the Cayley graph of G with respect to the generating set
X, and let TN be the maximal tree in Γ traversed by paths starting at the
identity vertex and labeled by words in N .
First, assume ii) holds, and let S be the stackable system. If eg,x is in
the tree TN in Γ, let Φ(eg,x ) := eg,x . On the other hand, if eg,x does not
lie in the tree TN in Γ and ∆g,x is the associated van Kampen diagram
in S, let Φ(eg,x ) be the path in Γ labeled by the word φ(eg,x ) in X ∗ such
that φ(eg,x )x−1 labels the isolated cell of ∆g,x . Note that this implies that
φ(eg,x )x−1 is a relator, and thus the possible lengths of the words φ(eg,x ) are
bounded. Now, we define a map ν from the set of directed edges in Γ r TN

HNN EXTENSIONS AND STACKABLE GROUPS

9

to Z+ by ν(eg,x ) := area of ∆g,x . Use the function ν and the usual ordering
on Z to order the set of recursive edges; this gives a well-founded ordering
~ such that e′ <Φ e implies ν(e′ ) < ν(e). Thus the group is stackable by
on E
Definition 1.1, and i) holds.
Next assume that iii) holds. For each directed edge eg,x of the Cayley
graph, let n(eg,x ) be the smallest area of a fully N -triangular van Kampen
diagram with boundary nf(g)xnf(gx)−1 . We define a stackable system S of
fully N -triangular van Kampen diagrams by induction on n(eg,x ). To start,
let S be the empty set. Note that n(eg,x ) = 0 if and only if eg,x is in TN ;
in this case add a degenerate diagram ∆(eg,x ) to S. Similarly, n(eg,x ) = 1
if and only if eg,x is not in TN and there is a minimal van Kampen diagram
for nf(g)xnf(gx)−1 ; place a choice of such a diagram in S. Suppose now that
n(eg,x ) > 1, and we have diagrams ∆g,x in (S) corresponding to all directed
edges with lower value for the function n. Let ∆′ be a fully N -triangular
van Kampen diagram for eg,x with n(eg,x ) 2-cells. Using Definition 3.3 iii),
∆′ is the disjoint union of a 2-cell σ containing px and fully N -triangular
diagrams ∆i , with certain gluings. The isolated edge ei associated with ∆i
must satisfy n(ei ) < n(eg,x ). For each i we replace the subdiagram ∆i of
∆′ by the diagram in S with the same boundary label, to obtain a diagram
∆g,x ; add this diagram to S. Then S is a stackable system, completing the
proof of ii).
Finally, assume that iv) holds. Then for each g ∈ G and x ∈ X, there is a
N -labeled van Kampen diagram with boundary label nf(g)xnf(gx)−1 ; from
among all such diagrams, let ∆′nf(g),x be a diagram with the least possible
number of 2-cells and let α(g, x) denote this number. We show that for each
g ∈ G and x ∈ X there is a fully N -triangular van Kampen diagram ∆g,x
with boundary label nf(g)xnf(gx)−1 by induction on α(g, x).
Suppose that α(g, x) = 0. Then the diagram ∆′g,x is degenerate, and
hence fully N -triangular. In this case we can take ∆g,x := ∆′g,x .
Suppose next that n := α(g, x) > 0, and that for all g′ ∈ G and x′ ∈
X with α(g′ , x′ ) < n there is a fully N -triangular diagram bounded by
nf(g ′ )x′ nf(g′ x′ )−1 . Let ∆′ := ∆′nf(g),x and let ∗ be the basepoint of ∆′ .
Suppose that there is a word w ∈ N that labels two paths p, p′ in ∆′
that start at ∗ and suppose that p and p′ can be factored as p = p1 p2 p3 and
p′ = p1 p′′ such that p2 is a nonempty edge path whose intersection with the
path p′ consists exactly of the initial vertex i(p2 ) and terminal vertex t(p2 )
of p2 . Since normal forms in N label simple paths in the tree TN , they must
also label simple paths in any van Kampen diagram; hence i(p2 ) 6= t(p2 ).
Now we can factor the path p′ = p1 p′2 p′3 such that p′2 is another path in ∆′
from i(p2 ) to t(p2 ). Moreover we can write w = w1 w2 w3 = w1 w2′ w3′ such
that for each i the word wi labels the path pi and wi′ labels p′i . The images
of the paths p1 p2 and p1 p′2 under the map π∆′ end at the same vertex in
the Cayley graph, and so prefix closure (and uniqueness) of the normal form
set imply that w2 = w2′ . A similar argument shows that the path p′2 cannot
intersect the path p except at the common endpoints of p2 and p′2 . Hence

10

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

the path p2 p′−1
is a simple loop in ∆′ . By the Jordan Curve Theorem, this
2
loop separates the diagram ∆′ into two subsets. We remove the subdiagram
of ∆′ contained inside this loop, and glue the two simple paths p2 and p′2 ;
this results in a new van Kampen diagram ∆′′ with the same basepoint and
boundary. Moreover, the diagram ∆′′ is N -labeled, and contains fewer cells
than ∆′ ; this contradicts our choice of ∆′ = ∆′g,x as a N -labeled triangular
van Kampen diagram with minimal number of 2-cells. Hence the set of edges
that lie along paths in ∆′ starting at ∗ and labeled by elements of N must
form a maximal tree, since a pair of such paths cannot have prefixes that
diverge and then merge.
If the edge eg,x lies in the tree TN , then either nf(gx) = nf(g)x or
nf(g) = nf(gx)x−1 . There is a degenerate, and hence fully N -triangular, van
Kampen diagram ∆g,x (= ∆′ ) consisting of a line segment labeled nf(gx) or
nf(g), respectively, in this case.
On the other hand, suppose that eg,x is not in TN . Note that ∆′ must
contain a 2-cell σ with the isolated edge px in its boundary, since px is the
only directed edge in the path along ∂∆′ mapped by π∆′ to an edge outside
of TN . If ∆′ contains only one 2-cell, then ∆′ is minimal, and hence fully N triangular. Suppose that ∆′ contains more than one 2-cell. Let v0 , v1 , ..., vt
be the successive vertices, and e1 , ...et the successive edges, of the path in
∂σ r px from the initial vertex v0 to the terminal vertex vt of px . For each
0 ≤ i ≤ t, there is a unique path pi from the basepoint ∗ to vi that is labeled
by a word in N . For each 0 ≤ i < t, the concatenated path li := pi ei p−1
i+1
is a loop in ∆′ . Let qi be the maximal common prefix of the pair of paths
pi , pi+1 ; that is, pi = qi ri and pi+1 = qi si . If qi equals one of the paths
p1 , pi+1 , then either qi = pi , ri is a constant path, and si = ei , or qi = pi+1 ,
ri = e−1
i , and si is constant; in both cases, the loop li follows a line segment
′
in ∆ and returns along the same segment back to ∗, and we let ∆i be the
degenerate van Kampen diagram given by this line segment. On the other
hand, if qi is a proper subpath of both pi and pi+1 , then the fact that normal
forms from ∗ label paths in a tree shows that the path ri ei s−1
is a simple
i
′
˜
loop in ∆ . Let ∆i denote the 2-complex inside this loop (including the
˜ i of ∆′ with the
bounding loop), and let ∆′i be the subdiagram ∆′i := qi ∆
same basepoint ∗. Again applying the fact that normal forms label paths
from ∗ that lie in a tree, for each vertex v of ∆′i , the path in ∆′ from ∗ to
v must lie in ∆′i ; hence ∆′i is N -labeled triangular. Since the number of
2-cells in ∆′i is at most n − 1, by our inductive assumption there is a fully
N -triangular van Kampen diagram ∆i with the same boundary label as ∆′i .
Now the diagram ∆g,x built from the disjoint union of the ∆i and σ, glued
along the normal form paths pi and the edges ei , is a fully N -triangular van
Kampen diagram with boundary label nf(g)xnf(gx)−1 , and therefore iii)
holds.


HNN EXTENSIONS AND STACKABLE GROUPS

11

4. HNN extensions and stackability
Throughout this section, let G = H∗ψ be the HNN-extension of the group
H with isomorphism ψ : A → B between subgroups A and B and stable
letter s. Assume that H is finitely generated and let H = hY | RH i be a
presentation for H, where Y is a finite inverse closed generating system for
H. Let X := {s, s−1 } ∪ Y , and let ρ : X ∗ → G be the canonical surjection.
Then G has the presentation
(1)

G = hX | RH , {sas−1 = ψ(a) | a ∈ A}i.

Notation 4.1. Let NH be a set of normal forms for H over Y . Let NH/A be
ρ

a subset of NH satisfying the properties that the composition NH/A → H →
H/A is a bijection and 1 ∈ NH/A , and similarly let NH/B ⊆ NH be a set of
normal forms for a set of coset representatives for B in H that contains 1.
The Britton set of normal forms [16, p. 181] for G is
NG := {h1 sε1 h2 sε2 . . . hn sεn h | n ≥ 0, h ∈ NH and εi = ±1 for 1 ≤ i ≤ n;
if εi = +1 then hi ∈ NH/B
and if εi = −1 then hi ∈ NH/A ;
and if εi = −εi−1 then hi 6= 1};
that is, NG = (NH/A s−1 ∪ NH/B s)∗ NH r ∪ε∈{±1} X ∗ sε s−ε X ∗ . Given such a
word w = h1 sε1 h2 sε2 . . . hn sεn h in NG , we define tl(w) := h1 sε1 h2 sε2 . . . hn sεn
and hd(w) := h; we refer to these as the tail and head of w, respectively.
The following is immediate from the definition of Britton’s normal forms;
we will apply this in the proof of Theorem 4.4 below.
Lemma 4.2. Let w = h1 sε1 h2 sε2 . . . hn sεn h ∈ N and let τ ∈ N be a tail. If
either n = 0, h1 6= 1, or h1 = 1 and sε1 equals the last letter of τ , we have
τw ∈ N .
Before proceeding to Theorem 4.4, we first need a result about changing
generating sets for stackable and autostackable groups.
Proposition 4.3. Let H be a stackable group with respect to an inverseclosed generating set Y , and let Z be an inverse-closed subset of H. Then
H is also stackable with respect to the generating set Y ∪ Z. Moreover, if H
is autostackable over Y , then H is also autostackable over Y ∪ Z.
Proof. Let Γ := Γ(H, Y ) and Γ′ := Γ(H, Y ∪ Z) be the Cayley graphs for H
over Y and Y ∪ Z, respectively. For each z ∈ Z r Y , fix a word wz ∈ Y ∗
such that z =H wz .
Let Φ be a bounded flow function for H over the generating set Y , with
associated maximal tree T in Γ, normal form set N , and stacking function;
φ = label ◦ Φ ◦ path : N × Y → Y ∗ . The tree T is also a maximal tree in Γ′ ,
and the associated normal forms over Y ∪ Z is the same set N . Define the
function φ′ : N × Y ∪ Z → (Y ∪ Z)∗ by φ′ (w, y) := φ(w, y) for all w ∈ N
and y ∈ Y , and φ′ (w, z) := wz for all w ∈ N and z ∈ Z r Y . Then φ′ is a

12

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

stacking function for H over Y ∪ Z, and Φ′ := path ◦ φ′ ◦ label is a bounded
flow function for H over Y ∪ Z.
In the case that H is autostackable over Y , and graph(φ) is synchronously
regular, we have
[
graph(φ′ ) = graph(φ) (∪z∈ZrY N × {z} × {wz }).
Since the class of synchronously regular languages is closed under projection on the first coordinate, finite direct products, and finite unions, then
graph(φ′ ) is also synchronously regular, and so H is autostackable over
Y ∪ Z.

Theorem 4.4. Let H be a stackable group, let A, B ≤ H be finitely generated, and let ψ : A → B be an isomorphism. Then the HNN extension
G = H∗ψ is also stackable.
Proof. Suppose that H is stackable with respect to a normal form set NH
over an inverse-closed generating set Y , and let hY | RH i be the finite stacking presentation associated to the bounded flow function for H over Y . Let
NH/A ,NH/B be subsets of NH (each containing 1) representing transversals of these subgroups. Using the proof of Proposition 4.3, by possibly
extending the flow function and adding relators (of the form z = wz ) to the
presentation, we may assume that the generating set Y contains a subset
ZA which is an inverse-closed generating set for A, as well as the subset
ZB := {ψ(a) | a ∈ ZA } of H, which generates B. (Note that this does not
affect the normal form sets NH , NH/A and NH/B .) Using Proposition 3.5,
for every word w ∈ NH and y ∈ Y , we have a fully NH -triangular van
Kampen diagram ∆H
w,y over the stacking presentation for H.
Let NG be the Britton normal form set of Notation 4.1. Since the set
NH is prefix-closed, then the set NG = (NH/A s−1 ∪ NH/B s)∗ NH ∩ (X ∗ r
∪ε∈{±1} X ∗ sε s−ε X ∗ ) is also prefix-closed. For all w ∈ X ∗ , let nf(w) denote
the normal form in NG of the element of G represented by w. Let Γ :=
Γ(G, X) be the Cayley graph for G over X := Y ∪ {s±1 }, and let T be the
maximal tree of Γ corresponding to the set NG .
We will show that G is stackable with respect to NG by showing that over
the finite presentation in Equation (1) there is a fully NG -triangular van
Kampen diagram ∆w,x with boundary label wxnf(wx)−1 for every normal
form word w ∈ NG and generator x ∈ X; that is, we apply Proposition 3.5.
We proceed via several cases depending upon w and x; in each case, we have
that fully NG -triangular van Kampen diagrams have been constructed for
the prior cases.
Case 1: Suppose that x ∈ Y . Let ∆H
hd(w),x be the fully NH -triangular van
Kampen diagram associated to hd(w) and x. By Lemma 4.2, for all v ∈
NH we have tl(w)v ∈ NG . Thus the diagram tl(w)∆H
hd(w),x is a fully NG triangular van Kampen diagram in G, with boundary label wxnf(wx)−1 .

HNN EXTENSIONS AND STACKABLE GROUPS

13

Figure 1. The diagram ∆w,s.

nf (w

b−

1 sa)

∆3

a

−1
nf(wb s)
∆2 s
nf(wb −1)

w

∆1

s

b−1

Case 2: Suppose that x = s±1 . The two cases x = s and x = s−1 are
analogous, so we assume that x = s and leave the case when x = s−1 to the
reader.
∗ denote the set of shortlex normal forms for B over the
Let SLB ⊂ ZB
generating set ZB with respect to some total ordering of ZB . The element of
H represented by hd(w) can be written hd(w) =H uv for a unique u ∈ NH/B
and v ∈ SLB .
We proceed by induction on the length of v. If v = 1, then either wx =
ws ∈ NG or else w ends with s−1 ; in either case, there is a degenerate van
Kampen diagram ∆w,x with boundary word wsnf(ws)−1 .
Next suppose that l(v) > 0 and that we have a fully NG -triangular van
Kampen diagram for nf(tl(w)uv ′ )snf(tl(w)uv ′ s)−1 for all v ′ ∈ SLB with
l(v ′ ) < l(v). Write v = v ′ b with v ′ ∈ SLB and b ∈ ZB . Let a ∈ ZA be the
letter satisfying ψ(a) = b.
The normal form nf(wb−1 ) is w′ := tl(w)nf(uv ′ ); then since hd(w′ ) =H uv ′
and l(v ′ ) < l(v), our inductive assumption implies that there is a fully NG triangular van Kampen diagram ∆2 with boundary word nf(wb−1 )snf(wb−1 s)−1 .
Applying Case 1, there are fully NG -triangular diagrams ∆1 = tl(w)∆H
hd(w),b−1
−1
H
and ∆3 = tl(wb s)∆hd(wb−1 s),a (see Figure 1). Gluing the diagrams ∆1 , ∆2
along their (simple) boundary paths nf(wb−1 ), and gluing the resulting dia˜ of
gram with ∆3 along their nf(wb−1 s) paths, results in the subdiagram ∆
−1
Figure 1 with boundary label wb sa. We glue a single 2-cell with boundary
˜ along their b−1 sa boundary paths; this yields a fully NG label b−1 sas−1 to ∆
triangular van Kampen diagram ∆w,x with boundary label wxnf(wx)−1 . 
Remark 4.5. We record here, for later use, the result of Theorem 4.4 in
terms of stacking maps. Suppose that φH : NH × Y → Y ∗ is the stacking
map associated to the bounded flow function on H in Theorem 4.4. For each
word w ∈ NG define transA (w) and subA (w) to be the unique elements of the
transversal NH/A and subgroup shortlex representatives SLA , respectively,
such that hd(w) =H transA (w)subA (w), and let last(subA (w)) denote the last
letter (in ZA ) of the word subA (w). Similarly define transB (w), subB (w), and
last(subB (w)). The stacking map for G over X is the function φG : NG ×X →

14

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

X ∗ defined for all w ∈ NG and x ∈ Y by:


φH (hd(w), x)





x
φG (w, x) :=



last(subB (w))−1 sψ −1 (last(subB (w)))



last(sub (w))−1 s−1 ψ(last(sub (w)))
A
A

if x ∈ Y
if x = s and hd(w) = transB (w)
or x = s−1 and hd(w) = transA (w)
if x = s and hd(w) 6= transB (w)
if x = s−1 and hd(w) 6= transA (w).

In the case that the graph of the stacking map φH for H is decidable
or synchronously regular, the proof of Theorem 4.4 does not show that the
same must hold for the graph of the stacking function φG . However, in many
special cases, this does hold.

Corollary 4.6. Let H be an autostackable [respectively, algorithmically
stackable] group over an inverse-closed generating set Y . Let A ≤ H be
generated by a finite inverse-closed set Z ⊆ Y with shortlex normal form
set SLA (with respect to some total ordering of Z), and let ψ : A → H be
a monomorphism with ψ(Z) ⊆ Y . Suppose further that there are regular
[respectively, decidable] subsets NH/A , NH/ψ(A) ⊆ NH , each containing 1,
representing transversals of these subgroups, and that for each z ∈ Z and
z̃ ∈ ψ(Z), the sets
Lz := {w ∈ NH | w =H transA (w)subA (w) for some
transA (w) ∈ NH/A and subA (w) ∈ SLA ∩ Z ∗ z} and
Lz̃′ := {w ∈ NH | w =H transψ(A) (w)subψ(A) (w) for some
transψ(A) (w) ∈ NH/ψ(A) and subψ(A) (w) ∈ ψ(SLA ) ∩ ψ(Z)∗ z̃}
are also regular [respectively, decidable]. Then the HNN extension G = H∗ψ
is autostackable [respectively, algorithmically stackable].
Proof. We give the proof in the autostackable case; the algorithmically stackable proof is similar. In the notation of the proof of Theorem 4.4, let s ∈ G
be the stable letter of the HNN extension, and let X = Y ∪ {s±1 }.
Let φH be the the stacking map for the autostackable structure for H,
and let φG be the stacking map for G from Remark 4.5. Now graph(φH )
is synchronously regular. Let proj1 , proj3 : (X ∗ )3 → X ∗ be the projection
maps on the first and third coordinates. Note that the normal form set for
H is NH = proj1 (graph(φH )), and since synchronously regular languages are
closed under projections, the set NH is regular. The normal form set for G
has the form NG = Tail · NH where
Tail := (NH/A s−1 ∪ NH/ψ(A) s)∗ ∩ (X ∗ r ∪ε∈{±1} X ∗ sε s−ε X ∗ ),
and so NG is built from regular languages using intersection, union, complementation, concatenation and Kleene star. (See Section 2 for properties of
regular and synchronously regular languages.) Hence NG also is a regular
language.

HNN EXTENSIONS AND STACKABLE GROUPS

15

The graph of φG can be written
graph(φG ) =

where
L1
L2,1
L2,−1
L3,z
L′3,z̃

=
=
=
=
=


∪y∈Y,v∈proj3 (graph(φH )) L1 × {y} × {v}

∪ ∪ε∈{±1} L2,ε × {sε } × {sε }

∪ ∪z̃∈ψ(Z) L′3,z̃ × {s} × {z̃ −1 sψ −1 (z̃)}

∪ ∪z∈Z L3,z × {s−1 } × {z −1 s−1 ψ(z)}

Tail · proj1 (graph(φH ) ∩ (X ∗ × {y} × {v})),
Tail · NH/ψ(A) ,
Tail · NH/A ,
Tail · Lz , and
Tail · L′z̃ .

Again closure properties of regular and synchronously regular languages
show that each of these languages is regular, and hence so is graph(φG ). 
In the algorithmically stackable case, Corollary 4.6 can be rephrased in
terms of solvability of the subgroup membership problem.
Corollary 4.7. Let H be an algorithmically stackable group, let A, B ≤ H
be finitely generated, and let ψ : A → B be an isomorphism. Suppose further
that the subgroup membership problem is decidable for the subgroups A and B
in H. Then the HNN extension G = H∗ψ is also algorithmically stackable.
Proof. From the proof of Theorem 4.4, there is a finite inverse-closed generating set Y for H containing a finite inverse-closed set Z of generators
for A as well as the generators ψ(Z) of B = ψ(A), and there is a stackable
structure for G = H∗ψ over X = Y ∪ {s±1 } with Britton normal form set
NG , such that the associate stacking map is given in Remark 4.5. From
Corollary 4.6, then, it suffices to show that there are decidable transversals
NH/A , NH/B ⊆ NH , each containing 1, such that the languages Lz and L′z̃
of Corollary 4.6 are also decidable.
Let <SL denote the shortlex ordering on Y ∗ corresponding to a total
ordering of Y . For each coset hA of H/A, let τhA denote the shortlex least
word in NH representing an element of hA, and let
NH/A = {τhA | hA ∈ H/A}.
Note that the empty word 1 is an element of NH/A .
In order to determine whether a given word w ∈ Y ∗ lies in NH/A , first use
decidability to determine whether w ∈ NH . If not, then (halt and output)
w ∈
/ NH/A ; if so, we next enumerate the finite set S of elements of Y ∗
satisfying v <SL w for all v ∈ S. For each word v ∈ S, use decidability to
determine whether v ∈ NH and use the solution of the subgroup membership
problem to determine whether v −1 w ∈ A. If there is a word v ∈ S with
v ∈ NH and v −1 w ∈ A, then w ∈
/ NH/A ; and if there is no such word in S,
then w ∈ NH/A . Hence NH/A is decidable.

16

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

Next suppose that z ∈ Z and consider the set of Corollary 4.6
Lz := {u ∈ NH | u =H τ σ for some τ ∈ NH/A and σ ∈ SLA ∩ Z ∗ z}
where (as before) SLA is the set of shortlex normal forms for A over Z. The
algorithm to determine whether a given word w over Y lies in Lz also begins
by using decidability to determine whether w ∈ NH , and if not, halts with
w∈
/ Lz . If w ∈ NH , then we repeat the algorithm in the previous paragraph
to compute the word τ ∈ NH/A satisfying τ = τwA ; that is, τ A = wA
and so τ −1 w ∈ A, and moreover τ ≤SL w is the shortlex least word with
this property. Next enumerate all words y0 , y1 , y2 , ... over Z in increasing
shortlex order. Now since the word τ −1 w represents an element of A, we
have τ −1 w =H yj for some indices j; we can use the solution of the word
problem from the algorithmically stackable structure on H to determine the
first index i for which τ −1 w =H yi . Then σ := yi ∈ SLA and w =H τ σ. Now
w ∈ Lz iff yi ends with the letter z. Thus Lz is also decidable.
A similar argument shows that the set
′
NH/B = {τhB
| hB ∈ H/B},
′ denotes the shortlex least word in N representing an element of
where τhB
H
hB, is decidable and contains 1, and for each z̃ ∈ ψ(Z) the set

Lz̃′ := {w ∈ NH | w =H τ σ for some τ ∈ NH/ψ(A) and σ ∈ ψ(SLA )∩ψ(Z)∗ z̃}
is also decidable.



5. Applications and Dehn functions
In this section we give three applications of Theorem 4.4 and Corollaries 4.6 and 4.7, that give information on the Dehn functions of stackable,
algorithmically stackable, and autostackable groups.
5.1. Stackable versus autostackable. In the first application, we show
that stackability and autostackability are not the same property, and that
the class of stackable groups contains groups whose Dehn function is not
computable.
Theorem 5.1. There exists a stackable group with unsolvable word problem,
and hence stackability does not imply algorithmic stackability.
Proof. Let C = hY | Ri be a finitely presented group with unsolvable word
problem. Let Y ′ be a copy of Y , and let H = F (Y ) × F (Y ′ ) be a direct
copy of the free groups generated by Y and Y ′ . Also let ρ : F (Y ) → C and
ρ′ : F (Y ′ ) → C be the quotient maps. Let A be the Mihailova subgroup
A = {(h, h′ ) ∈ H | ρ(h) = ρ′ (h′ )}
associated to C. Mihailova [17] showed that the subgroup membership problem for A in H is not decidable; that is, there does not exist an algorithm
that upon input of a word w in the generating set (Y ∪ Y ′ )±1 of H, can

HNN EXTENSIONS AND STACKABLE GROUPS

17

determine whether w represents an element of the subgroup A. The group
A is finitely generated (see for example the paper of Bogopolski and Ventura [4] for a discussion and recursive presentation for this group); let Z be
a finite generating set for A.
To construct an HNN extension from this data, we let ψ : A → A be the
identity function on A, and let G = H∗ψ . Let Ye := Y ∪ Y ′ ∪ Z, and for each
z ∈ Z, let wz ∈ ((Y ∪ Y ′ )±1 )∗ be a word satisfying z =H wz . Then
G = hYe ∪ {s} | [y, y ′ ] = 1 for all y ∈ Y, y ′ ∈ Y ′ , and
z = wz and szs−1 = z for all z ∈ Zi.
Since the group H is a direct product of free groups, H is a stackable group.
Now the proof of Theorem 4.4 shows that G is a stackable group, with a
stackable structure over the generating set (Ye ∪ {s})±1 yielding the above
as the stacking presentation.
If the word problem for G were to have a solution, then upon input of any
word sws−1 with w ∈ (Y ∪ Y ′ )±1 ∗ ⊆ Ye ±1 ∗ , the word problem algorithm
can determine whether or not sws−1 w−1 =G ε. However, sws−1 w−1 =G ε
if and only if w represents an element of the subgroup A in the domain of
ψ. Hence this solves subgroup membership as well, giving a contradiction.
Since G does not have solvable word problem, this stackable group G cannot
be algorithmically stackable.


5.2. Dehn functions for algorithmic stackability: Hydra groups.
In our second application, we show that Dehn functions of algorithmically
stackable groups can be extremely large.
Theorem 5.2. The class of algorithmically stackable groups includes groups
with Dehn functions in each level of the Grzegorczyk hierarchy of primitive
recursive functions.
Proof. Dison and Riley [12] defined a family of groups Γk (for k ≥ 2), built
by HNN extensions, and showed that the Dehn function of Γk is equivalent
to the k-th Ackerman function. In particular, for each integer k ≥ 2, the
group Γk = Gk ∗ψk is an HNN extension of a free-by-cyclic group
Gk = ha1 , ..., ak , t | ta1 t−1 = a1 , tai t−1 = ai ai−1 (i > 1)i
(known as a hydra group) with respect to the identity map ψK : Hk → Hk on
the finitely generated (rank k free) subgroup Hk = ha1 t−1 , ..., ak t−1 i. Since
the class of algorithmically stackable groups is closed under extension [8],
the group Gk is algorithmically stackable. Theorem 4.4 shows that Γk is
also stackable. Dison, Einstein and Riley [11, Theorem 3] have shown that
for the subgroup Hk of Gk , the subgroup membership problem is decidable.
Then Corollary 4.7 shows that Γk is also algorithmically stackable.


18

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

5.3. Dehn functions for autostackability: Baumslag’s nonmetabelian
group. In this third application we consider Baumslag’s nonmetabelian
group, also known as the Baumslag-Gersten group, which is presented by
G = ha, s | (sas−1 )a(sa−1 s−1 ) = a2 i = ha, t, s | tat−1 = a2 , sas−1 = ti.
This group can be realized as an HNN extension G = H∗ψ where H is the
Baumslag-Solitar group H = BS(1, 2) = ha, t | tat−1 = a2 i and ψ : hai → hti
is the map given by ψ(a) = t. The group H is autostackable [6, 7], and so
Theorem 4.4 shows that G is stackable. We strengthen this result to show
the following.
Theorem 5.3. Baumslag’s nonmetabelian group ha, s | (sas−1 )a(sa−1 s−1 ) =
a2 i is autostackable.
Proof. The Baumslag-Solitar group H = ha, t | tat−1 = a2 i has a finite
complete rewriting system on the generating set Y = {a±1 , t±1 } given by
{aε a−ε → 1, tε t−ε → 1, a2 t → ta, a−1 t → ata−1 , aε t−1 → t−1 a2ε | ε ∈ {±1} },
and hence is autostackable [7]. The normal form set of this autostackable
structure is the regular language
NH

= [({1, a} · t, t−1 )∗ r ∪ε∈{±1} Y ∗ tε t−ε Y ∗ ](a∗ ∪ (a−1 )∗ )
= [(t−1 )∗ ∪ ((t−1 )∗ at ∪ 1)({1, a} · t)∗ ](a∗ ∪ (a−1 )∗ ).

(That is, H is an HNN extension of the infinite cyclic group hai by the
monomorphism hai → hai defined by a 7→ a2 , and NH is the associated set
of Britton normal forms.)
Let A = hai and B = hti, subgroups of H, and let ψ : A → B be the map
ψ(a) = t, so that G = H∗ψ . Then the generating set Z := {a±1 } for A and
its image ψ(Z) = {t±1 } are both subsets of the generating set Y of H.
By Corollary 4.6, it now suffices to show that there are regular transversals
for these subgroups such that each of the languages Lz and L′z̃ is regular.
Define
NH/A := (t−1 )∗ ∪ ((t−1 )∗ at ∪ 1)({1, a} · t)∗
∗

NH/B := a ∪ (a

−1 ∗

) ∪t

−1

(t

−1 ∗

2 ∗

) · (a(a ) ∪ a

and
−1

(a−2 )∗ ).

Then NH/A and NH/B are subsets of NH (each containing 1) that are
transversals for A and B in H, respectively. We note that NH/A and NH/B
are built from finite sets using unions, concatentations, and Kleene star, and
so both of these sets are also regular languages.
The set of shortlex normal forms for elements of the subgroup A over the
generating set Z is SLA = a∗ ∪ (a−1 )∗ , and similarly the shortlext normal
forms for B over ψ(Z) is SLB = t∗ ∪ (t−1 )∗ .

HNN EXTENSIONS AND STACKABLE GROUPS

19

Let z ∈ Z. Then z = aε for some ε ∈ {±1}. Since NH = NH/A SLA , the
language Laε satisfies
Laε

= {w ∈ NH | w =H transA (w)subA (w) for some transA (w) ∈ NH/A
and subA (w) = aεi with i > 0}
= N H ∩ Y ∗ aε .

Then Laε is an intersection of regular languages, and hence is also regular.
Next, for z̃ ∈ ψ(Z), we have z̃ = tε with ε ∈ {±1}. Suppose first that
ε = 1. Then
L′t = {w ∈ NH | w =H transB (w)subB (w) for some transB (w) ∈ NH/ψ(A)
and sub(w) = tk with k > 0}.
Suppose that w ∈ NH ∩ Y ∗ tY ∗ ; that is, w ∈ ((t−1 )∗ at ∪ t)({1, a} · t)∗ ](a∗ ∪
(a−1 )∗ ). Then either w = t−i ataε1 · · · taεk taℓ , or w = taε1 · · · taεk taℓ for some
k
k+1
i, k ≥ 0, εi ∈ {0, 1} and ℓ ∈ Z. Hence either transB (w) = t−i a1+2ε1 +···+2 εk +2 ℓ
k
k+1
or transB (w) = a2ε1 +···+2 εk +2 ℓ (respectively), and subB (w) = tk+1 . Since
k ≥ 0, then last(sub(w)) = t, and so w ∈ L′t . Hence L′t ⊇ NH ∩ Y ∗ tY ∗ . On
the other hand, for any v ∈ L′t , we have v = nf(aj tk ) or v = nf(t−i a2j+1 tk )
for some i ≥ 0, j ∈ Z, and k > 0. Applying the rules of the rewriting system
above, then the normal form v must contain the letter t. That is,
L′t = NH ∩ Y ∗ tY ∗
and therefore this set is a regular language.
Finally we consider the set
L′t−1

= {w ∈ NH | w =H transB (w)subB (w) for some transB (w) ∈ NH/ψ(A)
and sub(w) = t−i with i > 0}.

In this case we have
L′t−1 = NH r (NH/B ∪ L′t ) = t−1 (t−1 )∗ ((a2 )∗ ∪ (a−2 )∗ ),
and so L′t−1 is also regular.
Corollary 4.6 now shows that G is autostackable.



The following Corollary is now immediate from Theorem 5.3 and Platonov’s
proof that the Dehn function of Baumslag’s nonmetabelian group is not elementary [18].
Corollary 5.4. The class of autostackable groups includes groups with nonelementary Dehn functions.
6. Autostackable metabelian groups
In this section we consider an infinite family of nonconstructible metabelian
groups. Let p ∈ {n ∈ Z | n ≥ 2} ∪ {∞}, and let
Gp = ha, s, t | ap = 1, [at , a] = 1, as = at a, [s, t] = 1i,
where the case p = ∞ means that no relation ap = 1 occurs. The group G∞
is Baumslag’s metabelian group, which is introduced in [3], and for p < ∞,

20

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

the torsion analog Gp of Baumslag’s metabelian group is the Diestel-Leader
group Γ3 (p) (which is also metabelian). Our objective in this section is to
show in Theorem 6.1 that G∞ is algorithmically stackable and the groups
Gp for p < ∞ are autostackable.
We begin with a description of the subgroup structure of Gp , following [3].
Let Hp be the subgroup of Gp generated by Y = {a±1 , t±1 }. In his paper [3],
Baumslag showed that a consequence of the relations in the presentation
j
i
above of G∞ is that [at , at ] = 1 for all i, j ∈ Z. Moreover
i

j

Hp = ha, t | [at , at ] = 1 for all i, j ∈ Z, ap = 1i
M

hti at−i i ⋊ hti,
=
i∈Z

where
is isomorphic to Zp for each i, hti ∼
= Z, and t acts on
L
i
−i
ht
at
i
conjugating
the
i-th
summand
to
the
(i + 1)-th summand;
i∈Z
that is, Hp is the (restricted) wreath product Hp = Zp ≀ Z. (In the case
that p = 2, the group H2 is also known as the lamplighter group.) Let
ψ : Hp → hat a, ti ≤ Hp be the map defined by ψ(a) = at a and ψ(t) = t;
then the group Gp is the HNN extension Gp = Hp ∗ψp , and the generator s
of Gp is the corresponding stable letter.
The crucial difference with Theorem 4.4 is that in this case the group Hp
is not finitely presentable, so Hp cannot have a stackable structure. Despite
this, there are some analogies between the proofs of Theorems 4.4 and 6.1; in
particular, the Britton set of normal forms are used for the HNN extensions
in both.
In order to describe the normal form set for Gp , and to streamline other
parts of the proof of Theorem 6.1, we also make use of an another way
toLview the elements
of this group. Using the isomorphism ρ̂ between

1
i1 β1 −i1 ) · · · (tin aβn t−in )) := β xi1 +
i
−i
1
i∈Z ht at i and Zp [x, x ] given by ρ̂((t a t
i
n
· · · + βn x , there are isomorphisms
b p := Zp [x, 1 ] ⋊ ht̂i
and
ρ̂ : Hp → H
x

bp := Zp [x, 1 ] ⋊ ht̂i ∗
ρ̂ : Gp → G
ψ̂
x
(with ρ̂(t) := t̂ and ρ̂(s) := ŝ) where the conjugation action of t̂ on Zp [x, x1 ]
is multiplication by x, and the map ψ̂ : Hp → h1 + xi ⋊ ht̂i is defined by
ψ̂(x0 ) := 1 + x and ψ̂(t̂) := t̂; that is, the conjugation action by the stable
b p is given by multiplication by 1 + x on the Zp [x, 1 ] subgroup
letter ŝ on H
x
and fixes t̂.
hti at−i i

Theorem 6.1. Baumslag’s metabelian group G∞ = ha, s, t | as = at a, [at , a] =
1, [s, t] = 1i is algorithmically stackable, and the Diestel-Leader torsion
analogs Gp = ha, s, t | as = at a, [at , a] = 1, [s, t] = 1, ap = 1i with p ≥ 2
are autostackable.
Proof. Although we cannot directly apply Theorem 4.4, we will use roughly
the same ingredients in order to build a stacking system for the group Gp .

HNN EXTENSIONS AND STACKABLE GROUPS

21

Consider the inverse closed generating set
X = {a±1 , s±1 , t±1 }
for Gp .
Step I. Normal forms and notation:
In order to build a set of normal forms for the group Hp , we use the
b p , and note that an arbitrary element of H
b p can be
isomorphism Hp ∼
= H
1
m
written uniquely in the form p(x)t̂ where p(x) ∈ Zp [x, x ] and m ∈ Z. Let
NHp := {tm | m ∈ Z} ∪
{tr aαr taαr+1 . . . taαl t−l+m | r, l, m ∈ Z, r ≤ l, αi ∈ Zp for r ≤ i ≤ l,
and αr , αl 6= 0};
here (and throughout this proof) we write αi ∈ Zp to mean that αi ∈ Z
in the case that p = ∞, and αi ∈ {0, 1, ..., p − 1} if p is finite. Then the
bp
restriction of the map ρ̂ to the set NHp gives a bijection ρ : NHp → H
defined by ρ(tm ) := t̂m and
ρ(tr aαr taαr+1 . . . taαl t−l+m ) := (αr xr + αr+1 xr+1 + · · · + αl xl )t̂m ,
where the integers r and l are the lowest and highest degrees in the polynomial in the Zp [x, x1 ] subgroup, respectively, and hence NHp is a set of normal
forms for Hp .
The HNN extension Gp = Hp ∗ψ is strictly ascending, in that the isomorphism ψ : A → B of subgroups of Hp maps the full group A = Hp to the
proper subgroup B = hat a, ti. The set NH/A := {1} ⊆ NHp is a transversal
for H/A. Under the map ρ̂ the subgroup B is isomorphic to the split extension by Z = ht̂i of the ideal I of Zp [x, 1/x] generated by 1 + x. This implies
that
1
H/B ∼
= Zp ,
= Zp [x, ]/I ∼
x
and the set
NH/B := {aβ | β ∈ Zp }
is a set of normal forms of a set of representatives of the cosets of B in H.
The corresponding Britton normal form set for the HNN extension Gp is
given by
N Gp

:= {s−k aβ1 saβ2 s . . . saβn sh | k, n ≥ 0, βi ∈ Zp for 1 ≤ i ≤ n,
β1 6= 0 if both k > 0 and n > 0, and h ∈ NHp }.

Given such a word u = s−k aβ1 saβ2 s . . . saβn sh ∈ NGp , as in Notation 4.1
we denote the tail and head of u as tl(u) := s−k aβ1 saβ2 s . . . saβn s and
hd(u) := h, respectively. Moreover, let pu (x) ∈ Zp [x, x1 ] and mu ∈ Z be
defined by pu = 0 and ρ(hd(u)) = t̂mu in the case that hd(u) is a power of
t, and ρ(hd(u)) = pu (x)t̂mu otherwise. Also in the latter case let ru and lu
denote the lowest and highest degrees, respectively, of monomials in pu (x).

22

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

Let αru ,u , ..., αlu ,u (or αru , ..., αlu when there is no ambiguity) denote the respective coefficients in the Laurent polynomial pu . In the case that pu 6= 0,
note that αlu ,u 6= 0; in the remainder of this proof, αlu ,u = 0 implies the
opposite case that pu = 0.
For all w ∈ X ∗ , let nf(w) denote the normal form in NGp of the element
of Gp represented by w. We note that the language NGp is prefix-closed.
~ and P~ be the
Let Γ := Γ(Gp , X) be the Cayley graph for Gp over X, let E
sets of directed edges and directed paths in Γ, and let T be the maximal
tree of Γ corresponding to the set NGp . For all u ∈ NGp and z ∈ X, let eu,z
denote the directed edge in Γ labeled by z with initial vertex labeled by the
element of Gp represented by u.
Step II. The stackable system of fully NGp -triangular van Kampen diagrams
for p < ∞:
In this part of the proof we prove that Gp is stackable over X in the
case when p is finite. (The case that p = ∞ is similar, and is discussed in
Step IV.)
We obtain the stackable structure by applying Proposition 3.5 and showing that over the finite presentation
Gp = ha, s, t | ap = 1, [at , a] = 1, [s, t] = 1, saα s−1 = taα t−1 aα ,
saα ts−1 = aα taα (α ∈ {1, ..., p − 1}) i,
there is a fully NGp -triangular van Kampen diagram ∆u,z with boundary
label uznf(uz)−1 for every normal form word u ∈ NGp and generator z ∈ X.
We proceed via several cases depending upon u and z; in each case, we have
that fully NGp -triangular van Kampen diagrams have been constructed for
the prior cases. Also in each case we record the corresponding function
~ → P~ on the edge eu,z , and the algorithm to compute this function.
Φ:E
Case 1: Suppose that z = t±1 . In this case, either the word ut±1 is in
normal form, or else the word u ends with the letter t±1 . Thus there is
a degenerate (and hence fully NGp -triangular) van Kampen diagram ∆u,z
with boundary label uznf(uz)−1 , and Φ(eu,z ) := eu,z .
Case 2: Suppose that z = a±1 and either pu (x) = 0 or both pu (x) 6= 0 and
mu − lu ≥ 0.
Case 2.1: Suppose further that pu (x) 6= 0 and mu − lu = 0. Then the word
u ends with the suffix aαlu with αlu > 0, and the last letter of u is a. If
z = a−1 , then the normal form of the word uz is the prefix u′ of u satisfying
u = u′ a. Thus again there is a degenerate diagram ∆u,z , and Φ(eu,z ) := eu,z .
On the other hand, if z = a and αlu < p − 1, then again the word uz is in
normal form, giving a degenerate diagram ∆u,z and Φ(eu,z ) := eu,z . Finally,
if z = a and αlu = p − 1, we can factor u = u′ ap−1 for some u′ ∈ NGp , and
so there is a minimal diagram ∆u,z = u′ ∆ap−1 ,a with a single 2-cell ∆ap−1 ,a
with boundary label ap ; in this case, Φ(eu,z ) := path(u, a−(p−1) ).

HNN EXTENSIONS AND STACKABLE GROUPS

23

Case 2.2: Suppose further that either pu (x) = 0 or both pu (x) 6= 0 and
mu − lu > 0. That is, either hd(u) = tmu , or hd(u) contains the letter a
and ends with the letter t. If z = a then the word uz is in normal form and
there is a degenerate diagram ∆u,z ; thus Φ(eu,z ) := eu,z . If z = a−1 , then
nf(uz) = uap−1 and there is a minimal diagram ∆u,z = u∆1,a−1 with a single
2-cell ∆1,a−1 with boundary label ap ; in this case, Φ(eu,z ) := path(u, ap−1 ).
Case 3: Suppose that z = a±1 , pu (x) 6= 0, and mu − lu = −1. Define
δ ∈ {±1} by z = aδ . We begin the construction of the fully NGp -triangular
van Kampen diagram ∆u,z with an isolated cell with one edge labeled z, and
the remaining boundary path in the other direction labeled ta−1 t−1 aδ tat−1 ;
that is, we take Φ(eu,z ) := path(u, ta−1 t−1 aδ tat−1 ). By case 1, we already
have fully NGp -triangular diagrams ∆u,t, ∆nf(uta−1 ),t−1 , ∆nf(uta−1 t−1 aδ ),t , and
∆nf(uta−1 t−1 aδ ta),t−1 . Hence in order to show that we can complete this to a
fully NGp -triangular diagram, it suffices to check that fully NGp -triangular
diagrams have already been constructed for the pairs (u1 , a−1 ), (u2 , aδ ), and
(u3 , a) where u1 = nf(ut), u2 = nf(uta−1 t−1 ), and u3 = nf(uta−1 t−1 aδ t).
Note that the word u ends with the suffix at−1 . The word u1 is the prefix
of u with the last letter t−1 removed, and so u1 ∈ NGp and u1 ends with the
letter a. Hence ∆u1 ,a−1 was built in case 2.1.
We prove that ∆u2 ,aδ has already been constructed by induction on αlu ,u
(and a prior case). The normal form u2 is obtained from u by removing the
last and next-to-last letters at−1 , and possibly free reduction (in the case
that αlu ,u = 1 and either lu > ru or lu = ru > 0); then either (hd(u2 ) = tru −1
and αlu2 ,u2 = 0), or (hd(u2 ) contains the letter a and mu2 − lu2 = 0), or
(hd(u2 ) contains the letter a, mu2 − lu2 = −1 and αlu2 ,u2 < αlu ,u ). Hence
the construction of ∆u2 ,aδ follows from case 2 or induction.
Writing u = tl(u)tru aαru ,u · · · taαlu ,u t−1 , we have
u3 = G p

tl(u)tru aαru ,u · · · taαlu ,u −1 t−1 aδ t

= Gp

tl(u)(tru aαru ,u t−ru ) · · · (tlu aαlu ,u −1 t−lu )(tlu −1 aδ t−(lu −1) )tlu

= Gp

tl(u)(tru aαru ,u t−ru ) · · · (tlu −1 aαlu −1,u +δ t−(lu −1) )(tlu aαlu ,u −1 t−lu )tlu .

Using the polynomial viewpoint, pu3 (x) = pu (x) + δxlu −1 − xlu . Now either
hd(u3 ) = tmu3 (if pu3 = 0), or mu3 − lu3 ≥ 0 (otherwise); hence ∆u3 ,a was
also constructed in case 2.
Case 4: Suppose that z = s−1 and tl(u) does not have a suffix of the form
as. Either tl(u) = s−k or tl(u) = s or tl(u) ends with s2 ; the property that we
exploit in this case is that for all of these options, we have tl(nf(tl(u)s−1 h)) =
nf(tl(u)s−1 ) and hd(nf(tl(u)s−1 h)) = nf(h) for all h ∈ {a±1 , t±1 }∗ . We
proceed by induction on the length l(hd(u)) of the head of u.
Suppose first that l(hd(u)) = 0. Since u = tl(u), either u = s−k (with
k ≤ 0), u = s, or u ends with s2 . In all three of these options, either
nf(us−1 ) = us−1 or nf(us−1 ) is the prefix of u obtained from u by removing
a final letter s. Hence there is a degenerate diagram ∆u,z , and we set
Φ(eu,z ) := eu,z .

24

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

Now suppose that l(hd(u)) > 0, and write u = u′ z ′ where z ′ ∈ {a, t±1 }.
If z ′ = tδ with δ ∈ {±1}, then we begin the construction of the fully
NGp -triangular van Kampen diagram ∆u,z with an isolated cell with one
edge labeled z, and the remaining boundary path in the other direction
labeled t−δ s−1 tδ , and hence set Φ(eu,z ) := path(u, t−δ s−1 tδ ). Now fully NGp triangular van Kampen diagrams ∆u,t−δ and ∆nf(ut−δ s−1 ),tδ are constructed
in case 1, and since nf(ut−δ ) = u′ satisfies l(u′ ) = l(u) − 1, the diagram
∆nf(ut−δ ),s−1 has been built by induction.
On the other hand if z ′ = a, we build ∆u,z starting with an isolated cell
with one edge labeled z, and the remaining boundary path in the other
direction labeled a−1 s−1 atat−1 , and so Φ(eu,z ) := path(u, a−1 s−1 atat−1 ).
As usual, the required fully NGp -triangular subdiagrams with isolated edges
labeled by t±1 have been built in case 1, and the degenerate diagram ∆u,a−1
is given in case 2.1. Since nf(ua−1 ) = u′ is a prefix of u, we again have built
the diagram ∆nf(ua−1 ),s−1 by induction. So it suffices to show that fully
NGp -triangular van Kampen diagrams have been built for the pairs (u1 , a),
and (u2 , a), where u1 = nf(ua−1 s−1 ) and u2 = nf(ua−1 s−1 at).
Since the last letter of u is z ′ = a, we can write u = tl(u)tru aαru ,u · · · taαlu ,u
where αlu ,u > 0. Now
u1 = G p
= Gp

tl(u)s−1 [s(tru aαru ,u · · · taαlu ,u −1 )s−1 ]
tl(u)s−1 [s(tru aαru ,u t−ru ) · · · (tlu aαlu ,u −1 t−lu )s−1 ]tlu

satisfies tl(u1 ) = nf(tl(u)s−1 ) and
hd(u1 ) = nf([s(tru aαru ,u t−ru ) · · · (tlu aαlu ,u −1 t−lu )s−1 ]tlu )
(applying the property noted at the start of case 4). Recall that in the
polynomial view, conjugation by ŝ results in multiplication by 1 + x, and
so pu1 (x) = [pu (x) − xlu ](1 + x) and ρ(hd(u1 )) = pu1 (x)tlu . The polynomial
pu1 (x) has degree lu1 that is at most lu + 1, and so mu1 − lu1 ≥ lu − (lu + 1) =
−1. Hence the pair (u1 , a) satisfies the hypotheses of case 2 or 3, and the
diagram ∆u1 ,a is constructed in one of those cases.
Finally we consider
u2 =Gp
= Gp

tl(u)s−1 [s(tru aαru ,u · · · taαlu ,u −1 )s−1 ]at
tl(u)s−1 [s(tru aαru ,u t−ru ) · · · (tlu aαlu ,u −1 t−lu )s−1 ](tlu at−lu )tlu +1 .

Again using the polynomial viewpoint, we have pu2 (x) = [pu (x) − xlu ](1 +
x) + xlu , which also has degree lu2 ≤ lu + 1, and mu2 = lu + 1, and so
mu2 − lu2 ≥ 0. Hence the diagram ∆u1 ,a is constructed in case 2.
Case 5: Suppose that z = s and hd(u) ∈ Im ψ. Similar to the situation
in case 4, a property that we exploit in this case is that tl(nf(tl(u)sh)) =
nf(tl(u)s) and hd(nf(tl(u)sh)) = nf(h) for all h ∈ {a±1 , t±1 }∗ .
Observe that hd(u) ∈ Imψ implies that pu (x) = qu (x)(1 + x) for some
qu (x) ∈ Zp [x, x1 ] that can be written in the form
qu (x) = γru ,u xru + · · · + γlu −1,u xlu −1

HNN EXTENSIONS AND STACKABLE GROUPS

25

with each γi,u ∈ Zp , and γlu −1,u = αlu ,u .
We proceed by induction on the number occt (u) of occurrences of t±1 in
the word hd(u). Since x + 1 divides pu (x), the polynomial pu (x) cannot be
a single monomial, and so either pu (x) = 0 or |lu − ru | > 0.
First suppose that occt (u) = 0. Since pu (x) is not a single monomial,
hd(u) cannot be a nontrivial power of a, and so hd(u) = 1 and u = tl(u). The
normal form nf(us) is either us or the word u with a final letter s−1 removed.
In this case there is a degenerate diagram ∆u,z , and we set Φ(eu,z ) := eu,z .
Now suppose that occt (u) > 0, and write u = u′ z ′ with u′ ∈ NGp and
z ′ ∈ {a, t±1 }.
If z ′ = tδ with δ ∈ {t±1 }, then as in case 4 we begin the diagram ∆u,z with
an isolated cell labeled by zt−δ s−1 tδ and set Φ(eu,z ) := path(u, t−δ stδ ). The
required fully NGp -triangular diagrams with isolated edges labeled t±1 are
constructed in case 1, and since nf(ut−δ ) = u′ satisfies occt (u′ ) = occt (u) −
1 < occt (u), the diagram ∆u′ ,z has already been built by induction.
Suppose instead that z ′ = a. Now u = tl(u)u′′ tδ aαlu ,u for some δ ∈ {±1},
′′
u ∈ NHp , and αlu ,u > 0. Recall that we are considering the case that p < ∞
in Step II, and so αlu ,u ∈ {1, 2, ..., p − 1}. Again using the fact that pu (x) is
not a single monomial, the exponent δ must be 1, and the word u′′ ∈ NHp
contains an occurrence of the letter a and ends either with a or t.
We build ∆u,z with an isolated cell labeled zt−1 a−αlu ,u s−1 aαlu ,u taαlu ,u ;
then Φ(eu,z ) = path(u, a−αlu ,u t−1 a−αlu ,u saαlu ,u t). For all 0 ≤ i ≤ αlu ,u −
1, there is a degenerate diagram ∆ua−i ,a−1 from case 2.1, and by case 1
it remains to show that we have built fully NGp -triangular diagrams associated to the pairs (u1,i , a−1 ), (u2 , s), and (u3,i , a) for 0 ≤ i < αlu ,u ,
where u1,i = nf(ua−αlu ,u t−1 a−i ), u2 = nf(ua−αlu ,u t−1 a−αlu ,u ), and u3,i =
nf(ua−αlu ,u t−1 a−αlu ,u sai ).
Using the factorization of u above, u1,i = nf(tl(u)u′′ a−i ); writing u′′ =
u′′′ aj (with 0 ≤ j ≤ p − 1), then u1,i = tl(u)u′′′ aj̃ where j̃ ∈ {0, ..., p − 1}
and j̃ ≡ j − i (mod p). This normal form u1,i satisfies either pu1,i (x) = 0,
or else pu1,i 6= 0 and mu1,i − lu1,i ≥ 0, and so the diagram ∆u1,i ,a−1 has been
constructed in case 2.
An analysis of the normal form u2 = nf(ua−αlu ,u t−1 a−αlu ,u ) yields
u2 = G p
= Gp

tl(u)tru aαru ,u · · · taαlu ,u a−αlu ,u t−1 a−αlu ,u
tl(u)[(tru aαru ,u t−ru ) · · · (tlu aαlu ,u t−lu )][(tlu a−αlu ,u t−(lu ) )(tlu −1 a−αlu ,u t−(lu −1) )]tlu −1 .

Then pu2 = pu − αlu ,u xlu −1 (x + 1), and so hd(u2 ) ∈ Im ψ. Hence the pair
(u2 , s) satisfies the properties of case 5. Moreover, since
u2 = nf(tl(u)u′′ a−αlu ,u ) = nf(tl(u)u′′′ aj a−αlu ,u ) = tl(u)u′′′ aj̃
where j̃ ∈ {0, ..., p−1} and j̃ ≡ j−αlu ,u (mod p), the normal form u2 satisfies
occt (u2 ) = occt (u) − 1 < occt (u), and the diagram ∆u2 ,s has already been
built by induction.

26

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

Finally we note that
u3,i =Gp
= Gp

u2 sai
tl(u)s[s−1 (tru aαru ,u t−ru ) · · · (tlu −1 aαlu −1,u −αlu ,u t−(lu −1) )s](tlu −1 ai t−(lu −1) )tlu −1 ,

and so (using the property noted at the beginning of case 5) tl(u3,i ) =
nf(tl(u)s) and
hd(u3,i ) = nf([s−1 (tru aαru ,u t−ru ) · · · (tlu −1 aαlu −1,u −αlu ,u t−(lu −1) )s](tlu −1 ai t−(lu −1) )tlu −1 ).
In the polynomial viewpoint, the conjugation action of ŝ−1 on the element
pu2 = pu − αlu ,u xlu −1 (x + 1) of Im ψ̂ is division by 1 + x, and so
[s−1 (tru aαru ,u t−ru ) · · · (tlu −1 aαlu −1,u −αlu ,u t−(lu −1) )s] =Gp ρ−1 (qu −αlu ,u xlu −1 ).
That is, pu3,i = qu −αlu ,u xlu −1 +ixlu −1 . Now either pu3,i = 0 (in the case that
i = 0 and pu = αlu ,u xlu −1 (x + 1)) or else pu3,i 6= 0 and lu3,i ≤ lu − 1 = mu3,i
(and so mu3,i − lu3,i ≥ 0). Thus the diagram ∆u3,i ,a is constructed in case 2.
Case 6: Suppose that z = a±1 , pu (x) 6= 0, and mu − lu < −1. Write z = aδ .
Pu
αi,u xi can be written
The Laurent polynomial pu (x) = li=r
u
pu (x) = qu (x)(1 + x) + Ru
for some Laurent polynomial qu (x) ∈ Zp [x, x1 ] and Ru ∈ Zp . (More specifically, set Ru = pu (−1) and let qu (x) ∈ Zp [x, x1 ] be the Laurent polynomial
such that pu (x) − Rp = qu (x)(x + 1) which can be found by multiplying
pu (x) − Rp by a suitable power of x and then applying the Euclidean algorithm). Define
dδ (u) = (d1,δ (u), d2,δ (u)) := (|mu −lu |, Ru −δ(−1)mu +1 ) ∈ {i ∈ N | i ≥ 2}×{0, ..., p−1},
where we consider the element Ru − δ(−1)mu +1 of Zp to be an integer in
{0, ..., p − 1} ⊂ N0 .
Consider the lexicographic ordering ≺ on {i ∈ N | i ≥ 2} × {0, ..., p − 1} ⊂
N × N0 (that is, (i1 , i2 ) ≺ (j1 , j2 ) whenever either i1 < j1 or else both i1 = j1
and i2 < j2 ); this is a well-founded strict partial ordering. We proceed by
(Noetherian) induction on this ordering on dδ (u).
For the base case, suppose that dδ (u) = (2, 0). Then mu − lu = −2 and
pu (−1) − δ(−1)mu +1 = 0. We begin the diagram ∆u,z with an isolated cell
with an isolated edge labeled z, and edge path in the other direction labeled
ta−δ t−1 saδ s−1 ; that is, Φ(eu,z ) := path(u, ta−δ t−1 saδ s−1 ). The subdiagrams
∆u,t and ∆nf(uta−δ ),t−1 are constructed in case 1, and so there are four remaining subdiagrams needed to build ∆u,z that we need to show have already
been constructed: ∆u1 ,a−δ , ∆u2 ,s , ∆u3 ,aδ , and ∆u4 ,s−1 , where u1 = nf(ut),
u2 = nf(uta−δ t−1 ), u3 = nf(uta−δ t−1 s), and u4 = nf(uta−δ t−1 saδ ).
Since u1 := nf(ut) satisfies mu1 − lu1 = −1, the diagram ∆nf(ut),a−δ is
built in case 3.

HNN EXTENSIONS AND STACKABLE GROUPS

27

The normal form u2 := nf(uta−δ t−1 ) satisfies
u2 =Gp
= Gp

tl(u)(tru aαru ,u t−ru ) · · · (tlu aαlu ,u t−lu )tmu ta−δ t−1
tl(u)(tru aαru ,u t−ru ) · · · (tlu aαlu ,u t−lu )(tmu +1 a−δ t−(mu +1) )tmu

and so pu2 (x) = pu (x) − δxmu +1 . Now pu2 (−1) = pu (−1) − δ(−1)mu +1 =
d2,δ (u) = 0. Then 1 + x divides the Laurent polynomial pu2 ; that is, pu2 is
in the ideal of Zp [x, x1 ] generated by 1 + x, and applying the isomorphism ρ̂
shows that hd(u2 ) ∈ Im ψ. Hence the diagram ∆u2 ,s is built in case 5.
Next u3 = nf(uta−δ t−1 s) = nf(u2 s) satisfies
u3 = G p

tl(u)(tru aαru ,u t−ru ) · · · (tlu aαlu ,u t−lu )(tmu +1 a−δ t−(mu +1) )tmu s

u3 = G p

tl(u)s[s−1 (tru aαru ,u t−ru ) · · · (tlu aαlu ,u t−lu )(tmu +1 a−δ t−(mu +1) )s]tmu .

As in case 5, we note that tl(u3 ) = nf(tl(u)s), and so the normal form of
the rest of the expression to the right of tl(u)s is the head of u3 . Then
pu3 (x) = (pu (x) − δxmu +1 )/(x + 1); since mu + 1 < lu , the polynomial pu3
has degree lu3 = lu − 1. Since mu3 = mu , then mu3 − lu3 = mu − lu + 1 = −1,
and again we apply case 3 to show that the diagram ∆u3 ,aδ has already been
constructed.
Now u4 = nf(u3 aδ ) satisfies
u4 =Gp tl(u)s[s−1 (tru aαru ,u t−ru ) · · · (tlu aαlu ,u t−lu )(tmu +1 a−δ t−(mu +1) )s][tmu aδ t−mu ]tmu .
Then again tl(u4 ) = nf(tl(u)s), and so either tl(u4 ) is a power of s±1 or ends
with s2 , but tl(u4 ) cannot end with as. Hence ∆u4 ,s−1 is constructed in
case 4.
For the inductive step, suppose that dδ (u) ≻ (2, 0).
Suppose further that d2,δ (u) = 0 (and hence d1,δ (u) = |mu − lu | >
2). We follow nearly the same proof as in the dδ (u) = (2, 0) (base) case
above; the isolated cell of ∆u,z is labeled zsa−δ s−1 taδ t−1 , and Φ(eu,z ) :=
path(u, ta−δ t−1 saδ s−1 ). The only differences with the proof of that base
case is that the applications of case 3 are replaced with induction. In particular, u1 satisfies mu1 − lu1 = mu − lu + 1, implying that d1,δ (u1 ) =
|mu1 − lu1 | = |mu − lu | + 1 < |mu − lu | = d1,δ (u), and so dδ (u1 ) ≺ dδ (u) and
the construction of ∆u1 ,a−δ follows from induction. Similarly the fact that
mu3 − lu3 = mu − lu + 1 implies that ∆u3 ,aδ is built by induction.
On the other hand suppose that d2,δ (u) > 0. (Here we have d1,δ (u) =
|mu − lu | ≥ 2.) Let
η := (−1)mu +1 .
The construction of ∆u,z begins with an isolated cell having isolated edge
labeled z, and edge path in the other direction labeled ta−η t−1 aδ taη t−1 then
Φ(eu,z ) := path(u, ta−η t−1 aδ taη t−1 ). Applying case 1 to obtain the required
(degenerate) diagrams with isolated edges labeled t±1 , we have left to check
whether the three fully NGp -triangular diagrams ∆u1 ,a−η , ∆ũ2 ,aδ and, ∆ũ3 ,aη
have already been constructed, where u1 = nf(ut), ũ2 = nf(uta−η t−1 ), and
ũ3 = nf(uta−η t−1 aδ t).

28

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

For the first of these, the arguments above show that |mu1 − lu1 | = |mu −
lu | − 1, and so dδ (u1 ) ≺ dδ (u); the construction of ∆u1 ,a−η follows from case
3 or induction.
Replacement of δ by η in the computation for u2 above shows that
ũ2 =Gp tl(u)(tru aαru ,u t−ru ) · · · (tlu aαlu ,u t−lu )(tmu +1 a−η t−(mu +1) )tmu
and pũ2 (x) = pu (x) − ηxmu +1 . Again using the fact that mu + 1 < lu , then
pũ2 (x) 6= 0, mũ2 = mu , and lũ2 = lu . We have d1,δ (ũ2 ) = d1,δ (u), and
Rũ2 = pũ2 (−1) = pu (−1) − η(−1)mu +1 = Ru − 1. Then
d2,δ (ũ2 ) = Rũ2 − δ(−1)mũ2 = Ru − 1 − δ(−1)mu = d2,δ (u) − 1 < d2,δ (u).
Therefore dδ (ũ2 ) ≺ dδ (u) and the construction of the diagram ∆ũ2 ,aδ follows
from induction.
Finally we consider
ũ3 =Gp
= Gp

tl(u)(tru aαru ,u t−ru ) · · · (tlu aαlu ,u t−lu )tmu ta−η t−1 aδ t
tl(u)(tru aαru ,u t−ru ) · · · (tlu aαlu ,u t−lu )(tmu +1 a−η t−(mu +1) )(tmu aδ t−mu )tmu +1 ,

which has associated polynomial pũ3 (x) = pu (x) − ηxmu +1 + δxmu . Here
mũ3 = mu + 1 and lũ3 = lu , and so d1,δ (ũ3 ) < d1,δ (u) and dδ (ũ2 ) ≺ dδ (u),
and so the construction of ∆ũ3 ,aη follows from induction.
Case 7: Suppose that z = s−1 and tl(u) has a suffix as. We proceed by
induction on the length l(hd(u)).
Suppose first that l(hd(u)) = 0. Then nf(us−1 ) = u′ , and so there is a
degenerate diagram ∆u,z and Φ(eu,z ) = eu,z .
Suppose next that l(hd(u)) > 0. Write u = u′ z ′ with u′ ∈ NGp and
′
z ∈ {a, t±1 }.
If z ′ = tδ with δ ∈ {t±1 }, the construction and inductive proof are identical to the z ′ = tδ subcase of case 4, with Φ(eu,z ) := path(u, t−δ stδ ).
On the other hand suppose that z ′ = a. We begin building ∆u,z with an
isolated cell labeled zta−1 t−1 a−1 sa; that is, Φ(eu, z) = path(u, a−1 s−1 atat−1 ).
Now case 1 provides fully NGp -triangular van Kampen diagrams ∆û,tδ and
cases 2,3, and 6 provide fully NGp -triangular van Kampen diagrams ∆û,aδ
for all û ∈ NGp and δ ∈ {±1}, yielding diagrams ∆u,a−1 , ∆nf(ua−1 s−1 ),a ,
∆nf(ua−1 s−1 a),t , ∆nf(ua−1 s−1 at),a , and ∆nf(ua−1 s−1 ata),t−1 . Since nf(ua−1 ) = u′
satisfies l(hd(u′ )) = l(hd(u)) − 1 < l(hd(u)), the diagram ∆nf(ua−1 ),s−1 has
also already been constructed, by induction.
Case 8: Suppose that z = s and hd(u) 6∈ Im ψ. As in case 5, we proceed by
induction on the number occt (u) of occurrences of t±1 in hd(u).
/
Suppose first that occt (u) = 0. Then hd(u) = aαlu , and since hd(u) ∈
Im ψ, then αlu > 0. In this case the word us is in normal form, and so we
have a degenerate diagram ∆u,z and Φ(eu,z ) = eu,z .
Now suppose that occt (u) > 0, and write u = u′ z ′ with u′ ∈ NGp and
z ′ ∈ {a, t±1 }.
If z ′ = tδ with δ ∈ {t±1 }, the construction of ∆u,z has isolated cell
labeled zt−δ s−1 tδ , with Φ(eu,z ) := path(u, t−δ stδ ). Since nf(ut−δ ) = u′

HNN EXTENSIONS AND STACKABLE GROUPS

29

satisfies occt (u′ ) = occt (u) − 1 < occt (u), the diagram ∆u′ ,z has already
been constructed by induction.
Suppose instead that z ′ = a. Now hd(u) = u′′ tδ aαlu for some δ ∈ {±1}
and u′′ ∈ NHp . Again we recall that p < ∞ in Step II, and so αlu ∈
{1, 2, ..., p − 1}.
If δ = 1, we build ∆u,z with an isolated cell labeled zt−1 a−αlu s−1 aαlu taαlu ;
then Φ(eu,z ) = path(u, a−αlu t−1 a−αlu saαlu t). Cases 1,2,3, and 6 provide
fully NGp -triangular van Kampen diagrams corresponding to the edges labeled t±1 and a±1 along the boundary of this isolated cell. Now the normal
form ũ := nf(ua−αlu t−1 a−αlu ) = nf(u′′ a−αlu ) is obtained from u′′ a−αlu by
possible reduction modulo p of a final power of a; then ũ satisfies occt (ũ) =
occt (u) − 1 < occt (u), and again induction applies to show that the diagram
∆ũ,s has already been constructed.
If δ = −1, we build ∆u,z with an isolated cell labeled za−αlu t−1 s−1 aαlu t−1 aαlu ;
then Φ(eu,z ) = path(u, a−αlu ta−αlu st−1 aαlu ). As before, cases 1,2,3, and 6
provide fully NGp -triangular van Kampen diagrams corresponding to the
edges labeled t±1 and a±1 . The normal form û := nf(ua−αlu ta−αlu ) =
u′′ a−αlu , and so occt (ũ) < occt (u). Once again induction applies to show
that the diagram ∆û,s has already been constructed, as required.
Step III. Autostackability of Gp for p < ∞:
In this section again we consider the p < ∞ case. Throughout this step
we will repeatedly apply the closure properties of regular and synchronously
regular languages discussed in Section 2.
Before analyzing the graph of the stacking map, we first discuss the set
NGp of normal forms. Let
Tail := {s−k aβ1 saβ2 s . . . saβn s | k, n ≥ 0, βi ∈ Zp for 1 ≤ i ≤ n,
and β1 6= 0 if both k > 0 and n > 0};
that is, Tail is the set of tails of elements of NGp . Then
Tail = (s−1 )∗ ({1, a, a2 , ..., ap−1 }s)∗ r X ∗ s−1 sX ∗
is built from finite subsets of X ∗ using concatenation, complement, and
Kleene star operations, and hence is a regular language. Similarly the normal
form set NHp for Hp can be written
NHp = (t∗ ∪(t−1 )∗ )({1, a, a2 , ..., ap−1 }t)∗ {1, a, a2 , ..., ap−1 }(t∗ ∪(t−1 )∗ )rX ∗ {tt−1 , t−1 t}X ∗
and so NHp is also regular. Finally the normal form set NGp is the concatenation NGp = Tail · NHp of these two regular languages, and therefore NGp
is also regular.
The stacking map associated to the flow function Φ in Step II of this proof
is given by
n
φ(u, z) := z if z = t±1

30

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

from case 1,

z





a−(p−1)





z




ap−1



ta−1 t−1 aδ tat−1
φ(u, z) :=

ta−δ t−1 saδ s−1









ta−η t−1 aδ taη t−1









= a and u ∈ Tail · (t−1 )∗ ∪ X ∗ t ∪ (X ∗ a r X ∗ ap−1 )
= a and u ∈ X ∗ ap−1
= a−1 and u ∈ X ∗ a
= a−1 and u ∈ Tail · (t−1 )∗ ∪ X ∗ t
= aδ , δ ∈ {±1}, and u ∈ X ∗ at−1
= aδ , δ ∈ {±1}, and u ∈ X ∗ aY ∗ t−2
and pu (−1) − δ(−1)mu +1 ≡ 0(mod p)
if z = aδ , δ ∈ {±1}, and u ∈ X ∗ aY ∗ t−2 ,
pu (−1) − δ(−1)mu +1 6≡ 0(mod p),
and η = (−1)mu +1

if
if
if
if
if
if

z
z
z
z
z
z

from cases 2,3, and 6 (where we recall that Y = {a±1 , t±1 }),


z
φ(u, z) := t−δ s−1 tδ

 −1 −1
a s atat−1

if z = s−1 and u ∈ Tail
if z = s−1 and u ∈ X ∗ tδ , δ ∈ {±1}
if z = s−1 and u ∈ X ∗ a

from cases 4 and 7, and

z



t−δ stδ
φ(u, z) :=

a−α t−1 a−α saα t


 −α −α −1 α
a ta st a

if
if
if
if

z
z
z
z

=s
=s
=s
=s

and
and
and
and

u ∈ Tail · a∗
u ∈ X ∗ tδ , δ ∈ {±1}
u ∈ X ∗ taα , α ∈ {1, ..., p − 1}
u ∈ X ∗ t−1 aα , α ∈ {1, ..., p − 1}

from cases 5 and 8. The graph graph(φ) of this function is a union of 15
languages, one for each of the pieces of this piecewise defined function. We
consider each of these languages in order.
The first language is L1 = ∪δ∈{±1} NGp × {tδ } × {tδ } (from case 1). Since
this is a product of regular languages, L1 is regular. The next five languages,
arising from cases 2 and 3, are
L2 = [NGp ∩ (Tail · (t−1 )∗ ∪ X ∗ t ∪ (X ∗ a r X ∗ ap−1 ))] × {a} × {a},
L3 = [NGp ∩ X ∗ ap−1 ] × {a} × {a−(p−1) },
L4 = [NGp ∩ X ∗ a] × {a−1 } × {a−1 },
L5 = [NGp ∩ Tail · (t−1 )∗ ∪ X ∗ t] × {a−1 } × {ap−1 },
∗

L6 = ∪δ∈{±1} [NGp ∩ X at

−1

δ

−1 −1 δ

] × {a } × {ta

t

a tat

and
−1

},

and regularity of NGp together with the closure properties show that all five
are synchronously regular. Similarly the last 7 languages, corresponding to

HNN EXTENSIONS AND STACKABLE GROUPS

31

the graph of the pieces of φ defined in cases 4,7,5, and 8, are
L9 = Tail × {s−1 } × {s−1 },
L10 = ∪δ∈{±1} [NGp ∩ X ∗ tδ ] × {s−1 } × {t−δ s−1 tδ },
L11 = [NGp ∩ X ∗ a] × {s−1 } × {a−1 s−1 atat−1 },
L12 = [Tail · a∗ ] × {s} × {s},
L13 = ∪δ∈{±1} [NGp ∩ X ∗ tδ ] × {s} × {t−δ stδ },
L14 = ∪α∈{1,...,p−1} [NGp ∩ X ∗ taα ] × {s} × {a−α t−1 a−α saα t},

and

L15 = ∪α∈{1,...,p−1} [NGp ∩ X ∗ t−1 aα ] × {s} × {a−α ta−α st−1 aα }.
Regularity of the languages Tail and NGp and closure properties also show
that these 7 languages are synchronously regular.
The remaining two subsets of graph(φ) arise from case 6, namely
L7 = ∪δ∈{±1} ∪η∈{±1} [X ∗ aY ∗ t−2 ∩ Tail · (Mη ∩ Nδ,η )]
×{aδ } × {ta−δ t−1 saδ s−1 } and
L8 = ∪δ∈{±1} ∪η∈{±1} [X ∗ aY ∗ t−2 ∩ Tail · (Mη ∩ (NHp r Nδ,η ))]
×{aδ } × {ta−η t−1 aδ taη t−1 },
where
Mη = {u ∈ NHp | (−1)mu +1 = η}, and
Nδ,η = {u ∈ NHp ∩ Y ∗ aY ∗ t−1 | pu (−1) ≡ δη(mod p)}.
In order to show that L7 and L8 are synchronously regular, it suffices to
show that the languages Mη and Nδ,η are regular.
For u ∈ NHp , the integer mu is the sum of the exponents of the letters
t±1 in u. That is, M1 is the set of words in NHp with t-exponent sum odd,
and M−1 is the set of words in NHp with t-exponent sum even. Let γ :
Y ∗ → Z/2 be the monoid homomorphism to the finite monoid Z/2 defined
by γ(a) = γ(a−1 ) = 0 and γ(t) = γ(t−1 ) = 1. The preimage sets γ −1 ({0})
and γ −1 ({1}) are regular sets (see Section 2). Then M1 = NHp ∩ γ −1 ({1})
and M−1 = NHp ∩γ −1 ({0}) are intersections of regular languages, and hence
Mη is regular for η ∈ {±1}.
Given any u ∈ NHp ∩Y ∗ aY ∗ t−1 , as usual we write pu (x) = αru ,u xru +· · ·+
αlu ,u xlu , where u = tru aαru ,u · · · taαlu ,u t−lu +mu . Then pu (−1) = (−1)ru (αru ,u +
· · ·+αlu ,u (−1)lu −ru . Splitting this into separate cases depending upon whether
ru is even or odd yields
eδ,η (t−1 )∗ ] ∪ [(t(t2 )∗ ∪ t−1 (t−2 )∗ )N
e−δ,η (t−1 )∗ ]
Nδ,η = [((t2 )∗ ∪ (t−2 )∗ )N

where
eδ,η := {aα0 taα1 · · · taαl t−1 | 0 ≤ l, αi ∈ {0, 1, ..., p − 1} for 0 ≤ i ≤ l,
N
α0 , αl 6= 0, and α0 − α1 + · · · + (−1)αl ≡ δη(mod p)}.
eδ,η is regular.
It now suffices to show that N

32

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

eδ,η is regular, we describe a finite state automaton
In order to show that N
(FSA) accepting this language. (We refer the reader to [10] and [15] for
details on the definition of a finite state automaton.) The alphabet of the
FSA is the set {a, t, t−1 }, and the set of states (i.e., the finite memory) of
the automaton is

Q = Zp × {y, n} × {±1} × Zp ∪ {I, F }.
The initial state is I, and the set of accept states is {δη} × {y} × {±1} × {0}.
The transition function d : Q×{a, t±1 } → Q, which determines the state that
the FSA moves to depending upon its current state and the next letter that
it reads, is defined by d(I, a) := (0, n, 1, 1), d(I, t±1 ) = F , d((i, n, µ, j), a) :=
(i, n, µ, j + 1) if 0 ≤ j < p − 1, d((i, n, µ, p − 1), a) := F , d((i, n, µ, j), t) :=
(i + µj(mod p), n, −µ, 0), d((i, n, µ, 0), t−1 ) := F , d((i, n, µ, j), t−1 ) := (i +
µj(mod p), y, −µ, 0) if 0 < j ≤ p−1, and d((i, y, µ, j), z) := F and d(F, z) :=
F for all z ∈ {a, t±1 }. That is, F is a “failure” state, and for the states
other than I, F , the first copy of Zp records the alternating sum α0 − α1 + ...
computed so far, the y/n records whether a t−1 letter has occurred, the ±1
records whether the current aαi word being read has (−1)i equal to 1 or -1,
and the final copy of Zp records the number of a letters that have been read
since the last occurrence of a letter t. A word u is accepted by this FSA
if and only if it starts with the letter a, contains no substring ap or tt−1 ,
ends with the letter t−1 but contains no other occurrence of that letter, and
eδ,η .
satisfies pu (−1) ≡ δη(mod p). This in turn holds iff u lies in N
We now have that all of the languages L1 , ..., L15 are synchronously regular. Therefore their union graph(φ) = ∪15
i=1 Li is also synchronously regular,
as required.

Step IV. Algorithmically stackable system of fully NGp -triangular van Kampen diagrams for p = ∞:
In this part of the proof we consider the case that p = ∞. The construction of the flow function can be done in a very similar way to the proofs in
earlier steps so we leave the details to the reader and just state the stacking
map that one gets over the finite presentation

G∞ = ha, s, t | ap = 1, [at , a] = 1, [s, t] = 1, sas−1 = tat−1 a, sats−1 = atai.

HNN EXTENSIONS AND STACKABLE GROUPS

φ(u, z) :=



z





z




ta−ε t−1 aδ taε t−1





ta−δ t−1 saδ s−1









ta−η t−1 aδ taη t−1














z




t−δ s−1 tδ




a−δ s−1 aδ taδ t−1




z





t−δ stδ




a−δ t−1 a−δ saδ t



a−δ ta−δ st−1 aδ

if
if
if
if

z
z
z
z

if z

if
if
if
if
if
if
if

z
z
z
z
z
z
z

33

= t±1
= a±1 and u ∈ Tail · (t−1 )∗ ∪ X ∗ t ∪ X ∗ a±1
= aδ , δ, ε ∈ {±1}, and u ∈ X ∗ aε t−1
= aδ , δ ∈ {±1}, and u ∈ X ∗ a±1 Y ∗ t−2
and pu (−1) − δ(−1)mu +1 = 0
= aδ , δ ∈ {±1}, and u ∈ X ∗ a±1 Y ∗ t−2 ,
pu (−1) − δ(−1)mu +1 6= 0
and η = (−1)mu +1 if pu (−1) − δ(−1)mu +1 > 0,
η = (−1)mu otherwise,
= s−1 and u ∈ Tail
= s−1 and u ∈ X ∗ tδ , δ ∈ {±1}
= s−1 and u ∈ X ∗ aδ , δ ∈ {±1}
= s and u ∈ Tail · (a∗ ∪ (a−1 )∗ )
= s and u ∈ X ∗ tδ , δ ∈ {±1}
= s and u ∈ X ∗ taδ (aδ )∗ , δ ∈ {±1}
= s and u ∈ X ∗ t−1 aδ (aδ )∗ , δ ∈ {±1}


As noted in Section 1, the following is immediate from Theorem 6.1.
Corollary 6.2. The class of autostackable groups contains nonconstructible
metabelian groups.
Acknowledgment
The first author was partially supported by grants from the National
Science Foundation (DMS-1313559) and the Simons Foundation (#245625)
and the second author was supported by Gobierno de Aragon, European
Regional Development Funds and MTM2015-67781-P.
References
[1] Bartholdi, L., Neuhauser, M., and Woess, W., Horocyclic products of trees,
J. Eur. Math. Soc. (JEMS) 10 (2008), 771–816.
[2] Baumslag, G., A non-cyclic one-relator group all of whose finite quotients are cyclic,
J. Austral. Math. Soc. 10 (1969), 497–498.
[3] Baumslag, G., A finitely presented metabelian group with a free abelian derived group
of infinite rank, Proc. Amer. Math. Soc. 35 (1972), 61–62.
[4] Bogopolski, O., and Ventura, E., A recursive presentation for Mihailova’s subgroup,
Groups Geom. Dyn. 4 (2010), 407–417.
[5] M. Brittenham and S. Hermiller, Tame filling invariants for groups, Internat. J. Algebra Comput. 25 (2015), 813–854.
[6] M. Brittenham and S. Hermiller, A uniform model for almost convexity and rewriting
systems, J. Group Theory 18 (2015), 805–828.
[7] M. Brittenham, S. Hermiller and D. Holt, Algorithms and topology for Cayley graphs
of groups, J. Algebra 415 (2014), 112–136.

34

S. HERMILLER AND C. MARTÍNEZ-PÉREZ

[8] M. Brittenham, S. Hermiller and A. Johnson, Homology and closure properties of
autostackable groups, J. Algebra 452 (2016), 596–617.
[9] M. Brittenham, S. Hermiller and T. Susse, Geometry of the word problem for 3manifold groups, preprint, 2016.
[10] Epstein, D.B.A., Cannon, J., Holt, D., Levy, S., Paterson, M. and Thurston, W.,
Word Processing in Groups, Jones and Bartlett, Boston, 1992.
[11] Dison, W., Einstein,, E., and Riley, T.R., Taming the hydra: the word problem and
extreme integer compression, arXiv:1509.02557.
[12] Dison, W. and Riley, T.R., Hydra groups, Comment. Math. Helv. 88 (2013), 507–540.
[13] Gersten, S.M., Dehn functions and ℓ1 -norms of finite presentations, in: Algorithms
and Classification in Combinatorial Group Theory, 195–225, Springer, Berlin, 1992.
[14] Groves, J.R.J. and Smith, G.C., Soluble groups with a finite rewriting system,
Proc. Edinburgh Math. Soc. 36 (1993), 283–288.
[15] Hopcroft, J. and Ullman, J.D., Introduction to automata theory, languages, and computation, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing
Co., Reading, Mass., 1979.
[16] Lyndon, R.C. and Schupp, P.E., Combinatorial group theory, Classics in Mathematics, Springer-Verlag, Berlin, 2001.
[17] Mihailova, K.A., The occurrence problem for direct products of groups,
Dokl. Acad. Nauk SSRR 119 (1958), 1103–1105.
[18] Platonov, A.N., An isoparametric function of the Baumslag-Gersten group, Vestnik Moskov. Univ. Ser. I Mat. Mekh. 2004, 12–17, 70; English. trans. Moscow
Univ. Math. Bull. 59 (2004), 12–17.
[19] Stein, M., Taback, J., and Wong, P., Automorphisms of higher rank lamplighter
groups, Internat. J. Algebra Comput. 25 (2015), 1275–1299.
Department of Mathematics, University of Nebraska, Lincoln NE 685880130, USA
E-mail address: hermiller@unl.edu
Departamento de Matemt́icas, Universidad de Zaragoza, 50009 Zaragoza,
Spain
E-mail address: conmar@unizar.es

