Computing generating sets of lattice ideals and Markov bases of lattices (Q840713)

Let \({L}\subseteq\mathbb{Z}^n\) be a lattice. In this paper, the authors exhibit a new algorithm, called the Project-and-Lift algorithm, which computes a Markov basis of \({L}\). A Markov basis of \(L\) is by definition a finite subset \(M\) of \(L\) such that for any \(\alpha\), \(\beta\in\mathbb{N}^n\) with \(\alpha-\beta\in L\), there exists a sequence \(z_1, \ldots, z_k\in\mathbb{N}^n\) such that \(z_1=\alpha\), \(z_k=\beta\) and either \(z_i-z_{i+1}\in M\) or \(z_{i+1}-z_i\in M\) for \(i=1, \ldots, k-1\). It is known that \(M\subseteq L\) is a Markov basis of \(L\) if and only if \(J(M)=\{x^{u^+}-x^{u^-}\mid u\in M\}\) is a Gröbner basis of the lattice ideal \(I(L)=\langle x^{u^+}-x^{u^-}\mid u\in L\rangle\) in \(K[x_1, \ldots, x_n]\), where \(K\) is a field, \(x=x_1, \ldots, x_n\) are indeterminates, \(u^\pm=(u_1^\pm,\ldots, u_n^\pm)\) and \(u_i^\pm=\max\{\pm u_i,0\}\) for \(i=1, \ldots, n\). The main points of the Project-and-Lift algorithm are: (1) find a coordinate subspace \(\mathbb{R}^m\) of \(\mathbb{R}^n\) (\(m\) need not be the first \(m\) coordinates) such that one can find a Markov basis of \(p_{n,m}(L)\) easily, e.g., by using the Hermite Normal Form, where \(p_{n,m}\) is the canonical projection and (2) construct a Markov basis of \(p_{n,l+1}(L)\) from that of \(p_{n,l}(L)\). The authors show, be experiments, that Project-and-Lift algorithm is significantly faster that existing algorithms.