Gracious Living


Ideals: Numbers But Better
March 8, 2011, 14:27
Filed under: Algebra, Math | Tags: , , ,

I left you with a bit of a teaser.  We’d defined rings, integral domains, and fields, and even seen a few examples, but in such a short exposition, there wasn’t very much time to give you the tools to work with them.  There turn out to be ideas that make better sense in a ring, like primality and divisibility.  But to understand them, we need to develop a little machinery, which in this case is the theory of ideals.  As I show below, ideals are like better-behaved numbers, and help us understand the structure of, among other things, the integers.

Modern commutative algebra essentially arose in the early 19th century, under the guidance of mathematicians like Dedekind and Abel.  As you’re probably aware, in \mathbb{Z}, every number has a unique factorization into primes, up to sign (and if you’re not aware of it, a prime is a number with no factors but itself and 1, like 2,3,5,7,\dotsc but not 4=2\cdot 2, 6=2\cdot 3,\dotsc).  The proof is really not hard: if a number is a prime, then we’re done, and if it’s not, then it has other factors, and we use induction to factorize each of them into primes; then if we have two different factorizations, we can divide through by one of them to get a prime factorization for 1, and it’s easy to see that the only such factorization is the trivial one.

The surprise is that such a theorem doesn’t always hold, even in familiar rings.  One example is the ring \{a+b\sqrt{-5}:a,b\in\mathbb{Z}\}, which we’ll call \mathbb{Z}[sqrt{-5}].  We now have

\displaystyle 6=2\cdot 3=(1+\sqrt{-5})(1-\sqrt{-5})

and it’s possible to show that all four of these numbers are primes in \mathbb{Z}[\sqrt{-5}].

Dedekind arrived at a resolution by realizing that unique prime factorization exists if we suitably abstract our definition of “number.” Now, I held off on showing you this because it’s actually related to the method of Dedekind cuts described in the last post, and seeing that in a relatively intuitive setting can be very helpful in the more unintuitive one here.  I don’t actually know if Dedekind was aware of the relationship between the two.

To be perfectly rigorous, we’ll define the divisibility relation in a ring R as follows: a|b if there is a r\in R with ra=b.  (Worst notation ever: it is symmetrical for an asymmetric relation, and looks like the letter l or number 1 if you’re sloppy.)  So in a field, everything is divisible by everything nonzero, for example.  It should be easy to see that this is a partial order.  We then define the principal ideal generated by a to be the set (a)=\{b:a|b\}.  A lot of properties of ring elements are expressed in their ideals.  For example, in \mathbb{Z}, p is prime iff xy\in(p)\Rightarrow x\in(p) or y\in(p): if any multiple of p has factors, then at least one of the factors is a multiple of p.

But divisibility has some other properties.  If a|b and a|c, then a|(b+c).  If a|b and c\in R is arbitrary, then a|cb.  We now define an ideal to be any subset I of R such that a,b\in I implies (a+b)\in I, and a\in I,r\in R implies ra\in I.  If you think about it, ideals are very nearly the Dedekind cuts of R, under the divisibility relation!  “Ideal” originally stood for “ideal number,” because they generalize the “numbers” in R in the same way that the reals generalize the rationals.  (Though note that R doesn’t really embed into its set of ideals: if a|b and b|a, then (a)=(b).  If R is an integral domain, we have a=ub where u is a unit, an element with a multiplicative inverse, like \pm 1 in \mathbb{Z}.)

In particular, we can operate on ideals like we do on numbers.  The sum of two ideals, I+J, is just the set \{i+j:i\in I,j\in J\}.  This is clearly an ideal, and moreover, it’s the smallest ideal containing both I and J — their least upper bound under the inclusion relation.  The greatest lower bound, meanwhile, is just the intersection I\cap J.  But we can also take the product IJ — in order for this to be an ideal, we need to define it as \left\{\sum_{n=1}^N i_nj_n:i_n\in I,j_n\in J,N\in\mathbb{N}\right\}.  You should check that all of these operations give ideals, and that IJ\subseteq I\cap J for all I,J.  Sadly, sum isn’t a group operation, but we do have a semiring in the sense that product is associative and distributes over sum (and is commutative if R is).  But we are able to write generators for non-principal ideals: define (a_1,\dotsc,a_n)=(a_1)+\dotsb+(a_n), the set of “linear combinations” of the a_i.

So if ideals are idealized numbers, and we can idealize their sum and product like the above, we can also idealize primeness.  We define I to be a prime ideal if it’s not the whole ring, and if whenever xy\in I, then x\in I or y\in I.

And the beautiful thing is: in \mathbb{Z}[\sqrt{-5}], though numbers don’t factorize uniquely into primes, ideals factorize uniquely into prime ideals.  We have

\displaystyle (6)=(2)(3)=(2,1+\sqrt{-5})^2(3,2+\sqrt{-5})(3,1+\sqrt{-5})=(1+\sqrt{-5})(1-\sqrt{-5}).

And using a little more machinery, we’ll be able to show that all of the ideals in the middle are, in fact, prime.

I’ll conclude with an exploration of these ideas in the integers.  The integers are an integral domain, but they’re even nicer than most integral domains!  This is because of the following great and simple theorem:

  • Theorem (Division algorithm for the integers).  For any a,b\in\mathbb{Z} with b\ne 0, there exist a unique q,r\in\mathbb{Z} with 0\le r<b and a=bq+r.

So essentially, there’s a unique way to divide integers with remainder.  The proof is an easy induction, and is left to you.  (Euclid was the first to record this theorem; the q is for “quotient” and r for “remainder.”)  In general, we define a Euclidean domain to be an integral domain R with a Euclidean function d:R-\{0\}\rightarrow\mathbb{N}, such that for all a,b\in R with b\ne 0, we have q,r\in R with a=bq+r and either r=0 or d(r)<d(b).  In the integers, the absolute value is such a function (though there are others).

What makes this nice is the following.  Define the greatest common divisor or gcd of a,b\in R to be an element c\in R that divides a and b and is a multiple of anything that divides them both.  (Likewise, define the least common multiple or lcm to be an element that is divisible by both but divides everything else that’s divisible by both.)  These may not exist and aren’t uniquely defined; even in an integral domain, they’re only defined up to multiplication by a unit.  They do generalize the familiar notions of gcd and lcm in \mathbb{Z}, though.  We now have:

  • Theorem (Euclidean algorithm/Bézout’s identity).  In a Euclidean domain R, for any a,b\in R, there are x,y\in R with ax+by=\text{gcd}(a,b).

Proof.  As the name suggests, Euclid actually invented an algorithm to find the gcd, and a slight extension lets you get the identity.  It’s a pretty cool trick for hand math.  The division algorithm gives

\displaystyle a=bq_0+r_0.

If r_0=0, then b|a, so b=\text{gcd}(a,b).  If it’s not zero, we basically repeat the process until it becomes zero.

\displaystyle b=r_0q_1+r_1

\displaystyle r_0=r_1q_2+r_2

\displaystyle \vdots

If d is our Euclidean function, then d(r_i) is strictly decreasing until some r_i is zero, say r_{n-1}=r_nq_{n+1}.  I claim that r_n is the gcd.  Working back through the steps of the algorithm, we have

r_{n-2}=r_{n-1}q_n+r_n=r_n(q_{n+1}q_n+1)

r_{n-3}=r_{n-2}q_{n-1}+r_{n-1}=r_n(q_{n+1}q_nq_{n-1}+q_{n-1}+q_{n+1})

\vdots

And eventually, we have b and a as multiples of r_n.  But on the other hand:

r_n=r_{n-2}-r_{n-1}q_n

r_n=(r_{n-4}-r_{n-3}q_{n-2})-(r_{n-3}-r_{n-2}q_{n-1})q_n

\vdots

We continue substituting later remainders for earlier ones, and end with r_n=ax+by, the statement of Bézout’s identity.  This finally proves that r_n=\text{gcd}(a,b): if c|a,b, then c|ax+by=r_n, as desired.  \square

(All right, let’s do an example: for a=54, b=42, we have

54=42\cdot 1+12

42=12\cdot 3+6

12=6\cdot 2

so 6 is the gcd, and working backwards gives

6=42-12\cdot 3

6=42-(54-42)\cdot 3

6=54\cdot (-3)+42\cdot 4

which should give you some idea of how this works in practice.)

Here’s where I’m going with this: by induction, we can find gcds of arbitrary finite sets of elements of a Euclidean domain.  So if I=(a_1,\dotsc,a_n) in a Euclidean domain, and the gcd of the a_i is b, then a_i\in (b) for all i, since it divides all of them; but at the same time, b\in I because of Bézout’s identity expressing b as a linear combination of the a_i.  Thus, every ideal is of the form (b)!  We call a domain in which this holds a principal ideal domain or PID.  We have just shown:

  • Corollary. Every Euclidean domain is a principal ideal domain.

In the integers, this means that the only ideals are those of the form (n).  Note that (-n)=(n), so we might as well take n to be nonnegative.  A little thought gives us the following easy formulas for working with ideals: (m)+(n)=(\text{gcd}(m,n)),(m)\cap (n)=(\text{lcm}(m,n)),(m)(n)=(mn).  n generates a prime ideal iff for every xy divisible by n, either x or y is divisible by n.  In particular, this means the only factors n has are itself and units, so n is zero or a prime number.  So the only prime ideals are 0 and (p) for p prime.

Two other ideals are of special note: (0)=\{0\}, called the zero ideal, and (1)=\mathbb{Z}, called the unit ideal.  In any ring, the zero ideal is just \{0\} and the unit ideal is the whole ring — moreover, the unit ideal is the only one containing the ring’s units.  These are the largest and smallest possible ideals.  We say that an ideal is maximal if it’s not (1) but (1) is the only ideal containing it.  In the integers, it’s clear that if m|n, then (m)\supseteq (n).  Thus, the maximal ideals are those generated by numbers without factors — but these are just the prime ideals!  As we’ll see later, maximal ideals are prime in every ring, though the converse doesn’t always hold.

This concludes the “number-theoretic” approach to ideal theory, and hopefully a nice introduction to very basic number theory.  The other approach is the “ring-theoretic” one, which I’ll do next: we’ll show why ideals in rings are like normal subgroups in groups.

Advertisements

3 Comments so far
Leave a comment

[…] Ideals: Numbers But Better (thetwomeatmeal.wordpress.com) Share and Enjoy: […]

Pingback by Cthulhu and other crazies » Blog Archive » Checking for primes? Dumber algorithm is faster algorithm

Hi, nice write-up. It might be worth while to point out the difference between an irreducible element and prime element. In the ring Z[sqrt -5] I would not call 2 and 3 prime numbers but instead irreducible numbers. Call a number irreducible if its only factorization includes only units and itself. There is a good reason why mathematicians often define prime numbers as follows: p is prime if whenever p|ab then p|a or p|b. This generalizes nicely to ideals. We can say an ideal A divides an ideal B, if there is an ideal C such that B=AC, written A|B. Then prime ideal can be defined the same way as a prime number, and this is nice because we get to see more of an overlap now. P is a prime ideal if whenever P|AB, then P|A or P|B. It turns out this definition is equivalent to your definition for prime ideal (I think it is always equivalent, though I could be wrong in some cases).

My point is not to say that you are wrong in any way, I just thought you might enjoy the response.

Comment by norou

You should start blogging again. Your public needs you!

Comment by Lily




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: