Timeline for What is the most efficient way to factor a matrix into a given set of generators?
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 22, 2015 at 20:08 | comment | added | j0equ1nn | @HJRW: Those look nice, that second one is pretty recent! I will have a look at these, thanks. | |
| Oct 22, 2015 at 20:04 | comment | added | HJRW | Perhaps I should also add that, at the cost of working with a bigger generating set, you probably don't need too fine a description of your fundamental domain. Check out the proof of the Svarc--Milnor Lemma. | |
| Oct 22, 2015 at 20:02 | comment | added | HJRW | If you want rigorous algorithms, some of the following may be of interest to you. arxiv.org/abs/1211.0264 arxiv.org/abs/math/0102154v2 arxiv.org/abs/1508.06720 | |
| Oct 22, 2015 at 18:28 | vote | accept | j0equ1nn | ||
| Oct 22, 2015 at 18:28 | comment | added | j0equ1nn | @HJRW: Yes, SnapPea does it well enough to get nice pictures, and well enough to use for some applications, but everything is in decimal approximations. You can be more precise about cusps since you can look carefully at maps on $\mathbb{C}\cong\partial\mathbb{H}^3$, but in general exact Dirichlet domains are difficult. | |
| Oct 22, 2015 at 9:14 | comment | added | HJRW | @j0equinn, this is beyond my pay grade. I thought SnapPea computes fundamental domains quite well in practice, but perhaps that's not what you're looking for. | |
| Oct 22, 2015 at 8:23 | comment | added | j0equ1nn | @HJRW: I understand what you mean, but I am using some additional info I did not explain to get more detailed info on certain Dirichlet domains. I realize it is more common to work in the other direction, but also (as far as I know) it is in general difficult to give an exact description of a Dirichlet domain. Like, how do we determine a sufficient finite subset of $G$ to check for contributing sides? Can the region be described using algebraic coordinates, if so in what field? With things like this we could compute exact volume, for insrance. | |
| Oct 20, 2015 at 19:18 | comment | added | HJRW | @j0equ1nn, preventing yourself from computing a fundamental domain beforehand means you're tying one hand behind your back. Almost all the progress that's been made in the last few decades on algorithms in groups has come from geometric considerations. You would write the $g_i$ and $m$ in terms of the new basis using the algorithm I suggested above: fix a a basepoint $*$ in your fundamental domain, compute $g_i*$ (or $m*$) and compute the geodesic $[*,g_i*]$. The face of the fundamenal domain you cross tells you the first generator in $g_i$, and you can then proceed by induction. | |
| Oct 20, 2015 at 12:44 | answer | added | Al Tal | timeline score: 6 | |
| Oct 18, 2015 at 21:53 | comment | added | j0equ1nn | @HJRW: In the problem we are forced to work with the given generators $g_1,\dots,g_n$. In addition I'm not allowing myself to assume I already have an effective computation of the Dirichlet domain (which I didn't say in the setup). But let's say I found a basis compatible with such a domain, how would I go about writing the $g_i$ and $m$ in this new basis? | |
| Oct 18, 2015 at 20:59 | comment | added | j0equ1nn | @DavidLoeffler: I know of the relationship to fundamental domains, but the problem is that in reality I'm trying to get a result about a fundamental domain, using this information. I can't assume I already know the fundamental domain. | |
| Oct 18, 2015 at 20:55 | comment | added | j0equ1nn | @DerekHolt: These groups are finitely presented, but they also always have a matrix representation of the form given, so perhaps I opened up too broadly. I've altered the statement to clarify. | |
| Oct 18, 2015 at 20:50 | history | edited | j0equ1nn | CC BY-SA 3.0 |
capitalized 2nd occurence of group g
|
| Oct 18, 2015 at 14:57 | comment | added | HJRW | As David Loeffler says, there's certainly a better way to do this using the geometry, at least in the Kleinian sub case. First, you need to know a fundamental domain. You then draw a geodesic from a base point * to m*. The first generator can be deduced from the face of the fundamental domain that the geodesic leaves, and one then proceeds by induction. I'm not sure of a reference, but this may even have been implemented in SnapPea. | |
| Oct 18, 2015 at 13:44 | answer | added | Stefan Kohl♦ | timeline score: 4 | |
| Oct 18, 2015 at 10:53 | comment | added | Derek Holt | I am bit puzzled because in the first sentence you referred to finite index subgroups of finitely presented groups, but the rest of your post did not mention presentations. | |
| Oct 18, 2015 at 9:08 | comment | added | David Loeffler | Jordan form, eigenvectors, etc feel like a red herring here -- the Jordan form of gh has essentially nothing to do with those of g or h. I'd guess that finding a "nice" fundamental domain is more likely to be a good starting point. There is a massive literature on the case of finite-index subgroups of $PSL_2(\mathbf{Z})$ (try googling "Farey symbols") and this might give you some useful pointers. | |
| Oct 17, 2015 at 23:11 | history | edited | j0equ1nn | CC BY-SA 3.0 |
added 263 characters in body
|
| Oct 17, 2015 at 22:41 | history | asked | j0equ1nn | CC BY-SA 3.0 |