November 11, 2019

What is a "beautiful" proof?

A couple weeks ago I was obsessed with a math problem. addition over the integers is commutative: a + b = b + a. Multiplication, which is repeated addition, is also commutative: a * b = b * a. Exponentiation, which is repeated multiplication, is not. Now, it turns out there are intuitive, non-geometric, first-principle proofs for addition and exponentiation, using group theory and number theory respectively. But what about multiplication? What's an intuitive, non-geometric proof that multiplication is commutative over the integers?

I asked this on Facebook, and got two classes of answers:

• Mathematicians: "Wow, that's a really interesting question!"
• Non-mathematicians: "This is stupid." Some of my favorites were "you should obviously learn some axiomatic set theory" (as if I don't teach it for a living) and "you're acting in bad faith, obviously multiplication is commutative, just break it down" (as if 'just break it down' is a valid proof technique).

The "official" proof for multiplication being commutative is a bunch of messy induction over Peano arithmetic. It's really unsatisfying to me. And that got me thinking about elegant proofs. I have a BA in math, but never felt math was "beautiful". It was always annoying grunt work, even when working in abstract domains. But in trying to work out exactly what I meant by "unsatisfying", I finally got that moment of seeing beautiful versus ugly math.

I figure if it took me ten years to feel it, it's probably not something a lot of people have felt, so now I wanna try to convey it in a way that's much better than I ever got while going through a whole degree in it! I'm going to use a different theorem: "the square root of two is irrational". I'll present two proofs for it, one ugly and one beautiful, and talk about the qualitative differences.

sqrt(2) is a canonical example of a "real" proof, to the point where you regularly see it used as an introduction to proof by contradiction. Here's how it works:

1. Assume sqrt(2) is rational. Then you can write it as p/q, which cannot be reduced further.
2. Square both sides to get 2 = p^2/q^2, or 2q^2 = p^2.
3. Since 2q^2 is even, p^2 must be even, which means p is even. This means we can rewrite p^2 as (2r)^2.
4. Now we have 2q^2 = 4r^2, or q^2 = 2r^2. By similar logic, we have q^2 = (2s)^2.
5. Plugging this back into our original equation, we have 2 = (2r^2)/(2s)^2, or sqrt(2) = 2r/2s.
6. Then sqrt(2) = r/s, but we already said p/q cannot be reduced further, so we have a contradiction.

It... works. But it's also really ugly. Steps 3-5 don't make sense: you're just moving numbers around in hopes of it getting us a solution. It almost seems like a coincidence that step 6 follows. Further, saying "well we found a smaller ratio, so our assumption that p/q was irreducible" is just an awfully odd property to hinge our proof on! It's like a magician's trick. Finally, while we use the "square-rootness" of it in step 2, the square-rootness matters only very subtly in step (4), by turning (2r)^2 into 4r^2 so we can divide both sides of the equation by 2.

It all feels very... artificial. Do you all see that? I'm not sure if that makes sense to other people as much as it does to me. It's just that this proof doesn't really give us any insight into how square roots work, or how rational numbers work, or anything really.

Okay, so here's a much more elegant proof.

1. Assume sqrt(2) is rational. Then you can write it as p/q, which cannot be reduced further.
2. This means that p and q are coprime: they share no factors in common.
3. 2 = p^2/q^2, or 2q^2 = p^2. So far, this is the exact same as the previous proof.
4. By the fundamental theorem of arithmetic, every number has a unique prime factorization. This means we can write p as p1^n1 * p2^n2 * ..., and corresponding for q.
5. (a^n)^2 = a^2n. So p^2 = p1^2n1 * p2^2n2 * ...
6. This means that p^2 and q^2 have an even number of prime factors. But 2q^2 must then have an odd number of prime factors. Which means that it's impossible for 2q^2=p^2 and we have a contradiction.

This proof is a bit more heavyweight than the previous proof, as it uses the fundamental theorem of arithmetic. Why, then, is it more elegant? First of all, it makes the square-rootness meaningful. There's a direct connection between the act of squaring and the parity of the prime factors. It doesn't have any busywork. Every step feels both natural and important. And "the parities don't match" is a much more damning contradiction than "oops we reduced it more".

There's also a pragmatic difference: the second proof is much stronger. The first proof doesn't do much besides prove the irrationality of sqrt(2). You have to do a bunch of work to extend it to sqrt(3), or the cube root of 2. But you can easily extend the second proof to cover any nth root of any prime number, and use that as a springboard to prove that any nth root of any whole number must be either whole or irrational. It gives us firepower.

That's what I was looking for in my multiplication question. Haven't found it yet, but I've seen some nice candidates! My favorite used the fact that whole numbers are totally ordered, which also explains why the proof doesn't extend to matrix or quaternion multiplication (which are both noncommutative).

If you're reading this on the web, you can subscribe here. Updates are once a week. My main website is here.

My new book, Logic for Programmers, is now in early access! Get it here.