Univariate Polynomial Rings#

Sage implements sparse and dense polynomials over commutative and non-commutative rings. In the non-commutative case, the polynomial variable commutes with the elements of the base ring.

AUTHOR:

William Stein
Kiran Kedlaya (2006-02-13): added macaulay2 option
Martin Albrecht (2006-08-25): removed it again as it isn’t needed anymore
Simon King (2011-05): Dense and sparse polynomial rings must not be equal.
Simon King (2011-10): Choice of categories for polynomial rings.

EXAMPLES:

sage: z = QQ['z'].0
sage: (z^3 + z - 1)^3
z^9 + 3*z^7 - 3*z^6 + 3*z^5 - 6*z^4 + 4*z^3 - 3*z^2 + 3*z - 1

Saving and loading of polynomial rings works:

sage: loads(dumps(QQ['x'])) == QQ['x']
True
sage: k = PolynomialRing(QQ['x'],'y'); loads(dumps(k))==k
True
sage: k = PolynomialRing(ZZ,'y'); loads(dumps(k)) == k
True
sage: k = PolynomialRing(ZZ,'y', sparse=True); loads(dumps(k))
Sparse Univariate Polynomial Ring in y over Integer Ring

Rings with different variable names are not equal; in fact, by github issue #9944, polynomial rings are equal if and only if they are identical (which should be the case for all parent structures in Sage):

sage: QQ['y'] != QQ['x']
True
sage: QQ['y'] != QQ['z']
True

We create a polynomial ring over a quaternion algebra:

sage: # needs sage.combinat sage.modules
sage: A.<i,j,k> = QuaternionAlgebra(QQ, -1,-1)
sage: R.<w> = PolynomialRing(A, sparse=True)
sage: f = w^3 + (i+j)*w + 1
sage: f
w^3 + (i + j)*w + 1
sage: f^2
w^6 + (2*i + 2*j)*w^4 + 2*w^3 - 2*w^2 + (2*i + 2*j)*w + 1
sage: f = w + i ; g = w + j
sage: f * g
w^2 + (i + j)*w + k
sage: g * f
w^2 + (i + j)*w - k

github issue #9944 introduced some changes related with coercion. Previously, a dense and a sparse polynomial ring with the same variable name over the same base ring evaluated equal, but of course they were not identical. Coercion maps are cached - but if a coercion to a dense ring is requested and a coercion to a sparse ring is returned instead (since the cache keys are equal!), all hell breaks loose.

Therefore, the coercion between rings of sparse and dense polynomials works as follows:

sage: R.<x> = PolynomialRing(QQ, sparse=True)
sage: S.<x> = QQ[]
sage: S == R
False
sage: S.has_coerce_map_from(R)
True
sage: R.has_coerce_map_from(S)
False
sage: (R.0 + S.0).parent()
Univariate Polynomial Ring in x over Rational Field
sage: (S.0 + R.0).parent()
Univariate Polynomial Ring in x over Rational Field

It may be that one has rings of dense or sparse polynomials over different base rings. In that situation, coercion works by means of the pushout() formalism:

sage: R.<x> = PolynomialRing(GF(5), sparse=True)
sage: S.<x> = PolynomialRing(ZZ)
sage: R.has_coerce_map_from(S)
False
sage: S.has_coerce_map_from(R)
False
sage: S.0 + R.0
2*x
sage: (S.0 + R.0).parent()
Univariate Polynomial Ring in x over Finite Field of size 5
sage: (S.0 + R.0).parent().is_sparse()
False

Similarly, there is a coercion from the (non-default) NTL implementation for univariate polynomials over the integers to the default FLINT implementation, but not vice versa:

sage: R.<x> = PolynomialRing(ZZ, implementation='NTL')                              # needs sage.libs.ntl
sage: S.<x> = PolynomialRing(ZZ, implementation='FLINT')
sage: (S.0 + R.0).parent() is S                                                     # needs sage.libs.flint sage.libs.ntl
True
sage: (R.0 + S.0).parent() is S                                                     # needs sage.libs.flint sage.libs.ntl
True

class sage.rings.polynomial.polynomial_ring.PolynomialRing_cdvf(base_ring, name=None, sparse=False, implementation=None, element_class=None, category=None)#

Bases: PolynomialRing_cdvr, PolynomialRing_field

A class for polynomial ring over complete discrete valuation fields

class sage.rings.polynomial.polynomial_ring.PolynomialRing_cdvr(base_ring, name=None, sparse=False, implementation=None, element_class=None, category=None)#

Bases: PolynomialRing_integral_domain

A class for polynomial ring over complete discrete valuation rings

class sage.rings.polynomial.polynomial_ring.PolynomialRing_commutative(base_ring, name=None, sparse=False, implementation=None, element_class=None, category=None)#

Bases: PolynomialRing_general

Univariate polynomial ring over a commutative ring.

quotient_by_principal_ideal(f, names=None, **kwds)#

Return the quotient of this polynomial ring by the principal ideal (generated by) \(f\).

INPUT:

f - either a polynomial in self, or a principal ideal of self.
further named arguments that are passed to the quotient constructor.

EXAMPLES:

sage: R.<x> = QQ[]
sage: I = (x^2 - 1) * R
sage: R.quotient_by_principal_ideal(I)                                      # needs sage.libs.pari
Univariate Quotient Polynomial Ring in xbar
 over Rational Field with modulus x^2 - 1

The same example, using the polynomial instead of the ideal, and customizing the variable name:

sage: R.<x> = QQ[]
sage: R.quotient_by_principal_ideal(x^2 - 1, names=('foo',))                # needs sage.libs.pari
Univariate Quotient Polynomial Ring in foo
 over Rational Field with modulus x^2 - 1

weyl_algebra()#

Return the Weyl algebra generated from self.

EXAMPLES:

sage: R = QQ['x']
sage: W = R.weyl_algebra(); W                                               # needs sage.modules
Differential Weyl algebra of polynomials in x over Rational Field
sage: W.polynomial_ring() == R                                              # needs sage.modules
True

class sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_finite_field(base_ring, name='x', element_class=None, implementation=None)#

Bases: PolynomialRing_field

Univariate polynomial ring over a finite field.

EXAMPLES:

sage: R = PolynomialRing(GF(27, 'a'), 'x')                                      # needs sage.rings.finite_rings
sage: type(R)                                                                   # needs sage.rings.finite_rings
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_finite_field_with_category'>

irreducible_element(n, algorithm=None)#

Construct a monic irreducible polynomial of degree \(n\).

INPUT:

n – integer: degree of the polynomial to construct
algorithm – string: algorithm to use, or None
- 'random' or None: try random polynomials until an irreducible one is found.
- 'first_lexicographic': try polynomials in lexicographic order until an irreducible one is found.

OUTPUT:

A monic irreducible polynomial of degree \(n\) in self.

EXAMPLES:

sage: # needs sage.modules sage.rings.finite_rings
sage: f = GF(5^3, 'a')['x'].irreducible_element(2)
sage: f.degree()
2
sage: f.is_irreducible()
True
sage: R = GF(19)['x']
sage: R.irreducible_element(21, algorithm="first_lexicographic")
x^21 + x + 5
sage: R = GF(5**2, 'a')['x']
sage: R.irreducible_element(17, algorithm="first_lexicographic")
x^17 + a*x + 4*a + 3

AUTHORS:

Peter Bruin (June 2013)
Jean-Pierre Flori (May 2014)

class sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_mod_n(base_ring, name=None, element_class=None, implementation=None, category=None)#

Bases: PolynomialRing_commutative

modulus()#

EXAMPLES:

sage: R.<x> = Zmod(15)[]
sage: R.modulus()
15

residue_field(ideal, names=None)#

Return the residue finite field at the given ideal.

EXAMPLES:

sage: # needs sage.libs.ntl
sage: R.<t> = GF(2)[]
sage: k.<a> = R.residue_field(t^3 + t + 1); k
Residue field in a
 of Principal ideal (t^3 + t + 1) of Univariate Polynomial Ring in t
 over Finite Field of size 2 (using GF2X)
sage: k.list()
[0, a, a^2, a + 1, a^2 + a, a^2 + a + 1, a^2 + 1, 1]
sage: R.residue_field(t)
Residue field of Principal ideal (t) of Univariate Polynomial Ring in t
 over Finite Field of size 2 (using GF2X)
sage: P = R.irreducible_element(8) * R
sage: P
Principal ideal (t^8 + t^4 + t^3 + t^2 + 1) of Univariate Polynomial Ring in t
 over Finite Field of size 2 (using GF2X)
sage: k.<a> = R.residue_field(P); k
Residue field in a
 of Principal ideal (t^8 + t^4 + t^3 + t^2 + 1) of Univariate Polynomial Ring in t
 over Finite Field of size 2 (using GF2X)
sage: k.cardinality()
256

Non-maximal ideals are not accepted:

sage: # needs sage.libs.ntl
sage: R.residue_field(t^2 + 1)
Traceback (most recent call last):
...
ArithmeticError: ideal is not maximal
sage: R.residue_field(0)
Traceback (most recent call last):
...
ArithmeticError: ideal is not maximal
sage: R.residue_field(1)
Traceback (most recent call last):
...
ArithmeticError: ideal is not maximal

class sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_mod_p(base_ring, name='x', implementation=None, element_class=None, category=None)#

Bases: PolynomialRing_dense_finite_field, PolynomialRing_dense_mod_n, PolynomialRing_singular_repr

irreducible_element(n, algorithm=None)#

Construct a monic irreducible polynomial of degree \(n\).

INPUT:

n – integer: the degree of the polynomial to construct
algorithm – string: algorithm to use, or None. Currently available options are:
- 'adleman-lenstra': a variant of the Adleman–Lenstra algorithm as implemented in PARI.
- 'conway': look up the Conway polynomial of degree \(n\) over the field of \(p\) elements in the database; raise a RuntimeError if it is not found.
- 'ffprimroot': use the pari:ffprimroot function from PARI.
- 'first_lexicographic': return the lexicographically smallest irreducible polynomial of degree \(n\).
- 'minimal_weight': return an irreducible polynomial of degree \(n\) with minimal number of non-zero coefficients. Only implemented for \(p = 2\).
- 'primitive': return a polynomial \(f\) such that a root of \(f\) generates the multiplicative group of the finite field extension defined by \(f\). This uses the Conway polynomial if possible, otherwise it uses 'ffprimroot'.
- 'random': try random polynomials until an irreducible one is found.
If algorithm is None, use \(x - 1\) in degree 1. In degree > 1, the Conway polynomial is used if it is found in the database. Otherwise, the algorithm minimal_weight is used if \(p = 2\), and the algorithm 'adleman-lenstra' if \(p > 2\).

OUTPUT:

A monic irreducible polynomial of degree \(n\) in self.

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: GF(5)['x'].irreducible_element(2)
x^2 + 4*x + 2
sage: GF(5)['x'].irreducible_element(2, algorithm="adleman-lenstra")
x^2 + x + 1
sage: GF(5)['x'].irreducible_element(2, algorithm="primitive")
x^2 + 4*x + 2
sage: GF(5)['x'].irreducible_element(32, algorithm="first_lexicographic")
x^32 + 2
sage: GF(5)['x'].irreducible_element(32, algorithm="conway")
Traceback (most recent call last):
...
RuntimeError: requested Conway polynomial not in database.
sage: GF(5)['x'].irreducible_element(32, algorithm="primitive")
x^32 + ...

In characteristic 2:

sage: GF(2)['x'].irreducible_element(33)                                    # needs sage.rings.finite_rings
x^33 + x^13 + x^12 + x^11 + x^10 + x^8 + x^6 + x^3 + 1
sage: GF(2)['x'].irreducible_element(33, algorithm="minimal_weight")        # needs sage.rings.finite_rings
x^33 + x^10 + 1

In degree 1:

sage: GF(97)['x'].irreducible_element(1)                                    # needs sage.rings.finite_rings
x + 96
sage: GF(97)['x'].irreducible_element(1, algorithm="conway")                # needs sage.rings.finite_rings
x + 92
sage: GF(97)['x'].irreducible_element(1, algorithm="adleman-lenstra")       # needs sage.rings.finite_rings
x

AUTHORS:

Peter Bruin (June 2013)
Jeroen Demeyer (September 2014): add “ffprimroot” algorithm, see github issue #8373.

class sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_padic_field_capped_relative(base_ring, name=None, implementation=None, element_class=None, category=None)#: Bases: PolynomialRing_dense_padic_field_generic

class sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_padic_field_generic(base_ring, name=None, implementation=None, element_class=None, category=None)#

Bases: PolynomialRing_cdvf

A class for dense polynomial ring over p-adic fields

class sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_padic_ring_capped_absolute(base_ring, name=None, implementation=None, element_class=None, category=None)#: Bases: PolynomialRing_dense_padic_ring_generic

class sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_padic_ring_capped_relative(base_ring, name=None, implementation=None, element_class=None, category=None)#: Bases: PolynomialRing_dense_padic_ring_generic

class sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_padic_ring_fixed_mod(base_ring, name=None, implementation=None, element_class=None, category=None)#: Bases: PolynomialRing_dense_padic_ring_generic

class sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_padic_ring_generic(base_ring, name=None, implementation=None, element_class=None, category=None)#

Bases: PolynomialRing_cdvr

A class for dense polynomial ring over p-adic rings

class sage.rings.polynomial.polynomial_ring.PolynomialRing_field(base_ring, name='x', sparse=False, implementation=None, element_class=None, category=None)#

Bases: PolynomialRing_integral_domain, PrincipalIdealDomain

divided_difference(points, full_table=False)#

Return the Newton divided-difference coefficients of the Lagrange interpolation polynomial through points.

INPUT:

points – a list of pairs \((x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)\) of elements of the base ring of self, where \(x_i - x_j\) is invertible for \(i \neq j\). This method converts the \(x_i\) and \(y_i\) into the base ring of self.
full_table – boolean (default: False): If True, return the full divided-difference table. If False, only return entries along the main diagonal; these are the Newton divided-difference coefficients \(F_{i,i}\).

OUTPUT:

The Newton divided-difference coefficients of the \(n\)-th Lagrange interpolation polynomial \(P_n(x)\) that passes through the points in points (see lagrange_polynomial()). These are the coefficients \(F_{0,0}, F_{1,1}, \dots, F_{n,n}\) in the base ring of self such that

\[P_n(x) = \sum_{i=0}^n F_{i,i} \prod_{j=0}^{i-1} (x - x_j)\]

EXAMPLES:

Only return the divided-difference coefficients \(F_{i,i}\). This example is taken from Example 1, page 121 of [BF2005]:

sage: # needs sage.rings.real_mpfr
sage: points = [(1.0, 0.7651977), (1.3, 0.6200860), (1.6, 0.4554022),
....:           (1.9, 0.2818186), (2.2, 0.1103623)]
sage: R = PolynomialRing(RR, "x")
sage: R.divided_difference(points)
[0.765197700000000,
 -0.483705666666666,
 -0.108733888888889,
 0.0658783950617283,
 0.00182510288066044]

Now return the full divided-difference table:

sage: # needs sage.rings.real_mpfr
sage: points = [(1.0, 0.7651977), (1.3, 0.6200860), (1.6, 0.4554022),
....:           (1.9, 0.2818186), (2.2, 0.1103623)]
sage: R = PolynomialRing(RR, "x")
sage: R.divided_difference(points, full_table=True)
[[0.765197700000000],
 [0.620086000000000, -0.483705666666666],
 [0.455402200000000, -0.548946000000000, -0.108733888888889],
 [0.281818600000000, -0.578612000000000,
                    -0.0494433333333339, 0.0658783950617283],
 [0.110362300000000, -0.571520999999999, 0.0118183333333349,
                    0.0680685185185209, 0.00182510288066044]]

The following example is taken from Example 4.12, page 225 of [MF1999]:

sage: points = [(1, -3), (2, 0), (3, 15), (4, 48), (5, 105), (6, 192)]
sage: R = PolynomialRing(QQ, "x")
sage: R.divided_difference(points)
[-3, 3, 6, 1, 0, 0]
sage: R.divided_difference(points, full_table=True)
[[-3],
 [0, 3],
 [15, 15, 6],
 [48, 33, 9, 1],
 [105, 57, 12, 1, 0],
 [192, 87, 15, 1, 0, 0]]

fraction_field()#

Returns the fraction field of self.

EXAMPLES:

sage: R.<t> = GF(5)[]
sage: R.fraction_field()
Fraction Field of Univariate Polynomial Ring in t
 over Finite Field of size 5

lagrange_polynomial(points, algorithm='divided_difference', previous_row=None)#

Return the Lagrange interpolation polynomial through the given points.

INPUT:

points – a list of pairs \((x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)\) of elements of the base ring of self, where \(x_i - x_j\) is invertible for \(i \neq j\). This method converts the \(x_i\) and \(y_i\) into the base ring of self.
algorithm – (default: 'divided_difference'): one of the following:
- 'divided_difference': use the method of divided differences.
- 'neville': adapt Neville’s method as described on page 144 of [BF2005] to recursively generate the Lagrange interpolation polynomial. Neville’s method generates a table of approximating polynomials, where the last row of that table contains the \(n\)-th Lagrange interpolation polynomial. The adaptation implemented by this method is to only generate the last row of this table, instead of the full table itself. Generating the full table can be memory inefficient.
previous_row – (default: None): This option is only relevant if used with algorithm='neville'. If provided, this should be the last row of the table resulting from a previous use of Neville’s method. If such a row is passed, then points should consist of both previous and new interpolating points. Neville’s method will then use that last row and the interpolating points to generate a new row containing an interpolation polynomial for the new points.

OUTPUT:

The Lagrange interpolation polynomial through the points \((x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)\). This is the unique polynomial \(P_n\) of degree at most \(n\) in self satisfying \(P_n(x_i) = y_i\) for \(0 \le i \le n\).

EXAMPLES:

By default, we use the method of divided differences:

sage: R = PolynomialRing(QQ, 'x')
sage: f = R.lagrange_polynomial([(0,1), (2,2), (3,-2), (-4,9)]); f
-23/84*x^3 - 11/84*x^2 + 13/7*x + 1
sage: f(0)
1
sage: f(2)
2
sage: f(3)
-2
sage: f(-4)
9

sage: # needs sage.rings.finite_rings
sage: R = PolynomialRing(GF(2**3, 'a'), 'x')
sage: a = R.base_ring().gen()
sage: f = R.lagrange_polynomial([(a^2+a, a), (a, 1), (a^2, a^2+a+1)]); f
a^2*x^2 + a^2*x + a^2
sage: f(a^2 + a)
a
sage: f(a)
1
sage: f(a^2)
a^2 + a + 1

Now use a memory efficient version of Neville’s method:

sage: R = PolynomialRing(QQ, 'x')
sage: R.lagrange_polynomial([(0,1), (2,2), (3,-2), (-4,9)],
....:                       algorithm="neville")
[9,
-11/7*x + 19/7,
-17/42*x^2 - 83/42*x + 53/7,
-23/84*x^3 - 11/84*x^2 + 13/7*x + 1]

sage: # needs sage.rings.finite_rings
sage: R = PolynomialRing(GF(2**3, 'a'), 'x')
sage: a = R.base_ring().gen()
sage: R.lagrange_polynomial([(a^2+a, a), (a, 1), (a^2, a^2+a+1)],
....:                       algorithm="neville")
[a^2 + a + 1, x + a + 1, a^2*x^2 + a^2*x + a^2]

Repeated use of Neville’s method to get better Lagrange interpolation polynomials:

sage: R = PolynomialRing(QQ, 'x')
sage: p = R.lagrange_polynomial([(0,1), (2,2)], algorithm="neville")
sage: R.lagrange_polynomial([(0,1), (2,2), (3,-2), (-4,9)],
....:                       algorithm="neville", previous_row=p)[-1]
-23/84*x^3 - 11/84*x^2 + 13/7*x + 1

sage: # needs sage.rings.finite_rings
sage: R = PolynomialRing(GF(2**3, 'a'), 'x')
sage: a = R.base_ring().gen()
sage: p = R.lagrange_polynomial([(a^2+a, a), (a, 1)], algorithm="neville")
sage: R.lagrange_polynomial([(a^2+a, a), (a, 1), (a^2, a^2+a+1)],
....:                       algorithm="neville", previous_row=p)[-1]
a^2*x^2 + a^2*x + a^2

class sage.rings.polynomial.polynomial_ring.PolynomialRing_general(base_ring, name=None, sparse=False, implementation=None, element_class=None, category=None)#

Bases: Ring

Univariate polynomial ring over a ring.

base_extend(R)#

Return the base extension of this polynomial ring to \(R\).

EXAMPLES:

sage: # needs sage.rings.real_mpfr
sage: R.<x> = RR[]; R
Univariate Polynomial Ring in x over Real Field with 53 bits of precision
sage: R.base_extend(CC)
Univariate Polynomial Ring in x over Complex Field with 53 bits of precision
sage: R.base_extend(QQ)
Traceback (most recent call last):
...
TypeError: no such base extension
sage: R.change_ring(QQ)
Univariate Polynomial Ring in x over Rational Field

change_ring(R)#

Return the polynomial ring in the same variable as self over \(R\).

EXAMPLES:

sage: # needs sage.rings.finite_rings sage.rings.real_interval_field
sage: R.<ZZZ> = RealIntervalField()[]; R
Univariate Polynomial Ring in ZZZ over
 Real Interval Field with 53 bits of precision
sage: R.change_ring(GF(19^2, 'b'))
Univariate Polynomial Ring in ZZZ over Finite Field in b of size 19^2

change_var(var)#

Return the polynomial ring in variable var over the same base ring.

EXAMPLES:

sage: R.<x> = ZZ[]; R
Univariate Polynomial Ring in x over Integer Ring
sage: R.change_var('y')
Univariate Polynomial Ring in y over Integer Ring

characteristic()#

Return the characteristic of this polynomial ring, which is the same as that of its base ring.

EXAMPLES:

sage: # needs sage.rings.real_interval_field
sage: R.<ZZZ> = RealIntervalField()[]; R
Univariate Polynomial Ring in ZZZ over Real Interval Field with 53 bits of precision
sage: R.characteristic()
0
sage: S = R.change_ring(GF(19^2, 'b')); S                                   # needs sage.rings.finite_rings
Univariate Polynomial Ring in ZZZ over Finite Field in b of size 19^2
sage: S.characteristic()                                                    # needs sage.rings.finite_rings
19

completion(p=None, prec=20, extras=None)#

Return the completion of self with respect to the irreducible polynomial p.

Currently only implemented for p=self.gen() (the default), i.e. you can only complete \(R[x]\) with respect to \(x\), the result being a ring of power series in \(x\). The prec variable controls the precision used in the power series ring. If prec is \(\infty\), then this returns a LazyPowerSeriesRing.

EXAMPLES:

sage: P.<x> = PolynomialRing(QQ)
sage: P
Univariate Polynomial Ring in x over Rational Field
sage: PP = P.completion(x)
sage: PP
Power Series Ring in x over Rational Field
sage: f = 1 - x
sage: PP(f)
1 - x
sage: 1 / f
-1/(x - 1)
sage: g = 1 / PP(f); g
1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11
 + x^12 + x^13 + x^14 + x^15 + x^16 + x^17 + x^18 + x^19 + O(x^20)
sage: 1 / g
1 - x + O(x^20)

sage: # needs sage.combinat
sage: PP = P.completion(x, prec=oo); PP
Lazy Taylor Series Ring in x over Rational Field
sage: g = 1 / PP(f); g
1 + x + x^2 + O(x^3)
sage: 1 / g == f
True

construction()#: Return the construction functor.

cyclotomic_polynomial(n)#

Return the nth cyclotomic polynomial as a polynomial in this polynomial ring. For details of the implementation, see the documentation for sage.rings.polynomial.cyclotomic.cyclotomic_coeffs().

EXAMPLES:

sage: R = ZZ['x']
sage: R.cyclotomic_polynomial(8)
x^4 + 1
sage: R.cyclotomic_polynomial(12)
x^4 - x^2 + 1

sage: S = PolynomialRing(FiniteField(7), 'x')
sage: S.cyclotomic_polynomial(12)
x^4 + 6*x^2 + 1
sage: S.cyclotomic_polynomial(1)
x + 6

extend_variables(added_names, order='degrevlex')#

Return a multivariate polynomial ring with the same base ring but with added_names as additional variables.

EXAMPLES:

sage: R.<x> = ZZ[]; R
Univariate Polynomial Ring in x over Integer Ring
sage: R.extend_variables('y, z')
Multivariate Polynomial Ring in x, y, z over Integer Ring
sage: R.extend_variables(('y', 'z'))
Multivariate Polynomial Ring in x, y, z over Integer Ring

flattening_morphism()#

Return the flattening morphism of this polynomial ring

EXAMPLES:

sage: QQ['a','b']['x'].flattening_morphism()
Flattening morphism:
  From: Univariate Polynomial Ring in x over
        Multivariate Polynomial Ring in a, b over Rational Field
  To:   Multivariate Polynomial Ring in a, b, x over Rational Field

sage: QQ['x'].flattening_morphism()
Identity endomorphism of Univariate Polynomial Ring in x over Rational Field

gen(n=0)#

Return the indeterminate generator of this polynomial ring.

EXAMPLES:

sage: R.<abc> = Integers(8)[]; R
Univariate Polynomial Ring in abc over Ring of integers modulo 8
sage: t = R.gen(); t
abc
sage: t.is_gen()
True

An identical generator is always returned.

sage: t is R.gen()
True

gens_dict()#

Return a dictionary whose entries are {name:variable,...}, where name stands for the variable names of this object (as strings) and variable stands for the corresponding generators (as elements of this object).

EXAMPLES:

sage: R.<y,x,a42> = RR[]
sage: R.gens_dict()
{'a42': a42, 'x': x, 'y': y}

is_exact()#

EXAMPLES:

sage: class Foo:
....:     def __init__(self, x):
....:         self._x = x
....:     @cached_method
....:     def f(self):
....:         return self._x^2
sage: a = Foo(2)
sage: print(a.f.cache)
None
sage: a.f()
4
sage: a.f.cache
4

is_field(proof=True)#

Return False, since polynomial rings are never fields.

EXAMPLES:

sage: # needs sage.libs.ntl
sage: R.<z> = Integers(2)[]; R
Univariate Polynomial Ring in z over Ring of integers modulo 2 (using GF2X)
sage: R.is_field()
False

is_integral_domain(proof=True)#

EXAMPLES:

sage: ZZ['x'].is_integral_domain()
True
sage: Integers(8)['x'].is_integral_domain()
False

is_noetherian()#

is_sparse()#

Return True if elements of this polynomial ring have a sparse representation.

EXAMPLES:

sage: R.<z> = Integers(8)[]; R
Univariate Polynomial Ring in z over Ring of integers modulo 8
sage: R.is_sparse()
False
sage: R.<W> = PolynomialRing(QQ, sparse=True); R
Sparse Univariate Polynomial Ring in W over Rational Field
sage: R.is_sparse()
True

is_unique_factorization_domain(proof=True)#

EXAMPLES:

sage: ZZ['x'].is_unique_factorization_domain()
True
sage: Integers(8)['x'].is_unique_factorization_domain()
False

karatsuba_threshold()#

Return the Karatsuba threshold used for this ring by the method _mul_karatsuba() to fall back to the schoolbook algorithm.

EXAMPLES:

sage: K = QQ['x']
sage: K.karatsuba_threshold()
8
sage: K = QQ['x']['y']
sage: K.karatsuba_threshold()
0

krull_dimension()#

Return the Krull dimension of this polynomial ring, which is one more than the Krull dimension of the base ring.

EXAMPLES:

sage: R.<x> = QQ[]
sage: R.krull_dimension()
1

sage: # needs sage.rings.finite_rings
sage: R.<z> = GF(9, 'a')[]; R
Univariate Polynomial Ring in z over Finite Field in a of size 3^2
sage: R.krull_dimension()
1
sage: S.<t> = R[]
sage: S.krull_dimension()
2
sage: for n in range(10):
....:     S = PolynomialRing(S, 'w')
sage: S.krull_dimension()
12

monics(of_degree=None, max_degree=None)#

Return an iterator over the monic polynomials of specified degree.

INPUT: Pass exactly one of:

max_degree - an int; the iterator will generate all monic polynomials which have degree less than or equal to max_degree
of_degree - an int; the iterator will generate all monic polynomials which have degree of_degree

OUTPUT: an iterator

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: P = PolynomialRing(GF(4, 'a'), 'y')
sage: for p in P.monics(of_degree=2): print(p)
y^2
y^2 + a
y^2 + a + 1
y^2 + 1
y^2 + a*y
y^2 + a*y + a
y^2 + a*y + a + 1
y^2 + a*y + 1
y^2 + (a + 1)*y
y^2 + (a + 1)*y + a
y^2 + (a + 1)*y + a + 1
y^2 + (a + 1)*y + 1
y^2 + y
y^2 + y + a
y^2 + y + a + 1
y^2 + y + 1
sage: for p in P.monics(max_degree=1): print(p)
1
y
y + a
y + a + 1
y + 1
sage: for p in P.monics(max_degree=1, of_degree=3): print(p)
Traceback (most recent call last):
...
ValueError: you should pass exactly one of of_degree and max_degree

AUTHORS:

Joel B. Mohler

monomial(exponent)#

Return the monomial with the exponent.

INPUT:

exponent – nonnegative integer

EXAMPLES:

sage: R.<x> = PolynomialRing(ZZ)
sage: R.monomial(5)
x^5
sage: e=(10,)
sage: R.monomial(*e)
x^10
sage: m = R.monomial(100)
sage: R.monomial(m.degree()) == m
True

ngens()#

Return the number of generators of this polynomial ring, which is 1 since it is a univariate polynomial ring.

EXAMPLES:

sage: R.<z> = Integers(8)[]; R
Univariate Polynomial Ring in z over Ring of integers modulo 8
sage: R.ngens()
1

parameter()#

Return the generator of this polynomial ring.

This is the same as self.gen().

polynomials(of_degree=None, max_degree=None)#

Return an iterator over the polynomials of specified degree.

INPUT: Pass exactly one of:

max_degree - an int; the iterator will generate all polynomials which have degree less than or equal to max_degree
of_degree - an int; the iterator will generate all polynomials which have degree of_degree

OUTPUT: an iterator

EXAMPLES:

sage: P = PolynomialRing(GF(3), 'y')
sage: for p in P.polynomials(of_degree=2): print(p)
y^2
y^2 + 1
y^2 + 2
y^2 + y
y^2 + y + 1
y^2 + y + 2
y^2 + 2*y
y^2 + 2*y + 1
y^2 + 2*y + 2
2*y^2
2*y^2 + 1
2*y^2 + 2
2*y^2 + y
2*y^2 + y + 1
2*y^2 + y + 2
2*y^2 + 2*y
2*y^2 + 2*y + 1
2*y^2 + 2*y + 2
sage: for p in P.polynomials(max_degree=1): print(p)
0
1
2
y
y + 1
y + 2
2*y
2*y + 1
2*y + 2
sage: for p in P.polynomials(max_degree=1, of_degree=3): print(p)
Traceback (most recent call last):
...
ValueError: you should pass exactly one of of_degree and max_degree

AUTHORS:

Joel B. Mohler

random_element(degree=(-1, 2), *args, **kwds)#

Return a random polynomial of given degree or with given degree bounds.

INPUT:

degree - optional integer for fixing the degree or a tuple of minimum and maximum degrees. By default set to (-1,2).
*args, **kwds - Passed on to the random_element method for the base ring

EXAMPLES:

sage: R.<x> = ZZ[]
sage: f = R.random_element(10, 5, 10)
sage: f.degree()
10
sage: f.parent() is R
True
sage: all(a in range(5, 10) for a in f.coefficients())
True
sage: R.random_element(6).degree()
6

If a tuple of two integers is given for the degree argument, a degree is first uniformly chosen, then a polynomial of that degree is given:

sage: R.random_element(degree=(0, 8)).degree() in range(0, 9)
True
sage: found = [False]*9
sage: while not all(found):
....:     found[R.random_element(degree=(0, 8)).degree()] = True

Note that the zero polynomial has degree \(-1\), so if you want to consider it set the minimum degree to \(-1\):

sage: while R.random_element(degree=(-1,2), x=-1, y=1) != R.zero():
....:     pass

set_karatsuba_threshold(Karatsuba_threshold)#

Changes the default threshold for this ring in the method _mul_karatsuba() to fall back to the schoolbook algorithm.

Warning

This method may have a negative performance impact in polynomial arithmetic. So use it at your own risk.

EXAMPLES:

sage: K = QQ['x']
sage: K.karatsuba_threshold()
8
sage: K.set_karatsuba_threshold(0)
sage: K.karatsuba_threshold()
0

some_elements()#

Return a list of polynomials.

This is typically used for running generic tests.

EXAMPLES:

sage: R.<x> = QQ[]
sage: R.some_elements()
[x, 0, 1, 1/2, x^2 + 2*x + 1, x^3, x^2 - 1, x^2 + 1, 2*x^2 + 2]

variable_names_recursive(depth=+Infinity)#

Return the list of variable names of this ring and its base rings, as if it were a single multi-variate polynomial.

INPUT:

depth – an integer or Infinity.

OUTPUT:

A tuple of strings.

EXAMPLES:

sage: R = QQ['x']['y']['z']
sage: R.variable_names_recursive()
('x', 'y', 'z')
sage: R.variable_names_recursive(2)
('y', 'z')

class sage.rings.polynomial.polynomial_ring.PolynomialRing_integral_domain(base_ring, name='x', sparse=False, implementation=None, element_class=None, category=None)#

Bases: PolynomialRing_commutative, PolynomialRing_singular_repr, IntegralDomain

construction()#

Return the construction functor.

EXAMPLES:

sage: from sage.rings.polynomial.polynomial_ring import PolynomialRing_integral_domain as PRing
sage: R = PRing(ZZ, 'x'); R
Univariate Polynomial Ring in x over Integer Ring
sage: functor, arg = R.construction(); functor, arg
(Poly[x], Integer Ring)
sage: functor.implementation is None
True

sage: # needs sage.libs.ntl
sage: R = PRing(ZZ, 'x', implementation='NTL'); R
Univariate Polynomial Ring in x over Integer Ring (using NTL)
sage: functor, arg = R.construction(); functor, arg
(Poly[x], Integer Ring)
sage: functor.implementation
'NTL'

weil_polynomials(d, q, sign=1, lead=1)#

Return all integer polynomials whose complex roots all have a specified absolute value.

Such polynomials \(f\) satisfy a functional equation

\[T^d f(q/T) = s q^{d/2} f(T)\]

where \(d\) is the degree of \(f\), \(s\) is a sign and \(q^{1/2}\) is the absolute value of the roots of \(f\).

INPUT:

d – integer, the degree of the polynomials
q – integer, the square of the complex absolute value of the roots
sign – integer (default \(1\)), the sign \(s\) of the functional equation
lead – integer, list of integers or list of pairs of integers (default \(1\)), constraints on the leading few coefficients of the generated polynomials. If pairs \((a, b)\) of integers are given, they are treated as a constraint of the form \(\equiv a \pmod{b}\); the moduli must be in decreasing order by divisibility, and the modulus of the leading coefficient must be 0.