Distribution of Mersenne Factors

[Batalov]

Originally Posted by tapion64

The path that leadeth to conjectures is beset on all sides by the inequeties of the selfish and the tyranny of evil men. Blessed is he who, in the name of charity and good will, shepherds the numbers through the valley of darkness, for he is truly their distribution's keeper and the finder of lost sense. But sometimes not.

Amen!

[tapion64]

Originally Posted by Batalov

Amen!

I like your paraphrasing of my quote better than my own quote >.>

[LaurV]

Well, you didn't get anything unusual. First, all the composite mersenne numbers are 7 (mod 8) so they must have at least one factor which is "7|8", and they always have an odd number of "7|8" factors, otherwise their product would not be 7|8. A composite mersenne can not have an even number of factors which are 7|8, because in this case their product two by two will be 1|8, so it can't be 2^n-1. In the same time, they may have, or may not have factors which are "1|8". These factors can came in arbitrary number, including zero. Also, a composite mersenne whose prime exponent p is 3|4 can have a factor which is 2p+1 [edit: two times bigger than p]. But a composite mersenne whose prime exponent p is 1|4, can not have a factor which is 2p+1, because in this case the factor will be 3|8, for example (take the pen!) which is impossible. The smallest possible factor can be 6p+1 in this case [edit: 6 times higher, the minimum factor]. There is no factor which is 4p+1, nor for p=1|4 neither for p=3|4, because in this case they can't be 1 or 7 mod 8. [edit: also both "2p+1 factors of mersenne numbers with p=3|4 exponents" and "6p+1 factors of mersenne numbers with p=1|4 exponents" are "7|8 factors" i.e. the smallest possible factors are always 7|8, statistically]



Therefore, if you take "all factors below a million", you will have in this set:

• factors of the form q = 7|8 = 2p+1 correspondent to prime exponents p=3|4, with p below 500k (i.e. 1M/2)
• factors of the form q = 7|8 = 6p+1 correspondent to prime exponents p=1|4, with p below 166k7 (i.e. 1M/6)
• other few factors of all forms for higher k, i.e. with k>=8 for p below 125k (i.e. 1M/8)

Put all these together and here is where your numbers come from. There will always be more factors of the form 7|8, and with 3|4 corespondent exponent, in any [0..N] natural set you take. This is valid for any set, not only mersenne, if you follow same conditions, and it leads nowhere. It is all a consequence of the form of the factors, of the fact that they are prime, and of the prime distribution (log(n)/n says something?). How many more, it depends on the N.

[science_man_88]

tapion have you looked at the thread about k values in mersenne factors ? , also have you considered that once 2kp+1 is eliminated you can say (2kp+1)(2jp+1) -> 4kjp^2+2kp+2jp+1 -> a new k value of (2kp+1)*j+k for all values j>=0. edit: is also eliminated;

[tapion64]

I'm aware of all of those things, @LaurV and scienceman. Note that primes = 2p+1 where p is also prime are Mersenne factors = 7 mod 8, if p are Sophie Germain primes = 3 mod 4. This 1:1 correspondence links them to the distribution of Sophie Germain primes (which occur evenly distributed among p = 1 and 3 mod 4). Then by taking the ratio among primes = 7 mod 8 that are Mersenne factors to those that aren't, we can multiply the expected factors that are = 7 mod 8 by the ratio again to get the expected number of factors = 1 mod 8. Then since Mersenne factors can only be = 1 or 7 mod 8, add the two estimations together and you get the number of expected Mersenne factors less than n.

Since Mersenne primes can only be = 7 mod 8, we should be able to discern a constant and a logarithmic factor that when multiplied by the expected number of Mersenne factors = 7 mod 8 will yield an approximation of Mersenne primes less than n. Note that Wagstaff came up with an estimation for Mersenne primes, his approximation was e^y/ln(2)*ln(ln(x)), where y is the Mascheroni constant. But there may be a way to state this as a ratio of primes = 7 mod p that are Mersenne primes, as opposed to just Mersenne factors.

[R.D. Silverman]

Originally Posted by Batalov

Amen!

I will inject one comment and then depart the entire thread.

The original question does not rise to the level of "conjecture".

It is a homework exercize from a course in analytic number theory
at (say) the 1st year graduate level.

[CRGreathouse]

Originally Posted by R.D. Silverman

It is a homework exercize from a course in analytic number theory
at (say) the 1st year graduate level.

How could that be? We don't even know whether there are infinitely many Mersenne primes, so it's consistent with current knowledge that all but finitely many Mersenne exponents are equivalent mod 8.

[tapion64]

Originally Posted by CRGreathouse

How could that be? We don't even know whether there are infinitely many Mersenne primes, so it's consistent with current knowledge that all but finitely many Mersenne exponents are equivalent mod 8.

Every prime occurs atleast once as a multiplicative order of 2 (I've proven this in another thread), and when they do it's as an order of a prime = 1 or 7 mod 8. All this conjecture hits on is the distribution of how often prime multiplicative orders occur, and thus how often factors of Mersenne numbers occur. It does not as yet have anything to do with the distribution of Mersenne primes (except that obviously the distribution of Mersenne primes is less than the distribution of Mersenne factors = 7 mod 8).

@Silverman the absent, the original question was clearly not a conjecture, it was a statement of a pattern, that led to the conjecture which links the distribution of Mersenne factors to the twin prime (or Shah-Wilson, technically) constant. As far as I can see, this is 'new', in that I can't find a published paper or textbook that asserts the same. There's clearly heuristical evidence for the conjecture, and there's a solid mathematical basis for it coming from the distribution of Sophie Germain primes.

EDIT: I did realize a mistake in the language I used. There's not a 1:1 correspondence from Sophie Germain primes = 3 mod 4 to primes = 7 mod 8, it's one way only. Clearly not all primes = 7 mod 8 have corresponding Sophie Germain primes (p-1)/2. But it doesn't affect the conjecture, as it only depends on the ratio of those which do have corresponding Sophie Germain primes.

[R.D. Silverman]

Originally Posted by CRGreathouse

How could that be? We don't even know whether there are infinitely many Mersenne primes, so it's consistent with current knowledge that all but finitely many Mersenne exponents are equivalent mod 8.

I am not sure what you are asking.

The question was about factors
of 2^p-1, for general p and such p are clearly equi-distributed mod 8
by e.g. PNT for AP. There are certainly infinitely many Mersenne numbers
and infinitely many prime factors of Mersenne numbers.

I am assuming, of course, that the definition of Mersenne number is
2^p-1 for prime p. I have also seen it defined as 2^n-1, for general n.

And of course, I am being pedantic in saying that we do know that there
are infinitely many Mersenne primes. We just have no proof..

[R.D. Silverman]

Originally Posted by R.D. Silverman

I am not sure what you are asking.

The question was about factors
of 2^p-1, for general p and such p are clearly equi-distributed mod 8
by e.g. PNT for AP. There are certainly infinitely many Mersenne numbers
and infinitely many prime factors of Mersenne numbers.

I am assuming, of course, that the definition of Mersenne number is
2^p-1 for prime p. I have also seen it defined as 2^n-1, for general n.

And of course, I am being pedantic in saying that we do know that there
are infinitely many Mersenne primes. We just have no proof..

A further note: Deriving this result should follow from a result of Fouvry
et.al. from the 80's in which they proved the first case of FLT was true
for infinitely many primes based upon a generalization of the Sophie Germain
criteria. They got counts for a given prime p of the number of primes of the
form 2p+1, 4p+1, 6p+1, ... 2kp+1, k = 1.....oo. Note that this preceded
Wiles' result.

[ewmayer]

Originally Posted by TheMawn

But yeah, the mathy people here don't take kindly to stats.

Not so - we don't take kindly to useless/misleading/bogus stats. Look closely and you'll see that statistics pervades every area of this forum, whether it be roundoff error handling in floating-point-based modmul math, or the large-scale distribution of primes of various kinds, or p-1, ecm and NFS factorization algorithms.