Infinite Polynomial Rings

By Infinite Polynomial Rings, we mean polynomial rings in a countably infinite number of variables. The implementation consists of a wrapper around the current finite polynomial rings in Sage.

AUTHORS:

An Infinite Polynomial Ring has finitely many generators x_\ast, y_\ast,... and infinitely many variables of the form x_0, x_1, x_2, ..., y_0, y_1, y_2,...,.... We refer to the natural number n as the index of the variable x_n.

INPUT:

  • R, the base ring, which must in fact be a field
  • names, a list of generator names. Generator names must be pairwise different. We only allow generator names that are single characters.
  • order (optional string). The default order is 'lex' (lexicographic). 'deglex' is degree lexicographic, and 'degrevlex' (degree reverse lexicographic) is possible but discouraged.

Each generator x produces an infinite sequence of variables x[1], x[2], ... which are printed on screen as x1, x2, ... and are latex typeset as x_{1}, x_{2}. Then, the Infinite Polynomial Ring is formed by polynomials in these variables.

By default, the monomials are ordered lexicographically. Alternatively, degree (reverse) lexicographic ordering is possible as well. However, we do not guarantee that the computation of Groebner bases will terminate in this case.

In either case, the variables of a Infinite Polynomial Ring X are ordered according to the following rule:

X.gen(i)[m] < X.gen(j)[n] if and only if i<j or (i==j and m<n)

We provide a ‘dense’ and a ‘sparse’ implementation. In the dense implementation, the Infinite Polynomial Ring carries a finite polynomial ring that comprises all variables up to the maximal index that has been used so far. This is potentially a very big ring and may also comprise many variables that are not used.

In the sparse implementation, we try to keep the underlying finite polynomial rings small, using only those variables that are really needed. By default, we use the dense implementation, since it usually is much faster.

We provide coercion from an Infinite Polynomial Ring X over a field F_X to an Infinite Polynomial ring Y over a field F_Y (regardless of dense or sparse implementation and of monomial ordering) if and only if there is a coercion from F_X to F_Y, and the set of generator names of X is a subset of the set of generator names of Y. The coercion map is name preserving. We also allow coercion from a classical polynomial ring to X if base rings and variable names fit.

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ, implementation='sparse')
sage: A.<a,b> = InfinitePolynomialRing(QQ, order='deglex')

sage: f = x[5] + 2; f
x5 + 2
sage: g = 3*y[1]; g
3*y1
sage: g._p.parent()
Univariate Polynomial Ring in y1 over Rational Field

sage: f2 = a[5] + 2; f2
a5 + 2
sage: g2 = 3*b[1]; g2
3*b1
sage: A.polynomial_ring()
Multivariate Polynomial Ring in b5, b4, b3, b2, b1, b0, a5, a4, a3, a2, a1, a0 over Rational Field

Of course, we provide the usual polynomial arithmetic:

sage: f+g
3*y1 + x5 + 2
sage: p = x[10]^2*(f+g); p
3*y1*x10^2 + x10^2*x5 + 2*x10^2

There is a permutation action on the variables, by permuting positive variable indices:

sage: P = Permutation(((10,1)))
sage: p^P
3*y10*x1^2 + x5*x1^2 + 2*x1^2

Note that x_0^P = x_0, since the permutations only change positive variable indices.

We also implemented ideals of Infinite Polynomial Rings. Here, it is thoroughly assumed that the ideals are set-wise invariant under the permutation action. We therefore refer to these ideals as Symmetric Ideals. Symmetric Ideals are finitely generated modulo addition, multiplication by ring elements and permutation of variables, and (at least in the default case of a lexicographic order), one can compute Groebner bases:

sage: I = (x[1]*y[2])*X
sage: I.groebner_basis()
[y1*x2, y2*x1]
sage: J = A*(a[1]*b[2])
sage: J.groebner_basis()
[b1*a2, b2*a1]

For more details, see SymmetricIdeal.

class sage.rings.polynomial.infinite_polynomial_ring.InfinitePolynomialGen(parent, name)

This class provides the object which is responsible for returning variables in an infinite polynomial ring (implemented in __getitem__()).

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(RR)
sage: x
Generator for the x's in Infinite polynomial ring in x, y over Real Field with 53 bits of precision
sage: x[5]
x5
sage: x == loads(dumps(x))
True 
__cmp__(other)

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: from sage.rings.polynomial.infinite_polynomial_ring import InfinitePolynomialGen
sage: x2 = InfinitePolynomialGen(X, 'x')
sage: x2 == x
True
__getitem__()

Returns the the variable x[i] where x is this sage.rings.polynomial.infinite_polynomial_ring.InfinitePolynomialGen, and i is a non-negative integer.

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x[1]
x1
__init__(parent, name)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: loads(dumps(x))
Generator for the x's in Infinite polynomial ring in x over Rational Field
__repr__()

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: x
Generator for the x's in Infinite polynomial ring in x, y over Rational Field
__weakref__
list of weak references to the object (if defined)
_latex_()

EXAMPLES:

sage: from sage.misc.latex import latex
sage: X.<x> = InfinitePolynomialRing(QQ)
sage: latex(x)
x_{st}
sage: latex(x[3])
x_{3}
class sage.rings.polynomial.infinite_polynomial_ring.InfinitePolynomialRingFactory

A factory for creating infinite polynomial ring elements. It handles making sure that they are unique as well as handling pickling. For more details, see UniqueFactory and infinite_polynomial_ring.

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: X2.<x> = InfinitePolynomialRing(QQ)
sage: X is X2
True
sage: X3.<x> = InfinitePolynomialRing(QQ, implementation='sparse')
sage: X is X3
False

sage: X is loads(dumps(X))
True
__weakref__
list of weak references to the object (if defined)
create_key(R, names=('x', ), order='lex', implementation='dense')

Creates a key which uniquely defines the infinite polynomial ring.

TESTS:

sage: InfinitePolynomialRing.create_key(QQ)
(Rational Field, ('x',), 'lex', 'dense')
sage: InfinitePolynomialRing.create_key(QQ, 'y')
(Rational Field, 'y', 'lex', 'dense')
sage: InfinitePolynomialRing.create_key(QQ, names='y', order='deglex', implementation='sparse')
(Rational Field, 'y', 'deglex', 'sparse')
sage: InfinitePolynomialRing.create_key(QQ, names=['x','y'], implementation='dense')
(Rational Field, ('x', 'y'), 'lex', 'dense')
create_object(version, key)

Returns the infinite polynomial ring corresponding to the key key.

TESTS:

sage: InfinitePolynomialRing.create_object('1.0', (QQ, 'x', 'deglex', 'sparse'))
Infinite polynomial ring in x over Rational Field
class sage.rings.polynomial.infinite_polynomial_ring.InfinitePolynomialRing_dense(R, names, order)

Dense implementation of Infinite Polynomial Rings

Compared with InfinitePolynomialRing_sparse, from which this class inherits, it keeps a polynomial ring that comprises all elements that have been created so far.

__init__(R, names, order)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ, implementation='sparse')
sage: X == loads(dumps(X))
True
polynomial_ring()

Returns the underlying finite polynomial ring.

Note

This ring returned can change over time as more variables are used.

EXAMPLES:

sage: X.<x, y> = InfinitePolynomialRing(QQ)
sage: X.polynomial_ring()
Multivariate Polynomial Ring in y0, x0 over Rational Field
sage: a = y[3]
sage: X.polynomial_ring()
Multivariate Polynomial Ring in y3, y2, y1, y0, x3, x2, x1, x0 over Rational Field
class sage.rings.polynomial.infinite_polynomial_ring.InfinitePolynomialRing_sparse(R, names, order)

Sparse implementation of Infinite Polynomial Rings.

An Infinite Polynomial Ring with generators x_\ast, y_\ast, ... over a field F is a free commutative F-algebra generated by x_0, x_1, x_2, ...,
y_0, y_1, y_2, ..., ... and is equipped with a permutation action on the generators, namely x_n^P = x_{P(n)}, y_{n}^P=y_{P(n)}, ... for any permutation P (note that variables of index zero are invariant under such permutation).

It is known that any permutation invariant ideal in an Infinite Polynomial Ring is finitely generated modulo the permutation action – see SymmetricIdeal for more details.

Usually, an instance of this class is created using InfinitePolynomialRing with the optional parameter implementation='sparse'. This takes care of uniqueness of parent structures. However, a direct construction is possible, in principle:

sage: X.<x,y> = InfinitePolynomialRing(QQ, implementation='sparse')
sage: Y.<x,y> = InfinitePolynomialRing(QQ, implementation='sparse')
sage: X is Y
True
sage: from sage.rings.polynomial.infinite_polynomial_ring import InfinitePolynomialRing_sparse
sage: Z = InfinitePolynomialRing_sparse(QQ, ['x','y'], 'lex')
sage: Z == X
True
sage: Z is X
False

The last parameter (‘lex’ in the above example) can also be ‘deglex’ or ‘degrevlex’; this would result in an Infinite Polynomial Ring in degree lexicographic or degree reverse lexicographic order.

See infinite_polynomial_ring for more details.

__cmp__(x)

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: X2.<x> = InfinitePolynomialRing(QQ)      
sage: X3.<x> = InfinitePolynomialRing(QQ, order='deglex')      
sage: Y.<y> = InfinitePolynomialRing(QQ)
sage: Z.<z> = InfinitePolynomialRing(GF(5))
sage: X == X
True
sage: X == X2
True
sage: X == X3
False
sage: X == Y
False
sage: X == Z
False
__init__(R, names, order)

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)

Infinite Polynomial Rings are unique parent structures:

sage: X is loads(dumps(X))
True
sage: p=x[10]*y[2]^3+2*x[1]*y[3]
sage: p
2*y3*x1 + y2^3*x10

We define another Infinite Polynomial Ring with same generator names but a different order. These rings are different, but allow for coercion:

sage: Y.<x,y> = InfinitePolynomialRing(QQ, order='deglex', implementation='dense')
sage: Y is X
False
sage: q=y[2]^3*x[10]+x[1]*y[3]*2
sage: q
y2^3*x10 + 2*y3*x1
sage: p==q
True
sage: X.gen(1)[2]*Y.gen(0)[1]
y2*x1

As usual, if there are coercion maps in both direction, the parent of the left operand is taken:

sage: (X.gen(1)[2]*Y.gen(0)[1]).parent() is X
True
__repr__()

EXAMPLES:

sage: InfinitePolynomialRing(QQ)
Infinite polynomial ring in x over Rational Field

sage: X.<x,y> = InfinitePolynomialRing(QQ, order='deglex'); X
Infinite polynomial ring in x, y over Rational Field
_coerce_map_from_()

Coerce things into self

EXAMPLES:

Here, we check to see that elements of a finitely generated polynomial ring with appropriate variable names coerce correctly into the Infinite Polynomial Ring:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: px0 = PolynomialRing(QQ,'x0').gen(0)
sage: px0 + x[0]
2*x0
sage: px0==x[0]
True

Note that any coercion will preserve variable names.

_element_constructor_(x)

EXAMPLES:

sage: X = InfinitePolynomialRing(QQ)
sage: a = X(2); a
2
sage: a.parent()
Infinite polynomial ring in x over Rational Field
sage: R=PolynomialRing(ZZ,['x3'])
sage: b = X(R.gen()); b
x3
sage: b.parent()
Infinite polynomial ring in x over Rational Field
sage: X('(x1^2+2/3*x4)*(x2+x5)')
2/3*x5*x4 + x5*x1^2 + 2/3*x4*x2 + x2*x1^2
_ideal_class_()
Return SymmetricIdeals (see there for further details).
_latex_()

EXAMPLES:

sage: from sage.misc.latex import latex
sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: latex(X)
\Bold{Q}[x_{st}, y_{st}]
characteristic()

Return the characteristic of the base field.

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(GF(25,'a'))
sage: X
Infinite polynomial ring in x, y over Finite Field in a of size 5^2
sage: X.characteristic()
5
gen()

Returns the i^{th} ‘generator’ (see the description in ngens()) of this infinite polynomial ring.

EXAMPLES:

sage: X = InfinitePolynomialRing(QQ)
sage: x = X.gen()
sage: x[1]
x1
sage: X.gen() is X.gen(0)
True
sage: XX = InfinitePolynomialRing(GF(5))
sage: XX.gen(0) is XX.gen()
True
ngens()

Returns the number of generators for this ring. Since there are countably infinitely many variables in this polynomial ring, by ‘generators’ we mean the number of infinite families of variables. See infinite_polynomial_ring for more details.

EXAMPLES:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: X.ngens()
1

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: X.ngens()
2
varname_cmp(x, y)

Comparison of two variable names

INPUT:

  • x,y should both be strings of the form a+str(n), where a is a single character appearing in the list of generator names, and n is an integer

RETURN:

-1,0,1 if x<y, x==y, x>y, respectively, where the order is defined as follows: x<y \iff the letter x[0] is earlier in the list of generator names of self than y[0], or (x[0]==y[0] and int(x[1:])<int(y[1:]))

EXAMPLES:

sage: X.<x,y> = InfinitePolynomialRing(QQ)
sage: X.varname_cmp('x1','y10')
-1
sage: X.varname_cmp('y1','x10')
1
sage: X.varname_cmp('y1','y10')
-1

Previous topic

Symmetric Reduction of Infinite Polynomials

Next topic

Elements of Infinite Polynomial Rings

This Page