Groups whose word problem can be solved in constant time

Question

Given a finitely generated group $G$, define an encoding of $G$ to be a one-to-one function $\Phi:G\to \bigcup_n \{0,1\}^n$ that sends each group element to a unique finite word. For $a,b\in G$, assuming that $\Phi(ab)$ can be computed from $\Phi(a)$ and $\Phi(b)$, my question is: is there a classification for groups where there exists an encoding $\Phi$ such that $\Phi(e_ia)$ can be computed in constant time by a multi-tape Turing machine from $\Phi(e_i)$ and $\Phi(a)$ where $e_1,\ldots,e_n$ is some choice of generators and $a\in G$.

For example, $\mathbb Z$ has such an encoding. Expanding the encoding to allow strings with letters $\{0,1,*\}$, we can represent an element in $\mathbb Z$ as $\cdots 000*11\cdots 1\underline{1}000\cdots$ with the appropriate number of $1$s to the right or the left of $*$ for positive or negative values and $\underline{\phantom{a}}$ indicating the position of the head of the Turing machine. Then we just add or remove a $1$. Similarly, using multiple tapes, we can encode $\mathbb Z^n$. Using symbols $\{a,b,a^{-1},b^{-1}\}$ we can represent the free group on $\{a,b\}$ by just writing down its usual representation as words. We could also, for instance, encode the group $\langle a,b \mid aaa=e\rangle$. (For each of these examples, the head of the Turing machine should be left at the end of each encoding, otherwise the algorithm may not be constant time.) However, I'm not sure of more complicated examples.

I believe that operating on all encodings rather than directly on the encoding produced by representations in terms of generators makes this question distinct from ``groups where a multi-tape Turing machine can compute the application of a generator $e_i$ to a word $w=w_1\cdots w_n$ when given the input $\cdots 000.w_1\cdots w_n00\cdots$,'' but I don't have an example of a group where there exists a more computationally efficient encoding than just writing down the word in terms of generators.

I am also curious about the more general context of simultaneously constant-time operations on sets. For instance, on $\mathbb Z$, the function $f(x)=x+1$ can be accomplished in constant time by encoding $x$ as a string of $x$ $1$s. Similarly, the operation $g(x)=2x$ can be accomplished in constant time by encoding $x$ in binary. In binary $f(x)$ cannot be computed in constant time, and when written as $x$ $1$s, $g(x)$ cannot be computed in constant time. Does there exist an encoding of $\mathbb Z$ such that both $f$ and $g$ can be computed in constant time? Is there a name for such collections of operations?

Answer 1

This is a long comment rather than an answer.

Using the ideas in the examples that you gave, you could show that any group that is virtually a direct product of finitely many free groups of finite rank has your property: if $N \unlhd G$ with $G/N$ finite and $N$ a direct product of free groups, then you can use one tape for each free factor of $N$, and use a constant amount of memory to keep track of which coset of $N$ in $G$ you are in. You could conjecture that all examples have this form, although that could be hard to prove.

I find it interesting that groups with your property have real-time word problem, which means that you can decide whether a word $x_1x_2 \cdots x_n$ is equal to the identity in $G$ by reading the letters of the word at constant speed - i.e. you are only allowed constant time between reading letters, and you must halt in constant time after reading the final letter.

There is no classification of groups with real-time word problem, but there are various examples known, and I would guess that this is a larger class of groups than those with your property. In fact the configuration at any time of the real-time Turing machine determines the group element represented by the subword that you have read so far. But you could have many different configurations describing the same group element, which is perhaps the main difference from your problem, where you require a unique binary string for each group element.

I did some work on this problem myself a few years ado, and two references are

D.F. Holt and S. Rees. Solving the word problem in real time. Journal of the London Mathematical Society (2001) , Vol.63 (No.3). pp. 623-639.

D. F. Holt and C. E. Röver. On Real-Time Word Problems J. London Math. Soc. (2003) 67 (2): 289-301.

Examples include finitely generated nilpotent groups, hyperbolic groups, groups hyperbolic relastive to virtually abelian subgroups,and the solvable Baumslag-Solitar groups $B(1,r)$. The class is closed under direct and free products.

There is another conjecture around that the groups whose word problem is an intersection of finitely many context-free languages are groups that are virtually a direct product of free groups i.e. the same class as mentioned above in connection with your problem, but I cannot see any direct link between the two problems.