Compute minimal number of generators of subring

Hi all,

Given a polynomial ring $R = k[x_1,...,x_n]$ over a field $k$ (say $\mathbb{Q}$) and a list of polynomials $p_1,..,p_n$ in $R$ (homogeneous say), is Sage capable of computing the minimal number of generators of the subring generated by $p_1,...,p_n$ over $k$?

Next, suppose $I$ is a homogeneous ideal of $R$. Can the same approach be used to compute the minimal number of generators of this subring after being projected to $R / I$ ?

Edit: Sorry for the bad formatting (see source), please help me fix it if you can!

Edit2: For example, let $R = \mathbb{Q} [x,y]$ and let $p_1 = x^2, p_2 = x^2 y, p_3 = x^4 y$. This generates a principal ideal, but as a subring it has 2 generators and it is those 2 generators that I want.

Edit3: In case it is helpful, the case I'm looking at is a ring with an action of a group, and its subring of invariants for which I have generators.

Edit4: Here's a suggested algorithm: sort the generators by degree. Then sequentially add them, and check if they were already in the subring. Does Sage even have suitable subring capabilities?

edit retag close merge delete

Welcome to Ask Sage! Thank you for your question!

( 2021-08-23 13:29:31 +0200 )edit

Hint: a concrete example would help exploring this question.

( 2021-08-23 13:30:52 +0200 )edit
1

For the suggested algorithm you might use the SAGBI functionality in Singular:

> LIB "sagbi.lib";
> ring r=0, (x,y), dp;
> ideal A = x2, x2y;
> sagbiReduce(x4y, A);
0
> sagbiReduce(x5y, A);
x5y
> sagbiReduce(x6y, A);
0


If this is sufficient, then I can add an answer showing how to do it from Sage.

( 2021-08-24 11:29:04 +0200 )edit

Huh I guess so! I don't know Singular syntax - does it work over a base field like QQ? E.g. does sagbiReduce(x4y+(5/2)x6y, A) return 0? And please also let me know how to deal with projecting it to $R/I$ !

( 2021-08-24 16:57:46 +0200 )edit
1

Singular works over a field of characteristic zero here, and yes sagbiReduce(x4y+(5/2)*x6y, A) returns 0. In SageMath you can do:

from sage.libs.singular.function import singular_function, lib as singular_lib
singular_lib('sagbi.lib')
sagbiReduce = singular_function('sagbiReduce')
R.<x,y> = PolynomialRing(QQ)
A = R.ideal(x^2, x^2*y)
sagbiReduce(x^4*y+(5/2)*x^6*y, A)._sage_()


Unfortunately I don't know how you would deal with $R/I$.

( 2021-08-24 17:34:12 +0200 )edit

Sort by » oldest newest most voted

I understand a minimal generating set to be a set of generators such that no proper subset is a set of generators.

(Is the cardinality of a minimal generating set always the same? For subrings I don't know.)

We suppose a generating set $p_1,\ldots,p_m$ for a subring of $k[x_1,\ldots,x_n]$ is given, and we want to find a subset which is minimal. For this it suffices to solve the subring containment problem: if we can test whether a given element belongs to some subring, then we can use this to identify redundant generators (and this can be optimized by looking at degrees, as suggested in Edit4 of the question).

In Singular the subring containment problem is solved by inSubring, which can be called from SageMath as follows:

def in_subring(p, A):
R = p.parent()
from sage.libs.singular.function import singular_function, lib as singular_lib
singular_lib('algebra.lib')
inSubring = singular_function('inSubring')
return inSubring(p, R.ideal(A))[0] == 1


For example:

sage: R.<x,y> = PolynomialRing(QQ)
sage: in_subring(x^4*y - (5/2)*x^6*y, [x^2, x^2*y])
True


The documentation of inSubring states that it does the same as algebra_containment (using a different algorithm), and the Theory section of the documentation of that procedure describes how it works. Namely, the trick is to introduce new variables $z_j$ (one for each generator of the subalgebra) and an elimination ordering such that the $x_i$ are all greater than all $z_j$'s; then a polynomial $f$ belongs to the subalgebra $k[p_1,\ldots,p_m]$ if and only if its normal form $NF(f, J)$ with respect to the ideal $J = \langle z_j - p_j \rangle$ (calculated by the multivariate division algorithm, using a Groebner basis with respect to the chosen monomial ordering) contains only $z_j$'s.

Repeating the above example using the new method:

sage: R.<x,y,z1,z2> = PolynomialRing(QQ, order='degrevlex(2),degrevlex(2)')
sage: f = x^4*y - (5/2)*x^6*y
sage: J = R.ideal([z1 - x^2, z2 - x^2*y])
sage: f.reduce(J)
-5/2*z1^2*z2 + z1*z2


If I'm not mistaken then this latter method can be adapted to test containment in a subalgebra of $R/I$ as follows:

sage: I = R.ideal([x^6])
sage: (f + x^7).reduce(J + I)
z1*z2

more

The minimal generating set $\{x^2,x^2+x\}$ for $k[x]$ shows that the "local minimum" number of generators is not necessarily the global minimum in general, but the answer by Harm Derksen to Minimal number of generators of a k-algebra over commutative rings states (without a reference) that there is no such issue in the graded/homogeneous case. Moreover he gives the formula $\dim_k(\mathfrak{m}/\mathfrak{m}^2)$ for the minimal number of generators, where $\mathfrak{m}$ is the ideal consisting of positive degree homogeneous elements in the subalgebra. That seems to check out in the above example as well.

( 2021-08-25 18:44:21 +0200 )edit