#5566: [with patch, needs work] 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
---------------------------------+------------------------------------------
Old description:
> 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/0411514/ 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.
>
> Note
>
> 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^5 + x1^4, x2*x1^2 + x1^4, 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^5 + x1^4,
> x2*x1^2 + x1^4,
> 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, y1*x1^3 + y1*x1^2, y1*x2 + 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).
>
> I overloaded the {{{__pow__}}} and {{{__mul__}}} methods for Symmetric
> Ideals, since the default methods do not give the correct result: We must
> have
>
> {{{(X*(x[1]))^2 == X*(x[1]^2,x[1]*x[2])}}}
New description:
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/0411514/ 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^5 + x1^4, x2*x1^2 + x1^4, 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^5 + x1^4,
x2*x1^2 + x1^4,
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, y1*x1^3 + y1*x1^2, y1*x2 + 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).
I overloaded the {{{__pow__}}} and {{{__mul__}}} methods for Symmetric
Ideals, since the default methods do not give the correct result: We must
have
{{{(X*(x[1]))^2 == X*(x[1]^2,x[1]*x[2])}}}
--
Comment(by SimonKing):
Replying to [comment:11 SimonKing]:
...
> sage: X.<x,y> = InfinitePolynomialRing(QQ)
> sage: I=X*(x[1]^2+y[2]^2,x[1]*x[2]*y[3]+x[1]*y[4])
> sage: J=I.groebner_basis(); J
> Symmetric 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 Infinite
polynomial ring in x, y over Rational Field
...
> I just stumbled over another error: When trying to compute this example
in the sparse implementation, it fails, since at some place a univariate
polynomial occurs, which has no reduce method.
It is fixed in reduce_bugfix.patch. Now, we have in the sparse
implementation:
{{{
sage: X.<x,y> = InfinitePolynomialRing(QQ,implementation='sparse')
sage: I=X*(x[1]^2+y[2]^2,x[1]*x[2]*y[3]+x[1]*y[4])
sage: J=I.groebner_basis(); J
Symmetric 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 Infinite
polynomial ring in x, y over Rational Field
}}}
which coincides with the result in the dense implementation.
So, hope it is ready for review...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5566#comment:12>
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
-~----------~----~----~----~------~----~------~--~---
