#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.
>
> 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.
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])}}}
--
Comment(by SimonKing):
Herewith i try to unify the dense and the sparse approach towards infinite
polynomial rings of ticket #5453. Also, when computing symmetric Groebner
bases, i strictly do as suggested by Aschenbrenner and Hillar, without the
attempt to be clever.
Here i repeat the main examples from above, with the new syntax, and
partially with corrected results:
{{{
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
sage: I.reduce(J)
Symmetric Ideal (0, 0) of Infinite polynomial ring in x, y over Rational
Field
}}}
Note that indeed the result is a symmetric Gröbner basis (which was not
the case in the original example that i gave):
{{{
sage: for P in Permutations(4):
....: print [(p^P).reduce(J) for p in J.gens()]
....:
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
}}}
The same example in 'deglex' or 'degrevlex' works, too, but it takes
longer.
Note that the implementation is now ''dense'':
{{{
sage: x[7]; X.polynomial_ring()
sage: x[7]; X.polynomial_ring()
x7
Multivariate Polynomial Ring in y7, y6, y5, y4, y3, y2, y1, y0, x7, x6,
x5, x4, x3, x2, x1, x0 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 really sucks that uni- and multivariate polynomials have a different
interface!
Continuing with the examples:
If high variable indices occur, the dense implementation is not good. But
the following works in the sparse implementation.
{{{
sage: X.<x,y> = InfinitePolynomialRing(QQ,implementation='sparse')
sage: P = SymmetricGroup(5).random_element()
sage: x[0]^P
x0
sage: I = X*(x[1]*y[1],x[50]*y[1000])
sage: [p._p.parent() for p in I.gens()]
[Multivariate Polynomial Ring in y1, x1 over Rational Field,
Multivariate Polynomial Ring in y1000, x50 over Rational Field]
sage: J=I.groebner_basis(); J
Symmetric Ideal (y1*x1, y1*x2, y2*x1) of Infinite polynomial ring in x, y
over Rational Field
sage: [p._p.parent() for p in J.gens()]
[Multivariate Polynomial Ring in y1, x1 over Rational Field,
Multivariate Polynomial Ring in y1, x2 over Rational Field,
Multivariate Polynomial Ring in y2, x1 over Rational Field]
}}}
OK.
Summary: It is a common interface for both implementations, but i need to
work on the reduce method.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5566#comment:11>
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
-~----------~----~----~----~------~----~------~--~---
