k-fellow traveler property and automatic structur

Question

Let P be a permutation group with some generating set S and let W be the word acceptor automaton of P, if I know the value of k (k-fellow-traveller property of CayleyGraph CG(P,S)). I realized that the number of states W changes in function of k, when value of k is "low", the total of states of W is also low.

For instance, if we have the following permutation groups (defined by the parameter p):

P1, where S={(i,i+1) in Symm__p, 1<=i< p} i.e. elements i-th and (i+1)-th of a permutation are interchanged. The CG(P1,S) is called blubble-sort graph

P2, where S={(1,i) in Symm__p, 1 < i < = p } i.e. the first and i-th elements of a permutation are interchanged. The CG(P2, S) is called star graph

P1 and P2 have order p!, I have made test with the library kbmag for 6 values of p=[4,9] and I found:

1)for P1 and when p=4,5,6,7,8,9, it is possible that k is bounded by 4 2)for P2, the value of k increases with respect to p 3)in all cases the W of P2 has much more states than the W of P1

My questions is if there is a relationship between the size of W and the value of k? I have realized that depends of the lexicographical order over the generating set S, I can improve the value of k (get a low value) and also the size of W. Another question is how choose the best lexicographical order?

Answer 1

The first point to note is that it is not so much the value of $k$ in the $k$-fellow-traveller property that determines the number of states of $W$, but rather the number $d$, say, of word-differences. These are the labels of the shortest words in the Cayley-graph that connect corresponding vertices in fellow-travelling paths. So $k$ is just the maximum length of a word-difference. You could have small $k$ but a large number ($O(|X|^{k+1})$) word-differences or in some examples $k$ could be large but with relatively few word-differences. The number of states of $W$ depends heavily on $d$. In fact $W$ can be computed from the set of word-differences using standard operations on automata. Since this involves determinizing a non-deterministic automaton, the number of states could potentially grow exponentially with $d$, but fortunately that does not tend to happen in typical examples (presumably because the word acceptor is in in some sense a natural object to be constructing).

Typically, automatic structures do not provide an efficient method of computing with finite groups. For arbitrary finite groups $G$ with a random minimal generating set, the number of word-differences and the number of states of $W$ seems to grow moderately quickly with $|G|$. I haven't investigated this seriously, but maybe something like $O(\sqrt{|G|})$ for the number of states of $W$.

But the symmetric group $S_p$ on generators $\{(1,2),(2,3),\ldots,(p-1,p)\}$ is an exception, and I think the reason for this is that $S_p$ is a Coxeter group on these generators, and in general Coxeter groups (finite and infinite) are automatic and the algorithms run quickly on them. (There is a nice theoretical description of the language of $W$.) In fact the numbers of word-differences and states of $W$ both grow quadratically with $p$. If you try $S_p$ on a difference generating set then, as you observed, they don't behave so nicely.

In general, the algorithms use an ordered monoid generating set $X$ of $G$, and the performance can vary considerably with $X$ and even occasionally with the chosen ordering of $X$. It is hard to predict which will be the optimal generating set, and it is not always one of minimal size (we saw that with the examples $S_p$). For example, with a Fibonacci group, it is much better to use the generators in the defining presentation than to reduce it to a $2$-generator group. So I cannot answer your question about how to choose the ordering - you just have to experiment.