Hand-waving asymptotics of the primorial function

Let n# be the "primorial" function, which is the product of all the primes less than or equal to n. So, for example, 7# = 8# = 9# = 10# = (2)(3)(5)(7) = 210.

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₂ 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⁶ or so.

It's suspected that for all n > 1, there is a prime with n² < p < (n+1)². 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)², k²). The product of these primes is at least

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

or ((k-1)!)²; 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¹¹ 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ⁿ. Consider log n#; this is

Σ_k=1ⁿ (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ⁿ (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⁴³. (This argument, of course, isn't rigorous.)