# Ring functionality

AbstractAlgebra has both commutative and noncommutative rings. Together we refer to them below as rings.

## Abstract types for rings

All commutative ring types in AbstractAlgebra belong to the `Ring`

abstract type and commutative ring elements belong to the `RingElem`

abstract type.

Noncommutative ring types belong to the `NCRing`

abstract type and their elements to `NCRingElem`

.

As Julia types cannot belong to our `RingElem`

type hierarchy, we also provide the union type `RingElement`

which includes `RingElem`

in union with the Julia types `Integer`

, `Rational`

and `AbstractFloat`

.

Similarly `NCRingElement`

includes the Julia types just mentioned in union with `NCRingElem`

.

Note that

```
Ring <: NCRing
RingElem <: NCRingElem
RingElement <: NCRingElement
```

## Functions for types and parents of rings

```
parent_type(::Type{T}) where T <: NCRingElement
elem_type(::Type{T}) where T <: NCRing
```

Return the type of the parent (resp. element) type corresponding to the given ring element (resp. parent) type.

```
base_ring(R::NCRing)
base_ring(a::NCRingElement)
```

For generic ring constructions over a base ring (e.g. polynomials over a coefficient ring), return the parent object of that base ring.

`parent(a::NCRingElement)`

Return the parent of the given ring element.

```
is_domain_type(::Type{T}) where T <: NCRingElement
is_exact_type(::Type{T}) where T <: NCRingElement
```

Return true if the given ring element type can only belong to elements of an integral domain or exact ring respectively. (An exact ring is one whose elements are represented exactly in the system without approximation.)

The following function is implemented where mathematically and algorithmically possible.

`characteristic(R::NCRing)`

## Constructors

If `R`

is a parent object of a ring in AbstractAlgebra, it can always be used to construct certain objects in that ring.

```
(R::NCRing)() # constructs zero
(R::NCRing)(c::Integer)
(R::NCRing)(c::elem_type(R))
(R::NCRing{T})(a::T) where T <: RingElement
```

## Basic functions

All rings in AbstractAlgebra are expected to implement basic ring operations, unary minus, binary addition, subtraction and multiplication, equality testing, powering.

In addition, the following are implemented for parents/elements just as they would be in Julia for types/objects.

```
zero(R::NCRing)
one(R::NCRing)
iszero(a::NCRingElement)
isone(a::NCRingElement)
```

In addition, the following are implemented where it is mathematically/algorithmically viable to do so.

```
is_unit(a::NCRingElement)
is_zero_divisor(a::NCRingElement)
is_zero_divisor_with_annihilator(a::NCRingElement)
```

The following standard Julia functions are also implemented for all ring elements.

```
hash(f::RingElement, h::UInt)
deepcopy_internal(a::RingElement, dict::IdDict)
show(io::IO, R::NCRing)
show(io::IO, a::NCRingElement)
```

## Basic functionality for inexact rings only

By default, inexact ring elements in AbstractAlgebra compare equal if they are the same to the minimum precision of the two elements. However, we also provide the following more strict notion of equality, which also requires the precisions to be the same.

`isequal(a::T, b::T) where T <: NCRingElement`

For floating point and ball arithmetic it is sometimes useful to be able to check if two elements are approximately equal, e.g. to suppress numerical noise in comparisons. For this, the following are provided.

`isapprox(a::T, b::T; atol::Real=sqrt(eps())) where T <: RingElement`

Similarly, for a parameterised ring with type `MyElem{T}`

over such an inexact ring we have the following.

```
isapprox(a::MyElem{T}, b::T; atol::Real=sqrt(eps())) where T <: RingElement
isapprox(a::T, b::MyElem{T}; atol::Real=sqrt(eps())) where T <: RingElement
```

These notionally perform a coercion into the parameterised ring before doing the approximate equality test.

## Basic functionality for commutative rings only

```
divexact(a::T, b::T) where T <: RingElement
inv(a::T)
```

Return `a/b`

or `1/a`

respectively, where the slash here refers to the mathematical notion of division in the ring, not Julia's floating point division operator.

## Basic functionality for noncommutative rings only

```
divexact_left(a::T, b::T) where T <: NCRingElement
divexact_right(a::T, b::T) where T <: NCRingElement
```

As per `divexact`

above, except that division by `b`

happens on the left or right, respectively, of `a`

.

## Unsafe ring 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!`

— Function`zero!(a)`

Return `zero(parent(a))`

, possibly modifying the object `a`

in the process.

`one!`

— Function`one!(a)`

Return `one(parent(a))`

, possibly modifying the object `a`

in the process.

`add!`

— Function```
add!(z, a, b)
add!(a, b)
```

Return `a + b`

, possibly modifying the object `z`

in the process. Aliasing is permitted. The two argument version is a shorthand for `add!(a, a, b)`

.

`sub!`

— Function```
sub!(z, a, b)
sub!(a, b)
```

Return `a - b`

, possibly modifying the object `z`

in the process. Aliasing is permitted. The two argument version is a shorthand for `sub!(a, a, b)`

.

`mul!`

— Function```
mul!(z, a, b)
mul!(a, b)
```

Return `a * b`

, possibly modifying the object `z`

in the process. Aliasing is permitted. The two argument version is a shorthand for `mul!(a, a, b)`

.

`neg!`

— Function```
neg!(z, a)
neg!(a)
```

Return `-a`

, possibly modifying the object `z`

in the process. Aliasing is permitted. The unary version is a shorthand for `neg!(a, a)`

.

`inv!`

— Function```
inv!(z, a)
inv!(a)
```

Return `AbstractAlgebra.inv(a)`

, possibly modifying the object `z`

in the process. Aliasing is permitted. The unary version is a shorthand for `inv!(a, a)`

.

`AbstractAlgebra.inv`

and `Base.inv`

differ only in their behavior on julia types like `Integer`

and `Rational{Int}`

. The former makes it adhere to the Ring interface.

`addmul!`

— Function```
addmul!(z, a, b, t)
addmul!(z, a, b)
```

Return `z + a * b`

, possibly modifying the objects `z`

and `t`

in the process.

The second version is usually a shorthand for `addmul!(z, a, b, parent(z)())`

, but in some cases may be more efficient. For multiple operations in a row that use temporary storage, it is still best to use the four argument version.

`submul!`

— Function```
submul!(z, a, b, t)
submul!(z, a, b)
```

Return `z - a * b`

, possibly modifying the objects `z`

and `t`

in the process.

The second version is usually a shorthand for `submul!(z, a, b, parent(z)())`

, but in some cases may be more efficient. For multiple operations in a row that use temporary storage, it is still best to use the four argument version.

`divexact!`

— Function`divexact!(A::Generic.Mat{AbsSimpleNumFieldElem}, p::ZZRingElem)`

Inplace: divide each entry of $A$ by $p$.

```
divexact!(z, a, b)
divexact!(a, b)
```

Return `divexact(a, b)`

, possibly modifying the object `z`

in the process. Aliasing is permitted. The two argument version is a shorthand for `divexact(a, a, b)`

.

`div!`

— Function```
div!(z, a, b)
div!(a, b)
```

Return `div(a, b)`

, possibly modifying the object `z`

in the process. Aliasing is permitted. The two argument version is a shorthand for `div(a, a, b)`

.

`AbstractAlgebra.div`

and `Base.div`

differ only in their behavior on julia types like `Integer`

and `Rational{Int}`

. The former makes it adhere to the Ring interface.

`rem!`

— Function```
rem!(z, a, b)
rem!(a, b)
```

Return `rem(a, b)`

, possibly modifying the object `z`

in the process. Aliasing is permitted. The two argument version is a shorthand for `rem(a, a, b)`

.

`mod!`

— Function`mod!(M::ZZMatrix, p::ZZRingElem)`

Reduces every entry modulo $p$ in-place, i.e. applies the mod function to every entry. Positive residue system.

`mod!(A::Generic.Mat{AbsSimpleNumFieldElem}, m::ZZRingElem)`

Inplace: reduce all entries of $A$ modulo $m$, into the positive residue system.

```
mod!(z, a, b)
mod!(a, b)
```

Return `mod(a, b)`

, possibly modifying the object `z`

in the process. Aliasing is permitted. The two argument version is a shorthand for `mod(a, a, b)`

.

`mod!(A::SRow{ZZRingElem}, n::Integer) -> SRow{ZZRingElem}`

Inplace reduction of all entries of $A$ modulo $n$ to the positive residue system.

`mod!(A::SRow{ZZRingElem}, n::ZZRingElem) -> SRow{ZZRingElem}`

Inplace reduction of all entries of $A$ modulo $n$ to the positive residue system.

`gcd!`

— Function```
gcd!(z, a, b)
gcd!(a, b)
```

Return `gcd(a, b)`

, possibly modifying the object `z`

in the process. Aliasing is permitted. The two argument version is a shorthand for `gcd(a, a, b)`

.

`lcm!`

— Function```
lcm!(z, a, b)
lcm!(a, b)
```

Return `lcm(a, b)`

, possibly modifying the object `z`

in the process. Aliasing is permitted. The two argument version is a shorthand for `lcm(a, a, b)`

.

## Random generation

The Julia random interface is implemented for all ring parents (instead of for types). The exact interface differs depending on the ring, but the parameters supplied are usually ranges, e.g. `-1:10`

for the range of allowed degrees for a univariate polynomial.

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

## Factorization

For commutative rings supporting factorization and irreducibility testing, the following optional functions may be implemented.

`is_irreducible`

— Method`is_irreducible(a::RingElement)`

Return `true`

if $a$ is irreducible, else return `false`

. Zero and units are by definition never irreducible.

`is_squarefree`

— Method`is_squarefree(a::RingElement)`

Return `true`

if $a$ is squarefree, else return `false`

. An element is squarefree if it it is not divisible by any squares except the squares of units.

```
factor(a::T) where T <: RingElement
factor_squarefree(a::T) where T <: RingElement
```

Return a factorization into irreducible or squarefree elements, respectively. The return is an object of type `Fac{T}`

.

`Fac`

— Type`Fac{T <: RingElement}`

Type for factored ring elements. The structure holds a unit of type `T`

and is an iterable collection of `T => Int`

pairs for the factors and exponents.

See `unit(a::Fac)`

, `evaluate(a::Fac)`

.

`unit`

— Method`unit(a::Fac{T}) -> T`

Return the unit of the factorization.

`evaluate`

— Method`evaluate(a::Fac{T}) -> T`

Multiply out the factorization into a single element.

`getindex`

— Method`getindex(a::Fac, b) -> Int`

If $b$ is a factor of $a$, the corresponding exponent is returned. Otherwise an error is thrown.

`setindex!`

— Method`setindex!(a::Fac{T}, c::Int, b::T)`

If $b$ is a factor of $a$, the corresponding entry is set to $c$.