Lecture from: 13.11.2024 | Video: Videos ETHZ
Rings
A ring is an algebraic structure that generalizes the concepts of addition and multiplication from familiar number systems like integers and real numbers. A ring is denoted as , where is a set, and are binary operations (addition and multiplication), is a unary operation (additive inverse), and 0 and 1 are special elements (additive and multiplicative identities).
A ring must satisfy the following properties:
-
Additive Group: forms an abelian group. This means:
- Associativity:
- Commutativity:
- Identity:
- Inverse: For every , there exists such that
-
Multiplicative Monoid: forms a monoid. Note that the multiplicative identity can be equal to in the trivial ring with just one element. Other rings where do exist too (rings with 0 divisors, we will return to these later), thus 1 is not 0 unless stated. This means:
- Associativity:
- Identity:
-
Distributivity: Multiplication distributes over addition:
- Left Distributivity:
- Right Distributivity:
Applications
Rings have numerous applications in various fields, including:
-
Error-Correcting Codes: Rings are used in the construction of error-correcting codes, which are essential for reliable data transmission and storage.
-
Secret Sharing: Rings play a role in secret sharing schemes, where a secret is divided into multiple shares distributed among participants, and a certain number of shares are required to reconstruct the secret.
-
Privacy Amplification: Rings are used in privacy amplification techniques, where a partially secret shared value (e.g., a bitstring) can be transformed into a shorter, more secret value. A public function compresses the bitstring (e.g., from 1000 bits to 800 bits). The specific choice of is public knowledge, but the way it is applied depends on an additional secret. The remaining 200 bits could function like this key, akin to a one-time pad.
Lemmas
-
: . Adding to both sides gives .
-
: . Adding to both sides gives .
-
if : Proof by contradiction. Assume . Let such that (such an exists since ). Then , which contradicts our assumption that . Therefore, .
Gaussian Integers
While familiar rings like (integers) and (real numbers) are commonly encountered, let’s explore a different ring: the Gaussian integers.
Gaussian integers are complex numbers of the form , where and are integers, and is the imaginary unit (). We can represent Gaussian integers as ordered pairs of integers: , where corresponds to .
The set of Gaussian integers is denoted as . We define the ring operations as follows:
-
Addition: . This corresponds to the usual addition of complex numbers: .
-
Multiplication: . This corresponds to the multiplication of complex numbers: .
-
Additive Identity: The additive identity is , corresponding to .
-
Multiplicative Identity: The multiplicative identity is , corresponding to . This is because .
-
Additive Inverse: The additive inverse of is , corresponding to .
The Gaussian integers form a ring, , because they satisfy all the ring axioms (additive group, multiplicative monoid, and distributivity). These properties are inherited from the complex numbers.
Visualization:
Gaussian integers can be visualized as points on a two-dimensional grid (complex plane), where the horizontal axis represents the real part () and the vertical axis represents the imaginary part (). Addition corresponds to vector addition on this grid. Multiplication has a geometric interpretation involving rotation and scaling, which is a bit more complex to visualize directly on the grid.
Divisibility in Gaussian Integers (Clicker…)
Divisibility in Gaussian Integers
In the ring of Gaussian integers, , we say that a Gaussian integer divides another Gaussian integer (denoted as ) if there exists a Gaussian integer such that .
How to determine if :
Divisibility in Gaussian integers is slightly more nuanced than in regular integers. We use the concept of the norm of a Gaussian integer. The norm of , denoted as or , is defined as . The norm is always a non-negative integer.
Calculate the norms: Compute and .
Check integer divisibility: If , then must divide in the regular integers. This is a necessary condition, but not sufficient. If does not divide , then cannot divide .
Complex division: If divides , perform the complex division , where is the complex conjugate of (if , then ).
Check if the quotient is a Gaussian integer: If the real and imaginary parts of the resulting quotient are both integers, then . Otherwise, does not divide .
Examples:
- Does divide ?
- divides , so we proceed to complex division: .
- Since is a Gaussian integer, .
- Does divide ?
- does not divide , so does not divide .
- Does divide ?
- divides , so we perform complex division: .
- Since is a Gaussian integer, .
- Does divide ?
- does not divide , hence does not divide .
By using the norm and performing complex division, we can systematically determine divisibility in the ring of Gaussian integers.
Greatest Common Divisor (GCD) of Gaussian Integers
Units in Gaussian Integers
A unit in a ring is an element that has a multiplicative inverse within the ring. In other words, an element is a unit if there exists an element in the ring such that .
In the ring of Gaussian integers, , we can find the units using the norm. If is a unit, then there exists such that . Taking the norm of both sides, we get , which implies . Since the norm of a Gaussian integer is always a non-negative integer, we must have .
So, we need to find Gaussian integers such that . The integer solutions to this equation are:
See the yellow dots…
Therefore, the units in are and . These are the only Gaussian integers that have multiplicative inverses within .
For future reference, when we discuss error-correcting codes, we will encounter a similar structure involving tuples of 8 bits. In this context, the underlying ring will be , representing byte-sized sequences where each element within the tuple is an element of .
Polynomial Rings:
Beyond numbers, rings can also be constructed using polynomials. Given a ring , we can form the polynomial ring , where the coefficients of the polynomials are elements of .
Elements of are polynomials of the form , where are the coefficients and is the indeterminate (or variable). We can represent these polynomials as sequences of their coefficients: , where only a finite number of coefficients are non-zero. For instance, if , the polynomial would be represented as .
The ring operations are defined as follows:
-
Addition: Addition is component-wise, using the addition operation of . If and , then , where each is performed in .
-
Multiplication: Multiplication is defined using the distributive law and the rule . The product of two polynomials and is given by the convolution of their coefficient sequences, with coefficient operations performed in : , where . For example, if and , then the coefficients of the product are:
- for All these coefficient operations are performed using the multiplication and addition defined in .
-
Additive Identity: The additive identity is the zero polynomial, represented by the sequence , where is the additive identity in .
-
Multiplicative Identity: The multiplicative identity is the constant polynomial 1, represented by the sequence , where is the multiplicative identity in .
-
Additive Inverse: The additive inverse of is , where is the additive inverse of in .
forms a ring under these operations. The familiar ring is a specific instance of this construction where .
Units in Polynomial Rings
A unit in a ring is an element that has a multiplicative inverse within the ring. In other words, an element is a unit if there exists an element such that , where 1 is the multiplicative identity of . The set of all units in is denoted by . This forms a group by itself under the multiplication operation of .
In the case of polynomial rings, determining the units depends on the underlying ring .
-
If is a field: If is a field (we’ll look at this later) (like or ), then the units in are precisely the non-zero constant polynomials. This is because the degree of the product of two polynomials is the sum of their degrees. Therefore, for a polynomial to have an inverse, its degree must be zero (a constant). Only constant polynomials that are themselves units in will be units in the polynomial ring, however since we assumed is a field, all elements (except 0) must be units.
-
If is not a field: If is not a field (like ), then the units in are the polynomials whose constant term is a unit in and all other coefficients are nilpotent (meaning some power of the coefficient is zero) in . In the simpler case of , the units are only the constant polynomials 1 and -1, because these are the only units in .
For example, in , the polynomial is not a unit because there is no polynomial in that, when multiplied by , yields 1. However, in , is a unit because its inverse within is .
Example: Graded Exercise from Last Exam - Commutativity of Addition in a Ring
While the standard definition of a ring requires the additive group to be abelian (commutative), we can demonstrate that commutativity of addition follows from the other ring axioms, even without explicitly requiring it.
Proof:
We want to show that for any , . We’ll use distributivity, the properties of the additive identity (0), and the multiplicative identity (1).
-
Expand (1 + 1)(a + b) using right distributivity:
-
Expand the terms using left distributivity:
-
Simplify using the multiplicative identity property (1a = a and 1b = b):
-
Now expand (1 + 1)(a + b) using left distributivity first:
-
Simplify using the multiplicative identity property:
-
We now have two expressions for (1 + 1)(a + b):
-
Add -a to the left of both sides (using associativity and the additive inverse property):
-
Add -b to the right of both sides (using associativity and additive inverses):
Therefore, we have proven that addition is commutative in a ring, even without explicitly including it as an axiom.
Irreducible Elements
In a ring, an irreducible element is analogous to a prime number in the integers. An element of a ring is called irreducible if it satisfies the following conditions:
- Non-zero and Non-unit: is not zero and not a unit (i.e., it does not have a multiplicative inverse in ).
- If , then either or is a unit. This means cannot be factored into two non-unit elements.
Essentially, irreducible elements are those that cannot be “broken down” further into smaller non-trivial factors within the ring.
Examples:
1. Gaussian Integers ():
- is irreducible: Suppose . Taking the norm (magnitude squared) of both sides, we get . Since are integers, the only possible factorizations of 2 are or . This implies that either or . If , then is a unit in (e.g., ). Similarly, if , then is a unit. Therefore, is irreducible.
- 3 is irreducible: Suppose . Taking the norm gives . The possible factorizations of 9 are . If or , then as before, we get units when they equal to and non-unit when they equal . The interesting case is . We are looking for a,b integers s.t. . However, this equation has no integer solutions. Therefore, 3 is irreducible in .
- 5 is not irreducible: , and neither nor are units (their norms are 5, not 1).
2. :
- is irreducible: If , then one of or must have degree 0 (be a constant). Since the only units in are the non-zero constant polynomials (which are just 1 in this case), either or must be 1, making irreducible.
- is irreducible: Similar to the case of , if , one of the factors must be a constant (and therefore a unit).
- is not irreducible in : This factors to in .
Integral Domains and Zero Divisors
An integral domain is a commutative ring with a multiplicative identity () and no zero divisors.
Zero Divisors: A zero divisor is a non-zero element of a ring such that there exists a non-zero element with . In other words, zero divisors are non-zero elements that, when multiplied by another non-zero element, produce zero.
Example in :
In the ring (integers modulo 20), consider the elements 8 and 15. Both are non-zero. However, . Therefore, both 8 and 15 are zero divisors in .
Avoiding Zero Divisors:
The presence of zero divisors can lead to complications when performing arithmetic operations, such as losing the cancellation property. For example, in , , but this doesn’t imply that either 8 or 15 are equal to 0. This is why integral domains, which have no zero divisors, are often preferred for many applications. A key property of integral domains is the cancellation property: if and , then .
Units and the Group of Units ()
Within a ring , a unit is an element that has a multiplicative inverse within the ring. Formally, an element is a unit if there exists an element such that . The set of all units in a ring is denoted by .
forms a group under the ring’s multiplication operation. This group is called the group of units of the ring . Let’s verify the group properties:
- Closure: If and are units in , then there exist and in . The product also has an inverse in , namely , since . Therefore, .
- Associativity: The associativity of multiplication is inherited from the ring .
- Identity: The multiplicative identity 1 of the ring serves as the identity element of the group , since for any .
- Inverses: By definition, every element in has a multiplicative inverse in .
Examples:
- Integers (): The units in are 1 and -1, so .
- Real Numbers (): The units in are all non-zero real numbers, so .
- Gaussian Integers (): The units in are . These are the only Gaussian integers with a norm (magnitude squared) equal to 1.
- : The units of are , where . Therefore . (See [[16 Isomorphism, Powers, Order, Generators, Lagrange’s Theorem, Multiplicative Groups, Euler’s Totient Function, RSA#eulers-totient-function—phim|Euler’s Totient Function ]])
Continue here: 18 Rings, Fields, Real Polynomial Fields, Polynomial Fields, Galois Fields