algorithm to compute the integral orthogonal group

Question

Suppose I have an indefinite quadratic form over the integers, and I want to compute its orthogonal group. Is there an algorithm, or at least a heuristic? If yes, is there any implementation anywhere?

Answer 1

Since the group you are looking for is arithmetic, you could in principle apply the algorithms from Some general algorithms. I: Arithmetic groups by Fritz J. Grunewald and Daniel Segal. However, to my knowledge nobody has implemented these algorithms and they would probably be rather inefficient.

In special cases you may have a better chance.

Consider the case of a ternary quadratic form $q$ and suppose you have an order $\mathcal{O}$ in an indefinite quaternion algebra over $\mathbb{Q}$ such that $q$ is the restriction of the reduced norm on the trace zero submodule of $\mathcal{O}$ (for example, this will be the case for the quadratic form $q(x,y,z)=abx^2-ay^2-bz^2$ by choosing the order $\mathbb{Z}+\mathbb{Z}i+\mathbb{Z}j+\mathbb{Z}ij$ where $i^2=a, j^2=b$ with nonzero $a,b\in \mathbb{Z}$, not both negative). Then the orthogonal group of $q$ is isomorphic to $\Gamma=N(\mathcal{O})/\mathbb{Q}^*$ where $N(\mathcal{O})$ is the normalizer of $\mathcal{O}$ in $B^*$. The finite index subgroup $\Gamma^+$ of elements of positive norm in $\Gamma$ is a Fuchsian group with finite covolume, so a presentation for this group can be found efficiently, for example by applying the algorithms from Computing fundamental domains for Fuchsian groups by John Voight that are available in Magma. From there you can go back to the group you are interested in.

More generally if your quadratic form has signature $(n,1)$ you should be able to compute a fundamental domain for the orthogonal group acting on the hyperbolic $n$-space, but I do not know any implementation that would do it directly. If $n=3$ you can use my algorithms from Computing arithmetic Kleinian groups that are implemented in Magma, but first you have to relate your quadratic form to some quaternion algebra (see The arithmetic of hyperbolic 3-manifolds by Colin Maclachlan and Alan W. Reid, section 10 for details).

Edit : let's do the construction for your example $A = \begin{pmatrix}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\end{pmatrix}$.

Since this quadratic form is isotropic with discriminant $-3$, we know that the orthogonal group is commensurable with the Bianchi group of $\mathbb{Q}(\sqrt{-3})$.

Let $L$ be the $\mathbb{Z}$-module generated by $\begin{pmatrix}0&0\\1&0\end{pmatrix}$, $\begin{pmatrix}0&-1\\0&0\end{pmatrix}$, $\begin{pmatrix}1&-1\\1&-1\end{pmatrix}$ and $\begin{pmatrix}-j&-1\\1&-j-1\end{pmatrix}$ where $j$ denotes a third root of unity. Then you can check that the Gram matrix of the determinant in this base is $A$ (in general, such an $L$ is given by a Clifford algebra construction).

Let $\sigma$ be the nontrivial automorphism of $F=\mathbb{Q}(j)$, $R=\mathbb{Z}[j]$, $\mathfrak{p}$ the unique prime above $3$. Define an action of $\mathrm{GL}_2(F)$ on $\mathrm{M}_2(F)$ by $g\cdot m = gmg^{-\sigma}$. Let $G = \{g\in\mathrm{GL}_2(F)\ |\ \det(g)\in\mathbb{Q}\text{ and }g\cdot L = L\}$. Then general arguments show that $\Gamma = G/\mathbb{Q}^*\simeq SO^+(A;\mathbb{Z})$ with the action we defined.

Let $I = L+jL$. Then every element stabilizing $L$ also stabilizes $I$. It is easy to see that $I = \{m\in\mathrm{M}_2(R)\ |\ \mathrm{tr}(m)\in\mathfrak{p}\}$. The (projective) stabilizer of $I$ is $\mathrm{PGL}_2(R)$ (the stabilizer contains this group, and this group is maximal). Let $V=\sqrt{-3}\mathrm{id}\mathbb{Q}+\mathrm{ker}(\mathrm{tr})\cap\mathrm{M}_2(\mathbb{Q})$. Then $L=V\cap I$, and every matrix with determinant in $\mathbb{Q}^*$ stabilizes $V$. Since every matrix in $\mathrm{GL}_2(R)$ is proportional to a matrix with rational determinant, we have $\Gamma = \mathrm{PGL}_2(R)$. The generators computed by my code are $\begin{pmatrix}-j&j\\0&-j-1\end{pmatrix}$, $\begin{pmatrix}-j&j+1\\0&j+1\end{pmatrix}$ and $\begin{pmatrix}-1&0\\-j-1&1\end{pmatrix}$, and the corresponding orthogonal matrices are

$g_1 = \begin{pmatrix}-1&0&-1&0\\-1&-1&0&0\\1&0&0&0\\-1&0&0&-1\end{pmatrix}$,

$g_2 = \begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}$,

and

$g_3 = \begin{pmatrix}-1&0&-1&0\\0&0&-1&-1\\0&0&1&0\\0&-1&-1&0\end{pmatrix}$, but you can use your favorite generators for $\mathrm{PGL}_2(R)$ instead.

Answer 2

I am currently writing such an algorithm (in Magma) for Lorentzian lattices. It is almost finished and has already been used to answer this question on MO.

It furnishes a fundamental domain for the action of the group of automorphisms $G$ of the lattice on the hyperbolic space, and identifies the boudary components. Thus it may be used to obtain a finite presentation of $G$.

Perhaps this algorithm will be available directly on Magma someday ... Now if you have an example in head, just tell me, I can perform the computations for you (if your example in not too twisted ... computations become quickly heavy).

Edit :

For your example : the Gram matrix is

A=  [0 1 1 1]
    [1 0 1 1]
    [1 1 0 1]
    [1 1 1 0] 

A fundamental domain is the convex hull of the following 4 points :

a=(0,0,1,1), b=(0,1,1,1), d=(1,1,1,1), c=(0,0,0,1)

(suitably rescaling a,b,c to make them fall in $\mathcal H_3$. The point c is a cusp.)

The reflections supported by the faces of this tetrahedron are

[-1  1  1  1] (a,b,c)
[ 0  1  0  0]
[ 0  0  1  0]
[ 0  0  0  1]

[0 1 0 0] (a,c,d)
[1 0 0 0]
[0 0 1 0]
[0 0 0 1]

[1 0 0 0] (b,c,d)
[0 0 1 0]
[0 1 0 0]
[0 0 0 1]

[1 0 0 0] (a,b,d)
[0 1 0 0]
[0 0 0 1]
[0 0 1 0]

The matrices I gave in the comments below are conjugated to these.