Ask Your Question

The number of solutions of a polynomial system using a Gröbner basis

asked 2020-01-26 11:38:10 +0200

The following extract from this Wikipedia page 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?

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted

answered 2020-01-26 12:14:29 +0200

rburing gravatar image

Yes, 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()

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

So perhaps the more interesting quantity is

 sage: I.radical().vector_space_dimension()

which agrees with the number of zeros without multiplicity.

(There is an easy algorithm to compute the radical of a zero-dimensional ideal.)

edit flag offensive delete link more


Is it required to compute the Gröbner basis? Does the function normal_basis() recompute the Gröbner basis?

Sébastien Palcoux gravatar imageSébastien Palcoux ( 2020-01-27 03:05:55 +0200 )edit

The 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.

rburing gravatar imagerburing ( 2020-01-27 10:57:43 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2020-01-26 11:38:10 +0200

Seen: 591 times

Last updated: Jan 26 '20