Symmetric Reduction of Infinite Polynomials

SymmetricReductionStrategy provides a framework for efficient symmetric reduction of Infinite Polynomials, see infinite_polynomial_element.

AUTHORS:

THEORY:

According to M. Aschenbrenner and C. Hillar [AB2007], Symmetric Reduction of an element p of an Infinite Polynomial Ring X by some other element q means the following:

  1. Let M and N be the leading terms of p and q.
  2. Test whether there is a permutation P that does not does not diminish the variable indices occurring in N and preserves their order, so that there is some term T\in X with T N^P = M. If there is no such permutation, return p
  3. Replace p by p-T q^P and continue with step 1.

When reducing one polynomial p with respect to a list L of other polynomials, there usually is a choice of order on which the efficiency crucially depends. Also it helps to modify the polynomials on the list in order to simplify the basic reduction steps.

The preparation of L may be expensive. Hence, if the same list is used many times then it is reasonable to perform the preparation only once. This is the background of SymmetricReductionStrategy.

Our current strategy is to keep the number of terms in the polynomials as small as possible. For this, we sort L by increasing number of terms. If several elements of L allow for a reduction of p, we chose the one with the smallest number of terms. Later on, it should be possible to implement further strategies for choice.

When adding a new polynomial q to L, we first reduce q with respect to L. Then, we test heuristically whether it is possible to reduce the number of terms of the elements of L by reduction modulo q. That way, we see best chances to keep the number of terms in intermediate reduction steps relatively small.

EXAMPLES:

First, we create an infinite polynomial ring and one of its elements:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: p = y[1]^2*y[3]+y[1]*x[3]

We want to symmetrically reduce it by another polynomial. So, we put this other polynomial into a list and create a Symmetric Reduction Strategy object:

sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: S = SymmetricReductionStrategy(X, [y[2]^2*y[1]])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
    y2^2*y1
sage: S.reduce(p)
y3*y1^2 + y1*x3

The preceding is correct, since any permutation that turns y[2]^2*y[1] into a factor of y[1]^2*y[3] interchanges the variable indices 1 and 2 – which is not allowed in a symmetric reduction. However, reduction by y[1]^2*y[2] works, since one can change variable index 1 into 2 and 2 into 3. So, we add this to S:

sage: S.add_generator(y[1]^2*y[2])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
    y2*y1^2,
    y2^2*y1
sage: S.reduce(p)
y1*x3

The next example shows that tail reduction is not done, unless it is explicitly advised:

sage: S.reduce(y[3] + 2*y[2]*y[1]^2 + 3*y[2]^2*y[1])
y3 + 3*y2^2*y1 + 2*y2*y1^2
sage: S.tailreduce(y[3] + 2*y[2]*y[1]^2 + 3*y[2]^2*y[1])
y3

However, it is possible to ask for tailreduction already when the Symmetric Reduction Strategy is created:

sage: S2 = SymmetricReductionStrategy(X, [y[2]^2*y[1],y[1]^2*y[2]], tailreduce=True)
sage: S2
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
    y2*y1^2,
    y2^2*y1
with tailreduction
sage: S2.reduce(y[3] + 2*y[2]*y[1]^2 + 3*y[2]^2*y[1])
y3
class sage.rings.polynomial.symmetric_reduction.SymmetricReductionStrategy

A framework for efficient symmetric reduction of InfinitePolynomial, see infinite_polynomial_element.

INPUT:

  • Parent, an Infinite Polynomial Ring, see infinite_polynomial_element.
  • L, a list of elements of Parent (default: L=[]) with respect to which reduction will be done
  • good_input: If this optional parameter is true, it is assumed that each element of L is symmetrically reduced with respect to the previous elements of L

EXAMPLES:

sage: X.<y> = InfinitePolynomialRing(QQ)
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: S = SymmetricReductionStrategy(X, [y[2]^2*y[1],y[1]^2*y[2]], good_input=True)
sage: S.reduce(y[3] + 2*y[2]*y[1]^2 + 3*y[2]^2*y[1])
y3 + 3*y2^2*y1 + 2*y2*y1^2
sage: S.tailreduce(y[3] + 2*y[2]*y[1]^2 + 3*y[2]^2*y[1])
y3
__call__()
INPUT:
A polynomial or an infinite polynomial
OUTPUT:
A polynomial whose parent ring allows for coercion of any generator of self

EXAMPLES:

sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: X.<x,y> = InfinitePolynomialRing(QQ, implementation='sparse')
sage: a, b = y[2]^2*y[1], y[1]^2*y[2]
sage: p = y[3]*x[2]*x[1]
sage: S = SymmetricReductionStrategy(X, [a,b])
sage: p._p.parent().has_coerce_map_from(a._p.parent())
False
sage: q = S(p)
sage: q.parent().has_coerce_map_from(a._p.parent())
True
sage: S(p) == S(p._p)
True
__cmp__()
x.__cmp__(y) <==> cmp(x,y)
__getinitargs__()
__getstate__()
__init__()
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
static __new__()
T.__new__(S, ...) -> a new object with type S, a subtype of T
__repr__()

String representation of self

EXAMPLES:

sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: S = SymmetricReductionStrategy(X, [y[2]^2*y[1],y[1]^2*y[2]], tailreduce=True)
sage: S  # indirect doctest
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
    y2*y1^2,
    y2^2*y1
with tailreduction
__setstate__()
add_generator()

Add another polynomial to self

NOTE:
Previously added polynomials may be modified. All input is prepared in view of an efficient symmetric reduction.

EXAMPLES:

sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: S = SymmetricReductionStrategy(X)
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field
sage: S.add_generator(y[3] + y[1]*(x[3]+x[1]))
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
    y3 + y1*x3 + y1*x1

Note that the first added polynomial will be simplified when adding a suitable second polynomial:

sage: S.add_generator(x[2]+x[1])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
    y3,
    x2 + x1

By default, reduction is applied to any newly added polynomial. This can be avoided by specifying the optional parameter ‘good_input’:

sage: S.add_generator(y[2]+y[1]*x[2])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
    y3,
    y2 + y1*x2,
    x2 + x1
sage: S.reduce(x[3]+x[2])
-2*x1
sage: S.add_generator(x[3]+x[2], good_input=True)
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
    y3,
    x3 + x2,
    y2 + y1*x2,
    x2 + x1

In the previous example, x[3] + x[2] is added without being reduced to zero.

gens()

Return the list of Infinite Polynomials modulo which self reduces

EXAMPLES:

sage: X.<y> = InfinitePolynomialRing(QQ)
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: S = SymmetricReductionStrategy(X, [y[2]^2*y[1],y[1]^2*y[2]])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in y over Rational Field, modulo
    y2*y1^2,
    y2^2*y1
sage: S.gens()
[y2*y1^2, y2^2*y1]
reduce()

Symmetric reduction of an infinite polynomial

By default, tail reduction is done if and only if it was specified when creating self. If the optional parameter ‘notail’ is True, tail reduction is avoided. However, we do not guarantee that there will be no tail reduction at all in that case.

If tail reduction shall be forced, use tailreduce().

Information on the progress of computation can be obtained by specifying the optional parameter report.

EXAMPLES:

sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: S = SymmetricReductionStrategy(X, [x[3]], tailreduce=True)
sage: S.reduce(y[4]*x[1] + y[1]*x[4])
y4*x1
sage: S.reduce(y[4]*x[1] + y[1]*x[4], notail=True)
y4*x1 + y1*x4

Last, we demonstrate the ‘report’ option:

sage: S = SymmetricReductionStrategy(X, [y[2]+x[1],y[2]*y[3]+y[1]*x[2]+x[4],x[3]+x[2]])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
    x3 + x2,
    y2 + x1,
    y1*x2 + x4 + x1^2
sage: S.reduce(y[3] + y[1]*x[3] + y[1]*x[1],report=True)
:::>
y1*x1 + x4 + x1^2 - x1

Each ‘:’ indicates that one reduction of the leading monomial was performed. Eventually, the ‘>’ indicates that the computation is finished.

reset()

Remove all polynomials from self

EXAMPLES:

sage: X.<y> = InfinitePolynomialRing(QQ)
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: S = SymmetricReductionStrategy(X, [y[2]^2*y[1],y[1]^2*y[2]])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in y over Rational Field, modulo
    y2*y1^2,
    y2^2*y1
sage: S.reset()
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in y over Rational Field
setgens()

Define the list of Infinite Polynomials modulo which self reduces

INPUT:

L, a list

NOTE:

It is not tested if L is a good input. That method simply assigns a copy of L to the generators of self.

EXAMPLES:

sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: X.<y> = InfinitePolynomialRing(QQ)
sage: S = SymmetricReductionStrategy(X, [y[2]^2*y[1],y[1]^2*y[2]])
sage: R = SymmetricReductionStrategy(X)
sage: R.setgens(S.gens())
sage: R
Symmetric Reduction Strategy in Infinite polynomial ring in y over Rational Field, modulo
    y2*y1^2,
    y2^2*y1
sage: R.gens() is S.gens()
False
sage: R.gens() == S.gens()
True
tailreduce()

Symmetric reduction of an infinite polynomial, with forced tail reduction

Information on the progress of computation can be obtained by specifying the optional parameter ‘report’.

EXAMPLES:

sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy
sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: S = SymmetricReductionStrategy(X, [x[3]])
sage: S.reduce(y[4]*x[1] + y[1]*x[4])
y4*x1 + y1*x4
sage: S.tailreduce(y[4]*x[1] + y[1]*x[4])
y4*x1

Last, we demonstrate the ‘report’ option:

sage: S = SymmetricReductionStrategy(X, [y[2]+x[1],y[2]*y[3]+y[1]*x[2]+x[4],x[3]+x[2]])
sage: S
Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo
    x3 + x2,
    y2 + x1,
    y1*x2 + x4 + x1^2
sage: S.tailreduce(y[3] + y[1]*x[3] + y[1]*x[1],report=True)
T[3]:::>
T[3]:>
y1*x1 - x2 + x1^2 - x1
The protocol means the following.
  • ‘T[3]’ means that we currently do tail reduction for a polynomial with three terms.
  • ‘:::>’ means that there were three reductions of leading terms.
  • The tail of the result of the preceding reduction still has three terms. One reduction of leading terms was possible, and then the final result was obtained.

Previous topic

Symmetric Ideals of Infinite Polynomial Rings

Next topic

Infinite Polynomial Rings

This Page