ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 25 Aug 2021 18:44:21 +0200Compute minimal number of generators of subringhttps://ask.sagemath.org/question/58630/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?Mon, 23 Aug 2021 13:19:02 +0200https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/Comment by manuela for <p>Hi all,</p>
<p>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$?</p>
<p>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$ ?</p>
<p>Edit: Sorry for the bad formatting (see source), please help me fix it if you can!</p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58669#post-id-58669That sounds excellent! If you post that (preferably with 1 simple example) I will accept it :-)
(Btw, the ideal $I$ will be homogeneous, just consisting of deg 1 functions)Tue, 24 Aug 2021 21:47:43 +0200https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58669#post-id-58669Comment by rburing for <p>Hi all,</p>
<p>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$?</p>
<p>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$ ?</p>
<p>Edit: Sorry for the bad formatting (see source), please help me fix it if you can!</p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58666#post-id-58666The reason for `A` to be defined as an ideal is purely technical, as Singular does not have a subalgebra type. According to the documentation and example, the object `A` (confusingly, of type `ideal`) is where the generators of the subalgebra are taken from. I've just found that there are simpler methods than `sagbiReduce`, namely [inSubring](https://www.singular.uni-kl.de/Manual/4-2-0/sing_1240.htm#SEC1321) and [algebra_containment](https://www.singular.uni-kl.de/Manual/4-2-1/sing_1247.htm#SEC1328). The Theory section in the documentation of the latter explains how the algebra containment problem is reduced to an ordinary normal form computation. That can seemingly easily be adapted to the $R/I$ case: just reduce with respect to $\langle y_i - p_i \rangle + I$.Tue, 24 Aug 2021 19:52:49 +0200https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58666#post-id-58666Comment by manuela for <p>Hi all,</p>
<p>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$?</p>
<p>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$ ?</p>
<p>Edit: Sorry for the bad formatting (see source), please help me fix it if you can!</p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58665#post-id-58665Thanks!! Can you please explain how it works, since it looks like A is constructed as an ideal?
Here's a suggested algorithm for $R/I$: construct the _ideal_ $I$, based on some generators $q_i$, and then consider it as a subring. Now add the generators $p_i$ one by one based on degree as before. Is this possible?Tue, 24 Aug 2021 19:04:43 +0200https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58665#post-id-58665Comment by rburing for <p>Hi all,</p>
<p>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$?</p>
<p>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$ ?</p>
<p>Edit: Sorry for the bad formatting (see source), please help me fix it if you can!</p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58660#post-id-58660Singular 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$.Tue, 24 Aug 2021 17:34:12 +0200https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58660#post-id-58660Comment by manuela for <p>Hi all,</p>
<p>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$?</p>
<p>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$ ?</p>
<p>Edit: Sorry for the bad formatting (see source), please help me fix it if you can!</p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58658#post-id-58658Huh 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$ !Tue, 24 Aug 2021 16:57:46 +0200https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58658#post-id-58658Comment by rburing for <p>Hi all,</p>
<p>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$?</p>
<p>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$ ?</p>
<p>Edit: Sorry for the bad formatting (see source), please help me fix it if you can!</p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58654#post-id-58654For the suggested algorithm you might use the [SAGBI functionality in Singular](https://www.singular.uni-kl.de/Manual/4-2-1/sing_1553.htm#SEC1634):
> 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.Tue, 24 Aug 2021 11:29:04 +0200https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58654#post-id-58654Comment by slelievre for <p>Hi all,</p>
<p>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$?</p>
<p>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$ ?</p>
<p>Edit: Sorry for the bad formatting (see source), please help me fix it if you can!</p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58632#post-id-58632Hint: a concrete example would help exploring this question.Mon, 23 Aug 2021 13:30:52 +0200https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58632#post-id-58632Comment by slelievre for <p>Hi all,</p>
<p>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$?</p>
<p>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$ ?</p>
<p>Edit: Sorry for the bad formatting (see source), please help me fix it if you can!</p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58631#post-id-58631Welcome to Ask Sage! Thank you for your question!Mon, 23 Aug 2021 13:29:31 +0200https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58631#post-id-58631Answer by rburing for <p>Hi all,</p>
<p>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$?</p>
<p>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$ ?</p>
<p>Edit: Sorry for the bad formatting (see source), please help me fix it if you can!</p>
<p>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.</p>
<p>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.</p>
<p>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?</p>
https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?answer=58679#post-id-58679I 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](https://www.singular.uni-kl.de/Manual/4-2-0/sing_1240.htm#SEC1321), 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](https://www.singular.uni-kl.de/Manual/4-2-1/sing_1247.htm#SEC1328) (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*z2Wed, 25 Aug 2021 16:03:05 +0200https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?answer=58679#post-id-58679Comment by rburing for <p>I understand a minimal generating set to be a set of generators such that no proper subset is a set of generators.</p>
<p>(Is the cardinality of a minimal generating set always the same? For subrings I don't know.)</p>
<p>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).</p>
<p>In Singular the subring containment problem is solved by <a href="https://www.singular.uni-kl.de/Manual/4-2-0/sing_1240.htm#SEC1321">inSubring</a>, which can be called from SageMath as follows:</p>
<pre><code>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
</code></pre>
<p>For example:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ)
sage: in_subring(x^4*y - (5/2)*x^6*y, [x^2, x^2*y])
True
</code></pre>
<p>The documentation of <code>inSubring</code> states that it does the same as <a href="https://www.singular.uni-kl.de/Manual/4-2-1/sing_1247.htm#SEC1328">algebra_containment</a> (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.</p>
<p>Repeating the above example using the new method:</p>
<pre><code>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
</code></pre>
<p>If I'm not mistaken then this latter method can be adapted to test containment in a subalgebra of $R/I$ as follows:</p>
<pre><code>sage: I = R.ideal([x^6])
sage: (f + x^7).reduce(J + I)
z1*z2
</code></pre>
https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58684#post-id-58684The 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](https://www.researchgate.net/post/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.Wed, 25 Aug 2021 18:44:21 +0200https://ask.sagemath.org/question/58630/compute-minimal-number-of-generators-of-subring/?comment=58684#post-id-58684