# Prove $x \leq \left( 1 + \frac{\log x}{\log2} \right) ^{\pi(x)}$

I am asked to use the Fundamental Theorem of Arithmetic to show that:

For $x > 1, \; x \leq \left( 1 + \frac{\log x}{\log2} \right) ^{\pi(x)}$

I have that:

$\exists \text{ primes } p_1,\dots,p_{\pi(x)} \text{ and non-negative integers } n_1, \dots, n_{\pi(x)}$ such that:

$x = \prod \limits_{i=1}^{\pi(x)}{p_i^{n_i}}$ so then $\log x = \sum\limits_{i=1}^{\pi(x)}n_i\log p_i$

Now I'm thinking I can use $\prod \limits_{i=1}^{\pi(x)}{\left( 1 + \frac{\log x}{\log p_i}\right)}$ as a stepping stone since $\prod \limits_{i=1}^{\pi(x)}{\left( 1 + \frac{\log x}{\log p_i}\right)} \leq \left( 1 + \frac{\log x }{\log 2} \right)^{\pi(x)}$, but I'm unsure how I can show that:

$x \leq \prod \limits_{i=1}^{\pi(x)}{\left( 1 + \frac{\log x}{\log p_i}\right)}$

Any help you may be able to offer would be greatly appreciated, thank you!

• You can write every $k \leqslant x$ in the form $\prod_{i = 1}^{\pi(x)} p_i^{n_i}$. From $k \leqslant x$, what (simple) bounds can you find for $n_i$? – Daniel Fischer Oct 22 '17 at 13:50

By the fundamental theorem of arithmetic (in fact we don't need its full strength, only the [easier] existence of prime factorisations, not the uniqueness) every positive integer $k$ has a prime factorisation

$$k = \prod_{i = 1}^{\infty} p_i^{n_i} \tag{1}$$

where $(p_i)$ is the sequence of primes in ascending order and the exponents $n_i$ are nonnegative integers, only finitely many of which are nonzero. In particular for every $i$ we have the inequality

$$p_i^{n_i} \leqslant k \tag{2}$$

since the product of the other factors is $\geqslant 1$ (it's a positive integer). It follows that $n_i = 0$ if $p_i > k$, and thus for a positive integer $k \leqslant x$ we have the factorisation

$$k = \prod_{i = 1}^{\pi(x)} p_i^{n_i} \tag{1'}$$

and the inequality

$$p_i^{n_i} \leqslant k \leqslant x \tag{2'}$$

from which we obtain

$$n_i \leqslant \frac{\log k}{\log p_i} \leqslant \frac{\log x}{\log p_i} \tag{3}$$

by taking logarithms and rearranging. Thus in the factorisations of positive integers $\leqslant x$, there are

$$1 + \biggl\lfloor \frac{\log x}{\log p_i}\biggr\rfloor \leqslant 1 + \biggl\lfloor \frac{\log x}{\log 2}\biggr\rfloor \leqslant 1 + \frac{\log x}{\log 2}$$

possible exponents for the prime $p_i \leqslant x$ (namely $0, 1, \dotsc, \bigl\lfloor \frac{\log x}{\log p_i}\bigr\rfloor$). Using all possible combinations of the exponents that may appear in the factorisation of a positive integer $k \leqslant x$, we can create

$$\prod_{i = 1}^{\pi(x)}\biggl(1 + \biggl\lfloor \frac{\log x}{\log p_i}\biggr\rfloor\biggr) \leqslant \biggl(1 + \frac{\log x}{\log 2}\biggr)^{\pi(x)}$$

products. For $x \geqslant 3$, some of these products (and for not-small $x$ the overwhelming majority of these products) will be larger than $x$, but by the fundamental theorem of arithmetic, all positive integers $k \leqslant x$ have a representation as such a product, whence

$$\lfloor x\rfloor \leqslant \prod_{i = 1}^{\pi(x)}\biggl(1 + \biggl\lfloor \frac{\log x}{\log p_i}\biggr\rfloor\biggr) \leqslant \biggl(1 + \frac{\log x}{\log 2}\biggr)^{\pi(x)}\,. \tag{4}$$

This is almost the desired inequality, only that we have $\lfloor x\rfloor$ as the left hand side rather than $x$. For $x \geqslant 3$ there is always at least one product exceeding $x$, and thus there are at least $\lfloor x\rfloor + 1 > x$ products, whence we have the desired

$$x \leqslant \biggl(1 + \frac{\log x}{\log 2}\biggr)^{\pi(x)} \tag{5}$$

for $x \geqslant 3$. And for $x = 2$, $(4)$ is the same as $(5)$.

However, $(5)$ does not hold for all non-integral values $1 < x < 3$, for example with $x = \sqrt{8} = 2^{3/2}$ we have

$$\biggl(1 + \frac{\log \sqrt{8}}{\log 2}\biggr)^{\pi(\sqrt{8})} = \biggl(1 + \frac{3}{2}\biggr)^1 = \frac{5}{2} < \sqrt{8}\,.$$