mersenneforum.org > Math Erdos-Kac Theorem
 Register FAQ Search Today's Posts Mark Forums Read

 2009-04-19, 18:07 #1 flouran     Dec 2008 34116 Posts 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?
2009-04-19, 20:02   #2
wblipp

"William"
May 2003
New Haven

23·103 Posts

Quote:
 Originally Posted by flouran 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).

2009-04-19, 21:52   #3
flouran

Dec 2008

83310 Posts

Quote:
 Originally Posted by wblipp 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

2009-04-19, 22:03   #4
CRGreathouse

Aug 2006

3·1,993 Posts

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

2009-04-19, 22:09   #5
flouran

Dec 2008

15018 Posts

Quote:
 Originally Posted by CRGreathouse 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 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

2009-04-19, 23:34   #6
CRGreathouse

Aug 2006

597910 Posts

Quote:
 Originally Posted by flouran 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 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

2009-04-19, 23:42   #7
flouran

Dec 2008

15018 Posts

Quote:
 Originally Posted by CRGreathouse 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

2009-04-19, 23:43   #8
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by flouran Why? Aren't we looking for numbers with 2 distinct prime factors though (hence, shouldn't $\alpha$ = 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

 2009-04-19, 23:48 #9 flouran     Dec 2008 15018 Posts What is the probability that a number near 10^70 has 3 distinct prime factors?
2009-04-19, 23:55   #10
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by flouran 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???

2009-04-19, 23:59   #11
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by flouran 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

 Similar Threads Thread Thread Starter Forum Replies Last Post xilman Lounge 83 2020-12-19 15:03 rogue And now for something completely different 32 2016-06-20 01:55 wildrabbitt Math 4 2015-09-16 02:40 herege Math 25 2006-11-18 09:54 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