# Basis of invariant polynomial system

I've been trying to compute a Grobner basis for a specific invariant polynomial system. It has 6 variables, 6 constants and 6 equations and is invariant to a group of cardinality 2. Various algorithms have been ran on it, including FGb/Gb through Maple and Singular through SAGE system. In both cases, the invariance was ignored and the computation of the Grobner basis failed to finish after hours (sometime days) of computation, while occupying all the memory available. Please note, I do not know what exactly the underlying algorithm was (Buchberger/F4/F5...). It is an engineering application and in practice, I would only need the first few polynomials of the Grobner basis, that is the ones with as low degree as possible. I'm an engineer not a mathematician, so my knowledge of the topic is very limited. I did however understood, that in case of invariant systems, a SAGBI basis (or invariant Grobner basis) can be computed much more efficiently. More important, the invariant Grobner basis can be computed "up to a given degree", which is exactly what I probably need. I got a hint that such algorithm might exist in SAGE. I've been searching through the SAGE documentation, but it seems I don't know what to search for and the system is huge. If anyone can point me to right direction it would be great! The problem:

X0  + Y0 - S0 = 0
X0   X1  + Y0   Y1   -     S1 = 0
X0 ( X1^2 + 2  X2 )+ Y0 ( Y1^2 + 2 Y2 )-   2 S2 = 0
X0 ( X1^3 + 6  X2 X1 )+ Y0 ( Y1^3 + 6 Y2 Y1 )  -   6 S3 = 0
X0 ( X1^4 + 12 X2 X1^2 + 12 X2^2 )+ Y0 ( Y1^4 + 12 Y2 Y1^2 + 12 Y2^2 )-  24 S4 = 0
X0 ( X1^5 + 20 X2 X1^3 + 60 X2^2 X1 )  + Y0 ( Y1^5 + 20 Y2 Y1^3 + 60 Y2^2 Y1 )  - 120 S5 = 0


Where X0,X1,X2,Y0,Y1,Y2 are variables S0...S5 are constants, all are complex numbers.

edit retag close merge delete

Sort by » oldest newest most voted

Hooray, there is SAGBI bases in Sage! Namely, Singular provides them. See singular manual

It is not totally staight forward to use it in Sage, because your base ring is a function field, and even though Singular itself can deal with it, lib_singular (which is used for many polynomial rings) cannot handle it, yet.

So, you could try it via the pexpect interface (see the Sage reference manual):

sage: R.<S0,S1,S2,S3,S4,S5> = QQ[]
sage: P.<X0,X1,X2, Y0,Y1,Y2> = Frac(R)[]
sage: I = P * [
X0  + Y0 - S0,
X0 *  X1  + Y0 *  Y1   -     S1,
X0* ( X1^2 + 2 * X2 )+ Y0* ( Y1^2 + 2* Y2 )-   2* S2,
X0* ( X1^3 + 6 * X2* X1 )+ Y0 *( Y1^3 + 6* Y2 *Y1 )  -   6 *S3,
X0* ( X1^4 + 12* X2* X1^2 + 12* X2^2 )+ Y0 *( Y1^4 + 12* Y2* Y1^2 + 12* Y2^2 )-  24* S4,
X0* ( X1^5 + 20* X2* X1^3 + 60* X2^2* X1 )  + Y0 *( Y1^5 + 20 *Y2* Y1^3 + 60* Y2^2 *Y1 )  - 120* S5]
sage: PI = singular(I)
sage: PI
X0+Y0+(-S0),
X0*X1+Y0*Y1+(-S1),
X0*X1^2+Y0*Y1^2+2*X0*X2+2*Y0*Y2+(-2*S2),
X0*X1^3+Y0*Y1^3+6*X0*X1*X2+6*Y0*Y1*Y2+(-6*S3),
X0*X1^4+Y0*Y1^4+12*X0*X1^2*X2+12*Y0*Y1^2*Y2+12*X0*X2^2+12*Y0*Y2^2+(-24*S4),
X0*X1^5+Y0*Y1^5+20*X0*X1^3*X2+20*Y0*Y1^3*Y2+60*X0*X1*X2^2+60*Y0*Y1*Y2^2+(-120*S5)
sage: singular.LIB("sagbi.lib")
sage: G = PI.sagbi()


However, it doesn't seem to be an easy problem - I give no guarantee that it will soon finish. Also, it seems that it can not be used with a degree bound; at least, the Singular manual does not mention it.

more

This is great! I'm gonna give the SAGBI basis a go today, will report...thanks again!

( 2011-11-26 09:35:27 +0200 )edit

update: there is a sagbipart(...) function which "performs k iterations of the SAGBI construction algorithm for the subalgebra given by the generators given by (the ideal) A". I'm aware this is not the same as "computing SAGBI basis of up to arbitrary degree", but it might, in practice, have very similar effect. how wrong am i ? Further, there doesn't seem to be a way to specify the invariance group to the system. Is it computed or what? Thanks!

( 2011-11-26 09:53:31 +0200 )edit

If you just want to compute a truncated Gröbner basis of your system (say, out to degree 7), then it's easy:

sage: R.<S0,S1,S2,S3,S4,S5> = QQ[]
sage: P.<X0,X1,X2, Y0,Y1,Y2> = Frac(R)[]
sage: P
Multivariate Polynomial Ring in X0, X1, X2, Y0, Y1, Y2 over Fraction Field of Multivariate Polynomial Ring in S0, S1, S2, S3, S4, S5 over Rational Field
sage: I = P * [
....: X0  + Y0 - S0,
....: X0 *  X1  + Y0 *  Y1   -     S1,
....: X0* ( X1^2 + 2 * X2 )+ Y0* ( Y1^2 + 2* Y2 )-   2* S2,
....: X0* ( X1^3 + 6 * X2* X1 )+ Y0 *( Y1^3 + 6* Y2 *Y1 )  -   6 *S3,
....: X0* ( X1^4 + 12* X2* X1^2 + 12* X2^2 )+ Y0 *( Y1^4 + 12* Y2* Y1^2 + 12* Y2^2 )-  24* S4,
....: X0* ( X1^5 + 20* X2* X1^3 + 60* X2^2* X1 )  + Y0 *( Y1^5 + 20 *Y2* Y1^3 + 60* Y2^2 *Y1 )  - 120* S5]
sage: I
Ideal (X0 + Y0 - S0, X0*X1 + Y0*Y1 - S1, X0*X1^2 + Y0*Y1^2 + 2*X0*X2 + 2*Y0*Y2 - 2*S2, X0*X1^3 + Y0*Y1^3 + 6*X0*X1*X2 + 6*Y0*Y1*Y2 - 6*S3, X0*X1^4 + Y0*Y1^4 + 12*X0*X1^2*X2 + 12*Y0*Y1^2*Y2 + 12*X0*X2^2 + 12*Y0*Y2^2 - 24*S4, X0*X1^5 + Y0*Y1^5 + 20*X0*X1^3*X2 + 20*Y0*Y1^3*Y2 + 60*X0*X1*X2^2 + 60*Y0*Y1*Y2^2 - 120*S5) of Multivariate Polynomial Ring in X0, X1, X2, Y0, Y1, Y2 over Fraction Field of Multivariate Polynomial Ring in S0, S1, S2, S3, S4, S5 over Rational Field
sage: %time G = I.groebner_basis(deg_bound = 7)
CPU times: user 0.17 s, sys: 0.01 s, total: 0.18 s
Wall time: 0.46 s
sage: len(G)
18


However, Note two things:

"Usual Gröbner bases" will always destroy the symmetry of your original equations. I am afraid it seems that there is no SAGBI basis in Sage. I wish it was.

Also note that the result is, in general, not a "Gröbner basis out to degree n" but a "truncated Gröbner basis". Namely, while computing the Gröbner basis, all polynomials with leading monomial of degree greater than n will simply be discarded of. But for inhomogeneous systems (like yours) it could happen that the s-polynomial of two polynomials of degree > n have a leading monomial of degree smaller than n. Hence, the truncation will lose information.

more

Thank you very much for your help Simon, very insightful. Let's assume there is a way to get a univariate polynomial from the truncated Grober basis. Since "information was lost", as you adequately put it, any actual solution arising from this potential univariate polynomial will in fact be wrong, right?

( 2011-11-26 09:28:30 +0200 )edit

Even though you haven't told us enough data to actually see what the problem is, there is certainly no canned one-liner in Sage that does everything that you want. I'll assume that every equation is invariant under the group, otherwise you'll have to do more representation theory. Your equations also need to be of fixed total degree, otherwise you might get the wrong answer if you truncate your Groebner basis computation at some maximum degree. There is some discussion in http://trac.sagemath.org/sage_trac/ti... on that very subject.

Roughly, you probably want to do the following. First, compute the Hironaka decomposition of your invariant ring. Express the equations in terms of the primary and secondary invariants. Run the Groebner basis computation in the invariant ring.

more

Sorry for the missing data. I have updated the question, attaching the problem definition.

( 2011-11-24 17:03:53 +0200 )edit

Hi Volker, I think the OP's problem is not "given a finite group action, compute a minimal generating set of the invariant ring". But just to put that straight: Hironaka decomposition is not needed to compute minimal generating sets, at least in the "classical" (non-modular) case. I introduced a more direct algorithm, that is implemented in Singular since a couple of years. At that time, it clearly outperformed what was in Magma. Meanwhile, Magma uses that algorithm as well.

( 2011-11-24 18:23:05 +0200 )edit