¹

1 Introduction↩︎

Let \(R\) be a polynomial ring over a field \(K\), endowed with a monomial (or term) order and \(A\) be a \(K\)-subalgebra of \(R\). The \(K\)-vector space spanned by the initial (or leading) monomials of the elements of \(A\) is a \(K\)-subalgebra \(\operatorname{in}(A)\) of \(R\). A Sagbi basis is a subset of \(A\) whose initial monomials generate \(\operatorname{in}(A)\) as a \(K\)-algebra. There is a clear analogy to Gröbner bases of ideals \(I\subset R\): a subset \(G\) of \(I\) is a Gröbner basis if the initial monomials of the polynomials \(f\in G\) generate (as an ideal) the initial ideal of \(I\). The acronym Sagbi, introduced by Robbiano and Sweedler [1], stands for “subalgebra analog to Gröbner bases of ideals”. Section 2 gives a compact introduction to Sagbi bases and their computation.

In [2] Bruns and Conca have described the implementation of the Sagbi algorithm in the Singular [3] library sagbiNormaliz.lib which uses Singular as the environment for polynomial computations and Normaliz [4] for the combinatorics. The first major goal of this note is the extension of the library by functions that, in addition to a Sagbi basis, compute a defining ideal of the subalgebra \(A\) in terms of the given generators (see Section 3). This extension is possible since Sagbi bases are characterized by the liftability of the binomial ideal defining the initial algebra \(\operatorname{in}(A)\) to a defining ideal of \(A\). Section 4 compares computation times of the approach via Sagbi bases to the classical elimination by CoCoA-5 [5] and Singular. No doubt, in general elimination is faster, but there are interesting cases in which the Sagbi approach is competitive or better.

Given positive integers \(m,n\) with \(m\leq n\) let \(X_{m\times n}\) be a \(m\times n\) matrix of variables over a field \(K\) and \(R=K[X_{m\times n}]\) be the polynomial ring generated by its entries. The algebras, whose Sagbi bases are most interesting to the authors, are the subalgebras \(A_t(m,n)\) of \(R\) generated by the \(t\)-minors of \(X_{m\times n}\). The \(t\)-minors are the determinants of \(t\times t\) submatrices of \(X\). In the case \(t = m\), the algebra \(A_m(m,n)\) is also denoted by \(G(m,n)\) and is the homogeneous coordinate ring of the classical Grassmannian, i.e., the variety of \(m\)-dimensional \(K\)-subspaces of the vector space \(K^n\).

In Section 5 we recall notions and tools introduced by Sturmfels and Zelevinsky [6], [7] for the investigation of the collections of initial monomials of the \(m\)-minors in \(G(m,n)\) under varying monomials orders. While the maximal minors do not form a Sagbi basis of \(G(m,n)\) in general, the collections of initial monomials always generates a subalgebra of the same dimension as \(G(m,n)\). This is not only of theoretical interest, but has computational consequences that we will use in later sections. The main tool for this result is the theory of Cartwright-Sturmfels ideals developed by Conca, De Negri and Gorla [8]–[9].

It is known by a theorem of Sturmfels [7] that the \(m\)-minors form a Sagbi basis of \(G(m,n)\) with respect to a diagonal monomial order, i.e., a monomial order for which the initial monomials of the minors are the product of the elements in their main diagonal. By a theorem of Bruns and Conca (for example, see [10] or [11]) if the characteristic of \(K\) is not too small, \(A_t(m,n)\) always has a finite Sagbi basis for a diagonal order. But, apart from the trivial case \(t=1\) and the case of Grassmannians, the \(t\)-minors do not form a Sagbi basis for a diagonal order. This raises the question whether there exists a monomial order on \(K[X_{m\times n}]\) for which the \(t\)-minors are a Sagbi basis. The main result of Section 7 is Theorem 9: this holds if and only if \(t = m\), or \(t+1=m=n\) or \(t = 1\). In the key case \(t+1 = m = n\) the selection of initial monomials that makes the \((m-1)\)-minors a Sagbi basis is unique up to the permutations of rows and columns (Theorem 12). In turn this follows from the Birkhoff–von Neumann theorem, applied to the Newton polytope of the product of \((m-1)\)-minors of \(X_{m\times m}\). We can then show that for larger formats the \(t\)-minors cannot be a Sagbi basis.

We illustrate the technique of the Newton polytope by several concrete examples, and demonstrate the use of Hilbert series in (dis)proving that certain sets of minors or products of minors are a Sagbi basis. This allows to find a universal Sagbi basis for \(m=n=3\) and \(t=2\) (Theorem 15), for \(G(3,6)\) (Theorem 18) and \(G(3,7)\) (Theorem 19). Hilbert series computations for the algebras generated by initial monomials of the \(3\)-minors in \(G(3,8)\) and \(G(3,9)\) show that universal Sagbi bases for them must be very complicated.

As a potential extension in another direction, in Remarks 22–24 we discuss the problem of finding universal Sagbi bases for the Rees algebra of the ideal of \(3\)-minors of \(X_{3\times 6}\) and of the ideal of \(3\)-minors of \(X_{3\times 7}\). The first case seems to be treatable while the second appears to be very complicated.

We point out that Sagbi bases and initial algebras of \(G(m,n)\) and, in particular, of \(G(3,n)\) have been studied by several authors, see [12]–[17].

The results in Sections 7 and 8 generalize statements contained in the third author’s master thesis [18] written under the supervision of the second author.

We would like to thank Barbara Betti and the anonymous reviewers for their insightful comments on an earlier version of the paper, which helped us improve the quality of the exposition.

2 Basics of Sagbi bases↩︎

This section is a slightly modified version of [2]. It is included to keep this paper as self-contained as possible.

The reader finds a compact discussion of Sagbi bases in [10]. We use the notation developed there. Kreuzer and Robbiano [19] give a more extensive introduction; see also Ene and Herzog [20] and Sturmfels [7]. Sagbi bases were introduced independently by Robbiano and Sweedler [1] and Kapur and Madlener [21]. The acronym Sagbi stands for “subalgebra analog to Gröbner bases of ideals” [1]. Some authors have adopted recently a new terminology, Khovanskii bases, for a notion that generalize that Sagbi bases but in this paper we keep the traditional name.

Let \(A \subset R=K[X_1,\dots,X_n]\) be a \(K\)-subalgebra and \({\mathcal{F}}\) a (not necessarily finite) family of polynomials belonging to \(A\). We assume that \(R\) is endowed with a monomial (or term) order \(<\). In the following we often employ a simplified terminology using subalgebra for \(K\)-subalgebra and order for monomial order. One calls \({\mathcal{F}}\) a Sagbi basis of \(A\) if the initial monomials \(\operatorname{in}(f)\), \(f\in {\mathcal{F}}\), generate the initial algebra \(\operatorname{in}(A)\). A Sagbi basis is automatically a system of generators of \(A\). If \({\mathcal{F}}\) is finite, then \(A\) and \(K[\operatorname{in}({\mathcal{F}})]\) are connected by a flat deformation (Conca, Herzog and Valla [22]), and this allows the transfer of homological properties and numerical invariants from the toric algebra \(K[\operatorname{in}({\mathcal{F}})]\) to \(A\). Chapter 6 of [10] exploits this approach for the investigation of algebras generated by minors.

Sagbi bases need not be finite, but can always be chosen countable. Therefore one must allow that \({\mathcal{F}}= (f_u)_{u\in N}\) with \(N=\{1,\dots,p\}\) with \(p\in {\mathbb{N}}\) or \(N={\mathbb{N}}\). We will always assume that the members of \({\mathcal{F}}\) are monic. This is evidently no essential restriction of generality as long as the base ring \(K\) is a field. However, in the bookkeeping underlying the computation of the defining ideal the division of a polynomial by its initial coefficient must of course be registered.

For us the following simple lemma is an important tool in the computation of Sagbi bases. For an \({\mathbb{N}}\)-graded \(K\)-vector space \(V\) one defines the Hilbert function of \(V\) by \[H(V,k) = \dim_K V_k, \qquad k\in{\mathbb{N}},\label{Hilb}\tag{1}\] where \(V_k\) is the subspace of degree \(k\) elements of \(V\).

To present \(A\) as a residue class ring of a polynomial ring, we choose \(P=K[Y_u: u\in N]\) and define a surjection \[\phi: P \to A, \qquad \phi(Y_u) = f_u, \;u\in N.\label{phi}\tag{2}\] The \(K\)-algebra \(K[\operatorname{in}({\mathcal{F}})]\) is a homomorphic image of \(P\), as well, namely by the surjection \[\psi: P \to K[\operatorname{in}({\mathcal{F}})], \qquad \psi(Y_u) = \operatorname{in}(f_u), \;u\in N.\] The kernel of \(\psi\) is generated by a set of binomials. In the terminology of [1], a binomial in \(\operatorname{Ker}\psi\) is called a tête-a-tête.

A monomial in \(P\) is given by an exponent vector \(e=(e_u)_{u\in N}\) of natural numbers \(e_u\) of which all but finitely many are \(0\). We set \(Y^{e} = \prod_{u\in N} Y_u^{e_u}\) and \[{\mathcal{F}}^e=\psi(Y^{e})=\prod_{u\in N} f_u^{e_u}.\] Let \(F\in P\) be a polynomial, given as a finite \(K\)-linear combination of monomials, \(F=\sum_i a_iY^{e_i}\) where the \(e_i\) are exponent vectors, and \(a_i\neq 0\) for all indices involved. We set \[\begin{align} \operatorname{in}_\phi(F)&=\max_i \; \operatorname{in}(\phi(Y^{e_i})), \\ \operatorname{init}_\phi(F)&=\sum_{\operatorname{in}(\phi(Y^{e_i}))=\operatorname{in}_\phi(F) } a_iY^{e_i}. \end{align}\] Note that in the definition of \(\operatorname{in}_\phi(F)\) the maximum is taken over the initial monomials with respect to the monomial order on \(R\) so that it is a monomial in \(R\). In contrast, \(\operatorname{init}_\phi(F)\) is a polynomial in \(P\). Since \(\phi(\operatorname{init}_\phi(F))\) can be \(0\), in general \(\operatorname{in}_\phi(F) \neq \operatorname{in}(\phi(F))\), and this cancellation of initials is the crucial aspect of Sagbi computation. One says that a polynomial \(F\in\operatorname{Ker}\phi\) lifts a polynomial \(H\in \operatorname{Ker}\psi\) if \(\operatorname{init}_\phi(F)=\operatorname{init}_\phi(H)\).

We can now formulate the Sagbi criterion (see [10]).

The Buchberger algorithm for a Gröbner basis of an ideal \(I\) starts from a system of generators \(G\) of \(I\). Then one applies two steps, namely (i) the computation of the \(S\)-polynomials \(S(g_1,g_2)\), \(g_1, g_2\in G\), and (ii) their reductions modulo \(G\). The nonzero reductions are then added to \(G\), and the next round of \(S\)-polynomials of the augmented \(G\) and their reductions is run. This produces an increasing sequence of initial ideals \(\operatorname{in}(G)\). Because of Noetherianity the process stops after finitely many rounds with a Gröbner basis of \(I\). The reduction of an \(S\)-polynomial \(S(g_1,g_2)\) to \(0\) is equivalent to the liftability of the “divided Koszul syzygy” of \(\operatorname{in}(g_1)\) and \(\operatorname{in}(g_2)\) to a syzygy of the polynomials \(g\in G\).

The computation of Sagbi bases follows the same pattern. There are however two main differences: an analog of the divided Koszul syzygies does not exist, and ascending chains of monomial subalgebras of \(R\) need not stabilize. For Sagbi bases one must therefore compute a binomial system of generators of \(\operatorname{Ker}\Psi\), and one cannot expect the algorithm to stop. The analog of reduction is called subduction (we again follow [1]) .

The process that computes a subduction of \(g\) modulo \({\mathcal{F}}\) is also called subduction. Here \(\operatorname{supp}(r)\) is the set of monomials of \(R\) appearing in \(r\) with a nonzero coefficient. In the computation of Sagbi bases, including defining ideals, one can replace (3) by the weaker condition

1. \(\operatorname{in}(r)\) is not of type \(\operatorname{in}({\mathcal{F}}^e)\).

There is an obvious algorithm that produces a subduction remainder \(r\) in \((3')\): if \(\operatorname{in}(g)=\operatorname{in}({\mathcal{F}}^e)\), we replace \(g\) by \(g - a\phi({\mathcal{F}}^e)\) where \(a\) is the leading coefficient of \(g\), and iterate this subduction step as long as possible. The algorithm stops since the sequence of initial monomials is descending and descending sequences in a monomial order are finite. Once \((3')\) is reached, one applies subduction steps iteratively to the remaining monomials to achieve the “tail subduction” asked for by (3).

The crucial observation for the computation of the defining ideal and for the proof of correctness of the Sagbi algorithm below is the following proposition.

It is enough to observe \(\operatorname{in}({\mathcal{F}}^{e_i})\le\operatorname{in}(\phi(\beta)) < \operatorname{in}_\phi(\beta)\) for all \(i\).

The algorithm (Sagbi) starts from the finite family \({\mathcal{F}}_0\) generating the subalgebra \(A\subset R\). Then one proceeds as follows:

1. Set \(i=0\).

2. Set \({\mathcal{F}}'=\emptyset\) and compute a binomial system of generators \({\mathcal{B}}_i\) of the kernel of \(\psi_i: P_i \to K[\operatorname{in}({\mathcal{F}}_i)]\), \(P_i=K[Y_F:F\in {\mathcal{F}}_i]\), \(\psi_i(Y_F)=\operatorname{in}(F)\).

3. For all \(\beta\in {\mathcal{B}}_i\) compute the subduction \(r\) of \(\phi_i(\beta)\) modulo \({\mathcal{F}}_i\), \(\phi_i\) given by the substitution \(Y_F\mapsto F\), \(F\in{\mathcal{F}}_i\). If \(r\neq 0\), make \(r\) monic and add it to \({\mathcal{F}}'\).

4. If \({\mathcal{F}}'=\emptyset\), set \({\mathcal{F}}_j={\mathcal{F}}_i\), \(P_j=P_i\), \({\mathcal{B}}_j={\mathcal{B}}_i\) for all \(j\ge i\) and stop.

5. Otherwise set \({\mathcal{F}}_{i+1}={\mathcal{F}}_i\cup {\mathcal{F}}'\), \(i=i+1\) and go to (2).

It follows from Theorem 1 and Proposition 2 that \({\mathcal{F}}=\bigcup_{i=0}^\infty{\mathcal{F}}_i\) is a Sagbi basis of \(A\). It is not hard to see that the algorithm stops after finitely many steps if \(A\) has a finite Sagbi basis (with respect to the given monomial order).

To complete the notation we define the polynomial ring \(P_\infty = \bigcup_{i=0}^\infty P_i\). It is endowed with surjective ring homomorphisms \(\phi_\infty: P_\infty \to A\), \(\phi_\infty(Y_F) = \phi_i(Y_F) = F\) for \(F\in {\mathcal{F}}_i\), and the analogously constructed \(\psi_\infty: P_\infty \to \operatorname{in}(A)\), \(\psi_\infty(Y_F) = \psi_i(Y_F) = \operatorname{in}(F)\).

3 Computing the defining ideal↩︎

The algebra \(A\) is given by the family of generators \({\mathcal{F}}_0\). The polynomial ring \(P_0 = K[Y_F: F\in {\mathcal{F}}_0]\) is mapped surjectively onto \(A\) by the \(K\)-algebra map \(\pi: P_0\to A\), \(\pi(Y_F)= F\), \(F\in {\mathcal{F}}_0\). We write \(\pi\) instead of \(\phi_0\) for better readability. Computing the defining ideal means to compute a (finite) system of polynomials in \(P_0\) generating the kernel of \(\pi\).

Theorem 1 and Proposition 2 show that we know a defining ideal of \(A\): \(\operatorname{Ker}\phi_\infty\) is generated by the polynomials that represent the subduction to \(0\) of the tête-a-têtes. But this defining ideal lives in the “wrong” polynomial ring, namely in \(P_\infty\) instead of \(P_0\). The “bookkeeping” that we need for computing \(\operatorname{Ker}\pi\) from \(\operatorname{Ker}\phi_\infty\) is a retraction \(\rho: P_\infty \to P_0\) of the natural embedding \(P_0\hookrightarrow P_\infty\) such that \(\phi_\infty = \pi \circ \rho\). Evidently, \(\operatorname{Ker}\pi =\rho(\operatorname{Ker}\phi_\infty)\) then.

We construct \(\rho\) and \(\operatorname{Ker}\pi\) inductively. Suppose we have reached step (3) in the Sagbi algorithm, and let \(\phi_i(\beta) = a_1{\mathcal{F}}^{e_1}+\dots+a_m{\mathcal{F}}^{e_m} +r\) be a subduction of \(\phi_i(\beta)\). There are two cases:

1. If \(r\neq 0\), then we register \[\rho(r) = \rho(\beta - (a_1Y^{e_1}+\dots+a_mY^{e_m})).\] This makes sense since \(\rho\) has already been computed on \(P_i\). To make \(r\) monic, divide both sides by the initial coefficient of \(r\).

   For the indeterminate \(Y_r\) introduced in \(P_{i+1}\) we set \(\rho(Y_r) = \rho(r)\). After all nonzero subduction remainders have been done, the retraction \(\rho\) has been extended to \(P_{i+1}\).

2. If \(r = 0\), then \(\rho(\beta - (a_1Y^{e_1}+\dots+a_mY^{e_m}))\) is added as a generator to \(\operatorname{Ker}\pi\).

For the computation of the Sagbi basis without the defining ideal the Singular library sagbiNormaliz.lib has \(3\) variants of the Sagbi algorithm:

1. uses the Sagbi algorithm as given above and can be applied to all subalgebras of polynomial rings.

2. can be applied to graded subalgebras of standard graded polynomial rings. In computing the Sagbi basis it proceeds degree by degree.

3. can be applied in the same cases as (Deg), provided the Hilbert series is known. It proceeds by degrees, using that the next “critical” degree can be read from the Hilbert function. Moreover, it avoids subductions as soon as it is clear that, roughly speaking, as many “new” elements of the Sagbi basis have been found as predicted by the difference of Hilbert functions of \(A\) and the subalgebra of \(A\) generated by the subset of the Sagbi basis computed so far.

See [2] for more precise information on these variants.

Since (Hilb) avoids complete subductions, it cannot be used for the computation of the defining ideal. Therefore only augmented versions of (Gen) and (Deg) have been provided for it. For the augmented versions, the same rule of thumb applies as for the pure Sagbi computations: whenever possible, use (Deg).

We use the normalized degree on the subalgebra \(A\): it is obtained from the standard degree of the surrounding polynomial ring by division by the \(\gcd\) of the standard degrees of the generators.

For the combinatorial computations involving monomial algebras and binomial ideals the library falls back on Normaliz. These computations do not change when the defining ideal is asked for. This is the first reason why computing the defining ideal extends the computation only mildly in most cases. Another reason is that the computation of the retraction \(\rho\) uses indeterminates instead of the potentially complicated original generators of the subalgebra \(A\).

4 Computational data↩︎

The subalgebras to which we have applied our algorithm are generated by minors of a matrix of inderterminates or closely related to them. Using the shortcut \[[m]= \{1,\dots m\},\] we let \[K[X] =K[X_{m\times n}] = K\bigl[X_{ij}: i\in [m],\;j\in [n]\bigr]\] denote the polynomial ring in \(mn\) indeterminates, arranged in an \(m\times n\) matrix. We assume that \(m\le n\), unless stated otherwise. The standard monomial orders on such a polynomial ring are the diagonal ones: for such an order, the initial monomial of any \(k\)-minor is the product of the indeterminates in the main diagonal of the submatrix. In this section, unless stated otherwise, a diagonal monomial order is used. Our standard reference is Bruns, Conca, Raicu and Varbaro [10].

We have tested the computation of defining ideals for algebras of the following types.

\(G(m,n)\)

homogeneous coordinate ring of the Grassmannian of \(m\)-spaces in \(K^n\) with respect to the Plücker embedding. It is subalgebra of the polynomial ring \(K[X_{m\times n}]\), generated by the \(m\)-minors. It is well-known that the \(m\)-minors not only generate \(G(m,n)\), but even are a Sagbi basis [10]. The defining ideal is generated by the degree \(2\) Plücker relations [10]. These properties are independent of the characteristic of the base field. In the computations we use characteristic \(0\).

\(G(m,n)_\ell\)

the same as \(G(m,n)\), but with a non-diagonal lexicographic order.

\(A_t(m,n)_c\)

is the subalgebra of \(K[X]\), \(\operatorname{char}K =c\), generated by the \(t\)-minors. If \(c= 0\) or \(c > \min(k,m-t,n-t)\), it has a finite Sagbi basis of which the \(t\)-minors form a strict subset in general [10]. The defining ideal is unknown in general, but for characteristic \(0\) conjectured to be generated in degree \(2\) and \(3\), see Bruns, Conca and Varbaro [23] or [10]. For \(t= 2\) this conjecture has been proved by Huang, Perlman, Polini, Raicu, and Sammartano [24].

\(R_{r}(m,n)\)

Let \(Y\) be an \(m\times r\) matrix of indeterminates and \(Z\) an \(r\times n\)-matrix. The subalgebra of \(K[Y,Z]\) generated by the entries of the product matrix \(YZ\) is isomorphic to the residue class ring of \(K[X_{m\times n}]\) by the ideal \(I_{r+1}\) generated by the \((r+1)\)-minors. Computing its Sagbi basis amounts to computing a toric deformation of the determinantal variety of rank \(r\) matrices of format \(m\times n\). See [10]. From the description given it is clear that the defining ideal of this algebra is \(I_{r+1}\).

\(\operatorname{Sec}_k(m,n)\)

denotes the homogeneous coordinate ring of the \(k\)th secant variety of \(G(m,n)\). See [25].

Table 1 lists computation times, cardinalities, and degrees of Sagbi bases and defining relations of several examples. We compare the computation times of sagbiNormaliz.lib to classical elimination by Singular and CoCoA5.

Table 1 contains only graded algebras. Consequently we have used the degree-by-degree variant of the algorithm.

In the table the column “bound” is rather irrelevant. The degree-by-degree variant asks for it. In the cases where we could compute a complete Sagbi basis it was chosen large enough to allow the complete computation. In the case of \(\operatorname{Sec}_2(3,7)\) the degree bound was set to \(3\) because a previous computation with t a larger degree bound suggested that no new relations came up after that degree.

for which a previous computation with a larger bound suggested the relations in degree \(3\).

The column “Sagbi” lists the maximal degree of the elements of the Sagbi basis (as far as computed). The column “comp” shows the degree to which the computation runs until the completion of the Sagbi basis is recognized or the degree bound is reached. These numbers seem to be too large by \(1\) in cases like \(G(m,n)\) where it is known a priori that the Sagbi basis lives in degree \(1\). However, the implementation goes degree by degree until it reaches a point at which the tête-a-tête has no binomials anymore.

The next two columns list the number of elements of the Sagbi basis and relations, as far as computed.

All computations were done on a PC with a AMD Ryzen 9000 CPU.

5 Coherent matchings, Newton polytopes and computational tools↩︎

For the computational proofs in the next sections we recall and extend some terminology and facts from [7]. For a polynomial \(F\in K[X_1,\dots, X_n]\) we denote by \({\mathcal{N}}(F)\) the Newton polytope of \(F\), i.e., the convex polytope spanned by the exponent vectors of the monomials in the support of \(F\).

For a finite list \({\mathcal{F}}=\{F_1,\dots, F_s\}\) of nonzero polynomials we let \({\mathcal{N}}({\mathcal{F}})\) denote the Newton polytope \({\mathcal{N}}(F_1\cdots F_s)\) of the product of the elements in \({\mathcal{F}}\). For such a list \({\mathcal{F}}\) a matching \(T\) is a list of monomials \(\{X^{a_1}, \dots, X^{a_s} \}\) such that \(X^{a_i}\) is in the support of \(F_i\) for \(i=1,\dots, s\). A matching is coherent if it consists of the initial monomials with respect to some monomial order or, equivalently, of some general enough positive integral weight vector. (For example, see [10].)

A vertex of \({\mathcal{N}}({\mathcal{F}})\) can be given by specifying a sufficiently general weight vector \(w\in {\mathbb{Z}}^n\). The vertex \(v\) of \({\mathcal{N}}({\mathcal{F}})\) is the unique point of \({\mathcal{N}}({\mathcal{F}})\) that maximizes \(w\). Without further hypothesis, it may not be possible to choose \(w\) positive. But if the elements in \({\mathcal{F}}\) are homogeneous (under an arbitrary positive grading), then \(w\) can be chosen as a positive vector. Indeed the vector \(g\) formed by the degrees of the variables is constant on every homogeneous polynomial, and \(v\) also maximizes \(w + mg\) for \(m \gg 0\), which has positive entries. An important observation here is that \({\mathcal{N}}({\mathcal{F}})\) is the Minkowski sum of the polytopes \({\mathcal{N}}(F_i)\) with \(i\in [s]\) and hence each vertex \(v\) of \({\mathcal{N}}({\mathcal{F}})\) is the sum \(v_1+\dots v_s\), in a unique way, of vertices \(v_i\) of \({\mathcal{N}}(F_i)\). Summing up we have

The observations above allow us to make statements about the Sagbi property of \({\mathcal{F}}\) with respect to all monomial orders: their number is infinite, but the Newton polytope has only finitely many vertices, or equivalently, the number of coherent matchings is finite. Let us list the computational tools that we will employ in the following. In Section 7 these tools will only be used to provide illustrative examples, but in Section 8 the proofs will be based on them.

1. We have used CoCoA [5] for computations based on random weight vectors, especially in connection with the computation of Hilbert functions.

2. Normaliz [4] has been used to confirm and extend the results of (1) on vertices of Newton polytopes.

3. We have extended a C++ program based on libnormaliz and CoCoALib that we already used in [2] for the computation of all coherent matchings of the set of \(3\)-minors in \(G(3,n)\) and deciding their Sagbi property. In the following we call this tool SagbiGrass.

6 Dimension of coherent matchings for \(G(m,n)\)↩︎

Denote by \({\mathcal{M}}_m\) the set of \(m\)-minors of \(X_{m\times n}\). Let \(T\) be coherent matching of \({\mathcal{M}}_m\subset K[X_{m\times n}]\) and let \(K[T]\) be the \(K\)-algebra it generates. Then by Lemma 1 we have \(H(K[T],i)\leq H(G(m,n),i)\) for all \(i\in{\mathbb{N}}\) and \(T\) is Sagbi if and only if equality holds for all \(i\in {\mathbb{N}}\). Hence the difference \(H(G(m,n),i)-H(K[T],i)\) can be taken as a measure of the failure of \(T\) being Sagbi. The goal of this section is to prove that the degree of growth of the \(H(G(m,n),i)\) and \(H(K[T],i)\) is always the same, that is:

In the proof we will use Cartwright-Sturmfels ideals and their properties. This theory has been developed in the series of papers [8], [9], [27]–[30] and has roots and applications in [31]–[34].

7 Are the minors a Sagbi basis?↩︎

Denote by \({\mathcal{M}}_t\) the set of \(t\)-minors of \(X_{m\times n}\). As we have already recalled, \({\mathcal{M}}_m\) is a Sagbi basis of \(G(m,n)\) with respect to the diagonal order. Furthermore, for \(1<t<m\) the set \({\mathcal{M}}_t\) is not a Sagbi basis of \(A_t(m,n)\) with respect to the diagonal order. The most immediate argument for this claim is that \(\dim A_t = mn\) if \(1 <t <m\) [10], but not all variables in the matrix \(X\) occur in diagonals. In the following the characteristic of the field is irrelevant.

Case (3) is trivial, and we have just recalled (1). As a next step we prove the existence of a suitable order in case (2).

The group \(G_{m\times n}\) acts on the polynomial ring \(K[X_{m\times n}]\) with \(S_m\) and \(S_n\) permuting the rows and columns of \(X\) and, when \(m=n\), the cyclic group of order \(2\) transposing the matrix.

A crucial point in the proof that \({\mathcal{M}}_t\) is never a Sagbi basis in all cases different from (1), (2) and (3) in Theorem 9 is that the selection of initial monomials in the proof of Proposition 10 is unique up to the action of \(G_{m\times m}\).

The group \(G_{m\times n}\) acts on the set \({\mathcal{M}}_t\) (up to sign) and hence also on the Newton polytope of \({\mathcal{M}}_t\).

As done in [6], when dealing with polynomials in \(K[X_{m\times n}]\) it is natural to represent the exponent vector of a monomial as a \(m\times n\) exponent matrix with entries in \({\mathbb{N}}\). Similarly a weight vector on \(K[X_{m\times n}]\) can be given as a \(m\times n\) matrix with entries in \({\mathbb{N}}\).

Inspection of the proof of Proposition 10 shows that the coherent matching constructed there has the exponent matrix \[Q_m= d_mI_m +E_m\] where

• \(I_m\) is the identity matrix of size \(m\times m\),

• \(d_m=(m-1)^2-1\) and

• \(E_m\) is a matrix of size \(m\times m\) with all entries \(1\).

As an example for \(m=3\) one has: \[Q_3 = 3\begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix} + \begin{pmatrix} 1 &1 &1 \\ 1 &1 &1 \\ 1 &1 &1 \end{pmatrix} =\begin{pmatrix} 4 &1 &1 \\ 1 &4 &1 \\ 1 &1 &4 \end{pmatrix} .\]

A matrix in \({\mathbb{N}}^{m\times n}\) is said to have full support if it has only positive entries.

As an immediate consequence of Proposition 10 and Theorem 12 we have:

A simple tool is the following evident lemma that will allow us to pass to submatrices.

We are ready to prove Theorem 9.

8 Universal Sagbi bases for \(A_2(3,3)\), \(G(3,6)\) and \(G(3,7)\)↩︎

Whereas the explicit computations in the previous section only served heuristic or illustrative purposes, they are crucial for the results in this section. All proofs are by computation.

A universal Sagbi basis for an algebra \(A\) is a set of elements that are a Sagbi basis for all orders. In this section we discuss universal Sagbi bases for two algebras \(A_2(3,3)\), \(G(3,6)\) and \(G(3,7)\). We start with the first:

Now consider the algebra \(G(3,6)\). The products of minors in the algebra are not a universal Sagbi basis: the only products of minors in \(G(3,6)\) are the products of maximal minors and the maximal minors do not form a universal Sagbi basis. The way out is to take the polynomial \[F=[1,2,3][4,5,6]-[1,2,4][3,5,6]\] and its orbit \[O_F=\bigl\{ [a,b,c][d,e,f]-[a,b,d][c,e,f] : \{a,b,c,d,e,f\}=[6] \bigr\} \mod \pm 1\] under \(S_6\) permuting the columns. The polynomial \(F\) has \(48\) terms and, up to sign, \(F\) is fixed by \(48\) permutations of columns. Hence, up to sign, \(O_F\) consists of \(15\) different polynomials. Our goal is to prove:

A surprising corollary of the proof of Theorem 18 is

Theorem 18 and its proof provide the basic data for the universal Sagbi basis of \(G(3,7)\). Again it is a proof by computation, but it is impossible to list all data in the same detail as in the proof of Theorem 18. Let us first extend the family \(O_F\). Again we start from \[F=[1,2,3][4,5,6]-[1,2,4][3,5,6],\] this time as an element of \(G(3,7)\), and let \(O_F^{(7)}\) be the orbit, up to sign, of \(F\) under the action of \(S_7\) by permutation of the columns. Therefore \(O_F^{(7)}\) consists of \(7\cdot 15=105\) polynomials of degree \(2\) in \(G(3,7)\).

Theorem 19 follows immediately from Proposition 20 that provides precise information on the nature of elements that must be added to \({\mathcal{M}}_3\). Let \(G(3,6)^{(i)}\) be the algebra generated by the \(3\)-minors of the matrix \(X_{3\times 7}^{(i)}\) obtained from \(X_{3\times 7}\) by removing column \(i\) with \(i=1,\dots,7\).

Let \(<\) be a monomial order on \(K[X_{m\times n}]\) with associated coherent match \(T\) of \({\mathcal{M}}_m\). Let \(Z\) be the set of the variables that so not appear in \(T\) (the forgotten variables). We know by [6] that \(Z\) contains exactly \(m(m-1)\) variables, \((m-1)\) per row. The precise combinatorial characterization of the possible \(Z\) is given in [6]. Let \(X_{m\times n}^0\) be the matrix obtained form \(X_{m\times n}\) by replacing with \(0\) the elements of \(Z\). Let \(\phi_Z: K[X_{m\times n}]\to K[X_{m\times n}^0]\) the \(K\)-algebra map defined by \(X_{ij}\to 0\) if \(X_{ij}\in Z\) and \(X_{ij}\to X_{ij}\) otherwise. Set \(G(m,n)^0=\phi_Z( G(m,n))\). As we have already seen implicitly in the proof of Theorem 18, an important consequence of Theorem 8 is the following:

Let \({\mathcal{F}}\subset R= K[X_1,\dots,X_n]\) be a set of polynomials of constant degree \(m\) and \(<\) a monomial order. As a vector space, the algebra \(K[{\mathcal{F}}]\) generated by \({\mathcal{F}}\) is the direct sum of the lowest degree components of the powers \(I^k\) of the ideal \(I\) generated by \({\mathcal{F}}\). The Rees algebra \[\operatorname{{\mathcal{R}}}(I) = \bigoplus_{k=0}^\infty I^kY^k\subset R[Y]\] has a standard \({\mathbb{Z}}\)-grading obtained by extending the standard grading on \(R\) by \(\deg Y = -m+1\) and also a finer standard \({\mathbb{Z}}^2\)-grading associated to \(\deg X_i=(1,0)\) and \(\deg Y=(-m,1)\). The properties of \(\operatorname{{\mathcal{R}}}(I)\) reflect properties of the powers of \(I\). For example, \(I\) has linear powers (i.e., all powers of \(I\) have a linear resolution) if and only if the \((1,0)\)-regularity of \(\operatorname{{\mathcal{R}}}(I)\) is \(0\), see [37] or [10]. Therefore it is interesting to investigate the initial algebras of \(\operatorname{{\mathcal{R}}}(I)\) under an extension of \(<\) to \(R[Y]\). Since the elements of \({\mathcal{F}}\) have constant degree \(m\), \(K[{\mathcal{F}}]\cong K[{\mathcal{F}}Y]\) is an algebra retract of \(\operatorname{{\mathcal{R}}}(I)\) by degree selection. As a \(K\)-algebra \(\operatorname{{\mathcal{R}}}(I)\) is generated by the indeterminates \(X_j\) and \({\mathcal{F}}Y\), and the critical question is whether they form a Sagbi basis of \(\operatorname{{\mathcal{R}}}(I)\). It is easy to see that necessary conditions for this are that \({\mathcal{F}}\) is a Gröbner basis of \(I\) and a Sagbi basis of \(K[{\mathcal{F}}]\). Furthermore the variables \(X_j\) and \({\mathcal{F}}Y\) form a Sagbi basis of \(\operatorname{{\mathcal{R}}}(I)\) if and only if \({\mathcal{F}}\) is a Gröbner basis of \(I\) and \[\operatorname{in}(\operatorname{{\mathcal{R}}}(I)) = \operatorname{{\mathcal{R}}}(\operatorname{in}(I)).\]

For \(m\leq n\), \({\mathcal{F}}= {\mathcal{M}}_m \subset K[X_{m\times n}]\) and the ideal \(I=({\mathcal{M}}_m)=I_m(X_{m\times n})\) of maximal minors we may study the various Sagbi bases of \(\operatorname{{\mathcal{R}}}(m,n)=\operatorname{{\mathcal{R}}}(I)\) as we have done for its subalgebra \(G(m,n)\). As \({\mathcal{M}}_m\) is a universal Gröbner basis, in this case we have that the union of the variables \(X_{ij}\) and \({\mathcal{M}}_mY\) is a Sagbi basis of \(\operatorname{{\mathcal{R}}}(m,n)\) with respect to \(<\) if and only if \(\operatorname{in}(\operatorname{{\mathcal{R}}}(I)) = \operatorname{{\mathcal{R}}}(\operatorname{in}(I))\). And this is actually the case for a diagonal order, see [10].

In the investigation of the Sagbi bases of \(\operatorname{{\mathcal{R}}}(m,n)\) the relevant Newton polytope is simply a translate of \({\mathcal{N}}({\mathcal{M}}_m)\) since the other algebras generators are the variables. Hence the subdivision of the coherent matchings in the \(4\) types given in [6] and used in the proofs of Theorems 18 and 19 applies to the study of \(\operatorname{{\mathcal{R}}}(3,n)\) as well. For a coherent matching \(T\) of \({\mathcal{M}}_m\) we will say that \(T\) is Sagbi for \(\operatorname{{\mathcal{R}}}(m,n)\) if the variables \(X_{ij}\) and \({\mathcal{M}}_mY\) form a Sagbi basis for \(\operatorname{{\mathcal{R}}}(m,n)\) for any monomial order associated to \(T\), i.e. \(\operatorname{in}(\operatorname{{\mathcal{R}}}(m,n))=\operatorname{{\mathcal{R}}}(T)\). Having said this, we do not try to explore fully this aspect of the story, but only collect some data and problems in the following remarks.

References↩︎