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. $$

$\endgroup$
1
  • 6
    $\begingroup$ Why "loosely speaking"? $\endgroup$
    – lhf
    Commented Jul 21, 2011 at 13:47

2 Answers 2

15
$\begingroup$

$\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.$$

$\endgroup$
1
  • $\begingroup$ Nice! This is much better than $n\log n$ to me. $\endgroup$
    – Oen
    Commented Jul 21, 2011 at 14:51
6
$\begingroup$

A short proof: Notice that all the primes $p$ with $n<p\leq 2n$ 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)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .