28.2 Power Series

Module: sage.rings.power_series_ring_element

File: sage/rings/power_series_ring_element.pyx (starting at line 1)

Power Series

SAGE provides an implementation of dense and sparse power series over any SAGE base ring.

Author Log:

• William Stein
• David Harvey (2006-09-11): added solve_linear_de() method
• Robert Bradshaw (2007-04): sqrt, rmul, lmul, shifting
• Robert Bradshaw (2007-04): SageX version

sage: R.<x> = PowerSeriesRing(ZZ)
sage: R([1,2,3])
1 + 2*x + 3*x^2
sage: R([1,2,3], 10)
1 + 2*x + 3*x^2 + O(x^10)
sage: f = 1 + 2*x - 3*x^3 + O(x^4); f
1 + 2*x - 3*x^3 + O(x^4)
sage: f^10
1 + 20*x + 180*x^2 + 930*x^3 + O(x^4)
sage: g = 1/f; g
1 - 2*x + 4*x^2 - 5*x^3 + O(x^4)
sage: g * f
1 + O(x^4)


In Python (as opposted to SAGE) create the power series ring and its generator as follows:

sage: R, x = objgen(PowerSeriesRing(ZZ, 'x'))
sage: parent(x)
Power Series Ring in x over Integer Ring


COERCION This example illustrates that coercion for power series rings is consistent with coercion for polynomial rings.

sage: poly_ring1.<gen1> = PolynomialRing(QQ)
sage: poly_ring2.<gen2> = PolynomialRing(QQ)
sage: huge_ring.<x> = PolynomialRing(poly_ring1)


The generator of the first ring gets coerced in as itself, since it is the base ring.

sage: huge_ring(gen1)
gen1


The generator of the second ring gets mapped via the natural map sending one generator to the other.

sage: huge_ring(gen2)
x


With power series the behavior is the same.

sage: power_ring1.<gen1> = PowerSeriesRing(QQ)
sage: power_ring2.<gen2> = PowerSeriesRing(QQ)
sage: huge_power_ring.<x> = PowerSeriesRing(power_ring1)
sage: huge_power_ring(gen1)
gen1
sage: huge_power_ring(gen2)
x


TODO: Rewrite valuation so it is *carried* along after any calculation, so in almost all cases f.valuation() is instant. Also, if you add f and g and their valuations are the same, note that we only have to look at terms at positions >= f.valuation().

Module-level Functions

 is_PowerSeries( )

 make_element_from_parent_v0( )

 make_powerseries_poly_v0( )

Class: PowerSeries

class PowerSeries
File: sage/rings/power_series_ring_element.pyx (starting at line 114)

A power series.

Functions: add_bigoh, base_extend, base_ring, change_ring, common_prec, degree, derivative, egf, exp, is_dense, is_gen, is_sparse, is_square, is_unit, laurent_series, list, O, ogf, padded_list, polynomial, prec, shift, solve_linear_de, sqrt, square_root, truncate, V, valuation, valuation_zero_part, variable

Returns the power series of precision at most prec got by adding prec to f, where q is the variable.

sage: R.<A> = RDF[[]]
sage: f = (1+A+O(A^5))^5; f
1.0 + 5.0*A + 10.0*A^2 + 10.0*A^3 + 5.0*A^4 + O(A^5)
1.0 + 5.0*A + 10.0*A^2 + O(A^3)
1.0 + 5.0*A + 10.0*A^2 + 10.0*A^3 + 5.0*A^4 + O(A^5)


 base_extend( )

Return a copy of this power series but with coefficients in R.

The following coercion uses base_extend implicitly:

sage: R.<t> = ZZ[['t']]
sage: (t - t^2) * Mod(1, 3)
t + 2*t^2


 base_ring( )

Return the base ring that this power series is defined over.

sage: R.<t> = GF(49,'alpha')[[]]
sage: (t^2 + O(t^3)).base_ring()
Finite Field in alpha of size 7^2


 change_ring( )

Change if possible the coefficients of self to lie in R.

sage: R.<T> = QQ[[]]; R
Power Series Ring in T over Rational Field
sage: f = 1 - 1/2*T + 1/3*T^2 + O(T^3)
sage: f.base_extend(GF(5))
Traceback (most recent call last):
...
TypeError: no base extension defined
sage: f.change_ring(GF(5))
1 + 2*T + 2*T^2 + O(T^3)
sage: f.change_ring(GF(3))
Traceback (most recent call last):
...
ZeroDivisionError: Inverse does not exist.


We can only change irng if there is a __call__ coercion defined. The following succeeds because ZZ(K(4)) is defined.

sage: K.<a> = NumberField(cyclotomic_polynomial(3), 'a')
sage: R.<t> = K[['t']]
sage: (4*t).change_ring(ZZ)
4*t


This does not succeed because ZZ(K(a+1)) is not defined.

sage: K.<a> = NumberField(cyclotomic_polynomial(3), 'a')
sage: R.<t> = K[['t']]
sage: ((a+1)*t).change_ring(ZZ)
Traceback (most recent call last):
...
TypeError: Unable to coerce a + 1 to an integer


 common_prec( )

Returns minimum precision of and self.

sage: R.<t> = PowerSeriesRing(QQ)


sage: f = t + t^2 + O(t^3)
sage: g = t + t^3 + t^4 + O(t^4)
sage: f.common_prec(g)
3
sage: g.common_prec(f)
3


sage: f = t + t^2 + O(t^3)
sage: g = t^2
sage: f.common_prec(g)
3
sage: g.common_prec(f)
3


sage: f = t + t^2
sage: f = t^2
sage: f.common_prec(g)
+Infinity


 degree( )

Return the degree of this power series, which is by definition the degree of the underlying polynomial.

sage: R.<t> = PowerSeriesRing(QQ, sparse=True)
sage: f = t^100000 + O(t^10000000)
sage: f.degree()
100000


 egf( )

Returns the exponential generating function associated to self.

This function is known as serlaplace in GP/PARI.

sage: R.<t> = PowerSeriesRing(QQ)
sage: f = t + t^2 + 2*t^3
sage: f.egf()
t + 1/2*t^2 + 1/3*t^3


 exp( )

Returns exp of this power series to the indicated precision.

INPUT:
prec -- integer; default is self.parent().default_prec


ALGORITHM: See PowerSeries.solve_linear_de().

NOTES: - Screwy things can happen if the coefficient ring is not a field of characteristic zero. See PowerSeries.solve_linear_de().

Author Log:

• David Harvey (2006-09-08): rewrote to use simplest possible lazy'' algorithm.
• David Harvey (2006-09-10): rewrote to use divide-and-conquer strategy.
• David Harvey (2006-09-11): factored functionality out to solve_linear_de().

sage: R.<t> = PowerSeriesRing(QQ, default_prec=10)


Check that is, well, :

sage: (t + O(t^10)).exp()
1 + t + 1/2*t^2 + 1/6*t^3 + 1/24*t^4 + 1/120*t^5 + 1/720*t^6 + 1/5040*t^7 +
1/40320*t^8 + 1/362880*t^9 + O(t^10)


Check that is :

sage: (sum([-(-t)^n/n for n in range(1, 10)]) + O(t^10)).exp()
1 + t + O(t^10)


Check that is whatever it is:

sage: (2*t + t^2 - t^5 + O(t^10)).exp()
1 + 2*t + 3*t^2 + 10/3*t^3 + 19/6*t^4 + 8/5*t^5 - 7/90*t^6 - 538/315*t^7 -
425/168*t^8 - 30629/11340*t^9 + O(t^10)


Check requesting lower precision:

sage: (t + t^2 - t^5 + O(t^10)).exp(5)
1 + t + 3/2*t^2 + 7/6*t^3 + 25/24*t^4 + O(t^5)


Can't get more precision than the input:

sage: (t + t^2 + O(t^3)).exp(10)
1 + t + 3/2*t^2 + O(t^3)


Check some boundary cases:

sage: (t + O(t^2)).exp(1)
1 + O(t)
sage: (t + O(t^2)).exp(0)
O(t^0)


 is_dense( )

sage: R.<t> = PowerSeriesRing(ZZ)
sage: t.is_dense()
True
sage: R.<t> = PowerSeriesRing(ZZ, sparse=True)
sage: t.is_dense()
False


 is_gen( )

Returns True if this the generator (the variable) of the power series ring.

sage: R.<t> = QQ[[]]
sage: t.is_gen()
True
sage: (1 + 2*t).is_gen()
False


Note that this only returns true on the actual generator, not on something that happens to be equal to it.

sage: (1*t).is_gen()
False
sage: 1*t == t
True


 is_sparse( )

sage: R.<t> = PowerSeriesRing(ZZ)
sage: t.is_sparse()
False
sage: R.<t> = PowerSeriesRing(ZZ, sparse=True)
sage: t.is_sparse()
True


 is_square( )

Returns True if this function has a square root in this ring, e.g. there is an element in self.parent() such that .

ALGORITHM: If the basering is a field, this is true whenver the power series has even valuation and the leading coefficent is a perfect square.

For an integral domain, it operates attempts the square root in the fraction field and tests whether or not the result lies in the original ring.

sage: K.<t> = PowerSeriesRing(QQ, 't', 5)
sage: (1+t).is_square()
True
sage: (2+t).is_square()
False
sage: (2+t.change_ring(RR)).is_square()
True
sage: t.is_square()
False
sage: K.<t> = PowerSeriesRing(ZZ, 't', 5)
sage: (1+t).is_square()
False
sage: f = (1+t)^100
sage: f.is_square()
True


 is_unit( )

Returns whether this power series is invertible, which is the case precisely when the constant term is invertible.

sage: R.<t> = PowerSeriesRing(ZZ)
sage: (-1 + t - t^5).is_unit()
True
sage: (3 + t - t^5).is_unit()
False


Author: David Harvey (2006-09-03)

 laurent_series( )

Return the Laurent series associated to this power series, i.e., this series considered as a Laurent series.

sage: k.<w> = QQ[[]]
sage: f = 1+17*w+15*w^3+O(w^5)
sage: parent(f)
Power Series Ring in w over Rational Field
sage: g = f.laurent_series(); g
1 + 17*w + 15*w^3 + O(w^5)


 O( )

Return this series plus prec. Does not change self.

 ogf( )

Returns the ordinary generating function associated to self.

This function is known as serlaplace in GP/PARI.

sage: R.<t> = PowerSeriesRing(QQ)
sage: f = t + t^2/factorial(2) + 2*t^3/factorial(3)
sage: f.ogf()
t + t^2 + 2*t^3


Return list of coefficients of self up to (but not include ).

Includes 0's in the list on the right so that the list has length .

INPUT:
n -- an integer that is at least 0


sage: R.<q> = PowerSeriesRing(QQ)
sage: f = 1 - 17*q + 13*q^2 + 10*q^4 + O(q^7)
sage: f.list()
[1, -17, 13, 0, 10]
[1, -17, 13, 0, 10, 0, 0]
[1, -17, 13, 0, 10, 0, 0, 0, 0, 0]
[1, -17, 13]


 prec( )

The precision of is by definition .

sage: R.<t> = ZZ[[]]
sage: (t^2 + O(t^3)).prec()
3
sage: (1 - t^2 + O(t^100)).prec()
100


 shift( )

Returns this power series multiplied by the power . If is negative, terms below will be discarded. Does not change this power series.

NOTE: Despite the fact that higher order terms are printed to the right in a power series, right shifting decreases the powers of , while left shifting increases them. This is to be consistant with polynomials, integers, etc.

sage: R.<t> = PowerSeriesRing(QQ['y'], 't', 5)
sage: f = ~(1+t); f
1 - t + t^2 - t^3 + t^4 + O(t^5)
sage: f.shift(3)
t^3 - t^4 + t^5 - t^6 + t^7 + O(t^8)
sage: f >> 2
1 - t + t^2 + O(t^3)
sage: f << 10
t^10 - t^11 + t^12 - t^13 + t^14 + O(t^15)
sage: t << 29
t^30


Author: Robert Bradshaw (2007-04-18)

 solve_linear_de( )

Obtains a power series solution to an inhomogeneous linear differential equation of the form:

INPUT:
self -- the power series $a(t)$
b -- the power series $b(t)$ (default is zero)
f0 -- the constant term of $f$ (initial condition'')
(default is 1)
prec -- desired precision of result (this will be reduced if
either a or b have less precision available)

OUTPUT:
the power series f, to indicated precision


ALGORITHM: A divide-and-conquer strategy; see the source code. Running time is approximately , where is the time required for a polynomial multiplication of length over the coefficient ring. (If you're working over something like RationalField(), running time analysis can be a little complicated because the coefficients tend to explode.)

NOTES: - If the coefficient ring is a field of characteristic zero, then the solution will exist and is unique. - For other coefficient rings, things are more complicated. A solution may not exist, and if it does it may not be unique. Generally, by the time the nth term has been computed, the algorithm will have attempted divisions by in the coefficient ring. So if your coefficient ring has enough precision'', and if your coefficient ring can perform divisions even when the answer is not unique, and if you know in advance that a solution exists, then this function will find a solution (otherwise it will probably crash).

Author: David Harvey (2006-09-11): factored functionality out from exp() function, cleaned up precision tests a bit

sage: R.<t> = PowerSeriesRing(QQ, default_prec=10)


sage: a = 2 - 3*t + 4*t^2 + O(t^10)
sage: b = 3 - 4*t^2 + O(t^7)
sage: f = a.solve_linear_de(prec=5, b=b, f0=3/5)
sage: f
3/5 + 21/5*t + 33/10*t^2 - 38/15*t^3 + 11/24*t^4 + O(t^5)
sage: f.derivative() - a*f - b
O(t^4)


sage: a = 2 - 3*t + 4*t^2
sage: b = b = 3 - 4*t^2
sage: f = a.solve_linear_de(b=b, f0=3/5)
Traceback (most recent call last):
...
ValueError: cannot solve differential equation to infinite precision


sage: a.solve_linear_de(prec=5, b=b, f0=3/5)
3/5 + 21/5*t + 33/10*t^2 - 38/15*t^3 + 11/24*t^4 + O(t^5)


 sqrt( )

The square root function.

INPUT:


prec - integer (default: None): if not None and the series has infinite precision, truncates series at precision prec. extend - bool (default: False); if True, return a square root in an extension ring, if necessary. Otherwise, raise a ValueError if the square is not in the base power series ring. For example, if extend is True the square root of a power series with odd degree leading coefficient is defined as an element of a formal extension ring. name - if extend is True, you must also specify the print name of formal square root. all - bool (default: False); if True, return all square roots of self, instead of just one.

ALGORITHM: Newton's method

sage: K.<t> = PowerSeriesRing(QQ, 't', 5)
sage: sqrt(t^2)
t
sage: sqrt(1+t)
1 + 1/2*t - 1/8*t^2 + 1/16*t^3 - 5/128*t^4 + O(t^5)
sage: sqrt(4+t)
2 + 1/4*t - 1/64*t^2 + 1/512*t^3 - 5/16384*t^4 + O(t^5)
sage: u = sqrt(2+t, prec=2, extend=True, name = 'alpha'); u
alpha
sage: u^2
2 + t
sage: u.parent()
Univariate Quotient Polynomial Ring in alpha over Power Series Ring in t
over Rational Field with modulus x^2 - 2 - t
sage: K.<t> = PowerSeriesRing(QQ, 't', 50)
sage: sqrt(1+2*t+t^2)
1 + t
sage: sqrt(t^2 +2*t^4 + t^6)
t + t^3
sage: sqrt(1 + t + t^2 + 7*t^3)^2
1 + t + t^2 + 7*t^3 + O(t^50)
sage: sqrt(K(0))
0
sage: sqrt(t^2)
t


sage: K.<t> = PowerSeriesRing(CDF, 5)
sage: v = sqrt(-1 + t + t^3, all=True); v
[1.0*I - 0.5*I*t - 0.125*I*t^2 - 0.5625*I*t^3 - 0.2890625*I*t^4 + O(t^5),
-1.0*I + 0.5*I*t + 0.125*I*t^2 + 0.5625*I*t^3 + 0.2890625*I*t^4 + O(t^5)]
sage: [a^2 for a in v]
[-1.0 + 1.0*t + 1.0*t^3 + O(t^5), -1.0 + 1.0*t + 1.0*t^3 + O(t^5)]


A formal square root:

sage: K.<t> = PowerSeriesRing(QQ, 5)
sage: f = 2*t + t^3 + O(t^4)
sage: s = f.sqrt(extend=True, name='sqrtf'); s
sqrtf
sage: s^2
2*t + t^3 + O(t^4)
sage: parent(s)
Univariate Quotient Polynomial Ring in sqrtf over Power Series Ring in t
over Rational Field with modulus x^2 - 2*t - t^3 + O(t^4)


Author Log:

• William Stein

 square_root( )

Return the square root of self in this ring. If this cannot be done then an error will be raised.

This function succeeds if and only if self.is_square()

sage: K.<t> = PowerSeriesRing(QQ, 't', 5)
sage: (1+t).square_root()
1 + 1/2*t - 1/8*t^2 + 1/16*t^3 - 5/128*t^4 + O(t^5)
sage: (2+t).square_root()
Traceback (most recent call last):
...
ValueError: Square root does not live in this ring.
sage: (2+t.change_ring(RR)).square_root()
1.41421356237309 + 0.353553390593274*t - 0.0441941738241591*t^2 +
0.0110485434560399*t^3 - 0.00345266983001242*t^4 + O(t^5)
sage: t.square_root()
Traceback (most recent call last):
...
ValueError: Square root not defined for power series of odd valuation.
sage: K.<t> = PowerSeriesRing(ZZ, 't', 5)
sage: f = (1+t)^20
sage: f.square_root()
1 + 10*t + 45*t^2 + 120*t^3 + 210*t^4 + O(t^5)
sage: f = 1+t
sage: f.square_root()
Traceback (most recent call last):
...
ValueError: Square root does not live in this ring.


 truncate( )

The polynomial obtained from power series by truncation.

sage: R.<I> = GF(2)[[]]
sage: f = 1/(1+I+O(I^8)); f
1 + I + I^2 + I^3 + I^4 + I^5 + I^6 + I^7 + O(I^8)
sage: f.truncate(5)
I^4 + I^3 + I^2 + I + 1


 V( )

If , then this function returns .

 valuation( )

Return the valuation of this power series.

This is equal to the valuation of the underlying polynomial.

Sparse examples:

sage: R.<t> = PowerSeriesRing(QQ, sparse=True)
sage: f = t^100000 + O(t^10000000)
sage: f.valuation()
100000
sage: R(0).valuation()
+Infinity


Dense examples:

sage: R.<t> = PowerSeriesRing(ZZ)
sage: f = 17*t^100 +O(t^110)
sage: f.valuation()
100
sage: t.valuation()
1


 valuation_zero_part( )

Factor self as as with nonzero. Then this function returns .

NOTE: this valuation zero part need not be a unit if, e.g., is not invertible in the base ring.

sage: R.<t> = PowerSeriesRing(QQ)
sage: ((1/3)*t^5*(17-2/3*t^3)).valuation_zero_part()
17/3 - 2/9*t^3


In this example the valuation 0 part is not a unit:

sage: R.<t> = PowerSeriesRing(ZZ, sparse=True)
sage: u = (-2*t^5*(17-t^3)).valuation_zero_part(); u
-34 + 2*t^3
sage: u.is_unit()
False
sage: u.valuation()
0


 variable( )

sage: R.<x> = PowerSeriesRing(Rationals())
sage: f = x^2 + 3*x^4 + O(x^7)
sage: f.variable()
'x'


Author: David Harvey (2006-08-08)

Special Functions: __call__, __cmp__, __copy__, __delitem__, __getitem__, __invert__, __lshift__, __mod__, __reduce__, __rlshift__, __rmod__, __rrshift__, __rshift__, __setitem__, _im_gens_, _latex_, _mul_prec, _pari_, _repr_

 __copy__( )

Return this power series. Power series are immutable so copy can safely just return the same polynomial.

sage: R.<q> = ZZ[[ ]]; R
Power Series Ring in q over Integer Ring
sage: f = 1 + 3*q + O(q^10)
sage: copy(f) is f       # !!! ok since power series are immutable.
True


 __reduce__( )

sage: K.<t> = PowerSeriesRing(QQ, 5)
sage: f = 1 + t - t^3 + O(t^12)
sage: loads(dumps(f)) == f
True


 _im_gens_( )

Returns the image of this series under the map that sends the generators to im_gens. This is used internally for computing homomorphisms.

sage: R.<t> = QQ[[]]
sage: f = 1 + t + t^2
sage: f._im_gens_(ZZ, [3])
13


 _latex_( )

Return latex representation of this power series.

sage: R.<t> = QQ[[]]
sage: f = -1/2 * t + 2/3*t^2 - 9/7 * t^15 + O(t^20); f
-1/2*t + 2/3*t^2 - 9/7*t^15 + O(t^20)
sage: latex(f)
-\frac{1}{2}t + \frac{2}{3}t^{2} - \frac{9}{7}t^{15} + O(t^{20})


 _mul_prec( )

 _pari_( )

Return PARI power series corresponding to this series.

This is currently only implemented over QQ and ZZ.

sage: k.<w> = QQ[[]]
sage: f = 1+17*w+15*w^3+O(w^5)
sage: pari(f)
1 + 17*w + 15*w^3 + O(w^5)
sage: pari(1 - 19*w + w^5)
Traceback (most recent call last):
...
RuntimeError: series precision must be finite for conversion to pari
object.


 _repr_( )

Return string represenation of this power series.

sage: R.<t> = ZZ[[]]
sage: (t^2 + O(t^3))._repr_()
't^2 + O(t^3)'


sage: R.<t> = QQ[[]]
sage: 1 / (1+2*t +O(t^5))
1 - 2*t + 4*t^2 - 8*t^3 + 16*t^4 + O(t^5)


sage: R.<t> = PowerSeriesRing(QQ, sparse=True)
sage: 1 / (1+2*t +O(t^5))
1 - 2*t + 4*t^2 - 8*t^3 + 16*t^4 + O(t^5)
sage: -13/2 * t^3  + 5*t^5 + O(t^10)
-13/2*t^3 + 5*t^5 + O(t^10)