Friday, June 03, 2005

Math Post the Second: On Factoring and Fermat

Prime factorization of integers, as promised.

This is a strongly intuitive thing. Prime numbers don't have any divisors; any number not a prime has several prime divisors, and since when you divide a number by something it gets smaller, if you just keep dividing out primes you'll eventually just get a big list of primes with no more composite part left. That part isn't actually so strange or difficult to understand; the other part is very obvious and yet extremely subtle. It's this: that factorization is unique, at least the list of factors is unique (six is two times three as much as it is three times two, but the way this is non-unique is pretty dumb, so we don't count it). Part of the subtlety is that the way to see the uniqueness isn't something I can explain as glibly as I can the existence; I hope another part will be illustrated by the following story.

Some people in the world have still heard of Fermat's Last Theorem; it got lots of play ten years ago, when it was just proven after a 350-year wait. The statement is simple enough: for any integers x, y, z, and n, none zero and n bigger than two, it is not the case that x^n+y^n=z^n. What most moderately informed non-mathematicians know is that the statement appeared in the margin of a book owned by Fermat accompanied by a notation to the effect that he knew a beautiful proof, but that the margin was too small to contain it. What moderately informed non-mathematicians generally do not know is that Fermat, like Newton, was quite the ass. Fermat was a lawyer and did math in his spare time, which is well and good until it turns out that the primary way he did math was by sending other mathematicians letters that amounted to schoolyard teasing: "I can prove this and you-oo ca-aan't!" It wasn't yet the tradition of his day to actually tell people how you proved the things you proved (you wouldn't believe how long the cubic and quartic equations were unpublished; solving cubics was a courtly version of a party trick for some of these guys), but he did occasionally do it. Thing is, knowing his methods, some very smart guys in the 1800s came up with what we still think was the proof he had.

It doesn't work. And the reason it doesn't is that prime factorizations stop being unique when you start looking at things only slightly more complicated than integers, but it's desperately easy to assume that it doesn't, particularly if you live hundreds of years ago and don't have access to modern algebra. In fact, this failure was only discovered because of this proof, and the methods for getting around it (and what grew out of them) currently go by the name of algebraic number theory. So uniqueness of factorization is a bit subtle. I'll assume the fact until I need the other things I need to explain it for other things, but just understand that it's subtle.

Next time: introduction to Group theory, my actual honest-to-goodness field.

(For the record, the example of non-unique factorization appears if you start with the integers, but just for kicks throw in a square root of negative five and all the sums and products you can make with integers and this new number. 'Prime' still makes sense, as does 'factorization,' as does 'unique.' The trouble is that the numbers 2, 3, 1 + sqrt(-5), and 1 - sqrt(-5) are all prime, and 6=2*3=(1 + sqrt(-5))(1 - sqrt(-5)), so factorization is still good but uniqueness is out the window)


Blogger Rousseau said...

Fun stuff!

Thing to add for your terminology people should know beforehand: subtle. (Not just in math speak, but Dennis speak)

11:59 AM  
Blogger Dennis said...

Well, thanks!

I imagine that the naive understanding of subtle will suffice until people can pick it up from context, which is a convenient excuse for not putting into words something I think I can't. But, to try: subtle for me means a combination of delicate, intricate, obscure, difficult, and the usual meaning of subtle. All these put together add up to almost what we started with, but not quite.

Again for the record, unique factorization is subtle in part because it's hard to explain, in part because it's very important, and in part because anything that has a group you can define in three different ways classifying the extent to which it fails is pretty out-there to begin with.

12:17 PM  
Blogger Rousseau said...

Keep them coming. I know others are reading this, theyre just too lazy to comment.

Random question: if someone proved a way to say whether one graph maps to another (graph isopmorphism) would that be useful or not?

3:55 PM  
Blogger Dennis said...

The new post is coming; my internet quit last night.

As to your question, just quickly in comments so I don't have to explain all the terminology: it kinda depends. There's already a perfectly serviceable algorithm to detect isomorphisms of finite graphs as long as all you're interested in is some method: try every possibility and check it locally. This is, as you might expect, rather slow. It is currently suspected that there is no fast algorithm to detect the existence of graph isomorphisms between arbitrary graphs, though I believe that the current best-bet is that the problem is not NP-complete. A fast algorithm to do this would be a reasonable-sized breakthrough (and of course a proof that there wasn't one would be a giant breakthrough). I hope that answers the question...

5:15 PM  
Blogger Vito said...

Actually unique factorization is quite straightforward to state (and the proof is not that hard): Each positive integer has one and only one prime factorization.

And it doesnt' really take a lot of effort to see what happens if you expand the field just slightly. If we move from natural numbers to integers (omitting zero*), it's trivially true that for any prime in N, there are actually 2 factorizations: 1p and (-1)(-p).

If we expand our set to be the Gaussian integers (and again omitting zero), we see that we have, as a minimum the factorizations for our prime p the two given above, plus i(-p) and (-i)p.

Now here's a more interesting thing: If we eliminate all the extra variations on factoring that we saw above, it's fairly obvious that for n in N the only complex factors that are possible are (a+bi)(a-bi) (although it's certainly possible that these are in fact non-prime in the gaussian integers). A bit of quick algebra shows that the natural numbers with complex factors all satisfy n=a^2+b^2. Now suppose we have n=a^2+b^2 and m=c^2+d^2 and we wish to show that there exist e and f such that mn=e^2+f^2. We can use our gaussian factorization of m and n and a bit of algebra to get the result quickly and easily:

* It's not strictly necessary to omit zero, but it is polite ;-)

2:23 PM  
Blogger Dennis said...

Vito: I would like first to point out that there is a difference between hard and subtle, which perhaps I should have made clearer before. The usual proofs for both the cases you're talking about depend on the property of having something like long division (called being a Euclidean ring), which is very rare among even commutative rings generally. The whole property of having such a well-behaved ordering is highly uncommon, and yes you can gloss over the issues by using the word "positive," but I want to bring out the ways that big stuff is hiding behind little stuff.

Second, I want to define unique factorization over the integers so I can generalize it to other rings later, where a notion of "natural number" is much less clear. In particular, I want to worry about things like order of multiplication (it can matter if the rings in question aren't commutative) and units and associate primes, because soon enough I won't be able to ignore these issues.

4:13 PM  

Post a Comment

<< Home