# Elements of Infinite Polynomial Rings¶

AUTHORS:

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
sage: b = y
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, or i==j and m>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 in A.

ASSUMPTIONS:

In the dense implementation, it must be ensured that the argument p coerces into A._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 in A.

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 and X._P (the underlying polynomial ring of X) both have two variables:

sage: X._P
Multivariate Polynomial Ring in alpha_1, alpha_0 over Integer Ring


By default, a coercion from P to X._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
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)

Element of a dense Polynomial Ring with a Countably Infinite Number of Variables.

INPUT:

• A – an Infinite Polynomial Ring in dense implementation

• p – a classical polynomial that can be interpreted in A.

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)

Element of a sparse Polynomial Ring with a Countably Infinite Number of Variables.

INPUT:

• A – an Infinite Polynomial Ring in sparse implementation

• p – a classical polynomial that can be interpreted in A.

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 + 1/2*c
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*x + x + x
sage: a.coefficient(x)
2*x_1
sage: a.coefficient(x)
2*x_0 + 1
sage: a.coefficient(x)
1
sage: a.coefficient(x*x)
2


We can also pass in a dictionary:

sage: a.coefficient({x:1, x: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], where i_j gives the exponent of self.parent().gen(j)[s] in the leading term of self.

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: p = x*y^3*x^2+2*x*y
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+x**2
sage: gcd(p1,p1+3)
1
sage: gcd(p1,p1)==p1
True

is_nilpotent()

Return True if self is nilpotent, i.e., some power of self is 0.

EXAMPLES:

sage: R.<x> = InfinitePolynomialRing(QQbar)
sage: (x+x).is_nilpotent()
False
sage: R(0).is_nilpotent()
True
sage: _.<x> = InfinitePolynomialRing(Zmod(4))
sage: (2*x).is_nilpotent()
True
sage: (2+x*x).is_nilpotent()
False
sage: _.<y> = InfinitePolynomialRing(Zmod(100))
sage: (5+2*y + 10*(y^2+y^2)).is_nilpotent()
False
sage: (10*y + 20*y - 30*y*y + 70*(y^2+y^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).is_unit()
False
sage: R1(1).is_unit()
True
sage: R1(2).is_unit()
False
sage: R2(2).is_unit()
True
sage: (1+a).is_unit()
False


Check that trac ticket #22454 is fixed:

sage: _.<x> = InfinitePolynomialRing(Zmod(4))
sage: (1 + 2*x).is_unit()
True
sage: (x*x).is_unit()
False
sage: _.<x> = InfinitePolynomialRing(Zmod(900))
sage: (7+150*x + 30*x + 120*x*x).is_unit()
True

lc()

The coefficient of the leading term of self.

EXAMPLES:

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

lm()

The leading monomial of self.

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: p = 2*x*y+x*y^3*x^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*y+3*x*y^3*x^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 if self is scalar.

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: p=x^2+y^2+x*x*y+x*y
sage: p.max_index()
4
sage: x.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*y+3*y
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 – a SymmetricIdeal or a list of Infinite Polynomials.

• tailreduce – (bool, default False) Tail reduction is performed if this parameter is True.

• report – (object, default None) If not None, 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 to I, possibly with tail reduction.

THEORY:

Reducing 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 $$TN^P = M$$. If there is no such permutation, return $$p$$

3. Replace $$p$$ by $$p-T q^P$$ and continue with step 1.

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: p = y^2*y+y*x^3
sage: p.reduce([y*x^2])
x_3^3*y_2 + y_3*y_1^2


The preceding is correct: If a permutation turns y*x^2 into a factor of the leading monomial y*x^3 of p, then it interchanges the variable indices 1 and 2; this is not allowed in a symmetric reduction. However, reduction by y*x^2 works, since one can change variable index 1 into 2 and 2 into 3:

sage: p.reduce([y*x^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)*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^2+y^2+x*x*y+x*y
sage: p.reduce(I, tailreduce=True, report=True)
:T:>
>
x_1^2 + y_2^2


The output ‘:’ means that there was one reduction of the leading monomial. ‘T’ 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*y^3*x^2+2*x*y
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 of self but squeezes them into the range 1,2,…

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ,implementation='sparse')
sage: p = x*y + x*y
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 + x + x
sage: a.stretch(2)
x_4 + x_2 + x_0

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: a = x + x + y*y; 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), where

• c = -1,0,1, or None if the leading monomial of self is smaller, equal, greater, or incomparable with respect to other in the monomial ordering of the Infinite Polynomial Ring

• sigma is a permutation witnessing self $$<_{sc}$$ other (resp. self $$>_{sc}$$ other) or is 1 if self.lm()==other.lm()

• w is 1 or is a term so that w*self.lt()^sigma == other.lt() if $$c\le 0$$, and w*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*x).symmetric_cancellation_order(x^2)
(None, 1, 1)
sage: (x*x).symmetric_cancellation_order(x*x*y)
(-1, [2, 3, 1], y_1)
sage: (x*x*y).symmetric_cancellation_order(x*x*y)
(None, 1, 1)
sage: (x*x*y).symmetric_cancellation_order(x*x*y)
(-1, [2, 3, 1], 1)

tail()

The tail of self (this is self minus its leading term).

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: p = 2*x*y+3*x*y^3*x^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 + x - 2*x*x
sage: p.variables()
(x_3, x_2, x_1)
sage: x.variables()
(x_1,)
sage: X(1).variables()
()