14
$\begingroup$

Let $n>1$ be an integer and let $\operatorname{rad}(n!)$ denote the radical of $n$-factorial. (The radical of an integer $m$ being, loosely speaking, the product of the prime divisors of $m$.)

Can one give an upper bound for $\log \operatorname{rad}(n!)$ better than $n\log n$?

Proof: $ \log \operatorname{rad}(n!) \leq \log (n!) \leq \log (n^n) \leq n \log n. $

  • 6
    Why "loosely speaking"?2011-07-21

2 Answers 2

14

$\text{rad}(n!)$ is just the product of the primes less than or equal to $n$ (so a primorial), so

$\log \text{ rad}(n!) = \mathop{\sum_{p \le n\;|\;p \text{ prime}}} \log p$

also known as the first Chebyshev function $\vartheta(n)$. The statement that $\vartheta(n) \sim n$ is equivalent to the prime number theorem, and the Riemann hypothesis gives bounds on the error of this approximation. More information is available at the Wikipedia article and in most books on analytic number theory.

Erdős' proof of Bertrand's postulate includes as a lemma the elementary upper bound

$\vartheta(n) \le n \log 4.$

  • 0
    Nice! This is much better than $n\log n$ to me.2011-07-21
6

A short proof: Notice that all the primes $p$ with $n must divide $\binom{2n}{n}$ so that $\frac{\text{rad}((2n)!)}{\text{rad}(n!)}\leq \binom{2n}{n}$. Also, $\binom{2n}{n}\leq 4^n$. Consequently for $n=2^k$

$\text{rad}(n!)\leq \binom{n}{n/2}\cdot \binom{n/2}{n/4}\cdots \binom{2}{1}\leq 4^\frac{n}{2} \cdot 4^\frac{n}{4}\cdots 2\leq 4^n$

and we see $\log \text{rad}(n!)\leq n\log 4$ for $n=2^k$. You can get other $n$ by noticing $\log \text{rad}(n!)$ is monotonic. (Without cleverness you could lose a factor of $2$ at worst)