mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-04-19, 18:07   #1
flouran
 
flouran's Avatar
 
Dec 2008

34116 Posts
Default Erdos-Kac Theorem

A beautiful theorem in number theory, the Erdos-Kac Theorem is much revered. However, despite its straight-forward simplicity I have no idea how to use it. As stipulated by the theorem, let \omega(n) denote the number of distinct prime factors around a number n, let N(x,a,b) be the number of integers for which a \le \frac{\omega(n) - \log \log N}{\sqrt{\log \log N}} \le b holds. Then \lim_{x\to\infty}N(x,a,b) = (\frac{x+o(x)}{2})[erf(\frac{b}{\sqrt(2)})-erf(\frac{a}{\sqrt(2)})]. Now, say I set n to be 10^70. How, using the implications of the Erdos-Kac Theorem would I figure out the probability that a number near 10^70 has 2 distinct prime factors?
flouran is offline   Reply With Quote
Old 2009-04-19, 20:02   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·103 Posts
Default

Quote:
Originally Posted by flouran View Post
Now, say I set n to be 10^70. How, using the implications of the Erdos-Kac Theorem would I figure out the probability that a number near 10^70 has 2 distinct prime factors?
Roughly, Erdos-Kac says the number of factors is asymptotically normally distributed with mean and variance = log log n. ln(ln(10^70))=5.08

You have at least two problems in turning this into an estimate - what to do about "less than 1 factor" and how to turn the continuous distribution into a discrete estimate. Two simple ideas are "integrate from -infinity to 1.5 for 1 factor, 1.5 to 2.5 for 2 factors" and "Approximate as Poisson distribution with mean 5.08." We have an external estimate for 1 factor from the Prime Number Theorem - so I would use that to test the reasonableness of the two simple ideas.

Prime Number Theorem 1/ln(10^70) = 0.00620 (see caveat)

N((1.5-5.08)/sqrt(5.08)) = 0.05600

exp(-5.08) = 0.00620


Based on this comparison, I would use the Poisson approximation, which estimates the probability of exactly two distinct factors as 5.08*exp(-5.08) = 0.0315


(Caveat - we really need to juggle the Prime Number Theorem estimate to include prime powers as well as primes, but that isn't going to change the conclusion).
wblipp is offline   Reply With Quote
Old 2009-04-19, 21:52   #3
flouran
 
flouran's Avatar
 
Dec 2008

83310 Posts
Default

Quote:
Originally Posted by wblipp View Post
Roughly, Erdos-Kac says the number of factors is asymptotically normally distributed with mean and variance = log log n. ln(ln(10^70))=5.08
Based on this comparison, I would use the Poisson approximation, which estimates the probability of exactly two distinct factors as 5.08*exp(-5.08) = 0.0315
As I recall, for Poisson distribution, the probability mass function is given by Pr(\alpha; \beta)=\frac{\beta^{\alpha} e^{-\beta}}{{\alpha}!},\,\!, where \alpha is the number of occurrences and \beta is the number of expected occurrences. However, in your derivation, you assumed an occurence of \alpha = 1, why (is it because \alpha = \omega(n)-1)? Sorry for the trivial questions, it's just that I haven't really taken any applied math courses (like stats) yet.

Last fiddled with by flouran on 2009-04-19 at 21:54
flouran is offline   Reply With Quote
Old 2009-04-19, 22:03   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

I have earlier calculations that show that, when numbers around n average about k distinct prime factors, log log n ~= k - 0.3 for small k (less than 7). I'm curious as to why your continuity correction goes the other way (and yet seems not to go far enough!). Of course part of it is the problem of using that method to predict a point rather than a range.

I may have to do some crunching on the Poisson version; that looks like a promising method for certain applications.


Is there a version of Erdos-Kac that has an error term rather than an asymptotic statement?

Quote:
Originally Posted by wblipp View Post
(Caveat - we really need to juggle the Prime Number Theorem estimate to include prime powers as well as primes, but that isn't going to change the conclusion).
Is that really going to do anything? There are only o(n^0.5) nontrivial prime powers up to n, after all. In the case of 10^70, we're talking 1.2565e33 to 1.2568e33 out of 6.243e67.
CRGreathouse is offline   Reply With Quote
Old 2009-04-19, 22:09   #5
flouran
 
flouran's Avatar
 
Dec 2008

15018 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I may have to do some crunching on the Poisson version; that looks like a promising method for certain applications.
Considering the fact that we are dealing with discrete events, the Poisson distribution seems to be the way to go.

Anyone want to answer my "rather trivial" question though?
Quote:
Originally Posted by flouran View Post
However, in your derivation, you assumed an occurence of \alpha = 1, why (is it because \alpha = \omega(n)-1)? Sorry for the trivial questions, it's just that I haven't really taken any applied math courses (like stats) yet.

Last fiddled with by flouran on 2009-04-19 at 22:10
flouran is offline   Reply With Quote
Old 2009-04-19, 23:34   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by flouran View Post
Anyone want to answer my "rather trivial" question though?
It's hard because your question doesn't match the post very closely at all! But I'll try.

Quote:
Originally Posted by flouran View Post
However, in your derivation, you assumed an occurence of \alpha = 1, why (is it because \alpha = \omega(n)-1)?
He has omega(n) = 1, not 2, because he's looking at numbers with one, not two, prime factors (thus the "Prime Number Theorem" comment). His formula could only correspond to alpha = 0; I don't know why you'd write 1. His (fairly natural, IMO) model has one prime factor 'for free' and the others appearing in a Poisson process.

Last fiddled with by CRGreathouse on 2009-04-20 at 00:03
CRGreathouse is offline   Reply With Quote
Old 2009-04-19, 23:42   #7
flouran
 
flouran's Avatar
 
Dec 2008

15018 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
He has omega(n) = 1, not 2, because he's looking at numbers with one, not two, prime factors
Why? Aren't we looking for numbers with 2 distinct prime factors though (hence, shouldn't \alpha = 2)?

Last fiddled with by flouran on 2009-04-19 at 23:42
flouran is offline   Reply With Quote
Old 2009-04-19, 23:43   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by flouran View Post
Why? Aren't we looking for numbers with 2 distinct prime factors though (hence, shouldn't \alpha = 2)?
Please reread wblipp's post #2.

And I stress that I *don't* think Erdos-Kac is a good way to do this.

Last fiddled with by CRGreathouse on 2009-04-19 at 23:45
CRGreathouse is offline   Reply With Quote
Old 2009-04-19, 23:48   #9
flouran
 
flouran's Avatar
 
Dec 2008

15018 Posts
Default

What is the probability that a number near 10^70 has 3 distinct prime factors?
flouran is offline   Reply With Quote
Old 2009-04-19, 23:55   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by flouran View Post
What is the probability that a number near 10^70 has 3 distinct prime factors?
The mean is 5.082, the std. dev. is 2.25. 3 factors is just a bit more
than 1 std. dev. below the mean. The distribution is normal.....

I assume that you know how to use a lookup table???
R.D. Silverman is offline   Reply With Quote
Old 2009-04-19, 23:59   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by flouran View Post
What is the probability that a number near 10^70 has 3 distinct prime factors?
The Landau result would be 8.01%, which is the same as using the Hardy-Ramanujan mean as a Poisson lambda.

Erdos-Kac, with continuity correction as I suggested to you privately on Thursday (and as William suggests above), gives 11.5%.

Last fiddled with by CRGreathouse on 2009-04-20 at 00:03
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Erdos numbers xilman Lounge 83 2020-12-19 15:03
Copeland-Erdos Constant Primes rogue And now for something completely different 32 2016-06-20 01:55
Erdos-Turan Conjecture. wildrabbitt Math 4 2015-09-16 02:40
Number Theorem herege Math 25 2006-11-18 09:54
Størmer's theorem grandpascorpion Factoring 0 2006-09-10 04:59

All times are UTC. The time now is 18:56.


Tue Oct 26 18:56:43 UTC 2021 up 95 days, 13:25, 0 users, load averages: 2.44, 2.29, 2.41

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.