Generic Puiseux series

AbstractAlgebra.jl allows the creation of Puiseux series over any computable commutative ring $R$.

Puiseux series are power series of the form $a_jx^{j/m} + a_{j+1}x^{(j+1)/m} + \cdots + a_{k-1}x^{(k-1)/m} + O(x^{k/m})$ for some integer $m > 0$ where $i \geq 0$, $a_i \in R$ and the relative precision $k - j$ is at most equal to some specified precision $n$.

The generic Puiseux series module is implemented in src/generic/PuiseuxSeries.jl.

As well as implementing the Series Ring interface, the Puiseux series module in AbstractAlgebra.jl implements the generic algorithms described below.

All of the generic functionality is part of the Generic submodule of AbstractAlgebra.jl. This is exported by default so that it is not necessary to qualify function names.

Types and parent objects

The types of generic Puiseux series implemented by AbstractAlgebra.jl are Generic.PuiseuxSeriesRingElem{T} and Generic.PuiseuxSeriesFieldElem{T}.

Both series element types belong to the union type Generic.PuiseuxSeriesElem.

Puiseux series elements belong directly to either RingElem or FieldElem since it is more useful to be able to distinguish whether they belong to a ring or field than it is to distinguish that they are Puiseux series.

The parent types for Puiseux series, Generic.PuiseuxSeriesRing{T} and Generic.PuiseuxSeriesField{T} respectively, belong to Ring and Field respectively.

The default precision, string representation of the variable and base ring $R$ of a generic Puiseux series are stored in its parent object.

Puiseux series ring constructors

In order to construct Puiseux series in AbstractAlgebra.jl, one must first construct the ring itself. This is accomplished with any of the following constructors.

puiseux_series_ring(R::Ring, prec_max::Int, s::VarName; cached::Bool = true)
puiseux_series_ring(R::Field, prec_max::Int, s::VarName; cached::Bool = true)
puiseux_series_field(R::Field, prec_max::Int, s::VarName; cached::Bool = true)

Given a base ring R, a maximum relative precision and a string s specifying how the generator (variable) should be printed, return a tuple S, x representing the Puiseux series ring and its generator.

By default, S will depend only on S, x and the maximum precision and will be cached. Setting the optional argument cached to false will prevent this.

Here are some examples of constructing various kinds of Puiseux series rings and coercing various elements into those rings.

Examples

julia> R, x = puiseux_series_ring(ZZ, 10, :x)
(Puiseux series ring in x over integers, x + O(x^11))

julia> S, y = puiseux_series_field(QQ, 10, :y)
(Puiseux series field in y over rationals, y + O(y^11))

julia> f = R()
O(x^10)

julia> g = S(123)
123 + O(y^10)

julia> h = R(BigInt(1234))
1234 + O(x^10)

julia> k = S(y + 1)
1 + y + O(y^10)

Big-oh notation

Series elements can be given a precision using the big-oh notation. This is provided by a function of the following form, (or something equivalent for Laurent series):

O(x::SeriesElem)

Examples

julia> R, x = puiseux_series_ring(ZZ, 10, :x)
(Puiseux series ring in x over integers, x + O(x^11))

julia> f = 1 + 2x + O(x^5)
1 + 2*x + O(x^5)

julia> g = 2x^(1//3) + 7x^(2//3) + O(x^(7//3))
2*x^(1//3) + 7*x^(2//3) + O(x^(7//3))

What is happening here in practice is that O(x^n) is creating the series 0 + O(x^n) and the rules for addition of series dictate that if this is added to a series of greater precision, then the lower of the two precisions must be used.

Of course it may be that the precision of the series that O(x^n) is added to is already lower than n, in which case adding O(x^n) has no effect. This is the case if the default precision is too low, since x on its own has the default precision.

Puiseux series implementation

Puiseux series have their maximum relative precision capped at some value prec_max. This refers to the internal Laurent series used to store the Puiseux series, i.e. the series without denominators in the exponents.

The Puiseux series type stores such a Laurent series and a scale or denominator for the exponents. For example, $f(x) = 1 + x^{1/3} + 2x^{2/3} + O(x^{7/3})$ would be stored as a Laurent series $1 + x + 2x^2 + O(x^7)$ and a scale of $3$..

The maximum precision is also used as a default (Laurent) precision in the case of coercing coefficients into the ring and for any computation where the result could mathematically be given to infinite precision.

In all models we say that two Puiseux series are equal if they agree up to the minimum absolute precision of the two power series.

Thus, for example, $x^5 + O(x^{10}) == 0 + O(x^5)$, since the minimum absolute precision is $5$.

Sometimes it is necessary to compare Puiseux series not just for arithmetic equality, as above, but to see if they have precisely the same precision and terms. For this purpose we introduce the isequal function.

For example, if $f = x^2 + O(x^7)$ and $g = x^2 + O(x^8)$ and $h = 0 + O(x^2)$ then $f == g$, $f == h$ and $g == h$, but isequal(f, g), isequal(f, h) and isequal(g, h) would all return false. However, if $k = x^2 + O(x^7)$ then isequal(f, k) would return true.

There are a number of technicalities that must be observed when working with Puiseux series. As these are the same as for the other series rings in AbstractAlgebra.jl, we refer the reader to the documentation of series rings for information about these issues.

Basic ring functionality

All Puiseux series provide the functionality described in the Ring and Series Ring interfaces with the exception of the pol_length and polcoeff functions. Naturally the set_precision!, set_valuation! and coeff functions can take a rational exponent.

Examples

julia> S, x = puiseux_series_ring(ZZ, 10, :x)
(Puiseux series ring in x over integers, x + O(x^11))

julia> f = 1 + 3x + x^3 + O(x^10)
1 + 3*x + x^3 + O(x^10)

julia> g = 1 + 2x^(1//3) + x^(2//3) + O(x^(7//3))
1 + 2*x^(1//3) + x^(2//3) + O(x^(7//3))

julia> h = zero(S)
O(x^10)

julia> k = one(S)
1 + O(x^10)

julia> isone(k)
true

julia> iszero(f)
false

julia> coeff(g, 1//3)
2

julia> U = base_ring(S)
Integers

julia> v = var(S)
:x

julia> T = parent(x + 1)
Puiseux series ring in x over integers

julia> g == deepcopy(g)
true

julia> t = divexact(2g, 2)
1 + 2*x^(1//3) + x^(2//3) + O(x^(7//3))

julia> p = precision(f)
10//1

Puiseux series functionality provided by AbstractAlgebra.jl

The functionality below is automatically provided by AbstractAlgebra.jl for any Puiseux series.

Of course, modules are encouraged to provide specific implementations of the functions described here, that override the generic implementation.

Basic functionality

coeff(a::Generic.PuiseuxSeriesElem, n::Int)
coeff(a::Generic.PuiseuxSeriesElem, n::Rational{Int})

Return the coefficient of the term of exponent $n$ of the given power series. If $n$ exceeds the current precision of the power series or does not correspond to a nonzero term of the Puiseux series, the function returns a zero coefficient.

AbstractAlgebra.modulusMethod
modulus(a::Generic.PuiseuxSeriesElem{T}) where {T <: ResElem}

Return the modulus of the coefficients of the given Puiseux series.

source
AbstractAlgebra.is_genMethod
is_gen(a::Generic.PuiseuxSeriesElem)

Return true if the given Puiseux series is arithmetically equal to the generator of its Puiseux series ring to its current precision, otherwise return false.

source

Examples

julia> R, t = puiseux_series_ring(QQ, 10, :t)
(Puiseux series field in t over rationals, t + O(t^11))

julia> S, x = puiseux_series_ring(R, 30, :x)
(Puiseux series field in x over R, x + O(x^31))

julia> a = O(x^4)
O(x^4)

julia> b = (t + 3)*x + (t^2 + 1)*x^2 + O(x^4)
(3 + t + O(t^10))*x + (1 + t^2 + O(t^10))*x^2 + O(x^4)

julia> k = is_gen(gen(R))
true

julia> m = is_unit(-1 + x^(1//3) + 2x^2)
true

julia> n = valuation(a)
4//1

julia> p = valuation(b)
1//1

julia> c = coeff(b, 2)
1 + t^2 + O(t^10)

Division

Base.invMethod
inv(M::MatrixElem{T}) where {T <: RingElement}

Given a non-singular $n\times n$ matrix over a ring, return an $n\times n$ matrix $X$ such that $MX = I_n$, where $I_n$ is the $n\times n$ identity matrix. If $M$ is not invertible over the base ring an exception is raised.

source
Base.inv(a::PuiseuxSeriesElem{T}) where T <: RingElement

Return the inverse of the power series $a$, i.e. $1/a$, if it exists. Otherwise an exception is raised.

source
 inv(a::LocalizedEuclideanRingElem{T}, checked::Bool = true)  where {T <: RingElem}

Returns the inverse element of $a$ if $a$ is a unit. If 'checked = false' the invertibility of $a$ is not checked and the corresponding inverse element of the Fraction Field is returned.

source

Examples

julia> R, x = puiseux_series_ring(QQ, 30, :x)
(Puiseux series field in x over rationals, x + O(x^31))

julia> a = 1 + x + 2x^2 + O(x^5)
1 + x + 2*x^2 + O(x^5)

julia> b = R(-1)
-1 + O(x^30)

julia> c = inv(a)
1 - x - x^2 + 3*x^3 - x^4 + O(x^5)

julia> d = inv(b)
-1 + O(x^30)

Derivative and integral

AbstractAlgebra.derivativeMethod
derivative(f::AbsPowerSeriesRingElem{T})

Return the derivative of the power series $f$.

source
derivative(f::RelPowerSeriesRingElem{T})

Return the derivative of the power series $f$.

julia> R, x = power_series_ring(QQ, 10, :x)
(Univariate power series ring in x over Rationals, x + O(x^11))

julia> f = 2 + x + 3x^3
2 + x + 3*x^3 + O(x^10)

julia> derivative(f)
1 + 9*x^2 + O(x^9)
source
derivative(f::MPolyRingElem{T}, j::Int) where {T <: RingElement}

Return the partial derivative of f with respect to $j$-th variable of the polynomial ring.

source
derivative(f::MPolyRingElem{T}, x::MPolyRingElem{T}) where T <: RingElement

Return the partial derivative of f with respect to x. The value x must be a generator of the polynomial ring of f.

source
derivative(a::Generic.PuiseuxSeriesElem{T}) where T <: RingElement

Return the derivative of the given Puiseux series $a$.

source
AbstractAlgebra.integralMethod
integral(f::AbsPowerSeriesRingElem{T})

Return the integral of the power series $f$.

source
integral(f::RelPowerSeriesRingElem{T})

Return the integral of the power series $f$.

julia> R, x = power_series_ring(QQ, 10, :x)
(Univariate power series ring in x over Rationals, x + O(x^11))

julia> f = 2 + x + 3x^3
2 + x + 3*x^3 + O(x^10)

julia> integral(f)
2*x + 1//2*x^2 + 3//4*x^4 + O(x^11)
source
integral(a::Generic.PuiseuxSeriesElem{T}) where T <: RingElement

Return the integral of the given Puiseux series $a$.

source

Examples

julia> R, x = puiseux_series_ring(QQ, 10, :x)
(Puiseux series field in x over rationals, x + O(x^11))

julia> f = x^(5//3) + x^(7//3) + x^(11//3)
x^(5//3) + x^(7//3) + x^(11//3) + O(x^5)

julia> derivative(f)
5//3*x^(2//3) + 7//3*x^(4//3) + 11//3*x^(8//3) + O(x^4)

julia> derivative(integral(f)) == f
true

Special functions

Base.logMethod
log(a::Generic.PuiseuxSeriesElem{T}) where T <: RingElement

Return the logarithm of the given Puiseux series $a$.

source
Base.expMethod
exp(a::AbsPowerSeriesRingElem)

Return the exponential of the power series $a$.

source
exp(a::RelPowerSeriesRingElem)

Return the exponential of the power series $a$.

source
exp(a::Generic.LaurentSeriesElem)

Return the exponential of the power series $a$.

source
exp(a::Generic.PuiseuxSeriesElem{T}) where T <: RingElement

Return the exponential of the given Puiseux series $a$.

source
Base.sqrtMethod
Base.sqrt(f::PolyRingElem{T}; check::Bool=true) where T <: RingElement

Return the square root of $f$. By default the function checks the input is square and raises an exception if not. If check=false this check is omitted.

source
Base.sqrt(a::FracElem{T}; check::Bool=true) where T <: RingElem

Return the square root of $a$. By default the function will throw an exception if the input is not square. If check=false this test is omitted.

source
sqrt(a::Generic.PuiseuxSeriesElem{T}; check::Bool=true) where T <: RingElement

Return the square root of the given Puiseux series $a$. By default the function will throw an exception if the input is not square. If check=false this test is omitted.

source

Examples

julia> R, t = polynomial_ring(QQ, :t)
(Univariate polynomial ring in t over rationals, t)

julia> S, x = puiseux_series_ring(R, 30, :x)
(Puiseux series ring in x over R, x + O(x^31))

julia> T, z = puiseux_series_ring(QQ, 30, :z)
(Puiseux series field in z over rationals, z + O(z^31))

julia> a = 1 + z + 3z^2 + O(z^5)
1 + z + 3*z^2 + O(z^5)

julia> b = z + 2z^2 + 5z^3 + O(z^5)
z + 2*z^2 + 5*z^3 + O(z^5)

julia> c = exp(x + O(x^40))
1 + x + 1//2*x^2 + 1//6*x^3 + 1//24*x^4 + 1//120*x^5 + 1//720*x^6 + 1//5040*x^7 + 1//40320*x^8 + 1//362880*x^9 + 1//3628800*x^10 + 1//39916800*x^11 + 1//479001600*x^12 + 1//6227020800*x^13 + 1//87178291200*x^14 + 1//1307674368000*x^15 + 1//20922789888000*x^16 + 1//355687428096000*x^17 + 1//6402373705728000*x^18 + 1//121645100408832000*x^19 + 1//2432902008176640000*x^20 + 1//51090942171709440000*x^21 + 1//1124000727777607680000*x^22 + 1//25852016738884976640000*x^23 + 1//620448401733239439360000*x^24 + 1//15511210043330985984000000*x^25 + 1//403291461126605635584000000*x^26 + 1//10888869450418352160768000000*x^27 + 1//304888344611713860501504000000*x^28 + 1//8841761993739701954543616000000*x^29 + 1//265252859812191058636308480000000*x^30 + O(x^31)

julia> d = divexact(x, exp(x + O(x^40)) - 1)
1 - 1//2*x + 1//12*x^2 - 1//720*x^4 + 1//30240*x^6 - 1//1209600*x^8 + 1//47900160*x^10 - 691//1307674368000*x^12 + 1//74724249600*x^14 - 3617//10670622842880000*x^16 + 43867//5109094217170944000*x^18 - 174611//802857662698291200000*x^20 + 77683//14101100039391805440000*x^22 - 236364091//1693824136731743669452800000*x^24 + 657931//186134520519971831808000000*x^26 - 3392780147//37893265687455865519472640000000*x^28 + O(x^29)

julia> f = exp(b)
1 + z + 5//2*z^2 + 43//6*z^3 + 193//24*z^4 + O(z^5)

julia> h = sqrt(a)
1 + 1//2*z + 11//8*z^2 - 11//16*z^3 - 77//128*z^4 + O(z^5)