Computing toric ideals (Q1283192)

Let \(R=k[X_1,\ldots,X_n]\) denote the polynomial ring in \(n\) indeterminates over a field \(k\). Ideals of \(R\) generated by binomials have long been noticed to have special features among all polynomial ideals in \(R\). A thorough modern account on these features has been given by \textit{D. Eisenbud} and \textit{B. Sturmfels} [Duke Math. J. 84, No. 1, 1-45 (1996; Zbl 0873.13021)]. A good case for the importance of binomial ideals is a so called toric ideal, by which one means an ideal generated by the polynomial relations of a set of power products. The reason for this intrusive terminology is that these ideals are the defining ideals of (affine, not necessarily normal) toric varieties. Toric ideals are a lot friendlier from the computational side than polynomials ideals for the obvious reason that they carry no coefficients besides \(\pm 1\) and (perhaps, hence) the \(S\)-polynomial out of any two constituents is again of the same form. This prevents the coefficient explosion so feared by computer algebraists (and, naturally, by users thereof). Still a whole lot more goes for it that may pass unnoticed at first, and this is the arithmetic-combinatoric content of toric ideals. The magical counterpoint has been dubbed lattice ideals. This fruitful interplay has been explained by \textit{B. Sturmfels} [``Gröbner bases and convex polytopes'' (Providence 1996; Zbl 0856.13020)]. To recover a set of generators of a toric ideal \({\mathcal I}\subset R\) out of its closely associated lattice ideal \(L\subset {\mathbb Z}^n\), one needs to further saturate by \(X_1\cdots X_n\) the ideal \(I_L\subset R\) generated by the binomials coming from the vectors of \(L\) (since one such vector induces a uniquely defined binomial only up to a multiplicative power of \(X_1\cdots X_n\)). The paper under review deals with various improvements of the existing Buchberger-like algorithms for computing (a set of generators of) a toric ideal, whereby the main endeavour is to do saturation by \(X_1\cdots X_n\) in a less time consuming step. The authors propose two algorithms, one of which depends on running symbolic parallel computation. The algebra developed for this purpose is quite easy and a major role is played by an observation attributed to \textit{S. Hosten} and \textit{J. Shapiro} to the effect that to saturate by \(X_1\cdots X_n\) one can roughly do it by the product of at most half of these variables (the main point is that one will ordinarily be saturating ideals generated by pure monomials, in which case the argument is clear at the outset). The authors have implemented the algorithms and give several examples of computation to show a fast performance, which by and large is dramatically superior to the known previously implemented algorithms. The paper is written in a leisure, enjoyable style which makes it quite easy to follow.