Ring theory extends from group theory, formalizing more algebraic structures over rings. Additionally, polynomial rings and their elements, polynomials, will be explored in this article.
Polynomials are not concretely defined in a single branch of mathematics, but rather they are defined within multiple contexts across multiple branches. One approach, however, is to define a polynomial not as an independent structure but as a subordinate structure, being an element of a polynomial ring. This is similar to how a vector is more commonly treated as an element of a vector space, rather than an independent structure.
The Rings
Ring
A ring is a set equipped with two binary operators, commonly referred to as addition and multiplication such that addition forms an abelian group with the set, multiplication forms a monoid with the set, and multiplication distributes over addition.
Note that while addition and multiplication are the most common, in latex blocks for abstraction purposes, we define addition to be the star operator and multiplication to be the diamond operator.
An abelian group is a set equipped with an operator that exhibits associativity and commutativity, contains an identity that when applied to any element does not change the element, and for every element, there exists an inverse such that an element applied with its inverse returns the identity.
A monoid is a set equipped with an operator that exhibits associativity and contains an identity element.
Finally, multiplication (diamond) distributes over addition (star).
def associative(a, b, c, op):
return op(a, op(b, c)) == op(op(a, b), c)
def is_identity(a, e, op):
return op(a, e) == op(e, a) and op(a, e) == a
def is_inverse(a, a_inv, e, op):
return op(a, a_inv) == op(a_inv, a) and op(a, a_inv) == e
def commutative(a, b, op):
return op(a, b) == op(b, a)
def distributive(a, b, c, op_add, op_mul):
return op_mul(a, op_add(b, c)) == op_add(op_mul(a, b), op_mul(a, c))Commutative Ring
A commutative ring is a ring where multiplication also commutes.
A nonzero commutative ring is a commutative ring where at least one element is not the zero element. That is to say the following.
Division Ring
Division rings aka skewfields are rings where multiplication admits a multiplicative inverse for every element (excluding zero) and the multiplicative identity element is not zero. The multiplicative inverse corresponds to division, just as the additive inverse corresponds to subtraction.
Field
A field is simply a commutative division ring. That is to say, addition and multiplication are associative, commutative, have identity elements, have inverse elements, and multiplication distributes over addition. One way to represent a field F is as follows.
The most common field is that of the real numbers with addition and multiplication as they are commonly understood. All real numbers associate and commute over addition and multiplication, additive identity is 0, multiplicative identity is 1, additive inverse returns zero by adding the positive and negative form of the same number, multiplicative inverse returns one by multiplying a number N and 1/N.
Field Extension
A field extension corresponds to the superset of a set which forms a field. That is to say, if a field's set A is a subset of another field's set B, then A is a subfield and B is a field extension.
A common field extension is the Complex numbers, which extends the Real numbers with the imaginary numbers.
Galois Field
A Galois field aka finite field, is a field with a finite number of elements. Galois fields are commonly a set of positive integers modulo a prime number. Galois fields are valuable tools for cryptography, enabling asymmetric encryption, homomorphic encryption, and zk-SNARKS.
set_s = { 0, 1, 2, 3, 4 }
add = lambda x, y : x + y % 5
mul = lambda x, y : x * y % 5Binary Fields
A binary field is a Galois field where the prime modulus is two. This enables efficient bitwise operations and efficient hardware implementations of finite field arithmetic. Interestingly, the addition (star) operation corresponds to the exclusive or (XOR) logic gate and the multiplication (diamond) operation corresponds to the and (AND) logic gate such that:
B = { 0, 1 }
logical_and = lambda x, y : x & y
logical_xor = lambda x, y : x ^ y
for a in B:
for b in B:
assert associative(a, b, a, logical_xor)
assert commutative(a, b, logical_xor)
assert is_identity(a, 0, logical_xor)
assert is_inverse(a, a, 0, logical_xor)
assert associative(a, b, a, logical_and)
assert commutative(a, b, logical_and)
assert is_identity(a, 1, logical_and)
# there is never a multiplicative inverse of 0
if not a == 0:
assert is_inverse(a, 1, 1, logical_and)Polynomial Ring
A polynomial ring, denoted R[X], is a commutative ring whose elements are polynomials with coefficients in R and variables aka indeterminants in X with a function that maps X into R[X].
Polynomials
A polynomial "p", being an element of a polynomial ring R[X], is representable as follows.
A more familiar and commonly used representation is as follows.
Univariate polynomials have a single variable in X while multivariate polynomials have multiple variables in X.
The degree of a polynomial is the highest variable exponentiation in the polynomial.
The leading coefficient (leadco) is the coefficient with the highest degree.
The constant term (const) is the term where the variable is exponentiated to the 0th power.
Note: The names of each function are not necessarily standard, they were chosen arbitrarily for intuition's sake.
Polynomial interpolation constructs an n-degree polynomial from n+1 points. Lagrange interpolation finds the polynomial that interpolates a given set of points.
Linear Polynomials
Linear polynomials do not require exponentiation and are representable as follows.
Polynomial Algebra
As mentioned, polynomial rings form, well, a ring.
The addition of polynomials is performed by adding the coefficients of corresponding variables and exponents.
The multiplication of polynomials is performed by multiplying each polynomial term with one another. Simplification through coefficient addition of corresponding variables and exponents is also possible.
The ring formed with polynomials is as follows.
In addition to polynomial addition, subtraction, and multiplication, there exists scalar-polynomial multiplication, where a scalar in R may be multiplied by all coefficients in the polynomial.
Morphisms
Ring Homomorphism
A ring homomorphism is a function between two rings that preserve addition, multiplication, and multiplicative identity.
Ring Isomorphism
If the ring homomorphism is a bijection, that is to say if that elements of the function's domain (output) corresponds one to one with elements of the function's codomain (input), then there exists an isomorphism where elements can be mapped from A to B as well as B to A.
Ring Endomorphism
A ring endomorphism is a ring homomorphism from a ring to itself.
Conclusion
Ring theory is, as all abstract nonsense is, fairly straight forward. However, the concepts defined in group theory and by extension, ring theory, are powerful tools for abstracting and "black boxing" functionality from elliptic curves to zkSNARK's. Polynomial rings enable arithmetic over polynomials for creating succinct proofs while Galois fields lay the foundations for elliptic curves and their abelian groups used in asymmetric cryptography. This should be a helpful resource as we explore deeper mathematical concepts in the future.
Until next time.