#5566: [with patch, needs review] Groebner bases of Symmetric Ideals
---------------------------------+------------------------------------------
Reporter: SimonKing | Owner: SimonKing
Type: enhancement | Status: new
Priority: major | Milestone: sage-3.4.1
Component: commutative algebra | Keywords: Symmetric Ideal
---------------------------------+------------------------------------------
Comment(by SimonKing):
Replying to [comment:7 SimonKing]:
> Replying to [comment:6 SimonKing]:
> > Example: if we start with an ideal
> > {{{
> > sage: I = X*(x[1]*y[1],x[50]*y[1000])
> > sage: J=I.groebner_basis()
> > sage: J
> > Ideal (x1*y1, x50*y1000, x51*y1) of Symmetric polynomial ring in y, x
over Rational Field
> > }}}
>
> ARRGH! This result is complete nonsense. I need to find out what
happened. Needs work. Sorry
Got it! The new version of ``SymmetricIdeals.patch`` should still apply to
sage-3.4 (tell me if I messed it up), and fixes the bug.
Let N be the maximal variable index occuring in the generators of a
symmetric ideal I. According to Aschenbrenner, one has to apply all
elements of Sym(N) to the generators, form all S-polynomials, interreduce,
then apply Sym(N+1), and so on, until it stabilizes.
Sym(N) can be rather huge, so i tried to be clever: Apply the
''generators'' of Sym(N) to the generators of J, interreduce, and repeat
until it stabilizes; i thought this is the same as applying ''all''
elements of Sym(N), but i was mistaken.
Now i proceed more carefully. I introduced a method 'squeezed', that makes
the variable indices as small as possible, without to change the ideal.
So, the N above is decreased. Next i apply ''all'' elements of Sym(N) to
the generators of {{{I.squeezed()}}}. Compute the S-polynomials and
interreduce (which i do using libsingular's groebner method).
The result takes care of symmetry out to level N. In order to make it
symmetric out to N+1, it then suffices to apply coset representatives of
Sym(N+1)/Sym(N), namely (1,N+1), (2,N+1), ..., (N,N+1). The rest is,
again, computation of S-polynomials and interreduction, and iteration.
Do you agree that this is a correct improvement of the algorithm of
Aschenbrenner and Hillar?
Anyway.
The critical example from above is now
{{{
sage: X.<x,y> = SymmetricPolynomialRing(QQ)
sage: I = X*(x[1]*y[1],x[50]*y[1000])
sage: [p._p.parent() for p in I.gens()] # start with different rings
[Multivariate Polynomial Ring in y1, x1 over Rational Field,
Multivariate Polynomial Ring in y1000, x50 over Rational Field]
sage: sage: J=I.groebner_basis()
sage: sage: J
Ideal (y1*x1, y1*x2, y2*x1) of Symmetric polynomial ring in x, y over
Rational Field
sage: sage: [p._p.parent() for p in J.gens()] # end with common rings
[Multivariate Polynomial Ring in y2, y1, x2, x1 over Rational Field,
Multivariate Polynomial Ring in y2, y1, x2, x1 over Rational Field,
Multivariate Polynomial Ring in y2, y1, x2, x1 over Rational Field]
}}}
And this is indeed the symmetric Groebner basis.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5566#comment:8>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
