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?

1$\begingroup$ Please define "compute". Do you mean a finite set of generators? $\endgroup$ – Marguax Sep 29 '13 at 21:47

$\begingroup$ @Marguax For my current purpose a finite set of generators will do. As I am sure you know, in general knowing a finite set of generators tells you very little about the group (for example, it is probably undecidable to find the presentation), so I am guessing this is hard here also. $\endgroup$ – Igor Rivin Sep 29 '13 at 21:53

$\begingroup$ This is very close to mathoverflow.net/questions/136338 ("Does anyone know of any papers in which structural aspects of the orthogonal group of some indefinite nonunimodular integral lattice are calculated?"). See also mathoverflow.net/questions/141284 (asking for generators of the automorphisms of the diagonal form $(19,5,1)$). $\endgroup$ – Noam D. Elkies Sep 29 '13 at 22:22

1$\begingroup$ @NoamD.Elkies, right, the new user "few_reps" indicated that there would be a preprint on the arxiv but was not otherwise specific. I'm guessing that the author of the preprint will not be named "few_reps" $\endgroup$ – Will Jagy Sep 29 '13 at 22:51

1$\begingroup$ @NoamD.Elkies in fact, it seems that Vinberg's algorithm is at least formulated only for forms looking like $k x_0^2 + \sum_{i=1}^n x_i.$ I don't know how crucial that is... $\endgroup$ – Igor Rivin Sep 29 '13 at 23:22
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^2ay^2bz^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 3manifolds 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&j1\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&j1\end{pmatrix}$, $\begin{pmatrix}j&j+1\\0&j+1\end{pmatrix}$ and $\begin{pmatrix}1&0\\j1&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.

$\begingroup$ Truly you are wise in the ways of science :) $\endgroup$ – Igor Rivin Oct 3 '13 at 13:51


$\begingroup$ I mean exactly what I say (by the way, in the comment to few_reps' answer I give the quadratic form, so maybe you can see if this is something you already know...) Thanks! $\endgroup$ – Igor Rivin Oct 3 '13 at 17:12

$\begingroup$ I have added your example. Hopefully I didn't make any mistake. Of course the computation is less straightforward than with few_reps's method. $\endgroup$ – Aurel Oct 7 '13 at 9:28

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.

$\begingroup$ Sure, the quad. form is: {{0, 1, 1, 1}, {1, 0, 1, 1}, {1, 1, 0, 1}, {1, 1, 1, 0}} (in mathematica format). $\endgroup$ – Igor Rivin Oct 3 '13 at 17:11

$\begingroup$ @few_reps: I would be happy to see your paper on arXiv soon. Reading it will be a very interesting continuation of what we discussed before. I'm interested if your method can generate Coxeter or rationalofpi angled polytopes in dimension four. $\endgroup$ – SashaKolpakov Oct 3 '13 at 17:19

$\begingroup$ This is a reflection group generated by 4 elements : $\endgroup$ – few_reps Oct 3 '13 at 17:28

$\begingroup$ $[[ 1, 0, 0, 0],[ 5, 3, 1, 1],[10, 4, 1, 2],[10, 4, 2, 1]]$, $[[0, 1, 0, 0],[1, 0, 0, 0],[0, 0, 1, 0],[0, 0, 0, 1]]$, $[[ 2, 2, 0, 1],[ 0, 1, 0, 0],[ 2, 4, 1, 2], [ 3, 6, 0, 2]]$, $[[1, 0, 0, 0],[0, 1, 0, 0],[0, 0, 0, 1],[0, 0, 1, 0]]$, (matrices act on the right) $\endgroup$ – few_reps Oct 3 '13 at 17:31

$\begingroup$ @Sasha : I'm working on it, but have first to finish the implementation ... $\endgroup$ – few_reps Oct 3 '13 at 17:37