Symmetric Reduction of Infinite Polynomials#
SymmetricReductionStrategy
provides a framework for efficient symmetric reduction of Infinite
Polynomials, see infinite_polynomial_element
.
AUTHORS:
Simon King <simon.king@nuigalway.ie>
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:
Let \(M\) and \(N\) be the leading terms of \(p\) and \(q\).
Test whether there is a permutation \(P\) that 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\).
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 choose 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]*y[3] + y[1]^2*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*x[1]])
sage: S
Symmetric Reduction Strategy in
Infinite polynomial ring in x, y over Rational Field, modulo
x_1*y_2^2
sage: S.reduce(p)
x_3*y_1^2 + y_3*y_1
The preceding is correct, since any permutation that turns
y[2]^2*x[1]
into a factor of y[1]^2*x[3]
interchanges the
variable indices 1 and 2 – which is not allowed in a symmetric
reduction. However, reduction by y[1]^2*x[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*x[2])
sage: S
Symmetric Reduction Strategy in
Infinite polynomial ring in x, y over Rational Field, modulo
x_2*y_1^2,
x_1*y_2^2
sage: S.reduce(p) # needs sage.combinat
y_3*y_1
The next example shows that tail reduction is not done, unless it is explicitly advised:
sage: S.reduce(x[3] + 2*x[2]*y[1]^2 + 3*y[2]^2*x[1]) # needs sage.combinat
x_3 + 2*x_2*y_1^2 + 3*x_1*y_2^2
sage: S.tailreduce(x[3] + 2*x[2]*y[1]^2 + 3*y[2]^2*x[1]) # needs sage.combinat
x_3
However, it is possible to ask for tailreduction already when the Symmetric Reduction Strategy is created:
sage: S2 = SymmetricReductionStrategy(X, [y[2]^2*x[1],y[1]^2*x[2]], tailreduce=True)
sage: S2
Symmetric Reduction Strategy in
Infinite polynomial ring in x, y over Rational Field, modulo
x_2*y_1^2,
x_1*y_2^2
with tailreduction
sage: S2.reduce(x[3] + 2*x[2]*y[1]^2 + 3*y[2]^2*x[1]) # needs sage.combinat
x_3
- class sage.rings.polynomial.symmetric_reduction.SymmetricReductionStrategy#
Bases:
object
A framework for efficient symmetric reduction of InfinitePolynomial, see
infinite_polynomial_element
.INPUT:
Parent
– an Infinite Polynomial Ring, seeinfinite_polynomial_element
.L
– (list, default the empty list) List of elements ofParent
with respect to which will be reduced.good_input
– (bool, defaultNone
) If this optional parameter is true, it is assumed that each element ofL
is symmetrically reduced with respect to the previous elements ofL
.
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]) y_3 + 3*y_2^2*y_1 + 2*y_2*y_1^2 sage: S.tailreduce(y[3] + 2*y[2]*y[1]^2 + 3*y[2]^2*y[1]) # needs sage.combinat y_3
- add_generator(p, good_input=None)#
Add another polynomial to
self
.INPUT:
p
– An element of the underlying infinite polynomial ring.good_input
– (bool, defaultNone
) IfTrue
, it is assumed thatp
is reduced with respect toself
. Otherwise, this reduction will be done first (which may cost some time).
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 x_3*y_1 + x_1*y_1 + y_3
Note that the first added polynomial will be simplified when adding a suitable second polynomial:
sage: S.add_generator(x[2] + x[1]) # needs sage.combinat sage: S # needs sage.combinat Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo y_3, x_2 + x_1
By default, reduction is applied to any newly added polynomial. This can be avoided by specifying the optional parameter ‘good_input’:
sage: # needs sage.combinat 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 y_3, x_1*y_1 - y_2, x_2 + x_1 sage: S.reduce(x[3] + x[2]) -2*x_1 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 y_3, x_3 + x_2, x_1*y_1 - y_2, x_2 + x_1
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 y_2*y_1^2, y_2^2*y_1 sage: S.gens() [y_2*y_1^2, y_2^2*y_1]
- reduce(p, notail=False, report=None)#
Symmetric reduction of an infinite polynomial.
INPUT:
p
– an element of the underlying infinite polynomial ring.notail
– (bool, defaultFalse
) IfTrue
, tail reduction is avoided (but there is no guarantee that there will be no tail reduction at all).report
– (object, defaultNone
) If notNone
, print information on the progress of the computation.
OUTPUT:
Reduction of
p
with respect toself
.Note
If tail reduction shall be forced, use
tailreduce()
.EXAMPLES:
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy sage: X.<x,y> = InfinitePolynomialRing(QQ) sage: S = SymmetricReductionStrategy(X, [y[3]], tailreduce=True) sage: S.reduce(y[4]*x[1] + y[1]*x[4]) x_4*y_1 sage: S.reduce(y[4]*x[1] + y[1]*x[4], notail=True) x_4*y_1 + x_1*y_4
Last, we demonstrate the
report
option:sage: S = SymmetricReductionStrategy(X, [x[2] + y[1], ....: x[2]*y[3] + x[1]*y[2] + y[4], ....: y[3] + y[2]]) sage: S Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo y_3 + y_2, x_2 + y_1, x_1*y_2 + y_4 - y_3*y_1 sage: S.reduce(x[3] + x[1]*y[3] + x[1]*y[1], report=True) :::> x_1*y_1 + y_4 - y_3*y_1 - y_1
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 y_2*y_1^2, y_2^2*y_1 sage: S.reset() sage: S Symmetric Reduction Strategy in Infinite polynomial ring in y over Rational Field
- setgens(L)#
Define the list of Infinite Polynomials modulo which self reduces.
INPUT:
L
– a list of elements of the underlying infinite polynomial ring.Note
It is not tested if
L
is a good input. That method simply assigns a copy ofL
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 y_2*y_1^2, y_2^2*y_1 sage: R.gens() is S.gens() False sage: R.gens() == S.gens() True
- tailreduce(p, report=None)#
Symmetric reduction of an infinite polynomial, with forced tail reduction.
INPUT:
p
– an element of the underlying infinite polynomial ring.report
– (object, defaultNone
) If notNone
, print information on the progress of the computation.
OUTPUT:
Reduction (including the non-leading elements) of
p
with respect toself
.EXAMPLES:
sage: from sage.rings.polynomial.symmetric_reduction import SymmetricReductionStrategy sage: X.<x,y> = InfinitePolynomialRing(QQ) sage: S = SymmetricReductionStrategy(X, [y[3]]) sage: S.reduce(y[4]*x[1] + y[1]*x[4]) x_4*y_1 + x_1*y_4 sage: S.tailreduce(y[4]*x[1] + y[1]*x[4]) # needs sage.combinat x_4*y_1
Last, we demonstrate the ‘report’ option:
sage: S = SymmetricReductionStrategy(X, [x[2] + y[1], ....: x[2]*x[3] + x[1]*y[2] + y[4], ....: y[3] + y[2]]) sage: S Symmetric Reduction Strategy in Infinite polynomial ring in x, y over Rational Field, modulo y_3 + y_2, x_2 + y_1, x_1*y_2 + y_4 + y_1^2 sage: S.tailreduce(x[3] + x[1]*y[3] + x[1]*y[1], report=True) # needs sage.combinat T[3]:::> T[3]:> x_1*y_1 - y_2 + y_1^2 - y_1
- 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.