8
$\begingroup$

I am studying finite index subgroups of certain finitely presented groups. The particular conditions on my groups make this problem easier than I phrase it here, but I am curious about a more general answer. After the main question I will indicate a simplified case for which there is probably a simplified answer.

Suppose you have a group of matrices $G\subset\mathrm{GL}_n(R)$ over a ring $R$, and suppose it is finitely generated so that $G=\langle g_1,\dots,g_n\rangle$. Next suppose you are given a matrix $m\in G$ and you want to know how to write it as a word in the generators, as short as possible. What is an efficient way of computing this?

An inefficient solution that will give you a word (not necessarily the shortest) is to systematically go through all possible words and check by multiplying them together until $m$ is a result, which is possible since the set of words on $n$ letters is countable.

Perhaps a smarter approach is to compute the Jordan canonical form of $m$ and of each of the $g_i$, then find a basis for $G$ in which you can write each of the $g_i$ as well as $m$, upon which the solution can be found just be piecing words together rather than having to multiply matrices each time. I'm uncertain if this would lead one to discover the shortest word. Even if it did, perhaps there is a more efficient process.

The easier sub-case: Suppose $G\subset\mathrm{PSL}_2(\mathbb{C})$ is discrete and arithmetic, i.e. is Kleinian and has a representation into $\mathrm{GL}_n(\mathbb{Q})$ for some $n$. Moreover, suppose $m=\overline{g}^{\top}g$ (it is Hermitian) for some $g\in G$. Is there an especially nice choice of generators for $\mathrm{PSL}_2(\mathbb{C})$ into which $m$ and the $g_i$ can be factored? Or, perhaps a better approach than that? I'm feeling like the eigendecomposition could be useful, perhaps by using $m$'s pair of orthogonal eigenvectors and the limited ways of splitting their eigenvalues (which are real) over the coefficient ring.

Improve this question
$\endgroup$
13
  • 5
    $\begingroup$ 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. $\endgroup$
    – David Loeffler
    Commented Oct 18, 2015 at 9:08
  • $\begingroup$ 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. $\endgroup$
    – Derek Holt
    Commented Oct 18, 2015 at 10:53
  • $\begingroup$ 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. $\endgroup$
    – HJRW
    Commented Oct 18, 2015 at 14:57
  • $\begingroup$ @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. $\endgroup$
    – j0equ1nn
    Commented Oct 18, 2015 at 20:55
  • 1
    $\begingroup$ 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 $\endgroup$
    – HJRW
    Commented Oct 22, 2015 at 20:02

2 Answers 2

Reset to default
4
$\begingroup$

As to your general question, there is a method which is better than the inefficient solution you give. -- Namely, compute spheres of radii $r = 1, 2, \dots$ with respect to the word metric about the identity and about the element $m$ to be factored, until these spheres intersect nontrivially. This way you always get the shortest possible word as desired, and depending on the structure of your group, you save a significant amount of runtime and memory. Also, you only need to store spheres of $3$ distinct radii $r-1, r, r+1$ about each of $1$ and $m$ at a time, which further reduces memory requirements -- how much, depends again on the structure of your qroup.

That said, in general the runtime- and memory requirements of this method are still exponential in the word length; I think it is not likely that without dropping the requirement to obtain a word of minimal length you can do much better in general, as the problem of finding a word of minimal length is already hard for finite permutation groups (popular example: solving the Rubik's Cube with the smallest possible number of moves).

Improve this answer
$\endgroup$
9
  • $\begingroup$ When you say spheres of radii $r$ about the identity and $m$, I think you mean in the word metric, yes? For example if $G=\langle g,h\rangle$ then $S_1(1)=\{g,g^{-1},h,h^{-1}\}$, $S_2(1)=\{g^2, gh, gh^{-1}, hg, hg^{-1}, h^2\},\dots$ and $S_1(m)=\{gm,g^{-1}m,hm,h^{-1}m,mg,mg^{-1},mh,mh^{-1}\},\dots$. I'd been doing this only considering spheres around $1$ and waiting until I hit $m$. Your suggestion is definitely an improvement as it vastly cuts down the length on later things to check. $\endgroup$
    – j0equ1nn
    Commented Oct 18, 2015 at 21:17
  • 2
    $\begingroup$ @j0equ1nn: Yes, I mean the word metric. (Though you omitted some elements from $S_2(1)$, which is $\{g^2,gh,gh^{-1},g^{-2},g^{-1}h,g^{-1}h^{-1},hg,hg^{-1},h^2,h^{-1}g,h^{-1}g^{-1},h^{-2}\}$, and likewise $S_1(m)$ should be $m S_1(1)$ and have cardinality $4$.) $\endgroup$
    – Stefan Kohl ♦
    Commented Oct 18, 2015 at 21:36
  • $\begingroup$ You're right, that list was incomplete, thanks for the correction. But why would we not need to consider multiplication on the other side in $S_r(m)$? $\endgroup$
    – j0equ1nn
    Commented Oct 18, 2015 at 22:04
  • 2
    $\begingroup$ @j0equ1nn: Multiplication from one side is enough since you can bring factors to the other side by conjugation, and since the spheres about $1$ with which you take the intersections are closed under cyclic conjugation (i.e. for example if $gh^2$ lies in the spheree, then also $h^2g = (gh^2)^g$ and $hgh = (gh^2)^{h^{-1}})$.. $\endgroup$
    – Stefan Kohl ♦
    Commented Oct 18, 2015 at 22:29
  • 1
    $\begingroup$ The algorithm that Stefan gave is the one that works for my purposes, and has cool tricks to reduce run-time. Since there are no other suggestions for shorter algorithms, I say this is a great answer. $\endgroup$
    – j0equ1nn
    Commented Oct 22, 2015 at 18:30
6
$\begingroup$

For the general case (i.e. no restrictions on the set $\{ g_1,\ldots,g_n \}$), one cannot get a computable upper bound on the runtime of any algorithm for the dimension $m\geq 4$. It follows from the undecidability of the membership problem in $SL_4(\mathbb{Z})$ due to Mikhailova. If one had an algorithm with a computable upper bound for the running time, then we could run it on any matrix $g\in SL_m(\mathbb{Z})$ and stop if it takes longer than our bound. After that we could check if the output indeed gives a word such that $g=g_{i_1}g_{i_2}\ldots g_{i_s}$ and hence we would solve the membership problem.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I suppose that in the algothithm suggested here by @StefanKohl , an upper bound could be expressed exponentially in terms of $n$ and the length of $g$, but since we don't know the length of $g$ this is a moot point. In my application I expect that the $g$ I need to test will be rather short, and I expect I can get the results I need with his algorithm. Also I get to use $\mathrm{PSL}_2(\mathbb{C})$. What might be known about decidability of membership for dimension $m=2$? $\endgroup$
    – j0equ1nn
    Commented Oct 20, 2015 at 17:36
  • 2
    $\begingroup$ The membership problem for lattices in $PSL_2(\mathbb{C})$ is decidable: see arXiv:1401.2648 . $\endgroup$
    – HJRW
    Commented Oct 20, 2015 at 19:13
  • $\begingroup$ BTW while this is an informative answer, it does not address the specific question because in the given setup, one knows that the $g$ is generated by the given generators. So we are not trying to determine membership, but rather an efficient way of finding a word of minimal length, knowing that one does exist. $\endgroup$
    – j0equ1nn
    Commented Apr 1, 2016 at 21:38
  • $\begingroup$ To j0equ1nn: the upshot was that if we could find a computable estimation to solve the expressibility (in the case when we know the element is expressible!), we would be able to use it to solve the membership problem in $SL(4,\mathbb{Z})$, which is undecidable. Factually it means that in the bad cases the length of the expression of your element is not bounded by any recursive function (polynomial, exponential, tower exponential...) on the data you are given (norms of the matrices). Still, it might be that you deal with the good cases, when the generator matrices give a nice subgroup. $\endgroup$
    – Al Tal
    Commented Apr 5, 2016 at 10:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .