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.Mon, 27 Jan 2020 10:57:43 +0100The number of solutions of a polynomial system using a Gröbner basishttps://ask.sagemath.org/question/49683/the-number-of-solutions-of-a-polynomial-system-using-a-grobner-basis/The following extract from [this Wikipedia page](https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis#Solutions_of_a_system_of_algebraic_equations) explains that we can easily deduce the number of solutions of a polynomial system using Gröbner basis:
> Given the Gröbner basis G of an ideal
> I, it has only a finite number of
> zeros, if and only if, for each
> variable x, G contains a polynomial
> with a leading monomial that is a
> power of x (without any other variable
> appearing in the leading term). If it
> is the case **the number of zeros**,
> counted with multiplicity, is equal to
> the number of monomials that are not
> multiple of any leading monomial of G.
> This number is called the degree of
> the ideal.
*Question*: Is there a function in Sage computing this number of zeros from a given Gröbner basis?Sun, 26 Jan 2020 11:38:10 +0100https://ask.sagemath.org/question/49683/the-number-of-solutions-of-a-polynomial-system-using-a-grobner-basis/Answer by rburing for <p>The following extract from <a href="https://en.wikipedia.org/wiki/Gr%C3%B6bner_basis#Solutions_of_a_system_of_algebraic_equations">this Wikipedia page</a> explains that we can easily deduce the number of solutions of a polynomial system using Gröbner basis: </p>
<blockquote>
<p>Given the Gröbner basis G of an ideal
I, it has only a finite number of
zeros, if and only if, for each
variable x, G contains a polynomial
with a leading monomial that is a
power of x (without any other variable
appearing in the leading term). If it
is the case <strong>the number of zeros</strong>,
counted with multiplicity, is equal to
the number of monomials that are not
multiple of any leading monomial of G.
This number is called the degree of
the ideal.</p>
</blockquote>
<p><em>Question</em>: Is there a function in Sage computing this number of zeros from a given Gröbner basis?</p>
https://ask.sagemath.org/question/49683/the-number-of-solutions-of-a-polynomial-system-using-a-grobner-basis/?answer=49684#post-id-49684Yes, these
> monomials that are not a multiple of any leading monomial of G
form a basis of the quotient ring $R/I$ (by the reduction algorithm), also called a *normal basis* for $I$.
sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: I = Ideal([x^2+y+z-1,x+y^2+z-1,x+y+z^2-1])
sage: B = I.groebner_basis(); B
[x^2 + y + z - 1, y^2 + x + z - 1, z^2 + x + y - 1]
sage: I.normal_basis()
[x*y*z, y*z, x*z, z, x*y, y, x, 1]
The number of elements in this basis, or the vector space dimension of $R/I$, can also be found as follows:
sage: I.vector_space_dimension()
8
The zero set, or variety, of the ideal is the following:
sage: I.variety(QQbar)
[{z: 0, y: 0, x: 1},
{z: 0, y: 1, x: 0},
{z: 1, y: 0, x: 0},
{z: -2.414213562373095?, y: -2.414213562373095?, x: -2.414213562373095?},
{z: 0.4142135623730951?, y: 0.4142135623730951?, x: 0.4142135623730951?}]
The number of elements is not 8, because we are missing the "multiplicities". Indeed,
sage: I.radical() == I
False
So perhaps the more interesting quantity is
sage: I.radical().vector_space_dimension()
5
which agrees with the number of zeros without multiplicity.
(There is an easy algorithm to compute the radical of a zero-dimensional ideal.)Sun, 26 Jan 2020 12:14:29 +0100https://ask.sagemath.org/question/49683/the-number-of-solutions-of-a-polynomial-system-using-a-grobner-basis/?answer=49684#post-id-49684Comment by Sébastien Palcoux for <p>Yes, these</p>
<blockquote>
<p>monomials that are not a multiple of any leading monomial of G</p>
</blockquote>
<p>form a basis of the quotient ring $R/I$ (by the reduction algorithm), also called a <em>normal basis</em> for $I$.</p>
<pre><code>sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: I = Ideal([x^2+y+z-1,x+y^2+z-1,x+y+z^2-1])
sage: B = I.groebner_basis(); B
[x^2 + y + z - 1, y^2 + x + z - 1, z^2 + x + y - 1]
sage: I.normal_basis()
[x*y*z, y*z, x*z, z, x*y, y, x, 1]
</code></pre>
<p>The number of elements in this basis, or the vector space dimension of $R/I$, can also be found as follows:</p>
<pre><code>sage: I.vector_space_dimension()
8
</code></pre>
<p>The zero set, or variety, of the ideal is the following:</p>
<pre><code>sage: I.variety(QQbar)
[{z: 0, y: 0, x: 1},
{z: 0, y: 1, x: 0},
{z: 1, y: 0, x: 0},
{z: -2.414213562373095?, y: -2.414213562373095?, x: -2.414213562373095?},
{z: 0.4142135623730951?, y: 0.4142135623730951?, x: 0.4142135623730951?}]
</code></pre>
<p>The number of elements is not 8, because we are missing the "multiplicities". Indeed,</p>
<pre><code> sage: I.radical() == I
False
</code></pre>
<p>So perhaps the more interesting quantity is</p>
<pre><code> sage: I.radical().vector_space_dimension()
5
</code></pre>
<p>which agrees with the number of zeros without multiplicity.</p>
<p>(There is an easy algorithm to compute the radical of a zero-dimensional ideal.)</p>
https://ask.sagemath.org/question/49683/the-number-of-solutions-of-a-polynomial-system-using-a-grobner-basis/?comment=49685#post-id-49685Is it required to compute the Gröbner basis? Does the function normal_basis() recompute the Gröbner basis?Mon, 27 Jan 2020 03:05:55 +0100https://ask.sagemath.org/question/49683/the-number-of-solutions-of-a-polynomial-system-using-a-grobner-basis/?comment=49685#post-id-49685Comment by rburing for <p>Yes, these</p>
<blockquote>
<p>monomials that are not a multiple of any leading monomial of G</p>
</blockquote>
<p>form a basis of the quotient ring $R/I$ (by the reduction algorithm), also called a <em>normal basis</em> for $I$.</p>
<pre><code>sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: I = Ideal([x^2+y+z-1,x+y^2+z-1,x+y+z^2-1])
sage: B = I.groebner_basis(); B
[x^2 + y + z - 1, y^2 + x + z - 1, z^2 + x + y - 1]
sage: I.normal_basis()
[x*y*z, y*z, x*z, z, x*y, y, x, 1]
</code></pre>
<p>The number of elements in this basis, or the vector space dimension of $R/I$, can also be found as follows:</p>
<pre><code>sage: I.vector_space_dimension()
8
</code></pre>
<p>The zero set, or variety, of the ideal is the following:</p>
<pre><code>sage: I.variety(QQbar)
[{z: 0, y: 0, x: 1},
{z: 0, y: 1, x: 0},
{z: 1, y: 0, x: 0},
{z: -2.414213562373095?, y: -2.414213562373095?, x: -2.414213562373095?},
{z: 0.4142135623730951?, y: 0.4142135623730951?, x: 0.4142135623730951?}]
</code></pre>
<p>The number of elements is not 8, because we are missing the "multiplicities". Indeed,</p>
<pre><code> sage: I.radical() == I
False
</code></pre>
<p>So perhaps the more interesting quantity is</p>
<pre><code> sage: I.radical().vector_space_dimension()
5
</code></pre>
<p>which agrees with the number of zeros without multiplicity.</p>
<p>(There is an easy algorithm to compute the radical of a zero-dimensional ideal.)</p>
https://ask.sagemath.org/question/49683/the-number-of-solutions-of-a-polynomial-system-using-a-grobner-basis/?comment=49690#post-id-49690The method `normal_basis()` internally requires a Gröbner basis. If one has not yet been computed, then it computes one. If one has been computed already, then it uses that one; it does not recompute it. Note also that the result / speed depends on the chosen monomial ordering (`degrevlex` by default). Of course the dimension does not depend on this choice.Mon, 27 Jan 2020 10:57:43 +0100https://ask.sagemath.org/question/49683/the-number-of-solutions-of-a-polynomial-system-using-a-grobner-basis/?comment=49690#post-id-49690