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})$.

  • $\begingroup$ David - to clarify your last sentence, are you or are you not interested in the case where $\Gamma$ is a closed surface group? $\endgroup$ – HJRW Oct 18 '12 at 9:41
  • $\begingroup$ In any case, it seems like Misha's comment on Agol's answer pretty much finishes that case off. $\endgroup$ – HJRW Oct 18 '12 at 9:41
  • $\begingroup$ I edited the last sentence to clarify that I am interested in the closed surface case. $\endgroup$ – David Dumas Oct 18 '12 at 13:26

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.

  • 2
    $\begingroup$ Here is another supporting piece of evidence that the discreteness problem is algorithmically unsolvable: One can ask for an algorithm to determine if a surface group representation lies in the closure of the quasifuchsian space (i.e., is discrete and faithful). This question, in the context of quadratic polynomials, is known to be algorithmically unsolvable (a theorem of Shashikura in conjunction with an observation of Penrose). There is probably enough machinery in place to prove the same result in the context of Kleinian groups. $\endgroup$ – Misha Oct 18 '12 at 4:26
  • $\begingroup$ Real computation is what I had in mind. Certainly I would want to allow computing words in the generators of $\rho(\Gamma)$ and comparisons between traces or matrix entries as "basic operations". Thanks for your answers, which convince me there is no hope for an algorithm in general. As in the punctured torus case, when actually implementing such a test I will need to settle for heuristics that leave a thin set in the character variety "undecided". $\endgroup$ – David Dumas Oct 18 '12 at 13:53
  • $\begingroup$ @David: At least in theory, the "thin" subset should be the boundary $B$ of the quasifuchsian space. Outside of $B$ you have an algorithm to detect membership: One machine will search for a finitely-sided fundamental domain and the other will search for pairs of group elements contradicting Jorgensen's inequality. Eventually, one of the machines stops. The set $B$ is "thin" in Baire category sense, but, I would guess, has Hausdorff dimension $12g-12$, i.e., maximal possible. Proving that Hausdorff dimension of $B$ is greater than $12g-13$, I think, is an open problem. $\endgroup$ – Misha Oct 18 '12 at 17:28
  • $\begingroup$ ...Incidentally, showing that Hausdorff dimension of $B$ is greater than $12g-13$ is one way to prove algorithmic unsolvability (this is the argument that worked in the context of degree 2 polynomials). $\endgroup$ – Misha Oct 18 '12 at 17:36
  • $\begingroup$ Misha - it sounds like you're saying that algorithimic solvability implies some sort of geometric regularity. Could you give a hint or a reference for the Shashikura--Penrose material? $\endgroup$ – HJRW Oct 18 '12 at 21:13

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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.