8
$\begingroup$

Any finitely presented group naturally gives rise to an edge-labeled graph (the Cayley graph) and I am considering paths through this graph. Paths correspond to infinite sequences of generators, so we can ask questions about the recursiveness (or not) of these sequences*. For example, is there a group where any recursive sequence of generators necessarily corresponds to a self-intersecting path?

Has anyone seen any questions like this answered anywhere? Any good resources for the recursive properties of finitely presented groups? Maybe just an example or two of a really badly behaved (in a recursion-theoretic sense) group?

*To alleviate any potential confusion, an infinite sequence, {s_i} is recursive if there is a Turing Machine that, on input n, produces s_n.

Improve this question
$\endgroup$
4
  • $\begingroup$ You probably want to insist that the group is an infinite finitely presented group $\endgroup$
    – Boris Bukh
    Commented Feb 5, 2010 at 10:45
  • $\begingroup$ It's natural to ask whether this is really a property of the group. As defined, it's merely a property of the group with a given generating set. $\endgroup$
    – HJRW
    Commented Feb 10, 2010 at 2:44
  • $\begingroup$ This is true. However, given two sets of generators, each generator in the first set can be written as a product of generators from the second set. Thus, a computable path given in the first set of generators can be computably transformed into a path given in the second set. It's not obvious that this new path is non-self-intersecting, however. $\endgroup$
    – Aubrey da Cunha
    Commented Feb 10, 2010 at 5:37
  • $\begingroup$ Aubrey - right! It seems natural to allow yourself to `enlarge' your generating set, by considering the following property: there exists a constant C such that there is a non-repeating infinite sequence of group elements {g_n} such that d(g_n,g_{n+1})< C in the word metric. This certainly is an invariant of your group. $\endgroup$
    – HJRW
    Commented Feb 10, 2010 at 19:07

1 Answer 1

Reset to default
5
$\begingroup$

Your question is very interesting. I don't have a complete answer.

First, let me note that in a finitely presented group, the Cayley graph itself may not be a decidable graph, since to know whether or not a node in the graph, which is a word in the presentation, is trivial or not amounts exactly to the word problem for that presentation. And since there are finitely presented groups having an undecidable word problem, there are finitely presented groups having an undecidable Cayley graph.

This suggests an interesting sub-case of your problem, the case when the Cayley graph is decidable. And in this case, one can at least find a non-intersecting infinite path that is low.

Let me explain. For any group presentation, one may form the tree T of all finite non-intersecting paths. This is the tree of attempts to build an infinite non-intersecting path. Your question is equivalent to asking, when the group is infinite, whether or not this tree has a computable infinite branch. If the Cayley graph is decidable, then this tree will be decidable. Thus, by the Low Basis Theorem, it follows that there is a branch b through the tree which is low, meaning that the halting problem relative to b is Turing equivalent to the ordinary halting problem. In particular, this branch b is strictly below the halting problem in the Turing degrees. This shows that any computably-presented group with a decidable Cayley graph admits a low non-intersecting path. Such a path is close to being computable, but perhaps not quite computable. (Even in this very special case when the Cayley graph is decidable, I'm not sure whether there must be a computable non-intersecting path.)

In the general case, the argument shows that for any group presentation of an infinite group, we can find an infinite non-intersecting path s, which has low degree relative to the Turing degree of the Cayley graph (low in the technical sense). I suspect that this is the best that one can say.

There is another classical theorem in computability that seems relevant to your question, namely, the fact that there are computable infinite binary branching trees T, subtrees of 2ω, having no computable infinite branches. These trees therefore constitute violations of the computable analogue of Konig's lemma. This problem is very like yours, isn't it? I am intrigued by the possibility of using that classical construction to build an example of the kind of group you seek.

There is a natural generalization of your question beyond the finitely presented groups, to the class of finitely-generated but computably presented groups. That is, consider a group presentation with finitely many generators and a computable list of relations. It may be easier to find a instance of the kind of group you seek having this more general form, since one can imagine a priority argument, where one gradually adds relations as the construction proceeds in order to meet various requirements that diagonalize against the computable paths.

Here are some resources to general decidability questions in finite group presentations: the undecidability of the word problem, the conjugacy problem, and the group isomorphism problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ As far as I have been able to discern, this is all that is known on the problem. $\endgroup$
    – Aubrey da Cunha
    Commented Feb 10, 2010 at 5:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .