For which groups is (non-)left orderability decidable?

Mainly, my question is in the title, but let me be more precise here.

Let $G$ be a finitely presented group with solvable word problem. If G is not left-orderable, is there an finite-time algorithm to establish this fact?

If the answer to the above question is unknown, is it known in the case $G$ is the fundamental group of a 3-manifold? Or is there a class of groups where it is known?

• Given your assumptions, then there is an algorithm. Solvable word problem means that one may construct the Cayley graph to some radius. If there is a total order on the ball of radius R compatible with all multiplications that land in that ball, for all R, then the group is orderable. So by the contrapositive, if it is not orderable, then there is some R such that any ordering on a ball of radius R in the Cayley graph is inconsistent. The difficult thing is to show that groups (including 3-manifold groups) are orderable. Without the caveat that $G$ is non-orderable, then this is open. May 22 '17 at 18:56
• The question is unclear. What's the input? Starting with "let $G$ be a group" sounds like $G$ is fixed. There should be something like some presentiation is the input...! The title even sounds like it's senseless. For a given group, the veracity of left-orderability is a Boolean variable.
– YCor
May 22 '17 at 21:16
• @YCor, a group can be given by a Turing machine solving it's word problem. The generators are the input alphabet of the Turing machine and you get a recursive presentation by saying all accepted words are 1. If you want to use the decidability of the word problem the Turing machine for the word problem should be part of the input. May 22 '17 at 23:21
• @DerekHolt -- sure: the class of groups with solvable word problem is such a class!
– HJRW
May 23 '17 at 19:27
• @HJRW I'm somewhat not convinced that I should be satisfied by phrasing of questions which (1) give a strong suspicion that the person who asked the question does not know exactly what (s)he's asking, namely is not aware that an algorithmic question involves an input, and that "a group" is not an acceptable input (2) given my best efforts, stay several potential interpretations which don't make the question senseless of trivial, and for which other users like Benjamin provide an interpretation distinct from any I could guess.
– YCor
May 23 '17 at 22:22

This is a very nice question, which I don't know how to answer. But I hope the following (shameless self-promotion) will be of interest.

You seem to be looking for some sort of local condition that certifies the (non-)existence of an ordering. Lars Louder and I made the following definition, which seems to encapsulate a certain simple class of orders in a finite amount of data. Definition: Consider a finite, 2-dimensional cell complex $X$ given by the following data: a finite disjoint union of circles $\mathbb{S}$ and an immersion to a finite graph $$\partial:\mathbb{S}\to\Gamma ~.$$ [Hopefully it's clear that $\Gamma$ is the 1-skeleton of $X$ and $\partial$ is the coproduct of the attaching maps of the 2-cells.] A stacking of $\partial$ is an embedding $\hat{\partial}:\mathbb{S}\to\Gamma\times\mathbb{R}$ so that $\pi\circ\hat{\partial}=\partial$ (ie $\hat{\partial}$ is a lift of $\partial$).

A point $x$ of $\mathbb{S}$ is called upper if, whenever $\partial(x)=\partial(y)$, the $\mathbb{R}$-coordinate of $\hat{\partial}(x)$ is greater than the $\mathbb{R}$-coordinate of $\hat{\partial}(y)$. Lower points are defined similarly.

The stacking $\hat{\partial}$ is called good if every component of $\mathbb{S}$ contains at least one upper point and at least one lower point.

It's easy to see that the existence of a stacking is equivalent to an order on a certain finite subset of the group; so in particular, if $\pi_1X$ is orderable then a stacking exists. More interestingly, goodness enables a kind of converse.

Proposition: If $X$ admits a good stacking then $\pi_1X$ is left-orderable.

More precisely, you can deduce from our results that, if $X$ has a good stacking, then $\pi_1X$ is locally indicable, and it then follows that $\pi_1X$ is orderable by the Burns--Hale theorem. (It would be nice to have a more direct proof of this fact!)

Note that a good stacking can be found algorithmically. In particular, this provides the kind of "local certificiation" of orderability that I think is relevant to the question.

The following can also be deduced from our results.

Proposition: A finitely presented subgroup $H$ of a one-relator group has a presentation complex with a good stacking if and only if $H$ is torsion-free.

So this provides a class of examples (with solvable word problem) in which orderability can be algorithmically determined.

I would tentatively conjecture that there are other classes of examples that good stackings can also certify in this way. For instance, it's possible that the fundamental group of any compact, irreducible 3-manifold with boundary admits a presentation complex with a good stacking.

Unfortunately, there's no chance of applying this to closed 3-manifolds, since 2-complexes with good stackings are automatically aspherical. But perhaps there's some modification that works?

• I'd be delighted to know what you're answering. I only have a rough guess based on your comments and Benjamin's. My most plausible guess is the following: the question is whether there is an algorithm where the input is a group presentation and a possible algorithm for the word problem; the algorithm runs and when the algorithm of the input indeed solves the word problem for this presentation in the input, it stops in finite time with answer YES/NO giving a correct answer to the question "does the given group presentation define a left-orderable group?".
– YCor
May 23 '17 at 22:29
• @YCor, well, the question actually only asks for a one-sided algorithm that answers "NO" if the given fp group is not left-orderable. But my answer describes a YES/NO algorithm, as in your comment, that works in the class of finitely presented subgroups of one-relator groups.
– HJRW
May 24 '17 at 8:29