## You are here

Homeproof that $4^x$ exceeds the product of the primes up to $x$

## Primary tabs

# proof that $4^{x}$ exceeds the product of the primes up to $x$

Statement. (Erdős & Surányi) Given the prime counting function $\pi(x)$ and notating the $i$th prime as $p_{i}$, the inequality

$4^{x}>\prod_{{i=1}}^{{\pi(x)}}p_{i}$ |

is always true for any nonnegative $x$. In other words, the $x$th power of 4 is greater than the primorial $\pi(x)\#$.

Note: $\lfloor x\rfloor$ is the integer nearest to the real number $x$ that’s not greater than $x$, while $\lceil x\rceil$ is the nearest integer to $x$ that’s not smaller than $x$.

Proof. It takes very little computational effort to verify this is true for $x$ set to 1 or 2. For larger $x$ we can high-ball the primorial $\pi(x)\#$ as

$2\prod_{{i=1}}^{{\lceil\frac{x}{2}\rceil}}2i+1$ |

(that is, twice the product of the odd numbers from 1 to $x$) and rephrase $4^{x}$ as

$2\prod_{{i=1}}^{{2x-1}}2.$ |

The first factor is obviously the same for both expressions, both iterators have the same start value, but cleary the iterator end values satisfy the inequality $(2x-1)>\lceil\frac{x}{2}\rceil$ as long as $x>2$. The first expression being iteratively multiplied clearly increases, but the second expression being iteratively multiplied is static (being a 2). This line of thought has failed to yield the desired result.

What if instead we divide both expressions by 2 and take their base 2 logarithms? Obviously, for half $4^{x}$,

$\log_{2}\left(\prod_{{i=1}}^{{2x-1}}2\right)=2x-1,$ |

giving us the sequence of odd numbers 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, etc. Not quite so obviously, for half our primorial high-ball, the base 2 logarithm is

$\frac{\log(\lceil\frac{x}{2}\rceil!!)}{log(2)},$ |

(where $\log(x)$ is the natural logarithm and $n!!$ is the double factorial), giving us the sequence (to 5 decimal places) 0, 1.58496, 1.58496, 3.90689, 3.90689, 6.71425, 6.71425, 9.88417, 9.88417, 13.3436, 13.3436, 17.044, 17.044, 20.9509, 20.9509, 25.0384, 25.0384, 29.2863, 29.2863, etc.

Unfortunately, both of these strategies are doomed to failure because eventually our high-ball for the primorial overtakes $4^{x}$. What Erdős and Surányi do instead is rephrase $x$ as $x=2n+1$ and then construct the binomial coefficient $\choose{2n+1}{n}$ and showing the relationship of this to $2^{x}$.

# References

- 1 Paul Erdős & János Surányi Topics in the theory of numbers New York: Springer (2003): 5.11

## Mathematics Subject Classification

11A41*no label found*11A25

*no label found*11N05

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Strategy for proof is flawed

I am aware that my initial strategy for this proof is flawed. At about x = 30, even [x/2]!! overtakes 2^(2x - 1). I'm still trying to figure out some high-ball for the primorial pi(x)# that can be proven to stay below 4^x.

## Re: Strategy for proof is flawed

What's wrong with using the binomial coefficients to prove this? They're nothing terribly advanced, and if you make sure to include the word "binomial coefficient" it will get linked, in case anyone finds the parentheses notation obfuscating. Besides, binomial coefficients were good enough for ErdÅ‘s.

## Re: Strategy for proof is flawed

i think that in view of the failed proof the article should be withdrawn.

if the author manages to construct a correct proof without

using binonial coefficients then that would in my view be a new proof that does not duplicate what we already have in PM and can be a new article.

## Re: Strategy for proof is flawed

Don't confuse my willingness to admit mistakes with a readiness to give up. I probably wouldn't be able to prove this in an olympiad-setting, but that's for the young anyway. A solution could present itself to me when I'm working on something else and this is at the fringe of my memory.