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[3]
sage: b = y[4]
sage: a
x3
sage: b
y4
sage: c = a*b+a^3-2*b^4
sage: c
-2*y4^4 + y4*x3 + x3^3

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)
-2 y_{4}^{4} + y_{4} x_{3} + x_{3}^{3}

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
-2*y5^4 + y5*x2 + x2^3

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, is_good_poly=False)

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). But a direct construction is possible as well.

INPUT:

  • A, an Infinite Polynomial Ring
  • p, which is either an Infinite Polynomial, a classical polynomial, a string, or anything else that can be interpreted in A.

If the optional parameter is_good_poly is given, then it is assumed that p is a classical polynomial that can be interpreted in A. Otherwise, the input is checked.

EXAMPLES:

sage: from sage.rings.polynomial.infinite_polynomial_element import InfinitePolynomial
sage: X.<x> = InfinitePolynomialRing(QQ)
sage: a = InfinitePolynomial(X, '(x1+x2)^2')
sage: a
x2^2 + 2*x2*x1 + x1^2
sage: p = a.polynomial()
sage: b = InfinitePolynomial(X, p)
sage: a==b
True
sage: InfinitePolynomial(X, int(1))
1
sage: InfinitePolynomial(X, 1)
1
sage: Y.<x,y> = InfinitePolynomialRing(GF(2), implementation='sparse')
sage: InfinitePolynomial(Y, a)
x2^2 + x1^2

If it is sure that p is a polynomial that fits well to X then the optional parameter is_good_poly can be used to speed up the element creation. However, this option should be used with care:

sage: R.<z0> = QQ[]
sage: InfinitePolynomial(Y, z0, is_good_poly=True)
z0

The preceding answer means that it was assumed that z0 fits into an Infinite Polynomial Ring generated by x and y – and in the sparse implementation of Infinite Polynomial Rings this is not tested. In the default implementation, it is somehow indirectly tested: The dense implementation of Infinite Polynomial Rings has an underlying ring, and if is_good_poly is granted, then that underlying ring will not be changed, resulting in a traceback.

sage: InfinitePolynomial(X, z0, is_good_poly=True)
...
TypeError: not a constant polynomial
sage: S.<x4> = QQ[]
sage: X.polynomial_ring()
Multivariate Polynomial Ring in x2, x1, x0 over Rational Field
sage: InfinitePolynomial(X, x4, is_good_poly=True)
...
TypeError: not a constant polynomial

Without the optional parameter, the underlying ring is appropriately changed:

sage: InfinitePolynomial(X, x4)
x4
sage: X.polynomial_ring()
Multivariate Polynomial Ring in x4, x3, x2, x1, x0 over Rational Field
class sage.rings.polynomial.infinite_polynomial_element.InfinitePolynomial_dense(A, p, is_good_poly=False)

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

INPUT:

  • X, an Infinite Polynomial Ring in dense implementation
  • p, which is either an Infinite Polynomial, a classical polynomial, a string, or anything else that can be interpreted in X.

If the optional parameter is_good_poly is given, then it is assumed that p is a classical polynomial that can be interpreted in X. Otherwise, the input is checked.

This class inherits from InfinitePolynomial_sparse. See there for a description of the methods.

__call__(*args, **kwargs)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: a = x[0] + x[1]
sage: a(x0=2,x1=x[1])
x1 + 2
sage: _.parent()
Infinite polynomial ring in x over Rational Field
sage: a(x1=3)
x0 + 3
sage: _.parent()
Infinite polynomial ring in x over Rational Field

sage: a(x1=x[100])
x100 + x0
__cmp__(x)
__init__(A, p, is_good_poly=False)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: a = x[1] + x[2]
sage: a == loads(dumps(a)) 
True
__pow__(n)

Exponentiation by an integer, or action by a callable object

NOTE:

The callable object must accept non-negative integers as input
and return non-negative integers. Typical use case is a permutation,
that will result in the corresponding permutation of variables.

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: x[10]^3
x10^3
sage: p = x[10]*y[2]+2*x[1]*y[3]
sage: P = Permutation(((1,2),(3,4,5)))
sage: p^P
2*y4*x2 + y1*x10
_add_(x)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x[1] + x[2]
x2 + x1
_div_(x)

Division of Infinite Polynomials. Note that the divisor must be scalar – Infinite Fraction Fields are not implemented yet.

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x[0]/2
1/2*x0
sage: x[0]/x[0]
...
NotImplementedError: Fraction Fields of Infinite Polynomial Rings are not implemented
_mul_(x)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x[2]*x[1]
x2*x1
_sub_(x)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x[2] - x[1]
x2 - x1
class sage.rings.polynomial.infinite_polynomial_element.InfinitePolynomial_sparse(A, p, is_good_poly=False)

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

INPUT:

  • A, an Infinite Polynomial Ring in sparse implementation
  • p, which is either an Infinite Polynomial, a classical polynomial, a string, or anything else that can be interpreted in A.

If the optional parameter is_good_poly is given, then it is assumed that p is a classical polynomial that can be interpreted in A. Otherwise, the input is checked.

__call__(*args, **kwargs)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ,implementation='sparse')
sage: a = x[0] + x[1]
sage: a(x0=2,x1=x[1])
x1 + 2
sage: _.parent()
Infinite polynomial ring in x over Rational Field
sage: a(x1=3)
x0 + 3
sage: _.parent()
Infinite polynomial ring in x over Rational Field

sage: a(x1=x[100])
x100 + x0
__cmp__(x)

Comparison of Infinite Polynomials

NOTE:

Let x and y are generators of the parent of self. We only consider monomial orderings in which x[m] < y[n] iff x appears earlier in the list of generators than y, or

x==y and m<n

Under this restriction, the monomial ordering can be ‘lex’ (default) or ‘deglex’.

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: a = x[10]^3
sage: b = x[1] + x[2]
sage: c = x[1] + x[2]
sage: d = y[1] + x[2]
sage: a == a
True
sage: b == c
True
sage: a == b
False
sage: c<d
True
__getattr__(s)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: latex(x[3]*x[2]^2) # indirect doctest
x_{3} x_{2}^{2}
__hash__()

Returns the hash of this element which is just the hash of the underlying finite polynomial.

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: a = x[0] + x[1]
sage: hash(a)
6447839315714024659   # 64-bit
233743571             # 32-bit
sage: hash(a._p)
6447839315714024659   # 64-bit
233743571             # 32-bit
__init__(A, p, is_good_poly=False)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: a = x[1] + x[2]
sage: a == loads(dumps(a)) 
True
__pow__(n)

Exponentiation by an integer, or action by a callable object

NOTE:

The callable object must accept non-negative integers as input
and return non-negative integers. Typical use case is a permutation,
that will result in the corresponding permutation of variables.

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: x[10]^3
x10^3
sage: p = x[10]*y[2]+2*x[1]*y[3]
sage: P = Permutation(((1,2),(3,4,5)))
sage: p^P
2*y4*x2 + y1*x10
__repr__()

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: str(x[1] + x[2])  # indirect doctest
'x2 + x1'
__weakref__
list of weak references to the object (if defined)
_add_(x)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x[1] + x[2]
x2 + x1
_div_(x)

Division of Infinite Polynomials. Note that the divisor must be scalar – Infinite Fraction Fields are not implemented yet.

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x[0]/2
1/2*x0
sage: x[0]/x[0]
...
NotImplementedError: Fraction Fields of Infinite Polynomial Rings are not implemented
_mul_(x)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x[2]*x[1]
x2*x1
_sub_(x)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x[2] - x[1]
x2 - x1
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*x1
sage: a.coefficient(x[1])
2*x0 + 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 in increasing order sorted by generator names

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: p.footprint()
{10: [1, 0], 30: [0, 1]}
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()
2
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()
y30*x10
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()
2*y30*x10
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[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
y1*x2 + 3*y0
sage: p.polynomial()
y1*x2 + 3*y0
sage: p.polynomial().parent()
Multivariate Polynomial Ring in y2, y1, y0, x2, x1, x0 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:

  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.

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[1]*x[3]
sage: p.reduce([y[2]^2*y[1]])
y3*y1^2 + y1*x3

The preceding is correct, since any permutation that turns y[2]^2*y[1] into a factor of y[1]^2*y[3] interchanges the variable indices 1 and 2 – which is not allowed. However, reduction by y[1]^2*y[2] works, since one can change variable index 1 into 2 and 2 into 3:

sage: p.reduce([y[1]^2*y[2]])
y1*x3

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 = (x[2])*X
sage: p.reduce(I)
y3*y1^2 + y1*x3
sage: p.reduce(I, tailreduce=True)
y3*y1^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[3]:>
>
y4*x1 + y2^2 + x1^2

The output ‘T[3]’ means that tail reduction is performed on a polynomial with three terms. ‘:’ means that there was one reduction of the leading monomial. At ‘>’, one round of the reduction process is finished.

ring()

The ring which self belongs to. This is the same as self.parent().

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ,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 Rational Field
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()
y4*x2 + y3*x1
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)
x4 + x2 + x0       

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: a = x[0] + x[1] + y[0]*y[1]; a
y1*y0 + x1 + x0
sage: a.stretch(2)
y2*y0 + x2 + x0

TESTS:

sage: X.<x> = InfinitePolynomialRing(QQ, implementation='sparse')
sage: a = x[2] + x[3]
sage: a.stretch(2000)
x6000 + x4000
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], y1)
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()
3*y1^3*x10*x1^2
variables()

Return the variables occurring in self (list 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()
[x3, x2, x1]
sage: x[1].variables()
[x1]
sage: X(1).variables()
[]

Previous topic

Infinite Polynomial Rings

Next topic

Educational Versions of Groebner Basis Algorithms.

This Page