\documentclass{amsart} \usepackage{amsfonts, amsmath, amssymb} \usepackage[norelsize]{algorithm2e} \usepackage{enumitem} \usepackage{xcolor} \usepackage[hidelinks]{hyperref} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{definition}{Definition} \newtheorem{remark}{Remark} % Places where an input of the author is still needed. \newcommand{\todo}[1]{\textcolor{red}{[TODO: #1]}} \newcommand{\Sym}{\operatorname{Sym}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\rank}{\operatorname{rank}} \newcommand{\Del}{\operatorname{Del}} \newcommand{\cone}{\operatorname{cone}} \newcommand{\linspan}{\operatorname{span}} \newcommand{\relint}{\operatorname{relint}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\RR}{\mathbb{R}} \newcommand{\QQ}{\mathbb{Q}} \begin{document} \author{Mathieu Dutour Sikiri\'c} \address{Mathieu Dutour Sikiri\'c, MSM programming, Karlovacka cesta 28B, 10452 Klinca selo} \email{mathieu.dutour@gmail.com} \title{Algorithms for computing iso-Delaunay domains} \date{} \begin{abstract} For a linear space \(T\) of quadratic forms, we describe an algorithm enumerating the iso-Delaunay domains of \(T\), and a randomized search for an iso-Delaunay domain all of whose extreme rays are positive definite. For the quadratic forms in six variables, the search finds \(1472\) pairwise inequivalent \(L\)-type domains all of whose extreme rays are positive definite, the smallest having \(24\) facets and \(47\) extreme rays. No such domain exists in dimension \(2\leq n\leq 5\). \end{abstract} \maketitle \section{Introduction} Let \(T\) be a linear space of symmetric \(n\times n\) matrices containing a positive definite one. The positive definite forms of \(T\) that have the same Delaunay tessellation form a relatively open polyhedral cone, an iso-Delaunay domain, also called a \(T\)-secondary cone \cite{DutourSikiriSchurmannVallentin2008}. For \(T=\Sym_n(\RR)\) these are the \(L\)-type domains of Voronoi's second reduction theory \cite{Voronoi1908}, and each full-dimensional one determines a combinatorial type of primitive parallelohedra. Several programs enumerate iso-Delaunay domains. Some treat only the full space \(T=\Sym_n(\RR)\): the secondary cone cruiser \texttt{scc} of Sch\"urmann and Vallentin \cite{SchurmannVallentinSCC}, which was one of the implementations used for the complete classification in dimension \(5\) \cite{DutourSikiricGarberSchurmannWaldmann2016}, and the program of Baburin and Engel, who found \(567\,613\,632\) combinatorial types of primitive parallelohedra in dimension \(6\), a lower bound since their enumeration is not complete \cite{BaburinEngel2013}. Others treat a general \(T\)-space: the GAP package \texttt{polyhedral} \cite{DutourSikiricGAPpolyhedral} and its C++ version \cite{DutourSikiricPolyhedralCommon}, which is the one described and used here, and the Julia code of Miebach \cite{Miebach2025}, who used it for the sphere coverings of Eisenstein, Gaussian and Hurwitzian lattices. We consider the following question: is there a full-dimensional iso-Delaunay domain all of whose extreme rays are positive definite forms? The extreme rays of the \(L\)-type domains include the rigid forms, whose \(L\)-type domain is a single ray, and the question was raised in the study of the six-dimensional rigid forms \cite{DutourVallentin2005}. In the classical case \(T=\Sym_n(\RR)\) the extreme rays of an \(L\)-type domain often include forms of rank \(1\), and for \(2\leq n\leq 5\) every full-dimensional domain has such a ray. We show that the answer is positive for \(n=6\). \begin{theorem} There exist \(L\)-type domains of positive definite quadratic forms in six variables, of dimension \(21\), all of whose extreme rays are positive definite. \end{theorem} In Section~\ref{sec:enum} we describe the enumeration of the iso-Delaunay domains of a space \(T\), together with a canonical interior point of a polyhedral cone, which is of independent interest. Section~\ref{sec:tests} gives test cases for the enumeration, over the Hermitian forms of imaginary quadratic rings. In Section~\ref{sec:search} we describe a randomized search for a domain all of whose extreme rays have full rank, and in Section~\ref{sec:dim6} we report its outcome for \(n=6\): \(1472\) pairwise inequivalent such domains. \section{Enumeration of iso-Delaunay domains}\label{sec:enum} \subsection{The input space} Let \(T \subset \Sym_n(\RR)\) be the rational linear space of symmetric matrices under consideration. We use its saturated integral matrix lattice \begin{equation} T_{\ZZ}=T\cap\Sym_n(\ZZ) \end{equation} and assume that it spans \(T\) over \(\RR\). Fix a \(\ZZ\)-basis \(B_1,\ldots,B_m\) of \(T_{\ZZ}\), and write \(\ell_u(x)=x^{t}B_u x\). Thus the integral coordinate vectors are exactly the integral matrices in \(T\). A point \(q=(q_1,\ldots,q_m)\in\RR^m\) represents the Gram matrix \begin{equation} Q(q)=\sum_{u=1}^{m} q_u B_u . \end{equation} The enumeration is performed inside the positive definite part of \(T\). A domain is represented by a Delaunay tessellation \(\Del(Q)\), an interior Gram matrix \(Q\), and an invariant short-vector family used for equivalence tests. \begin{definition} An iso-Delaunay domain in \(T\) is the relatively open cone of all positive-definite forms \(Q\in T\) that have a fixed Delaunay tessellation. Its closure is a rational polyhedral cone in \(T\). \end{definition} In particular, if \(U\in\GL_n(\ZZ)\) preserves \(T\), then \(Q\mapsto U^tQU\) preserves \(T_{\ZZ}\). Its induced matrix in the above \(T\)-coordinates therefore belongs to \(\GL_m(\ZZ)\). We write \(\GL(T_{\ZZ})\) for the group of these induced matrices. This integral coordinate structure is also used in the enumeration of \(T\)-perfect forms \cite{Schuermann2009}. The algorithm follows the \(T\)-secondary-cone theory of \cite{DutourSikiriSchurmannVallentin2008}, itself a generalization of Voronoi's reduction theory \cite{Voronoi1908}. The finite object that is enumerated is not the full infinite tessellation of \(\RR^n\), but a list of orbits of Delaunay polytopes together with facet adjacencies and stabilizer groups. \begin{remark}\label{rem:non_simplicial} For \(T=\Sym_n(\RR)\) the Delaunay tessellation of a form in a full-dimensional iso-Delaunay domain is a triangulation. For a general \(T\)-space this is no longer true: the Delaunay polytopes of a generic form of \(T\) need not be simplices. What characterizes the forms of a full-dimensional domain is that no Delaunay polytope imposes a nonzero linear equality on \(T\); see \eqref{eq:wall_inequality} below and Section~\ref{sec:initial}. \end{remark} \subsection{Linear inequalities from one Delaunay wall} The fundamental local computation is the construction of the wall inequality associated with a Delaunay polytope \(P\) and a neighbouring Delaunay polytope \(P'\). Let \(v_1,\ldots,v_s\in\ZZ^n\) be the vertices of \(P\), and choose an affine basis \(v_{i_0},\ldots,v_{i_n}\) of \(P\). For a test vertex \(w\), write \(w\) as an affine combination of this basis, that is, \begin{equation}\label{eq:affine_combination} \sum_{k=0}^{n}\lambda_k = 1,\qquad w = \sum_{k=0}^{n}\lambda_k v_{i_k}. \end{equation} Here ``affine basis'' means only that the \(n+1\) selected vertices are affinely independent, so the coefficients \(\lambda_k\) are real and uniquely determined. This differs from the terminology of Deza and Laurent \cite{DezaLaurent1997}, where an affine basis of a lattice polytope is required to give integral affine coefficients for every vertex of the polytope. That stronger condition cannot be imposed here: there exist Delaunay polytopes having no affine basis in the integral sense \cite{DutourSikiricGrishukhin2007}. Then the Delaunay condition that \(w\) is outside or on the circumsphere of the basis is the linear condition \begin{equation}\label{eq:wall_inequality} \sum_{u=1}^{m} q_u \left( \ell_u(w) - \sum_{k=0}^{n}\lambda_k \ell_u(v_{i_k}) \right) \geq 0 . \end{equation} When \(w\) is itself a vertex of \(P\) the left-hand side must vanish, which is a linear equality on \(T\); this linear form is nonzero exactly when \(P\) cannot remain a Delaunay polytope on an open subset of \(T\). For an actual facet adjacency \(P,P'\), any vertex of \(P'\setminus P\) gives the same inequality up to a positive scalar factor. The scalar is canonicalized by taking the unique primitive integral vector of the ray, which is possible since the coefficients of \eqref{eq:wall_inequality} are rational. All Delaunay-adjacency records producing that same wall are grouped together. For a Delaunay tessellation \(D\), one loops over all orbits of Delaunay polytopes and over all their facet adjacencies. This gives \begin{equation} a_1(q)\geq 0,\ldots,a_N(q)\geq 0, \end{equation} the full half-space description of the closure of the iso-Delaunay domain. Redundant inequalities are then removed, leaving the irredundant wall description used for adjacency. This redundancy removal is carried out by Clarkson's output-sensitive redundancy algorithm \cite{Clarkson1994}. The implementation is the one of \cite{DutourSikiricPolyhedralCommon}: it is built on an exact fraction-free simplex method, whose first phase is run in floating-point arithmetic and its terminal basis then certified, or repaired, in exact arithmetic, and it warm-starts the successive linear programs of Clarkson's algorithm. The same exact simplex method solves the linear programs of Algorithm~\ref{Algo_GeomInterior}. \begin{algorithm} \KwData{A Delaunay tessellation \(D\) represented by orbit representatives of Delaunay polytopes and their facet adjacencies; a basis \(B_1,\ldots,B_m\) of \(T_{\ZZ}\)} \KwResult{The irredundant wall inequalities of the iso-Delaunay cone of \(D\)} ${\mathcal A}\leftarrow \emptyset$.\\ \For{each orbit representative \(P\) of a Delaunay polytope of \(D\)}{ choose an affine basis \(v_{i_0},\ldots,v_{i_n}\) of \(P\).\\ \For{each facet-neighbour \(P'\) of \(P\)}{ choose a vertex \(w\in P'\setminus P\).\\ compute \(\lambda_0,\ldots,\lambda_n\) from \eqref{eq:affine_combination}.\\ \(a(q)\leftarrow\) the linear form occurring in \eqref{eq:wall_inequality}.\\ replace \(a\) by its primitive integral positive multiple.\\ append to \(a\) the adjacency record \((P,P')\).\\ ${\mathcal A}\leftarrow {\mathcal A}\cup\{a\}$, merging equal canonical inequalities and their adjacency records.\\ } } remove redundant inequalities from \({\mathcal A}\) by Clarkson's algorithm.\\ \KwRet{\({\mathcal A}\)} \caption{Wall inequalities of an iso-Delaunay cone} \label{Algo_WallInequalities} \end{algorithm} \subsection{A canonical interior point of a polyhedral cone}\label{sec:interior} The enumeration needs a representative point in the interior of each iso-Delaunay domain. The construction of this point is not specific to iso-Delaunay domains. It applies to any pointed rational polyhedral cone and gives a canonical representative whenever such cones are classified up to the action of an arithmetic group, for instance the perfect domains of Voronoi's algorithm \cite{Voronoi1908,Schuermann2009} as well as the iso-Delaunay domains considered here. We therefore state it in this generality, and return to iso-Delaunay domains at the end of this section. Let \begin{equation} C=\{q\in\RR^m : a_i(q)\geq 0,\ 1\leq i\leq N\} \end{equation} be a full-dimensional pointed polyhedral cone in \(\RR^m\) with rational facets. We take for \(a_1,\ldots,a_N\) the facet-defining inequalities of \(C\), each normalized to be primitive integral: \(a_i(q)=\langle \alpha_i,q\rangle\) with \(\alpha_i\in\ZZ^m\) having coprime coordinates. This list is determined by \(C\) up to order. The goal is to choose a point \(p(C)\) in the interior of \(C\) such that \begin{enumerate}[label=(\roman*)] \item \(p(C)\) depends only on \(C\), and not on the order of the inequalities; \item \(p(A\,C)=A\,p(C)\) for every \(A\in\GL_m(\ZZ)\). \end{enumerate} In particular \(p(C)\) is fixed by the stabilizer of \(C\) in \(\GL_m(\ZZ)\). A generic linear program would find an interior point, but the result would depend on accidental choices in the linear program. \paragraph{The first linear program.} The first step fixes the scale of the cone by working on the affine section \begin{equation} S=\{q\in\RR^m : a_i(q)\geq 1 \text{ for all } i\}. \end{equation} On this section minimize the symmetric objective \begin{equation}\label{eq:sym_objective} \sum_{i=1}^{N} (a_i(q)-1), \end{equation} which is the sum of all inequalities and is therefore independent of their order. The linear program is bounded and its optimal face \begin{equation} F=\left\{q\in S : \sum_i(a_i(q)-1)=\mu\right\}, \end{equation} where \(\mu\geq 0\) is the optimal value, is a polytope. Indeed, the linear form \(\sum_i a_i\) is positive on \(C\setminus\{0\}\): if it vanishes at \(q\in C\) then every \(a_i(q)\) vanishes, and \(q=0\) since \(C\) is pointed. If \(F\) is a single point, that point is returned. It lies in the interior of \(C\), since \(a_i(q)\geq 1>0\) for every \(i\). \paragraph{The degenerate case.} The recursion is cleanest in homogeneous coordinates, and this is how it is implemented. Put \(\hat q=(t,q)\in\RR^{1+m}\) and consider the cone \begin{equation} K=\{(t,q) : a_i(q)-t\geq 0,\ 1\leq i\leq N\}, \end{equation} whose section \(t=1\) is \(S\). The optimal value defines the hyperplane \begin{equation} H=\left\{(t,q) : \sum_{i=1}^N a_i(q)-(N+\mu)t=0\right\}, \end{equation} whose section \(t=1\) is the affine span of the optimal objective level. Inside the linear space \(H\), some of the inequalities \(a_i(q)-t\geq 0\) are equalities on all of \(K\cap H\). Let \(W\subseteq H\) be the linear space they define and let \(I\) be the set of the remaining inequalities, those that are not identically zero on \(W\). Then \(K\cap W\) is a full-dimensional cone of \(W\) described by the inequalities in \(I\), and its section \(t=1\) is \(F\). \begin{lemma}\label{lem:positive_t} If \(F\) is not a single point, then \(\mu>0\) and \(t>0\) on \((K\cap W)\setminus\{0\}\). \end{lemma} \begin{proof} If \(\mu=0\), the optimum is attained exactly at the points with \(a_i(q)=1\) for all \(i\). Two distinct such points differ by a nonzero \(d\) with \(a_i(d)=0\) for all \(i\), which contradicts the pointedness of \(C\). Hence \(\mu>0\). For \((t,q)\in K\cap H\), summing the inequalities \(a_i(q)\geq t\) gives \((N+\mu)t=\sum_i a_i(q)\geq Nt\), that is \(\mu t\geq 0\), so \(t\geq 0\). If \(t=0\), then every \(a_i(q)\geq 0\) and \(\sum_i a_i(q)=0\), so \(q=0\) as above. \end{proof} The construction is now applied recursively to the cone \(K\cap W\) of \(W\), in coordinates of \(W\). By Lemma~\ref{lem:positive_t} this cone is pointed and the point \((t_0,q_0)\) returned by the recursion has \(t_0>0\); the algorithm returns \(q_0/t_0\). This is a point of the relative interior of \(F\), hence an interior point of \(C\). The recursion terminates since \(\dim W<\dim H<1+m\). Indeed the objective is not constant on \(S\), which contains \(q+\lambda q'\) for \(q\in S\), \(q'\) in the interior of \(C\) and \(\lambda\geq 0\); hence \(F\) is a proper face of \(S\), at least one inequality \(a_i(q)\geq 1\) is tight on \(F\), and the corresponding inequality \(a_i(q)-t\geq 0\) is an equality on \(K\cap H\). \paragraph{Equivariance.} This construction uses only linear programming and linear algebra; no full dual-description computation is needed. Permuting the inequalities does not change the point. The recursion only uses the restrictions of the forms \(a_i(q)-t\) to \(W\), which do not depend on the basis chosen for \(W\). Let \(A\in\GL_m(\ZZ)\) act on coordinates by \(q\mapsto Aq\). The facet inequalities of \(A\,C\) are the forms \(a_i\circ A^{-1}\), and since \(A^{-1}\) is an integral unimodular matrix these are again primitive integral. Hence the normalized inequalities of \(A\,C\) are exactly the transforms of those of \(C\), each step above commutes with \(A\), and \(p(A\,C)=A\,p(C)\). Equivariance does not hold for an arbitrary linear change of coordinates, nor for an individual rescaling of the inequalities, because the primitive normalization depends on the lattice \(\ZZ^m\). The lattice must therefore be fixed before the point is computed. \begin{algorithm} \KwData{A full-dimensional pointed cone \(C=\{q\in\RR^m:a_i(q)\geq 0\}\), given by its facet inequalities \(a_i\), each primitive integral} \KwResult{A point \(p(C)\) in the interior of \(C\), equivariant under \(\GL_m(\ZZ)\)} Solve the linear program minimizing \(\sum_i(a_i(q)-1)\) subject to \(a_i(q)\geq 1\); let \(\mu\) be the optimal value and \(q^*\) a solution.\\ \If{the optimal face is the single point \(q^*\)}{ \KwRet{\(q^*\)} } \(K\leftarrow\{(t,q):a_i(q)-t\geq 0\}\), \(H\leftarrow\{(t,q):\sum_i a_i(q)-(N+\mu)t=0\}\).\\ \(W\leftarrow\) the subspace of \(H\) cut out by the inequalities that are equalities on \(K\cap H\).\\ Express the inequalities that are not identically zero on \(W\) in a basis of \(W\).\\ \((t_0,q_0)\leftarrow\) result of Algorithm~\ref{Algo_GeomInterior} applied to this cone of \(W\), mapped back to \(\RR^{1+m}\).\\ \KwRet{\(q_0/t_0\)} \caption{Geometrically unique interior point} \label{Algo_GeomInterior} \end{algorithm} The point of this canonical choice is the following statement, which reduces the equivalence of cones to the equivalence of points. \begin{lemma}\label{lem:canonical_equivalence} Let \(\Gamma\subseteq\GL_m(\ZZ)\) be a group and let \(\mathcal{F}\) be a \(\Gamma\)-invariant family of full-dimensional pointed rational polyhedral cones in \(\RR^m\) with pairwise disjoint interiors. For \(C,C'\in \mathcal{F}\), we have \(C'=A\,C\) for some \(A\in\Gamma\) if and only if \(p(C')=A\,p(C)\) for some \(A\in\Gamma\). \end{lemma} \begin{proof} If \(C'=A\,C\), then \(p(C')=A\,p(C)\) by equivariance. Conversely, if \(p(C')=A\,p(C)\), then this point lies in the interior of \(C'\) and in the interior of \(A\,C\in\mathcal{F}\). Since distinct cones of \(\mathcal{F}\) have disjoint interiors, \(C'=A\,C\). \end{proof} \paragraph{Application to iso-Delaunay domains.} In the coordinates \(q\) of the previous sections the lattice \(\ZZ^m\) is \(T_{\ZZ}\), and \(\GL(T_{\ZZ})\) is a subgroup of \(\GL_m(\ZZ)\). The closure \(C\) of a full-dimensional iso-Delaunay domain is pointed, since it is contained in the cone of positive semidefinite matrices, and its facet inequalities are the primitive integral ones produced by Algorithm~\ref{Algo_WallInequalities}. We write \(Q_C\) for the Gram matrix of the point \(p(C)\) and call it the interior form of the domain. The full-dimensional iso-Delaunay domains have pairwise disjoint interiors and are permuted by \(\GL(T_{\ZZ})\). Lemma~\ref{lem:canonical_equivalence} with \(\Gamma=\GL(T_{\ZZ})\) therefore shows that two such domains are equivalent if and only if their interior forms are; this is what makes the equivalence test of Section~\ref{sec:equivalence} correct. \subsection{Construction of an initial form}\label{sec:initial} It remains to construct a form lying in a full-dimensional iso-Delaunay domain. This is done iteratively. Fix a positive-definite matrix \(Q_{\mathrm{ref}}\in T\). Choose integral coefficients \(c_u\), form \begin{equation} Q=\sum_{u=1}^{m}c_uB_u, \end{equation} and add sufficiently many copies of \(Q_{\mathrm{ref}}\) to make \(Q\) positive definite. If an arithmetic automorphism of \(Q\) does not fix the \(T\)-space pointwise, discard \(Q\) and sample again. The automorphisms that fix \(T\) pointwise are automorphisms of every form of \(T\); a form with more symmetry is special in \(T\), and discarding it is a cheap way to avoid forms lying on walls. The random generation starts with simple forms: the coefficients \(c_u\) are sampled uniformly in \(\{-N,\ldots,N\}\), starting from \(N=2\). If the \(k\)-th candidate fails the tests below, \(N\) is increased by \(k\), so that \(N=2+k(k+1)/2\) after \(k\) failures. The precise rate of growth is not part of the mathematical algorithm; its purpose is to explore low-complexity forms first without restricting the search to a fixed finite set. For a form passing this symmetry test, enumerate its Delaunay tessellation. This enumeration may be stopped as soon as a Delaunay polytope imposes a nonzero linear equality on \(T\). Such an equality means that \(Q\) lies on a proper iso-Delaunay wall rather than in a full-dimensional domain. Once a tessellation \(D_0\) passes all tests, its wall inequalities are computed and Algorithm~\ref{Algo_GeomInterior} supplies the distinguished interior form \(Q_0\). The iterative construction is summarized in Algorithm~\ref{Algo_InitialIsoDelaunay}. \paragraph{A prescribed common form.} The enumeration may be restricted to the \emph{star} of a prescribed positive-definite form \(G=Q_{\mathrm{common}}\in T\): the set of full-dimensional iso-Delaunay domains whose closure contains \(G\). This is used when \(G\) lies on walls, for instance when \(G\) has a non-generic Delaunay tessellation. The seed must then be a domain of the star. Since the domains are cones, the form \(P+sG\) with \(P\) a generic form tends to the ray of \(G\) as \(s\to\infty\), and lies in a domain of the star for \(s\) large enough. The algorithm therefore samples \(P\) as above, tests \(Q=P+2^kG\) at the \(k\)-th attempt, and accepts a full-dimensional domain only if \(G\) belongs to its closure, that is, if \(a(G)\geq 0\) for all its wall inequalities \(a\). This test is made once for the whole domain after its Delaunay tessellation has been computed. \begin{algorithm} \KwData{The saturated \(T\)-space with basis \(B_1,\ldots,B_m\), a positive-definite form \(Q_{\mathrm{ref}}\in T\), and optionally a positive-definite form \(G=Q_{\mathrm{common}}\in T\)} \KwResult{A Delaunay tessellation \(D_0\) of a full-dimensional iso-Delaunay domain, whose closure contains \(G\) if \(G\) is given, and its distinguished interior form \(Q_0\)} \(k\leftarrow 0\), \(N\leftarrow 2\).\\ \While{no initial domain has been found}{ Choose random integral coefficients \(c_1,\ldots,c_m\) in \(\{-N,\ldots,N\}\).\\ \(Q\leftarrow\sum_{u=1}^{m}c_uB_u\).\\ \While{\(Q\) is not positive definite}{ \(Q\leftarrow Q+Q_{\mathrm{ref}}\). } \If{some arithmetic automorphism of \(Q\) does not fix \(T\) pointwise}{ \(k\leftarrow k+1\), \(N\leftarrow N+k\), and continue with another sampled form. } \If{\(G\) is prescribed}{ \(Q\leftarrow Q+2^kG\). } Enumerate the Delaunay tessellation \(D\) of \(Q\), stopping if a Delaunay polytope imposes a nonzero equality on \(T\).\\ \If{the enumeration finishes without stopping}{ \({\mathcal A}_0\leftarrow\) wall inequalities of \(D\) by Algorithm~\ref{Algo_WallInequalities}.\\ \If{\(G\) is not prescribed, or \(a(G)\geq 0\) for all \(a\in{\mathcal A}_0\)}{ \(Q_0\leftarrow\) result of Algorithm~\ref{Algo_GeomInterior} applied to \({\mathcal A}_0\).\\ \KwRet{\((D,Q_0)\)} } } \(k\leftarrow k+1\), \(N\leftarrow N+k\). } \caption{Iterative construction of an initial iso-Delaunay domain} \label{Algo_InitialIsoDelaunay} \end{algorithm} \subsection{Adjacent domains and flips} The adjacency graph of iso-Delaunay domains is obtained by crossing irredundant walls of the current cone. For each orbit representative of an irredundant inequality, the algorithm first computes a point in the relative interior of the corresponding facet. If this point does not represent a positive-definite matrix, the wall belongs to the boundary of the positive definite cone and no adjacent iso-Delaunay domain is produced. Otherwise the wall is crossed by a \(T\)-flip. Testing a single point is enough by the following remark. \begin{remark}\label{rem:facet_pd} Let \(X\) be a convex subset of the cone of positive semidefinite matrices. All the points of the relative interior of \(X\) lie in the relative interior of the same face of that cone, and the faces of the positive semidefinite cone are determined by the kernel. Hence all the points of \(\relint X\) have the same rank. Applied to a facet of an iso-Delaunay cone, either every point of its relative interior is positive definite, or the facet lies in the boundary of the positive semidefinite cone. \end{remark} When a common form \(G\) is prescribed, a wall is crossed only if \(G\) lies on it, that is, if its inequality vanishes at \(G\). Crossing a wall not containing \(G\) would leave the star of \(G\). Because \(G\) is positive definite, the domains of the star form a complete fan around the ray of \(G\) modulo the line \(\RR G\), since the iso-Delaunay domains form a locally finite decomposition of the positive definite cone \cite{DutourSikiriSchurmannVallentin2008}, and any two of them are therefore connected by a sequence of crossings of walls containing \(G\). The flip uses the adjacency records stored with the wall inequality to identify all Delaunay polytopes that meet at the wall. These polytopes form repartitioning polytopes. The repartitioning construction lifts vertices by the height \(x^tQx\) for an interior form \(Q\) of the old domain. Its facets split into three classes: \begin{itemize}[leftmargin=2em] \item lower facets, which are the old Delaunay polytopes; \item higher facets, which become the new Delaunay polytopes after crossing the wall; \item barrel facets, which transmit adjacencies between neighbouring repartitioning polytopes. \end{itemize} After the higher facets have been identified modulo the local symmetry group, one reconstructs the whole finite orbit description of the new Delaunay tessellation and recomputes its facet adjacencies. All the flips across the walls of one domain start from the same tessellation \(D\), so the data depending only on \(D\), such as the stabilizers of its Delaunay polytopes, are computed once and shared by these flips. \begin{algorithm} \KwData{An iso-Delaunay domain \(C\), represented by its Delaunay tessellation \(D\), an interior form \(Q\), and the wall inequalities of \(C\); a set \({\mathcal K}\) of walls of \(C\) whose adjacent domain is already known; optionally a common form \(G\)} \KwResult{The list of positive-definite iso-Delaunay domains adjacent to \(C\), one for each orbit of walls of \(C\) under its stabilizer that meets no wall of \({\mathcal K}\)} \({\mathcal N}\leftarrow\emptyset\).\\ Compute the stabilizer of \(C\) in the arithmetic group preserving \(T\).\\ Compute orbit representatives of the irredundant walls of \(C\), taking the walls of \({\mathcal K}\) as the representatives of their orbits.\\ \For{each wall representative \(F\notin{\mathcal K}\), with inequality \(a_F\)}{ compute a point \(q_F\) in the relative interior of \(F\).\\ \If{\(Q(q_F)\) is not positive definite}{ continue to the next wall. } \If{\(G\) is prescribed and \(a_F(G)\neq 0\)}{ continue to the next wall. } collect all Delaunay adjacencies producing the wall \(F\).\\ construct the associated repartitioning polytopes.\\ replace lower facets by higher facets, keeping barrel facets for adjacency matching.\\ reconstruct the finite orbit description of the flipped Delaunay tessellation \(D'\).\\ compute an interior form \(Q'\) of the cone of \(D'\) by Algorithm~\ref{Algo_GeomInterior}.\\ \({\mathcal N}\leftarrow{\mathcal N}\cup\{(D',Q')\}\). } \KwRet{\({\mathcal N}\)} \caption{Adjacent iso-Delaunay domains} \label{Algo_AdjacentIsoDelaunay} \end{algorithm} \subsection{Equivalence and graph traversal}\label{sec:equivalence} Enumeration is a graph traversal in which each visited vertex is an iso-Delaunay domain and each edge is a positive-definite wall crossing. The data required by this traversal are: \begin{itemize}[leftmargin=2em] \item construction of one initial iso-Delaunay domain; \item computation of all adjacent domains by the wall-and-flip procedure above; \item computation of a fast invariant, for instance from an invariant short-vector family of the interior Gram matrix; \item an exact equivalence test between two domains, obtained by finding a \(T\)-space-preserving integral change of basis sending one interior Gram matrix and short-vector family to the other. Because the matrix lattice \(T_{\ZZ}\) is saturated, the induced transformation matrix in the chosen \(T\)-coordinates is integral. By Lemma~\ref{lem:canonical_equivalence}, comparing the interior Gram matrices produced by Algorithm~\ref{Algo_GeomInterior} decides the equivalence of the domains. \end{itemize} When a common form \(G\) is prescribed, the arithmetic group is replaced by the stabilizer of \(G\) in it, so that the equivalences preserve the star of \(G\). The output of the traversal is therefore one representative for each iso-Delaunay domain modulo the arithmetic group preserving the \(T\)-space. \subsection{Enumeration algorithm} The top-dimensional enumeration is obtained by putting the preceding subroutines together. Its structure is the usual adjacency enumeration: maintain a queue of domains still to be processed, compute all neighbours of one domain, and insert only those neighbours that are not equivalent to previously found domains. The adjacency relation is symmetric, and this saves flips. Suppose that crossing the wall \(F\) of \(C\), with inequality \(a_F\), gives a domain \(C'\), and that \(C'=g\,C''\) for a domain \(C''\) of the queue and an element \(g\) of the arithmetic group. Then \(C'\) has the wall \(F\), with inequality \(-a_F\), and crossing it leads back to \(C\). Hence the wall \(g^{-1}F\) of \(C''\) leads to a domain equivalent to \(C\), which need not be computed when \(C''\) is processed. Such walls are recorded with the domains of the queue and passed to Algorithm~\ref{Algo_AdjacentIsoDelaunay}. In this way each orbit of walls is crossed from one side only, which roughly halves the number of flips. \begin{algorithm} \KwData{A \(T\)-space with basis \(B_1,\ldots,B_m\), an arithmetic group preserving \(T\), and optionally a common Gram matrix \(Q_{\mathrm{common}}\)} \KwResult{A set \({\mathcal R}\) of inequivalent full-dimensional iso-Delaunay domains in \(T\), restricted to the star of \(Q_{\mathrm{common}}\) if it is given} \((D_0,Q_0)\leftarrow\) result of Algorithm~\ref{Algo_InitialIsoDelaunay}.\\ \({\mathcal T}\leftarrow\{(D_0,Q_0)\}\), \({\mathcal R}\leftarrow\emptyset\), \({\mathcal K}(D_0,Q_0)\leftarrow\emptyset\).\\ \While{\({\mathcal T}\neq\emptyset\)}{ choose \(C=(D,Q)\in{\mathcal T}\).\\ \({\mathcal T}\leftarrow{\mathcal T}\setminus\{C\}\).\\ \({\mathcal R}\leftarrow{\mathcal R}\cup\{C\}\).\\ \({\mathcal N}\leftarrow\) adjacent domains of \(C\) by Algorithm~\ref{Algo_AdjacentIsoDelaunay}, with the known walls \({\mathcal K}(C)\).\\ \For{\(C'\in{\mathcal N}\), obtained by crossing the wall \(F\) of \(C\)}{ \eIf{\(C'=g\,C''\) for some \(C''\in{\mathcal R}\cup{\mathcal T}\)}{ \If{\(C''\in{\mathcal T}\)}{ \({\mathcal K}(C'')\leftarrow{\mathcal K}(C'')\cup\{g^{-1}F\}\). } }{ \({\mathcal T}\leftarrow{\mathcal T}\cup\{C'\}\), \({\mathcal K}(C')\leftarrow\{F\}\). } } } \KwRet{\({\mathcal R}\)} \caption{Enumeration of full-dimensional iso-Delaunay domains} \label{Algo_IsoDelaunayEnumeration} \end{algorithm} \section{Test cases: Hermitian forms over imaginary quadratic rings} \label{sec:tests} The enumeration of Section~\ref{sec:enum} applies to any \(T\)-space, and the spaces of Hermitian forms over the ring of integers of an imaginary quadratic field give test cases in which the arithmetic group is not \(\GL_n(\ZZ)\). These spaces and their perfect forms are studied in \cite{DutourSikiricGanglGunnellsHankeSchurmannYasaki2016}, whose model we use. \paragraph{The \(T\)-space.} Let \(R=\ZZ[\alpha]\) be the ring of integers of an imaginary quadratic field, with \(\alpha^2-s\alpha+p=0\), \(s\in\{0,1\}\); the Gaussian integers \(\ZZ[i]\) have \((s,p)=(0,1)\) and the Eisenstein integers \((s,p)=(1,1)\). We identify \(R^n\) with \(\ZZ^{2n}\) by writing \(x=a+\alpha b\) with \(a,b\in\ZZ^n\). A Hermitian form \(H\) on \(R^n\) defines the real quadratic form \((a,b)\mapsto H(x,x)\) on \(\ZZ^{2n}\), and \(T\subset\Sym_{2n}(\RR)\) is the space of these forms, of dimension \(n^2\); its explicit description as a space of symmetric \(2n\times 2n\) matrices is given in \cite[Section~6.1]{DutourSikiricGanglGunnellsHankeSchurmannYasaki2016}. Let \(M_\alpha\in\GL_{2n}(\ZZ)\) be the matrix of the multiplication by \(\alpha\). Since \(H(\alpha x,\alpha x)=p\,H(x,x)\), every \(A\in T\) satisfies \(M_\alpha^tAM_\alpha=pA\). \paragraph{The groups.} The group \(\GL_n(R)\) is the group of the matrices of \(\GL_{2n}(\ZZ)\) that commute with \(M_\alpha\); it preserves \(T\). The Galois conjugation \(\sigma\colon a+\alpha b\mapsto a+\bar\alpha b\) is also a matrix of \(\GL_{2n}(\ZZ)\) preserving \(T\), which normalizes \(\GL_n(R)\), and we also consider the group \(K_n(R)=\GL_n(R)\cup\GL_n(R)\,\sigma\). The stabilizers and the equivalences of positive definite forms in \(\GL_n(R)\) are computed by the algorithm of Plesken and Souvignier \cite{PleskenSouvignier1997} applied to the pair of forms \(A\) and \(AM_\alpha\): an element of \(\GL_{2n}(\ZZ)\) preserving both commutes with \(M_\alpha\). The elements of the coset \(\GL_n(R)\,\sigma\) do not commute with \(M_\alpha\) and are reduced to \(\GL_n(R)\): the element \(g\sigma\) maps \(A_1\) to \(A_2\) if and only if \(g\) maps \(\sigma A_1\sigma^t\) to \(A_2\). The group \(K_n(R)\) can also be obtained without this reduction, as the group of all the elements of \(\GL_{2n}(\ZZ)\) preserving \(T\), and the two computations have to agree. Table~\ref{tab:tests} gives the numbers of inequivalent full-dimensional iso-Delaunay domains for \(n=2\) and the first ten discriminants, and for \(n=3\) over the Gaussian and the Eisenstein integers, with the running times of the enumeration. For \(n=3\) over \(\ZZ[i]\), the computation of \(K_3(\ZZ[i])\) as the group of all the elements preserving \(T\) gives the same \(103\) domains. \begin{table}[ht] \caption{Number of inequivalent full-dimensional iso-Delaunay domains of Hermitian forms over the ring of integers of \(\QQ(\sqrt{d})\), and the wall-clock time of their enumeration in seconds, on a single core of an Apple M4 Max.} \label{tab:tests} \begin{tabular}{rrrrrr} \(n\) & \(d\) & \(\GL_n(R)\) & time (s) & \(K_n(R)\) & time (s)\\ \hline \(2\) & \(-3\) & \(1\) & \(0.06\) & \(1\) & \(0.02\)\\ \(2\) & \(-4\) & \(1\) & \(0.03\) & \(1\) & \(0.03\)\\ \(2\) & \(-7\) & \(16\) & \(0.06\) & \(11\) & \(0.05\)\\ \(2\) & \(-8\) & \(5\) & \(0.04\) & \(5\) & \(0.04\)\\ \(2\) & \(-11\) & \(58\) & \(0.16\) & \(35\) & \(0.10\)\\ \(2\) & \(-15\) & \(127\) & \(0.32\) & \(74\) & \(0.20\)\\ \(2\) & \(-19\) & \(198\) & \(0.52\) & \(112\) & \(0.31\)\\ \(2\) & \(-20\) & \(61\) & \(0.18\) & \(43\) & \(0.14\)\\ \(2\) & \(-23\) & \(343\) & \(0.90\) & \(190\) & \(0.53\)\\ \(2\) & \(-24\) & \(86\) & \(0.26\) & \(61\) & \(0.22\)\\ \(3\) & \(-3\) & \(23413\) & \(1061\) & \(11832\) & \(401\)\\ \(3\) & \(-4\) & \(206\) & \(8.9\) & \(103\) & \(4.9\)\\ \end{tabular} \end{table} \section{Finding iso-Delaunay domains with all rays of full rank}\label{sec:search} The following search is more targeted than full enumeration. Its purpose is to find, in a fixed dimension \(n\), a top-dimensional iso-Delaunay domain whose every extreme ray gives a full-rank Gram matrix. The search is not dimension-specific. \subsection{The objective function} Let \(C\subset T\) be the closure of an iso-Delaunay domain with irredundant inequality description. A dual-description computation returns its extreme rays \begin{equation} r^{(1)},\ldots,r^{(s)}\in \RR^m . \end{equation} Each ray is interpreted as a symmetric matrix \begin{equation} R_i=\sum_{u=1}^{m} r^{(i)}_u B_u . \end{equation} The desired property is \begin{equation} \rank(R_i)=n \qquad \text{for every extreme ray } i . \end{equation} Since \(C\) is contained in the cone of positive semidefinite matrices, each \(R_i\) is positive semidefinite, and the property says that every \(R_i\) is positive definite. As \(C\) is the conical hull of its extreme rays, it is then equivalent to \(C\setminus\{0\}\) consisting of positive definite forms, and it implies, by Remark~\ref{rem:facet_pd}, that every wall of \(C\) is crossed by a flip into another iso-Delaunay domain. The search uses the integer objective \begin{equation} \Phi(C)=\sum_{i=1}^{s} (n-\rank(R_i)). \end{equation} Thus \(\Phi(C)=0\) exactly when all extreme rays have full rank. For each visited domain, the inequalities are recomputed, redundancy is removed by Clarkson's algorithm, the extreme rays are computed, and the rank defects are summed. This makes the objective independent of any redundant wall description used during adjacency generation. The dual descriptions are the dominant cost of the search; the implementation chooses among several dual description methods adaptively during the run. \begin{remark}\label{rem:small_n} For \(T=\Sym_n(\RR)\) with \(2\leq n\leq 5\), no domain has \(\Phi=0\). For \(n=5\), the complete classification of the \(L\)-types \cite{DutourSikiricGarberSchurmannWaldmann2016} shows that every secondary cone \(C\) decomposes as \(C=F(C)+\sum_{i=1}^{h}\RR_{+}v_iv_i^{t}\), where the fundamental face \(F(C)\) is the smallest face of \(C\) containing all its extreme rays of rank greater than \(1\), and \(\dim C=\dim F(C)+h\). The fundamental faces that occur have dimension at most \(5\), so each of the \(222\) full-dimensional domains, of dimension \(15\), has at least \(10\) extreme rays of rank \(1\). For \(n=4\) there are three full-dimensional domains \cite{Voronoi1908}, with \(10\), \(9\) and \(9\) extreme rays of rank \(1\), and for \(n=2,3\) the only full-dimensional domain, Voronoi's principal domain, has all its extreme rays of rank \(1\). \end{remark} \begin{algorithm} \KwData{An iso-Delaunay domain \(C\) with Delaunay tessellation \(D\)} \KwResult{The rank-defect score \(\Phi(C)\)} Compute the wall inequalities of \(D\) by Algorithm~\ref{Algo_WallInequalities}.\\ Remove redundant inequalities by Clarkson's algorithm.\\ Compute the extreme rays \(r^{(1)},\ldots,r^{(s)}\) of the resulting cone.\\ \(\Phi\leftarrow 0\).\\ \For{\(i=1,\ldots,s\)}{ \(R_i\leftarrow\sum_{u=1}^m r^{(i)}_u B_u\).\\ \(\Phi\leftarrow \Phi+(n-\rank(R_i))\). } \KwRet{\(\Phi\)} \caption{Rank-defect objective} \label{Algo_RankDefect} \end{algorithm} \subsection{Greedy descent with random escapes} The search starts from a generic iso-Delaunay domain obtained by Algorithm~\ref{Algo_InitialIsoDelaunay}. The strategy is the same one used in Frank Vallentin's PhD thesis \cite{VallentinPhD}: move greedily in the graph of adjacent \(L\)-types when the objective improves, and use random walks to leave local minima. In that thesis this strategy was used to find record lattice coverings in dimension \(6\). The neighbours of a domain are taken from Algorithm~\ref{Algo_AdjacentIsoDelaunay}, that is, one neighbour for each orbit of flippable walls under the stabilizer of the domain. This is enough for the greedy step, because \(\Phi\) is invariant under the arithmetic group and two walls in the same orbit lead to equivalent neighbours. For the random walk it means that each step chooses uniformly among the orbits of flippable walls, which is not the same distribution as choosing uniformly among the walls themselves. \begin{algorithm} \KwData{An \(n\)-dimensional \(T\)-space, a random-walk length \(N_{\rm walk}\), and an iteration bound \(N_{\rm iter}\)} \KwResult{A domain \(C\) with \(\Phi(C)=0\), if one is found within the search budget} \(C\leftarrow\) result of Algorithm~\ref{Algo_InitialIsoDelaunay}.\\ \(\phi\leftarrow\Phi(C)\), computed by Algorithm~\ref{Algo_RankDefect}.\\ \For{\(t=1,\ldots,N_{\rm iter}\)}{ \If{\(\phi=0\)}{ \KwRet{\(C\)} } \({\mathcal N}\leftarrow\) adjacent domains of \(C\) by Algorithm~\ref{Algo_AdjacentIsoDelaunay}.\\ compute \(\Phi(C')\) for all \(C'\in{\mathcal N}\).\\ \(\phi_{\min}\leftarrow \min\{\Phi(C'):C'\in{\mathcal N}\}\).\\ \eIf{\(\phi_{\min}<\phi\)}{ choose uniformly a domain \(C'\in{\mathcal N}\) with \(\Phi(C')=\phi_{\min}\).\\ \(C\leftarrow C'\), \(\phi\leftarrow\phi_{\min}\).\\ }{ \For{\(j=1,\ldots,N_{\rm walk}\)}{ choose uniformly an orbit of flippable walls of \(C\) and replace \(C\) by the domain across a wall of that orbit. } recompute \(\phi=\Phi(C)\). } } \KwRet{\bf fail} \caption{Search for an iso-Delaunay domain with full-rank rays} \label{Algo_FullRankSearch} \end{algorithm} The output condition is exactly \(\Phi(C)=0\). In this case every extreme ray of the iso-Delaunay domain has full rank. \subsection{Search parameters} The search is controlled by the following parameters: \begin{itemize}[leftmargin=2em] \item the length of the random escape walk after a local minimum; \item the cap on the number of outer iterations. \end{itemize} The iteration cap is part of the mathematical design of the search, not only a safety guard. In some dimensions there is no domain with \(\Phi=0\), as Remark~\ref{rem:small_n} shows, so an unconditional search for a zero would not terminate. The search exploits the adjacency graph of iso-Delaunay domains until such a domain is found or the chosen computational budget is exhausted. \section{Iso-Delaunay domains in dimension 6 with full-rank rays} \label{sec:dim6} We ran Algorithm~\ref{Algo_FullRankSearch} for \(T=\Sym_6(\RR)\), the classical case of Voronoi's second reduction, where the iso-Delaunay domains are the \(L\)-type domains. Here \(m=21\), and the basis \(B_1,\ldots,B_{21}\) consists of the matrices \(E_{ii}\) and \(E_{ij}+E_{ji}\) for \(i