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^32*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 nonnegative integers as input and
returns nonnegative 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 \(pT 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 nontrivial 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 nonzero.
OUTPUT:
(c, sigma, w)
, where c = 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 Ring  sigma 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 wellquasiordering 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)
 c = 1,0,1, or None if the leading monomial of

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() ()