From: hook@nas.nasa.gov (Edward C. Hook) Subject: Re: Very Round Numbers. Date: 14 Sep 1999 20:17:29 GMT Newsgroups: sci.math Keywords: Bonse's inequality In article <37DE1D2F.52830F23@win.tue.nl>, Andre Engels writes: |> Bill Taylor wrote: [deletia --djr] |> Let p_n be the n'th prime, and let Q_n be prod{k=1...n}p_k. |> |> Then for your definition we need to prove that: |> n>3 => p_(n+1)*p_(n+2) incidentily was also the one I stumbled upon, we need the slightly |> weaker n>3 => p_(n+1)^2 (plus a separate check of all numbers upto 48 in both cases). |> The "slightly weaker" result is known as "Bonse's inequality". I'll resurrect (and slightly edit) an ancient post of mine which gives a proof of the result. After that, I'll indicate how to prove the stronger result that's mentioned up above. First, Bonse's inequality: >From hook Tue Mar 21 08:14:15 1995 >Date: Tue, 21 Mar 1995 08:14:14 -0800 >From: hook (Edward C. Hook) >Subject: Re: a property of 30 - sci.math #90022 >Status: RO A while ago, someone asked for a reference to a proof of the fact that 30 is the largest integer, n, with the property that k < n and (k,n) = 1 implies that k is prime. The poster recalled seeing a proof that showed that such an n must be less that 7^2 and then examined the few cases left in order to prove the result. I don't have a reference, but (while taking my shower this morning) I came up with what *must* be the proof alluded to above. It's based on a nice result that my ancient notes tell me is called "Bonse's inequality": Let p_k denote the k'th prime. Then (p_{n+1})^2 < p_1*p_2*...*p_n for n >= 4. If you grant me this result, then I can prove the assertion above concerning 30 as follows: If n has the stated property, and n >= p^2 for some prime p, then p | n. Therefore, if n >= 7^2, then n is divisible by 2, 3, 5 and 7. Hence, n >= 2*3*5*7 = p_1*p_2*p_3*p_4 > (p_5)^2 which implies that p_5 | n. But, then, n >= p_1*p_2*p_3*p_4*p_5 > (p_6)^2 ... and so forth. That is, an easy induction proves that, as soon as n >= 7^2, n is divisible by *every* prime. This absurdity establishes that there is *no* such n >= 7^2. Since 30 obviously has the property in question, and we can check that none of the integers strictly between 30 and 49 have the property, we're done. (-- If you're pressed for time, hit 'n' now --) Of course, the above inequality may not be near the top of most people's toolchests, so let me try my hand at a proof (following the hints in a problem set that I waded through *many* years ago). First, let k be a positive integer and consider the set { p_1*p_2*...*p_{k-1}*i - 1 | 1 <= i <= p_k }; no element of this set is divisible by any of the first k-1 primes and, if p >= p_k is any other prime, p can divide *at*most*one* element of this set. (If it divides 2 different elements, then it divides their difference which is of the form p_1*p_2*...*p_{k-1}*j with j < p_k -- impossible.) A peculiar consequence of this observation is that, if n - k + 1 < p_k, then there is some element of the set which is not divisible by any of the first n primes -- that's because each of the n - k + 1 primes p_k, ..., p_n can divide no more than one of the p_k elements of the set, so one version of the Pigeonhole Principle says that there's got to be some element left over. Such an element has its least prime divisor >= p_{n+1} and it is obviously <= p_1*p_2*...*p_k - 1, so we've proved: If n - k + 1 < p_k, then p_{n+1} < p_1*p_2*...*p_k. Now, fix n and let k be the *smallest* positive integer such that our cond- ition n - k + 1 < p_k holds. Then, n - (k-1) + 1 >= p_{k-1} or, equivalently, n - k >= p_{k-1} - 2. If you compare the values k & p_{k-1} - 2 for increasing k, you'll see that p_{k-1} - 2 >= k for k >= 5. (Well, you'll certainly see that this is true for k = 5 -- but, once it's true for some value of k, it's clearly true for all larger values since the LHS increases by at least 2 at each step ...) Furthermore, if n >= 10 and k is chosen as above, then necessarily k >= 5. (Otherwise, n >= 10 and k <= 4 implies that n - k + 1 >= 10 - 4 + 1 = 7 = p_4, contradicting the choice of k.) So we've reached our next waystation: If n >= 10, then p_{n+1} < p_1*p_2*...*p_k for some k such that n - k >= k. But, then, using the obvious fact that p_i < p_{k+i} for i > 0, we get (p_{n+1})^2 < (p_1*p_2*...*p_k)*(p_1*p_2*...*p_k) < (p_1*p_2*...*p_k)*(p_{k+1}*p_{k+2}*...*p_{2k}) < p_1*p_2*...*p_{2k}*p_{2k+1}*...*p_n which is Bonse's inequality. This completes the proof under the assumption that n >= 10. By inspecting the situation for smaller values of n, we find that, in fact, the inequality holds for n >= 4 (as originally asserted). And, for the stronger result: If you look carefully at what just happened, you'll see that we actually established (using Andre's notation): If n >= 10, then p_{n+1} < Q_k for some k >= 5 such that n - k >= k The other ingredient that's needed is Bertrand's Postulate, which assures us that p_{n+1} < p_{n+2} < 2p_{n+1}. Having that, we can adjust the argument above: p_{n+1}*p_{n+2} < (p_1*p_2*...*p_k)(2*p_1*p_2*...*p_k) (note the extra factor of 2 hiding in there). Then note that, for k > 1, 2*p_1 = 4 < 5 <= p_{k+1} and, as above, p_i < p_{k+i} for i > 1 to get the bound p_{n+1}*p_{n+2} < p_1*p_2*...*p_k*p_{k+1}*...*p_{2k} = Q_{2k} <= Q_n as desired (at least for n >= 10 -- one can then check what happens for n < 10 by hand & verify that the result holds for n > 3). -- Ed Hook | Copula eam, se non posit MRJ Technology Solutions, Inc. | acceptera jocularum. NAS, NASA Ames Research Center | I can barely speak for myself, much Internet: hook@nas.nasa.gov | less for my employer