#5566: [with patch, needs review] Symmetric Groebner bases and Infinitely
Generated Polynomial Rings
---------------------------------+------------------------------------------
Reporter: SimonKing | Owner: SimonKing
Type: enhancement | Status: new
Priority: major | Milestone: sage-3.4.2
Component: commutative algebra | Keywords: Symmetric Ideal
---------------------------------+------------------------------------------
Comment(by SimonKing):
Since many things changed, here is an account of what the patch provides:
* Two implementations of polynomial rings over fields with countably many
generators, indexed by natural numbers:
- A sparse implementation, that allows for working with very high
variable indices
- A dense implementation, that is much faster provided the variable
indices are not too big.
* Elements of these infinite polynomial rings, with usual arithmetic and
with a permutation action on the variables.
* Symmetric Ideals, which are ideals that, in addition, are invariant
under variable permutation.
* Gröbner stuff:
- A symmetric version of polynomial reduction, based on the Cython
class 'SymmetricReductionStrategy' that tries to perform the reduction in
an efficient way (idea: keep intermediate results small).
- Symmetric Interreduction
- Computation of Symmetric Gröbner bases, which is at least possible
for lexicographic term order, according to Aschenbrenner and Hillar.
'''__Disclaimer__'''
I am afraid that again I tried to be clever in implementing the symmetric
Gröbner basis computation. The following is my justification:
The underlying idea of any Gröbner basis computation (symmetric or
straight) is:
* Perform certain operations that may yield new leading monomials.
* Continue to perform these operations until it stabilizes.
In the case of symmetric ideals, these operations are (according to
Aschenbrenner and Hillar):
1. S-polynomials
2. The action of Sym(N), the full symmetric group, where N is some number
that will increase until it stabilizes.
I replace Sym(N) by the elementary transpositions (i,j) for i,j<=N. I
think this works, for the following reason:
* Let m, n be monomials, m<n, and let P in Sym(N) be a permutation so
that {{{m^P>n^P}}}.
* The action of P does not change the polynomial degree. Hence, in all of
our term orders (lex, deglex, degrevlex), "{{{m<n but m^P>n^P}}}" can only
occur if P changes the lexicographic order of m and n.
* If it changes the lexicographic order then we find indices i, j so that
- the exponents of x_k in m and n coincide, for all k<i
- the exponent of x_i in m is smaller than the exponent of x_j in m
- P(j)=i.
* Hence, the elementary transposition (i,j) would change the order of m
and n as well.
In other words, if there is a permutation that turns a non-leading
monomial into a leading monomial, then there is an elementary
transposition that does the job as well.
I am sorry to do mathematics here. With that trick, I can do serious
examples (20000 polynomials out to variables index 10), which would be
impossible when studying ''all'' permutations.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5566#comment:20>
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
-~----------~----~----~----~------~----~------~--~---
