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, 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.

TESTS:

We test whether coercion works, even in complicated cases in which finite polynomial rings are merged with infinite polynomial rings:

sage: A.<a> = InfinitePolynomialRing(ZZ,implementation='sparse',order='degrevlex')
sage: B.<b_2,b_1> = A[]
sage: C.<b,c> = InfinitePolynomialRing(B,order='degrevlex')
sage: C
Infinite polynomial ring in b, c over Infinite polynomial ring in a over Integer Ring
sage: 1/2*b_1*a[4]+c[3]
1/2*a_4*b_1 + c_3

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, which is 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)
...
TypeError

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:

sage: Y.<alpha,beta> = InfinitePolynomialRing(GF(2), implementation='sparse')
sage: a = (alpha_1+alpha_2)^2
sage: InfinitePolynomial(Y, a)
alpha_1^2 + 2*alpha_1*alpha_2 + alpha_2^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 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)¶

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 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[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], 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])]

TESTS:

This is a test whether it also works when the underlying polynomial ring is not implemented in libsingular:

sage: X.<x> = InfinitePolynomialRing(ZZ)
sage: Y.<y,z> = X[]
sage: Z.<a> = InfinitePolynomialRing(Y)
sage: Z
Infinite polynomial ring in a over Multivariate Polynomial Ring in y, z over Infinite polynomial ring in x over Integer Ring
sage: type(Z._P)
<class 'sage.rings.polynomial.multi_polynomial_ring.MPolynomialRing_polydict'>
sage: p = a[12]^3*a[2]^7*a[4] + a[4]*a[2]
sage: sorted(p.footprint().items())
[(2, [7]), (4, [1]), (12, [3])]

is_unit()¶

Answers whether self is a unit

EXAMPLES:

sage: R1.<x,y> = InfinitePolynomialRing(ZZ)
sage: R2.<x,y> = InfinitePolynomialRing(QQ)
sage: p = 1 + x[2]
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

lc(*args, **kwds)¶

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(*args, **kwds)¶

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(*args, **kwds)¶

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(*args, **kwds)¶

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

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)

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.

INPUT:

I – a SymmetricIdeal or a list of Infinite Polynomials
Sometimes it is useful to reduce not only the leading term of $p$ . This tail reduction is performed if the optional parameter tailreduce is True.
If the optional parameter report is not None, some information on the progress of computation is given, since reduction of huge polynomials may be expensive.

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

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

TESTS:

The following would hardly work in a dense implementation, because an underlying polynomial ring with 6001 variables would be created. This is avoided in the sparse implementation:

sage: X.<x> = InfinitePolynomialRing(QQ, implementation='sparse')
sage: a = x[2] + x[3]
sage: a.stretch(2000)
x_6000 + x_4000

symmetric_cancellation_order(other)¶

Comparison of leading terms by Symmetric Cancellation Order, $<_{sc}$

INPUT:

self, other – two Infinite Polynomials

ASSUMPTION:

Both Infintie 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[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 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(*args, **kwds)¶

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

Elements of Infinite Polynomial Rings¶

Previous topic

Next topic

This Page

Navigation

Elements of Infinite Polynomial Rings¶

Previous topic

Next topic

This Page

Quick search

Navigation