Algorithm to test for discrete or quasi-Fuchsian subgroups of PSL(2,C)

Question

Let $\Gamma = \pi_1(S)$ denote the fundamental group of a compact surface $S$ of genus $g>1$.

Given a representation $\rho : \Gamma \to \mathrm{PSL}(2,\mathbb{C})$, specified by matrix representatives for the images of a fixed generating set, is there an algorithm to answer either of the following questions?

1) Is the image $\rho(\Gamma)$ a quasi-Fuchsian group?

2) Is the image $\rho(\Gamma)$ discrete?

There are a number of related situations where I am aware of algorithms of this type, but all are limited to special classes of two-generator subgroups of $\mathrm{PSL}(2,\mathbb{C})$. For example:

• For two-generator subgroups of $\mathrm{PSL}(2,\mathbb{R})$ there is the Gilman-Maskit algorithm which tests for discreteness. There are some related sufficient conditions for discreteness in the two-generator case in $\mathrm{PSL}(2,\mathbb{C})$.

• For punctured torus groups (i.e. representations of $\mathbb{F}_2$ where $abab^{-1}$ maps to a parabolic element) in $\mathrm{PSL}(2,\mathbb{C})$ there is a method of Komori, Sugawa, Wada, and Yamashita based on simultaneously testing Jorgensen's inequality (attempting to find a certificate that the group is not discrete) while also trying to find a Ford fundamental domain (of a type that would give a certificate that the group is quasi-Fuchsian).

• Also in the punctured torus case, Bowditch has a conjectural characterization of quasi-Fuchsian groups in terms of a certain subset of the infinite trivalent tree of "generating triples", which is easy to test algorithmically. As in the previous case this can be combined with Jorgensen's inequality to get a heuristic test for discreteness.

Based on these cases I would especially like to know about methods for discreteness or quasi-Fuchsian testing that apply in the compact surface case without assuming that the representation maps into $\mathrm{PSL}(2,\mathbb{R})$.

Answer 1

To make the question precise, you should probably specify what model of computation you want to answer the question in? For example, if the matrix entries are given by algebraic numbers, then I think you can just work with a Turing machine. I suppose you could also work with an oracle that gives you as many decimal places of the numbers that you like. However, I think this interpretation could have issues, because how do you tell if two numbers are equal? Maybe the natural interpretation then is to use real computation. In any case, I think the problem is open with either interpretation.

I think for subgroups of $PSL_2(\mathbb{R})$, there is an algorithm in either model extending the Gilman-Maskit algorithm. The point is that you either find a violation of Jorgensen's inequality (in fact, one can just find an irrational rotation in the subgroup generated by the matrices if the subgroup is not solvable), or you compute a finite-sided fundamental domain for the group (see e.g. Manning's paper).

The issue in the general case to implementing this algorithm is what do you do if the fundamental domain of the group has infinitely many sides, i.e. the group is degenerate? In the case of real computation, this seems to kill this approach to an algorithm.

If the matrices are algebraic, there's a chance this algorithm could work. The point is that I don't know of any degenerate groups with algebraic coefficients which are not fibers of a fibration. Let's suppose that any degenerate group with algebraic coefficients is a fiber of a fibration (I made a stab at trying to prove this, but I never published it since Walter Neumann pointed out to me that a generic degenerate group is transcendental, since there are uncountably many ending laminations, but countably many algebraic groups). Then either the group is geometrically finite, and one should be able to search for a finite-sided fundamental domain, or else it is the fiber of a fibration, and one should be able to compute a finite-volume hyperbolic 3-orbifold fibering over the circle, such that the fiber group is generated by the matrices.

In any case, I think there is a procedure to detect if a group is indiscrete, but no known procedure to detect if a group is discrete.

Answer 2

Indeed, the answer to the discreteness problem turns out to depend on the computability model. In the Real-RAM or BSS (Blum-Shub-Smale) model of computations over the reals, the answer is negative: The discreteness problem (for finitely generated nonelementary subgroups of $PSL(2,C)$) is undecidable, see here, as in the case of the Mandelbrot set $M$ (due to Blum, Shub and Smale). On the other hand, in the bit-computability model, the discreteness problem for finitely generated nonelementary subgroups of $PSL(2,C)$, turns out to be decidable. Interestingly, computability of the Mandelbrot set $M$ in the bit-computability model is still an open problem. However, $M$ is bit-computable, conditional on some major conjectures in holomorphic dynamics (say, local connectivity of $M$). This conditional result is due to Peter Hertling.