Finitely generated semiautomatic groups

Abstract

The present work shows that Cayley automatic groups are semiautomatic and exhibits some further constructions of semiautomatic groups; as a consequence, various undecidability results for Cayley automatic groups hold also for finitely generated semiautomatic groups. However, in spite of their generality, the word problem of finitely generated semiautomatic groups is still solvable in quadratic time. Furthermore, the present work establishes that every finitely generated group of nilpotency class three is semiautomatic. It remains open whether the finitely generated semiautomatic groups are a strict superclass of the Cayley automatic groups.

Keywords

Nilpotent groups automatic groups automatic structures semiautomatic structures Cayley automatic groups semigroups finitely generated groups

1. Introduction

Hodgson [8 ,9] as well as Khoussainov and Nerode [13] initiated the study of automatic structures, including that of groups. In their approach, such a group is given by a regular set A as the domain (denoting the representatives of the group) such that both, the group operation ∘ and the equality =, are automatic; that is, there is an automaton which reads the convoluted tuples $(x, y, z)$ or $(x, y)$ and decides whether such a tuple satisfies $x \circ y = z$ or $x = y$ , respectively. Here, for $x = x_{1} x_{2} \dots x_{m}$ and $y = y_{1} y_{2} \dots y_{n}$ with $x_{i}, y_{i} \in Σ$ , the convolution of the pair $(x, y)$ is the string $\begin{matrix} (\binom{x_{1}}{y_{1}}) (\binom{x_{2}}{y_{2}}) \dots (\binom{x_{max {m, m}}}{y_{max {m, n}}}) \end{matrix}$ over the new alphabet ${(Σ \cup {#})}^{2}$ , where $x_{i}$ (respectively $y_{i}$ ) is taken to be # in case of $i > m$ (respectively, $i > n$ ). The convolution over triples or tuples in general is defined similarly. The advantage of this setting is that every function and relation definable in the language of group theory using parameters from the group is again automatic. Furthermore, automata providing the mappings can be found algorithmically. This also leads to the conclusion that for every fixed automatic group, the first-order theory is decidable [13]. Furthermore, automatic functions are precisely those which can be computed in linear time by a position-faithful one-tape Turing machine [3], thus the automatic functions coincide with the smallest reasonable time complexity class for functions.

Epstein, Cannon, Holt, Levy, Paterson and Thurston [6] argued that in the above formalisation, automaticity is, at least from the viewpoint of finitely generated groups, too restrictive. They furthermore wanted that the representatives of the group elements are given as words over the generators, leading to more meaningful representatives than arbitrary strings. Their concept of automatic groups led, for finitely generated groups, to a larger class of groups, though, by definition, it of course does not include groups which require infinitely many generators; groups with infinitely many generators, to some extent, were covered in the notion of automaticity by Hodgson, Khoussainov and Nerode. Nies and Thomas [16,17] provide results which contrast and compare these two notions of automaticity and give an overview on results for groups which are automatic in the sense of Hodgson, Khoussainov and Nerode.

Kharlampovich, Khoussainov and Miasnikov [12] generalised the notion further to Cayley automatic groups. Here a finitely generated group $(A, \circ)$ is Cayley automatic iff the domain A is a regular set, for every group element there is a unique representative in A and, for every $a \in A$ , the mapping $x \mapsto x \circ a$ is automatic. Note that the above requires multiplication by constants to be automatic only from one side; when multiplication by a constant from both sides are automatic, then the group is called Cayley biautomatic.

Finitely generated Cayley automatic groups have word problem decidable in quadratic time, carrying over the corresponding result from the two previous versions of automaticity. As opposed to the case of automatic groups (in the original sense of Hodgson), Miasnikov and Šunić [15] showed that several natural problems like the conjugacy problem can be undecidable for some Cayley automatic groups.

Jain, Khoussainov, Stephan, Teng and Zou [11] investigated the general approach where, in a structure for some relations and functions, it is only required that the versions of the functions or relations with all but one variable fixed to constants is automatic. Here the convention is to put the automatic domains, functions and relations before a semicolon and the semiautomatic relations after the semicolon. For a group, the semiautomatic group $(A, \circ; =)$ would be a structure where the domain A is regular, the group operation (with both inputs) is automatic and for each fixed element $a \in A$ the set ${b \in A : b = a}$ is regular – note that group elements might have several representatives in semiautomatic groups.

In the present work, for any group, ε represents the neutral element. One of the basic results obtained is that the notion $(A, \circ; =)$ collapses to an automatic group (in the sense of Hodgson, Khoussainov and Nerode), as $\begin{matrix} a = b \Leftrightarrow \exists c [a \circ c = ε and b \circ c = ε] . \end{matrix}$ For semiautomatic groups, the two interesting group structures are $(A, =; \circ)$ and $(A; \circ, =)$ . In the first one, the equality is automatic, while in the second one, both the group operation and the equality are only semiautomatic. If a group is finitely generated, then the definition of being Cayley biautomatic is the same as having a presentation of the form $(A, =; \circ)$ .

Finitely generated semiautomatic groups share with the other types of automatic groups one important property: The word problem can be decided in quadratic time and the algorithm is the same as known for the Cayley automatic groups [12]. Thus finitely generated groups with an undecidable or very complex word problem are not semiautomatic.

One of the problems left open in the present work is the following: Is every finitely generated semiautomatic group Cayley automatic? More generally, does every semiautomatic group admit a presentation where the multiplication with a fixed group element from one side only is semiautomatic and the equality is automatic?

2. Basic facts and examples

Finitely generated groups are groups for which there is a set $a_{1}, \dots, a_{n}$ of generators such that every element of the group can be expressed as a finite word over the $a_{i}$ and $a_{i}^{- 1}$ where a word like $a_{1} a_{1} a_{2} a_{1}^{- 1}$ then stands for $a_{1} \circ a_{1} \circ a_{2} \circ a_{1}^{- 1}$ . A group $(A, \circ)$ has nilpotency class 3 if for all elements $x_{1}, y_{1}, y_{2}, y_{3}$ in the group it holds that the element $x_{4}$ of the sequence given inductively for $k = 1, 2, 3$ by $\begin{matrix} x_{k + 1} = x_{k} \circ y_{k} \circ x_{k}^{- 1} \circ y_{k}^{- 1} \end{matrix}$ is the neutral element ε of A. Thus there are some rules to move one element over another element by generating some spin-off element, say $\begin{matrix} a_{i} \circ a_{i^{'}} = a_{i^{'}} \circ a_{i} \circ b_{j} \end{matrix}$ and the elements of the form $x \circ y \circ x^{- 1} \circ y^{- 1}$ generate a commutative subgroup B of the group. Furthermore, B is a normal subgroup of A, that is, for all $x \in B$ and $y \in A$ , the element $y \circ x \circ y^{- 1}$ is also in B. The factor group $A / B = {x \circ B : x \in A}$ with $x = y$ if $x \circ B = y \circ B$ as sets is also commutative and finitely generated; here $(x \circ B) \circ (y \circ B) = (x \circ (y \circ B \circ y^{- 1})) \circ (y \circ B) = (x \circ y) \circ B \circ B = (x \circ y) \circ B$ and these equalities use that $B = y \circ B \circ y^{- 1}$ for all $y \in A$ . Thus $A / B$ is isomorphic to a finite product of the form $\begin{matrix} Z^{r} \times {0, 1, \dots, p_{r + 1} - 1} \times \dots \times {0, 1, \dots, p_{n} - 1} \end{matrix}$ for some $n, r ⩽ n$ and $p_{r + 1}, \dots, p_{n} ⩾ 2$ . This is used in the construction of Theorem 8. Note that if $a_{i}^{p_{n}} = ε$ in the factor group, it means that $a_{i}^{p_{n}} \in B$ in the original group B and the automatic mappings for multiplication with generators have to take care of this fact.

In the case of a finitely generated group, it can be shown that, for every fixed $a \in A$ , the mappings $x \mapsto x \circ a$ and $x \mapsto a \circ x$ are automatic by proving this fact only for the generators and their inverses. This fact is used at several places in the paper.

Furthermore, for a semiautomatic group with generators $a_{1}, a_{2}, \dots, a_{n}$ , it can be checked in quadratic time whether a word w over these generators is equal to the neutral element ε. The idea is to start with a representative of ε and then, from the front to the end of the word, multiply the representative with the corresponding generator or its inverse depending on the symbol of the word read. When the whole word is processed, a finite automaton is used for checking whether the group element is equal to ε. That the algorithm is in quadratic time stems from the fact that each of the automatic functions involved makes the word only longer by a constant amount of symbols and that the running of the automatic functions is in linear time. Thus, the maximum length is bounded by a constant multiplied with the length of the word involved. This gives the overall quadratic bound of the decision algorithm. The details are more or less the same as in the case of Cayley automatic groups as well as Thurston automatic groups and follow the known proof [6,12].

The constructions in Theorem 8 and elsewhere use that there is a copy of the integers $(Z, +, =, <)$ which is automatic including equality and order; this is well-known since the beginning of automatic structures [8,13]. The automatic representation follows the well-known algorithm for verifying an addition in the examples

3 8 3 8 8 2 8 3 1 2 3 4 + 1 2 3 4 5 6 7 + 5 6 = 3 9 6 2 2 8 5 0 = 1 2 9 0

where the algorithm goes from the end to the front, adding the two top digits and taking the carry digit into account. For automatic structures where the strings start in the front at the same position – instead of ending at the same position as the numbers in the example – one just codes the numbers in the reverse order, so 1234 would be stored as 4321 and 56 as 65 so that at the start the first two digits 4,6 have to be added, and then the next digits 3,5 plus carry and so on.

In summary, the natural numbers can be coded as binary or decimal numbers in reverse order so that the symbol $a_{n}$ of the input always refers to the digit of $2^{n}$ or $10^{n}$ , respectively. For uniqueness, leading zeroes are not allowed in the representation. Then the usual binary or decimal addition of such numbers invokes an addition and the following automatic order is the order on the decimals: $a_{0} a_{1} \dots a_{n} < b_{0} b_{1} \dots b_{m}$ iff $n < m$ or $n = m$ and the largest k with $a_{k} \neq b_{k}$ has that $a_{k} < b_{k}$ in the order of the digits. Having addition and order on the binary or decimal natural numbers, the representation can be extended to that of $(Z, +, =, <)$ by representing each integer z as a pair of two natural numbers $(x, y)$ with $z = x - y$ . Then $(x_{1}, y_{1}) = (x_{2}, y_{2})$ iff $x_{1} + y_{2} = x_{2} + y_{1}$ what can be checked in this representation. Multiplication of an integer z with a fixed convoluted vector like $(1, 3, 2)$ can be implemented as a constant repeated adding $(z, 0, 0) + (0, z, 0) + (0, z, 0) + (0, z, 0) + (0, 0, z) + (0, 0, z)$ for proof purposes; the actual automatic structure can apply slightly more efficient algorithms. Similarly, a convoluted tuple $(z_{1}, \dots, z_{k})$ can be mapped to $v_{1} \cdot z_{1} + v_{2} \cdot z_{2} + \dots + v_{k} \cdot z_{k}$ for fixed vectors $v_{1}, \dots, v_{k}$ in $Z^{h}$ for fixed h. The finitely generated automatic groups (in sense of Khoussainov and Nerode) are fully characterised as those which are given by finite index extension of an Abelian finitely generated group [17,18]; thus all such groups are also automatic in the sense of Thurston. Note for this characterisation, that if a finitely generated group is a finite index extension of some subgroup, then the subgroup which it extends is also finitely generated [19, page 55]. An example for a nilpotent Cayley biautomatic group, that is, a finitely generated semiautomatic group of the form $(A, =; \circ)$ , is the group of all unitriangular $n \times n$ matrices over $Z$ .

Example 1.
Consider the group of all matrices of the form $\begin{matrix} \{(\begin{matrix} 1 & a & d & f \\ 0 & 1 & b & e \\ 0 & 0 & 1 & c \\ 0 & 0 & 0 & 1 \end{matrix}) : a, b, c, d, e, f \in Z\} \end{matrix}$ which is generated by the three generators of the form $\begin{matrix} (\begin{matrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{matrix}) \end{matrix}$ and their inverses $\begin{matrix} (\begin{matrix} 1 & - 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & - 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 1 \end{matrix}) . \end{matrix}$ This group is Cayley biautomatic and has nilpotency class 3; the reason is that the commutators $x^{- 1} \circ y^{- 1} \circ x \circ y$ of two upper unitriangular matrices $x, y$ have 0 in the semidiagonal next to the main diagonal and the commutator of three elements have 0 in the first two semidiagonals next to the main diagonal and that the commutators of four elements are always the identity matrix. It can be represented by convoluted tuples of the form $(a, b, c, d, e, f)$ where $a, b, c, d, e, f$ are integers in any given semiautomatic representation $(Z, +, =; \cdot)$ of the ring of integers.

Note that not every subgroup of the above has a regular domain. For example the subgroup generated by $\begin{matrix} (\begin{matrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}) \end{matrix}$ and their inverses consists of group elements of the form $\begin{matrix} (\begin{matrix} 1 & a & d & f \\ 0 & 1 & b & e \\ 0 & 0 & 1 & c \\ 0 & 0 & 0 & 1 \end{matrix}) \end{matrix}$ where $a = c$ , $a \cdot b = d + e$ and some constraint on f holds (on when f has to be odd and when it has to be even). The equation $a \cdot b = d + e$ implies that this group is not a regular subset of the representation of the unitriangular matrices from Example 1. These dependencies make it difficult to exploit on one hand the Cayley biautomaticity of the unitriangular matrices in their natural representation as a group and on the other hand to embed a given nilpotent group into this group in a way that its domain is a regular subset of the group in the matrix representation. It is conjectured that this is impossible and that there is no way to overcome this; that is, that there are finitely generated groups of nilpotency class 3 which are not Cayley automatic. However, one can generalise the just defined matrix group to have a more general example.
Example 2.
For a given number n of generators with $n ⩾ 3$ , let the group $G_{n}$ be represented by vectors of $4 \times 4$ matrices over the integers of the form $\begin{matrix} (\begin{matrix} 1 & m_{i} & m_{i, j} & m_{i, j, k} \\ 0 & 1 & m_{j} & m_{j, k} \\ 0 & 0 & 1 & m_{k} \\ 0 & 0 & 0 & 1 \end{matrix}) \end{matrix}$ where each coordinate is given by a triple of indices $(i, j, k)$ with $1 ⩽ i < j < k ⩽ n$ of coordinates and the group operation is the component wise matrix multiplication; in a vector of matrices representing a group element, if two different matrices contain, perhaps at different positions, entries with the same indices, then the corresponding numbers have to be the same. For example, all group members in $G_{4}$ are of the form $\begin{array}{l} ((\begin{matrix} 1 & m_{1} & m_{1, 2} & m_{1, 2, 3} \\ 0 & 1 & m_{2} & m_{2, 3} \\ 0 & 0 & 1 & m_{3} \\ 0 & 0 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & m_{1} & m_{1, 2} & m_{1, 2, 4} \\ 0 & 1 & m_{2} & m_{2, 4} \\ 0 & 0 & 1 & m_{4} \\ 0 & 0 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & m_{1} & m_{1, 3} & m_{1, 3, 4} \\ 0 & 1 & m_{3} & m_{3, 4} \\ 0 & 0 & 1 & m_{4} \\ 0 & 0 & 0 & 1 \end{matrix}), \\ (\begin{matrix} 1 & m_{2} & m_{2, 3} & m_{2, 3, 4} \\ 0 & 1 & m_{3} & m_{3, 4} \\ 0 & 0 & 1 & m_{4} \\ 0 & 0 & 0 & 1 \end{matrix})) \end{array}$ and they satisfy that all numbers called $m_{2}$ in these matrices have the same value and also all numbers called $m_{3, 4}$ have the same value. The generators are all the vectors $a_{h}$ where $m_{h} = 1$ and all other entries( $m_{i}$ with $i \neq h$ , $m_{i, j}$ and $m_{i, j, k}$ ) are 0. For example, in $G_{4}$ , $a_{1} \circ a_{1} \circ a_{2}$ is $\begin{matrix} ((\begin{matrix} 1 & 2 & 2 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & 2 & 2 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & 2 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix})) . \end{matrix}$ This group has nilpotency class 3. The group $G_{n}$ is a semiautomatic group where equality is automatic and the group operation is semiautomatic; as a representation one takes a convolution of all the $m_{i}$ , $m_{i, j}$ , $m_{i, j, k}$ which, in turn, are all represented in a fixed representation of the automatic group of integers. The group $G_{n}$ is not the free group of nilpotency class 3: $a_{1}$ and $a_{1}^{- 1} \circ a_{2}^{- 1} \circ a_{1} \circ a_{2}$ commute although they would not do it in the free group of nilpotency class 3.
3. Constructions of semiautomatic groups

Recall that a Cayley automatic group is a finitely generated group $(A, \circ)$ where the domain A is regular, every group element has a unique representative in A and for every $a \in A$ , the mapping $x \mapsto x \circ a$ is automatic. This notion is equivalent to allowing multiple representatives in A for the group elements, but additionally requiring that equality is automatic.

A semiautomatic finitely generated group where the equality is automatic is called Cayley biautomatic, Example 2 is an example of a Cayley biautomatic group. Miasnikov and Šunić [15] showed that there are Cayley automatic groups which are not Cayley biautomatic. They also showed that there are Cayley automatic groups for which the conjugacy problem is undecidable and that the isomorphism problem is also undecidable for the class of Cayley automatic groups.

Berdinsky and Khoussainov [2] have shown that every Baumslag Solitar group is Cayley automatic and Jain, Khoussainov, Stephan, Teng and Zou [11] announced that every Baumslag Solitar group is semiautomatic. This and other results follow now from a general transfer theorem which shows that every Cayley automatic group is semiautomatic.

Theorem 3.
If $(A, =; {x \mapsto x \circ a : a \in A})$ is a Cayley automatic group, then the group has a semiautomatic presentation $(B, x \mapsto x^{- 1}; \circ, =)$ ; in this presentation the domain is regular and the inversion is an automatic function, whereas the equality and the group operation are semiautomatic.
Proof.
Given the Cayley automatic group A as in the statement of the theorem, let $B = {(v, w) : v, w \in A}$ be the set of convoluted pairs $(v, w)$ , where the pair $(v, w)$ stands for the element $v^{- 1} \circ w$ of A. Now $(v, w) \circ (ε, u) = v^{- 1} \circ w \circ ε^{- 1} \circ u = v^{- 1} \circ w \circ u = (v, w \circ u)$ , $(u, ε) \circ (v, w) = u^{- 1} \circ ε \circ v^{- 1} \circ w = {(v \circ u)}^{- 1} \circ w = (v \circ u, w)$ and $(v, w) \circ (w, v) = v^{- 1} \circ w \circ w^{- 1} \circ v = ε$ . As every fixed element $a \in A$ can be represented by either $(ε, a)$ or $(a^{- 1}, ε)$ , multiplication with a fixed group element from either side is automatic. Furthermore, the mapping $(v, w) \mapsto (w, v)$ is automatic and computes the inverse. The set of representations of a fixed element $a \in A$ is the set ${(v, w) : (a, ε) \circ (v, w) = (ε, ε)} = {(v, w) : v \circ a = w}$ , where the latter set is easily seen to be regular. □

The above result shows that the undecidability results for Cayley automatic groups by Miasnikov, Šunić and Ventura [15,20] generalise to finitely generated semiautomatic groups.
Corollary 4.
There is a semiautomatic group $(A; \circ, =)$ for which the conjugacy problem is undecidable. Furthermore, the isomorphism problem for semiautomatic groups is undecidable.

The next result shows that all semiautomatic groups can have an automatic inversion.
Proposition 5.
Every semiautomatic group $(A; \circ, =)$ has a further semiautomatic presentation $(B, x \mapsto x^{- 1}; \circ, =)$ .
Proof.
The proposition is proven by introducing two new symbols, + and −, such that $B = {+, -} \cdot A$ consists of all $+ x$ representing $x \in A$ and $- x$ representing $x^{- 1}$ for $x \in A$ . The inverse is now computed by the function interchanging + and −. For fixed $a \in A$ , $x \mapsto x \circ a$ becomes $+ x \mapsto + (x \circ a)$ and $- x \mapsto - (a^{- 1} \circ x)$ , $x \mapsto a \circ x$ is implemented similarly and ${+ x : x = a} \cup {- x : x = a^{- 1}}$ is the regular set of representatives of a in B. □
Theorem 6.
Assume that $(A, \circ, =)$ is an automatic group (in the sense of Hodgson, Khoussainov and Nerode), $(B; \circ, =)$ is a semiautomatic group and ${ϕ_{b} : b \in B}$ is a family of homomorphisms from A to A such that for each $b, b^{'} \in B$ , $ϕ_{b \circ b^{'}} (a) = ϕ_{b} (ϕ_{b^{'}} (a))$ and each $ϕ_{b}$ is an automatic mapping, then the semidirect product $A ⋊_{ϕ} B$ is also a semiautomatic group (with both equality and group operation being semiautomatic). Here the group operation in $A ⋊_{ϕ} B$ is defined by $(a, b) \circ (a^{'}, b^{'}) = (a \circ ϕ_{b} (a^{'}), b \circ b^{'})$ .
Proof.
Consider the representation set $C = {(a, b, \tilde{a}) : a, \tilde{a} \in A and b \in B}$ , where $(a, b, \tilde{a}) \in C$ stands for $(a, ε) \circ (ε, b) \circ (\tilde{a}, ε)$ in the group $A ⋊_{ϕ} B$ . Now, for a fixed $a^{'} \in A$ , $b^{'} \in B$ and arbitrary $(a, b, \tilde{a}) \in C$ , the multiplications are defined as follows: $\begin{array}{l} (a, b, \tilde{a}) \circ (a^{'}, ε) \mapsto (a, b, \tilde{a} \circ a^{'}); \\ (a^{'}, ε) \circ (a, b, \tilde{a}) \mapsto (a^{'} \circ a, b, \tilde{a}); \\ (a, b, \tilde{a}) \circ (ε, b^{'}) \mapsto (a, b \circ b^{'}, ϕ_{b^{' - 1}} (\tilde{a})); \\ (ε, b^{'}) \circ (a, b, \tilde{a}) \mapsto (ϕ_{b^{'}} (a), b^{'} \circ b, \tilde{a}) . \end{array}$ The last mapping is derived from the following equations $(ε, b^{'}) \circ (a, ε) \circ (ε, b) \circ (\tilde{a}, ε) = (ε, b^{'}) \circ (a, ε) \circ (ε, b^{' - 1}) \circ (ε, b^{'}) \circ (ε, b) \circ (\tilde{a}, ε) = (ε, b^{'}) \circ (ε, b^{' - 1}) \circ (ϕ_{b^{'}} (a), ε) \circ (ε, b^{'} \circ b) \circ (\tilde{a}, ε) = (ϕ_{b^{'}} (a), ε) \circ (ε, b^{'} \circ b) \circ (\tilde{a}, ε)$ . Note that multiplying with $(a^{'}, b^{'}, {\tilde{a}}^{'})$ in C can be defined using the above as $(a^{'}, b^{'}, {\tilde{a}}^{'}) = (a^{'}, ε) \circ (ε, b^{'}) \circ ({\tilde{a}}^{'}, ε)$ . Now, all the four mappings above are automatic as they only use homomorphisms from B, which are automatic, and multiplication with fixed group elements in the basic groups A and B, which are automatic. It follows that ∘ is semiautomatic in C.

For equality, note that $(a, b, \tilde{a}) = (a^{'}, b^{'}, {\tilde{a}}^{'})$ iff $b = b^{'}$ (in group B) and $a \circ ϕ_{b} (\tilde{a}) = a^{'} \circ ϕ_{b^{'}} ({\tilde{a}}^{'})$ (in group A). Thus, for a fixed $(a^{'}, b^{'}, {\tilde{a}}^{'}) \in C$ and any $(a, b, \tilde{a}) \in C$ , $(a, b, \tilde{a}) = (a^{'}, b^{'}, {\tilde{a}}^{'})$ iff $b = b^{'}$ (in group B) and $a \circ ϕ_{b^{'}} (\tilde{a}) = a^{'} \circ ϕ_{b^{'}} ({\tilde{a}}^{'})$ . As $ϕ_{b^{'}}$ , ∘ restricted to A and equality in A are automatic, it follows that equality is semiautomatic in C. □

It can also be shown that the free product of finitely many semiautomatic groups is semiautomatic. The construction is very much inline with the one of Kharlampovich, Khoussainov and Miasnikov [12] for Cayley automatic groups with some adjustments for semiautomaticity. Theorem 7.
The free product of finitely many semiautomatic groups is semiautomatic.
Proof.
Let $(A_{1}; \circ, =), \dots, (A_{n}; \circ, =)$ be semiautomatic groups which all share the empty word ε as neutral element and use disjoint alphabets to represent the other elements. Note that, for each fixed $a \in A_{k}$ , there is an automatic mapping $x \mapsto a \circ x$ (for $x \in A_{k}$ ) such that the length of $a \circ x$ is at most a constant more than the length of x. Let # be a symbol not appearing in the alphabets of $A_{1}, \dots, A_{k}$ . Now each member of the free product B of $A_{1}, \dots, A_{k}$ is a word of the form $#^{+} u_{1} #^{+} u_{2} #^{+} \dots #^{+} u_{m} #^{+}$ with $u_{1}, \dots, u_{m}$ representing elements different from ε and no two subsequent $u_{h}, u_{h + 1}$ are from the same group $A_{k}$ . Any word from $#^{+}$ denotes the neutral element of the group. It is sufficient to show that the multiplication with any fixed element from $A_{1} \cup A_{2} \cup \dots \cup A_{n} - {ε}$ is automatic, multiplying with ε can be realised by the identity function. Consider $a \in A_{k} - {ε}$ .

Now $x \mapsto a \circ x$ is given as follows: x is mapped to $# a #$ in the case that $x \in #^{+}$ ; x is mapped to $# a # x$ in the case that the first component $u_{1}$ from x is not from $A_{k}$ ; x is mapped to the word $x^{'}$ , where $u_{1}$ is replaced by $#^{| u_{1} |}$ in the case that $u_{1} = a^{- 1}$ ; otherwise x is mapped to the word $x^{'}$ , where $u_{1}$ is replaced by a word from $(a \circ u_{1}) #^{*}$ . To ensure automaticity of the mapping, in the last two cases above, enough #’s are filled in to make sure that length of x and $x^{'}$ do not differ by more than a constant (independent of x).

The mapping $x \mapsto x \circ a$ is given as follows: x is mapped to $# a #$ in the case that $x \in #^{+}$ ; x is mapped to $x # a #$ in the case that the last component $u_{m}$ of x is not from $A_{k}$ ; the last part of the form $u_{m} #^{+}$ is erased from x by the mapping in the case that $u_{m} = a^{- 1}$ and the last part $u_{m} #^{+}$ is replaced by $(u_{m} \circ a) #$ in the case that $u_{m} \in A_{k} - {a^{- 1}}$ .

Furthermore, for comparing whether x of the form $#^{+} u_{1} #^{+} \dots #^{+} u_{n} #^{+}$ represents a fixed element $# a_{1} # a_{2} # \dots # a_{m} #$ , consider the automaton consisting of m distinct subautomatons: the hth subautomaton checks whether the component $u_{h}$ of x is from the same $A_{k}$ as $a_{h}$ and has the same value; the automaton accepts iff all these checks succeed and the number of components n of x is exactly m. □

4. Nilpotent groups

Kharlampovich, Khoussainov and Miasnikov [12] showed that finitely generated groups of nilpotency class 1 or 2 are Cayley automatic. The next theorem uses semiautomatic groups in place of Cayley automatic groups and pushes the above result one step further. As it is open whether all the finitely generated groups of nilpotency class 3 are Cayley automatic, this result provides possible candidates for separating the two notions within the finitely generated groups.

Theorem 8.
Every finitely generated group of nilpotency class 3 can be represented as a semiautomatic group $(A; \circ, =)$ .
Proof.
Let $a_{1}, \dots, a_{n}$ be the finitely many generators in the original nilpotent group.

Consider the factor group of the given group over the quotient group generated by all elements of the form $x \circ y \circ x^{- 1} \circ y^{- 1}$ . This group is Abelian and is isomorphic to $\begin{matrix} Z^{r} \times {0, 1, \dots, p_{r + 1} - 1} \times \dots \times {0, 1, \dots, p_{n} - 1} \end{matrix}$ for some $r ⩽ n$ and natural numbers $p_{r + 1}, \dots, p_{n} ⩾ 2$ .

Let $b_{1}, \dots, b_{n^{'}}$ be all the group elements of the form $a_{i}^{- 1} \circ a_{i^{'}}^{- 1} \circ a_{i} \circ a_{i^{'}}$ and let $c_{1}, \dots, c_{n^{″}}$ be all the group elements of the form $a_{i}^{- 1} \circ b_{j}^{- 1} \circ a_{i} \circ b_{j}$ or $b_{j}^{- 1} \circ a_{i}^{- 1} \circ b_{j} \circ a_{i}$ . As the group is of nilpotency class three and as the $b_{i}$ are commutators, the $c_{1}, \dots, c_{n^{″}}$ are “commutators of second degree” and commute with all group elements. Furthermore, for each $i, j$ there is a k with $\begin{matrix} a_{i} \circ b_{j} = b_{j} \circ a_{i} \circ c_{k}, a_{i} \circ b_{j}^{- 1} = b_{j}^{- 1} \circ a_{i} \circ c_{k}^{- 1} \end{matrix}$ and that for each $i, i^{'}$ there are $j, k$ with $\begin{matrix} a_{i} \circ a_{i^{'}} = a_{i^{'}} \circ a_{i} \circ b_{j}, a_{i} \circ a_{i^{'}}^{- 1} = a_{i^{'}}^{- 1} \circ a_{i} \circ b_{j}^{- 1} \circ c_{k} . \end{matrix}$ Similar rules allow to move $a_{i}^{- 1}$ over $a_{i^{'}}, b_{j}$ . Note that, as the group has nilpotency class 3, the elements $c_{k}$ commute with all group elements. Thus, Furthermore, if $a_{i} \circ b_{j} = b_{j} \circ a_{i} \circ c_{k}$ , then $b_{j} \circ a_{i} = a_{i} \circ b_{j} \circ c_{k}^{- 1}$ and $a_{i}^{- 1} \circ b_{j} = b_{j} \circ a_{i}^{- 1} \circ c_{k}^{- 1}$ . Note that the group elements $b_{j}, b_{j^{'}}$ also commute with each other, as when, for example, $b_{j^{'}} = a_{i}^{- 1} \circ a_{i^{'}}^{- 1} \circ a_{i} \circ a_{i^{'}}$ then $b_{j} \circ b_{j^{'}} = b_{j} \circ a_{i}^{- 1} \circ a_{i^{'}}^{- 1} \circ a_{i} \circ a_{i^{'}} = a_{i}^{- 1} \circ a_{i^{'}}^{- 1} \circ a_{i} \circ a_{i^{'}} \circ b_{j} = b_{j^{'}} \circ b_{j}$ . The reason is that the $c_{k}, c_{k^{'}}$ produced by moving $a_{i}^{- 1}, a_{i^{'}}^{- 1}$ , respectively, over $b_{j}$ , are cancelled out when moving $a_{i}, a_{i^{'}}$ over $b_{j}$ . Now, each group element is given by a convoluted tuple of integers $\begin{matrix} (m_{1}, \dots, m_{n}, m_{1}^{'}, \dots, m_{n^{'}}^{'}, m_{1}^{″}, \dots, m_{n^{″}}^{″}) \end{matrix}$ where, for $i = r + 1, \dots, n$ , $m_{i} \in {0, 1, \dots, p_{i} - 1}$ . The above member of A represents $\begin{matrix} a_{1}^{m_{1}} \circ \dots \circ a_{n}^{m_{n}} \circ b_{1}^{m_{1}^{'}} \circ \dots \circ b_{n^{'}}^{m_{n^{'}}^{'}} \circ c_{1}^{m_{1}^{″}} \circ \dots \circ c_{n^{″}}^{m_{n^{″}}^{″}} . \end{matrix}$ Note that several tuples of this type may represent the same group element due to products of some $b_{j}$ and $c_{k}$ being ε.

In the representation set A, the integers $m_{i}$ and $m_{j}^{'}$ in the above are represented in binary, with the reverse ordering of the bits to allow automatic addition of components. Furthermore, each $m_{k}^{″}$ is represented as a convoluted tuple $(h_{0}, h_{1}, \dots, h_{n})$ of integers (in binary using reverse ordering of the bits) satisfying $\begin{matrix} m_{k}^{″} = h_{0} + h_{1} \cdot m_{1} + \dots + h_{n} \cdot m_{n}, \end{matrix}$ The number of integers used in the overall representation described above is $n + n^{'} + (n + 1) \cdot n^{″}$ , which is a constant independent of the group element; therefore convolution can indeed be used to represent the group element.

Now it will be shown that multiplication with a fixed $a_{i}$ is automatic and that equality is semiautomatic.

First, for automaticity of the multiplication with a fixed element, note that it is sufficient to show that multiplication with a fixed generator from $a_{1}, a_{1}^{- 1}, \dots, a_{n}, a_{n}^{- 1}$ is automatic, as every other group element is a fixed product of these. This is shown in several steps, the number of steps is constant and each step is automatic. For showing that the mapping $x \mapsto a_{i} \circ x$ is automatic, it is now described how, $a_{i} \circ a_{i^{'}}^{m_{i^{'}}} a_{i^{'} + 1}^{m_{i^{'} + 1}} \dots a_{n}^{m_{n}} b_{1}^{m_{1}^{'}} \dots b_{n^{'}}^{m_{n^{'}}^{'}} c_{1}^{m_{1}^{″}} \dots c_{n^{″}}^{m_{n^{″}}^{″}}$ is updated to $a_{i^{'}}^{m_{i^{'}}} \circ a_{i} \circ a_{i^{'} + 1}^{m_{i^{'} + 1}} \dots a_{n}^{m_{n}} b_{1}^{s_{1}^{'}} \dots b_{n^{'}}^{s_{n^{'}}^{'}} c_{1}^{s_{1}^{″}} \dots c_{n^{″}}^{s_{n^{″}}^{″}}$ , where $i^{'} < i$ and $m_{k}^{″} = (h_{0}^{k}, h_{1}^{k}, \dots, h_{n}^{k})$ . Repeatedly using this mechanism to shift $a_{i}$ over $a_{1}^{m_{1}} a_{2}^{m_{2}} \dots a_{i - 1}^{m_{i - 1}}$ and then showing how to handle the increase of $m_{i}$ by 1, gives the multiplication by $a_{i}$ for any member of the group as represented in A. Now suppose $1 ⩽ i^{'} < i$ , $1 ⩽ q ⩽ n$ , and $m_{i^{'}} > 0$ . There are $j, k_{1}, \dots, k_{n}$ such that $a_{i} a_{i^{'}} = a_{i^{'}} a_{i} b_{j}$ and $b_{j} a_{q} = a_{q} b_{j} c_{k_{q}}$ . Then, the following operations are done to update $m_{j}^{'}$ and various $m_{k}^{″}$ to obtain the corresponding $s_{j}^{'}$ and $s_{j}^{″}$ (values not updated are unchanged).
$m_{i^{'}}$ is added to $m_{j}^{'}$ (to handle the increase in the $b_{j}$ ).

$m_{i^{'}} (m_{i^{'}} - 1) / 2$ is added to $m_{k_{i^{'}}}^{'}$ (to handle the increase in $c_{k_{i^{'}}}$ due to moving of $b_{j}$ generated in (a) over $a_{i^{'}}^{m_{i^{'}}}$ ). If $m_{i^{'}}$ is odd, then the above addition can be achieved by adding $(m_{i^{'}} - 1) / 2$ to $h_{i^{'}}^{k_{i^{'}}}$ . If $m_{i^{'}}$ is even, $m_{i^{'}} (m_{i^{'}} - 1) / 2 = m_{i^{'}} (m_{i^{'}} - 2) / 2 + m_{i^{'}} / 2$ . Thus, the above addition can be achieved by adding $m_{i^{'}} / 2$ to $h_{0}^{k_{i^{'}}}$ and adding $(m_{i^{'}} - 2) / 2$ to $h_{i^{'}}^{k_{i^{'}}}$ .

$m_{i^{'}} * m_{q}$ is added to $m_{k_{q}}^{″}$ , for $q = i^{'} + 1, \dots, n$ (to handle the increase in $c_{k_{q}}$ due to moving of $b_{j}^{m_{i^{'}}}$ over $a_{q}^{m_{q}}$ ). This can be done by adding $m_{i^{'}}$ to $h_{q}^{k_{q}}$ .
Note that $a_{i} \circ a_{i^{'}}^{- 1} = a_{i^{'}}^{- 1} \circ a_{i} \circ b_{j}^{- 1} \circ c_{k^{'}}$ for some $k^{'}$ which permits to handle the case when $m_{i^{'}} < 0$ in a similar manner. For the multiplication $\begin{matrix} a_{i} \circ a_{i}^{m_{i}} a_{i + 1}^{m_{i + 1}} \dots a_{n}^{m_{n}} b_{1}^{m_{1}^{'}} \dots b_{n^{'}}^{m_{n^{'}}^{'}} c_{1}^{m_{1}^{″}} \dots c_{n^{″}}^{m_{n^{″}}^{″}}, \end{matrix}$ one updates $m_{i}$ to $m_{i} + 1$ and, as a chain reaction, for $k = 1, \dots, n^{″}$ , update $h_{0}^{k}$ to $h_{0}^{k} - h_{i}^{k}$ , for the tuple $(h_{0}^{k}, h_{1}^{k}, \dots, h_{n}^{k})$ representing $m_{k}^{″}$ (so that the new value of $m_{i}$ is used rather than the older value in the computation of $m_{k}^{″}$ ).

Similarly it can be shown that also the mappings $x \mapsto a_{i}^{- 1} \circ x$ , $x \mapsto x \circ a_{i}$ and $x \mapsto x \circ a_{i}^{- 1}$ are automatic.

The above handles all multiplications by $a_{i}$ on the left except for the case of $i > r$ and $m_{i} + 1 = p_{i}$ . To handle this, an additional multiplication by $a_{i}^{- p_{i}}$ can be done using the above mechanism to bring the power of $a_{i}$ to 0.

Now, for showing semiautomaticity of equality, for any fixed element $\begin{matrix} a_{1}^{m_{1}} \circ \dots \circ a_{n}^{m_{n}} \circ b_{1}^{m_{1}^{'}} \circ \dots \circ b_{n^{'}}^{m_{n^{'}}^{'}} \circ c_{1}^{m_{1}^{″}} \circ \dots \circ c_{n^{″}}^{m_{n^{″}}^{″}} \in A \end{matrix}$ it is shown that the set of its representatives in A is regular. Note that in the vector of the exponents, for each further representative of the group element, the first n coordinates must also be $m_{1}, m_{2}, \dots, m_{n}$ , which can be easily checked. In the case that these n coordinates are equal, one can tailormake an automaton to check for equality. The automaton can, for each k and for the coordinates $(h_{0}, h_{1}, \dots, h_{n})$ representing $m_{k}^{″}$ , use the formula $\begin{matrix} h_{0} + h_{1} \cdot m_{1} + \dots + h_{n} \cdot m_{n} \end{matrix}$ to get the explicit value corresponding to $m_{k}^{″}$ in the other representative, in binary notation, as multiplication of integers by constants can be done automatically. However, the $m^{'}$ -coordinates and $m^{″}$ -coordinates can be different for the two representatives. The difference of these coordinates must, however, give a vector representing ε. Thus, it suffices to give a test for neutrality in the $m^{'}$ -coordinates and $m^{″}$ -coordinates in order to be able to decide equality to the fixed given element. Call a set ${v_{1}, \dots, v_{r}}$ of vectors representing these coordinates to be independent over $Z$ iff no $v_{h}$ can be obtained from a linear combination of the others using coefficients from $Z$ . If one of the sets ${v_{1}, v_{2}, \dots, v_{r}}$ , ${- v_{1}, v_{2}, \dots, v_{r}}$ , ${v_{1} - v_{2}, v_{2}, \dots, v_{r}}$ , ${v_{2} - v_{1}, v_{2}, \dots, v_{r}}$ is independent, then all of them are. So Euclid’s algorithm can be run on the vectors until all but one vector have a 0 in the first coordinate; then one can run the algorithm until, among all those vectors with a 0 in the first coordinate, all but at most one have a 0 in the second coordinate and so on. This implies that the number of independent vectors is not larger than the number of coordinates. Thus there are fixed vectors ${v_{1}, \dots, v_{ℓ}}$ such that two vectors $\begin{array}{l} (m_{1}, \dots, m_{n}, m_{1}^{'}, \dots, m_{n^{'}}^{'}, m_{1}^{″}, \dots, m_{n^{″}}^{″}) and \\ (m_{1}, \dots, m_{n}, {\tilde{m}}_{1}^{'}, \dots, {\tilde{m}}_{n^{'}}^{'}, {\tilde{m}}_{1}^{″}, \dots, {\tilde{m}}_{n^{″}}^{″}) \end{array}$ represent the same element iff the difference $\begin{matrix} (0, \dots, 0, m_{1}^{'} - {\tilde{m}}_{1}^{'}, \dots, m_{n^{'}}^{'} - {\tilde{m}}_{n^{'}}^{'}, m_{1}^{″} - {\tilde{m}}_{1}^{″}, \dots, m_{n^{″}}^{″} - {\tilde{m}}_{n^{″}}^{″}) \end{matrix}$ is of the form $r_{1} \cdot v_{1} + r_{2} \cdot v_{2} + \dots r_{ℓ} \cdot v_{ℓ}$ for some $r_{1}, \dots, r_{ℓ} \in Z$ . This is an existentially quantified formula, where the multiplication with fixed vectors (represented as convoluted tuples) can be done by an automatic function and their adding and comparing with the target as well. Thus the predicate whether the two vectors from above representing the two group elements are the same is automatic. Thus for each group element $\begin{matrix} a_{1}^{m_{1}} \circ \dots \circ a_{n}^{m_{n}} \circ b_{1}^{m_{1}^{'}} \circ \dots \circ b_{n^{'}}^{m_{n^{'}}^{'}} \circ c_{1}^{m_{1}^{″}} \circ \dots \circ c_{n^{″}}^{m_{n^{″}}^{″}} \end{matrix}$ there is a finite automaton which decides whether another group element is equal to it. So the group $(A; \circ, =)$ is semiautomatic. □

For the representation used in the above theorem, by using the natural subgroup B of all elements in A generated by the $b_{j}$ and $c_{k}$ , the following Theorem 9 below can be shown. The key idea is to represent each group element in the form $b \circ a \circ \tilde{b}$ where $b, \tilde{b}$ are in B and a is either $a_{1}^{m_{1}} \circ \dots \circ a_{n}^{m_{n}}$ or $a_{n}^{m_{n}} \circ \dots \circ a_{1}^{m_{1}}$ ; these two orderings are used in order to facilitate inversion. Item (b) in the theorem below is proven by coding a computationally difficult problem into the theory of the structure of the group and then conclude that this problem would be solvable in the case that the given structure is semiautomatic. Theorem 9.
In the following, $(A, \circ)$ denotes a finitely generated group of nilpotency class 3, B denotes the commutator subgroup generated by all elements of the form $x \circ y \circ x^{- 1} \circ y^{- 1}$ with $x, y \in A$ and ∙ denotes the restriction of ∘ to the domain $(A \times B) \cup (B \times A)$ .
For every A as above, the structure $(A, B, x \mapsto x^{- 1}, ∙; \circ, =)$ is semiautomatic.

For some A as above, the structure $(A, B, ∙, =; \circ)$ is not semiautomatic.

Proof.
(a): The notation from the proof of Theorem 8 is carried over for this proof. The group elements are represented as products $b \circ a \circ \tilde{b}$ where (i) $b, \tilde{b}$ are products of $b_{j}$ ’s and $c_{k}$ ’s represented in the same format as they are represented in Theorem 8 and (ii) a is a member of $(a_{1}^{} a_{2}^{} \dots a_{n}^{} \cup a_{n}^{} \dots a_{2}^{} a_{1}^{})$ represented as a convoluted tuple $(m_{0}, m_{1}, \dots, m_{n})$ , where $m_{0} \in {- 1, 1}$ ; the tuple $(m_{0}, m_{1}, \dots, m_{n})$ represents $a_{1}^{m_{1}} \circ \dots \circ a_{n}^{m_{n}}$ , if $m_{0} = 1$ , and $a_{n}^{m_{n}} \circ \dots \circ a_{1}^{m_{1}}$ , if $m_{0} = - 1$ .

The mappings $b \mapsto b^{- 1}$ , $a \mapsto a^{- 1}$ and $\tilde{b} \mapsto {\tilde{b}}^{- 1}$ are realised by negating all entries in the corresponding tuples; for mapping $(b \circ a \circ \tilde{b})$ to ${(b \circ a \circ \tilde{b})}^{- 1}$ , one has to exchange the entries of b and $\tilde{b}$ as well, as ${(b \circ a \circ \tilde{b})}^{- 1} = {\tilde{b}}^{- 1} \circ a^{- 1} \circ b^{- 1}$ . Thus the mapping $x \mapsto x^{- 1}$ (in the chosen representation) is automatic.

Note that, in the representation for $\hat{b} \in B$ , all the m-coordinates are 0. Thus for the component $m_{k}^{″}$ in the representation of $\hat{b}$ , the integers $h_{1}, h_{2}, \dots$ (as in Theorem 8) can be ignored. Hence, the multiplication $\hat{b} ∙ (b \circ a \circ \tilde{b})$ , can be done by adding $m_{j}^{'}$ coordinate of the representation of $\hat{b}$ to the corresponding $m_{j}^{'}$ coordinate of b and the $h_{0}$ -component of the $m_{k}^{″}$ coordinate of $\hat{b}$ to the corresponding $h_{0}$ -component of the $m_{k}^{″}$ coordinates of b. Similarly, when computing $(b \circ a \circ \tilde{b}) ∙ \hat{b}$ , the coordinates of $\hat{b}$ are added as above to those of $\tilde{b}$ .

Note that, in the representation chosen for this proof, $\hat{b} \in B$ is actually a product of the form: $b^{'} \circ ε \circ {\tilde{b}}^{'}$ , where $b^{'}, {\tilde{b}}^{'}$ are represented as in Theorem 8. The coordinates of $b^{'}$ and ${\tilde{b}}^{'}$ as above can be contracted to the coordinates of one member of B by simply adding, component-wise, prior to carrying out the multiplication ∙ as described above. These arguments explain why ∙ is an automatic function.

Multiplication of an element x with generators $a_{i}$ from either side as done in Theorem 8, can easily be adjusted to the representation chosen here.

Now, assume a fixed group element $x = a_{1}^{m_{1}} a_{2}^{m_{2}} \dots a_{n}^{m_{n}} \circ b^{'}$ , where $b^{'} \in B$ , is given. Let $a = a_{1}^{m_{1}} a_{2}^{m_{2}} \dots a_{n}^{m_{n}}$ . Note that for all representatives $y = b \circ a^{'} \circ \tilde{b}$ of x in the representation chosen, the coordinates $m_{1}, m_{2}, \dots, m_{n}$ corresponding to $a^{'}$ must match to that of a as above. Furthermore, there is a fixed element $\hat{b} \in B$ such that $\begin{matrix} a_{n}^{m_{n}} \circ \dots \circ a_{1}^{m_{1}} = a_{1}^{m_{1}} \circ \dots \circ a_{n}^{m_{n}} \circ \hat{b} . \end{matrix}$ Now, for any given representative $y = b \circ a^{'} \circ \tilde{b}$ with the coordinates for $a^{'}$ being $m_{0} = - 1, m_{1}, \dots, m_{n}$ , the coordinate $m_{0}$ can be converted to $+ 1$ , by replacing $\tilde{b}$ by $\hat{b} \circ \tilde{b}$ . Furthermore, using the arguments given in the proof of Theorem 8, there is a fixed automatic homomorphism $ϕ_{a} : B \to B$ such that $b \circ a = a \circ ϕ_{a} (b)$ . The products $ϕ_{a} (b) \circ \tilde{b}$ or $ϕ_{a} (b) \circ \hat{b} \circ \tilde{b}$ can be carried out by componentwise addition of the vectors involved. Once this is done, the algorithm from Theorem 8 can be used to compare y in the resulting representation with that of x. Thus equality is semiautomatic in the representation chosen.

For the proof of (b), one starts with the free group $\hat{A}$ of nilpotency class 3 generated by ${\hat{a}}_{1}, \dots, {\hat{a}}_{7}$ . Let $\hat{B}$ denote the subgroup generated by ${x^{- 1} \circ y^{- 1} \circ x \circ y : x, y \in \hat{A}}$ and $\hat{C}$ denote the subgroup generated by ${x^{- 1} \circ y^{- 1} \circ x \circ y : x \in \hat{B}, y \in \hat{A}}$ . For a suitable subgroup $\tilde{C}$ of $\hat{C}$ defined below, one chooses A by defining $\begin{matrix} A = {x \circ \tilde{C} : x \in \hat{A}} . \end{matrix}$ Furthermore, let B denote ${x \circ \tilde{C} : x \in \hat{B}}$ and C denote ${x \circ \tilde{C} : x \in \hat{C}}$ . The choice of $\tilde{C}$ will be crucial. Note that one can make two $c, c^{'}$ from $\hat{C}$ to be equal in C by putting $c^{- 1} \circ c^{'}$ into $\tilde{C}$ . Similarly, one can make c to be ε by putting c into $\tilde{C}$ . Furthermore, one can make $c = c^{'} \circ c^{″}$ by putting $c^{- 1} \circ c^{'} \circ c^{″}$ in $\tilde{C}$ . The $\tilde{C}$ will be defined implicitly based on the above methods below.

The goal is to code a hard problem into the theory of the automatic structure $(A, B, ∙, =; \circ)$ . So one considers the structure which can check membership in A, membership in B, multiplication of two elements with one in B and one in A and equality; furthermore, multiplcation with fixed members from A from either side can also be used.

Now the following will be shown: For an NP-hard problem, one can choose A (by chosing $\tilde{C}$ appropriately) such that there is a automatic relation R in $B \times B \times B$ and a polynomial time function f mapping parameters $(α, β, γ)$ to members of $B \times B \times B$ such that $f (α, β, γ) \in R$ iff a corresponding instance of a fixed NP-complete problem can be solved. Since automatic relations can be solved in linear time [3], this would result in a proof that $P = N P$ . Admittedly, the hypothesis $P = N P$ is not yet refuted; however, a more complicated coding could do the same for any given Diophantine set and would result in a situation where automaticity permits to decide a nonrecursive Diophantine set, a contradiction. As the coding for this is much more involved, only the coding of the NP-hard problem is supplied in order to convince the reader that not every structure of the form $(A, B, ∙, =; \circ)$ is semiautomatic. So the goal is to solve the following NP-hard set in the integers: $\begin{matrix} S = {(α, β, γ) : \exists μ, ν \in Z [μ^{2} ⩽ γ^{2} and μ^{2} + ν \cdot β = α]} . \end{matrix}$ Here the complexity of $(α, β, γ)$ is measured in the number of bits needed for their binary represenation and the NP-hardness of this set was shown by Manders and Adleman [14]. Now a formula representing an automatic relation R will be defined along with special elements $b_{1}, c_{1}, c_{2} \in B$ defined later such that $(c_{1}^{α}, b_{1}^{β}, c_{2}^{γ^{2}}) \in R$ iff $(α, β, γ) \in S$ .

Note that due to ∙ being automatic, one can compute for fixed $b \in B$ a power $b^{δ}$ by using that the functions $b^{δ} \mapsto b^{2 δ} = b^{δ} ∙ b^{δ}$ and $b^{δ} \mapsto b^{2 δ + 1} = b^{δ} ∙ b^{δ} ∙ b$ are both automatic and can be computed in linear time. Furthermore, the representatives of $b^{2 δ}$ and $b^{2 δ + 1}$ are both only a constant longer than that of $b^{δ}$ ; this implies that the overall function $δ \mapsto b^{δ}$ can be computed in time polynomial in the number of digits of δ, as one starts with $u_{0} = ε$ and one does, inductively for each digit $d = d_{1}, \dots, d_{ℓ}$ of δ, the update $u = u ∙ u ∙ b^{d}$ , with $b^{d} = ε$ for $d = 0$ and $b^{d} = b$ for $d = 1$ . Note that $γ^{2}$ can be computed beforehand in polynomial time from γ.

Recall that $a_{1}, \dots, a_{7}$ are the generators of A. R will be defined by an existentially quantified formula which asks for the existence of an $x, x_{1}, x_{2} \in A$ and $y, y_{1}, y_{2} \in B$ satisfying the conditions laid out below. Note that $\begin{matrix} x \in a_{1}^{m_{1}} \circ a_{2}^{m_{2}} \circ \dots \circ a_{6}^{m_{6}} \circ a_{7}^{m_{7}} \circ B \end{matrix}$ and similarly for $x_{1}, x_{2}$ . Furthermore, for studying how the generator $a_{7}$ commutes with the other generators, let $b_{1}, \dots, b_{6}$ denote the members of B satisfying $\begin{matrix} a_{7} \circ a_{1} = a_{1} \circ a_{7} \circ b_{1}, \dots, a_{7} \circ a_{6} = a_{6} \circ a_{7} \circ b_{6} . \end{matrix}$ $\tilde{C}$ is chosen such that the following conditions are true for the degree of commutativity between $a_{1}, \dots, a_{6}$ and $b_{1}, \dots, b_{6}$ : $\begin{array}{l} b_{1} \circ a_{1} = a_{1} \circ b_{1} \circ c_{1}, b_{2} \circ a_{2} = a_{2} \circ b_{2} \circ c_{1} \circ c_{2}, \\ b_{3} \circ a_{3} = a_{3} \circ b_{3} \circ c_{2}, b_{4} \circ a_{4} = a_{4} \circ b_{4} \circ c_{2}, \\ b_{5} \circ a_{5} = a_{5} \circ b_{5} \circ c_{2}, b_{6} \circ a_{6} = a_{6} \circ b_{6} \circ c_{2} . \end{array}$ Here by definition $c_{1} = b_{1}^{- 1} \circ a_{1}^{- 1} \circ b_{1} \circ a_{1}$ and $c_{2} = b_{3}^{- 1} \circ a_{3}^{- 1} \circ b_{3} \circ a_{3}$ and the other four equations redefine the corresponding commutators for $a_{i}, b_{i}$ . Furthermore, one defines for all different $i, i^{'}, i^{″} \in {1, \dots, 7}$ that $\begin{matrix} a_{i}^{- 1} \circ {(a_{i^{'}}^{- 1} \circ a_{i^{″}}^{- 1} \circ a_{i^{'}} \circ a_{i^{″}})}^{- 1} \circ a_{i} \circ (a_{i^{'}}^{- 1} \circ a_{i^{″}}^{- 1} \circ a_{i^{'}} \circ a_{i^{″}}) = ε \end{matrix}$ and this implies that $b_{j} \circ a_{i} = a_{i} \circ b_{j}$ for $i, j \in {1, \dots, 6}$ with $i \neq j$ . Now there is a $c \in C$ such that $\begin{matrix} a_{7} \circ x = x \circ a_{7} \circ b_{1}^{m_{1}} \circ b_{2}^{m_{2}} \circ \dots \circ b_{6}^{m_{6}} \circ c . \end{matrix}$ It is required that $y, y_{1}, y_{2}$ depend on $x, x_{1}, x_{2}$ and each other as follows: $\begin{array}{l} a_{7} \circ x = (x \circ a_{7}) ∙ y, a_{7} \circ x_{1} = (x_{1} \circ a_{7}) ∙ y_{1}, \\ a_{7} \circ x_{2} = (x_{2} \circ a_{7}) ∙ y_{2}, y = y_{1} ∙ y_{2} . \end{array}$ The first of the following conditions is due to the choice of $m_{1}, \dots, m_{6}$ and the second and third conditions will be imposed implicitly: $\begin{array}{l} y \in a_{1} \circ b_{1}^{m_{1}} \circ \dots \circ b_{6}^{m_{6}} \circ C, \\ y_{1} \in a_{1} \circ b_{1}^{m_{1}} \circ C, \\ y_{2} \in a_{2} \circ b_{2}^{m_{2}} \circ \dots \circ b_{6}^{m_{6}} \circ C \end{array}$ For the second and third conditions, one ensures that $b_{1}$ does not occur in $y_{2}$ and that $b_{2}, \dots, b_{6}$ do not occur in $y_{1}$ by requiring the following commutativity conditions on $y_{1}, y_{2}$ : $\begin{array}{l} a_{1} \circ y_{2} = y_{2} \circ a_{1}, a_{2} \circ y_{1} = y_{1} \circ a_{2}, a_{3} \circ y_{1} = y_{1} \circ a_{3}, \\ a_{4} \circ y_{1} = y_{1} \circ a_{4}, a_{5} \circ y_{1} = y_{1} \circ a_{5}, a_{6} \circ y_{1} = y_{1} \circ a_{6} . \end{array}$ In addition one requires that either $a_{7}$ does not occur in $x, x_{1}, x_{2}$ or $a_{7}$ commutes with $b_{1}, \dots, b_{6}$ . This is obtained by postulating, for $i = 1, \dots, 6$ and $\tilde{x} = x, x_{1}, x_{2}$ and for all $\tilde{y} \in B$ , $\begin{matrix} if a_{i} \circ \tilde{x} = (\tilde{x} \circ a_{i}) ∙ \tilde{y} then a_{7} \circ \tilde{y} = \tilde{y} \circ a_{7} . \end{matrix}$ Note that if $a_{7}$ occurs in $\tilde{x}$ then moving $a_{i}$ over $a_{7}$ gives a member of $b_{i}^{- 1} \circ C$ while all other commutators of $a_{i}$ and $a_{i^{'}}$ with $i^{'} \in {1, \dots, 6} - {i}$ do commute with $a_{7}$ . If now $\tilde{y}$ is the member of B generated by moving $a_{i}$ over x and $a_{7} \circ \tilde{y} = \tilde{y} \circ a_{7}$ then either $a_{7}$ does not occur in $\tilde{x}$ and thus $b_{i}$ does not occur in $\tilde{y}$ or $a_{7}$ and $b_{i}$ commute. The above conditions together give that $\begin{matrix} b_{1}^{β} ∙ y_{2} ∙ x = x ∙ b_{1}^{β} ∙ y_{2} ∙ c_{1}^{β m_{1} + m_{2}^{2}} ∙ c_{2}^{m_{2}^{2} + m_{3}^{2} + \dots + m_{6}^{2}} \end{matrix}$ and thus one imposes the additional constraint that $\begin{matrix} b_{1}^{β} ∙ y_{2} ∙ x = x ∙ b_{1}^{β} ∙ y_{2} ∙ c_{1}^{α} ∙ c_{2}^{γ^{2}} . \end{matrix}$ These conditions together enforce that $β m_{1} + m_{2}^{2} = α$ and $m_{2}^{2} + m_{3}^{2} + \dots + m_{6}^{2} = γ^{2}$ . Using the theorem that every natural number is the sum of four integer squares, one has that the solvability of the conditions is equivalent to the existence of integers $m_{1}, m_{2}$ with $β m_{1} + m_{2}^{2} = α$ and $m_{2}^{2} ⩽ γ^{2}$ . Thus one has the following statement:

$(α, β, γ) \in S$ iff $(c_{1}^{α}, b_{1}^{β}, c_{2}^{γ^{2}}) \in R$ iff there are $x, x_{1}, x_{2} \in A$ and $y, y_{1}, y_{2} \in B$ such that $\begin{matrix} b_{1}^{β} ∙ y_{2} ∙ x = x ∙ b_{1}^{β} ∙ y_{2} ∙ c_{1}^{α} ∙ c_{2}^{γ^{2}} \end{matrix}$ and the equations governing the specific form of the variables $x, x_{1}, x_{2}, y, y_{1}, y_{2}$ are satisfied, namely $\begin{array}{l} a_{7} \circ x = (x \circ a_{7}) ∙ y, a_{7} \circ x_{1} = (x_{1} \circ a_{7}) ∙ y_{1}, a_{7} \circ x_{2} = (x_{2} \circ a_{7}) ∙ y_{2}, \\ y = y_{1} ∙ y_{2}, \\ a_{1} \circ y_{2} = y_{2} \circ a_{1}, a_{2} \circ y_{1} = y_{1} \circ a_{2}, a_{3} \circ y_{1} = y_{1} \circ a_{3}, \\ a_{4} \circ y_{1} = y_{1} \circ a_{4}, a_{5} \circ y_{1} = y_{1} \circ a_{5}, a_{6} \circ y_{1} = y_{1} \circ a_{6} \end{array}$ and, for $i = 1, \dots, 6$ and $\tilde{x} = x, x_{1}, x_{2}$ and for all $\tilde{y} \in B$ , $\begin{matrix} if a_{i} \circ \tilde{x} = (\tilde{x} \circ a_{i}) ∙ \tilde{y} then a_{7} \circ \tilde{y} = \tilde{y} \circ a_{7} . \end{matrix}$ This comprehensive formula defines that R is an automatic relation in the case that $(A, B, ∙, =; \circ)$ is semiautomatic. If R would be automatic, P would be equal to NP. This shows that the assumption of R being automatic is unlikely. A more complicated construction could also code up an unsolvable Diophantine set which then would be solved if the corresponding structure is semiautomatic; the group and the formula required would, however, be much more complicated. Therefore the proof is here given by coding an NP-complete problem. □

5. Conclusion

The present work established that every Cayley automatic group is semiautomatic, thus permitting to prove that the semiautomatic groups have an undecidable isomorphism problem and an undecidable conjugacy problem. Prior work showed that finitely generated groups of nilpotency class 2 are on one hand Cayley biautomatic [12] and on the other hand not automatic [18]; however, the situation was left open for nilpotent groups of higher classes. The present paper shows that finitely generated groups of nilpotency class three are always semiautomatic. As one could not establish that they are always Cayley automatic, these groups form a natural candidate to separate these two notions. In general, the following questions are open at the point of writing of this paper:

Is every finitely generated semiautomatic group Cayley automatic?

More generally, does every semiautomatic group $(G; \circ, =)$ have a presentation in which the equality is automatic and, for each constant a, also the mapping $x \mapsto x \circ a$ is automatic?

Are all finitely generated nilpotent groups semiautomatic?

Are all finitely generated nilpotent groups Cayley automatic?

Are all finitely generated nilpotent groups Cayley biautomatic?

The results in this paper give some progress towards these questions, but leave all of them open.

Footnotes

Acknowledgements

F. Stephan (PI) and S. Jain (Co-PI) are supported in part by Singapore Ministry of Education Academic Research Fund Tier 1 grants R146-000-181-112 and R252-000-534-112 as well as Tier 2 grants MOE2013-T2-1-062/R146-000-184-112 and MOE2016-T2-1-019/R146-000-234-112. Additionally, S. Jain was supported in part by NUS grant C252-000-087-001. B. Khoussainov is supported in part by above mentioned grant MOE2016-T2-1-019/R146-000-234-112 (as a collaborator) and by the Marsden Fund grant of the Royal Society of New Zealand. A conference version of this paper was presented at CiE 2016 []. Furthermore, F. Stephan acknowledges the funding of JSPS and NUS (R146-000-192-133 and R146-000-192-733) for the joint IMS-JSPS Workshop on Mathematical Logic and the Foundations of Mathematics in 2016 where he presented a survey on the joint results of this and other papers in the area of semiautomatic groups and semigroups.

References

Afshari,

Barmpalias,

S.B

Cooper and

Stephan, Post’s programme for the Ershov hierarchy, Journal of Logic and Computation17 (2007), 1025–1040. doi:10.1093/logcom/exm032.

Berdinsky and

Khoussainov, On automatic transitive graphs, in: Developments in Language Theory – Eighteenth International Conference, DLT 2014, Proceedings, Ekaterinburg, Russia, August 26–29, 2014, LNCS, Vol. 8633, Springer, 2014, pp. 1–12.

Case,

Jain,

Seah and

Stephan, Automatic functions, linear time and learning, Logical Methods in Computer Science9(3) (2013).

S.B.

Cooper, Mathematics, metaphysics and the multiverse, in: Computation, Physics and Beyond – International Workshop on Theoretical Computer Science, WTCS 2012, Revised Selected and Invited Papers, Auckland, New Zealand, 21–24 February 2012, LNCS, Vol. 7160, Springer, 2012, pp. 252–267. Dedicated to Cristian S. Calude on the Occasion of His Sixtieth Birthday.

S.B.

Cooper, The machine as data: A computational view of emergence and definability, Synthese192(7) (2015), 1955–1988. doi:10.1007/s11229-015-0803-4.

D.B.A.

Epstein,

J.W.

Cannon,

D.F.

Holt,

S.V.F.

Levy,

M.S.

Paterson and

W.P.

Thurston, Word Processing in Groups, Jones and Bartlett Publishers, Boston, 1992.

T.V.

Gopal,

Agrawal,

Li and

S.B.

Cooper, A roadmap to TAMC, in: Theory and Applications of Models of Computation – Eleventh Annual Conference, TAMC 2014, Proceedings, Chennai, India, LNCS, Vol. 8402, Springer, 2014, pp. 1–6.

B.R.

Hodgson, Théories décidables par automate fini, Ph.D. thesis, Département de mathématiques et de statistique, Université de Montréal, 1976.

B.R.

Hodgson, Décidabilité par automate fini, Annales des sciences mathématiques du Québec7(1) (1983), 39–57.

10.

Jain,

Khoussainov and

Stephan, Finitely generated semiautomatic groups, in: Pursuit of the Universal, Twelfth Conference on Computability in Europe, CiE 2016, Proceedings, Paris, France, 27 June–1 July 2016, LNCS, Vol. 9709, Springer, 2016, pp. 282–291.

11.

Jain,

Khoussainov,

Stephan,

Teng and

Zou, Semiautomatic structures, Theory of Computing Systems61(4) (2017), 1254–1287. doi:10.1007/s00224-017-9792-7.

12.

Kharlampovich,

Khoussainov and

Miasnikov, From automatic structures to automatic groups, Groups, Geometry and Dynamical Systems8(1) (2014), 157–198.

13.

Khoussainov and

Nerode, Automatic presentations of structures, in: Logic and Computational Complexity, International Workshop, LCC 1994, Proceedings, Indianapolis, Indiana, USA, October 13–16, 1994, LNCS, Vol. 960, Springer, 1995, pp. 367–392. doi:10.1007/3-540-60178-3_93.

14.

K.L.

Manders and

Adleman, NP-complete decision problems for binary quadratics, Journal of Computer and System Sciences16 (1978), 168–184. doi:10.1016/0022-0000(78)90044-2.

15.

Miasnikov and

Šunić, Cayley graph automatic groups are not necessarily Cayley graph biautomatic, in: Language and Automata Theory and Applications – Sixth International Conference, LATA 2012, Proceedings, A Coruña, Spain, March 5–9, 2012,

A.H.

Dediu and

Martín-Vide, eds, LNCS, Vol. 7183, Springer, 2012, pp. 401–407.

16.

Nies, Describing groups, The Bulletin of Symbolic Logic13(3) (2007), 305–339. doi:10.2178/bsl/1186666149.

17.

Nies and Richard , Thomas. FA-presentable groups and rings, Journal of Algebra320 (2008), 569–585. doi:10.1016/j.jalgebra.2007.04.015.

18.

Oliver and

R.M.

Thomas, Automatic presentations for finitely generated groups, in: Twentysecond Annual Symposium on Theoretical Aspects of Computer Science (STACS 2005), Proceedings, Stuttgart, Germany, LNCS, Vol. 3404, Springer, 2005, pp. 693–704.

19.

J.S.

Rose, A Course on Group Theory, Dover Publications, 2012.

20.

Šunić and

Ventura, The conjugacy problem in automaton groups is not solvable, Journal of Algebra364 (2012), 148–154. doi:10.1016/j.jalgebra.2012.04.014.