0
$\begingroup$

This is Problem 10.22 in The Nature Of Computation.

Show that any integer $x$ has at most $O(\log x/\log \log x)$ distinct prime factors. Hint: if we list the primes in increasing order, the $i$th prime is at least $i$.

The solution manual argues:

Since the $i$th prime is at least $i$, if $x$ has $d$ distinct factors then $x \geq d!$. Stirling's approximation gives $d! \geq d^d e^{-d}$, so if we pessimistically assume that $x = d!$ we have $\log x = \Theta(d\log d)$ and $\log \log x = \Theta(\log d)$. Then $$ d = \Theta\bigg(\frac{\log x}{\log d}\bigg) = \Theta\bigg(\frac{\log x}{\log \log x}\bigg)\,, $$ Replacing $\Theta$ with $O$ gives an upper bound that holds when $x \geq d!$.

This deduction doesn't appear fully kosher to me. Since we're interested in an upper bound for $d$ we need the lower bound $\log d \geq \log \log x$ for the central statement to hold. But we don't have such a lower bound. We pessimistically assumed that $x = d!$. In other words, $x \geq d!$. We can turn this into $\log \log x \geq \alpha \log d$ for some constant $\alpha$. But this inequality is pointing in the wrong direction.

$\endgroup$
2
$\begingroup$

I agree that there is a slight problem, but I don't see it at exactly the same place as you. It may also be irritating that it sets $x=d!$ 'pessimisticly', when that is really not necessary and $d!$ can be used at all times until the very end.

The problem is IMO the moment the proof goes from an inequality $d! \ge d^de^{-d}$ to a $\Theta$-statement, that requires inequalities in both directions. To put it bluntly, clearly, $d! \ge 1$, but obviously not $\log (d!) = \Theta(0)$.

Of course, the Stirling approximation provides the necessary accurancy that the inequality lacks:

$$d! \sim \sqrt{2\pi d}\space d^de^{-d}$$

which means (much more but also) there are $c_1,c_2 > 0$ with $$c_1\sqrt{2\pi d}\space d^de^{-d} \le d! \le c_2\sqrt{2\pi d}\space d^de^{-d},$$

which further imples

$$\log (c_1) + \frac12\log (2\pi) + \frac12\log (d) + d\log d-d \le \log d! \le \log (c_2) + \frac12\log (2\pi) + \frac12\log (d) + d\log d-d,$$

and on both sides the term $d\log d$-term dominates, the remaining terms are just $o(d\log d)$, so we get (as stated in the proof, but not really validated):

$$\log (d!) = \Theta (d\log d).$$

From that follows in the same way the also used:

$$\log \log (d!) = \Theta (\log d),$$

and we finally get

$$d=\Theta \left({\log (d!) \over \log\log (d!)}\right).$$

Note that this is a statement only about $d$ and $d!$, nothing about the original problem is used here. That statement implies there is a $c>0$ with

$$d \le c{\log (d!) \over \log\log (d!)}$$.

Now, to tackle the original problem, all that is now needed is to see that

$$d \le c{\log (x) \over \log\log (x)}$$

(with the exact same $c$ as before) is to simply note that $f(x)={\log (x) \over \log\log x}$ is monotincally increasing (for $x \ge e^e$), because $g(y)={y \over \log y}$ is monotonically increasing for $y \ge e$ and remember that $x \ge d!$.

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