# Ring Interface

AbstractAlgebra.jl generic code makes use of a standardised set of functions which it expects to be implemented for all rings. Here we document this interface. All libraries which want to make use of the generic capabilities of AbstractAlgebra.jl must supply all of the required functionality for their rings.

In addition to the required functions, there are also optional functions which can be provided for certain types of rings, e.g. GCD domains or fields, etc. If implemented, these allow the generic code to provide additional functionality for those rings, or in some cases, to select more efficient algorithms.

## Types

Most rings must supply two types:

- a type for the parent object (representing the ring itself)
- a type for elements of that ring

For example, the generic univariate polynomial type in AbstractAlgebra.jl provides two types in generic/GenericTypes.jl:

`Generic.PolyRing{T}`

for the parent objects`Generic.Poly{T}`

for the actual polynomials

The parent type must belong to `Ring`

and the element type must belong to `RingElem`

. Of course, the types may belong to these abstract types transitively, e.g. `Poly{T}`

actually belongs to `PolyRingElem{T}`

which in turn belongs to `RingElem`

.

For parameterised rings, we advise that the types of both the parent objects and element objects to be parameterised by the types of the elements of the base ring (see the function `base_ring`

below for a definition).

There can be variations on this theme: e.g. in some areas of mathematics there is a notion of a coefficient domain, in which case it may make sense to parameterise all types by the type of elements of this coefficient domain. But note that this may have implications for the ad hoc operators one might like to explicitly implement.

## RingElement type union

Because of its lack of multiple inheritance, Julia does not allow Julia Base types to belong to `RingElem`

. To allow us to work equally with AbstractAlgebra and Julia types that represent elements of rings we define a union type `RingElement`

in `src/julia/JuliaTypes`

.

So far, in addition to `RingElem`

the union type `RingElement`

includes the Julia types `Integer`

, `Rational`

and `AbstractFloat`

.

Most of the generic code in AbstractAlgebra makes use of the union type `RingElement`

instead of `RingElem`

so that the generic functions also accept the Julia Base ring types.

One must be careful when defining ad hoc binary operations for ring element types. It is often necessary to define separate versions of the functions for `RingElem`

then for each of the Julia types separately in order to avoid ambiguity warnings.

Note that even though `RingElement`

is a union type we still have the following inclusion

`RingElement <: NCRingElement`

## Parent object caches

In many cases, it is desirable to have only one object in the system to represent each ring. This means that if the same ring is constructed twice, elements of the two rings will be compatible as far as arithmetic is concerned.

In order to facilitate this, global caches of rings are stored in AbstractAlgebra.jl, usually implemented using dictionaries. For example, the `Generic.PolyRing`

parent objects are looked up in a dictionary `PolyID`

to see if they have been previously defined.

Whether these global caches are provided or not, depends on both mathematical and algorithmic considerations. E.g. in the case of number fields, it isn't desirable to identify all number fields with the same defining polynomial, as they may be considered with distinct embeddings into one another. In other cases, identifying whether two rings are the same may be prohibitively expensive. Generally, it may only make sense algorithmically to identify two rings if they were constructed from identical data.

If a global cache is provided, it must be optionally possible to construct the parent objects without caching. This is done by passing a boolean value `cached`

to the inner constructor of the parent object. See `src/generic/GenericTypes.jl`

for examples of how to construct and handle such caches.

## Required functions for all rings

In the following, we list all the functions that are required to be provided for rings in AbstractAlgebra.jl or by external libraries wanting to use AbstractAlgebra.jl.

We give this interface for fictitious types `MyParent`

for the type of the ring parent object `R`

and `MyElem`

for the type of the elements of the ring.

Generic functions in AbstractAlgebra.jl may not rely on the existence of functions that are not documented here. If they do, those functions will only be available for rings that implement that additional functionality, and should be documented as such.

### Data type and parent object methods

`parent_type(::Type{MyElem})`

Return the type of the corresponding parent object for the given element type. For example, `parent_type(Generic.Poly{T})`

will return `Generic.PolyRing{T}`

.

`elem_type(::Type{MyParent})`

Return the type of the elements of the ring whose parent object has the given type. This is the inverse of the `parent_type`

function, i.e. `elem_type(Generic.PolyRing{T})`

will return `Generic.Poly{T}`

.

`base_ring_type(::Type{MyParent})`

Return the type of the of base rings for parent objects with the given parent type. For example, `base_ring_type(Generic.PolyRing{T})`

will return `parent_type(T)`

.

`base_ring(R::MyParent)`

Given a parent object `R`

, representing a ring, this function returns the parent object of any base ring that parameterises this ring. For example, the base ring of the ring of polynomials over the integers would be the integer ring.

If the ring is not parameterised by another ring, this function must return `Union{}`

.

There is a distinction between a base ring and other kinds of parameters. For example, in the ring $\mathbb{Z}/n\mathbb{Z}$, the modulus $n$ is a parameter, but the only base ring is $\mathbb{Z}$. We consider the ring $\mathbb{Z}/n\mathbb{Z}$ to have been constructed from the base ring $\mathbb{Z}$ by taking its quotient by a (principal) ideal.

`parent(f::MyElem)`

Return the parent object of the given element, i.e. return the ring to which the given element belongs.

This is usually stored in a field `parent`

in each ring element. (If the parent objects have `mutable struct`

types, the internal overhead here is just an additional machine pointer stored in each element of the ring.)

For some element types it isn't necessary to append the parent object as a field of every element. This is the case when the parent object can be reconstructed just given the type of the elements. For example, this is the case for the ring of integers and in fact for any ring element type that isn't parameterised or generic in any way.

`is_domain_type(::Type{MyElem})`

Return `true`

if every element of the given element type (which may be parameterised or an abstract type) necessarily has a parent that is an integral domain, otherwise if this cannot be guaranteed, the function returns `false`

.

For example, if `MyElem`

was the type of elements of generic residue rings of a polynomial ring, the answer to the question would depend on the modulus of the residue ring. Therefore `is_domain_type`

would have to return `false`

, since we cannot guarantee that we are dealing with elements of an integral domain in general. But if the given element type was for rational integers, the answer would be `true`

, since every rational integer has as parent the ring of rational integers, which is an integral domain.

Note that this function depends only on the type of an element and cannot access information about the object itself, or its parent.

`is_exact_type(::Type{MyElem})`

Return `true`

if every element of the given type is represented exactly. For example, $p$-adic numbers, real and complex floating point numbers and power series are not exact, as we can only represent them in general with finite truncations. Similarly polynomials and matrices over inexact element types are themselves inexact.

Integers, rationals, finite fields and polynomials and matrices over them are always exact.

Note that `MyElem`

may be parameterised or an abstract type, in which case every element of every type represented by `MyElem`

must be exact, otherwise the function must return `false`

.

`Base.hash(f::MyElem, h::UInt)`

Return a hash for the object $f$ of type `UInt`

. This is used as a hopefully cheap way to distinguish objects that differ arithmetically.

If the object has components, e.g. the coefficients of a polynomial or elements of a matrix, these should be hashed recursively, passing the same parameter `h`

to all levels. Each component should then be xor'd with `h`

before combining the individual component hashes to give the final hash.

The hash functions in AbstractAlgebra.jl usually start from some fixed 64 bit hexadecimal value that has been picked at random by the library author for that type. That is then truncated to fit a `UInt`

(in case the latter is not 64 bits). This ensures that objects that are the same arithmetically (or that have the same components), but have different types (or structures), are unlikely to hash to the same value.

`deepcopy_internal(f::MyElem, dict::IdDict)`

Return a copy of the given element, recursively copying all components of the object.

Obviously the parent, if it is stored in the element, should not be copied. The new element should have precisely the same parent as the old object.

For types that cannot self-reference themselves anywhere internally, the `dict`

argument may be ignored.

In the case that internal self-references are possible, please consult the Julia documentation on how to implement `deepcopy_internal`

.

### Constructors

Outer constructors for most AbstractAlgebra types are provided by overloading the call syntax for parent objects.

If `R`

is a parent object for a given ring we require the following constructors.

`(R::MyParent)()`

Return the zero object of the given ring.

`(R::MyParent)(a::Integer)`

Coerce the given integer into the given ring.

`(R::MyParent)(a::MyElem)`

If $a$ belongs to the given ring, the function returns it (without making a copy). Otherwise an error is thrown.

For parameterised rings we also require a function to coerce from the base ring into the parent ring.

`(R::MyParent{T})(a::T) where T <: RingElem`

Coerce $a$ into the ring $R$ if $a$ belongs to the base ring of $R$.

### Basic manipulation of rings and elements

`zero(R::MyParent)`

Return the zero element of the given ring.

`one(R::MyParent)`

Return the multiplicative identity of the given ring.

`iszero(f::MyElem)`

Return `true`

if the given element is the zero element of the ring it belongs to.

`isone(f::MyElem)`

Return `true`

if the given element is the multiplicative identity of the ring it belongs to.

### Canonicalisation

`canonical_unit(f::MyElem)`

When fractions are created with two elements of the given type, it is nice to be able to represent them in some kind of canonical form. This is of course not always possible. But for example, fractions of integers can be canonicalised by first removing any common factors of the numerator and denominator, then making the denominator positive.

In AbstractAlgebra.jl, the denominator would be made positive by dividing both the numerator and denominator by the canonical unit of the denominator. For a negative denominator, this would be $-1$.

For elements of a field, `canonical_unit`

simply returns the element itself. In general, `canonical_unit`

of an invertible element should be that element. Finally, if $a = ub$ we should have the identity `canonical_unit(a) = canonical_unit(u)*canonical_unit(b)`

.

For some rings, it is completely impractical to implement this function, in which case it may return $1$ in the given ring. The function must however always exist, and always return an element of the ring.

### String I/O

`show(io::IO, R::MyParent)`

This should print an English description of the parent ring (to the given IO object). If the ring is parameterised, it can call the corresponding `show`

function for any rings it depends on.

`show(io::IO, f::MyElem)`

This should print a human readable, textual representation of the object (to the given IO object). It can recursively call the corresponding `show`

functions for any of its components.

### Expressions

To obtain best results when printing composed types derived from other types, e.g., polynomials, the following method should be implemented.

`expressify(f::MyElem; context = nothing)`

which must return either `Expr`

, `Symbol`

, `Integer`

or `String`

.

For a type which implements `expressify`

, one can automatically derive `show`

methods supporting output as plain text, LaTeX and `html`

by using the following:

`@enable_all_show_via_expressify MyElem`

This defines the following show methods for the specified type `MyElem`

:

```
function Base.show(io::IO, a::MyElem)
show_via_expressify(io, a)
end
function Base.show(io::IO, mi::MIME"text/plain", a::MyElem)
show_via_expressify(io, mi, a)
end
function Base.show(io::IO, mi::MIME"text/latex", a::MyElem)
show_via_expressify(io, mi, a)
end
function Base.show(io::IO, mi::MIME"text/html", a::MyElem)
show_via_expressify(io, mi, a)
end
```

As an example, assume that an object `f`

of type `MyElem`

has two components `f.a`

and `f.b`

of integer type, which should be printed as `a^b`

, this can be implemented as

`expressify(f::MyElem; context = nothing) = Expr(:call, :^, f.a, f.b)`

If `f.a`

and `f.b`

themselves are objects that can be expressified, this can be implemented as

```
function expressify(f::MyElem; context = nothing)
return Expr(:call, :^, expressify(f.a, context = context),
expressify(f.b, context = context))
end
```

As noted above, expressify should return an `Expr`

, `Symbol`

, `Integer`

or `String`

. The rendering of such expressions with a particular MIME type to an output context is controlled by the following rules which are subject to change slightly in future versions of AbstracAlgebra.

`Integer`

: The printing of integers is straightforward and automatically includes transformations such as `1 + (-2)*x => 1 - 2*x`

as this is cumbersome to implement per-type.

`Symbol`

: Since variable names are stored as mere symbols in AbstractAlgebra, some transformations related to subscripts are applied to symbols automatically in latex output. The `\operatorname{`

in the following table is actually replaced with the more portable `\mathop{\mathrm{`

.

expressify | latex output |
---|---|

`Symbol("a")` | `a` |

`Symbol("α")` | `{\alpha}` |

`Symbol("x1")` | `\operatorname{x1}` |

`Symbol("xy_1")` | `\operatorname{xy}_{1}` |

`Symbol("sin")` | `\operatorname{sin}` |

`Symbol("sin_cos")` | `\operatorname{sin\_cos}` |

`Symbol("sin_1")` | `\operatorname{sin}_{1}` |

`Symbol("sin_cos_1")` | `\operatorname{sin\_cos}_{1}` |

`Symbol("αaβb_1_2")` | `\operatorname{{\alpha}a{\beta}b}_{1,2}` |

`Expr`

: These are the most versatile as the `Expr`

objects themselves contain a symbolic head and any number of arguments. What looks like `f(a,b)`

in textual output is `Expr(:call, :f, :a, :b)`

under the hood. AbstractAlgebra currently contains the following printing rules for such expressions.

expressify | output | latex notes |
---|---|---|

`Expr(:call, :+, a, b)` | `a + b` | |

`Expr(:call, :*, a, b)` | `a*b` | one space for implied multiplication |

`Expr(:call, :cdot, a, b)` | `a * b` | a real `\cdot` is used |

`Expr(:call, :^, a, b)` | `a^b` | may include some courtesy parentheses |

`Expr(:call, ://, a, b)` | `a//b` | will create a fraction box |

`Expr(:call, :/, a, b)` | `a/b` | will not create a fraction box |

`Expr(:call, a, b, c)` | `a(b, c)` | |

`Expr(:ref, a, b, c)` | `a[b, c]` | |

`Expr(:vcat, a, b)` | `[a; b]` | actually vertical |

`Expr(:vect, a, b)` | `[a, b]` | |

`Expr(:tuple, a, b)` | `(a, b)` | |

`Expr(:list, a, b)` | `{a, b}` | |

`Expr(:series, a, b)` | `a, b` | |

`Expr(:sequence, a, b)` | `ab` | |

`Expr(:row, a, b)` | `a b` | combine with `:vcat` to make matrices |

`Expr(:hcat, a, b)` | `a b` |

`String`

: Strings are printed verbatim and should only be used as a last resort as they provide absolutely no precedence information on their contents.

### Unary operations

`-(f::MyElem)`

Return $-f$.

### Binary operations

```
+(f::MyElem, g::MyElem)
-(f::MyElem, g::MyElem)
*(f::MyElem, g::MyElem)
```

Return $f + g$, $f - g$ or $fg$, respectively.

### Comparison

`==(f::MyElem, g::MyElem)`

Return `true`

if $f$ and $g$ are arithmetically equal. In the case where the two elements are inexact, the function returns `true`

if they agree to the minimum precision of the two.

`isequal(f::MyElem, g::MyElem)`

For exact rings, this should return the same thing as `==`

above. For inexact rings, this returns `true`

only if the two elements are arithmetically equal and have the same precision.

### Powering

`^(f::MyElem, e::Int)`

Return $f^e$. The function should throw a `DomainError()`

if negative exponents don't make sense but are passed to the function.

### Exact division

`divexact(f::MyElem, g::MyElem; check::Bool=true)`

Return $f/g$, though note that Julia uses `/`

for floating point division. Here we mean exact division in the ring, i.e. return $q$ such that $f = gq$. A `DivideError()`

should be thrown if $g$ is zero.

If `check=true`

the function should check that the division is exact and throw an exception if not.

If `check=false`

the check may be omitted for performance reasons. The behaviour is then undefined if a division is performed that is not exact. This may include throwing an exception, returning meaningless results, hanging or crashing. The function should only be called with `check=false`

if it is already known that the division will be exact.

### Inverse

`inv(f::MyElem)`

Return the inverse of $f$, i.e. $1/f$, though note that Julia uses `/`

for floating point division. Here we mean exact division in the ring.

A fallback for this function is provided in terms of `divexact`

so an implementation can be omitted if preferred.

### Unsafe operators

To speed up polynomial and matrix arithmetic, it sometimes makes sense to mutate values in place rather than replace them with a newly created object every time they are modified.

For this purpose, certain mutating operators are required. In order to support immutable types (struct in Julia) and systems that don't have in-place operators, all unsafe operators must return the (ostensibly) mutated value. Only the returned value is used in computations, so this lifts the requirement that the unsafe operators actually mutate the value.

Note the exclamation point is a convention, which indicates that the object may be mutated in-place.

To make use of these functions, one must be certain that no other references are held to the object being mutated, otherwise those values will also be changed!

The results of `deepcopy`

and all arithmetic operations, including powering and division can be assumed to be new objects without other references being held, as can objects returned from constructors.

It is important to recognise that `R(a)`

where `R`

is the ring `a`

belongs to, does not create a new value. For this case, use `deepcopy(a)`

.

`zero!(f::MyElem)`

Set the value $f$ to zero in place. Return the mutated value.

`mul!(c::MyElem, a::MyElem, b::MyElem)`

Set $c$ to the value $ab$ in place. Return the mutated value. Aliasing is permitted.

`add!(c::MyElem, a::MyElem, b::MyElem)`

Set $c$ to the value $a + b$ in place. Return the mutated value. Aliasing is permitted.

`addeq!(a::MyElem, b::MyElem)`

Set $a$ to $a + b$ in place. Return the mutated value. Aliasing is permitted.

### Random generation

The random functions are only used for test code to generate test data. They therefore don't need to provide any guarantees on uniformity, and in fact, test values that are known to be a good source of corner cases can be supplied.

`rand(R::MyParent, v...)`

Return a random element in the given ring of the specified size.

There can be as many arguments as is necessary to specify the size of the test example which is being produced.

### Promotion rules

AbstractAlgebra currently has a very simple coercion model. With few exceptions only simple coercions are supported. For example if $x \in \mathbb{Z}$ and $y \in \mathbb{Z}[x]$ then $x + y$ can be computed by coercing $x$ into the same ring as $y$ and then adding in that ring.

Complex coercions such as adding elements of $\mathbb{Q}$ and $\mathbb{Z}[x]$ are not supported, as this would require finding and creating a common overring in which the elements could be added.

AbstractAlgebra supports simple coercions by overloading parent object call syntax `R(x)`

to coerce the object `x`

into the ring `R`

. However, to coerce elements up a tower of rings, one needs to also have a promotion system similar to Julia's type promotion system.

As for Julia, AbstractAlgebra's promotion system only specifies what happens to types. It is the coercions themselves that must deal with the mathematical situation at the level of rings, including checking that the object can even be coerced into the given ring.

We now describe the required AbstractAlgebra type promotion rules.

For every ring, one wants to be able to coerce integers into the ring. And for any ring constructed over a base ring, one would like to be able to coerce from the base ring into the ring.

The required promotion rules to support this look a bit different depending on whether the element type is parameterised or not and whether it is built on a base ring.

For ring element types `MyElem`

that are neither parameterised nor built over a base ring, the promotion rules can be defined as follows:

`promote_rule(::Type{MyElem}, ::Type{T}) where {T <: Integer} = MyElem`

For ring element types `MyElem`

that aren't parameterised, but which have a base ring with concrete element type `T`

the promotion rules can be defined as follows:

`promote_rule(::Type{MyElem}, ::Type{U}) where U <: Integer = MyElem`

`promote_rule(::Type{MyElem}, ::Type{T}) = MyElem`

For ring element types `MyElem{T}`

that are parameterised by the type of elements of the base ring, the promotion rules can be defined as follows:

`promote_rule(::Type{MyElem{T}}, ::Type{MyElem{T}}) where T <: RingElement = MyElem{T}`

```
function promote_rule(::Type{MyElem{T}}, ::Type{U}) where {T <: RingElement, U <: RingElement}
promote_rule(T, U) == T ? MyElem{T} : Union{}
end
```

## Required functionality for inexact rings

### Approximation (floating point and ball arithmetic only)

`isapprox(f::MyElem, g::MyElem; atol::Real=sqrt(eps()))`

This is used by test code that uses rings involving floating point or ball arithmetic. The function should return `true`

if all components of $f$ and $g$ are equal to within the square root of the Julia epsilon, since numerical noise may make an exact comparison impossible.

For parameterised rings over an inexact ring, we also require the following ad hoc approximation functionality.

`isapprox(f::MyElem{T}, g::T; atol::Real=sqrt(eps())) where T <: RingElem`

`isapprox(f::T, g::MyElem{T}; atol::Real=sqrt(eps())) where T <: RingElem`

These notionally coerce the element of the base ring into the parameterised ring and do a full comparison.

## Optional functionality

Some functionality is difficult or impossible to implement for all rings in the system. If it is provided, additional functionality or performance may become available. Here is a list of all functions that are considered optional and can't be relied on by generic functions in the AbstractAlgebra Ring interface.

It may be that no algorithm, or no efficient algorithm is known to implement these functions. As these functions are optional, they do not need to exist. Julia will already inform the user that the function has not been implemented if it is called but doesn't exist.

### Optional basic manipulation functionality

`is_unit(f::MyElem)`

Return `true`

if the given element is a unit in the ring it belongs to.

`is_zero_divisor(f::MyElem)`

Return `true`

if the given element is a zero divisor in the ring it belongs to. When this function does not exist for a given ring then the total ring of fractions may not be usable over that ring. All fields in the system have a fallback defined for this function.

`characteristic(R::MyParent)`

Return the characteristic of the ring. The function should not be defined if it is not possible to unconditionally give the characteristic. AbstractAlgebra will raise an exception is such cases.

### Optional binary ad hoc operators

By default, ad hoc operations are handled by AbstractAlgebra.jl if they are not defined explicitly, by coercing both operands into the same ring and then performing the required operation.

In some cases, e.g. for matrices, this leads to very inefficient behaviour. In such cases, it is advised to implement some of these operators explicitly.

It can occasionally be worth adding a separate set of ad hoc binary operators for the type `Int`

, if this can be done more efficiently than for arbitrary Julia Integer types.

```
+(f::MyElem, c::Integer)
-(f::MyElem, c::Integer)
*(f::MyElem, c::Integer)
```

```
+(c::Integer, f::MyElem)
-(c::Integer, f::MyElem)
*(c::Integer, f::MyElem)
```

For parameterised types, it is also sometimes more performant to provide explicit ad hoc operators with elements of the base ring.

```
+(f::MyElem{T}, c::T) where T <: RingElem
-(f::MyElem{T}, c::T) where T <: RingElem
*(f::MyElem{T}, c::T) where T <: RingElem
```

```
+(c::T, f::MyElem{T}) where T <: RingElem
-(c::T, f::MyElem{T}) where T <: RingElem
*(c::T, f::MyElem{T}) where T <: RingElem
```

### Optional ad hoc comparisons

`==(f::MyElem, c::Integer)`

`==(c::Integer, f::MyElem)`

`==(f::MyElem{T}, c:T) where T <: RingElem`

`==(c::T, f::MyElem{T}) where T <: RingElem`

### Optional ad hoc exact division functions

`divexact(a::MyElem{T}, b::T) where T <: RingElem`

`divexact(a::MyElem, b::Integer)`

### Optional powering functions

`^(f::MyElem, e::BigInt)`

In case $f$ cannot explode in size when powered by a very large integer, and it is practical to do so, one may provide this function to support powering with `BigInt`

exponents (or for external modules, any other big integer type).

### Optional unsafe operators

`addmul!(c::MyElem, a::MyElem, b::MyElem, t::MyElem)`

Set $c = c + ab$ in-place. Return the mutated value. The value $t$ should be a temporary of the same type as $a$, $b$ and $c$, which can be used arbitrarily by the implementation to speed up the computation. Aliasing between $a$, $b$ and $c$ is permitted.

## Minimal example of ring implementation

Here is a minimal example of implementing the Ring Interface for a constant polynomial type (i.e. polynomials of degree less than one).

```
# ConstPoly.jl : Implements constant polynomials
using AbstractAlgebra
using Random: Random, SamplerTrivial, GLOBAL_RNG
using RandomExtensions: RandomExtensions, Make2, AbstractRNG
import AbstractAlgebra: parent_type, elem_type, base_ring, base_ring_type, parent, is_domain_type,
is_exact_type, canonical_unit, isequal, divexact, zero!, mul!, add!, addeq!,
get_cached!, is_unit, characteristic, Ring, RingElem, expressify
import Base: show, +, -, *, ^, ==, inv, isone, iszero, one, zero, rand,
deepcopy_internal, hash
mutable struct ConstPolyRing{T <: RingElement} <: Ring
base_ring::Ring
function ConstPolyRing{T}(R::Ring, cached::Bool) where T <: RingElement
return get_cached!(ConstPolyID, R, cached) do
new{T}(R)
end::ConstPolyRing{T}
end
end
const ConstPolyID = AbstractAlgebra.CacheDictType{Ring, ConstPolyRing}()
mutable struct ConstPoly{T <: RingElement} <: RingElem
c::T
parent::ConstPolyRing{T}
function ConstPoly{T}(c::T) where T <: RingElement
return new(c)
end
end
# Data type and parent object methods
parent_type(::Type{ConstPoly{T}}) where T <: RingElement = ConstPolyRing{T}
elem_type(::Type{ConstPolyRing{T}}) where T <: RingElement = ConstPoly{T}
base_ring_type(::Type{ConstPolyRing{T}}) where T <: RingElement = parent_type(T)
base_ring(R::ConstPolyRing) = R.base_ring::base_ring_type(R)
parent(f::ConstPoly) = f.parent
is_domain_type(::Type{ConstPoly{T}}) where T <: RingElement = is_domain_type(T)
is_exact_type(::Type{ConstPoly{T}}) where T <: RingElement = is_exact_type(T)
function hash(f::ConstPoly, h::UInt)
r = 0x65125ab8e0cd44ca
return xor(r, hash(f.c, h))
end
function deepcopy_internal(f::ConstPoly{T}, dict::IdDict) where T <: RingElement
r = ConstPoly{T}(deepcopy_internal(f.c, dict))
r.parent = f.parent # parent should not be deepcopied
return r
end
# Basic manipulation
zero(R::ConstPolyRing) = R()
one(R::ConstPolyRing) = R(1)
iszero(f::ConstPoly) = iszero(f.c)
isone(f::ConstPoly) = isone(f.c)
is_unit(f::ConstPoly) = is_unit(f.c)
characteristic(R::ConstPolyRing) = characteristic(base_ring(R))
# Canonical unit
canonical_unit(f::ConstPoly) = canonical_unit(f.c)
# String I/O
function show(io::IO, R::ConstPolyRing)
print(io, "Constant polynomials over ")
show(io, base_ring(R))
end
function show(io::IO, f::ConstPoly)
print(io, f.c)
end
# Expressification (optional)
function expressify(R::ConstPolyRing; context = nothing)
return Expr(:sequence, Expr(:text, "Constant polynomials over "),
expressify(base_ring(R), context = context))
end
function expressify(f::ConstPoly; context = nothing)
return expressify(f.c, context = context)
end
# Unary operations
function -(f::ConstPoly)
R = parent(f)
return R(-f.c)
end
# Binary operations
function +(f::ConstPoly{T}, g::ConstPoly{T}) where T <: RingElement
check_parent(f, g)
R = parent(f)
return R(f.c + g.c)
end
function -(f::ConstPoly{T}, g::ConstPoly{T}) where T <: RingElement
check_parent(f, g)
R = parent(f)
return R(f.c - g.c)
end
function *(f::ConstPoly{T}, g::ConstPoly{T}) where T <: RingElement
check_parent(f, g)
R = parent(f)
return R(f.c*g.c)
end
# Comparison
function ==(f::ConstPoly{T}, g::ConstPoly{T}) where T <: RingElement
check_parent(f, g)
return f.c == g.c
end
function isequal(f::ConstPoly{T}, g::ConstPoly{T}) where T <: RingElement
check_parent(f, g)
return isequal(f.c, g.c)
end
# Powering need not be implemented if * is
# Exact division
function divexact(f::ConstPoly{T}, g::ConstPoly{T}; check::Bool = true) where T <: RingElement
check_parent(f, g)
R = parent(f)
return R(divexact(f.c, g.c, check = check))
end
# Inverse
function inv(f::ConstPoly)
R = parent(f)
return R(AbstractAlgebra.inv(f.c))
end
# Unsafe operators
function zero!(f::ConstPoly)
f.c = zero(base_ring(parent(f)))
return f
end
function mul!(f::ConstPoly{T}, g::ConstPoly{T}, h::ConstPoly{T}) where T <: RingElement
f.c = g.c*h.c
return f
end
function add!(f::ConstPoly{T}, g::ConstPoly{T}, h::ConstPoly{T}) where T <: RingElement
f.c = g.c + h.c
return f
end
function addeq!(f::ConstPoly{T}, g::ConstPoly{T}) where T <: RingElement
f.c += g.c
return f
end
# Random generation
RandomExtensions.maketype(R::ConstPolyRing, _) = elem_type(R)
rand(rng::AbstractRNG, sp::SamplerTrivial{<:Make2{ConstPoly,ConstPolyRing}}) =
sp[][1](rand(rng, sp[][2]))
rand(rng::AbstractRNG, R::ConstPolyRing, n::AbstractUnitRange{Int}) = R(rand(rng, n))
rand(R::ConstPolyRing, n::AbstractUnitRange{Int}) = rand(Random.GLOBAL_RNG, R, n)
# Promotion rules
promote_rule(::Type{ConstPoly{T}}, ::Type{ConstPoly{T}}) where T <: RingElement = ConstPoly{T}
function promote_rule(::Type{ConstPoly{T}}, ::Type{U}) where {T <: RingElement, U <: RingElement}
promote_rule(T, U) == T ? ConstPoly{T} : Union{}
end
# Constructors
function (R::ConstPolyRing{T})() where T <: RingElement
r = ConstPoly{T}(base_ring(R)(0))
r.parent = R
return r
end
function (R::ConstPolyRing{T})(c::Integer) where T <: RingElement
r = ConstPoly{T}(base_ring(R)(c))
r.parent = R
return r
end
# Needed to prevent ambiguity
function (R::ConstPolyRing{T})(c::T) where T <: Integer
r = ConstPoly{T}(base_ring(R)(c))
r.parent = R
return r
end
function (R::ConstPolyRing{T})(c::T) where T <: RingElement
base_ring(R) != parent(c) && error("Unable to coerce element")
r = ConstPoly{T}(c)
r.parent = R
return r
end
function (R::ConstPolyRing{T})(f::ConstPoly{T}) where T <: RingElement
R != parent(f) && error("Unable to coerce element")
return f
end
# Parent constructor
function constant_polynomial_ring(R::Ring, cached::Bool=true)
T = elem_type(R)
return ConstPolyRing{T}(R, cached)
end
```

The above implementation of `constant_polynomial_ring`

may be tested as follows.

```
using Test
include(joinpath(pathof(AbstractAlgebra), "..", "..", "test", "Rings-conformance-tests.jl"))
S, _ = polynomial_ring(QQ, "x")
function test_elem(R::ConstPolyRing{elem_type(S)})
return R(rand(base_ring(R), 1:6, -999:999))
end
test_Ring_interface(constant_polynomial_ring(S))
```