Skip to main content
MathOverflow

Return to Answer

replaced the link to the arXiv front end; see https://meta.mathoverflow.net/questions/5124/is-it-time-to-replace-links-to-the-ucdavis-arxiv-frontend
Source Link
Martin Sleziak
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

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 computationreal 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 paperManning'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 thisI 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.

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.

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.

added 5 characters in body
Source Link
Ian Agol
Ian Agol
  • 68.8k
  • 3
  • 194
  • 358

To make the question precise, you should probably specify what model of computation you want to answer the question in? For example, if the matricesmatrix entries are given by algebraic integersnumbers, 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.

To make the question precise, you should probably specify what model of computation you want to answer the question in? For example, if the matrices are given by algebraic integers, 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.

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.

Source Link
Ian Agol
Ian Agol
  • 68.8k
  • 3
  • 194
  • 358

To make the question precise, you should probably specify what model of computation you want to answer the question in? For example, if the matrices are given by algebraic integers, 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.