6
$\begingroup$

I have been reading several articles about automatic groups and metric spaces of negative curvature. However it is not clear for me the relationship between automatic groups, hyperbolcity and the k-fellow traveler property. Specifically I would like to ask:

1) Given the word acceptor and multipliers of a shortlex automatic structure for the group G, is it possible to compute the value of k for the k-fellow traveler property? (maybe using the number of the states of such automata?)

2)Assume we know the value of k for a given group G. Is it possible to use the value of k to determine the minimal number of states of a word acceptor and multipliers of an shortlex automatic structure for G?

3)Given a automatic group G, What is the relationship between the k-fellow traveler property and the number of states of the multipliers and word acceptor of a shortlex automatic structure for G?

4)Following the book of Bridson (Metric space of non-positive curvature) the value of k can be bounded by the hyperbolicity of the Cayley Graph of G k=2(2*delta+1). Is there any relationship where the value of k can be used to bound the hyperbolicity of the CG?

Or I would also appreciate a good source (for non-mathematician) where I could find the answers.

Thanks in advance for any help.

Edit. I modified 1 question and added 2 new ones in order to be clear about what I want to ask.

$\endgroup$

1 Answer 1

4
$\begingroup$

If a multiplier automaton is in a state $\sigma$ after reading prefixes $u(i),v(i)$ of the input words $u,v$ then the group element $u(i)^{-1}v(i)$ is uniquely determined by $\sigma$. So I guess a crude upper bound for the fellow-travelling constant $k$ is twice the maximum number of states of any of the multiplier automata. Since the shortlex automatic structure enables you to reduce any word to shortlex normal form, it is certainly possible (and straightforward) to use it to compute the possible the length in the group of the elements $u(i)^{-1}v(i)$ determined by each state, and thereby determine $k$ exactly.

I don't understand Question 2. If you are given the shortlex automatic structure, then you don't need $k$ to compute the minimal number of states of the automata, you can compute them directly from the automata themselves using the standard algorithm (Myhill-Nerode?) for this.

I have no idea what source to recommend for a non-mathematician. Presumably you are already familiar with "Word Processing in groups" by Epstein et al? There are alternative sources but I don't think any of them are more elementary.

Added later. For the new question 2, I don't believe that there is any straightforward way to do this. Of course, if a group (defined by a finite presentation) is shortlex automatic, then it is possible to compute the automatic structure, and knowing the value of $k$ could make that a little easier, because it would help you know when to stop certain searches, but I am doubtful whether it would really help much in practice.

You could derive an upper bound on the numbers of states from $k$, but it would be doubly exponential in $k$, because you can construct the word acceptor with each state being a subset of the set of words of length at most $k$, whereas the states of the multipliers consist of pairs $(\sigma,u)$ with $\sigma$ a state of the word acceptor and $u$ a word of length at most $k$. It is possible that there is a simply exponential bound, but perhaps not. The algorithms that construc the automatic structure have complexity doubly exponential in $k$ in theory. Fortunately, in practice they do seem to work. This is mainly because critical quantity is not the maximum length $k$ of the wors that arise as $u(i)^{-1}v(i)$ in the notation above, but the total number of such words, which is typically much smaller than the total number of words of length $k$.

So I guess the real answer is that $k$ is not the best number to use for this purpose, and I think that answers Question 3 as well.

Question 4 is interesting. In the paper

P. Papasoglu, Strongly geodesically automatic groups are hyperbolic. Invent. Math., 121(2):323-334, 1995.

Papasoglu proved that if geodesic bigons in the Cayley graph are unformly thin, then the group is hyperbolic. The thinness constant ($k'$ say) of geodesic bigons is the fellow-travelling constant for all geodesic bigons rather than just those labelled by shortlex least words, so it could be a little larger than your $k$, but typically not much so.

I had a student a while ago who went through Papasoglu's proof and tried to bound the thinness of geodesic triangles constant $\delta$ in temrs of $k'$, but again the best bound he could come up with was doubly exponential in $k'$. In all of the examples I have ever seen, we seem to get things like $\delta = k'+2$, so it is frustrating not to be able to get a better bound. Papsoglu told me once that he had also tried to do this without success.

$\endgroup$
1
  • $\begingroup$ Dear Prof. Holt. Thanks for your fast reply. The first question is more clear for me now. I re-wrote the second question (actually I add a few additional questions) in order to be clear about what I'm asking. In general, I would like to understand the relationship between the number of states of the word acceptor and multipliers of a shortlex automatic structure of a group G and the k-fellow traveler property/hyperbolicity. $\endgroup$
    – Miguel
    May 19, 2015 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.