Doubts, scientific breakthroughs and conspiracy theories about Wagstaff Conjecture (from Lucky13)

[Madpoo]

Originally Posted by kriesel

I hope it's either statistical fluctuation, or an actual pattern with mathematical justification TBD, not a consequence of similar effect undiscovered bugs lurking in the primality test codes. Some of the codes have ancestry in common. If there was an issue in common, present in a bit of "DNA in common", despite the best efforts of the authors and extreme care in using differing programs on differing hardware in multiple confirmations by multiple individuals, how could we know?

If it helps put you at ease, the current iterations of programs can be run against the known primes that have an exponent == 3 mod 4, and I think those tests have been done lately and confirmed. But if in doubt, run your own test to make sure.

EDIT: By "done lately and confirmed" I mean there are people who do sometimes run new tests of previously discovered primes - the server doesn't accept them, but people do the tests, I guess just to see what happens, or whatever.

[kriesel]

Originally Posted by Madpoo

If it helps put you at ease, the current iterations of programs can be run against the known primes that have an exponent == 3 mod 4, and I think those tests have been done lately and confirmed. But if in doubt, run your own test to make sure.

EDIT: By "done lately and confirmed" I mean there are people who do sometimes run new tests of previously discovered primes - the server doesn't accept them, but people do the tests, I guess just to see what happens, or whatever.

Perhaps people rerun them to test their setup for reliability, or to see what sort of alert sound it might make. (No sound if it's a known one, in my experience.)

In PRP3, for the series of all known Mersenne exponents, I'm half way through M49 now, having started from M2, running the exponents big enough for gpuOwL V5.0-9c13870, and the lower exponents were run on prime95 v29.4b8.
After the gpuowl run completes (and perhaps with some delay if I've guessed M51 right), run times will go up at https://www.mersenneforum.org/showpo...6&postcount=10

Haven't seen anything out of the ordinary yet. That's encouraging but not definitive.

If they all pass, it does not necessarily mean the existing codes are without flaw.
If one fails, it does not necessarily mean the existing codes are flawed, it could be a transient hardware issue.There's a sliver of a chance of an error occurring outside the loop of iterations that are guarded for accuracy by the Gerbicz check.
No disrespect to any of the authors (or users, or hardware designers for that matter; some tasks are just very hard). I've fixed code that failed nonreproducibly at low rates. Ppb or lower frequency bugs can be hard to determine exist, much less identify and resolve. Current assignments can be of order 10¹⁸ core clocks to complete.

[GP2]

Originally Posted by Madpoo

I ran a quick count of the distinct exponents with any known factors and whether that exponent is 1 or 3 mod 4:

Mod Count
1 14,559,812 (49.301%)
3 14,972,752 (50.699%)

I wouldn't say it's a runaway for the 3 mod 4 exponents being factored. In fact it seems like a pretty basic variation around 50/50 based on an incomplete set.

But exponents of p=3 mod 4 do have slightly more factors than exponents of p=1 mod 4, as was noted as early as 1967 by Ehrman (and cited by Wagstaff in 1983).

So I would expect that the counts above will never be exactly 50/50 even theoretically. If you slightly alter the λ of a Poisson distribution then you slightly alter your counts at k=0.

We could look at the factors themselves, rather than distinct exponents with or without factors. Based on the same dataset I used before (frozen on 2018-12-01), I get:

                         all f    f <= 65 bits
p=1 mod 4, f=1 mod 8    9846883     9304449
p=3 mod 4, f=1 mod 8    9833742     9310151

p=1 mod 4, f=7 mod 8   10655959    10119410
p=3 mod 4, f=7 mod 8   11565454    11045807

So

1. There are more factors with f=7 (mod 8) than f=1 (mod 8)
2. The fact that exponents with p=3 (mod 4) are more likely to have factors than exponents with p=1 (mod 4) is due to the factors that are 7 (mod 8).
3. As your post also reflected, factors of size 65 bits or less are a pretty big subset of the set of all known factors

If p=3 mod 4 and 2p+1 is prime, then it's a factor of the Mersenne number with exponent p, and f=2p+1=7 mod 8. And if p=1 mod 4 then the smallest possible factor is 6p+1, and again in this case there will be f=6p+1=7 mod 8.

[preda]

Originally Posted by kriesel

I hope it's either statistical fluctuation, or an actual pattern with mathematical justification TBD, not a consequence of similar effect undiscovered bugs lurking in the primality test codes. Some of the codes have ancestry in common. If there was an issue in common, present in a bit of "DNA in common", despite the best efforts of the authors and extreme care in using differing programs on differing hardware in multiple confirmations by multiple individuals, how could we know?

I think we are confident with very high probability that the currently known mersenne primes (51 of them) are indeed prime.

So the "systematic error" could be only in the form of undiscovered primes (below the current wavefront).

If that would be the case, then the density of MPs would be even farther away from what's theoretically predicted.

[mart_r]

Originally Posted by GP2

1. There are more factors with f=7 (mod 8) than f=1 (mod 8)
2. The fact that exponents with p=3 (mod 4) are more likely to have factors than exponents with p=1 (mod 4) is due to the factors that are 7 (mod 8).
3. As your post also reflected, factors of size 65 bits or less are a pretty big subset of the set of all known factors

If p=3 mod 4 and 2p+1 is prime, then it's a factor of the Mersenne number with exponent p, and f=2p+1=7 mod 8. And if p=1 mod 4 then the smallest possible factor is 6p+1, and again in this case there will be f=6p+1=7 mod 8.

Not sure how good of a comparison they are, but generalized repunits may provide enough data for some empirical analysis.
Some time ago I searched for primes p such that 2kp+1 give less primes than average for small k, thus making it more probable that (b^p-1)/(b-1) is prime. The output was not that significant, as far as I remember, but it was just a thought.

[GP2]

Originally Posted by mart_r

Not sure how good of a comparison they are, but generalized repunits may provide enough data for some empirical analysis.
Some time ago I searched for primes p such that 2kp+1 give less primes than average for small k, thus making it more probable that (b^p-1)/(b-1) is prime. The output was not that significant, as far as I remember, but it was just a thought.

Paul Bourdelais is looking for generalized repunit primes, but I think he's only reached the 1M or 2M exponent ranges by now.

And apart from Wagstaff (b=−2), I've been doing ECM lately to find more factors for generalized repunits for bases 3, 5, 7, 11, 12 and −3, −5, −7, −10, −11, −12. I've contributed the factors to FactorDB and found some new PRP cofactors, But it's mostly very unexplored territory. For instance, for base b=3 I'm finding lots of small factors unknown by FactorDB at a wavefront of a mere p=63k or so, and at even lower p for the other bases.

So right now there just aren't that many known primes or semiprimes yet for these repunits, and the statistics are too low to be meaningful.

[GP2]

As mentioned earlier, filtering by non-tiny p is in practice equivalent to filtering by the asymmetricity of the factors that make up the semiprime.

We can only find relatively small factors, so beyond the Cunningham project range where nearly everything is fully factored, every Mersenne semprime or Wagstaff semiprime that we are capable of discovering is necessarily composed of two highly asymmetric factors.

These were the counts when we filtered Mersenne semiprimes by size of the exponent p:

Originally Posted by GP2

Mersenne semiprimes

             filter by
           p greater than:
           10^3 10^4 10^5
mod 4
     p=1    16   10    7
     p=3    30   20   14
mod 8
     p=1     8    5    3
     p=3    12    7    5
     p=5     8    5    4
     p=7    18   13    9

But if we consider only Mersenne semiprimes (of any size) where the bit length of the (smaller) factor is less than 5% of the bit length of the Mersenne number, then we get nearly the same counts as when we filter for exponent p < 10^3 :

Mersenne semiprimes

        filter by asymmetric bit length:
           len(small factor) < 0.05 *
           len(Mersenne number)
mod 4
     p=1    15
     p=3    29
mod 8
     p=1     8
     p=3    11
     p=5     7
     p=7    18

Similarly, these were the counts when we filtered Wagstaff semiprimes by size of the exponent p:

Originally Posted by GP2

Wagstaff semiprimes

             filter by
           p greater than:
           10^3 10^4 10^5
mod 4
     p=1    24   13    5
     p=3    13    6    2
mod 8
     p=1    14    9    3
     p=3     6    3    2
     p=5    10    4    2
     p=7     7    3    0

And again, if we consider only Wagstaff semiprimes (of any size) where the bit length of the (smaller) factor is less than 5% of the bit length of the Wagstaff number, then we get nearly the same counts as when we filter for exponent p < 10^3 :

Wagstaff semiprimes

        filter by asymmetric bit length:
           len(small factor) < 0.05 *
           len(Mersenne number)
mod 4
     p=1    21
     p=3    11
mod 8
     p=1    12
     p=3     5
     p=5     9
     p=7     6

[GP2]

All factors of Mersenne numbers are 1 or 7 (mod 8). But all factors in general are 1 or 5 (mod 6), except for 2 and 3.

Combining the two gives: All factors of Mersenne numbers are 1 or 7 or 17 or 23 (mod 24).

The various congruence classes are not equally likely (factor data frozen as of December 1):

[(1, 170925), (7, 190532), (17, 185312), (23, 207834)]      0M < p < 10M
[(1, 135127), (7, 150156), (17, 146802), (23, 165115)]     10M < p < 20M
[(1,  83674), (7,  95232), (17,  92200), (23, 104402)]    990M < p < 1000M

There is a marked difference between p=1 (mod 4) and p=3 (mod 4):

    p=1 (mod 4)
[(1,  85562), (7, 102644), (17,  92628), (23,  88934)]      0M < p < 10M
[(1,  67370), (7,  81196), (17,  73487), (23,  69787)]     10M < p < 20M
[(1,  41802), (7,  51688), (17,  46104), (23,  44159)]    990M < p < 1000M

    p=3 (mod 4)
[(1,  85363), (7,  87888), (17,  92684), (23, 118900)]      0M < p < 10M
[(1,  67757), (7,  68960), (17,  73315), (23,  95328)]     10M < p < 20M
[(1,  41872), (7,  43544), (17,  46096), (23,  60243)]    990M < p < 1000M

It's interesting, for example, that for exponents p=3 (mod 4), factors that are f=23 (mod 24) are found about one-third more frequently than the other kinds.

Empirically, all Mersenne numbers with odd exponent are 7 mod 24 (that is, the values of the Mersenne numbers themselves, not the values of the exponents).

Therefore a Mersenne semiprime must consist of either a (1, 7) mod 24 pair of factors or a (17, 23) mod 24 pair of factors. So the frequency asymmetries of 1,7,17,23 mod 24 factors maybe can start to explain why p=1 (mod 4) and p=3 (mod 4) seem to produce semiprimes with different likelihood?

[GP2]

Likewise, all factors of Wagstaff numbers are 1 or 3 (mod 8) and consequently 1, 11, 17, 19 (mod 24).

For all known factors (as of a couple of days ago), we also have asymmetries:

    all
[(1, 520596), (11, 807965), (17, 638798), (19, 672074)]

    p=1 (mod 4)
[(1, 257566), (11, 514932), (17, 316467), (19, 279297)]

    p=3 (mod 4)
[(1, 263030), (11, 293033), (17, 322331), (19, 392777)]

Empirically, all 2^n+1 with odd exponent are 9 mod 24, and Wagstaff numbers (2^n+1)/3 with odd exponent are all 11 or 19 mod 24, except for n=3 which gives (2^n+1)/3 = 3.

[science_man_88]

Originally Posted by GP2

All factors of Mersenne numbers are 1 or 7 (mod 8). But all factors in general are 1 or 5 (mod 6), except for 2 and 3.

Combining the two gives: All factors of Mersenne numbers are 1 or 7 or 17 or 23 (mod 24).

The various congruence classes are not equally likely (factor data frozen as of December 1):

[(1, 170925), (7, 190532), (17, 185312), (23, 207834)]      0M < p < 10M
[(1, 135127), (7, 150156), (17, 146802), (23, 165115)]     10M < p < 20M
[(1,  83674), (7,  95232), (17,  92200), (23, 104402)]    990M < p < 1000M

There is a marked difference between p=1 (mod 4) and p=3 (mod 4):

    p=1 (mod 4)
[(1,  85562), (7, 102644), (17,  92628), (23,  88934)]      0M < p < 10M
[(1,  67370), (7,  81196), (17,  73487), (23,  69787)]     10M < p < 20M
[(1,  41802), (7,  51688), (17,  46104), (23,  44159)]    990M < p < 1000M

    p=3 (mod 4)
[(1,  85363), (7,  87888), (17,  92684), (23, 118900)]      0M < p < 10M
[(1,  67757), (7,  68960), (17,  73315), (23,  95328)]     10M < p < 20M
[(1,  41872), (7,  43544), (17,  46096), (23,  60243)]    990M < p < 1000M

It's interesting, for example, that for exponents p=3 (mod 4), factors that are f=23 (mod 24) are found about one-third more frequently than the other kinds.

Empirically, all Mersenne numbers with odd exponent are 7 mod 24 (that is, the values of the Mersenne numbers themselves, not the values of the exponents).

Therefore a Mersenne semiprime must consist of either a (1, 7) mod 24 pair of factors or a (17, 23) mod 24 pair of factors. So the frequency asymmetries of 1,7,17,23 mod 24 factors maybe can start to explain why p=1 (mod 4) and p=3 (mod 4) seem to produce semiprimes with different likelihood?

no matter the mersenne with prime exponent, an odd number of prime factors need be 3 mod 4, 1 mod 4 can have any number at last check. so 7 mod 8 is slightly biased potentially from that. not just sophie germain primes.

[JeppeSN]

I do not know what "empirically" means in the preceding posts, but for any odd \(p\) we have \[2^p\equiv(-1)^p = -1 \pmod 3\] and also for any \(p\ge 3\) we have \[2^p=2^3\cdot 2^{p-3}\equiv 0\cdot 2^{p-3}=0 \pmod 8\] so if we combine, whenever \(p\) is both odd and at least three, then \(2^p\equiv 8 \pmod {24}\). Therefore \(2^p-1\equiv 7 \pmod {24}\) and \(2^p+1\equiv 9 \pmod {24}\).

/JeppeSN