We extend work of the first author and Khoussainov to show that being Cayley automatic is closed under taking the restricted wreath product with a virtually infinite cyclic group. This adds to the list of known examples of Cayley automatic groups.
In contrast to being automatic, being Cayley automatic emph{a priori} has no geometric consequences. Specifically, Cayley graphs of automatic groups enjoy a fellow traveler property. Here we study a distance function introduced by the first author an
d Trakuldit which aims to measure how far a Cayley automatic group is from being automatic, in terms of how badly the Cayley graph fails the fellow traveler property. The first author and Trakuldit showed that if it fails by at most a constant amount, then the group is in fact automatic. In this article we show that for a large class of non-automatic Cayley automatic groups this function is bounded below by a linear function in a precise sense defined herein. In fact, for all Cayley automatic groups which have super-quadratic Dehn function, or which are not finitely presented, we can construct a non-decreasing function which (1) depends only on the group and (2) bounds from below the distance function for any Cayley automatic structure on the group.
We exhibit a regular language of geodesics for a large set of elements of $BS(1,n)$ and show that the growth rate of this language is the growth rate of the group. This provides a straightforward calculation of the growth rate of $BS(1,n)$, which was
initially computed by Collins, Edjvet and Gill in [5]. Our methods are based on those we develop in [8] to show that $BS(1,n)$ has a positive density of elements of positive, negative and zero conjugation curvature, as introduced by Bar-Natan, Duchin and Kropholler in [1].
For an element in $BS(1,n) = langle t,a | tat^{-1} = a^n rangle$ written in the normal form $t^{-u}a^vt^w$ with $u,w geq 0$ and $v in mathbb{Z}$, we exhibit a geodesic word representing the element and give a formula for its word length with respect
to the generating set ${t,a}$. Using this word length formula, we prove that there are sets of elements of positive density of positive, negative and zero conjugation curvature, as defined by Bar Natan, Duchin and Kropholler.
We show that the higher rank lamplighter groups, or Diestel-Leader groups $Gamma_d(q)$ for $d geq 3$, are graph automatic. This introduces a new family of graph automatic groups which are not automatic.
The definition of graph automatic groups by Kharlampovich, Khoussainov and Miasnikov and its extension to C-graph automatic by Murray Elder and the first author raise the question of whether Thompsons group F is graph automatic. We define a language
of normal forms based on the combinatorial caret types which arise when elements of F are considered as pairs of finite rooted binary trees, which we show to be accepted by a finite state machine with 2 counters, and forms the basis of a 3-counter graph automatic structure for the group.
It is not known whether Thompsons group F is automatic. With the recent extensions of the notion of an automatic group to graph automatic by Kharlampovich, Khoussainov and Miasnikov and then to C-graph automatic by the authors, a compelling question
is whether F is graph automatic or C-graph automatic for an appropriate language class C. The extended definitions allow the use of a symbol alphabet for the normal form language, replacing the dependence on generating set. In this paper we construct a 1-counter graph automatic structure for F based on the standard infinite normal form for group elements.
Let $Gamma_d(q)$ denote the group whose Cayley graph with respect to a particular generating set is the Diestel-Leader graph $DL_d(q)$, as described by Bartholdi, Neuhauser and Woess. We compute both $Aut(Gamma_d(q))$ and $Out(Gamma_d(q))$ for $d geq
2$, and apply our results to count twisted conjugacy classes in these groups when $d geq 3$. Specifically, we show that when $d geq 3$, the groups $Gamma_d(q)$ have property $R_{infty}$, that is, every automorphism has an infinite number of twisted conjugacy classes. In contrast, when $d=2$ the lamplighter groups $Gamma_2(q)=L_q = {mathbb Z}_q wr {mathbb Z}$ have property $R_{infty}$ if and only if $(q,6) eq 1$.
We describe a family of finitely presented groups which are quasi-isometric but not bilipschitz equivalent. The first such examples were described by the first author and are the lamplighter groups $F wr mathbb{Z}$ where $F$ is a finite group; these
groups are finitely generated but not finitely presented. The examples presented in this paper are higher rank generalizations of these lamplighter groups and include groups that are of type $F_n$ for any $n$.
We generalize the notion of a graph automatic group introduced by Kharlampovich, Khoussainov and Miasnikov (arXiv:1107.3645) by replacing the regular languages in their definition with more powerful language classes. For a fixed language class $mathc
al C$, we call the resulting groups $mathcal C$-graph automatic. We prove that the class of $mathcal C$-graph automatic groups is closed under change of generating set, direct and free product for certain classes $mathcal C$. We show that for quasi-realtime counter-graph automatic groups where normal forms have length that is linear in the geodesic length, there is an algorithm to compute normal forms (and therefore solve the word problem) in polynomial time. The class of quasi-realtime counter-graph automatic groups includes all Baumslag-Solitar groups, and the free group of countably infinite rank. Context-sensitive-graph automatic groups are shown to be a very large class, which encompasses, for example, groups with unsolvable conjugacy problem, the Grigorchuk group, and Thompsons groups $F,T$ and $V$.
