Extending the Synchronous Fellow Traveler Property

Prohrak Kruengthomya Mahidol University, Faculty of Science, Department of Mathematics, Bangkok 10400, Thailand; e–mail: [email protected]. Dmitry Berdinsky Mahidol University, Faculty of Science, Department of Mathematics and Centre of Excellence in Mathematics, CHE, Bangkok 10400, Thailand; e–mail: [email protected].

Abstract

We introduce an extension of the fellow traveler property which allows fellow travelers to be at distance bounded from above by a function $f(n)$ growing slower than any linear function. We study normal forms satisfying this extended fellow traveler property and certain geometric constraints that naturally generalize two fundamental properties of an automatic normal form – the regularity of its language and the bounded length difference property. We show examples of such normal forms and prove some non–existence theorems.

Keywords: fellow traveler property, normal form, quasigeodesic, prefix–closed, Baumslag–Solitar group, wreath product

1 Introduction

The fellow traveler property is a cornerstone of the theory of automatic groups introduced by Thurston and others [8]. A normal form of a group satisfies the fellow traveler property if every two normal forms of group elements which are at distance one (with respect to some fixed set of generators) are $k$ –fellow travelers for some positive integer $k$ . The latter, informally speaking, means that when two fellow travelers are synchronously moving with the same speed along the paths labeled by such normal forms they are always at distance at most $k$ from each other. Each automatic group admits an automatic structure that includes a normal form which satisfies the fellow traveler property [8, § 2.3]. If a normal form of a group satisfies the fellow traveler property and its language is regular, then the group must be automatic.

The idea of extending automatic groups while retaining the fellow traveler property or its natural relaxations is not new. Requiring the fellow traveler property for a normal form but dropping the regularity condition for its language leads to the notions of a combing and a combable group. Bridson showed that there exist combable groups which are not automatic [4]¹¹1Note that the notion of a combable group used by Bridson is different from the one originally introduced by Epstein and Thurston [8, § 3.6].. A more general approach is to allow fellow travelers moving with different speeds. This leads to the notion of the asynchronous fellow traveler property. Thurston showed that the Baumslag–Solitar group $BS(p,q)$ for $1\leqslant p<q$ admits a normal form which satisfies the asynchronous fellow traveler and the language of this normal form is regular [8, § 7.4]. Bridson and Gilman showed that the fundamental group of a compact $3$ –manifold admits a normal form which satisfies the asynchronous fellow traveler property and its language is indexed [5].

In this paper we consider a relaxation of the fellow traveler property requiring fellow travelers to move with the same speed (synchronously) but allowing them to be at distance bounded from above by $f(n)$ , where $f:\mathbb{N}\rightarrow\mathbb{R}_{+}$ is a function growing slower than any linear function, e.g., $n^{\alpha}$ for $0<\alpha<1$ or $\log(n)$ , and $n$ is the distance that fellow travelers traversed starting from the origin, see Definition 5. In this case we say that a normal form satisfies the $f(n)$ –fellow traveler property. First in the subsection 3.1 we notice that such normal forms can be trivially constructed. So then in the subsection 3.2 we introduce two types of geometric constraints each of which makes constructing such normal forms nontrivial. The first geometric constraint requires a normal form to be quasigeodesic. It is a relaxation of the bounded length difference property²²2Note the bounded length difference property is referred to as the comparable length property in [4]. Also, the bounded length difference property is incorporated in the notion of a combable group introduced by Epstein and Thurston. It is an open question whether there exists a combable group in the sense of Epstein and Thurston which is not automatic. [8, Lemma 2.3.9] which requires the geodesic length of a group element and the length of its normal form to be linearly comparable, see Definition 6. The second geometric constraint requires a normal form to be quasiregular. It is a relaxation of the regularity condition for the language of a normal form which requires that for each prefix $u$ of a normal form of a group element there exists a word $v$ of length at most $c>0$ for which $uv$ is a normal form of some group element, see Definition 7. Alternatively, quasiregularity can be considered as a relaxation of prefix–closedness; see also Definition 8 and Theorem 9.

The main results of the paper are as follows. In Theorems 14 and 15 we show that there exists no quasigeodesic normal form which satisfies the $f(n)$ –fellow traveler property in a finitely presented group with the strongly–super–polynomial Dehn function and a non–finitely presented group, respectively; see Definition 12 for the notion of a strongly–super–polynomial function. In Theorem 16 we show relation between the notion of a Cayley distance function studied by Elder, Taback, Trakuldit and the second author [1, 2, 3] and quasigeodesic normal forms satisfying the $f(n)$ –fellow traveler property. Namely, Theorem 16 shows that if a non–automatic group has a Cayley automatic representation for which the Cayley distance function $h(n)$ grows slower than a linear function³³3The existence of such Cayley automatic representations is an open question., then this group admits a quasigeodesic normal form satisfying the $h(n)$ –fellow traveler property. Theorem 17 shows that for $1\leqslant p<q$ the Baumslag–Solitar group $BS(p,q)=\langle a,t\,|\,ta^{p}t^{-1}=a^{q}\rangle$ admits a prefix–closed (so quasiregular) normal form satisfying the $\log(n)$ –fellow traveler property. Theorem 20 shows that the wreath product $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ admits a prefix–closed normal form satisfying the $\sqrt{n}$ –fellow traveler property⁴⁴4Note that by Theorems 14 and 15 the groups $BS(p,q)$ for $1\leqslant p<q$ and $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ do not admit quasigeodesic normal forms satisfying the $f(n)$ –fellow traveler property..

The rest of the paper is organized as follows. In Section 2 we recall the notions of a group, a normal form, an automatic group, the fellow traveler property and the relations $\preceq$ and $\ll$ for nondecreasing functions appeared in this paper. In Section 3 we introduce the $f(n)$ –fellow traveler property, quasigeodesic and quasiregular normal forms. In Section 4 for quasigeodesic normal forms satisfying the $f(n)$ –fellow traveler property we prove the non–existence theorems in groups with the strongly–super–polynomial Dehn function and non–finitely presented groups and show relation with the notion of a Cayley distance function. In Section 5 we show examples of quasiregular normal forms satisfying the $f(n)$ –fellow traveler property. Section 6 concludes the paper.

2 Preliminaries

In this section we introduce necessary notations and recall some definitions.

Groups and normal forms. Let $G$ be a finitely generated infinite group and $A=\{a_{1},\dots,a_{m}\}$ , where $a_{i}\in G$ for $i=1,\dots,m$ , be a finite set generating $G$ : each element of $G$ can be written as a product of elements from $A$ and their inverses. We allow different $a_{i},a_{j}\in A$ , $i\neq j$ , to be equal in $G$ and some elements in $A$ to be equal the identity $e\in G$ . We denote by $A^{-1}$ the set of formal inverses for elements in $A$ : $A^{-1}=\{a_{1}^{-1},\dots,a_{m}^{-1}\}$ and by $S$ the union of $A$ and $A^{-1}$ : $S=A\cup A^{-1}$ . We denote by $d_{A}$ the word metric in $G$ relative to $A$ : for $g_{1},g_{2}\in G$ the distance $d_{A}(g_{1},g_{2})$ is the length of a shortest word $u\in S^{*}$ equal to $g_{1}^{-1}g_{2}$ in $G$ . For a given $g\in G$ we denote by $d_{A}(g)$ the distance between $g$ and the identity $e\in G$ with respect to $d_{A}$ : $d_{A}(g)=d_{A}(e,g)$ . For a given $w=s_{1}\dots s_{\ell}\in S^{*}$ , we denote by $|w|$ the length of $w$ : $|w|=\ell$ and by $\pi(w)$ the group element $s_{1}\dots s_{\ell}\in G$ , where $\pi$ refers to the canonical projection map $\pi:S^{*}\rightarrow G$ .

A normal form of $G$ is a rule for assigning a word $w\in S^{*}$ to a group element $g\in G$ such that $\pi(w)=g$ . The word $w$ is referred to as a normal form of $g$ . In this paper we always assume that a normal form is one–to–one: for each $g\in G$ exactly one word $w\in S^{*}$ is assigned. A normal form defines a language $L\subseteq S^{*}$ . Similarly, a language $L\subseteq S^{*}$ for which the restriction $\pi_{L}:L\rightarrow G$ is surjective and one–to–one defines a normal form of $G$ .

The fellow traveler property and automatic groups. Let $w\in S^{*}$ be a word and $t\in[0,+\infty)$ be a nonnegative integer. We define $w(t)$ to be the prefix of $w$ of a length $t$ if $t\leqslant|w|$ and $w$ if $t>|w|$ . Let $L\subseteq S^{*}$ be a normal form of $G$ . We denote by $s(n)$ a function $s:[0,+\infty)\rightarrow\mathbb{R}_{+}$ defined as:

s(n)=\max\{d_{A}(\pi(w_{1}(t)),\pi(w_{2}(t)))\,|\,t\leqslant n,\,w_{1},w_{2}\in L,a\in A,\pi(w_{1})a=\pi(w_{2})\}.

(1)

The function $s(n)$ is the maximum distance between fellow travelers moving with the same speed along the paths in $\Gamma(G,A)$ labeled by words $w_{1}$ and $w_{2}$ for which $\pi(w_{1})a=\pi(w_{2})$ for some $a\in A$ .

Definition 1 (the fellow traveler property).

It is said that the normal form $L\subseteq S^{*}$ satisfies the fellow traveler property if the function $s(n)$ given by (1) is bounded from above by a constant.

Recall that the group $G$ is called automatic if it admits a normal form $L\subseteq S^{*}$ for which the language $L$ is regular and for each $a\in A$ the binary relation $R_{a}=\{(u,v)\,|\,\pi(u)a=\pi(v)\}$ is recognized by a two–tape synchronous automaton [8]. In this case the normal form $L$ satisfies the fellow traveler property. Equivalently, if $G$ admits a normal form $L\subseteq S^{*}$ which satisfies the fellow traveler property and $L$ is regular, then $G$ must be automatic [8, Theorem 2.3.5]. In this paper we focus on groups which are not automatic (non–automatic groups).

The relations $\preceq$ and $\ll$ for nondecreasing functions. We denote by $\mathbb{N}$ a set of all natural numbers which includes zero. For a given $N\in\mathbb{N}$ we denote by $[N,+\infty)$ the set $\left[N,+\infty\right)=\{n\in\mathbb{N}\,|\,n\geqslant N\}$ . Let $\mathcal{F}$ be the set of all nondecreasing functions $f:[N,+\infty)\rightarrow\mathbb{R}_{+}$ , where $\mathbb{R}_{+}=\{x\geqslant 0\,|\,x\in\mathbb{R}\}$ .

Definition 2 ( $\preceq$ relation).

For given $f,h\in\mathcal{F}$ we say that $h\preceq f$ if there exist positive integers $K,M$ and a nonnegative $N$ such that $h(n)\leqslant Kf(Mn)$ for all $n\in\left[N,+\infty\right)$ . We say that $h\asymp f$ if $h\preceq f$ and $f\preceq h$ . If $h\preceq f$ and $h\not\asymp f$ , we say that $h\prec f$ .

Definition 3 ( $\ll$ relation).

For given $f,h\in\mathcal{F}$ we say that $h\ll f$ if there exists an unbounded function $t\in\mathcal{F}$ such that $ht\preceq f$ .

We denote by $\mathfrak{i}:[0,+\infty)\rightarrow\mathbb{R}_{+}$ the identity function: $\mathfrak{i}(n)=n$ . Note that $f\ll\mathfrak{i}$ is stronger than $f\prec\mathfrak{i}$ , that is, $f\ll\mathfrak{i}$ implies $f\prec\mathfrak{i}$ . Indeed, $f\ll\mathfrak{i}$ implies $f\preceq\mathfrak{i}$ . Now suppose that $f\ll\mathfrak{i}$ and $\mathfrak{i}\preceq f$ . The inequality $\mathfrak{i}\preceq f$ implies that there exist positive integers $K,M$ and a nonnegative integer $N$ such that $n\leqslant Kf(Mn)$ for all $n\in\left[N,+\infty\right)$ . The inequality $f\ll\mathfrak{i}$ implies that there exist positive integers $K^{\prime},M^{\prime}$ and a nonnegative integer $N^{\prime}$ such that $f(n)t(n)\leqslant K^{\prime}M^{\prime}n$ for all $n\in\left[N^{\prime},+\infty\right)$ , where $t(n)$ is some unbounded function. Therefore, $f(n)\leqslant\frac{K^{\prime}M^{\prime}}{t(n)}n$ for all $n\in\left[N^{\prime},+\infty\right)$ , which implies that $Kf(Mn)\leqslant\frac{KK^{\prime}MM^{\prime}}{t(Mn)}n$ also for all $n\in\left[N^{\prime},+\infty\right)$ . Since $t(n)$ is unbounded, we get a contradiction. Therefore, we have that $\mathfrak{i}\not\preceq f$ , so $\mathfrak{i}\prec f$ . The reverse ( $f\prec\mathfrak{i}$ implies $f\ll\mathfrak{i}$ ) in general is not true as it is shown in Example 4.

Example 4.

Let $n_{i},i\geqslant 1$ be an infinite sequence defined recursively by the identities: $n_{0}=0$ , $n_{1}=1$ and $n_{i+1}=n_{i}2^{2i}$ for $i\geqslant 1$ . Let $f(n)$ be a function for which $f(n)=2n_{i}$ for $n_{i}\leqslant n<n_{i+1}$ . Clearly, $f(n)\preceq\mathfrak{i}$ . Let us show that $\mathfrak{i}\not\preceq f(n)$ . The inequality $\mathfrak{i}\preceq f$ implies that there exist positive integers $K,M$ and $N$ such that $n\leqslant Kf(Mn)$ for all $n\in\left[N,+\infty\right)$ . Therefore, if $n_{i}2^{i}\geqslant N$ , then $n_{i}2^{i}\leqslant Kf(Mn_{i}2^{i})$ . By the definition of $f(n)$ , if $M<2^{i}$ , then $f(Mn_{i}2^{i})=2n_{i}$ . Therefore, if $n_{i}2^{i}\geqslant N$ and $M<2^{i}$ , then $n_{i}2^{i}\leqslant 2Kn_{i}$ . The latter inequality is true only if $2^{i}\leqslant 2K$ and false, otherwise. Thus, $\mathfrak{i}\not\preceq f$ . Therefore, $f\prec\mathfrak{i}$ . Let us show now that $f\not\ll\mathfrak{i}$ . The inequality $f\ll\mathfrak{i}$ implies that there exist positive integers $K,M$ and a nonnegative integer $N$ such that $t(n)f(n)\leqslant KMn$ for some unbounded $t\in\mathcal{F}$ and all $n\in\left[N,+\infty\right)$ . Since $t(n)$ is unbounded, there exists $i_{0}$ such that for all $i\geqslant i_{0}$ , $t(n_{i})\geqslant KM$ which implies that $f(n_{i})=2n_{i}\leqslant n_{i}$ for all $i\geqslant i_{0}$ . The latter is impossible for $i>0$ .

3 The $f(n)$ –Fellow Traveler Property

We extend the fellow traveler property by allowing the distance between fellow travelers to be bounded from above by a nondecreasing function $f(n)$ . If $f(n)$ is bounded from above by a constant, then one simply gets the fellow traveler property, see Definition 1. We will allow the function $f(n)$ to be unbounded.

Definition 5 (the $f(n)$ –fellow traveler property).

Let $f\in\mathcal{F}$ be a function for which $f\ll\mathfrak{i}$ . We say that a given normal form $L\subseteq S^{*}$ of a group $G$ satisfies the $f(n)$ –fellow traveller property if for the function $s(n)$ given by (1) the inequality $s\preceq f$ holds.

In Definition 5 the function $f(n)$ is an upper bound for the distance between fellow travelers in coarse sense. It can be verified that Definition 5 does not depend on the choice of the set of generators $A$ . By the triangle inequality, for every normal form in $G$ we always have that $s(n)\leqslant 2n$ for all $n\in\mathbb{N}$ . From Example 4 we see that there exists a function $f\prec\mathfrak{i}$ for which $f(n)=2n$ at infinitely many points. If $f\ll\mathfrak{i}$ , then, informally speaking, $f$ genuinely grows slower than $\mathfrak{i}$ . This explains the choice of the inequality $f\ll\mathfrak{i}$ over the inequality $f\prec\mathfrak{i}$ in Definition 5. For illustration of the $f(n)$ –fellow traveler property see Fig. 1.

Refer to caption — Figure 1: The upper and lower curves show the paths labeled by the normal forms $w_{1}$ and $w_{2}$ of group elements $g$ and $ga$ , respectively. The pairs of dots and dashed curves connecting it show fellow travelers and shortest paths between them, respectively.

3.1 Normal forms satisfying the $f(n)$ –fellow traveler property

We now show two ways of modifying a given normal form so the modified normal form satisfies the $f(n)$ –fellow traveler property for some $f\ll\mathfrak{i}$ . Let us be given a normal form of a group $G$ defined by a language $L\subseteq S^{*}$ .

First way. Let $u\in S^{*}$ be a word defining a loop in $\Gamma(G,S)$ : $\pi(u)=e$ . We define a language $L^{\prime}\subseteq S^{*}$ as $L^{\prime}=\{u^{\ell^{2}}w\,|\,w\in L\wedge\ell=|w|\}$ . That is, for every $w\in L$ we attach a prefix $u^{\ell^{2}}$ to the word $w$ , where $\ell=|w|$ . See Figure 2 for illustration. For a normal form given by a language $L^{\prime}$ the function $s(n)$ is bounded from above by $\sqrt{n}$ : $s(n)\preceq\sqrt{n}$ . Indeed, let us consider two words $w_{1}\in L$ and $w_{2}\in L$ for which $\pi(w_{1})a=\pi(w_{2})$ . Let $|u|=c$ , $\ell_{1}=|w_{1}|$ and $\ell_{2}=|w_{2}|$ . Without loss of generality we assume that $\ell_{1}\leqslant\ell_{2}$ . We denote by $n$ a number of steps traversed by fellow travelers along the paths labeled by $w_{1}$ and $w_{2}$ . There are three different cases to consider:

•

If $n\leqslant c\ell_{1}^{2}$ , then the distance between fellow travelers is bounded from above by $2c$ .
•

If $c\ell_{1}^{2}<n\leqslant c\ell_{2}^{2}$ , then the distance between fellow travelers is bounded from above by $(\ell_{1}+c)$ , so it is strictly less than $\sqrt{n/c}+c$ .
•

If $c\ell_{2}^{2}<n\leqslant c\ell_{2}^{2}+\ell_{2}$ , then the distance between fellow travelers is bounded from above by $\ell_{1}$ + $\ell_{2}\leqslant 2\ell_{2}$ , so it is strictly less than $2\sqrt{n/c}$ .

From these three cases it can be seen that $s(n)\preceq\sqrt{n}$ for the normal form defined by the language $L^{\prime}$ .

Second way. Let $w=s_{1}\dots s_{m}$ be a nonempty word in the language $L$ . For each integer $k\in\{1,\dots,m\}$ , let us choose a loop $u_{k}\in S^{*}$ for which $C_{1}\sqrt{k}\leqslant|u_{k}|\leqslant C_{2}\sqrt{k}$ for some fixed constants $C_{1},C_{2}>0$ . These loops $u_{k}$ , $k=1,\dots,m$ can be chosen arbitrarily for each $w\in L$ and $k\in\{1,\dots,m\}$ , where $m=|w|$ . Let $w^{\prime}=s_{1}u_{1}s_{2}u_{2}\dots s_{m}u_{m}$ . If $w=\varepsilon$ , then we put $w^{\prime}=\varepsilon$ . We define a language $L^{\prime\prime}\subseteq S^{*}$ as $L^{\prime\prime}=\{w^{\prime}\,|\,w\in L\}$ . See Figure 3 for illustration.

For a normal form given by a language $L^{\prime\prime}$ the function $s(n)$ is bounded from above by $\sqrt{n}$ : $s(n)\preceq\sqrt{n}$ . Indeed, let us consider two words $w_{1}=s_{1}\dots s_{m_{1}}\in L$ and $w_{2}=t_{1}\dots t_{m_{2}}\in L$ for which $\pi(w_{1})a=\pi(w_{2})$ . For the words $w_{1}$ and $w_{2}$ , let $w_{1}^{\prime}=s_{1}u_{1}\dots s_{m_{1}}u_{m_{1}}$ and $w_{2}^{\prime}=t_{1}v_{1}\dots t_{m_{2}}v_{m_{2}}$ , respectively. Let $n$ be a number of steps traversed by fellow travelers along the paths labeled by $w_{1}$ and $w_{2}$ . We denote by $k_{1}$ the integer for which $w_{1}(n)=s_{1}u_{1}\dots s_{k_{1}}u_{k_{1}}q_{1}$ , where either $k_{1}=m_{1}$ and $q_{1}=\varepsilon$ or $q_{1}$ is a proper prefix of $s_{k_{1}+1}u_{k_{1}+1}$ . Similarly, we denote by $k_{2}$ the integer for which $w_{2}(n)=t_{1}v_{1}\dots t_{k_{2}}v_{k_{2}}q_{2}$ , where either $k_{2}=m_{2}$ and $q_{2}=\varepsilon$ or $q_{2}$ is a proper prefix of $t_{k_{2}+1}v_{k_{2}+1}$ . Now the distance between fellow travelers is bounded from above by $k_{1}+|q_{1}|+k_{2}+|q_{2}|\leqslant k_{1}+(1+C_{2}\sqrt{k_{1}+1})+k_{2}+(1+C_{2}\sqrt{k_{2}+1})$ . On the other hand, we have that $Ck_{1}^{\frac{3}{2}}\leqslant n$ and $Ck_{2}^{\frac{3}{2}}\leqslant n$ for some constant $C>0$ . Therefore, $s(n)\preceq n^{\frac{2}{3}}$ for the normal form defined by the language $L^{\prime\prime}$ .

3.2 Quasigeodesic and quasiregular normal forms

We introduce two kinds of geometric constraints for a normal form which originate from two basic properties of an automatic normal form: the bounded length difference property [8, Lemma 2.3.9] and the regularity of its language. These geometric constraints in general are an obstacle for trivial constructions of normal forms satisfying the $f(n)$ –fellow traveler property shown in the subsection 3.1. In this paper normal forms satisfying these geometric constraints are referred to as quasigeodesic and quasiregular.

Quasigeodesic normal forms. Recall that the bounded length difference property for the normal form defined by a language $L\subseteq S^{*}$ means that there exists a constant $C^{\prime}>0$ such that for every $w_{1},w_{2}\in L$ for which $\pi(w_{1})a=\pi(w_{2})$ for some $a\in A$ the inequality $||w_{1}|-|w_{2}||\leqslant C^{\prime}$ holds. Let $C=\max\{C^{\prime},|w_{0}|\}$ , where $w_{0}$ is the normal form of the identity $e\in G$ . Then the bounded length difference property implies that for every $w\in L$ we have $|w|\leqslant C(d_{A}(\pi(w))+1)$ . The latter is the notion of a quasigeodesic normal form introduced by Elder and Taback [7], see Definition 6. Note that for a normal form being quasigeodesic, in general, does not imply having the bounded length difference property.

Definition 6 (quasigeodesic normal form).

A normal form defined by a language $L\subseteq S^{*}$ is said to be quasigeodesic if there is a constant $C>0$ such that for every $w\in L$ the inequality $|w|\leqslant C(d_{A}(\pi(w))+1)$ holds.

Note that if $L\subseteq S^{*}$ is a quasigeodesic normal form in the sense of Definition 6, the paths labeled by elements of $L$ might not be quasigeodesics in the standard sense, i.e., not every subword $u^{\prime}$ of $u\in L$ needs to satisfy the inequality $|u^{\prime}|\leqslant C(d_{A}(\pi(u^{\prime}))+1)$ . We notice that normal forms constructed in the subsection 3.1 are not quasigeodesic. Indeed, for the first way we have that the normal form of a group element $\pi(w)$ is $w^{\prime}=u^{\ell^{2}}w$ , where $\ell=|w|$ . Since $d_{A}(\pi(w))\leqslant\ell$ and $|w^{\prime}|=|u|\ell^{2}+\ell\geqslant\ell^{2}$ , the inequality $|w^{\prime}|\leqslant C(d_{A}(\pi(w))+1)$ cannot hold for all $w\in L$ and some constant $C>0$ . For the second way we have that the normal form of a group element $\pi(w)$ is $w^{\prime}=s_{1}u_{1}s_{2}u_{2}\dots s_{m}u_{m}$ . Since $d_{A}(\pi(w))\leqslant m$ and $w^{\prime}=m+|u_{1}|+\dots+|u_{m}|\geqslant C_{1}\frac{m}{2}\sqrt{\frac{m}{2}}$ , the inequality $|w^{\prime}|\leqslant C(d_{A}(\pi(w))+1)$ cannot not hold for all $w\in L$ and some constant $C>0$ .

Quasiregular normal forms. In Definition 7 we introduce the notion of a quasiregular normal form. We consider it as a geometric version of the regularity of the language $L\subseteq S^{*}$ defining a normal form. Indeed, if a language $L\subseteq S^{*}$ is regular, then the normal form it defines is quasiregular. Note that a quasiregular normal form does not necessarily define a regular language $L\subseteq S^{*}$ .

Definition 7 (quasiregular normal form).

We say that a normal form defined by a language $L\subseteq S^{*}$ is quasiregular if there exists a constant $c\geqslant 0$ such that for each prefix $u\in S^{*}$ of a word $w=uv\in L$ there is a word $x\in S^{*}$ of length $|x|\leqslant c$ for which $ux\in L$ .

We notice that a normal form constructed using the first way in the subsection 3.1 is not quasiregular. Indeed, there are infinitely many words $u^{k}x\in L$ , where $u$ is a fixed loop and $|x|\leqslant c$ , that represent group elements for which the distances to $e\in G$ are bounded by some constant from above. The number of such group elements is finite. Since we consider only one–to–one normal forms, the latter is impossible. Also, there does not seem to be any trivial construction of quasiregular normal forms using the second way in the subsection 3.1.

One can consider a more restricted version of the notion of a quasiregular normal forms by additionally requiring in Definition 7 that $x$ is a prefix of $v$ . This leads to the notion of a quasiprefix–closed normal form introduced in Definition 8.

Definition 8 (quasiprefix–closed normal form).

We say that a normal form defined by a language $L\subseteq S^{*}$ is quasiprefix–closed if there exists a constant $C\geqslant 0$ such that for every prefix $u\in S^{*}$ of a word $w=uv\in L$ there is a prefix $x\in S^{*}$ of length $|x|\leqslant C$ of the word $v$ for which $ux\in L$ .

Prefix–closed normal forms are exactly quasiprefix–closed normal forms with the constant $C=0$ . A quasiprefix–closed normal form is quasiregular. The reverse in general is not true. However, Theorem 9 shows that if a quasiregular normal form satisfies the $f(n)$ –fellow traveler property, then one can construct a quasiprefix–closed normal form which also satisfies the $f(n)$ –fellow traveler property. So in the context of the $f(n)$ –fellow traveler property the notions of a quasiregular normal form and a quasiprefix–closed normal form are equivalent.

Theorem 9.

Suppose $L\subseteq S^{*}$ defines a quasiregular normal form for some constant $c\geqslant 0$ which satisfies the $f(n)$ –fellow traveler property. Then one can construct a quasiprefix–closed normal form $L^{\prime}\subseteq S^{*}$ for the constant $C=4c$ which also satisfies the $f(n)$ –fellow traveler property.

Proof.

First we note that if $c=0$ , then the normal form defined by the language $L$ is prefix–closed. So we further assume that $c>0$ . Now let $u$ be a prefix of length $k(c+1)$ of a word $w=uv\in L$ for an integer $k\geqslant 0$ . Since $L$ is a quasiregular normal form, there exists $x\in S^{*}$ of length $|x|\leqslant c$ for which $ux\in L$ . Let $y\in S^{*}$ be any word of length $c-|x|$ . We define $q(u)$ to be the word $xyy^{-1}x^{-1}\in S^{*}$ , where $x^{-1}$ and $y^{-1}$ are the inverses of $x$ and $y$ , respectively. The word $q(u)$ depends on $u$ only.

A word $w\in L$ can be always written as a concatenation $w=u_{1}u_{2}\dots u_{m}t$ of words $u_{1},\dots,u_{m}\in S^{*}$ and $t\in S^{*}$ , where $|u_{1}|=\dots=|u_{m}|=c+1$ and $0\leqslant|t|<c+1$ . For each word $w\in L$ we construct a word $w^{\prime}$ as follows:

w^{\prime}=u_{1}q(u_{1})\dots u_{m-1}q(u_{1}\dots u_{m-1})u_{m}t.

(2)

We define a language $L^{\prime}$ as $L^{\prime}=\{w^{\prime}\,|\,w\in L\}$ . Let us show that $L^{\prime}$ is a quasiprefix–closed normal form for the constant $C=4c$ . We denote by $x_{i},y_{i}\in S^{*}$ the words for which $q(u_{1}\dots u_{i})=x_{i}y_{i}y_{i}^{-1}x_{i}^{-1}$ . Let $u^{\prime}$ be a prefix of $w^{\prime}$ . There are the following three possibilities.

•

The prefix $u^{\prime}$ is of the form $u^{\prime}=u_{1}q(u_{1})\dots u_{i-1}q(u_{1}\dots u_{i-1})p_{i}$ , where $i=1,\dots,m-1$ and $p_{i}$ is a prefix of $u_{i}$ . By the definition of $x_{i}$ , we have that $u_{1}\dots u_{i-1}u_{i}x_{i}\in L$ . Let $u^{\prime\prime}=u_{1}q(u_{1})\dots u_{i-1}q(u_{1}\dots u_{i-1})u_{i}x_{i}$ . It can be seen that $u^{\prime\prime}\in L^{\prime}$ , $u^{\prime}$ is a prefix of $u^{\prime\prime}$ and $u^{\prime\prime}$ is a prefix of $w^{\prime}$ . Let $u_{i}=p_{i}\tau_{i}$ . Then $u^{\prime\prime}=u^{\prime}\tau_{i}x_{i}$ , so $|u^{\prime\prime}|-|u^{\prime}|=|\tau_{i}|+|x_{i}|\leqslant\left(c+1\right)+c\leqslant 4c$ .
•

The prefix $u^{\prime}$ is of the form $u^{\prime}=u_{1}q(u_{1})\dots u_{i-1}q(u_{1}\dots u_{i-1})u_{i}p_{i}$ , where $i=1,\dots,m-1$ and $p_{i}$ is a prefix of $q(u_{1}\dots u_{i})=x_{i}y_{i}y_{i}^{-1}x_{i}^{-1}$ . If $p_{i}$ is a prefix of $x_{i}$ , then we put $u^{\prime\prime}=u_{1}q(u_{1})\dots u_{i-1}q(u_{1}\dots u_{i-1})u_{i}x_{i}$ . If $p_{i}$ is not a prefix of $x_{i}$ , then we put $u^{\prime\prime}=u_{1}q(u_{1})\dots u_{i-1}q(u_{1}\dots u_{i-1})u_{i}q(u_{1}\dots u_{i})\gamma_{i}$ , where $\gamma_{i}=u_{i+1}x_{i+1}$ if $i<m-1$ and $\gamma_{i}=u_{m}t$ if $i=m-1$ . It can be seen that $u^{\prime\prime}\in L^{\prime}$ , $u^{\prime}$ is a prefix of $u^{\prime\prime}$ and $u^{\prime\prime}$ is a prefix of $w^{\prime}$ . In the first case when $p_{i}$ is a prefix of $x_{i}$ , we have that $|u^{\prime\prime}|-|u^{\prime}|\leqslant|x_{i}|\leqslant c$ . In the second case when $p_{i}$ is not a prefix of $x_{i}$ , we have that $|u^{\prime\prime}|-|u^{\prime}|\leqslant(2c-1)+(c+1)+c=4c$ .
•

The prefix $u^{\prime}$ is of the form $u^{\prime}=u_{1}q(u_{1})\dots u_{m-1}q(u_{1}\dots u_{m-1})p_{m}$ , where $p_{m}$ is a prefix of $u_{m}t$ . Let $u^{\prime\prime}=w^{\prime}$ . Then $u^{\prime\prime}\in L$ , $u^{\prime}$ is a prefix of $u^{\prime\prime}$ and $u^{\prime\prime}$ is a prefix of $w^{\prime}$ . We have that $|u^{\prime\prime}|-|u^{\prime}|\leqslant(c+1)+c\leqslant 4c$ .

It is straightforward from (2) that if $L$ satisfies the $f(n)$ –fellow traveler property, then $L^{\prime}$ also satisfies the $f(n)$ –fellow traveler property. ∎

4 Quasigeodesic Normal Forms

This section discusses quasigeodesic normal forms in the context of the $f(n)$ –fellow traveler property. In the subsection 4.1 we show that groups with the strongly–super–polynomial Dehn function and non–finitely presented groups do not admit quasigeodesic normal forms satisfying the $f(n)$ –fellow traveler property. In the subsection 4.2 we show relation with the notion of a Cayley distance function.

4.1 Non–existence theorems

This subsection presents non–existence theorems for quasigeodesic normal forms satisfying the $f(n)$ –fellow traveler property. First we consider finitely presented groups. We show that if the Dehn function of a group is strongly–super–polynomial (see Definition 12), then it does not admit a quasigeodesic normal form satisfying the $f(n)$ –fellow traveler property (see Theorem 14). Then we consider non–finitely presented groups. We show that they do not admit quasigeodesic normal forms satisfying the $f(n)$ –fellow traveler property (see Theorem 15).

Finitely presented groups. Let $G$ be a group. We assume first that $G$ is finitely presented. Let $G=\langle A\,|\,R\rangle$ be a finite presentation of $G$ . We denote by $F_{A}$ a free group on $A$ . Let $w\in F_{A}$ be a reduced word for which $\pi(w)=e$ in the group $G$ . Let us recall the definitions of a combinatorial area and the Dehn function.

Definition 10 (combinatorial area).

The area $\mathcal{A}(w)$ with respect to the presentation $\langle A\,|\,R\rangle$ is the minimum $N$ for which $w=\prod\limits_{i=1}^{N}\tau_{i}^{-1}r_{i}^{\pm 1}\tau_{i}$ in $F_{A}$ , where $r_{i}\in R$ and $\tau_{i}\in F_{A}$ .

Definition 11 (Dehn function).

The Dehn function of $G$ with respect to the presentation $\langle A\,|\,R\rangle$ is the function $\delta:\mathbb{N}\rightarrow\mathbb{N}$ such that $\delta(n)=\max\{\mathcal{A}(w)\,|\,w\in F_{A},|w|\leqslant n\}$ .

Now we recall the notion of a strongly–super–polynomial function introduced in [1].

Definition 12 (strongly–super–polynomial function).

A non–zero function $f\in\mathcal{F}$ is said to be strongly–super–polynomial if $n^{2}f\ll f$ .

Note that for every $c>0$ , one has that $n^{2}f\ll f$ if and only if $n^{c}f\ll f$ [1]. Strongly–super–polynomial functions include, for example, exponential functions.

The following lemma is a key ingredient in the proof of Theorem 14.

Lemma 13.

If a group $G=\langle A\,|\,R\rangle$ admits a quasigeodesic normal form satisfying the $f(n)$ –fellow traveler property, then there exist constants $C,D>0$ and $n_{0}\geqslant 0$ such that for the Dehn function $\delta(n)$ of $G$ with respect to the presentation $\langle A\,|\,R\rangle$ the inequality $\delta(n)\leqslant Dn^{2}\delta(Cf(Cn))$ holds for all $n\geqslant n_{0}$ .

Proof.

Suppose that $G$ admits a quasigeodesic normal form satisfying the $f(n)$ –fellow traveler property. Let $L\subseteq S^{*}$ be a language defining such normal form in $G$ . Now let $w=s_{1}\dots s_{n}\in S^{*}$ be a word for which $\pi(w)=e$ in the group $G$ , where $n=|w|$ . For each $i=1,\dots,n-1$ , let $u_{i}\in L$ be the normal form of the group element $g_{i}=\pi(s_{1}\dots s_{i})$ . We first divide a loop $w$ into subloops: $s_{1}u_{1}^{-1}$ , $u_{1}s_{2}u_{2}^{-1},\dots,u_{n-2}s_{n-1}u_{n-1}^{-1}$ , $u_{n-1}s_{n}$ .

For a given $i\in\{1,\dots,n-1\}$ and $j\geqslant 1$ we denote by $u_{i,j}\in S$ the $j$ th symbol in the normal form $u_{i}\in S^{*}$ , if $j\leqslant|u_{i}|$ , and $u_{i,j}=e$ , if $j>|u_{i}|$ . In particular, a prefix of $u_{i}$ of length $j\leqslant|u_{i}|$ is $u_{i,1}\dots u_{i,j}$ . For a given $i\in\{1,\dots,n-2\}$ and $j\geqslant 1$ , let $v_{i,j}\in S^{*}$ be a shortest path connecting $g_{i,j}=\pi(u_{i,1}\dots u_{i,j})$ and $g_{i+1,j}=\pi(u_{i+1,1}\dots u_{i+1,j})$ : $g_{i,j}\cdot v_{i,j}=g_{i+1,j}$ . For illustration see Figure 4.

For a given $i\in\{1,\dots,n-2\}$ , let $m_{i}=\max\{|u_{i}|,|u_{i+1}|\}-1$ . Now we divide each subloop $u_{i}s_{i+1}u_{i+1}^{-1},i=1,\dots,n-2$ into smaller subloops $w_{i,j},j=1,\dots,m_{i}$ : if $j=1$ , then $w_{i,1}=u_{i,1}v_{i,1}u_{i+1,1}^{-1}$ , if $2\leqslant j\leqslant m_{i}-1$ , then $w_{i,j}=u_{i,j}v_{i,j}u_{i+1,j}^{-1}v_{i,j-1}^{-1}$ and if $j=m_{i}$ , then $w_{i,m_{i}}=u_{i,m_{i}}s_{i+1}u_{i+1,m_{i}}^{-1}v_{i,m_{i}}^{-1}$ . Therefore, for the area $\mathcal{A}(w)$ we have: $\mathcal{A}(w)\leqslant\mathcal{A}(s_{1}u_{1}^{-1})+\mathcal{A}(u_{n-1}s_{n})+\sum\limits_{i=1}^{n-2}\sum\limits_{j=1}^{m_{i}}\mathcal{A}(w_{i,j})$ .

Let $s(n)$ be the function defined by the equation (1) for the normal form $L$ and the set of generators $A$ . We have: $|w_{i,j}|\leqslant s(j)+s(j-1)+2$ for $1\leqslant j\leqslant m_{i}-1$ and $|w_{i,m_{i}}|\leqslant 3+s(j-1)$ for $j=m_{i}$ . Since the normal form $L$ is quasigeodesic, there exists a positive integer $D$ such that $Dn\geqslant m_{i}$ for all $i=1,\dots,n-2$ .

If $s(n)$ is an unbounded function we may assume that $s(D)\geqslant\max\{|s_{1}u_{1}^{-1}|,|u_{n-1}s_{n}|\}$ ; in particular, $s(D)\geqslant 1$ . The total number of terms in the expression $\mathcal{A}(s_{1}u_{1}^{-1})+\mathcal{A}(u_{n-1}s_{n})+\sum\limits_{i=1}^{n-2}\sum\limits_{j=1}^{m_{i}}\mathcal{A}(w_{i,j})$ is at most $Dn^{2}$ and each term is bounded from above by $4s(Dn)$ . Therefore, $\mathcal{A}(w)\leqslant Dn^{2}\delta(4s(Dn))$ which implies that $\delta(n)\leqslant Dn^{2}\delta(4s(Dn))$ for all $n$ . Since the normal form $L$ satisfies the $f(n)$ –fellow traveler property, we have that $s\preceq f$ which implies that there exists a constant $C_{0}>0$ and $n_{0}\geqslant 0$ such that $s(n)\leqslant C_{0}f(C_{0}n)$ for all $n\geqslant n_{0}$ . Therefore, $\delta(n)\leqslant Dn^{2}\delta(4s(Dn))\leqslant Dn^{2}\delta(4C_{0}f(C_{0}Dn))$ . Let $C=\max\{4C_{0},C_{0}D\}$ . Then we have that $\delta(n)\leqslant Dn^{2}\delta(Cf(Cn))$ for all $n\geqslant n_{0}$ .

If the function $s(n)$ is bounded from above by a constant, then we immediately obtain that $\delta(n)=O(n^{2})$ . In particular, one can always get that $\delta(n)\leqslant Dn^{2}\delta(Cf(Cn))$ for all $n\geqslant n_{0}$ for some integer constants $C,D>0$ and $n_{0}\geqslant 0$ . ∎

Theorem 14.

If the Dehn function of a group $G=\langle A\,|\,R\rangle$ with respect to the presentation $\langle A\,|\,R\rangle$ is strongly–super–polynomial, then $G$ does not admit a quasigeodesic normal form that satisfies the $f(n)$ –fellow traveler property.

Proof.

Let $\delta(n)$ be the Dehn function of a group $G$ with respect to a presentation $\langle A\,|\,R\rangle$ . Since the Dehn function $\delta(n)$ is strongly–super–polynomial, $n^{2}\delta(n)\ll\delta(n)$ . Therefore, there exist an unbounded function $t(n)\in\mathcal{F}$ and constants $K,M,N_{0}$ such that for all $n\geqslant N_{0}$ :

n^{2}\delta(n)t(n)\leqslant K\delta(Mn).

(3)

\delta(n)\leqslant Dn^{2}\delta(Cf(Cn)).

(4)

Let $N_{2}=\max\{N_{0},N_{1}\}$ . By the inequalities (3) and (4) we obtain that for all $n\geqslant N_{2}$ :

n^{2}\delta(n)t(n)\leqslant K\delta(Mn)\leqslant DKM^{2}n^{2}\delta(Cf(CMn)).

Therefore, $\delta(n)t(n)\leqslant DKM^{2}\delta(Cf(CMn))$ for all $n\geqslant N_{2}$ . Let $N_{3}=\min\{n\,|\,2DKM^{2}\leqslant t(n)\}$ and $N_{4}=\max\{N_{2},N_{3}\}$ . Then, $2\delta(n)\leqslant\delta(Cf(CMn))$ for all $n\geqslant N_{4}$ .

Let $N_{5}=\min\{n\,|\,\delta(n)\geqslant 1\}$ and $N_{6}=\max\{N_{4},N_{5}\}$ . Then, $n\leqslant Cf(CMn)$ for all $n\geqslant N_{6}$ as if, otherwise, $n>Cf(CMn)$ for some $n\geqslant N_{6}$ , then $2\delta(n)\leqslant\delta(Cf(CMn))\leqslant\delta(n)$ which leads to a contradiction with the inequality $\delta(n)\geqslant 1$ . Since $f\ll\mathfrak{i}$ , there exists an unbounded function $\tau(n)\in\mathcal{F}$ and constants $E,N_{7}$ such that $f(CMn)\tau(CMn)\leqslant En$ for all $n\geqslant N_{7}$ . Let $N_{8}=\max\{N_{6},N_{7}\}$ . From the inequalities $n\leqslant Cf(CMn)$ and $f(CMn)\tau(CMn)\leqslant En$ we conclude that $n\tau(CMn)\leqslant CEn$ for all $n\geqslant N_{8}$ . As the function $\tau(n)$ is unbounded, we get a contradiction. ∎

Non–finitely presented groups. Now we assume that $G$ is a non–finitely presented group. In this case no additional assumptions are needed to show non–existence Theorem 15. Equivalently, Theorem 15 claims that if $G$ is a finitely generated group admitting a quasigeodesic normal form with the $f(n)$ –fellow traveler property, then $G$ is finitely presented.

Theorem 15.

If $G$ is a non–finitely presented group, then $G$ does not admit a quasigeodesic normal form that satisfies the $f(n)$ –fellow traveller property.

Proof.

First we notice that there exist infinitely many words $w\in S^{*}$ for which $\pi(w)=e$ such that for every decomposition of $w$ as the product $w=\prod\limits_{j=1}^{k}r_{j}^{-1}u_{j}r_{j}$ , where $r_{j},u_{j}\in S^{*}$ and $\pi(u_{j})=e$ for $j=1,\dots,k$ , for some $1\leqslant m\leqslant k$ the length of $u_{m}$ is greater than or equal to the length of $w$ : $|u_{m}|\geqslant|w|$ . Indeed, if such infinitely many words did not exist, the group $G$ would be finitely presented. We denote the set of such words by $W$ .

We prove the theorem by contradiction. Assume that $G$ admits a quasigeodesic normal form satisfying the $f(n)$ –fellow traveller property for some function $f\ll\mathfrak{i}$ . Let $L\subseteq S^{*}$ be a language defining such normal form in $G$ . Let $w=s_{1}\dots s_{n}$ be a word from the set $W$ . For each $i=1,\dots,n-1$ , let $u_{i}\in L$ be the normal form of the group element $g_{i}=\pi(s_{1}\dots s_{i})$ . Similarly to Lemma 13, we divide a loop $w$ into subloops: $s_{1}u_{1}^{-1}$ , $u_{1}s_{2}u_{2}^{-1}$ , …, $u_{n-2}s_{n-1}u_{n-1}^{-1}$ , $u_{n-1}s_{n}$ . For a given $i\in\{1,\dots,n-1\}$ and $j\geqslant 1$ we denote by $u_{i,j}\in S$ the $j$ th symbol in the normal form $u_{j}\in S^{*}$ , if $j\geqslant|u_{i}|$ , and $u_{i,j}=e$ , if $j>|u_{i}|$ . For a given $i\in\{1,\dots,n-2\}$ and $j\geqslant 1$ , we denote by $v_{i,j}\in S^{*}$ a shortest path connecting $g_{i,j}=\pi(u_{i,1}\dots u_{i,j})$ and $g_{i+1,j}=\pi(u_{i+1,1}\dots u_{i+1,j})$ .

For a given $i\in\{1,\dots,n-2\}$ , let $\ell_{i}=\max\{|u_{i}|,|u_{i+1}|\}-1$ . Similarly to the proof of Lemma 13, let us divide each subloop $u_{i}s_{i+1}u_{i+1}^{-1}$ , $i=1,\dots,n-2$ into smaller subloops $w_{i,j},j=1,\dots,\ell_{i}$ : if $j=1$ , then $w_{i,1}=u_{i,1}v_{i,1}u_{i+1,1}^{-1}$ , if $2\leqslant j\leqslant\ell_{i}-1$ , then $w_{i,j}=u_{i,j}v_{i,j}u_{i+1,j}^{-1}v_{i,j-1}^{-1}$ and if $j=\ell_{i}$ , then $w_{i,\ell_{i}}=u_{i,\ell_{i}}s_{i+1}u_{i+1,\ell_{i}}^{-1}v_{i,\ell_{i}}^{-1}$ .

Let $s(n)$ be the function defined by the equation (1) for the normal form $L$ and the set of generators $A$ . Let $\ell=\max\{\ell_{i}\,|\,i=1,\dots,n-2\}$ . Then, $|w_{i,j}|\leqslant 4s(\ell)$ for all $i=1,\dots,n-2$ and $1\leqslant j\leqslant\ell_{i}$ , where we assume that $\ell$ is big enough so $s(\ell)\geqslant 1$ . Since the normal form is quasigeodesic, there exists an integer constant $C>0$ for which $\ell_{i}\leqslant Cn$ for all $i=1,\dots,n-2$ , so $\ell\leqslant Cn$ .

As $s\preceq f$ for some $f\ll\mathfrak{i}$ , there exists an unbounded function $t\in\mathcal{F}$ for which $s(n)t(n)\preceq\mathfrak{i}$ . In particular, $s(n)\leqslant\frac{1}{8C}n$ for all $n\geqslant N$ for some $N$ . Therefore, if $n\geqslant N$ , then $|w_{i,j}|\leqslant\frac{n}{2}$ for all $i=1,\dots,n-2$ and $1\leqslant j\leqslant\ell_{i}$ . Furthermore, we may assume that $n$ is big enough so $|s_{1}u_{1}^{-1}|,|u_{n-1}s_{n}|\leqslant\frac{n}{2}$ . Since $\frac{n}{2}<n$ and $w\in W$ , we get a contradiction. ∎

4.2 Relation with a Cayley distance function

We find relation with the notion of a Cayley distance function studied in [1, 2, 3]. A Cayley distance function $h:\mathbb{N}\rightarrow\mathbb{R}_{+}$ is defined for an arbitrary bijection $\psi:L\rightarrow G$ between a language $L\subseteq S^{*}$ and a group $G$ by the following identity:

h(n)=\max\{d_{A}(\psi(w),\pi(w))\,|\,w\in L^{\leqslant n}\}\,\,\mathrm{if}\,\,L^{\leqslant n}\neq\varnothing,

where $L^{\leqslant n}=\{w\,|\,|w|\leqslant n\}$ is the set of words in $L$ of length less than or equal to $n$ , and $h(n)=0$ if $L^{\leqslant n}=\varnothing$ .

Cayley automatic groups were introduced by Kharlampovich, Khoussainov and Miasnikov [10]. We recall that a group $G$ is called Cayley automatic if there exists a bijection $\psi:L\rightarrow G$ for which $L$ is a regular language and for each $a\in A$ the relation $R_{a}=\{(u_{1},u_{2})\in L\times L\,|\,\psi(u_{1})a=\psi(u_{2})\}$ is recognized by a two–tape synchronous automaton. The bijection $\psi:L\rightarrow G$ is referred to as a Cayley automatic representation of $G$ . Cayley automatic groups extend automatic groups retaining exactly the same computational model but allowing an arbitrary bijection $\psi:L\rightarrow G$ , not only a canonical mapping $\pi:L\rightarrow G$ like in the notion of an automatic group.

In [3] it is asked if there exists a Cayley automatic representation of a non–automatic group $G$ such that for the Cayley distance function $h:\mathbb{N}\rightarrow\mathbb{R}_{+}$ the inequality $h\prec\mathfrak{i}$ holds. This problem can be slightly narrowed by requiring that $h\ll\mathfrak{i}$ . Theorem 16 shows that if such Cayley automatic representation exists, then $G$ admits a quasigeodesic normal form satisfying the $h(n)$ –fellow traveler property.

Theorem 16.

If a non–automatic group $G$ has a Cayley automatic representation $\psi:L\rightarrow G$ with the Cayley distance function $h\ll\mathfrak{i}$ , then there exists a quasigeodesic normal form $L^{\prime}\subseteq S^{*}$ that satisfies the $h(n)$ –fellow traveler property.

Proof.

First we describe how to construct a normal form $L^{\prime}$ from a given Cayley automatic representation $\psi:L\rightarrow G$ . For a given $u\in L$ let $v\in S^{*}$ be a word corresponding to a shortest path between $\pi(u)$ and $\psi(u)$ in the Cayley graph $\Gamma(G,A)$ for which $\psi(u)=\pi(uv)$ . We define the language $L^{\prime}\subseteq S^{*}$ as $L^{\prime}=\{uv\,|\,u\in L\}$ . Below we prove that $L^{\prime}$ defines a quasigeodesic normal form that satisfies the $h(n)$ –fellow traveler property.

We now show that the normal form defined by $L^{\prime}$ is quasigeodesic. Let $g=\psi(u)$ for some $u\in L$ and $w=uv\in L^{\prime}$ be the normal form of $g$ . We need to show that $|uv|\leqslant Cd_{A}(g)+C$ for some constant $C>0$ . Since $\psi:L\rightarrow G$ is a Cayley automatic representation, there exists a constant $C_{1}>0$ for which $|u|\leqslant C_{1}(d_{A}(g)+1)$ . Let $n=|u|$ . Then $|v|\leqslant h(n)$ . Therefore, $|w|=|u|+|v|\leqslant n+h(n)$ . Since $h\ll\mathfrak{i}$ , then $h(n)\leqslant C_{2}n$ for some constant $C_{2}>0$ and all $n\geqslant N_{0}$ . Let $C_{3}=C_{2}+1$ . Then we have that $|w|\leqslant C_{3}n\leqslant C_{3}C_{1}(d_{A}(g)+1)$ for all $n\geqslant N_{0}$ . Therefore, there exists a constant $C>0$ such that $|w|\leqslant C(d_{A}(g)+1)$ for all $n\geqslant 0$ .

Let us show that $L^{\prime}$ defines a normal form in $G$ that satisfies the $h(n)$ –fellow traveler property. Let $w_{1}=u_{1}v_{1}\in L^{\prime}$ and $w_{2}=u_{2}v_{2}\in L^{\prime}$ be the normal forms of the group elements $g_{1}=\pi(w_{1})$ and $g_{2}=\pi(w_{2})$ for which $g_{1}a=g_{2}$ for some $a\in A$ . See Figure 5 for illustration. We denote by $m$ the minimum $m=\min\{|u_{1}|,|u_{2}|\}$ . Let $s(n)$ be the function defined by the equation (1) for the normal form $L^{\prime}$ and the set of generators $A$ . It can be shown that $s(n)\leqslant 2h(n)+C_{0}$ for all $n\leqslant m$ and some constant $C_{0}>0$ ; this is proved in details for all $n\geqslant 0$ in [2, Theorem 2.1]. If $n\geqslant m$ , then by the triangle inequality $d_{A}(\pi(w_{1}(n)),\pi(w_{2}(n)))\leqslant|v_{1}|+|v_{2}|+||u_{1}|-|u_{2}||+1$ . Since the representation $\psi:L\rightarrow G$ is Cayley automatic, $||u_{1}|-|u_{2}||\leqslant C_{2}$ for some constant $C_{2}$ . Let $C_{3}=C_{2}+1$ . Therefore, for all $n\geqslant m$ :

\begin{split}d_{A}(\pi(w_{1}(n)),\pi(w_{2}(n)))\leqslant|v_{1}|+|v_{2}|+C_{3}\leqslant h(|u_{1}|)+h(|u_{2}|)+C_{3}\leqslant\\ h(m)+h(m+C_{2})+C_{3}\leqslant 2h(m+C_{2})+C_{3}\leqslant 2h(n+C_{2})+C_{3}.\end{split}

Let $C_{4}=\max\{C_{0},C_{3}\}$ . Then, for all $n\geqslant 0$ , we have that $d_{A}(\pi(w_{1}(n)),\pi(w_{2}(n)))\leqslant 2h(n+C_{2})+C_{4}$ . Let $f(n)=2h(n+C_{2})+C_{4}$ . Since $f(n)\preceq h(n)$ , we get that $s(n)\preceq h(n)$ . Therefore, $L^{\prime}$ defines a normal form of $G$ satisfying the $h(n)$ –fellow traveler property. ∎

5 Quasiregular Normal Forms

This section discusses quasiregular normal forms in the context of the $f(n)$ –fellow traveler property. By Theorems 14 and 15 for groups with the strongly–super–polynomial Dehn function and non–finitely presented groups there exist no quasigeodesic normal forms satisfying the $f(n)$ –fellow traveler property. In this section we show examples of quasiregular normal forms satisfying the $f(n)$ –fellow traveler property for such groups.

5.1 Baumslag–Solitar groups

We consider a family of the Baumslag–Solitar groups $BS(p,q)=\langle a,t\,|\,ta^{p}t^{-1}=a^{q}\rangle$ for $1\leqslant p<q$ . Each group of this family has the exponential Dehn function, so by Theorem 14 it does not admit a quasigeodesic normal form satisfying the $f(n)$ –fellow traveler property. In Theorem 17 we will show that each group of this family admits a quasiregular normal form satisfying the $\log(n)$ –fellow traveler property.

Theorem 17.

Each group $BS(p,q)$ for $1\leqslant p<q$ admits a quasiregular normal form satisfying the $\log(n)$ –fellow traveler property.

Proof.

Every group element $g\in BS(p,q)$ for $1\leqslant p<q$ can be uniquely written as a freely reduced word over the alphabet $\{a^{\pm 1},t^{\pm 1}\}$ of the form:

w=w_{\ell}t^{\varepsilon_{\ell}}\dots w_{1}t^{\varepsilon_{1}}a^{k},

(5)

where $\varepsilon_{i}\in\{+1,-1\}$ , $w_{i}\in\{\epsilon,a,\dots,a^{p-1}\}$ if $\varepsilon_{i}=-1$ , $w_{i}\in\{\epsilon,a,\dots,a^{q-1}\}$ if $\varepsilon_{i}=+1$ and $k\in\mathbb{Z}$ . So the identity (5) defines a normal form in $BS(p,q)$ . This normal form is prefix–closed, so it is quasiregular. Below we show that it satisfies the $\log(n)$ –fellow traveler property.

Let $A=\{a,t\}$ and $d_{A}$ be the word metric in $BS(p,q)$ with respect to the generators $a$ and $t$ . Burillo and Elder [6] showed that there exist constants $C_{1},C_{2},D_{1},D_{2}>0$ such that for all $g\in BS(p,q)$ :

C_{1}(\ell+\log(|k|+1))-D_{1}\leqslant d_{A}(g)\leqslant C_{2}(\ell+\log(|k|+1))+D_{2}.

(6)

We first consider a pair of group elements $g$ and $ga$ . Let $w_{a}$ be the normal form of $ga$ . Then $w_{a}=w_{\ell}t^{\varepsilon_{\ell}}\dots w_{1}t^{\varepsilon_{1}}a^{k}$ . Clearly, $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 1$ for all $n\geqslant 0$ .

Now we consider a pair of group elements $g$ and $gt$ . We denote by $w_{t}$ the normal form of $gt$ . Let $k=mq+r$ , where $m\in\mathbb{Z}$ and $r\in\{0,\dots,q-1\}$ . We have three different cases:

•

Suppose $r\neq 0$ . Then $w_{t}=w_{\ell}t^{\varepsilon_{\ell}}\dots w_{1}t^{\varepsilon_{1}}a^{r}ta^{mp}$ . Let $u=w_{\ell}t^{\varepsilon_{\ell}}\dots w_{1}t^{\varepsilon_{1}}$ . If $n\leqslant|u|$ , then $d_{A}(\pi(w(n)),\pi(w_{t}(n)))=0$ . If $|u|<n\leqslant|u|+r+1$ , then $d_{A}(\pi(w(n)),\pi(w_{t}(n)))\leqslant 2r+2$ . If $n>|u|+r+1$ , then $d_{A}(\pi(w(n)),\pi(w_{t}(n)))\leqslant d_{A}(a^{r}ta^{i})+d_{A}(a^{j})$ , where $i=\min\{|mp|,n-(|u|+r+1)\}*\mathrm{sign}(k)$ and $j=\min\{|k|,n-|u|\}*\mathrm{sign}(k)$ . By (6), $d_{A}(a^{r}ta^{i})\leqslant C_{2}(1+\log(|i|+1))+D_{2}$ and $d_{A}(a^{j})\leqslant C_{2}\log(|j|+1)+D_{2}$ . Therefore, $d_{A}(\pi(w(n)),\pi(w_{t}(n)))\leqslant 2C_{2}\log(n+1)+C_{2}+2D_{2}$ .
•

Suppose $r=0$ and either $\varepsilon_{1}=1$ or $\ell=0$ . Then $w_{t}=w_{\ell}t^{\varepsilon_{\ell}}\dots w_{1}t^{\varepsilon_{1}}ta^{mp}$ . Let $u=w_{\ell}t^{\varepsilon_{\ell}}\dots w_{1}t^{\varepsilon_{1}}$ . If $n\leqslant|u|$ , then $d_{A}(\pi(w(n)),\pi(w_{t}(n)))=0$ . If $n>|u|$ , then $d_{A}(\pi(w(n)),\pi(w_{t}(n)))\leqslant d_{A}(ta^{i})+d_{A}(a^{j})$ , where $i=\min\{|mp|,n-|u|-1\}*\mathrm{sign}(k)$ and $j=\min\{|k|,n-|u|\}*\mathrm{sign}(k)$ . By (6), $d_{A}(ta^{i})\leqslant C_{2}(1+\log(|i|+1))+D_{2}$ and $d_{A}(a^{j})\leqslant C_{2}\log(|j|+1)+D_{2}$ . Therefore, $d_{A}(\pi(w(n)),\pi(w_{t}(n)))\leqslant 2C_{2}\log(n+1)+C_{2}+2D_{2}$ .
•

Suppose $r=0$ , $\varepsilon_{1}=-1$ and $\ell\geqslant 1$ . Then $w_{t}=w_{\ell}t^{\varepsilon_{\ell}}\dots w_{2}t^{\varepsilon_{2}}w_{1}a^{mp}$ . Let $v=w_{\ell}t^{\varepsilon_{\ell}}\dots w_{2}t^{\varepsilon_{2}}w_{1}$ . If $n\leqslant|v|$ , then $d_{A}(\pi(w(n)),\pi(w_{t}(n)))=0$ . If $n>|v|$ , then $d_{A}(\pi(w(n)),\pi(w_{t}(n)))\leqslant d_{A}(a^{i})+d_{A}(t^{-1}a^{j})$ , where $i=\min\{|mp|,n-|v|\}*\mathrm{sign}(k)$ and $j=\min\{|k|,n-|v|-1\}*\mathrm{sign}(k)$ . By (6), $d_{A}(a^{i})\leqslant C_{2}\log(|i|+1)+D_{2}$ and $d_{A}(t^{-1}a^{j})\leqslant C_{2}(1+\log(|j|+1))+D_{2}$ . Therefore, $d_{A}(\pi(w(n)),\pi(w_{t}(n)))\leqslant 2C_{2}\log(n+1)+C_{2}+2D_{2}$ .

From these three cases we can see that $s(n)\preceq\log(n)$ . Therefore, the normal form given by the identity (5) satisfies the $\log(n)$ –fellow traveler property. ∎

Remark 18.

We note that for the normal form in the proof of Theorem 17 the upper bound $s(n)\preceq\log(n)$ is sharp. Indeed, let $w=a^{mq^{2}}$ for $m>0$ . Then $w_{t}=ta^{mpq}$ . For $n=mq$ we have that $d_{A}(\pi(w(n)),\pi(w_{t}(n)))=d_{A}(a^{mq},ta^{mq-1})=d_{A}(a^{-mq}ta^{mq-1})=d_{A}(ta^{m(q-p)-1})$ . By (6), $d_{A}(ta^{m(q-p)-1})\geqslant C_{1}(1+\log|m(q-p)|)-D_{1}=C_{1}\left(1-\log\left(\frac{q}{q-p}\right)+\log(mq)\right)-D_{1}$ . Therefore, for $n=mq$ we have that:

d_{A}(\pi(w(n)),\pi(w_{t}(n)))\geqslant C_{1}\log(n)-\left(D_{1}+C_{1}\log\left(\frac{q}{q-p}\right)-C_{1}\right).

Therefore, by the triangle inequality we get that for all $n$ :

d_{A}(\pi(w(n)),\pi(w_{t}(n)))\geqslant C_{1}\log(n)-\left(D_{1}+C_{1}\log\left(\frac{q}{q-p}\right)-C_{1}+2q\right).

This implies that $\log(n)\preceq s(n)$ .

Remark 19.

Let us be given a normal form of $BS(p,q)$ for $1\leqslant p<q$ satisfying the $f(n)$ –fellow traveler property. We denote by $m_{a},m_{a^{-1}},m_{t}$ and $m_{t^{-1}}$ the functions which send the normal form of a group element $g\in BS(p,q)$ to the normal form of a group element $ga,ga^{-1},gt$ and $gt^{-1}$ , respectively. One can notice that the functions $m_{a},m_{a^{-1}},m_{t}$ and $m_{t^{-1}}$ cannot be all computed in $o(n\log n)$ time on a one–tape Turing machine. Indeed, suppose each of the functions $m_{a},m_{a^{-1}},m_{t}$ and $m_{t^{-1}}$ is computed on a one–tape Turing machine in $o(n\log n)$ time. Hartmanis [9] and, independently, Trachtenbrot [12] showed that a language recognized on a one–tape Turing machine in $o(n\log n)$ time must be regular. This fact and the pumping lemma imply that if each of the functions $m_{a},m_{a^{-1}},m_{t}$ and $m_{t^{-1}}$ is computed on a one–tape Turing machine in $o(n\log n)$ time, then the normal form satisfies the bounded length difference property, so it is quasigeodesic; for the proof see [11, Theorem 4]. Thus, by Theorem 14, we arrive at a contradiction. However, it can be verified that for the normal form given by the identity (5) the functions $m_{a},m_{a^{-1}},m_{t}$ and $m_{t^{-1}}$ can be computed in $O(n)$ time using a more powerful computational model – a two–tape Turing machine. Though this verification is not difficult we omit it as it is out of scope of this paper.

5.2 Wreath product $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$

We consider the wreath product $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}=\langle a,b,c\,|\,[a^{i_{1}}b^{j_{1}}ca^{-i_{1}}b^{-j_{1}},a^{i_{2}}b^{j_{2}}ca^{-i_{2}}b^{-j_{2}}]=e,ab=ba,c^{2}=e\rangle$ . This group is non–finitely presented, so by Theorem 15 it does not admit a quasigeodesic normal form satisfying the $f(n)$ –fellow traveler property. In Theorem 20 we will show that $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ admits a quasiregular normal form satisfying the $\sqrt{n}$ –fellow traveler property.

Every group element of $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ can be written as a pair $(\varphi,z)$ , where $\varphi:\mathbb{Z}^{2}\rightarrow\mathbb{Z}_{2}$ is a function such that $\varphi(\xi)$ is not equal to the identity for at most finitely many $\xi\in\mathbb{Z}^{2}$ and $z\in\mathbb{Z}^{2}$ . For the group $\mathbb{Z}^{2}=\{(x,y)\,|\,x,y\in\mathbb{Z}\}$ we denote by $a$ and $b$ the generators $a=(1,0)$ and $b=(0,1)$ . The group $\mathbb{Z}^{2}$ is canonically embedded in $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ by mapping $\xi\in\mathbb{Z}^{2}$ to $(\varphi_{e},\xi)$ , where $\varphi_{e}:\mathbb{Z}^{2}\rightarrow\mathbb{Z}_{2}$ sends every element of $\mathbb{Z}^{2}$ to the identity $e\in\mathbb{Z}_{2}$ . We denote by $c$ the nontrivial element of $\mathbb{Z}_{2}$ . The group $\mathbb{Z}_{2}$ is canonically embedded in $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ by mapping $c$ to $(\varphi_{c},(0,0))$ , where $\varphi_{c}:\mathbb{Z}^{2}\rightarrow\mathbb{Z}_{2}$ is a function such that $\varphi_{c}(\xi)=e$ if $\xi\neq(0,0)$ and $\varphi_{c}((0,0))=c$ . We will identify $a,b$ and $c$ with the group elements $(\varphi_{e},a)$ , $(\varphi_{e},b)$ and $(\varphi_{c},(0,0))$ in $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ , respectively. The set $A=\{a,b,c\}$ generates the group $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ .

Theorem 20.

The wreath product $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ admits a quasiregular normal form satisfying the $\sqrt{n}$ –fellow traveler property.

Proof.

Let $\Gamma$ be the infinite directed graph shown in Fig. 6 which is isomorphic to $\left(\mathbb{N};\mathrm{S}\right)$ , where $\mathrm{S}$ is the successor function $\mathrm{S}(n)=n+1$ . The vertices of $\Gamma$ are identified with elements of $\mathbb{Z}^{2}$ , each vertex in $V(\Gamma)\setminus\{(0,0)\}$ has exactly one ingoing and one outgoing edges and the vertex $(0,0)$ has one outgoing edge and no ingoing edges. Let $\tau:\mathbb{N}\rightarrow\mathbb{Z}^{2}$ be the mapping such that $\tau(0)=(0,0)$ and, for $k>0$ , $\tau(k)=(x,y)$ is the end vertex of a directed path in $\Gamma$ of length $k$ which starts in the vertex $(0,0)$ .

Now we define a normal form in the group $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ as follows. Let $g=(\varphi,z)\in\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ , where $\varphi:\mathbb{Z}^{2}\rightarrow\mathbb{Z}_{2}$ and $z\in\mathbb{Z}^{2}$ . Let $u_{0}=c$ if $\varphi(\tau(0))=c$ and $u_{0}=\varepsilon$ if $\varphi(\tau(0))=e$ . We denote by $m$ the maximum $m=\max\{i\,|\,\varphi(\tau(i))=c\}$ ; if $\varphi(\xi)=e$ for all $\xi$ then we put $m=0$ . For a given integer $i\in\left[1,m\right]$ , let $\alpha_{i}=a,b,a^{-1}$ and $b^{-1}$ if $\tau(i)-\tau(i-1)$ is equal to $(1,0)$ , $(0,1)$ , $(-1,0)$ and $(0,-1)$ , respectively, and let $\beta_{i}=c$ if $\varphi(\tau(i))=c$ and $\beta_{i}=\varepsilon$ if $\varphi(\tau(i))=e$ . Let $u_{i}=\alpha_{i}\beta_{i}$ for $i\in\left[1,m\right]$ and $u$ be the concatenation $u=u_{0}u_{1}\dots u_{m}$ .

Let $l$ be the integer for which $\tau(l)=z$ . If $l>m$ , for a given $i\in\left[1,l-m\right]$ let $v_{i}=a,b,a^{-1}$ and $b^{-1}$ if $\tau(m+i)-\tau(m+i-1)$ is equal to $(1,0)$ , $(0,1)$ , $(-1,0)$ and $(0,-1)$ , respectively. If $l<m$ , for a given $i\in\left[1,m-l\right]$ let $v_{i}=a,b,a^{-1}$ and $b^{-1}$ if $\tau(m-i)-\tau(m-i+1)$ is equal to $(1,0)$ , $(0,1)$ , $(-1,0)$ and $(0,-1)$ , respectively. If $l=m$ , let $v=\varepsilon$ . If $l\neq m$ , let $v=v_{1}\dots v_{k}$ , where $k=|l-m|$ .

Finally we define a normal form $w$ of the element $g=(\varphi,z)$ as a concatenation of $u$ and $v$ : $w=uv$ . Informally speaking, the normal form $w$ is obtained as follows. Imagine the lamplighter who moves along the graph $\Gamma$ starting from $(0,0)$ writing $a,a^{-1},b$ and $b^{-1}$ depending whether it moves right, left, up and down, respectively. The lamplighter writes $c$ if the lamp at the current position $(x,y)\in\mathbb{Z}^{2}$ is lit: $\varphi((x,y))=c$ . After the lamplighter reaches the position $f(\tau(m))$ it either moves further along $\Gamma$ , if $l>m$ , or goes back along $\Gamma$ , if $l<m$ , until it reaches the position $\tau(l)=z$ ; while moving it writes $a,a^{-1},b$ and $b^{-1}$ depending whether it moves right, left, up and down, respectively. For illustration let us consider the group element $h\in\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ shown in Fig. 6: a black square means that the lamp at the current position is lit, i.e., $\varphi((x,y))=c$ , a white square means that the lamp at the current position is unlit, i.e., $\varphi((x,y))=e$ , and a black circle shows the position of the lamplighter $z$ and that the lamp at this position is lit, i.e., $\varphi(z)=c$ . For this group element $h$ the word $u$ is as follows:

\begin{split}u=acba^{-1}a^{-1}b^{-1}cb^{-1}caaabbba^{-1}ca^{-1}a^{-1}a^{-1}b^{-1}b^{-1}cb^{-1}b^{-1}aacaaabcbbcbcbc\\ a^{-1}ca^{-1}a^{-1}a^{-1}a^{-1}a^{-1}cb^{-1}cb^{-1}b^{-1}b^{-1}b^{-1}cb^{-1}acacaaaaac,\end{split}

and the word $v$ is as follows:

v=a^{-1}a^{-1}a^{-1}a^{-1}a^{-1}a^{-1}a^{-1}bbbbbbaaaaaab^{-1}b^{-1}b^{-1}b^{-1}b^{-1}a^{-1}a^{-1}a^{-1},

and the normal form of $h$ is a concatenation of $u$ and $v$ . The described normal form of $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ is prefix–closed, so it is quasiregular. Let us show that it satisfies the $\sqrt{n}$ –fellow traveler property.

We start with a pair of group elements $g=(\varphi,z)$ and $ga=(\varphi,z^{\prime})$ , where $z^{\prime}=z+(1,0)$ . Let $l^{\prime}$ be the integer for which $\tau(l^{\prime})=z^{\prime}$ . Let $w_{a}=u_{a}v_{a}$ be the normal form of $ga$ . We first notice that $d_{A}(\pi(w(n)),\pi(w_{a}(n)))$ can be bounded from above by $|l-l^{\prime}|$ for every $n$ :

d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant|l-l^{\prime}|.

(7)

For a given $p=(x,y)\in\mathbb{Z}^{2}$ , let $r(p)=\max\{|x|,|y|\}$ and $k(p)$ be an integer for which $\tau(k(p))=p$ . One can notice the following lower and upper bounds for $k(p)$ :

(2r(p)-1)^{2}-1\leqslant k(p)\leqslant(2r(p)+1)^{2}-1.

(8)

In particular, (8) implies that $(2r(z)-1)^{2}-1\leqslant l\leqslant(2r(z)+1)^{2}-1$ and $(2r(z^{\prime})-1)^{2}-1\leqslant l^{\prime}\leqslant(2r(z^{\prime})+1)^{2}-1$ . Therefore, $|l-l^{\prime}|\leqslant 4(r(z^{\prime})+r(z))|r(z^{\prime})-r(z)+1|$ . Since $|r(z^{\prime})-r(z)|\leqslant 1$ , we obtain that $|l-l^{\prime}|\leqslant 8(r(z)+r(z^{\prime}))$ . Therefore, by (7) we obtain that for every $n$ :

d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 16r(z)+8,\,\,d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 16r(z^{\prime})+8.

(9)

Now we notice that $u=u_{a}$ . Therefore, if $n\leqslant|u|$ , then $d_{A}(\pi(w(n)),\pi(w_{a}(n)))=0$ . For $n>|u|$ we consider the following three cases:

•

Suppose $l^{\prime}\geqslant l\geqslant m$ . If $|u|<n\leqslant|u|+(l-m)$ , then $d_{A}(\pi(w(n)),\pi(w_{a}(n)))=0$ . By (9) we have that $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 16r(z)+8$ . Therefore, by (8), $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8(\sqrt{l+1}+1)+8$ . If $n>|u|+(l-m)$ , then $n\geqslant l$ . Therefore, $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8\sqrt{n+1}+16$ . Similarly, suppose $l\geqslant l^{\prime}\geqslant m$ . If $|u|<n\leqslant|u|+(l^{\prime}-m)$ , then $d_{A}(\pi(w(n)),\pi(w_{a}(n)))=0$ . By (9) we have that $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 16r(z^{\prime})+8$ . Therefore, by (8), $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8(\sqrt{l^{\prime}+1}+1)+8$ . If $n>|u|+(l^{\prime}-m)$ , then $n\geqslant l^{\prime}$ . Therefore, $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8\sqrt{n+1}+16$ .
•

Suppose $l^{\prime}\geqslant m\geqslant l$ . By (9) we have that $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 16r(z)+8$ . Therefore, by (8), $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8(\sqrt{l+1}+1)+8$ . If $n>|u|$ , then $n\geqslant l$ . Therefore, $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8\sqrt{n+1}+16$ . Similarly, suppose $l\geqslant m\geqslant l^{\prime}$ . By (9) we have that $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 16r^{\prime}(z)+8$ . Therefore, by (8), $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8(\sqrt{l^{\prime}+1}+1)+8$ . If $n>|u|$ , then $n\geqslant l^{\prime}$ . Therefore, $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8\sqrt{n+1}+16$ .
•

Suppose $m\geqslant l^{\prime}\geqslant l$ . If $|u|<n\leqslant|u|+(m-l^{\prime})$ , then $d_{A}(\pi(w(n)),\pi(w_{a}(n)))=0$ . By (9) we have that $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 16r^{\prime}(z)+8$ . Therefore, by (8), $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8(\sqrt{l^{\prime}+1}+1)+8$ . If $n>|u|+(m-l^{\prime})$ , then $n\geqslant l^{\prime}$ . Therefore, $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8\sqrt{n+1}+16$ . Similarly, suppose $m\geqslant l\geqslant l^{\prime}$ . If $|u|<n\leqslant|u|+(m-l)$ , then $d_{A}(\pi(w(n)),\pi(w_{a}(n)))=0$ . By (9) we have that $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 16r(z)+8$ . Therefore, by (8), $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8(\sqrt{l+1}+1)+8$ . If $n>|u|+(m-l)$ , $n\geqslant l$ . Therefore, $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\leqslant 8\sqrt{n+1}+16$ .

From these three cases we can see that $d_{A}(\pi(w(n)),\pi(w_{a}(n)))\preceq\sqrt{n}$ .

Now let us consider a pair of group elements $g=(\varphi,z)$ and $gc=(\varphi^{\prime},z)$ , where $\varphi(\gamma)=\varphi^{\prime}(\gamma)$ if $\gamma\neq z$ and $\varphi^{\prime}(\gamma)=\varphi(\gamma)c$ if $\gamma=z$ . There are two different cases to consider: $l\geqslant m$ and $l<m$ . Let $w_{c}=u_{c}v_{c}$ be the normal form of $gc$ . The case $l\geqslant m$ is straightforward: $d_{A}(\pi(w(n)),\pi(w_{c}(n)))\leqslant 1$ for all $n$ .

Now let us consider the case $l<m$ . We denote by $\widetilde{u}$ the following prefix of $u$ : $\widetilde{u}=u_{0}u_{1}\dots u_{m-1}\alpha_{m}$ . If $n\leqslant|\widetilde{u}|$ , then $d_{A}(\pi(w(n)),\pi(w_{c}(n)))=0$ . Suppose now that $n>|\widetilde{u}|$ . We assume that $\beta_{m}=\varepsilon$ . Let $\widetilde{v}$ be the suffix of $w(n)$ which follows $\widetilde{u}$ : $w(n)=\widetilde{u}\widetilde{v}$ .

Let $z_{0}=\tau(m)$ and $z_{1}=\tau(k)$ be a position of the lamplighter for a group element $\pi(w(n))$ . We denote by $(x_{0},y_{0})$ and $(x_{1},y_{1})$ the coordinates of $z_{0}$ and $z_{1}$ , respectively. There are two different cases: $\widetilde{v}=\alpha_{m+1}\beta_{m+1}\dots\beta_{k-1}\alpha_{k}$ or $\widetilde{v}=\alpha_{m+1}\beta_{m+1}\dots\alpha_{k}\beta_{k}$ , where $\beta_{k}=c$ . Let us analyze these two cases:

•

Suppose $\widetilde{v}=\alpha_{m+1}\beta_{m+1}\dots\alpha_{k}$ . Then $w_{c}(n)=\widetilde{u}c\alpha_{m+1}\beta_{m+1}\dots\alpha_{k-1}\beta_{k-1}$ , so we have that:

$\pi(w_{c}(n))=\pi(w(n))a^{x_{0}-x_{1}}b^{y_{0}-y_{1}}ca^{x_{1}-x_{0}}b^{y_{1}-y_{0}}\alpha_{k}^{-1}.$

Therefore, $d_{A}(\pi(w(n)),\pi(w_{c}(n)))\leqslant 2|x_{1}-x_{0}|+2|y_{1}-y_{0}|+2\leqslant 2(|x_{1}|+|y_{1}|+|x_{0}|+|y_{0}|+1)\leqslant 2(2r(z_{1})+2r(z_{0})+1)$ . By (8), $2r(z_{0})\leqslant\sqrt{m+1}+1$ and $2r(z_{1})\leqslant\sqrt{k+1}+1$ . Therefore, $d_{A}(\pi(w(n)),\pi(w_{c}(n)))\leqslant 2(\sqrt{k+1}+1+\sqrt{m+1}+1+1)$ . Since $n\geqslant k\geqslant m$ , we have that $d_{A}(\pi(w(n)),\pi(w_{c}(n)))\leqslant 4\sqrt{n+1}+6$ .
•

Suppose $\widetilde{v}=\alpha_{m+1}\beta_{m+1}\dots\alpha_{k}c$ . Then $w_{c}(n)=\widetilde{u}c\alpha_{m+1}\beta_{m+1}\dots\beta_{k-1}\alpha_{k}$ , so we have that:

$\pi(w_{c}(n))=\pi(w(n))a^{x_{0}-x_{1}}b^{y_{0}-y_{1}}ca^{x_{1}-x_{0}}b^{y_{1}-y_{0}}c.$

Therefore, $d_{A}(\pi(w(n)),\pi(w_{c}(n)))\leqslant 2|x_{1}-x_{0}|+2|y_{1}-y_{0}|+2$ . By exactly the same argument as in the previous case we have that $d_{A}(\pi(w(n)),\pi(w_{c}(n)))\leqslant 4\sqrt{n+1}+6$ .

Therefore, if $\beta_{m}=\varepsilon$ , we have that $d_{A}(\pi(w(n)),\pi(w_{c}(n)))\preceq\sqrt{n}$ . If $\beta_{m}=c$ , then swapping the role of $w(n)$ and $w_{c}(n)$ in the argument above yields $d_{A}(\pi(w(n)),\pi(w_{c}(n)))\preceq\sqrt{n}$ . Thus we finally proved that $s(n)\preceq\sqrt{n}$ . ∎

Remark 21.

We note that for the normal form in the proof of Theorem 20 the upper bound $s(n)\preceq\sqrt{n}$ is sharp. A proof of this is as follows. For a given $m\geqslant 0$ let $\varphi_{m}:\mathbb{Z}^{2}\rightarrow\mathbb{Z}_{2}$ be a function for which $\varphi_{m}(\tau(m))=c$ and $\varphi_{m}(p)=e$ for $p\neq\tau(m)$ . We denote by $g_{m}$ the group element $g_{m}=(\varphi_{m},(0,0))$ . Let $w_{m}$ and $w_{ma}$ be the normal forms of $g_{m}$ and $g_{m}a$ , respectively. Let $n=m+1$ and $z_{m}=\tau(m)$ . Then $\pi(w_{m}(n))=(\varphi_{m},z_{m})$ and $\pi(w_{ma}(n))=(\varphi_{0},z_{m})$ . Let $z_{m}=(x_{m},y_{m})$ . The distance $d_{A}(\pi(w_{m}(n)),\pi(w_{ma}(n)))$ is equal to $2(|x_{m}|+|y_{m}|+1)$ . Indeed, in order to obtain $g_{m}a$ from $g_{m}$ the lamplighter moves from the position $(x_{m},y_{m})$ to the position $(0,0)$ choosing a shortest route, switch on a lamp, moves back to the position $(x_{m},y_{m})$ and switch off a lamp. In particular, $d_{A}(\pi(w_{m}(n)),\pi(w_{ma}(n)))\geqslant 2r(z_{m})+1$ . By (8), we have that $(2r(z_{m})+1)^{2}\geqslant m+1$ . Therefore, $d_{A}(\pi(w_{m}(n)),\pi(w_{ma}(n)))\geqslant\sqrt{n}$ . This implies that $\sqrt{n}\preceq s(n)$ .

6 Discussion and Open Questions

Theorems 14 and 15 show that for a finitely presented group with the strongly–super–polynomial Dehn function or a non–finitely presented group there exists no quasigeodesic normal form satisfying the $f(n)$ –fellow traveler property. The following question is apparent from these results.

1.

Is there a quasigeodesic normal form satisfying the $f(n)$ –fellow traveler property for some finitely presented non–automatic group with the Dehn function which is not strongly–super–polynomial? Some interesting candidates to consider this question include, for example, the Heisenberg group $\mathcal{H}_{3}(\mathbb{Z})$ and the higher Heisenberg groups $\mathcal{H}_{2k+1}(\mathbb{Z})$ , $k>1$ .

Theorems 17 and 20 show the existence of a quasiregular normal form satisfying the $f(n)$ –fellow traveler property for Baumslag–Solitar groups $BS(p,q)$ , $1\leqslant p<q$ , and the wreath product $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ . We leave the following question for future consideration.

2.

Is there a quasiregular normal form satisfying the $f(n)$ –fellow traveler property for the fundamental group of a torus bundle over a circle $\mathbb{Z}^{2}\rtimes_{A}\mathbb{Z}$ , where $A\in\mathrm{GL}(2,\mathbb{Z})$ has two real eigenvalues not equal to $\pm 1$ ? Recall that the latter guarantees that $\mathbb{Z}^{2}\rtimes_{A}\mathbb{Z}$ has at least exponential Dehn function, so no quasigeodesic normal form satisfying the $f(n)$ –fellow traveler property exists in this case.

In addition to that there are other questions that might be worth considering. Is there a quasiregular normal form satisfying the $f(n)$ –fellow traveler proper for $BS(p,q)$ , $1\leqslant p<q$ , for some $f\ll\log(n)$ ? Is there a quasiregular normal form satisfying the $f(n)$ –fellow traveler proper for $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$ , $1\leqslant p<q$ , for some $f\ll\sqrt{n}$ ? What are the other examples of groups which admit quasiregular normal forms satisfying the $f(n)$ –fellow traveler property?

Acknowledgments

The authors thank the anonymous reviewer for useful comments.

References

[1] Berdinsky, D., Elder, M., Taback, J.: On the geometry of Cayley automatic groups. International Journal of Algebra and Computation 32, 383–409 (2022)
[2] Berdinsky, D., Trakuldit, P.: Towards quantitative classification of Cayley automatic groups. East–West J. of Mathematics 20(2), 107–124 (2018)
[3] Berdinsky, D., Trakuldit, P.: Measuring closeness between Cayley automatic groups and automatic groups. In: Klein, S., Martín-Vide, C., Shapira, D. (eds.) Language and Automata Theory and Applications, vol. 10792, pp. 245–257. Springer International Publishing (2018)
[4] Bridson, M.R.: Combings of groups and the grammar of reparameterization. Comment. Math. Helv. 78, 752–771 (2003)
[5] Bridson, M.R., Gilman, R.H.: Formal language theory and the geometry of 3–manifolds. Commentarii Mathematici Helvetici 71(1), 525–555 (1996)
[6] Burillo, J., Elder, M.: Metric properties of Baumslag–Solitar groups. International Journal of Algebra and Computation 25(5), 799–811 (2015)
[7] Elder, M., Taback, J.: $C$ –graph automatic groups. Journal of Algebra 413, 289–319 (2014)
[8] Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M.S., Thurston, W.P.: Word Processing in Groups. Jones and Barlett Publishers. Boston, MA (1992)
[9] Hartmanis, J.: Computational complexity of one–tape Turing machine computations. Journal of the Association of Computing Machinery 15, 411–418 (1968)
[10] Kharlampovich, O., Khoussainov, B., Miasnikov, A.: From automatic structures to automatic groups. Groups, Geometry and Dynamics 8(1), 157–198 (2014)
[11] Kruengthomya, P., Berdinsky, D.: Cayley Linear–Time Computable Groups. journal of Groups, Complexity, Cryptology Volume 15, Issue 2, 1–22 (Apr 2024)
[12] Trachtenbrot, B.: Turing computations with logarithmic delay. Algebra i Logica 3 (1964), (In Russian) English translation in U. of California Computing Center, Tech. Rep. No. 5, Berkeley, Calif., 1966.

Extending the Synchronous Fellow Traveler Property

1 Introduction

2 Preliminaries

Definition 1 (the fellow traveler property).

Definition 2 (⪯\preceq relation).

Definition 3 (≪\ll relation).

Example 4.

3 The f​(n)f(n)–Fellow Traveler Property

Definition 5 (the f​(n)f(n)–fellow traveler property).

3.1 Normal forms satisfying the f​(n)f(n)–fellow traveler property

3.2 Quasigeodesic and quasiregular normal forms

Definition 6 (quasigeodesic normal form).

Definition 7 (quasiregular normal form).

Definition 8 (quasiprefix–closed normal form).

Theorem 9.

Proof.

4 Quasigeodesic Normal Forms

4.1 Non–existence theorems

Definition 10 (combinatorial area).

Definition 11 (Dehn function).

Definition 12 (strongly–super–polynomial function).

Lemma 13.

Proof.

Theorem 14.

Proof.

Theorem 15.

Proof.

4.2 Relation with a Cayley distance function

Theorem 16.

Proof.

5 Quasiregular Normal Forms

5.1 Baumslag–Solitar groups

Theorem 17.

Proof.

Remark 18.

Remark 19.

5.2 Wreath product ℤ2≀ℤ2\mathbb{Z}_{2}\wr\mathbb{Z}^{2}

Theorem 20.

Proof.

Remark 21.

6 Discussion and Open Questions

Acknowledgments

References

Definition 2 ( $\preceq$ relation).

Definition 3 ( $\ll$ relation).

3 The $f(n)$ –Fellow Traveler Property

Definition 5 (the $f(n)$ –fellow traveler property).

3.1 Normal forms satisfying the $f(n)$ –fellow traveler property

5.2 Wreath product $\mathbb{Z}_{2}\wr\mathbb{Z}^{2}$