A friend of mine asked for a proof that n# > n, for n ≥ 3.

The easiest proof I can think of is as follows: you begin with Bertrand's postulate, which states that there is always a prime in the interval [k+1, 2k] for any k. (The link goes to David Galvin's exposition of Erdos' elementary proof of this fact, which inspired the following rhyme from Erdos: "Chebyshev said it, and I say it again/There is always a prime between n and 2n." This proof depends on some properties of the prime factorizations of binomial coefficients.)

In particular, there is a prime p, which depends on n, in the interval (n/2, n]; this prime is strictly greater than n/2. Also, 2 is a prime. If n ≥ 4, then p ≠ 2, and we have n# > 2p > 2(n/2) = n. We only need to check n = 3, which is easy: 3# = (2)(3) = 6.

Of course, this proof is throwing out a ridiculously large amount of information. From repeatedly applying Bertrand's postulate we can do better; in particular we get n# > (n/2) (n/2)#. (I'm ignoring the fact that n/2 might not be an integer.) Repeating this we get n# > (n/2) (n/4) (n/4)#, and so on. If we repeat this k times, where k is the greatest integer less than log

_{2}n times, we get

n# > (n/2) (n/4) ... (n/2

^{k}) = n

^{k}/ 2

^{1+2+...+k}= n

^{k}/ 2

^{k(k+1)/2}.

Recalling that 2

^{k}≈ n, this is

n

^{lg n}/ n

^{((lg n) + 1)/2}

or on the order of n

^{(lg n)/2}. (lg denotes the base-2 logarithm.) For example, this tells us that 100# is at least 10

^{6}or so.

It's suspected that for all n > 1, there is a prime with n

^{2}< p < (n+1)

^{2}. This gives a stronger lower bound. Namely, let k be the largest integer less than or equal to n

^{1/2}. Thenn if this conjecture is true, there's a prime in each of (1,4), (4,9), (9,16), (16,25), ..., ((k-1)

^{2}, k

^{2}). The product of these primes is at least

(1)(4)(9)...((k-1)

^{2})

or ((k-1)!)

^{2}; this is on the order of (k/2e)

^{k}. (I've replaced k-1 with k here, and used Stirling's approximation.) Recalling that k ~ n

^{1/2}, this is (√(n)/2e)

^{√(n)}. For n = 100, this means 100# is at least 10

^{11}or so. (I'm not actually willing to write n# > (√(n)/2e)

^{√(n)}because I haven't carefully considered what's going on at the endpoints of the products.)

And here's a quick heuristic justification for why n# is about e

^{n}. Consider log n#; this is

Σ

_{k=1}

^{n}(log k) [k is prime]

where the expression "[n is prime]" is 1 if n is prime and 0 isn't. Now, from the Prime Number Theorem we know that the the "probability" that n is prime is 1/(log n). (This is how I remember the Prime Number Theorem; it's a bit silly, because a number is either prime or it's not, but I find it a useful heuristic.) So the "expectation" of log n# is

Σ

_{k=1}

^{n}(log k) (1/log k)

which is just the sum of n terms, each of which is equal to 1. So, in fact, 100# is about 10

^{43}. (This argument, of course, isn't rigorous.)

## No comments:

Post a Comment