Computing Gröbner bases of pure binomial ideals via submodules of \(\mathbb Z^n\) (Q432760): Difference between revisions

This paper is about the computation of Gröbner bases of lattice ideals, that is binomial ideals of the form \(\langle x^u - x^v : u-v \in L\rangle\), where \(L\subset \mathbb{Z}^n\) is an integer lattice. It is obvious that the notion of a Gröbner basis can be defined combinatorially, and that computations can be done in \(\mathbb{Z}^n\) [\textit{R. Hemmecke} and \textit{P. N. Malkin}, J. Symb. Comput. 44, No. 10, 1463--1476 (2009; Zbl 1200.13048)]. Instead of working with the lattice \(L\subset \mathbb{Z}^n\), the present paper suggest to use a presentation \(F: \mathbb{Z}^m \to L \to 0\) and work in the presentation. Their method builds on a sign-consistent decomposition of \(L\) and Hilbert basis computations for the respective cones. There are theoretical reasons for the author's observation that this yields no interesting results or computational speed-ups: Gröbner bases of toric ideals (the argument also works for lattice ideals) have an exponential degree bound [\textit{B. Sturmfels}, Tôhoku Math. J., II. Ser. 43, No. 2, 249--261 (1991; Zbl 0714.14034)], while merely determining the size of a Hilbert basis is \#P-complete and NP-hard [\textit{M. Hermann, L. Juban} and \textit{P. G. Kolaitis}, Lect. Notes Comput. Sci. 1705, 13--32 (1999; Zbl 1044.11631)]. The paper also uses notions subtly different from those established in the literature. In particular, in computational algebraic geometry an ideal \(I\subset k[x_1,\dots,x_n]\) is \textit{saturated} if \(I:\langle x_1,\dots,x_n\rangle = I\). The authors use the term for \(\left( I:\prod_{i=1}^n x_i\right ) = I\). A binomial ideal such that \(\left( I:\prod_{i=1}^n x_i\right ) = I\) is usually called a \textit{lattice ideal} and although the title suggests much more, the methods in the paper are restricted to this case. Anybody interested in the computation of Gröbner bases of lattice ideals should read Hemmecke/Malkin, [loc. cit.] instead.