Universal ring
AbstractAlgebra provides a module, implemented in src/UniversalRing.jl for universal rings. They "universalize" rings which have a notion of generators (or variables) and coefficients. The most important example of such a ring is a multivariate polynomial ring. In contrast to the usual multivariate polynomial ring, its universal pendant allows for variables to be added at any time.
Another example is the ring of multivariate Laurent polynomials.
The type of the universal ring is UniversalRing{T, U} where T is the type of the elements of the underlying ring and U is the type of the coefficients. In the case of multivariate polynomials T would be a subtype of MPolyRingElem and U would be the type of the coefficients of the polynomials, for example BigInt.
Universal polynomial ring
To compensate for the fact that the number of variables may change, many of the functions relax their restrictions on exponent vectors. For example, if one creates a polynomial when the ring only has two variables, each exponent vector would consist of two integers. Later, when the ring has more variable, these exponent vectors will still be accepted. The exponent vectors are simply padded out to the full number of variables behind the scenes.
The universal polynomial ring behaves exactly like a multivariate polynomial ring with the few differences noted above.
The only functionality not implemented is the ability to do divrem by an ideal of polynomials.
The universal polynomial ring is very useful for doing symbolic manipulation. However, it is important to understand that AbstractAlgebra is not a symbolic system and the performance of the universal polynomial ring will closely match that of a multivariate polynomial ring with the same number of variables.
The disadvantage of this approach to symbolic manipulation is that some manipulations that would be offered by a symbolic system are not available, as variables are not identified by their names alone in AbstractAlgebra, as would be the case symbolically, but by objects.
The most powerful symbolic tools we offer are the generalized evaluation functions, the multivariate coefficient functionality, the ability to change coefficient ring and to map coefficients according to a supplied function and the ability to convert a multivariate which happens to have just one variable into a dense univariate polynomial.
Further facilities may be added in future to ease symbolic manipulations.
Constructors
In order to construct universal polynomials in AbstractAlgebra, one must first construct the universal polynomial ring itself. This is unique given a coefficient ring.
The universal polynomial ring over a given coefficient ring R is constructed with one of the following constructor functions.
AbstractAlgebra.universal_polynomial_ring — Function
universal_polynomial_ring(R::Ring, varnames::Vector{Symbol}; cached::Bool=true, internal_ordering::Symbol=:lex)
universal_polynomial_ring(R::Ring; cached::Bool=true, internal_ordering::Symbol=:lex)Given a coefficient ring R and variable names, say varnames = [:x1, :x2, ...], return a tuple S, [x1, x2, ...] of the universal polynomial ring S = R[x1, x2, \dots] and its generators x1, x2, \dots.
If varnames is omitted, return an object representing the universal polynomial ring S = R[\ldots] with no variables in it initially.
By default (cached=true), the output S will be cached, i.e. if universal_polynomial_ring is invoked again with the same coefficient ring R and monomial ordering internal_ordering, the same (identical) ring is returned. Keep in mind that this ring might already have more variables than supplied in varnames. Setting cached to false ensures a distinct new ring is returned, and will also prevent it from being cached.
Examples
julia> S, (x,y) = universal_polynomial_ring(ZZ, [:x,:y])
(Universal polynomial ring over Integers, UniversalRingElem{AbstractAlgebra.Generic.MPoly{BigInt}, BigInt}[x, y])
julia> z = gen(S, :z)
z
julia> x*y - z
x*y - z
julia> S = universal_polynomial_ring(ZZ)
Universal polynomial ring over Integers
julia> x = gen(S, :x)
x
julia> y, z = gens(S, [:y, :z])
2-element Vector{UniversalRingElem{AbstractAlgebra.Generic.MPoly{BigInt}, BigInt}}:
y
z
julia> x*y - z
x*y - zSimilarly, on can construct universal Laurent polynomial rings.
AbstractAlgebra.universal_laurent_polynomial_ring — Function
universal_laurent_polynomial_ring(R::Ring, varnames::Vector{Symbol}; cached::Bool=true)
universal_laurent_polynomial_ring(R::Ring; cached::Bool=true)Given a coefficient ring R and variable names, say varnames = [:x1, :x2, ...], return a tuple S, [x1, x2, ...] of the universal Laurent polynomial ring S = R[x1, x2, \dots] and its generators x1, x2, \dots.
If varnames is omitted, return an object representing the universal Laurent polynomial ring S = R[\ldots] with no variables in it initially.
By default (cached=true), the output S will be cached, i.e. if universal_laurent_polynomial_ring is invoked again with the same coefficient ring R, the same (identical) ring is returned. Keep in mind that this ring might already have more variables than supplied in varnames. Setting cached to false ensures a distinct new ring is returned, and will also prevent it from being cached.
Examples
julia> S, (x,y) = universal_laurent_polynomial_ring(ZZ, [:x,:y])
(Universal Laurent polynomial ring over Integers, UniversalRingElem{AbstractAlgebra.Generic.LaurentMPolyWrap{BigInt, AbstractAlgebra.Generic.MPoly{BigInt}, AbstractAlgebra.Generic.LaurentMPolyWrapRing{BigInt, AbstractAlgebra.Generic.MPolyRing{BigInt}}}, BigInt}[x, y])
julia> z = gen(S, :z)
z
julia> x*y - z
x*y - z
julia> S = universal_laurent_polynomial_ring(ZZ)
Universal Laurent polynomial ring over Integers
julia> x = gen(S, :x)
x
julia> y, z = gens(S, [:y, :z])
2-element Vector{UniversalRingElem{AbstractAlgebra.Generic.LaurentMPolyWrap{BigInt, AbstractAlgebra.Generic.MPoly{BigInt}, AbstractAlgebra.Generic.LaurentMPolyWrapRing{BigInt, AbstractAlgebra.Generic.MPolyRing{BigInt}}}, BigInt}}:
y
z
julia> x^(-1)*y - z
-z + x^-1*yAdding variables
There are two ways to add variables to a universal ring S.
gen(S::UniversalRing, var::VarName)
gens(S::UniversalRing, vars::Vector{VarName})Examples
julia> S = universal_polynomial_ring(ZZ)
Universal polynomial ring over Integers
julia> x = gen(S, :x)
x
julia> number_of_generators(S)
1
julia> y, z = gens(S, [:y, :z])
2-element Vector{UniversalRingElem{AbstractAlgebra.Generic.MPoly{BigInt}, BigInt}}:
y
z
julia> number_of_generators(S)
3Implement universal rings
To be able to use a ring as a base ring of an universal ring one has to implement a few methods. In addition to the variable and coefficient related methods like gen, gens, symbols, coefficient_ring there are the two internal methods _add_gens and _upgrade used to extend the number of variables.
AbstractAlgebra._add_gens — Function
_add_gens(R::MPolyRing, varnames::Vector{Symbol})Return a new uncached multivariate polynomial ring which has the same properties as R but varnames as additional generators.
_add_gens(R::LaurentMPolyWrapRing, varnames::Vector{Symbol})Return a new uncached multivariate Laurent polynomial ring which has the same properties as R but varnames as additional generators.
AbstractAlgebra._upgrade — Function
_upgrade(p::MPolyRingElem{T}, R::MPolyRing{T}) where {T}Return an element of R which is obtained from p by mapping the $i$-th variable of parent(p) to the $i$-th variable of R. For this to work, R needs to have at least as many variables as parent(p).
_upgrade(p::LaurentMPolyWrap{T}, R::LaurentMPolyRingWrap{T}) where {T}Return an element of R which is obtained from p by mapping the $i$-th variable of parent(p) to the $i$-th variable of R. For this to work, R needs to have at least as many variables as parent(p).
Hashing
To be able to use subtypes of UniversalRingElem efficiently as keys of a dictionary or similar applications, it is necessary to implement a custom hash function. The results should not depend on the number of variables currently in the parent. An example implementation can be found in src/UnivPoly.jl