Leaf spaces and transverse structures — Question 8.7

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A left order on a group $G$ is a total order $<$ satisfying $g<h\Rightarrow ag<ah$. Its positive cone is $G^+=\{g:1<g\}$, with $G=G^+\sqcup\{1\}\sqcup(G^+)^{-1}$ and $G^+G^+\subseteq G^+$. Fix finite word encodings for a finitely generated group. For a class $\mathsf T$ of machines, a $\mathsf T$-order means that its positive cone is recognized by a machine in that class; in the finite-state case the source considers geodesic word representatives.

Statement recorded in the supplied source.

For fundamental groups $G=\pi_1(M)$ of hyperbolic $3$-manifolds, determine which computational kinds of left orders exist, as the machine class $\mathsf T$ varies. Include finite-state automata, Turing machines and Turing machines with a specified oracle $O$. Classify the complexity of recognizing positive elements, rather than only whether the group is left-orderable. [S2]

Short English statement

Classify the computational complexity of left orders on hyperbolic manifold groups, from finite automata to ordinary and oracle Turing machines.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 10300030 (AMR-102-0030). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Danny Calegari, Problems in foliations and laminations of 3-manifolds, version 0.78 (2002), Question 8.7; Definitions 1.1--1.10 and local definitions and remarks. https://arxiv.org/abs/math/0209081v1.