07 November 2005

Lots of primes, but not so many proofs

There's a classic "topological" proof of the infinitude of primes given by Fürstenberg:
Consider the an unusual topology on \Z in which our basic open sets are both-ways-infinite arithmetic progressions (i.e. sets of the form \{ ... , c-d, c, c+d, c+2d , ... \}). It's clear the the intersection of two (and hence finitely many) basic opens is a basic open (or empty), and in general any open set is either empty or the union of possibly infinitely many of these basic opens, and is thus infinite. It's also the case that arithmetic progressions are closed. Since every integer that's not 1 or -1 is a multiple of some prime, the union over all primes p of the sequences \{ ... , -p , 0 , p , ... \} is exactly \Z \setminus \{ -1 , 1 \} . But if there were only finitely many primes, then this set would be closed, so \{ -1 , 1 \} would be open but finite, a contradiction.

I'd like to unpack this proof a bit. First of all, we don't need the topological language. It's enough to say that every number is divisible by some prime, so the only numbers that are in the intersection over all primes p of \{ np+k : 1\leq k \leq p-1 \} are 1 and -1, but that this set is infinite if there are only finitely many primes. In fact, we can do even better: \{ np+k : 1\leq k \leq p-1 \} contains the set of numbers that are 1 mod p, and the intersection of these sets is infinite if there are only finitely many primes (and none of them, clearly, are divisible by any primes). But why? One answer: The Chinese Remainder Theorem. Which is a heavy piece of machinery, and clearly more than we need. A better answer: because if some number c is in two arithmetic progressions, one with step-size d and the other with step-size e, then certainly c+de is also in both arithmetic progressions, as is c+2de, etc. And since 1 \in \bigcap_{p prime} \{ ... , 1-p, 1, 1+p , ... \}, if there are only finitely many primes, then 1+n\prod_{p prime} p is also in the set. But, of course, the proof doesn't even actually need all those infinitely many things that aren't divisible by any prime; 1 + \prod_{p prime} p is not divisible by any prime but is not one or minus one. Just as Euclid said.

Fürstenberg's proof obfuscates Euclid's original proof, but ultimately reduces to it. To unpack all the little claims in Fürstenberg's proof (e.g. that the intersection of finitely many basic opens is either empty or a basic open) requires Euclid-style arguments. As a way of thinking about this integers, Fürstenberg's proof is nice — describing all open sets, for instance, is nontrivial (right?) — and it shows some of the power of using topological language. But as a proof of in the infinitude of primes, it fails to say anything more than Euclid's (and, if claims that it's less explanatory than the earlier proof, perhaps it says yes; it is extremely obfuscated). Fürstenberg's proof of the infinitude of primes is simply Euclid's proof with garnish.


Theo said...

I do, however, consider the following a distinct proof:
By unique factorization, the harmonic sum \sum_{n=1}^{\infty} 1/n can be factorized as \prod_{p prime} \sum_{n=0}^\infty 1/p^n = \prod_{p prime} 1/(p-1). But the harmonic sum diverges, and so the product must be infinite.

I even consider this a different proof:
By unique factorization, the sum \sum_{n=1}^{\infty} 1/n^2 can be factorized as \prod_{p prime} \sum_{n=0}^\infty 1/p^{2n} = \prod_{p prime} 1/(p^2-1). But the sum is irrational (it evaluates to \pi^2/6), and so the product must be infinite.

I wonder if any of my readers have a better theory than I have (I'm going on intuition) for when two proofs are distinct.

Kenny said...

I've always figured something like that was going on in this topological proof, but it's good to see it spelled out like that. These two zeta-based proofs do seem different, though I'd like to investigate the latter one to make sure it doesn't smuggle something back in. And unique factorization seems to be almost giving away the game in terms of coming up with a "distinct" proof.

Anyway, as far as I know, there is no good theory of identity of proofs. I had a friend in Australia who wanted to work on this, and was therefore teaching a bunch of computer scientists topology, category theory, homotopies, linear logic, and the like. Philosophers of mathematics have only recently started looking at explanatoriness of proofs, but it seems that identity of proofs is an importantly related problem. I'll have to remember to think of that more often.