Module maths_traits::algebra::ring_like

Traits for structures with both an addition and multiplication operation

While ring-like structures can technically apply to any pair of operations, for ease of use and to stick with mathematical convention, these operations are taken to be specifically addition and multiplication where multiplication distributes over addition.

Implementation

This module build upon and behaves in a way similar to the group-like structures. However, in addition to the basic group traits, the following properties are also considered:

• Distributivity:
  • Multiplication can act on summed elements independently, iez*(x+y)=z*x+z*y and (x+y)*z=x*z+y*z for all x, y, and z.
  • Represented by the Distributive trait
  • Note that unlike other marker traits, this one takes a type parameter so that multiplication between types can also be marked (such as scalar-vector or matrix-vector multiplication)
• The Exponentiation and Logarthm operations:
  • Unary operations that map between addition and multiplication
  • Represented with the Exponential trait
• Properties regarding partial divisibility and factoring
  • These traits essentially measure how "integer-like" a particular ring is by abstracting many properties and operations commonly associated with integers and natural numbers
  • These include, but are not limited to:
    • Divisibility
    • Primality
    • GCD
    • Euclidean Division
    • Factorizability
  • For more information, see each individual trait's documentation

Usage

Similarly to the group-like module, there are a number of trait aliases corresponding to a system of ring-like algebraic structures that form a heirarchy as represented in the following diagram:

    Add Abelian Group   Mul Semigroup
           |                 |
           -------Ring--------
                    |
    ----------Unital Ring-------------------------
    |                    |             |         |
    |             Commutative Ring   Domain      |
    |                    |             |         |
    |                    ---------------         |
    |                           |                |
    |                     Integral Domain        |
    |                           |                |
Division Ring            ---GCD Domain---        |
    |                    |              |        |
    |                   UFD       Bezout Domain  |
    |                    |              |        |
    |                    ------PID-------        |
    |                           |                |
    |                    Euclidean Domain        |
    |                           |                |
    -------------Field-----------         Exponential Ring
                   |                             |
                   ------Exponential Field--------

Note also that in addition to the above system, there is a complementary system of "Semirings" that follows almost the same exact structure but doesn't require a subtraction operation.

For more information, see each structure's documentation

Naming

It is worth noting that in mathematical literature, there is some leniency in what certain structures are called, so some trait aliases may be named differently than what some are used to.

In particular:

• Some mathematicians and literature use the term "Ring" to refer to what is called a "Unital Ring" here, instead preferring the term "Rng" for Rings without a multiplicative identity. In fact, this convention is probably the majority considering how little use there is for non-unital rings. However, the choice was made against using the "Rng" system for the simple reason that it is obviously highly prone to typesetting errors and is arguably pretty unintuitive for those learning the terminology.
• The term "Semiring" doesn't really have an established meaning in mathematical convention, so the use here reflects a particular design choice more than a particular standard.

Traits

Bezout	A trait for finding the Bezout coefficients of a pair of elements
Distributive	A marker trait for stucts whose multiplication operation preserves addition, ie z*(x+y)=z*x+z*y and (x+y)*z=x*z+y*z for all x, y, and z.
Divisibility	Common methods regarding multiplicative inverses in a ring or semiring
EuclideanDiv	A trait for performing division with with remainder
Exponential	A unary operation mapping addition into multiplication
Factorizable	For semirings that have a known algorithm for decomposing elements into a set of irreducible factors
GCD	A trait for finding the greatest common divisor and least common multiple of two elements
NoZeroDivisors	A marker trait for semirings where there are no nonzero elements that multiply to zero
Primality	Methods for testing irreduciblity and primality
UniquelyFactorizable	A marker trait for semirings where each element's set of irreducible divisors is unique

Functions

euclidean	Uses the Euclidean Algorithm to find the GCD of two ring elements using division with remainder
extended_euclidean	Uses the Extended Euclidean Algorithm to find the GCD of two ring elements and their bezout coefficients using division with remainder
miller_rabin	Determines if a given Natural number is prime using the Miller-Rabin primality test

Trait aliases

BezoutDomain	A commutative ring where every pair of elements has a weighted sum to their GCD
CommutativeRing	A unital ring where multiplication is commutative
CommutativeSemiring	A unital semiring where multiplication is commutative
DivisionRing	A ring with a multiplicative inverse
DivisionSemiring	A semiring with a multiplicative inverse
Domain	A unital ring with no pairs of nonzero elements that multiply to zero
EuclideanDomain	A commutative ring with a division algorithm for dividing with a remainder
EuclideanSemidomain	A UF semidomain with a division algorithm for dividing with a remainder
ExponentialField	A field with an exponential operation
ExponentialRing	A ring with an exponential operation
Field	A set that is both an additive and multiplicative abelian group where multiplication distributes
GCDDomain	A commutative ring where every pair of elements has a greatest common divisor
GCDSemidomain	An integral semidomain where every pair of elements has a greatest common divisor
IntegralDomain	A domain that is commutative
IntegralSemidomain	A semidomain that is commutative
PID	An integral domain where every ideal is generated by one element
Ring	An additive abelian group with a distributive and associative multiplication operation
Semidomain	A unital semiring with no pairs of nonzero elements that multiply to zero
Semiring	A commutative and additive monoid with a distributive and associative multiplication operation
UFD	A commutative ring that is uniquely factorizable into irreducible (up to units)
UFSemidomain	A GCD semidomain where every pair of elements is uniquely factorizable into irreducible elements (up to units)
UnitalRing	A ring with an identity element
UnitalSemiring	A semiring with an identity element