Suppose I have a discrete group $G<\mathrm{SL}_2(\mathbb{C})$, and it is finitely generated by some known generators. That is, $G=\langle g_1,\dots,g_n\rangle$.

The Frobenius norm of a matrix $m=\begin{pmatrix}a&b\\ c&d\end{pmatrix}$ is $\|m\|:=\sqrt{|a|^2+|b|^2+|c|^2+|d|^2}$. The set of elements in $G$ having the same Frobenius norm is a discrete subset of a compact set, and therefore is finite.

I'm interested in algorithms for enumerating elements of $G$ by their Frobenius norm. That is, find all elements of smallest (nontrivial) Frobenius norm, then find all elements of next smallest Frobenius norm, etc. I have different techniques for different cases using other properties of the groups, but what is an efficient algorithm to do this generally, knowing only that we are given the generators?

  • 1
    $\begingroup$ The Frobenius norm is related to $d(mj,j)$ where $j$ is the $(0,0,1)$ in the upper-space model of hyperbolic space. If your group is geometrically finite, computing first a Dirichlet domain allows you to enumerate elements by increasing $d(mj,j)$. $\endgroup$ – Aurel Mar 21 '16 at 10:14
  • 1
    $\begingroup$ @Aurel Actually I know exactly what you mean, and that's related to what I'm doing. But I want to do this in order to compute Dirichlet domains -- if I already have my domain I no longer care about this problem. In fact I've read your paper on Dirichlet domains for arithmetic Kleinian groups and enjoyed it very much. I'm doing something involving non-arithmetic groups. $\endgroup$ – j0equ1nn Mar 21 '16 at 10:18
  • 2
    $\begingroup$ Thanks :-) I see. Are your groups geometrically finite, or do you want to recursively enumerate a Dirichlet domain even for non geometrically finite groups? If the group is geometrically finite given by generators, even if it is non-arithmetic, I give an algorithm in my paper (despite the title, see section 2.4.1). $\endgroup$ – Aurel Mar 21 '16 at 10:29
  • $\begingroup$ They are geometrically finite. I did not remember that part of the paper, I'll have another look! $\endgroup$ – j0equ1nn Mar 21 '16 at 10:34
  • $\begingroup$ @Aurel I see what you mean about your algorithm applying to arbitrary finitely generated Kleinian groups (which are necessarily geometrically finite). But without the extra info gained from quaternion orders, the run-time seems exponential, right? We can search through words in the generators by length but this gives no guarantee of finding elements contributing faces any time soon. Maybe this is really the nature of the problem, and a non-arithmetic approach really should be case-by-case to be efficient. What do you think? $\endgroup$ – j0equ1nn Mar 21 '16 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.