Combing nilpotent and polycyclic groups
Robert H. Gilman, Derek F. Holt and Sarah Rees
Keywords
combings, automatic groups, nilpotent groups, polycyclic groups, formal languages, fellow traveller property
Status
Published in
Internat. J. Algebra Comput. 9 (1999) 135--155.
Abstract
The notable exclusions from the family of automatic groups are
those nilpotent groups which are not virtually abelian,
and the fundamental groups of compact $3$-manifolds based on the $Nil$ or $Sol$
geometries.
Of these, the $3$-manifold groups have been shown by Bridson and Gilman to lie
in a family of groups defined by conditions slightly more general than those
of automatic groups, that is, to have combings which lie in the formal
language class of indexed languages.
In fact, the combings constructed by Bridson and Gilman for these groups
can also be seen to be real-time languages (that is,
recognised by real-time Turing machines).
This article investigates the situation for nilpotent and polycyclic groups.
It is shown that a finitely generated class 2 nilpotent group with cyclic
commutator subgroup is real-time combable, as are also all
2 or 3-generated class 2 nilpotent groups, and groups in specific
families of nilpotent groups (the finitely generated Heisenberg groups,
groups of unipotent matrices over $\Z$ and the free class 2 nilpotent groups).
Further it is shown that any polycyclic-by-finite group embeds in a
real-time combable group.
All the combings constructed in the article are boundedly asynchronous,
and those for nilpotent-by-finite groups have
polynomially bounded length functions, of degree equal to the nilpotency class,
$c$; this verifies a polynomial upper bound on the Dehn functions of those groups
of degree $c$+1.
The preprint is available as gzipped
dvi (39 kB) and
postscript (128 kB) files.
Alternatively, you can request a copy by
e-mailing me.
Sarah Rees
21 July 1998.