Compute minimal number of generators of subring

edit

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