Elements of Infinite Polynomial Rings¶
AUTHORS:
Simon King <simon.king@nuigalway.ie>
Mike Hansen <mhansen@gmail.com>
An Infinite Polynomial Ring has generators \(x_\ast, y_\ast,...\), so
that the variables are of the form \(x_0, x_1, x_2, ..., y_0, y_1,
y_2,...,...\) (see infinite_polynomial_ring
).
Using the generators, we can create elements as follows:
sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: a = x[3]
sage: b = y[4]
sage: a
x_3
sage: b
y_4
sage: c = a*b+a^3-2*b^4
sage: c
x_3^3 + x_3*y_4 - 2*y_4^4
Any Infinite Polynomial Ring X
is equipped with a monomial ordering.
We only consider monomial orderings in which:
X.gen(i)[m] > X.gen(j)[n]
\(\iff\)i<j
, ori==j
andm>n
Under this restriction, the monomial ordering can be lexicographic (default), degree lexicographic, or degree reverse lexicographic. Here, the ordering is lexicographic, and elements can be compared as usual:
sage: X._order
'lex'
sage: a > b
True
Note that, when a method is called that is not directly implemented
for ‘InfinitePolynomial’, it is tried to call this method for the
underlying classical polynomial. This holds, e.g., when applying the
latex
function:
sage: latex(c)
x_{3}^{3} + x_{3} y_{4} - 2 y_{4}^{4}
There is a permutation action on Infinite Polynomial Rings by permuting the indices of the variables:
sage: P = Permutation(((4,5),(2,3)))
sage: c^P
x_2^3 + x_2*y_5 - 2*y_5^4
Note that P(0)==0
, and thus variables of index zero are invariant
under the permutation action. More generally, if P
is any
callable object that accepts non-negative integers as input and
returns non-negative integers, then c^P
means to apply P
to
the variable indices occurring in c
.
- sage.rings.polynomial.infinite_polynomial_element.InfinitePolynomial(A, p)¶
Create an element of a Polynomial Ring with a Countably Infinite Number of Variables.
Usually, an InfinitePolynomial is obtained by using the generators of an Infinite Polynomial Ring (see
infinite_polynomial_ring
) or by conversion.INPUT:
A
– an Infinite Polynomial Ring.p
– a classical polynomial that can be interpreted inA
.
ASSUMPTIONS:
In the dense implementation, it must be ensured that the argument
p
coerces intoA._P
by a name preserving conversion map.In the sparse implementation, in the direct construction of an infinite polynomial, it is not tested whether the argument
p
makes sense inA
.EXAMPLES:
sage: from sage.rings.polynomial.infinite_polynomial_element import InfinitePolynomial sage: X.<alpha> = InfinitePolynomialRing(ZZ) sage: P.<alpha_1,alpha_2> = ZZ[]
Currently,
P
andX._P
(the underlying polynomial ring ofX
) both have two variables:sage: X._P Multivariate Polynomial Ring in alpha_1, alpha_0 over Integer Ring
By default, a coercion from
P
toX._P
would not be name preserving. However, this is taken care for; a name preserving conversion is impossible, and by consequence an error is raised:sage: InfinitePolynomial(X, (alpha_1+alpha_2)^2) Traceback (most recent call last): ... TypeError: Could not find a mapping of the passed element to this ring.
When extending the underlying polynomial ring, the construction of an infinite polynomial works:
sage: alpha[2] alpha_2 sage: InfinitePolynomial(X, (alpha_1+alpha_2)^2) alpha_2^2 + 2*alpha_2*alpha_1 + alpha_1^2
In the sparse implementation, it is not checked whether the polynomial really belongs to the parent, and when it does not, the results may be unexpected due to coercions:
sage: Y.<alpha,beta> = InfinitePolynomialRing(GF(2), implementation='sparse') sage: a = (alpha_1+alpha_2)^2 sage: InfinitePolynomial(Y, a) alpha_0^2 + beta_0^2
However, it is checked when doing a conversion:
sage: Y(a) alpha_2^2 + alpha_1^2
- class sage.rings.polynomial.infinite_polynomial_element.InfinitePolynomial_dense(A, p)¶
Bases:
sage.rings.polynomial.infinite_polynomial_element.InfinitePolynomial_sparse
Element of a dense Polynomial Ring with a Countably Infinite Number of Variables.
INPUT:
A
– an Infinite Polynomial Ring in dense implementationp
– a classical polynomial that can be interpreted inA
.
Of course, one should not directly invoke this class, but rather construct elements of
A
in the usual way.This class inherits from
InfinitePolynomial_sparse
. See there for a description of the methods.
- class sage.rings.polynomial.infinite_polynomial_element.InfinitePolynomial_sparse(A, p)¶
Bases:
sage.structure.element.RingElement
Element of a sparse Polynomial Ring with a Countably Infinite Number of Variables.
INPUT:
A
– an Infinite Polynomial Ring in sparse implementationp
– a classical polynomial that can be interpreted inA
.
Of course, one should not directly invoke this class, but rather construct elements of
A
in the usual way.EXAMPLES:
sage: A.<a> = QQ[] sage: B.<b,c> = InfinitePolynomialRing(A,implementation='sparse') sage: p = a*b[100] + 1/2*c[4] sage: p a*b_100 + 1/2*c_4 sage: p.parent() Infinite polynomial ring in b, c over Univariate Polynomial Ring in a over Rational Field sage: p.polynomial().parent() Multivariate Polynomial Ring in b_100, b_0, c_4, c_0 over Univariate Polynomial Ring in a over Rational Field
- coefficient(monomial)¶
Returns the coefficient of a monomial in this polynomial.
INPUT:
A monomial (element of the parent of self) or
a dictionary that describes a monomial (the keys are variables of the parent of self, the values are the corresponding exponents)
EXAMPLES:
We can get the coefficient in front of monomials:
sage: X.<x> = InfinitePolynomialRing(QQ) sage: a = 2*x[0]*x[1] + x[1] + x[2] sage: a.coefficient(x[0]) 2*x_1 sage: a.coefficient(x[1]) 2*x_0 + 1 sage: a.coefficient(x[2]) 1 sage: a.coefficient(x[0]*x[1]) 2
We can also pass in a dictionary:
sage: a.coefficient({x[0]:1, x[1]:1}) 2
- footprint()¶
Leading exponents sorted by index and generator.
OUTPUT:
D
– a dictionary whose keys are the occurring variable indices.D[s]
is a list[i_1,...,i_n]
, wherei_j
gives the exponent ofself.parent().gen(j)[s]
in the leading term ofself
.EXAMPLES:
sage: X.<x,y> = InfinitePolynomialRing(QQ) sage: p = x[30]*y[1]^3*x[1]^2+2*x[10]*y[30] sage: sorted(p.footprint().items()) [(1, [2, 3]), (30, [1, 0])]
- gcd(x)¶
computes the greatest common divisor
EXAMPLES:
sage: R.<x>=InfinitePolynomialRing(QQ) sage: p1=x[0]+x[1]**2 sage: gcd(p1,p1+3) 1 sage: gcd(p1,p1)==p1 True
- is_nilpotent()¶
Return
True
ifself
is nilpotent, i.e., some power ofself
is 0.EXAMPLES:
sage: R.<x> = InfinitePolynomialRing(QQbar) sage: (x[0]+x[1]).is_nilpotent() False sage: R(0).is_nilpotent() True sage: _.<x> = InfinitePolynomialRing(Zmod(4)) sage: (2*x[0]).is_nilpotent() True sage: (2+x[4]*x[7]).is_nilpotent() False sage: _.<y> = InfinitePolynomialRing(Zmod(100)) sage: (5+2*y[0] + 10*(y[0]^2+y[1]^2)).is_nilpotent() False sage: (10*y[2] + 20*y[5] - 30*y[2]*y[5] + 70*(y[2]^2+y[5]^2)).is_nilpotent() True
- is_unit()¶
Answer whether
self
is a unit.EXAMPLES:
sage: R1.<x,y> = InfinitePolynomialRing(ZZ) sage: R2.<a,b> = InfinitePolynomialRing(QQ) sage: (1+x[2]).is_unit() False sage: R1(1).is_unit() True sage: R1(2).is_unit() False sage: R2(2).is_unit() True sage: (1+a[2]).is_unit() False
Check that trac ticket #22454 is fixed:
sage: _.<x> = InfinitePolynomialRing(Zmod(4)) sage: (1 + 2*x[0]).is_unit() True sage: (x[0]*x[1]).is_unit() False sage: _.<x> = InfinitePolynomialRing(Zmod(900)) sage: (7+150*x[0] + 30*x[1] + 120*x[1]*x[100]).is_unit() True
- lc()¶
The coefficient of the leading term of
self
.EXAMPLES:
sage: X.<x,y> = InfinitePolynomialRing(QQ) sage: p = 2*x[10]*y[30]+3*x[10]*y[1]^3*x[1]^2 sage: p.lc() 3
- lm()¶
The leading monomial of
self
.EXAMPLES:
sage: X.<x,y> = InfinitePolynomialRing(QQ) sage: p = 2*x[10]*y[30]+x[10]*y[1]^3*x[1]^2 sage: p.lm() x_10*x_1^2*y_1^3
- lt()¶
The leading term (= product of coefficient and monomial) of
self
.EXAMPLES:
sage: X.<x,y> = InfinitePolynomialRing(QQ) sage: p = 2*x[10]*y[30]+3*x[10]*y[1]^3*x[1]^2 sage: p.lt() 3*x_10*x_1^2*y_1^3
- max_index()¶
Return the maximal index of a variable occurring in
self
, or -1 ifself
is scalar.EXAMPLES:
sage: X.<x,y> = InfinitePolynomialRing(QQ) sage: p=x[1]^2+y[2]^2+x[1]*x[2]*y[3]+x[1]*y[4] sage: p.max_index() 4 sage: x[0].max_index() 0 sage: X(10).max_index() -1
- polynomial()¶
Return the underlying polynomial.
EXAMPLES:
sage: X.<x,y> = InfinitePolynomialRing(GF(7)) sage: p = x[2]*y[1]+3*y[0] sage: p x_2*y_1 + 3*y_0 sage: p.polynomial() x_2*y_1 + 3*y_0 sage: p.polynomial().parent() Multivariate Polynomial Ring in x_2, x_1, x_0, y_2, y_1, y_0 over Finite Field of size 7 sage: p.parent() Infinite polynomial ring in x, y over Finite Field of size 7
- reduce(I, tailreduce=False, report=None)¶
Symmetrical reduction of
self
with respect to a symmetric ideal (or list of Infinite Polynomials).INPUT:
I
– aSymmetricIdeal
or a list of Infinite Polynomials.tailreduce
– (bool, defaultFalse
) Tail reduction is performed if this parameter isTrue
.report
– (object, defaultNone
) If notNone
, some information on the progress of computation is printed, since reduction of huge polynomials may take a long time.
OUTPUT:
Symmetrical reduction of
self
with respect toI
, possibly with tail reduction.THEORY:
Reducing 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 does not diminish the variable indices occurring in \(N\) and preserves their order, so that there is some term \(T\in X\) with \(TN^P = M\). If there is no such permutation, return \(p\)
Replace \(p\) by \(p-T q^P\) and continue with step 1.
EXAMPLES:
sage: X.<x,y> = InfinitePolynomialRing(QQ) sage: p = y[1]^2*y[3]+y[2]*x[3]^3 sage: p.reduce([y[2]*x[1]^2]) x_3^3*y_2 + y_3*y_1^2
The preceding is correct: If a permutation turns
y[2]*x[1]^2
into a factor of the leading monomialy[2]*x[3]^3
ofp
, then it interchanges the variable indices 1 and 2; this is not allowed in a symmetric reduction. However, reduction byy[1]*x[2]^2
works, since one can change variable index 1 into 2 and 2 into 3:sage: p.reduce([y[1]*x[2]^2]) y_3*y_1^2
The next example shows that tail reduction is not done, unless it is explicitly advised. The input can also be a Symmetric Ideal:
sage: I = (y[3])*X sage: p.reduce(I) x_3^3*y_2 + y_3*y_1^2 sage: p.reduce(I, tailreduce=True) x_3^3*y_2
Last, we demonstrate the
report
option:sage: p=x[1]^2+y[2]^2+x[1]*x[2]*y[3]+x[1]*y[4] sage: p.reduce(I, tailreduce=True, report=True) :T[2]:> > x_1^2 + y_2^2
The output ‘:’ means that there was one reduction of the leading monomial. ‘T[2]’ means that a tail reduction was performed on a polynomial with two terms. At ‘>’, one round of the reduction process is finished (there could only be several non-trivial rounds if \(I\) was generated by more than one polynomial).
- ring()¶
The ring which
self
belongs to.This is the same as
self.parent()
.EXAMPLES:
sage: X.<x,y> = InfinitePolynomialRing(ZZ,implementation='sparse') sage: p = x[100]*y[1]^3*x[1]^2+2*x[10]*y[30] sage: p.ring() Infinite polynomial ring in x, y over Integer Ring
- squeezed()¶
Reduce the variable indices occurring in
self
.OUTPUT:
Apply a permutation to
self
that does not change the order of the variable indices ofself
but squeezes them into the range 1,2,…EXAMPLES:
sage: X.<x,y> = InfinitePolynomialRing(QQ,implementation='sparse') sage: p = x[1]*y[100] + x[50]*y[1000] sage: p.squeezed() x_2*y_4 + x_1*y_3
- stretch(k)¶
Stretch
self
by a given factor.INPUT:
k
– an integer.OUTPUT:
Replace \(v_n\) with \(v_{n\cdot k}\) for all generators \(v_\ast\) occurring in self.
EXAMPLES:
sage: X.<x> = InfinitePolynomialRing(QQ) sage: a = x[0] + x[1] + x[2] sage: a.stretch(2) x_4 + x_2 + x_0 sage: X.<x,y> = InfinitePolynomialRing(QQ) sage: a = x[0] + x[1] + y[0]*y[1]; a x_1 + x_0 + y_1*y_0 sage: a.stretch(2) x_2 + x_0 + y_2*y_0
- symmetric_cancellation_order(other)¶
Comparison of leading terms by Symmetric Cancellation Order, \(<_{sc}\).
INPUT:
self, other – two Infinite Polynomials
ASSUMPTION:
Both Infinite Polynomials are non-zero.
OUTPUT:
(c, sigma, w)
, wherec = -1,0,1, or None if the leading monomial of
self
is smaller, equal, greater, or incomparable with respect toother
in the monomial ordering of the Infinite Polynomial Ringsigma is a permutation witnessing
self
\(<_{sc}\)other
(resp.self
\(>_{sc}\)other
) or is 1 ifself.lm()==other.lm()
w is 1 or is a term so that
w*self.lt()^sigma == other.lt()
if \(c\le 0\), andw*other.lt()^sigma == self.lt()
if \(c=1\)
THEORY:
If the Symmetric Cancellation Order is a well-quasi-ordering then computation of Groebner bases always terminates. This is the case, e.g., if the monomial order is lexicographic. For that reason, lexicographic order is our default order.
EXAMPLES:
sage: X.<x,y> = InfinitePolynomialRing(QQ) sage: (x[2]*x[1]).symmetric_cancellation_order(x[2]^2) (None, 1, 1) sage: (x[2]*x[1]).symmetric_cancellation_order(x[2]*x[3]*y[1]) (-1, [2, 3, 1], y_1) sage: (x[2]*x[1]*y[1]).symmetric_cancellation_order(x[2]*x[3]*y[1]) (None, 1, 1) sage: (x[2]*x[1]*y[1]).symmetric_cancellation_order(x[2]*x[3]*y[2]) (-1, [2, 3, 1], 1)
- tail()¶
The tail of
self
(this isself
minus its leading term).EXAMPLES:
sage: X.<x,y> = InfinitePolynomialRing(QQ) sage: p = 2*x[10]*y[30]+3*x[10]*y[1]^3*x[1]^2 sage: p.tail() 2*x_10*y_30
- variables()¶
Return the variables occurring in
self
(tuple of elements of some polynomial ring).EXAMPLES:
sage: X.<x> = InfinitePolynomialRing(QQ) sage: p = x[1] + x[2] - 2*x[1]*x[3] sage: p.variables() (x_3, x_2, x_1) sage: x[1].variables() (x_1,) sage: X(1).variables() ()