Mersenne primes with P=1 mod 4 and P=3 mod 4

[GP2]

According to Wagstaff's conjecture, as described at http://www.utm.edu/research/primes/n...tMersenne.html, there is a higher probability of 2^P-1 being prime if P=1 mod 4 than if P=3 mod 4.

(And of course there is 100% probability if P is prime and P=2 mod 4 ).

The probability of 2^P-1 being prime is conjectured to be (e^gamma log aP )/(P log 2), where a=2 if P=3 mod 4 and a=6 if P=1 mod 4, and gamma is Euler's constant 0.57721566490153286...

If we look at the known Mersenne primes, there are 23 exponents P with P=1 mod 4 and 15 exponents P with P=3 mod 4 (and obviously 1 with P=2 mod 4). See http://opteron.mersenneforum.org/png/P_mod_4.png. Interestingly enough all five of GIMPS's discoveries (not including the new M40) were P=1 mod 4 exponents.

Can we calculate the expected number of primes of each type based on Wagstaff's formula and see if it matches?

This is equivalent to flipping N different unbalanced coins, where each coin N_i has a different probability P_i of landing on heads. What is the expected number of heads, and what is the probability of M heads, where 0 <= M <= N ? We have the limiting case of M << N and P_i << 1.

The complication is that each P_i is different, otherwise it would be a simple calculation...

[GP2]

Naturally as P -> infinity, the ratio
log 6P / log 2P = (log 6 + log P) / (log 2 + log P) -> 1.

So eventually the number of P=1 mod 4 and P=3 mod 4 prime exponents should even out.

At the current leading edge of P = 21.5M, the ratio of probabilities is already down to 1.0625.

[nfortino]

The number of expected Mersenne primes below a certain exponent predicted Wagstaff's conjecture by can be found using the not so elegant solution of writing a program to add up all the probabilities for each prime up to and including 13466917. I get the results, in about 15 seconds:
Expected primes with p 1 mod 4 = 23.35, actual 23
Expected primes with p 3 mod 4 = 22.21, actual 15
Total expected primes 45.56, actual 38.
I had the program output relevant data at every Mersenne prime exponent, but that would make a long post. If anyone wants it, I will gladly post it. Clearly Wagstaff's conjecture is close with p=1mod4, but not very good with p=3mod4.

Regards,
Nick

[GP2]

I haven't verified your calculation, but if it's true I wonder if the low number of "P=3 mod 4" Mersenne primes constitutes a statistical anomaly at odds with Wagstaff's conjecture.

Then again the plot of
http://opteron.mersenneforum.org/png/P_mod_4.png
seems to show numerous consecutive streaks where P=1 mod 4 or P=3 mod 4 dominate. So maybe we're due for a long streak of "P=3 mod 4" Mersenne primes yet to be discovered.

[nfortino]

First, a verification would be appreciated. Second, it is worth noting there is no guarantee there are not undiscovered Mersenne primes with p=1mod4 with exponents below 13466917 (Although I find it hard to believe there are 7). Also, at the bottom of the prime page you gave a link to, there is a link for a loose justification of Wagstaff's conjecture. http://www.utm.edu/research/primes/m...heuristic.html Included is a method to evaluate the sum, but it looks like it will only work for very large N. However, I think an adaptation of the idea might help us.

[ewmayer]

I, too, have been puzzling over the apparent mismatch between
the statistical frequency of p == 1 and 3 mod 4 M-primes predicted
by Wagstaff's theorem and those actually seen for the 39 known odd-
exponent Mersennes, and traded some e-mails with Chris Caldwell
and Carl Pomerance about this back when the process of verifying
the "false alarm" M#40 was taking place this past June. Neither of
them was able to think of any obvious problem with Wagstaff's
prediction which might explain the discrepancy. Here's the original
e-mail I sent to them, with the false M#40 x'ed out to preserve the
anonymity of the person whose machine reported the number as
being prime:

Wagstaff's [1983] statistical argument predicts the probability that 2^p-1 is prime is about (e^gamma log(a*p))/(p log 2) where a=2 if p == 3 (mod 4) and a=6 if p == 1 (mod 4). This predicts that M(p) with p == 1 (mod 4) will always have a greater likelihood of being prime than those with p == 3 (mod 4), but that the ratio of exponents in the two congruence classes should tend towards one as p tends to infinity. (Since log(a*p) = log(a) + log(p), and the log(a) part is fixed and O(1), i.e. the log(p) part will dominate at large p.) Let's look at the actual data for the 40 known M-primes:

p p%4
-------- ---
3 3
5 1
7 3
13 1
17 1
19 3
31 3
61 1
89 1
107 3
127 3
521 1
607 3
1279 3
2203 3
2281 1
3217 1
4253 1
4423 3
9689 1
9941 1
11213 1
19937 1
21701 1
23209 1
44497 1
86243 3
110503 3
132049 1
216091 3
756839 3
859433 1
1257787 3
1398269 1
2976221 1
3021377 1
6972593 1
13466917 1
xxxxxxxx 1

Of the 39 known odd-exponent M-primes, 24 have p==1 mod 4 and 15 have p==3 mod 4.
Of the 20 largest-known M-primes, a whopping 15 have p==1 mod 4 and just 5 have p==3 mod 4!

So overall, we indeed see more primes having p == 1 (mod 4) as Wagstaff conjectures, but the trend with increasing p is the opposite of what we expect - we actually see a greater ratio of M(p) with p == 3 (mod 4) at small p than we do at the larger p. While this is a quite small sample in statistical terms, I'm surprised at the extent to which the ratio of p == 1 (mod 4) M-primes to p == 3 (mod 4) M-primes seems to go against the predicted trend.

It's also noteworthy that all six of the primes discovered to date by GIMPS have p == 1 (mod 4)! Not that I'm suggesting we restrict ourselves to solely to exponents in this congruence class, mind you - for all we know, the next six (or ten, or even twenty) might all have p == 3 (mod 4).


Using Wagstaff's conjectured odds of primality of

(e^gamma log(a*p))/(p log 2) where a=2 if p == 3 (mod 4) and a=6 if p == 1 (mod 4),

for p ~ 2^24, the expected ratio of 1 mod 4's to 3 mod 4's is

log(6*2^24)/log(2*2^24) ~= 1.063,

i.e. we should be seeing nearly equal numbers of each kind of exponent at this point - that's what made the excess number of 1 mod 4's among the 20 largest-known M-primes so striking (The 1.063 of course applies only to the high end of the range of primes discovered by GIMPS, but even at the low end the excess of 1 mod 4's predicted by the formula is not great. Could be just a statistical fluke, but perhaps Chris Caldwell can use one of his stats packages to tell us what the odds (among a random ensemble of 20-prime sets obeying the conjectured statistics) of fifteen 1 mod 4's versus just five 3 mod 4's is.

At that time, Chris replied with:

If these are independent trials with two outcomes (1 or 3 modulo 4); then the probability of getting 15 or more of 20 "1 (mod 4)"s is 0.020695 (0.028465 with a ratio of 1.063).

Now the one thing that has changed with the latest discovery is that M#40 actually has p == 3 mod 4, which breaks a string of 5 consecutive 1 mod 4s, and thus a "mere" 14 of the 20 largest-known Mersennes have p == 1 mod 4. That still seems improbable enough to perhaps indicate something interesting with regard to the apparent discrepancy with Wagstaff's prediction.

I'm sending a copy of this to sAM Wagstaff, to solicit his input - if he finds no simple way to explain the apparent discrepancy I'll probably put togther a short note about this for submission to the number theory mailing list, perhaps in conjunction with a link to the official press release announcing the discovery of M#40.

Best regards,
-Ernst

[nfortino]

Originally posted by ewmayer
Now the one thing that has changed with the latest discovery is that M#40 actually has p == 3 mod 4, which breaks a string of 5 consecutive 1 mod 4s, and thus a "mere" 14 of the 20 largest-known Mersennes have p == 1 mod 4.

Well, using a ratio of 1.063 between p=1mod4 and p=3mod4, and using a method that gets the same probability that 15 or more of the last 20 Mersenne primes have p=1mod4 as Dr. Caldwell got, I get a probability of 7.52% that at least 14 of the 20 have p=1mod4. Although this is still a low probability, it’s not overwhelmingly small. We could just be in a small fluke, or we may have missed one along the way.

[GP2]

I looked at the data files to see if there was any difference between exponents with P=1 mod 4 and with P=3 mod 4.

As you know, there is a certain error rate for Lucas-Lehmer testing of exponents, due to faulty hardware, overclocking, bad memory, cosmic rays or whatnot. Errors are discovered through double and triple checking, which is often done years after the original result for any given exponent.

It seems that results for exponents with P=1 mod 4 have about 1.025 - 1.03 times greater chance of having an error than exponents with P=3 mod 4. I don't know if this is statistically significant.

Taking only results for George Woltman's programs with program code W[A-Z][0-9] we get error rates of:

7019/(7019+235902) = 0.028894 for P=1 mod 4
6514/(6514+225060) = 0.028129 for P=3 mod 4

The ratio 0.028894/0.028129 = 1.027

Just fishing for any possible difference in the way Prime95 handles the two congruence classes of exponents...

[ewmayer]

Just got this reply from Carl Pomerance:

If you were to flip a
coin 20 times and got 14 or more of heads or of tails, the
chance would be 11.53%, and this would not be viewed as
terribly extraordinary. If it persists for the next 20,
then maybe you have something, but even then, it would only
be a hint.

Yes, 14 of 20 is a bit lopsided but by no
means extraordinary. I think this is another case of the human tendency
to try to spot patterns even where none exist. At this point, if anything
were anomalous in the mod-4 statistics, it would seem to be the excess
of p == 3 mod 4's at smaller exponents, the opposite of what one would
expect based on the asymptotics. But perhaps this is simply a scenario
in which the asymptotic behavior doesn't really take hold until p is very
large. (And even then it only does so in a long-term average sense, and
the few dozen "coin flips" we have made to date aren't enough to discern it.)
Looking again at the p mod 4's for the 39 known odd-exponent Mersennes,
I see the first 10 are evenly split between 1 and 3, then 4 of the next 5 are == 3,
10 of the next 11 are == 1 (including a run of seven consecutive 1 mod 4's,
from p = 9689 to 44497), 5 of the next 7 are == 3, then 5 consecutive 1s,
then the latest prime with p == 3 mod 4. Fairly typical behavior for a random
distribution, actually, and the "excess" of 3 mod 4s at small p (e.g. 9 of the
first 15, whereas we'd expect more 1s than 3s) magically vanishes if we
consider (say) the first 25. Again, the eye is drawn to the clumps.

In any event, #40 (in terms of discovery order - for all we know it may prove
to be #41 in terms of size) was a nice early Christmas gift.

[tom11784]

Originally posted by nfortino
The number of expected Mersenne primes below a certain exponent predicted Wagstaff's conjecture by can be found using the not so elegant solution of writing a program to add up all the probabilities for each prime up to and including 13466917. I get the results, in about 15 seconds:
Expected primes with p 1 mod 4 = 23.35, actual 23
Expected primes with p 3 mod 4 = 22.21, actual 15
Total expected primes 45.56, actual 38.
I had the program output relevant data at every Mersenne prime exponent, but that would make a long post. If anyone wants it, I will gladly post it. Clearly Wagstaff's conjecture is close with p=1mod4, but not very good with p=3mod4.

Regards,
Nick

Just for my curiosity ... what does the expected sum of p 3 mod 4 become if you replace a=2 by a=1 in that case?

[nfortino]

Originally posted by tom11784
Just for my curiosity ... what does the expected sum of p 3 mod 4 become if you replace a=2 by a=1 in that case?

Going to M13466917, I get 19.63 (actual 15) for p = 3 mod 4, and a total of 42.99 (actual 38) with a=1. Unfortunately, it still isn't quite right. Also, even if it happened to be right, in my opinion changing the constants is just a blind stab in the dark, and provides no support for the conjecture. Support for the current conjecture (along with the constants) can be found at http://www.utm.edu/research/primes/m...heuristic.html