Integer-valued polynomial rings

AUTHORS:

• Frédéric Chapoton (2023-03): Initial version

class sage.rings.polynomial.integer_valued_polynomials.IntegerValuedPolynomialRing(R)

Bases: UniqueRepresentation, Parent

The integer-valued polynomial ring over a base ring \(R\).

Integer-valued polynomial rings are commutative and associative algebras, with a basis indexed by non-negative integers.

There are two natural bases, made of the sequence \(\binom{x}{n}\) for \(n \geq 0\) (the binomial basis) and of the other sequence \(\binom{x+n}{n}\) for \(n \geq 0\) (the shifted basis).

These two bases are available as follows:

sage: B = IntegerValuedPolynomialRing(QQ).Binomial()
sage: S = IntegerValuedPolynomialRing(QQ).Shifted()

or by using the shortcuts:

sage: B = IntegerValuedPolynomialRing(QQ).B()
sage: S = IntegerValuedPolynomialRing(QQ).S()

There is a conversion formula between the two bases:

\[\binom{x}{i} = \sum_{k=0}^{i} (-1)^{i-k} \binom{i}{k} \binom{x+k}{k}\]

with inverse:

\[\binom{x+i}{i} = \sum_{k=0}^{i} \binom{i}{k} \binom{x}{k}.\]

REFERENCES:

• Wikipedia article Integer-valued polynomial

B

alias of Binomial

class Bases(parent_with_realization)

Bases: Category_realization_of_parent

class ElementMethods

Bases: object

content()

Return the content of self.

This is the gcd of the coefficients.

EXAMPLES:

sage: F = IntegerValuedPolynomialRing(ZZ).S()
sage: B = F.basis()
sage: (3*B[4]+6*B[7]).content()
3

polynomial()

Convert to a polynomial in \(x\).

EXAMPLES:

sage: F = IntegerValuedPolynomialRing(ZZ).S()
sage: B = F.gen()
sage: (B+1).polynomial()
x + 2

sage: F = IntegerValuedPolynomialRing(ZZ).B()
sage: B = F.gen()
sage: (B+1).polynomial()
x + 1

shift(j=1)

Shift all indices by \(j\).

INPUT:

• \(j\) – integer (default: 1)

In the binomial basis, the shift by 1 corresponds to a summation operator from \(0\) to \(x\).

EXAMPLES:

sage: F = IntegerValuedPolynomialRing(ZZ).B()
sage: B = F.gen()
sage: (B+1).shift()
B[1] + B[2]
sage: (B+1).shift(3)
B[3] + B[4]

sum_of_coefficients()

Return the sum of coefficients.

In the shifted basis, this is the evaluation at \(x=0\).

EXAMPLES:

sage: F = IntegerValuedPolynomialRing(ZZ).S()
sage: B = F.basis()
sage: (B[2]*B[4]).sum_of_coefficients()
1

class ParentMethods

Bases: object

algebra_generators()

Return the generators of this algebra.

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(ZZ).S(); A
Integer-Valued Polynomial Ring over Integer Ring
in the shifted basis
sage: A.algebra_generators()
Family (S[1],)

degree_on_basis(m)

Return the degree of the basis element indexed by m.

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(QQ).S()
sage: A.degree_on_basis(4)
4

from_polynomial(p)

Convert a polynomial into the ring of integer-valued polynomials.

This raises a ValueError if this is not possible.

INPUT:

• p – a polynomial in one variable

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(ZZ).S()
sage: S = A.basis()
sage: S[5].polynomial()
1/120*x^5 + 1/8*x^4 + 17/24*x^3 + 15/8*x^2 + 137/60*x + 1
sage: A.from_polynomial(_)
S[5]
sage: x = polygen(QQ, 'x')
sage: A.from_polynomial(x)
-S[0] + S[1]

sage: A = IntegerValuedPolynomialRing(ZZ).B()
sage: B = A.basis()
sage: B[5].polynomial()
1/120*x^5 - 1/12*x^4 + 7/24*x^3 - 5/12*x^2 + 1/5*x
sage: A.from_polynomial(_)
B[5]
sage: x = polygen(QQ, 'x')
sage: A.from_polynomial(x)
B[1]

gen(i=0)

Return the generator of this algebra.

The optional argument is ignored.

EXAMPLES:

sage: F = IntegerValuedPolynomialRing(ZZ).B()
sage: F.gen()
B[1]

gens()

Return the generators of this algebra.

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(ZZ).S(); A
Integer-Valued Polynomial Ring over Integer Ring
in the shifted basis
sage: A.algebra_generators()
Family (S[1],)

one_basis()

Return the number 0, which index the unit of this algebra.

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(QQ).S()
sage: A.one_basis()
0
sage: A.one()
S[0]

super_categories()

Return the super-categories of self.

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(QQ); A
Integer-Valued Polynomial Ring over Rational Field
sage: C = A.Bases(); C
Category of bases of Integer-Valued Polynomial Ring
over Rational Field
sage: C.super_categories()
[Category of realizations of Integer-Valued Polynomial Ring
 over Rational Field,
 Join of Category of algebras with basis over Rational Field and
 Category of filtered algebras over Rational Field and
 Category of commutative algebras over Rational Field and
 Category of realizations of unital magmas]

class Binomial(A)

Bases: CombinatorialFreeModule, BindableClass

The integer-valued polynomial ring in the binomial basis.

The basis used here is given by \(B[i] = \binom{x}{i}\) for \(i \in \NN\).

Assuming \(n_1 \leq n_2\), the product of two monomials \(B[n_1] \cdot B[n_2]\) is given by the sum

\[\sum_{k=0}^{n_1} \binom{n_1}{k}\binom{n_1+n_2-k}{n_1} B[n_1 + n_2 - k].\]

The product of two monomials is therefore a positive linear combination of monomials.

EXAMPLES:

sage: F = IntegerValuedPolynomialRing(QQ).B(); F
Integer-Valued Polynomial Ring over Rational Field
in the binomial basis

sage: F.gen()
B[1]

sage: S = IntegerValuedPolynomialRing(ZZ).B(); S
Integer-Valued Polynomial Ring over Integer Ring
in the binomial basis
sage: S.base_ring()
Integer Ring

sage: G = IntegerValuedPolynomialRing(S).B(); G
Integer-Valued Polynomial Ring over Integer-Valued Polynomial Ring
over Integer Ring in the binomial basis in the binomial basis
sage: G.base_ring()
Integer-Valued Polynomial Ring over Integer Ring
in the binomial basis

Integer-valued polynomial rings commute with their base ring:

sage: K = IntegerValuedPolynomialRing(QQ).B()
sage: a = K.gen()
sage: K.is_commutative()
True
sage: L = IntegerValuedPolynomialRing(K).B()
sage: c = L.gen()
sage: L.is_commutative()
True
sage: s = a * c^3; s
B[1]*B[1] + 6*B[1]*B[2] + 6*B[1]*B[3]
sage: parent(s)
Integer-Valued Polynomial Ring over Integer-Valued Polynomial
Ring over Rational Field in the binomial basis in the binomial basis

Integer-valued polynomial rings are commutative:

sage: c^3 * a == c * a * c * c
True

We can also manipulate elements in the basis:

sage: F = IntegerValuedPolynomialRing(QQ).B()
sage: B = F.basis()
sage: B[2] * B[3]
3*B[3] + 12*B[4] + 10*B[5]
sage: 1 - B[2] * B[2] / 2
B[0] - 1/2*B[2] - 3*B[3] - 3*B[4]

and coerce elements from our base field:

sage: F(4/3)
4/3*B[0]

class Element

Bases: IndexedFreeModuleElement

variable_shift(k=1)

Return the image by the shift of variables.

On polynomials, the action is the shift on variables \(x \mapsto x + k\).

INPUT:

• \(k\) – integer (default: 1)

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(ZZ).B()
sage: B = A.basis()
sage: B[5].variable_shift()
B[4] + B[5]
sage: B[5].variable_shift(-1)
-B[0] + B[1] - B[2] + B[3] - B[4] + B[5]

product_on_basis(n1, n2)

Return the product of basis elements n1 and n2.

INPUT:

• n1, n2 – integers

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(QQ).B()
sage: A.product_on_basis(0, 1)
B[1]
sage: A.product_on_basis(1, 2)
2*B[2] + 3*B[3]

S

alias of Shifted

class Shifted(A)

Bases: CombinatorialFreeModule, BindableClass

The integer-valued polynomial ring in the shifted basis.

The basis used here is given by \(S[i] = \binom{i+x}{i}\) for \(i \in \NN\).

Assuming \(n_1 \leq n_2\), the product of two monomials \(S[n_1] \cdot S[n_2]\) is given by the sum

\[\sum_{k=0}^{n_1} (-1)^k \binom{n_1}{k}\binom{n_1+n_2-k}{n_1} S[n_1 + n_2 - k].\]

EXAMPLES:

sage: F = IntegerValuedPolynomialRing(QQ).S(); F
Integer-Valued Polynomial Ring over Rational Field
in the shifted basis

sage: F.gen()
S[1]

sage: S = IntegerValuedPolynomialRing(ZZ).S(); S
Integer-Valued Polynomial Ring over Integer Ring
in the shifted basis
sage: S.base_ring()
Integer Ring

sage: G = IntegerValuedPolynomialRing(S).S(); G
Integer-Valued Polynomial Ring over Integer-Valued Polynomial
Ring over Integer Ring in the shifted basis in the shifted basis
sage: G.base_ring()
Integer-Valued Polynomial Ring over Integer Ring
in the shifted basis

Integer-valued polynomial rings commute with their base ring:

sage: K = IntegerValuedPolynomialRing(QQ).S()
sage: a = K.gen()
sage: K.is_commutative()
True
sage: L = IntegerValuedPolynomialRing(K).S()
sage: c = L.gen()
sage: L.is_commutative()
True
sage: s = a * c^3; s
S[1]*S[1] + (-6*S[1])*S[2] + 6*S[1]*S[3]
sage: parent(s)
Integer-Valued Polynomial Ring over Integer-Valued Polynomial
Ring over Rational Field in the shifted basis in the shifted basis

Integer-valued polynomial rings are commutative:

sage: c^3 * a == c * a * c * c
True

We can also manipulate elements in the basis and coerce elements from our base field:

sage: F = IntegerValuedPolynomialRing(QQ).S()
sage: S = F.basis()
sage: S[2] * S[3]
3*S[3] - 12*S[4] + 10*S[5]
sage: 1 - S[2] * S[2] / 2
S[0] - 1/2*S[2] + 3*S[3] - 3*S[4]

class Element

Bases: IndexedFreeModuleElement

delta()

Return the image by the difference operator \(\Delta\).

The operator \(\Delta\) is defined on polynomials by

\[f \mapsto f(x+1)-f(x).\]

EXAMPLES:

sage: F = IntegerValuedPolynomialRing(ZZ).S()
sage: S = F.basis()
sage: S[5].delta()
S[0] + S[1] + S[2] + S[3] + S[4]

derivative_at_minus_one()

Return the derivative at \(-1\).

This is sometimes useful when \(-1\) is a root.

See also

umbra()

EXAMPLES:

sage: F = IntegerValuedPolynomialRing(ZZ).S()
sage: B = F.gen()
sage: (B+1).derivative_at_minus_one()
1

fraction()

Return the generating series of values as a fraction.

In the case of Ehrhart polynomials, this is known as the Ehrhart series.

See also

h_vector(), h_polynomial()

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(ZZ).S()
sage: ex = A.monomial(4)
sage: f = ex.fraction();f
-1/(t^5 - 5*t^4 + 10*t^3 - 10*t^2 + 5*t - 1)

sage: F = LazyPowerSeriesRing(QQ, 't')
sage: F(f)
1 + 5*t + 15*t^2 + 35*t^3 + 70*t^4 + 126*t^5 + 210*t^6 + O(t^7)

sage: poly = ex.polynomial()
sage: [poly(i) for i in range(6)]
[1, 5, 15, 35, 70, 126]

sage: y = polygen(QQ, 'y')
sage: penta = A.from_polynomial(7/2*y^2 + 7/2*y + 1)
sage: penta.fraction()
(-t^2 - 5*t - 1)/(t^3 - 3*t^2 + 3*t - 1)

h_polynomial()

Return the \(h\)-vector as a polynomial.

See also

h_vector(), fraction()

EXAMPLES:

sage: x = polygen(QQ,'x')
sage: A = IntegerValuedPolynomialRing(ZZ).S()
sage: ex = A.from_polynomial((1+x)**3)
sage: ex.h_polynomial()
z^2 + 4*z + 1

h_vector()

Return the numerator of the generating series of values.

If self is an Ehrhart polynomial, this is the \(h\)-vector.

See also

h_polynomial(), fraction()

EXAMPLES:

sage: x = polygen(QQ,'x')
sage: A = IntegerValuedPolynomialRing(ZZ).S()
sage: ex = A.from_polynomial((1+x)**3)
sage: ex.h_vector()
(0, 1, 4, 1)

umbra()

Return the Bernoulli umbra.

This is the derivative at \(-1\) of the shift by one.

See also

derivative_at_minus_one()

EXAMPLES:

sage: F = IntegerValuedPolynomialRing(ZZ).S()
sage: B = F.gen()
sage: (B+1).umbra()
3/2

variable_shift(k=1)

Return the image by the shift of variables.

On polynomials, the action is the shift on variables \(x \mapsto x + k\).

INPUT:

• \(k\) – integer (default: 1)

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(ZZ).S()
sage: S = A.basis()
sage: S[5].variable_shift()
S[0] + S[1] + S[2] + S[3] + S[4] + S[5]

sage: S[5].variable_shift(-1)
-S[4] + S[5]

from_h_vector(h)

Convert from some \(h\)-vector.

INPUT:

• h – a tuple or vector

See also

Element.h_vector()

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(ZZ).S()
sage: S = A.basis()
sage: ex = S[2]+S[4]
sage: A.from_h_vector(ex.h_vector())
S[2] + S[4]

product_on_basis(n1, n2)

Return the product of basis elements n1 and n2.

INPUT:

• n1, n2 – integers

EXAMPLES:

sage: A = IntegerValuedPolynomialRing(QQ).S()
sage: A.product_on_basis(0, 1)
S[1]
sage: A.product_on_basis(1, 2)
-2*S[2] + 3*S[3]

a_realization()

Return a default realization.

The Binomial realization is chosen.

EXAMPLES:

sage: IntegerValuedPolynomialRing(QQ).a_realization()
Integer-Valued Polynomial Ring over Rational Field
in the binomial basis