The factorials are too damn high!
May 7, 2012 Leave a comment
Suppose I want to know how many factors of are in , for some . How would I go about computing that? For each even number less than or equal to , I get at least one factor of in . So The number of factors is at least . But there’s more. For the numbers divisible by , I only counted one copy of . I need to count another for each multiple of . There are multiples of less than or equal to . But then multiples of , , etc.
Let denote the number of factors of some prime in . The above argument generalizes to show that
Taking the floor of each term in the sum only makes things smaller, so we have the inequality:
Now suppose there were only finitely many primes. We can factor
We’re about to do some work with the exponents, so let’s take the log of everything in sight to make this notationally easier:
Now using our inequality from before,
I don’t particularly care what that sum is, but I do care that it’s some fixed number, independent of . If there were infinitely many primes, it would be an infinite sum that doesn’t converge, making the inequality say that , which is useless. But under the assumption that there are only finitely many primes, we know that there is some fixed constant (that sum) for which is never larger than . What this means is that always. This is just not true. If , then increasing makes grow faster than . More than that, how much faster is unbounded.
I don’t really want to go into the details here, but it should be believable that factorials grow faster than any exponential. That is, if you give me a constant , I can give you a number such that . To see exactly how fast they grow, have a look at Stirling’s approximation. Anyway, if there were finitely many primes, factorials wouldn’t be able to grow as fast as they should, so we have a contradiction. That is, there are infinitely many primes.