Probability of primality

siegert81 · 2011-02-12, 06:01

I notice that when I get a new number to test from GIMPS, the program will say that it has a 1 in 450,000 chance of being prime (not the actual probability). How is this probability determined? How can one calculate probabilities for other types of numbers (Proth, generalized Fermat, factorial, etc.)?

How does trial division up to N affect the probability of a number's primality?

ckdo · 2011-02-12, 07:10

Read "The Math".

NBtarheel_33 · 2011-02-12, 08:43

Quote:

Originally Posted by cmd

non it :

non probabilità non di non primalità

<snip crazy crap>

"

<Bob Silverman> Would you happen to be on quaaludes? </Bob Silverman>

mart_r · 2011-02-18, 19:06

Although I'm able to write at the same level of creativity as cmd does, it gets slightly irritating by now.

But that's beside the point, because

I, too, have a question about the probability of primality:
Look at the graph attached: it seems fairly less likely for a number n to be prime compared to the approximation via Mertens' theorem, if it's trial divided up to about n^¼. I've also checked this for numbers in the regions 10⁶ and a few others. The graphs always looked about the same: at some number x the purple line dropped below the blue line, reached a certain minimum, then turned around and headed toward 2.
Sure, I did expect it to look about that way, but what confuses me is that minimum value at around sqrt(sqrt(n)). Is there anything known about this?

(The difference is small, sure, but when I look for simultaneous primes, the difference between, for example, 3.95^14 and 4^14 becomes more significant...)

axn · 2011-02-18, 20:05

Quote:

Originally Posted by mart_r

I, too, have a question about the probability of primality:
Look at the graph attached: it seems fairly less likely for a number n to be prime compared to the approximation via Mertens' theorem, if it's trial divided up to about n^¼. I've also checked this for numbers in the regions 10⁶ and a few others. The graphs always looked about the same: at some number x the purple line dropped below the blue line, reached a certain minimum, then turned around and headed toward 2.
Sure, I did expect it to look about that way, but what confuses me is that minimum value at around sqrt(sqrt(n)). Is there anything known about this?

How was this graph generated? What are the axes? What is q1 & q2? The graph shapes are not consistent with the equations written there?

mart_r · 2011-02-18, 21:47

Quote:

Originally Posted by axn

How was this graph generated? What are the axes? What is q1 & q2? The graph shapes are not consistent with the equations written there?

I used one million values for n between 99,500,000 and 100,499,999 for the graph. The values of q₁ and q₂ are those on the y-axis for trial division up to p (x-axis).
The graph shapes are not consistent with the equations? Then my program/algorithm would be flawed... what graphs do you get for said values?

CRGreathouse · 2011-02-19, 00:45

I also have trouble understanding the graph.

mart_r · 2011-02-19, 08:19

Aah shoot, I went for ln instead of log... aaand mixed up the actual value with the reciprocal value, what's wrong with me???? I'll upload a new graph...

Anyway, for a better understanding (I hope): trial division up to p=1000 gives a probability of about (1.773*log(1000))/log(n) for n~10⁸ and (1.789*log(1000))/log(n) for lim n-->infinity.

mart_r · 2011-03-02, 17:24

I found some time to check through another calculation again, and the values do seem to fluctuate.

That means: let q_n denote the parameter such that the probability of primality for a number n, when trial divided up to p, equals log(n)/(q_n*log(p)).
According to Mertens' theorem, for n = infinity, q_inf converges to e^gamma as p increases. (And specifically, from what I can tell, q_inf ~ $e^{gamma}*(1+\frac{1}{sqrt p*log(p)})$ )
Applying SOE for a given n and juxtaposing the values for n = infinity, the value q_n for the fixed n fluctuates around the other, q_inf, as p increases, with a local minimum at p ~ n^0.362. Moreover, looking at the difference between the two values of q, there's a local maximum at p ~ n^0.288 which is of a much smaller scale than the local minimum. Again, before that, there is another yet smaller minimum at p ~ n^0.23...0.24.
(Mathematically correctly phrased? Unclear constant/letter assignment? Mr Silverman?:)

These are only results I obtained for relatively small n.
No conjecture, nothing I can prove, just sounding out.

CRGreathouse · 2011-03-03, 13:36

Quote:

Originally Posted by mart_r

That means: let q_n denote the parameter such that the probability of primality for a number n, when trial divided up to p, equals log(n)/(q_n*log(p)).

OK, this can be defined sensibly if we think of choosing a random number in so appropriate region of n (say, 0.9n to 1.1n) that is p-smooth. Of course the interval can be taken arbitrarily small if we're willing to look at large enough numbers.

Quote:

Originally Posted by mart_r

According to Mertens' theorem, for n = infinity, q_inf converges to e^gamma as p increases.

Right. Or rather the appropriate product converges to that value by Mertens' theorem, and for n sufficiently large (n ≫ p^{2 + ε}, I think) you have
$q_\infty\stackrel{\tiny\Delta}{=}\lim_{p\to\infty}q_p=e^\gamma.$

Quote:

Originally Posted by mart_r

And specifically, from what I can tell, q_inf ~ $e^{gamma}*(1+\frac{1}{sqrt p*log(p)})$

I trust this is to be interpreted as

$q_p=e^\gamma\left(1+\frac{1+o(1)}{\sqrt p\log p}\right)$

as $p\to\infty$ and $n\gg p^{2+\varepsilon}.$

Hmm. First of all, the best known bounds on the product itself are much weaker -- more like (1 + O(1/log^2 n)) than (1 + o(n^-.5)). Getting that part under that much control seems hard, probably of RH-like difficulty (though I don't know this!). Once you have a number for the product, though, you may have additional problems getting the numbers to work nicely if p is close to the square root of n, causing Maier-Granville type problems. (Fortunately the examples you have below have p small enough that I don't think this second type of problem will be an issue.)

Quote:

Originally Posted by mart_r

Applying SOE for a given n and juxtaposing the values for n = infinity, the value q_n for the fixed n fluctuates around the other, q_inf, as p increases, with a local minimum at p ~ n^0.362. Moreover, looking at the difference between the two values of q, there's a local maximum at p ~ n^0.288 which is of a much smaller scale than the local minimum. Again, before that, there is another yet smaller minimum at p ~ n^0.23...0.24.

I'm not sure I understand.

mart_r · 2011-03-03, 20:27

Quote:

Originally Posted by CRGreathouse

I trust this is to be interpreted as

$q_p=e^\gamma\left(1+\frac{1+o(1)}{\sqrt p\log p}\right)$

as $p\to\infty$ and $n\gg p^{2+\varepsilon}.$

Right, the error term behaves much like $\frac{Li(x)-Pi(x)}{sqrt x/log(x)}-1$ .
And I was looking for an acceptable approximation rather than a bound.

Quote:

Originally Posted by CRGreathouse

I'm not sure I understand.

Me, too :)

You see, for a long time I lived on the assumption that a number n, when trial divided up to p, has a chance of $\frac{2*\log p}{\log n}$ being prime. (Some time ago, axn pointed out to me that this is not quite true.) The only thing I do here is to elaborate on the "2" in this fraction.

Again, a nice graphic potpourri in the attachment. By the difference between the graphs you may see what I was referring to when I talked about these local maxima/minima.

And thanks for contributing so much to my "projects", it's highly appreciated.

2011-02-12, 06:01	#1
siegert81 Dec 2010 1001010₂ Posts	Probability of primality I notice that when I get a new number to test from GIMPS, the program will say that it has a 1 in 450,000 chance of being prime (not the actual probability). How is this probability determined? How can one calculate probabilities for other types of numbers (Proth, generalized Fermat, factorial, etc.)? How does trial division up to N affect the probability of a number's primality?

2011-02-18, 19:06	#4
mart_r Dec 2008 you know...around... 2²·11·17 Posts	Although I'm able to write at the same level of creativity as cmd does, it gets slightly irritating by now. But that's beside the point, because I, too, have a question about the probability of primality: Look at the graph attached: it seems fairly less likely for a number n to be prime compared to the approximation via Mertens' theorem, if it's trial divided up to about n^¼. I've also checked this for numbers in the regions 10⁶ and a few others. The graphs always looked about the same: at some number x the purple line dropped below the blue line, reached a certain minimum, then turned around and headed toward 2. Sure, I did expect it to look about that way, but what confuses me is that minimum value at around sqrt(sqrt(n)). Is there anything known about this? (The difference is small, sure, but when I look for simultaneous primes, the difference between, for example, 3.95^14 and 4^14 becomes more significant...) Attached Thumbnails

2011-02-19, 08:19	#8
mart_r Dec 2008 you know...around... 1354₈ Posts	Aah shoot, I went for ln instead of log... aaand mixed up the actual value with the reciprocal value, what's wrong with me???? I'll upload a new graph... Anyway, for a better understanding (I hope): trial division up to p=1000 gives a probability of about (1.773log(1000))/log(n) for n~10⁸ and (1.789log(1000))/log(n) for lim n-->infinity. Attached Thumbnails Last fiddled with by mart_r on 2011-02-19 at 08:27

2011-03-02, 17:24	#9
mart_r Dec 2008 you know...around... 2²·11·17 Posts	I found some time to check through another calculation again, and the values do seem to fluctuate. That means: let q_n denote the parameter such that the probability of primality for a number n, when trial divided up to p, equals log(n)/(q_nlog(p)). According to Mertens' theorem, for n = infinity, q_inf converges to e^gamma as p increases. (And specifically, from what I can tell, q_inf ~ $e^{gamma}(1+\frac{1}{sqrt plog(p)})$ ) Applying SOE for a given n and juxtaposing the values for n = infinity, the value q_n for the fixed n fluctuates around the other, q_inf, as p increases, with a local minimum at p ~ n^0.362. Moreover, looking at the difference between the two values of q, there's a local maximum at p ~ n^0.288 which is of a much smaller scale than the local minimum. Again, before that, there is another yet smaller minimum at p ~ n^0.23...0.24. (Mathematically correctly phrased? Unclear constant/letter assignment? Mr Silverman?:) These are only results I obtained for relatively small n. No conjecture, nothing I can prove, just sounding out. Last fiddled with by mart_r on 2011-03-02 at 17:27*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
probability	ATH	Homework Help	7	2014-10-23 00:50
Probability of factor (TF)	nuggetprime	Math	2	2011-03-19 22:14
Primality searches and primality successes	marco_calabresi	Information & Answers	3	2009-04-17 19:44
P-1 Probability question	JuanTutors	Factoring	2	2005-01-12 20:41
What is the probability distribution for M42 ?	dsouza123	Math	2	2004-06-02 02:16

2011-02-12, 07:10	#2
ckdo Dec 2007 Cleves, Germany 1022₈ Posts	Read "The Math".

2011-02-19, 00:45	#7
CRGreathouse Aug 2006 3·1,993 Posts	I also have trouble understanding the graph.