#5566: Groebner bases of Symmetric Ideals
---------------------------------+------------------------------------------
Reporter: SimonKing | Owner: SimonKing
Type: enhancement | Status: new
Priority: major | Milestone: sage-3.4.1
Component: commutative algebra | Keywords:
---------------------------------+------------------------------------------
This ticket is related with [#5453], but the patch should apply to a clean
{{{sage-3.4}}}.
'''Symmetric Ideals''' were introduced by
[http://de.arxiv.org/abs/math/0502078/ Aschenbrenner and Hillar], meaning
"ideals in polynomial rings with countably many variables that are set-
wise invariant under all variable permutations"; it was shown that they
are finitely generated.
Later on, Aschenbrenner and Hillar also presented a
[http://de.arxiv.org/abs/0801.4439/ Buchberger algorithm] for Symmetric
Ideals.
My aim is to implement this into Sage. The patch provides classes for the
Symmetric Polynomial Rings, their elements and their ideals. The methods
implement basic polynomial arithmetic, the permutation action, the
''Symmetric Cancellation Order'' (a notion that is central in the work of
Aschenbrenner and Hillar), symmetric reduction, and the computation of
Gröbner bases.
Here are some examples showing the main features
{{{
sage: X.<x,y> = SymmetricPolynomialRing(QQ)
}}}
Now, x and y are generators of X, meaning that we have two infinite
sequences of variables, one obtained by {{{x[n]}}} and the other by
{{{y[m]}}} for integers m, n.
We can do polynomial arithmetic in X, and we can create ideals in the
usual way:
{{{
sage: I=X*(x[1]^2+y[2]^2,x[1]*x[2]*y[3]+x[1]*y[4])
}}}
Now, we can compute a Gröbner basis; the default monomial order is
lexicographic (see below).
{{{
sage: J=I.groebner_basis()
sage: J
Ideal (x1^4 + x1^3, x2*x1^2 - x1^3, x2^2 - x1^2, y1*x1^3 + y1*x1^2, y1*x2
+ y1*x1^2, y1^2 + x1^2, y2*x1 + y1*x1^2) of Symmetric polynomial ring in
x, y over Rational Field
}}}
We can do ideal membership test by computing normal forms (symmetric
reduction):
{{{
sage: I.reduce(J)
Ideal (0, 0) of Symmetric polynomial ring in x, y over Rational Field
}}}
Note that J is not point-wise symmetric. E.g., we have
{{{
sage: G=J.gens()
sage: P=Permutation([1, 4, 3, 2])
sage: G[2]
x2^2 - x1^2
sage: G[2]^P
x4^2 - x1^2
sage: G.__contains__(G[2]^P)
False
}}}
But it is set-wise symmetric, e.g.:
{{{
sage: [(p^P).reduce(J) for p in G]
[0, 0, 0, 0, 0, 0, 0]
}}}
As usual, it is a special feature of Gröbner bases that they produce
unique normal forms. I is not a Gröbner basis, and thus ideal membership
test wouldn't work:
{{{
sage: [p.reduce(I) for p in G]
[x1^4 + x1^3,
x2*x1^2 - x1^3,
x2^2 - x1^2,
y1*x1^3 + y1*x1^2,
y1*x2 + y1*x1^2,
y1^2 + x1^2,
y2*x1 + y1*x1^2]
}}}
Note that various monomial orders are supported: lex (default), deglex,
and degrevlex.
Note that Aschenbrenner and Hillar restrict their attention to the
lexicographic order, and it is not entirely clear whether the Buchberger
algorithm would terminate in the other orders, too. But here, it does. As
usual, the Gröbner basis depends on the ordering:
{{{
sage: Y.<x,y> = SymmetricPolynomialRing(QQ,order='degrevlex')
sage: I2=Y*(x[1]^2+y[2]^2,x[1]*x[2]*y[3]+x[1]*y[4])
sage: J2=I2.groebner_basis()
sage: J2
Ideal (y3*x1 - y2*x1, x2^2 - x1^2, y1*x2 - y2*x1, y1^2 + x1^2, x2*x1^2 -
x1^3, y1*x1^2 + y2*x1, y2*x1^2 + y2*x1, y2*x2*x1 + y2*x1, y2*y1*x1 + x1^3,
x1^4 + x1^3) of Symmetric polynomial ring in x, y over Rational Field
}}}
Note that we assume an automatic (name-preserving) conversion between X
and Y. Hence, we can do the following and see that J2 is not a
''lexicographic'' Gröbner basis:
{{{
sage: J.reduce(J2)
Ideal (0, 0, 0, y2*x1 + y1*x1^2, y2*x1 + y1*x1^2, 0, y2*x1 + y1*x1^2) of
Symmetric polynomial ring in x, y over Rational Field
}}}
In any order, we insist to have {{{X.gen(i)[m]<X.gen(j)[n]}}} if and only
if i<j or (i==j and m<n).
Probably the doc tests should be improved, and I think it would also be
nice to overload the {{{__pow__}}} and {{{__mul__}}} methods for Symmetric
Ideals, since the default methods do not give the correct result: We
should have {{{(X*(x[1]))^2 == X*(x[1]^2,x[1]*x[2])}}}.
Also, it may be that there should be no coercion between X and Y in the
above situation.
Therefore I am uncertain whether it is 'needs review' or 'needs work'. I
think I leave it as 'with patch'...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5566>
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
-~----------~----~----~----~------~----~------~--~---
