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?



algorithm to compute the integral orthogonal group
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](http://magma.maths.usyd.edu.au/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](http://www.normalesup.org/~page/software.html), 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.


