Hi! :)
These are a few notes I made for myself and my true-blue friend Scartol, who's bringing Emmy Noether to FA status and wants to know more about her mathematics. So do I; so here we go! :) We're going to explore the basic ideas of groups, rings, and fields. Several of these ideas are really useful in error-correcting codes, which are used to transmit information or store information (as on a CD or DVD). I'll be adding material here as I learn about it.
Beginning in the early 19th century, mathematicians began to study ever-more-abstract systems with ever-more-abstract sets of rules, to find the minimal properties that were responsible for certain observations. For example, suppose that you notice that X is true about Y; that leads mathematicians to wonder: what is the smallest set of assumptions about Y that accounts for X?
Groups
editA group G is a set of objects called elements and an operation to combine two elements to form a new element. This binary operation is sometimes called "multiplication", but only for convenience; the operation may have nothing to do with numerical multiplication. For example, the operation could be rotating a face of a Rubik's cube, or taking the XOR of two binary numbers, or anything.
Well, not anything. To fulfil the definition of a group, the elements and the operation must have the following properties[1]
- The combination a * b of any two elements a and b must also belong to the group; the group is said to be closed.
- The operation is associative a * (b * c) = (a * b) * c. In other words, if we combine a with b, and then combine the result with c, we get the same result as if we had first combined b with c and then combined that result with a.
- There is an identity element e such that e * a = a * e = a for all a.
- Every element a in G has a inverse element a-1 such that a * a-1 = a-1 a = e. An element may be its own inverse, a * a = e.
A set M that fulfils the first three requirements is called a monoid.[2] Therefore, a group is a monoid in which every element has an inverse (the fourth requirement)..[3] The order of elements in a combination can change the result: a * b need not equal b * a for a generic group. If a group does satisfy that equality, i.e., if a b = b a, then the group is said to be abelian.[4]
For illustration, consider the set of integers, which is not a group under normal multiplication. It fulfils the first three criteria and therefore is a monoid: the product of every pair of integers is another integer (the group is closed); the multiplication of three integers is associative; and there is a multiplicative identity, namely 1. However, it fails the fourth criterion: the multiplicative inverses of integers are not themselves integers. However, the set of integers is a group under the combining operation of numerical addition. The group is closed, the operation is associative, and the identity element e is zero: 0 + a = a + 0 = a. It also passes the fourth criterion, because every integer has an inverse integer -a that produces the identity: a + (-a) = 0. Subsets of the integers may also be groups under addition, e.g., the set of multiples of three {...,-6, -3, 0, 3, 6,...}.
Another good example, relevant for the discussion below, is the set of integers from 0 to p-1, where p is a prime number such as 7; here, the binary operation is normal addition, but modulo p. Here's the table of combinations for such a group with p=5[5]
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
The binary operation need not have anything to do with numerical addition or multiplication, however. The set of binary numbers of length 23 forms a group under the binary operation XOR. As an even more sophisticated example, consider the set of permutation of three elements ABC
| Group element name | e | i | j | k | l | m |
|---|---|---|---|---|---|---|
| Permutation | swap nothing | swap first two | swap last two | swap first and last | move last to first | move first to last |
| Result on ABC | ABC | BAC | ACB | CBA | CAB | BCA |
These permutations {e, i–m} form a group where permutation are "combined" by performing them after one another. They form a group because they meet the four criteria: two successive permutations is another permutation (for example, i*j = m), the combination of permutations is associative, there is an identity element e, and every permutation has an inverse permutation. This example illustrates that processes such as permutations or rotations can also form the elements of a mathematical group.
The definition of a group is very basic, and you might think that nothing interesting could be derived from such simple postulates. But group theory is a rather interesting field and hasn't been exhausted in the 170-some years since its invention by Galois. One important area is the study of representations of a group. A particular group is defined by the multiplication table among its elements, but very different objects can yield the same multiplication table and thus correspond to the same group. For example, more than one set of matrices might have the same multiplication table as given above for the permutations. Mathematicians studied the minimal representations of the group, which correspond to the smallest matrices that obey the multiplication table; these are called the irreducible representations.
Rings
editRings resemble groups, but they have two binary operations, called "addition" and "multiplication" and denoted + and * for convenience.[6] Again, these two operations may have nothing to do with numerical addition and multiplication; all that matters is that they satisfy the following criteria. Under "addition", the elements of a ring must form an abelian group, i.e., a + b = b + a. Hence, the ring must have an additive identity element (usually denoted "0"), a + 0 = a. The multiplication operation must beassociative a * (b * c) = (a * b) * c. The two operations together must be distributive
A ring may have a multiplicative identity (usually denoted "1"). If so, some elements a of the ring may have a multiplicative inverse a-1 such that a * a-1 = a-1 a = e; such elements are said to be regular. A ring in which all elements except the additive identity 0 are regular, i.e., have a multiplicative inverse, is called a division ring, provided that the multiplicative and additive identities are not the same element, i.e., 1 ≠ 0.[7]
Fields
editA field is a division ring in which multiplication is commutative.[8] A good example is the set of integers from 0 to p-1 (where p is again a prime number) under the operations of addition and multiplication modulo p. The addition table for p=5 was given above, the multiplication table is given here[9]
| * | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
This field has a multiplicative identity, namely 1, and every element has a multiplicative inverse. For illustration, 2*3 = 3*2 = 6, which equals 1 modulo 5; therefore, 2 and 3 are multiplicative inverses of each other in this field. Similarly, 1 and 4 are their own inverses, e.g., 4*4=16 which equals 1 modulo 5. The additive identity 0 has no inverse; nothing times zero equals 1.
This example is a finite field, since it has a finite number of elements; such fields are also called Galois fields after their discoverer Évariste Galois. The above example is denoted as GF(5); more generally, Galois fields are denoted as GF(pm), since it can be shown that the number of elements in any finite field must be a power m of a prime number p. Galois fields are the basis for most modern codes.
Ideals
editAn ideal I of a ring R is a subset of the ring such that two criteria are satisfied: the elements of I form a ring themselves, and any element of the original ring R multiplied by an element of the ideal gives an element of the ideal.[10] An example of an ideal I is the set of multiples of three under numerical multiplication and addition. This set I is a subset of the ring R of all integers; it forms its own ring, and any element of I (any multiple of three) multiplied by any element of R (any integer) gives an element of I (another multiple of three).
Since the order of multiplication can be important in groups and rings, there are two types of ideals, left and right.[11] A left ideal IL is one in which any element x of R multiplying an element i of IL on the left (i.e., x * i) gives an element of IL; that need not be true for the right-hand multiplication (i.e., i * x). The converse is true for the right ideal IR. If both are true, i.e., a set that is both a left- and right-ideal is known as a two-sided ideal. If the operation of multiplication is commutative, every ideal is a two-sided ideal.
Modules
editA so-called module over a ring R is an abelian group G of elements such as ξ and η that can be combined with ring elements such as a and b to form an element ζ of the group.[12] The ring and group elements are combined by another binary operation, ·, which obeys the following laws
If the ring has an multiplicative identity element e then
Strictly speaking, these are left modules since the ring element combines with the group element from the left; one may also define the corresponding right module. However, left modules are by far the most common type.[13]
References
edit- ^ Choquet-Bruhat and DeWitt-Morette, p. 7.
- ^ Lang, p. 3.
- ^ Lang, p. 7.
- ^ Choquet-Bruhat and DeWitt-Morette, p. 7.
- ^ Lin and Costello, p. 18.
- ^ Choquet-Bruhat and DeWitt-Morette, p. 8; Lang, p. 60.
- ^ Lang, p. 61; Choquet-Bruhat and DeWitt-Morette, p. 8.
- ^ Lin and Costello, pp. 19–20.
- ^ Lin and Costello, p. 19.
- ^ Lang, p. 62; Choquet-Bruhat and DeWitt-Morette, p. 8.
- ^ Lang, p. 62; Choquet-Bruhat and DeWitt-Morette, p. 8.
- ^ Lang, p. 81; Choquet-Bruhat and DeWitt-Morette, p. 8.
- ^ Lang, p. 81.
Bibliography
editChoquet-Bruhat Y, DeWitt-Morette C (1982). Analysis, Manifolds and Physics. New York: North-Holland. ISBN 978-0444860170.
Lin S, Costello DJ, Jr. (1983). Error Control Coding: Fundamentals and Applications. Englewood Cliffs, NJ: Prentice-hall. ISBN 0-13-283796-X.{{cite book}}: CS1 maint: multiple names: authors list (link)
Lang S (1984). Algebra (2nd ed. ed.). Reading, MA: Addison-Wesley. ISBN 0-201-05487-6. {{cite book}}: |edition= has extra text (help)