Elements of Infinite Polynomial Rings¶

AUTHORS:

Simon King <simon.king@nuigalway.ie>
Mike Hansen <mhansen@gmail.com>

An Infinite Polynomial Ring has generators $x_{*}, y_{*}, . . .$ , 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] $⟺$ 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 nonnegative integers as input and returns nonnegative integers, then c^P means to apply P to the variable indices occurring in c.

If you want to substitute variables you can use the standard polynomial methods, such as subs():

sage: R.<x,y> = InfinitePolynomialRing(QQ)
sage: f = x[1] + x[1]*x[2]*x[3]
sage: f.subs({x[1]: x[0]})
x_3*x_2*x_0 + x_0
sage: g = x[0] + x[1] + y[0]
sage: g.subs({x[0]: y[0]})
x_1 + 2*y_0

class sage.rings.polynomial.infinite_polynomial_element.InfinitePolynomial(A, p)[source]¶

Bases: CommutativePolynomial

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[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

constant_coefficient()[source]¶

Return the constant coefficient of this multivariate polynomial.

EXAMPLES:

sage: R.<x, y> = InfinitePolynomialRing(QQ)
sage: f = 3*x[3]^2 - 2*x[2]*y[2] + 5
sage: f.constant_coefficient()
5
sage: f = 3*x[3]^2
sage: f.constant_coefficient()
0

degree(x=None, std_grading=False)[source]¶

Return the degree of self in x, where x must be one of the generators for the parent of self.

INPUT:

x – a generator of the parent of self. If x is not specified (or is None), return the total degree, which is the maximum degree of any monomial. Note that a weighted term ordering alters the grading of the generators of the ring; see the tests below. To avoid this behavior, set the optional argument std_grading=True.

OUTPUT: integer

EXAMPLES:

sage: R.<x, y> = InfinitePolynomialRing(QQ)
sage: p = x[3]*x[2]^2*y[5]^3 + 1
sage: p.degree()
6
sage: p.degree(y[5])
3
sage: p.degree(y[3])
0

degrees()[source]¶

Return an index element corresponding to the maximal degree of each variable in this polynomial.

EXAMPLES:

sage: Z.<z> = InfinitePolynomialRing(QQ)
sage: f = 2*z[2]*z[3] + 3*z[1]^2*z[5]^4
sage: f.degrees()
{B[1]: 2, B[2]: 1, B[3]: 1, B[5]: 4}

sage: X.<x, y> = InfinitePolynomialRing(QQ, implementation="sparse")
sage: g = 2*x[0]*x[2] + 3*x[1]^2*y[1]^4
sage: g.degrees()
{B[(0, 0)]: 1, B[(0, 1)]: 2, B[(0, 2)]: 1, B[(1, 1)]: 4}

denominator()[source]¶

Return a denominator of self.

First, the lcm of the denominators of the entries of self is computed and returned. If this computation fails, the unit of the parent of self is returned.

Note that some subclasses may implement their own denominator function.

Warning

This is not the denominator of the rational function defined by self, which would always be 1 since self is a polynomial.

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: p = 2/3*x[1] + 4/9*x[2] - 2*x[1]*x[3]
sage: d = p.denominator(); d
9

exponents()[source]¶

Return the exponents of the monomials appearing in this polynomial.

EXAMPLES:

sage: Z.<z> = InfinitePolynomialRing(QQ)
sage: f = 2*z[2]*z[3] + 3*z[1]^2*z[5]
sage: f.exponents()
[2*B[1] + B[5], B[2] + B[3]]

sage: X.<x, y> = InfinitePolynomialRing(QQ, implementation="sparse")
sage: g = 2*x[0]*x[2] + 3*x[1]^2*y[1]
sage: g.exponents()  # random
[B[(0, 0)] + B[(0, 2)], 2*B[(0, 1)] + B[(1, 1)]]

factor(proof=None)[source]¶

Return the factorization of this polynomial.

INPUT:

proof – ignored

EXAMPLES:

sage: R.<x> = InfinitePolynomialRing(QQbar)
sage: factor(x[3]^2 - x[1]^2)
(x_3 - x_1) * (x_3 + x_1)

footprint()[source]¶

Leading exponents sorted by index and generator.

OUTPUT: D; 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[30]*y[1]^3*x[1]^2 + 2*x[10]*y[30]
sage: sorted(p.footprint().items())
[(1, [2, 3]), (30, [1, 0])]

is_constant()[source]¶

Return True if self is a constant and False otherwise.

EXAMPLES:

sage: R.<x> = InfinitePolynomialRing(QQbar)
sage: f = 3*x[3]^2 - 2*x[1] + 5
sage: f.is_constant()
False
sage: g = 10*f^0
sage: g.is_constant()
True

is_monomial()[source]¶

Return whether self is a monomial.

A monomial is a product of generators with coefficient 1. Use is_term() to allow an arbitrary coefficient.

EXAMPLES:

sage: R.<x, y> = InfinitePolynomialRing(QQ)
sage: p = 2*x[2]*y[2]
sage: p.is_monomial()
False
sage: (p/2).is_monomial()
True

is_nilpotent()[source]¶

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

EXAMPLES:

sage: R.<x> = InfinitePolynomialRing(QQbar)                                 # needs sage.rings.number_field
sage: (x[0] + x[1]).is_nilpotent()                                          # needs sage.rings.number_field
False
sage: R(0).is_nilpotent()                                                   # needs sage.rings.number_field
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_term()[source]¶

Return whether self is a term.

A term is a product of generators times a non-zero element of the base ring. Use is_monomial() to check whether the element is a term with coefficient 1.

EXAMPLES:

sage: R.<x, y> = InfinitePolynomialRing(QQ)
sage: p = 2*x[2]*y[2] + 5
sage: p.is_term()
False
sage: (p-5).is_term()
True

is_unit()[source]¶

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 Issue #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()[source]¶

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()[source]¶

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()[source]¶

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()[source]¶

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[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

monomial_coefficients(copy=None)[source]¶

Return underlying dictionary with keys the exponents and values the coefficients of this polynomial.

EXAMPLES:

sage: Z.<z> = InfinitePolynomialRing(QQ)
sage: f = 2*z[2]*z[3] + 3*z[1]^2*z[5]
sage: f.monomial_coefficients()
{2*B[1] + B[5]: 3, B[2] + B[3]: 2}

sage: X.<x, y> = InfinitePolynomialRing(QQ, implementation="sparse")
sage: g = 2*x[0]*x[2] + 3*x[1]^2*y[1]
sage: g.monomial_coefficients()
{B[(0, 0)] + B[(0, 2)]: 2, 2*B[(0, 1)] + B[(1, 1)]: 3}

monomials()[source]¶

Return the list of monomials in self.

The returned list is decreasingly ordered by the term ordering of self.parent().

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: p = x[1]^3 + x[2] - 2*x[1]*x[3]
sage: p.monomials()
[x_3*x_1, x_2, x_1^3]

sage: X.<x> = InfinitePolynomialRing(QQ, order='deglex')
sage: p = x[1]^3 + x[2] - 2*x[1]*x[3]
sage: p.monomials()
[x_1^3, x_3*x_1, x_2]

numerator()[source]¶

Return a numerator of self, computed as self * self.denominator().

Warning

This is not the numerator of the rational function defined by self, which would always be self since it is a polynomial.

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: p = 2/3*x[1] + 4/9*x[2] - 2*x[1]*x[3]
sage: num = p.numerator(); num
-18*x_3*x_1 + 4*x_2 + 6*x_1

polynomial()[source]¶

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)[source]¶

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 – boolean (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:

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 $T N^{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 monomial y[2]*x[3]^3 of p, then it interchanges the variable indices 1 and 2; this is not allowed in a symmetric reduction. However, reduction by y[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])                                               # needs sage.libs.singular
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)                                          # needs sage.libs.singular
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)                             # needs sage.libs.singular
: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()[source]¶

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()[source]¶

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[1]*y[100] + x[50]*y[1000]
sage: p.squeezed()
x_2*y_4 + x_1*y_3

stretch(k)[source]¶

Stretch self by a given factor.

INPUT:

k – integer

OUTPUT: replace $v_{n}$ with $v_{n \cdot k}$ for all generators $v_{*}$ 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

subs(fixed=None, **kwargs)[source]¶

Substitute variables in self.

INPUT:

fixed – (optional) dict with {variable: value} pairs
**kwargs – named parameters

OUTPUT: the resulting substitution

EXAMPLES:

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

Passing fixed={x[1]: x[0]}. Note that the keys may be given using the generators of the infinite polynomial ring or as a string:

sage: f.subs({x[1]: x[0]})
x_3*x_2*x_0 + x_0
sage: f.subs({'x_1': x[0]})
x_3*x_2*x_0 + x_0

Passing the variables as names parameters:

sage: f.subs(x_1=y[1])
x_3*x_2*y_1 + y_1
sage: f.subs(x_1=y[1], x_2=2)
2*x_3*y_1 + y_1

The substitution returns the original polynomial if you try to substitute a variable not present:

sage: g = x[0] + x[1]
sage: g.subs({y[0]: x[0]})
x_1 + x_0

The substitution can also handle matrices:

sage: # needs sage.modules
sage: M = matrix([[1,0], [0,2]])
sage: N = matrix([[0,3], [4,0]])
sage: g = x[0]^2 + 3*x[1]
sage: g.subs({'x_0': M})
[3*x_1 + 1         0]
[        0 3*x_1 + 4]
sage: g.subs({x[0]: M, x[1]: N})
[ 1  9]
[12  4]

If you pass both fixed and kwargs, any conflicts will defer to fixed:

sage: R.<x,y> = InfinitePolynomialRing(QQ)
sage: f = x[0]
sage: f.subs({x[0]: 1})
1
sage: f.subs(x_0=5)
5
sage: f.subs({x[0]: 1}, x_0=5)
1

symmetric_cancellation_order(other)[source]¶

Comparison of leading terms by Symmetric Cancellation Order, $<_{s c}$ .

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 to other in the monomial ordering of the Infinite Polynomial Ring
sigma is a permutation witnessing self $<_{s c}$ other (resp. self $>_{s c}$ 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 \leq 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[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()[source]¶

The tail of self (this is self 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()[source]¶

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

class sage.rings.polynomial.infinite_polynomial_element.InfinitePolynomial_dense(A, p)[source]¶

Bases: InfinitePolynomial

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.

coefficient(monomial)[source]¶

Return the coefficient of a monomial in self.

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

gcd(x)[source]¶

Compute 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

monomial_coefficient(mon)[source]¶

Return the base ring element that is the coefficient of mon in self.

This function contrasts with the function coefficient(), which returns the coefficient of a monomial viewing this polynomial in a polynomial ring over a base ring having fewer variables.

INPUT:

mon – a monomial in the parent of self

OUTPUT: coefficient in base ring