The factorials are too damn high!

Suppose I want to know how many factors of 2 are in n!, for some n. How would I go about computing that? For each even number less than or equal to n, I get at least one factor of 2 in n!. So The number of factors is at least \lfloor\frac n2\rfloor. But there’s more. For the numbers divisible by 4, I only counted one copy of 2. I need to count another for each multiple of 4. There are \lfloor \frac n4\rfloor multiples of 4 less than or equal to n. But then multiples of 8, 16, etc.

Let D_p(n) denote the number of factors of some prime p in n!. The above argument generalizes to show that

D_p(n)=\lfloor\frac np\rfloor+\lfloor\frac n{p^2}\rfloor+\lfloor\frac n{p^3}\rfloor+\cdots

Taking the floor of each term in the sum only makes things smaller, so we have the inequality:

D_p(n)\le \frac np+\frac n{p^2}+\frac n{p^3}+\cdots=n\cdot\left(\frac 1{p-1}\right)

Now suppose there were only finitely many primes. We can factor

n!=\prod_{i=1}^rp_i^{D_{p_i}(n)}

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:

\log n!=\sum_{i=1}^r D_{p_i}(n)\cdot \log p_i.

Now using our inequality from before,

\log n! \le n\cdot\sum_{i=1}^r\left(\frac1{p_i-1}\right)\cdot\log p_i

I don’t particularly care what that sum is, but I do care that it’s some fixed number, independent of n. If there were infinitely many primes, it would be an infinite sum that doesn’t converge, making the inequality say that \log n!\le \infty, which is useless. But under the assumption that there are only finitely many primes, we know that there is some fixed constant c (that sum) for which \log n! is never larger than c\cdot n. What this means is that n!\le c^n always. This is just not true. If n>c, then increasing n makes n! grow faster than c^n. 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 c, I can give you a number N such that N!>c^N. 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.

Advertisements

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