musevic's profile - activity

Hi all!

I've been looking into the SAGBI-Grobner basis and I gave it a test drive. My very simple multivariate system is invariant and I want to find its SAGBI basis via the Singular library. I'm pretty sure the code below produces wrong result for some reason (I'm by no means saying there is a bug in the Singular lib).

The last polynomial is in fact invariant to the same G as the original system, the rest of the polynomials are identical to the original ones. A paper on the topic by Nicolas M. Thiery: Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Grobner Basis states that the remainder of dividing any polynomial with any other in the SAGBI basis should be 0, but I'm sure this is not the case here, or am I missing something? Sorry in advance for vagueness - I don't understand the topic 100%. It should be simple however to compute SAGBI basis of this system by hand or see just by looking at the result, that something might be wrong here. I suspect there is something wrong with the original set of polynomials... A link to the worksheet, if it helps!

Thank you in advance,

Sash

R1.<S0,S1,S2,S3> = QQ[]
P1.<X0,X1, Y0,Y1> = Frac(R1)[]
I1 = P * [
     X0  + Y0 - S0,
     X0 *  X1    + Y0 *  Y1     -      S1,
     X0* ( X1^2 )+ Y0 *( Y1^2 ) -   2* S2]
PI = singular(I1)
singular.LIB("sagbi.lib")
PI.sagbi()
------------------------------------------------
X0+Y0+(-S0),
X0*X1+Y0*Y1+(-S1),
X0*X1^2+Y0*Y1^2+(-2*S2),
X0*X1^2*Y0-2*X0*X1*Y0*Y1+X0*Y0*Y1^2+(-S0)*X0*X1^2+(-S0)*Y0*Y1^2+(2*S1)*X0*X1+(2*S1)*Y0*Y1+(-2*S2)*X0+(-2*S2)*Y0+(2*S0*S2-S1^2)

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!

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

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?

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.

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

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.