A principal ideal domain (pid) is an integral domain with only principal ideals. Thus every ideal H in the ring R is x*R for some element x. If you want the entire ring, use 1*R, whereas 0*R defines the 0 ideal.
If R is a noncommutative domain, R is a left pid if its left ideals are all principal. An example is the half quaternions.
If R is a pid and S is a quotient ring of R, S is probably not an integral domain, and thus not technically a pid, but still its ideals are all principal. Each ideal downstairs comes from an ideal upstairs by correspondence, and if g generates the ideal in R, then the image of g generates the corresponding ideal in S. An example is the integers mod n for any n.
In a pid, an element x is prime iff it is irreducible. One direction is true for any integral domain, so run the other direction and assume x is irreducible. It generates an ideal that is maximal among principal ideals, and since all ideals are principal, it is a maximal ideal. This is also a prime ideal, hence x is prime.
To summarize, x nonzero in a pid is prime, iff x is irreducible, iff x*R is a prime ideal, iff x*R is a maximal ideal, iff R mod x*R is a field. There is one other prime ideal, namely 0. This is the only prime ideal in a field, but if R is not a field then there are other prime/maximal ideals over 0. Since every nonzero prime ideal is maximal, a chain of prime ideals always has length 2, with 0 at the bottom and some maximal ideal at the top.
Every euclidean domain is a pid. Take an ideal H, and consider all the nonzero elements x in H. Select x with the least metric d(x) in H. For any y in H, write y = c*x + r. Now r is also in H, and d(r) is suppose to be less than d(x). Since d(x) is minimal, d(r) = 0, r = 0, and y = cx. This makes H principal, generated by x.
Euclidean implies pid, and pid implies ufd. Each nonzero x is prime iff it is irreducible, and that is criterion 4 for unique factorization. But there is one more thing to prove; R must be a factorization domain. The proof is essentially the same as for a euclidean domain. Suppose f cannot be written as a finite product of irreducibles. Think of f as f0, and write f0 = x1f1, where f1 cannot be written as a finite product of irreducibles. By construction, f0 is a multiple of f1. If f1 is a multiple of f0, say cf0, then f0 = x1cf0, which makes x1 a unit. Since f0 was separated into nonunits, this is a contradiction. Thus f1 is not a multiple of f0.
Let H0 be the multiples of f0, and let H1 be the multiples of f1. H1 properly contains H0.
Write f1 = x2f2, where f2 cannot be written as a finite product of irreducibles. Repeating the above, H2, the multiples of f2, properly contains H1. Continue this forever, building an ascending chain Hi of principal ideals.
Let U be the union over Hi. U is an ideal, hence principal, hence generated by some s. For purposes of illustration, let H7 bring s into the picture. Thus s is a multiple of f7. Since f8 belongs to U, f8 is a multiple of s. Yet s is a multiple of f7, hence f8 is a multiple of f7. This is a contradiction. Thus irreducibles cannot spin off forever. Every nonunit is a finite product of irreducibles, and a pid is a factorization domain, and a ufd. Within the world of integral domains, the euclideans are a subset of the pids, are a subset of the ufds.
| Integral Domains |
| Factorization Domains |
| Unique Factorization Domains |
| Principal Ideal Domains |
| Euclidean Domains |
At each level, containment is proper. This will be demonstrated throughout this chapter. We already saw a factorization domain that is not a ufd. Let's build an integral domain that is not a factorization domain.
Start with a field K and adjoin infinitely many indeterminants, x0 x1 x2 x3 … and x-1 x-2 x-3 … Thus indeterminants go up and down forever. For each pair of successive indeterminants, such as x2 and x3, let x22 = x3. These relations generate an ideal H. Note that the polynomials of H never have a constant term. Mod out by H to get the quotient ring R. Since H does not contain any constants, R includes the subring K. The elements of K all represent different cosets of H.
If a string contains an exponent, such as x33, replace this with x3x4, giving another string in the same coset of H. Thus R can be represented by polynomials without exponents. These are called reduced polynomials.
Every generator of H, when reduced, collapses to 0. There are no reduced polynomials in H. Thus the distinct reduced polynomials in R do indeed represent different cosets of H.
Let the measure of the indeterminant xi be 2i. Thus x2 has a measure of 4 and x3 has a measure of 8. Let the measure of a string be the sum of the measures of the indeterminants times their exponents. Since all indeterminants have a positive measure, the measure of any string is positive. To illustrate, the measure of x-1x1x33 = ½ + 2 + 24.
Since x22 and x3 both have measure 8, replacing one with the other does not change the measure of a string. Reducing a string preserves its measure.
Multiplying two strings together adds their measures, before or after the reductions. Once reduced, the measure of a string completely determines that string. Just read the measure in base 2.
Given two polynomials, the lowest string in the first (by measure) times the lowest string in the second produces the lowest string in the product, which survives. Thus R is an integral domain.
Suppose x0 is the finite product of irreducible polynomials p1 * p2 * p3 * … pn. The lowest measure in the product comes from the lowest string in each polynomial, and this survives. The highest measure also survives, and both of these measures, and every measure in between, is 1, corresponding to the measure of x0. Every string in p1 has the same measure, and there is only one string for each measure, hence p1 is one string, rather than a linear combination of strings. The same holds for p2 through pn - and the sum of their measures is 1. However, no string is irreducible. If the lowest indeterminant is x5, you can always replace it with x4 * x4. Therefore x0 has no finite factorization, and R is not a factorization domain.
This is rather contrived; almost every integral domain that you encounter is a factorization domain.
If R is an integral domain, and its prime ideals are principal, then R is a pid.
Start by showing an ascending chain of ideals is never principal. Consider an ascending chain of ever increasing ideals. If x generates the union of these ideals, then x appears in some ideal H in the chain. The next ideal is bigger, and includes elements outside of x*R. Thus x does not generate the union of the chain. The union of any ascending chain of ideals is not principal.
Now consider the ideals of R that are not principal and order them by containment. By the above, the union of a chain of nonprincipal ideals is nonprincipal. Zorn's lemma applies, giving a maximal nonprincipal ideal. Such an ideal is known to be prime. But we're assuming all prime ideals are principal, so this is a contradiction. We cannot have a nonprincipal ideal, else it would start the ascending chain; hence R is a pid.
I have already mentioned the 4 criteria that make a factorization domain a ufd. Here they are again for review, followed by a fifth.
Every two elements have a gcd.
Every two elements have a lcm.
Every n is uniquely a product of irreducibles.
Every n is irreducible iff it is prime.
The intersection of principal ideals is principal.
If a and b generate principal ideals, and l is the least common multiple, or lcm, of a and b, then l divides every multiple of a and b, l generates the intersection of a*R and b*R, and the intersection is principal. Conversely, let the intersection be principal, generated by l. Every multiple of a and b is a multiple of l, and l is the lcm. All 5 criteria are equivalent.
Let R be a ufd, and let S be R mod a prime ideal P, so that S is an integral domain. I will show S is a factorization domain, and then by criterion 4, S is a ufd.
Let z be an element in S with preimage y in R. Factor y uniquely into primes. Let f, a prime factor of y, generate a principal prime ideal in R. This maps to a principal prime ideal in S. Thus the image of f is a prime element in S. Put this all together and z is a product of primes in S. Prime implies irreducible in an integral domain, hence z is also a finite product of irreducibles, and S is a factorization domain.
Suppose f is an irreducible element of S that is not prime. Let e be a preimage of f. If e is irreducible then e is prime, whence f is prime. Thus e is not irreducible. Write e as a unique product of primes (up to associates). If two of these primes are nonunits in S then f is reducible. They all map to units in S except for one of the primes, which I will call u. Now u maps to v, which is prime, and an associate of f. Every associate of a prime element is also prime, hence f is prime after all. This makes S a ufd.
If Q is a minimal nonzero prime ideal in S, corresponding to a minimal prime in R over P, let z lie in Q and factor z into primes. One of these factors lies in Q. If f is a prime factor of z it generates a prime ideal inside Q, which has to be Q. Thus Q is principal, generated by some prime f.
In the ring of integers, gcd(a,b) can always be written as a linear combination of a and b. Bezout showed that the same is true in a pid, although there may not be an efficient algorithm for deriving the gcd, or the linear combination that produces the gcd.
In a pid, let a and b generate an ideal, which must be principal; call it Rc. Clearly c divides a and b. If g = gcd(a,b), then g also divides a and b, and Rg contains the ideals Ra and Rb, and hence Rc. Thus g divides c. Yet c divides g, hence c = g. (In this context, g = c means g and c are associates.) Since g is in the ideal generated by a and b, g is some linear combination of a and b, using coefficients from R.
Generalize this to a finite list of elements. Their common gcd is a linear combination of those elements. For instance:
g = xa + yb
h = gcd(g,c)
h = wg + zc
h = wxa + wyb + zc
Proceed by induction on the number of elements in the set.
I deliberately wrote everything on the left to show that this holds for left pids, though these are quite rare.
Bezout's identity fails for arbitrary ufds. In Z[x], the integer polynomials over x, 2 and x are coprime, with a gcd of 1, yet no linear combination of 2 and x yields 1. This is a ufd that is not a pid.
In the last section we found a ufd that was not a pid. To finish the proof of proper containment, we need to build a pid that is not euclidean. This is quite technical, so hang on.
Recall that a euclidean metric d() can be normalized so that d(u) = 1 iff u is a unit. Let w be a nonunit in R with the smallest metric. Mod out by the principal ideal generated by w, and let x represent a coset of w, i.e. an element in the quotient ring. If x is not a multiple of w then d(x) < d(w). With d(w) minimal, d(x) = 1, and x is a unit. Each nonzero coset of w is a unit. If there are more nonzero cosets than units, then d(w) cannot be minimal. I'm going to build a ring where every w has R/{w} > 3, yet there are only 2 units, 1 and -1. Allow for these units, and 0 ( the image of w itself), and there is one more coset that is not a unit. Such a ring cannot be a euclidean domain.
Adjoin the square root of -m to the integers, for m > 3. The points of R form a lattice of rectangles in the complex plane, where each rectangle is one unit wide and sqrt(m) units high. The area of each rectangle is sqrt(m). Here is a row of rectangles with m = 5. Each is 2.236 times as tall as it is wide. Larger values of m would produce taller rectangles.
The units of R lie on the unit circle in the complex plane; and the only points of R that lie on the unit circle are 1 and -1. These are the only units of R.
Let w have the smallest metric greater than 1. Let q = sqrt(m), and let w = c+dqi. The principal ideal generated by w is a lattice of larger rectangles, tilted relative to the axes. This is overlaid on top of the smaller base cells. The first rectangle is spanned by w and wqi, vectors that are 90 degrees apart. This is the principal rectangle.
Let z be an arbitrary lattice point a+bqi. Subtract multiples of w or multiples of wqi from z, thus giving the same coset of w. Pull z back to a point inside the principal rectangle spanned by w and wqi. These are the canonical representatives of the quotient ring. How many are there? How big is the quotient ring? Divide the area of the principal rectangle by the area of the base cell. The area of the base cell is q, as described earlier. To find the area of the principal rectangle, take the determinant of its two vectors, [c,dq] and [-dm,cq], giving q(c2+md2). Divide this by the area of the base cell, and the quotient ring has size c2+md2. If w is not a unit, not 1 or -1, then the quotient ring has size at least 4. (This happens when c = 2 and d = 0.) The quotient ring is too big, and R is not a euclidean domain.
When m is 3 mod 4, adjoin ½(1+qi) to the integers, thus tiling the complex plane with parallelograms. The base cell is spanned by 1 and ½(1+qi). This cell has area q/2. As m increases, the parallelograms grow taller, and their area increases.
ASsume m is at least 15. Once again the only units are 1 and -1. Let w = c+dqi, where c and d are integers or half integers, and w is not a unit. Now w generates a lattice of larger parallelograms, tilted relative to the axes. The vectors of w are [c,dq] and [-dm+c,(c+d)q]/2, where c and d are both integers or both half integers. Take the determinant, divide by q/2, and get the same formula c2+md2, where c and d are integers or half integers. With m at least 15, the size is at least 4, and R is not a euclidean domain.
Now for the prize. Set m = 19 and adjoin ½(1+qi), as described above. This is not a euclidean domain, since m ≥ 15, yet it is a pid.
Given a proper ideal H, let x be the element of H, other than 0, that is closest to the origin. Remember that x spans a lattice of parallelograms in the plane. This is the principal ideal generated by x, living in H. We'll see that x generates all of H.
Consider any point y in H, and reduce y mod x, so that y lies in the principal parallelogram spanned by x. The base of this tilted parallelogram runs from the origin to x, and the side, which is not quite perpendicular to the base, runs from the origin to x×½(1+qi). After an appropriate translation, y lies somewhere in this parallelogram.
We know that y might be somewhere in the middle, far from the four corners. That's why the gcd algorithm doesn't work. But if y isn't close to one of the corners, then 2y is. Show this for all points in the complex plane, so we don't have to worry about lattices.
Pivot the parallelogram about the origin and scale its dimensions, so that its base runs along the x axis from 0 to 1. The slanted side now runs from the origin up to ½(1+q), giving a height of approximately 2.179. The height of y is at least 0.866, sqrt(3)/2, else y is less than 1 unit away from one of the two lower corners. At the same time, y is no higher than 2.179-0.866 = 1.313, else y is within one unit of one of the upper corners. Now double y, and its height is trapped between 1.732 and 2.616. It is now close to one of the upper corners of the parallelogram.
Return to our lattice in the complex plane, spanned by x. If y is in H, shift y into the principal parallelogram spanned by x, and either y or 2y lands smack on one of the corners. Close doesn't count, because that would produce a vector in H that is shorter than x, yet x is closest to the origin.
Suppose 2y is a multiple of x, but y is not. Thus y is the midpoint of a segment that joins the origin to one of the other three corners. We know that y is not ½x, x being minimal. Suppose y = ½xs, where s is ½(1+qi). In other words, y is the midpoint of the left side of the parallelogram. Multiply y by s-1 and add 3x.
½sx × (s-1) + 3x = ½(s2-s)x + 3x
The key observation is that s2-s = -5. So y×(s-1) becomes -5/2 times x, and when you add 3x, you get ½x, which contradicts the minimality of x.
Finally, y could be ½x×(s+1), the center of the parallelogram. Subtract x, multiply by s, and add 3x. Once again you get ½x, which is a contradiction.
The point y, an arbitrary point in H, is a multiple of x, hence H is principal. R is a pid, but not a euclidean domain.
If you adjoin other square roots to the integers, the square root of a positive or a negative number, do you get a pid, or a ufd? The answer is, hardly ever. Things look promising at first. The square root of -1 (gaussian integers), -2, -3 (with half integer coordinates gives the eisenstein integers), -7, and -11; these are all euclidean, thus a pid and a ufd. We saw above that -19 is not euclidean, but it still produces a pid. However, unique factorization spreads thin after that. Here are the values of m, up to 10,000, that lead to unique factorization.
Negative: -1, -2, -3, -7, -11, -19, -43, -67, -163
Positive: 2, 3, 5, 13, 21, 29, 53, 77, 173, 293, 437
Let R be a factorization domain and let w generate a proper principal ideal in R. Let P be a nonzero prime ideal inside w*R. Take any nonzero element f in P and factor it. This does not assume R is a ufd, but since R is a factorization domain there is a finite factorization for f. One of these irreducibles, call it x, is in P, and in w*R. Now w generates x, which is irreducible, hence w and x are associates. Therefore w*R = P. A nonzero prine ideal inside a principal ideal becomes the entire principal ideal.
When w is prime, w*R is a minimal nonzero prime ideal. The ideal is prime, and another prime ideal inside would have to equal w*R.
If R is a ufd, the converse is also true. Let P be a minimal nonzero prime ideal and let f be a nonzero element in P. Factor f, giving an irreducible factor x in P, which is also prime. Now x*R is a prime ideal inside P, but P is minimal, hence x*R = P, and P is principal. In a ufd, minimal nonzero prime ideals correspond 1 for 1 with prime elements (up to associates).
Let R be a commutative ring, which will also act as the range for a set of functions that I will call S. Let D be the domain for the functions of S. Traditionally, D is the positive integers, though in its most general setting D could be the nonzero associate classes of a ufd, or the nonzero ideals of a dedekind domain. In any case, S consists of all possible functions from D into R.
Let addition in S occur pointwise. Thus (f+g)(n) = f(n) + g(n). Addition forms an abelian group, with the zero function acting as the group identity.
Let (fg)(n) be the sum of f(j)×g(n/j), for all divisors j of n.
Since finite sums can be reversed, multiplication is commutative.
Regardless of grouping, a product such as f*g*h adds terms f(i)×g(j)×h(k), where ijk = n. Thus multiplication is associative.
Finally, multiplication distributes over addition, thus S is a commutative ring. This is known as the arithmetic ring of D over R. In this case arithmetic is an adjective, describing the ring, hence the accent is on the first and third syllables, like an arithmetic progression. When arithmetic is a noun, the accent is on the second syllable.
Let e be the function that sets e(1) = 1, and is 0 otherwise. Verify that e is the multiplicative identity of S.
A copy of R is embedded in S, via R*e. Thus S is an R algebra.
If D is derived from a field, D contains but one element, the class of 1; and S = R.
Set D to the positive integers, and review the mobius function μ. If f is the constant function 1, then f*μ = e. Therefore μ has an inverse, namely the constant function 1.
What are the units in S? Note that fg)(1) = f(1)g(1). Write fg = e, and f(1) has to bea unit. If R is not a field, or D is nontrivial, S is not a field.
In general, f is a unit iff f(1) is a unit. Use a form of synthetic division to build e/f. If f(1) = u, let g(1) = v, where uv = 1. For each prime p, set g(p) = -f(p)v/u. If n = p2, set g(n) = -(f(n)v + f(p)g(p))/u. If n = pq, set g(n) = -(f(n)v + f(p)g(q) + f(q)g(p))/u. Continue this process through all values of n, whence g becomes the inverse of f.
If D is the positive integers, and R is an integral domain, then so is S. Suppose fg = 0, yet f and g are nonzero. Let y be the least integer for which f(y) ≠ 0, and let z be the least integer for which g(z) ≠ 0. Consider (fg)(yz). Look at a term such as f(i)g(j). If i is less than y, f(y) = 0. Similarly, if j is less than z, g(z) = 0. The only term that matters is f(y)g(z), and this is nonzero. If f and g are nonzero then fg is nonzero. This makes S an integral domain.
This can be generalized to any domain D. Well order the elements of D by the following criteria. Well order the primes in any way you like. Sort the elements by the least prime in the factorization. In other words, the even numbers come before the odds (not counting 1). Within the odd composites, those divisible by 3 come first. Within the composites not divisible by 2 or 3, those divisible by 5 come first, and so on.
For all numbers having the same smallest prime, sort by the exponent on that prime. Within the evens, the numbers are arranged according to 21, 22, 23, 24, 25, and so on. Within one of these groups, sort by the next smallest prime, then its exponent, then the next smallest prime and its exponent, and so on.
Using this ordering, select y and z as above, and expand (fg)(yz). Consider the term f(i)g(j). If the least prime of i is less than the least prime of y, the result is 0. Similarly, the least prime of j cannot be less than the least prime of z. Let p be the least prime of y, and let q be the least prime of z. If p < q, all the powers of p have to live in i. If any live in j then g(j) is 0. This consumes all the powers of p in yz. Similarly, if q < p, all the powers of q live in j. If p = q, i cannot have fewer powers of p than y, and j cannot have fewer powers of p than z. Once again all the powers of p are accounted for.
The least prime in yz has been allocated between i and j, in a manner consistent with y and z. Move on to the next prime in yz. It is placed in i, or in j, or both, commensurate with its presence in y and z. This continues all the way down the line, until i = y and j = z. The product is always 0 unless i = y and j = z. Then two nonzero elements combine to produce a nonzero product, and fg is nonzero.
One could spend a lot of time analyzing these rings for various combinations of D and R. What does an ideal look like? Are these rings noetherian? Do they ever form a ufd? What does the prime spectrum look like? And so on. This is a rather specialized area of mathematics, so for now I'm going to move on to other topics.