10
$\begingroup$

I was reading Hanson's proof that $\prod\limits_{p^a \le n}p^a < 3^n$ where $p$ is a prime and it occurred to me that there might be a simpler argument for $\prod\limits_{p \le n} p < 3^n$. Am I wrong?

Here's the argument that I was thinking:

(1) Let $n\# = \prod\limits_{p \le n}p$

(2) For all $n \le 124$, $n\# < 3^n$.

This can be checked manually by comparing $p\#$ to $3^p$ for $p < 124$. In each case $3^p > p\#$

(3) Assume it is true up to some $n-1 \ge 124$

(4) We can assume that $n$ is odd since if it is not $n\# = (n-1)\#$.

(5) There exists $m$ such that $n = 4m-c$ and $c=1$ or $c=3$ with $m \ge 32$

(6) $\dfrac{(4m-c)\#}{m\#} = \dfrac{(4m-c)\#}{(2m)\#}\dfrac{(2m)\#}{(m)\#} < {{4m-c}\choose{2m}}{{2m}\choose{m}}$

Note: For each prime greater than $2m$, it will divide $(4m-c)!$ but not $(2m!)$ or $(2m-c)!$. For each prime $m < p \le 2m$, it will divide $(2m)!$ but not $m!$.

(7) ${{4m-c}\choose{2m}}{{2m}\choose{m}} = \left(\frac{(4m-c)\dots(2m+1)}{(2m-c)!}\right)\left(\frac{(2m)\dots(m+1)}{m!}\right) = {{4m-c}\choose{2m-c,m,m}}$

Where ${{4m-c}\choose{2m-c,m,m}} = \dfrac{(4m-c)!}{(2m-c)!(m!)(m!)}$

(8) Using the Multinomial Theorem:

$${{4m-c}\choose{2m-c,m,m}} = \left(\frac{1}{2^{2m-c}}\right){{4m-c}\choose{2m-c,m,m}}2^{2m-c} < \left(\frac{1}{2^{2m-c}}\right)(1+2)^{4m-c}$$

(9) For both $c=1$ and $c=3$, I can show that for $m\ge 32, \left(\frac{1}{2^{2m-c}}\right)3^{4m-c} < 3^{3m-c}$

  • For $c=1$:

$$\frac{3^{4m-1}}{2^{2m-1}} = \left(\frac{27}{2}\right)\left(\frac{81}{4}\right)^{m-1} < 14(21^{m-1})<9(27^{m-1}) = 3^{3m-1}$$

Note: Using induction, it can be show for $m\ge 2, (14)(21^{m-1}) < 9(27^{m-1})$

  • For $c=3$:

$$\frac{3^{4m-3}}{2^{2m-3}} = \left(\dfrac{3^9}{2^3}\right)\left(\frac{81}{4}\right)^{m-3} < (2461)(21^{m-3})<(27^{m-3}) = 3^{3m-3}$$

Note: Using induction, it can be show for $m\ge 32, (2461)(21^{m-3}) < 27^{m-3}$

(10) $n\# = (m\#)\left(\frac{(4m-c)\#}{m\#}\right) < (3^m)(3^{3m-c}) = 3^{4m-c} = 3^n$


Edit 1: Great point that I did not make clear that $p$ is only primes.

I have updated my question. To be clear $\prod\limits_{p \le n}p \ne n!$ is referring to the primorial.


Edit 2: Step (7) is completely wrong.

Clearly, if $(3m-c)! > (m!)(2m-c)!$, the value is lower not higher.

Edit 3: I think that I found a fix using the multinomial theorem.

I have corrected step (7) which was previously incorrect.

Please let me know if you see a problem with the updated argument.

—-

Edit 4: Step(8) is wrong.

To use the mutinomial coefficient, I need three discrete integers not two.

The corrected statement is $(1 + 2 + 1)$ which breaks the argument.

$\endgroup$
  • $\begingroup$ $n!$ is not less than $3^n$ for $n≥7$. Indeed, $7!=5040$ but $3^7=2187$. $\endgroup$ – lulu Sep 29 '18 at 11:54
  • $\begingroup$ This is $n\#$ which is only the primes. $n\# < n!$. $7\# = 7*5*3*2 < 2187$. $\endgroup$ – Larry Freeman Sep 29 '18 at 11:55
  • 1
    $\begingroup$ Ah. That's not what you wrote. Your product does not indicate that you are only looking at primes. $\endgroup$ – lulu Sep 29 '18 at 11:56
  • 2
    $\begingroup$ Re step 7: ${A\choose B}{B\choose C}\color{red}\ge {A\choose C}$ (combinatorical: pick $B$ from $A$ and then $C$ from these $B$ vs. pick $C$ from $A$) with equality only when $B=A$ or $B=C$ $\endgroup$ – Hagen von Eitzen Sep 29 '18 at 12:01
  • 2
    $\begingroup$ Sorry I don't see it. One reason why the proof cannot be correct is that nowhere in the proof do you use any properties of primes. If every odd integer happened to be prime then your argument would still work, but in this case proving something that is false. $\endgroup$ – Winther Sep 30 '18 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.