Which properties can be read off the balls of a Cayley graph?

Question

For which properties (P) [of groups] does the following hold:

given a group $G$ which has a finite presentation with at most $n$ relations of length at most $\ell$, there is a $R(n,\ell)$ so that, if the ball of radius $R$ in the [labelled/unlabelled] Cayley graph of $G$ [w.r.t. to the generating set of said presentation] is given, then one can conclude whether (P) hold or not.

There are quite a few caveats/comments to the question:

• by "decided" I mean one can always deduce whether (P) holds or not.
• the ball of radius $R$ cannot be computed if the word problem is not solvable for $G$. So the ball of radius $R$ needs to be given.
• there might be two questions: one for the labelled Cayley graph and one for the unlabelled Cayley graph.
• in the sense of the above question, the presentation is not an input of the problem, only $n$ and $\ell$ (but if you have the labelled Cayley graphs, I think [but maybe I'm wrong] you can read off the presentation from a large enough ball)
• one might like to consider the presentation as an input. Then if it has solvable word problem, the question is still interesting (since it puts a limit on how large the balls need to be computed)
• the only property which I believe[!] I know this is true is hyperbolicity.
• there are some results which enable to conclude that the group has property (T), but they do not always conclude (at least, not the ones I am aware of).
• you only get one ball, not all balls of radius $R$. So for example it's not clear to me that properties related to the growth of the group answer this question.

Answer 1

This question gestures in a few different directions. Since I think they may all be of some interest, I'll attempt to summarise what's known in a few of these directions here. Hopefully some of this helps!

Finitely generated groups

For a finitely generated group $G$ with a given generating set $S$, we can ask whether there is an $R$ such that $P$ is determined by the labelled isomorphism type of the ball $B(R)$ in the Cayley graph. These are exactly the properties that are open in the Gromov--Grigorchuk space of marked groups -- see, for instance, this paper of Cornulier--Guyot--Pitsch, and many others.

To give a flavour, for finitely presented groups, these properties $P$ are closed under passing to quotients. So examples include finiteness, Property (T), and the isolated groups studied in the above-mentioned paper.

Finitely presented groups

The original version of the question gives us a finitely presented group $G=\langle a_i\mid r_j\rangle$, and a constant $R$ that depends on the presentation. However, as noted in comments, if we take $R$ greater than the lengths of all the relators, then $G$ is determined up to isomorphism by the (again labelled) $R$-ball in the Cayley graph, since the loops in this ball generate all the relators. So $G$ itself, and hence every property of $G$, is trivially determined by this ball. However...

Recursively enumerable properties

Just because the ball determines $P$ doesn't mean that "one can always deduce whether (P) holds or not" (in the words of the question), in the sense that we may not know which $R$-balls correspond to $P$ and which $R$-balls correspond to not $P$.

This brings us into the world of algorithmic properties of groups. Properties $P$ that can be read off a finite ball are very close to the recursively enumerable properties: $P$ is recursively enumerable if there's a Turing machine that takes as input a finite presentation and terminates if and only if the resulting group has $P$.

If there's a Turing machine $T(P)$ that takes as input a finite labelled graph $B$ and terminates only if a group with $R$-ball $B$ has $P$ then $P$ is recursively enumerable: indeed, given your group presentation $G$, one can in parallel try to compute all balls $B_R$ and input them into $T(P)$. If any of these eventually terminate then we know that $G$ has $P$.

So although this isn't a perfect match for the condition stated in the question (which asks for the algorithm to decide whether or not $G$ has $P$ based on the $R$-ball), I think recursively enumerable properties are a good approximation to what the question asks for.

Here's a brief list of some properties that we know are recursively enumerable:

• Hyperbolicity is recursively enumerable by a theorem of Papasoglu [Papasoglu, 'An algorithm detecting hyperbolicity'. Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994).].
• Automaticity is recursively enumerable by a theorem of Epstein et al [Epstein et al. Word processing in groups. Jones and Bartlett Publishers, Boston, MA, 1992. xii+330 pp].
• Property (T) is recursively enumerable by the theorem of Ozawa mentioned above.
• Limit groups in the sense of Sela are recursively enumerable by a theorem of Groves and myself. ...

In practice, almost all of these results involve checking some condition on some suitably large ball in the Cayley graph, so fall into at least the spirit of the question.

Recursive properties modulo the word problem

A property $P$ is recursive if both $P$ and not $P$ are recursively enumerable. The Adyan--Rabin theorem implies that this fails for every Markov property, meaning that very few non-trivial properties are recursive. There one or two exceptions, the most notable being anything that depends on the abelianisation.

The failure of most properties to be recursive can be traced back to the existence of finitely presented groups with unsolvable word problem (the Novikov--Boone theorem). So, as in the original question, it makes sense to ask whether assuming a solution to the word problem makes any properties $P$ recursive.

Groves, Manning and I called a property $P$ recursive modulo word problem if $P$ can be determined inside any class of group presentations in which the word problem is uniformly solvable. (There are other definitions that might encapsulate this idea better, as proposed for instance by Rauzy.) Remarkably, quite a few properties turn out to be recursive modulo the word problem, including:

• abelian-ness, and more generally nilpotence of class $k$ for any $k$;
• freeness, being the fundamenal group of a closed surfaces, and limit groups in the sense of Sela (Groves--W.),
• admitting a non-trivial free splitting (Touikan)
• being a geometric 3-manifold group (Groves--Manning--W.)