Vinberg's algorithm

A Lorentzian lattice $L$ is an integral $\Z$-lattice of signature $(s_+, s_-)$ with $s_+=1$ and $s_->0$. A root of $r \in L$ is a primitive vector s.t. reflection in the hyperplane $r^\perp$ maps $L$ to itself. Let $W(L)\leq O(L)$ be the Weyl group, that is the group generated by reflections in the root hyperplanes of $L$. We say that $L$ is reflective if $W(L)$ is of finite index in $O(L)$. For $x,y \in L$ we write $x.y:=\Phi(x,y)$ and $x^2:=\Phi(x,x)$ for the symmetric bilinear form in $L$.

See for example [Tur18] for the theory of Arithmetic Reflection Groups and Reflective Lorentzian Lattices.

Description

Vinberg's algorithm constructs a fundamental polyhedron $P$ for a Lorentzian lattice $L$ by computing its fundamental roots $r$, i.e. the roots $r$ which are perpendicular to the faces of $P$ and which have inner product at least 0 with the elements of $P$. Choose $v_0$ in $L$ primitive with $v_0^2 > 0$ as a point that $P$ should contain.

Let $Q$ be the Gram matrix of $L$ with respect to some basis. A vector $r$ is a fundamental root, if

• the vector $r$ is primitive,
• reflection by $r$ preserves the lattice, i.e. $\frac{2}{r^2} r Q$ is an integer matrix,
• the pair $(r, v_0)$ is positive oriented, i.e. $r. v_0 > 0$,
• the product $r. \~{r} \geq \ 0$ for all roots $\~{r}$ already found.

This implies that $r^2$ divides $2 i$ for $i$ being the level of $Q$, i.e. the last invariant of the Smith normal form of $Q$.

$P$ can be constructed by solving $r.v_0 = n$ and $r^2 = k$ by increasing order of the value $\frac{n^2}{k}$ and $r$ satisfying the above conditions.

If $v_0$ lies on a root hyperplane, then $P$ is not uniquely determined. In that case we need a direction vector $v_1$ which satisfies $\~{v}. v_1 \neq 0$ for all possible roots $\~{v}$ with $v_0. \~{v} = 0$

With $v_0$ and $v_1$ fixed $P$ is uniquely determined for any choice of root lengths and maximal distance $v_0.r$. We choose the first roots $r$ by increasing order of the value $\frac{\~{r}. v_1}{r^2}$ for all possible roots $\~{v}$ with $v_0. \~{v} = 0$. For any other root length we continue as stated above.

For proofs of the statements above and further explanations see [Vin75].

Function

vinberg_algorithm(Q::ZZMatrix, upper_bound; v0::ZZMatrix, root_lengths::Vector{ZZRingElem}, direction_vector::ZZMatrix) -> Vector{ZZMatrix}

vinberg_algorithm(S::ZZLat, upper_bound; v0::ZZMatrix, root_lengths::Vector{ZZRingElem}, direction_vector::ZZMatrix) -> Vector{ZZMatrix}

Contact

Please direct questions about this part of OSCAR to the following people:

• Simon Brandhorst.
• Stevell Muller,

You can ask questions in the OSCAR Slack.

Alternatively, you can raise an issue on github.