• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter madilyn
  • Start date
  • #1
13
0

Homework Statement



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

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 [itex]n[/itex] would be [itex]k[/itex] such that
[tex]\displaystyle{\dfrac{n}{\prod_{i=1}^{k}\left(2i-1\right)}=1}[/tex]
[tex]\ln n=\sum_{i=1}^{k}\ln\left(2i-1\right)[/tex]
Using AM-GM inequality,
[tex]\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}[/tex]
The best I can arrive at is:
[tex]\ln\ln n\geq\ln k+\dfrac{1}{k}\ln n[/tex]
which is ugly. I've also tried attacking this with
[tex]\dfrac{\sqrt{n}}{\prod_{i=1}^{k}\left(2i-1\right)}=1[/tex]
instead, but this makes my inequality uglier.

What should I do? Thanks!
 

Answers and Replies

  • #2
34,060
9,934
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,"?
 
  • #3
13
0
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:

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

I don't think this cuts through the problem though. :(
 
  • #4
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,760
5,036
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
13
0
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 [itex]{\displaystyle \limsup_{x\rightarrow\infty}\left[p\left(n\right)/\left(\dfrac{\log n}{\log\log n}\right)\right]<\infty}[/itex].

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

I believe that means [itex]p\left(n\right)[/itex] is within some constant multiple of [itex]\dfrac{\log n}{\log\log n}[/itex] neglecting small [itex]n<n_0[/itex]. So we don't need a very strong bound.
 
  • #6
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,760
5,036
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?
 
  • #7
13
0
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 [itex]p\left(n\right)[/itex] is bounded above by some constant multiple of [itex]\dfrac{\ln\ln n}{\ln n}[/itex] as well as below by the negative of the same constant multiple of [itex]\dfrac{\ln\ln n}{\ln n}[/itex]? Is this what you mean by "asymptotically behaves like" instead of "asymptotically bounded above by"?

Since [itex]p\left(n\right)>0[/itex] for all [itex]n>0[/itex], doesn't this suffice for the lower bound condition of [itex]p\left(n\right)\in\mathcal{O}\left(...\right)[/itex] so this reduces to a problem of finding the upper bound?
 
  • #8
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,760
5,036
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.
 
  • #9
13
0
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 [itex]\mathcal{O}\left(\dfrac{\ln n}{\sqrt[n]{n}}\right)[/itex], which is still too loose. I really admire the people who led all the way to the PNT.
 
  • #10
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
32,760
5,036
I see - thanks!



Yeah. I've been staring at my approach and it seems to get me to [itex]\mathcal{O}\left(\dfrac{\ln n}{\sqrt[n]{n}}\right)[/itex], 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.
 
  • #11
13
0
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!
 

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

Replies
6
Views
41K
  • Last Post
Replies
5
Views
1K
Replies
2
Views
2K
  • Last Post
Replies
10
Views
4K
Replies
1
Views
1K
Replies
19
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
19K
Top