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$
  • 6
    $\begingroup$ Why "loosely speaking"? $\endgroup$ – lhf Jul 21 '11 at 13:47
14
$\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$
  • $\begingroup$ Nice! This is much better than $n\log n$ to me. $\endgroup$ – Oen Jul 21 '11 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$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.