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

[madilyn]

Homework Statement

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

Homework Equations

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!

 

[mfb]

I don't understand your approach.

Since every prime number except 2 is prime

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,"?

 

[madilyn]

I don't understand your approach.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,"?

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. :(

 

[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'?

 

[madilyn]

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'?

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.

 

[haruspex]

I believe that means $p\left(n\right)$ is within some constant multiple of $\dfrac{\log n}{\log\log n}$

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?

 

[madilyn]

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'?

I will think about your approach. It seems to me that my approach would suffice if I can show that [itex]

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?

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

 

[haruspex]

Is this what you mean by "asymptotically behaves like"

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

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.

Fair enough.

 

[madilyn]

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

I see - thanks!

Fair enough.

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.

 

[haruspex]

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.

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.

 

[madilyn]

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.

I think Sterling's formula works and is cleaner than AM-GM on odd factors. I should've done that.

I got the production function in the geometric part wrong, otherwise I realized that approach works too after a few simplifying assumptions (as you've pointed out, this bound is really weak).

Thanks so much!