# Number of unique prime factors of n is O(log n/(log log n))?

1. Feb 10, 2015

1. The problem statement, all variables and given/known data

Let $f(n)$ denote the number of unique prime factors of some positive integer $n > 1$. Prove that $f(n) \in \mathcal{O}\left(\dfrac{\log n}{\log \log n}\right)$

2. Relevant equations

3. The attempt at a solution

Since every prime number except 2 is prime, an upper bound on the number of prime factors of any $n$ would be $k$ such that
$$\displaystyle{\dfrac{n}{\prod_{i=1}^{k}\left(2i-1\right)}=1}$$
$$\ln n=\sum_{i=1}^{k}\ln\left(2i-1\right)$$
Using AM-GM inequality,
$$\sum_{i=1}^{k}\ln\left(2i-1\right)\geq k\sqrt[k]{\prod_{i=1}^{k}\left(2i-1\right)}=k\sqrt[k]{n}$$
The best I can arrive at is:
$$\ln\ln n\geq\ln k+\dfrac{1}{k}\ln n$$
which is ugly. I've also tried attacking this with
$$\dfrac{\sqrt{n}}{\prod_{i=1}^{k}\left(2i-1\right)}=1$$
instead, but this makes my inequality uglier.

What should I do? Thanks!

2. Feb 10, 2015

### Staff: Mentor

I guess that last word should be "odd", otherwise the statement is odd (sorry ;)).
What does the next equation say? That equation has no solution for most n, I would expect an inequality here.

How do you get the equation below "Using AM-GM inequality,"?

3. Feb 10, 2015

Haha, yes it should read "odd".

The left hand side of the inequality is the arithmetic mean while the right hand side is the geometric mean:

$${\displaystyle \dfrac{\sum_{i=1}^{k}\ln\left(2i-1\right)}{k}\geq\sqrt[k]{\prod_{i=1}^{k}\left(2i-1\right)}}$$

I don't think this cuts through the problem though. :(

4. Feb 10, 2015

### haruspex

I would approach this another way entirely.
For any prime p < n, what is the probability that p|n?
Are these probabilities independent?
Using that, what is the average number of different primes that divide n?
To go further, need to use the usual formula for the density of primes. I assume you are allowed to use that.

Interestingly, I don't get the given answer. Seems too high. Is the ∈ symbol denoting 'behaves like' or 'is bounded above by'?

5. Feb 10, 2015

It means ${\displaystyle \limsup_{x\rightarrow\infty}\left[p\left(n\right)/\left(\dfrac{\log n}{\log\log n}\right)\right]<\infty}$.

Alternatively, $\exists c,n_{0} c\geq0$ and for all $n\geq n_{0}$, such that $\left|p\left(n\right)\right|\leq c\dfrac{\log n}{\log\log n}$.

I believe that means $p\left(n\right)$ is within some constant multiple of $\dfrac{\log n}{\log\log n}$ neglecting small $n<n_0$. So we don't need a very strong bound.

6. Feb 10, 2015

### haruspex

Well, no, that would mean it is asymptotically like $\dfrac{\log n}{\log\log n}$, whereas all your other statements say it is asymptotically bounded above by $\dfrac{\log n}{\log\log n}$.
I make the asymptotic behaviour $\ln\ln n$. If so, the given expression is indeed an asymptotic upper bound, but a very loose one.

Have you tried answering my other questions?

7. Feb 10, 2015

I will think about your approach. It seems to me that my approach would suffice if I can show that $Sorry I accidentally posted before answering your other questions. I'm still thinking about your approach. Our professor did emphasize that we didn't need to and shouldn't rely on the density of primes to prove this proposition. That seems to prevent your approach. Hm, I'm getting confused now. Doesn't it mean that [itex]p\left(n\right)$ is bounded above by some constant multiple of $\dfrac{\ln\ln n}{\ln n}$ as well as below by the negative of the same constant multiple of $\dfrac{\ln\ln n}{\ln n}$? Is this what you mean by "asymptotically behaves like" instead of "asymptotically bounded above by"?

Since $p\left(n\right)>0$ for all $n>0$, doesn't this suffice for the lower bound condition of $p\left(n\right)\in\mathcal{O}\left(...\right)$ so this reduces to a problem of finding the upper bound?

8. Feb 10, 2015

### haruspex

No, 'asymptotically behaves like' would mean $0 < {\displaystyle \lim_{x\rightarrow\infty}\left[p\left(n\right)/\left(\dfrac{\log n}{\log\log n}\right)\right]<\infty}$
Fair enough.

9. Feb 10, 2015

I see - thanks!

Yeah. I've been staring at my approach and it seems to get me to $\mathcal{O}\left(\dfrac{\ln n}{\sqrt[n]{n}}\right)$, which is still too loose. I really admire the people who led all the way to the PNT.

10. Feb 10, 2015

### haruspex

How about Sterling's formula? I think that'll do it. But you don't need to go to the trouble of eliminating even factors, that makes little difference.

11. Feb 10, 2015