Confirming Conjecture of Mersenne Primes and Square Triangular Numbers

[ramsey2879]

I managed to write a basic program using true/false arrays with binary like addition subtraction and multiplication that checked all Mersenne numbers, M_p = 2^{p} -1 \mid p = \mb{prime} for primes from p = 3 up through p = 929 base upon the conjectured relation between Mersenne Primes and Square Triangular Numbers

I let my program run until it had checked the primeness of M(P) for first 160 odd primes (up through p = 929) and it correctly indicated whether M(p) is prime or not in this range for all odd primes.

My conjecture that if p is odd then M(p) is prime if and only if S_{2^{p-1}} == 1 \mod M(p) proved correct for each of these 160 odd primes. p = 2 is excluded from my conjecture since M(p) = 3 is a factor in my recursive formula for S_{2^{p-1}} where S_{n} squared is the nth square triangular number. <br /> <br /> Is it correct to say that there is less than a (1/2)^(160) probability that my conjecture is false and that a counter example exists for an odd prime? Assuming that no one finds a counter example of course<br /> 2. <br /> If this probability is expressed as a decimal number, how many zeros come between the first non zero digit and the decimal point?

 

[matt grime]

You are assuming at each prime you check that there is a 1/2 chance of it being correct. There is nothing (you have said) to support this belief at all.

If we assume that S_{2^{p-1}}==1 mod p is true at random half the time, then it is certainly compelling evidence, but I do not know that, and you have not justified why it is true.

 

[Gokul43201]

If this probability is expressed as a decimal number, how many zeros come between the first non zero digit and the decimal point?

Subject to your showing that the probability of each incidence being true is 1/2, this probability is about 10^{-48}

 

[ramsey2879]

You are assuming at each prime you check that there is a 1/2 chance of it being correct. There is nothing (you have said) to support this belief at all.

If we assume that S_{2^{p-1}}==1 mod p is true at random half the time, then it is certainly compelling evidence, but I do not know that, and you have not justified why it is true.

I am saying that if My conjecture is true then it must choose correctly from either M(p) is prime i.e. S_{2^{p-1}} = = 1 \mod M(p) or M(p) is not prime, i.e. S_{2^{p-1}} \neq 1 \mod M(p) for each prime p. For p = 3,5,7,13,17,19,31,61,89,107,127,521 and 607 M(p) = 2^p -1 is known to be a Mersenne prime and S_{2^{p-1}} == 1 \mod M(p). On the other hand for all primes in the set {,11,23,...929} where 2^{p} - 1 is not Mersenne Prime, it is true that [S_{2^{n}} \neq 1 \mod M(p) for any n greater than 0 as the cycle begins with 1,36, 11604 ... and much reach a point where a term is repeated and a new cylcle begins because these term involve straight forward multiplication in a like manner each time but the initial values are never obtained again mod M(p) as the cycle starts with [S_{2^{i} = S_{2^{i+j}} \ mod M(p) for some i > 0 and none of the values S_{2^{n}} \mod M(p) \mid 0 \leq n &lt; i appear more than once mod M{p} except for terms S_{m} where m is not a power of 2. Thus for 160 times in a row my test gave the correct result out of two possible choices.
Adding to the evidence is that for 2^{p} -1 = prime, that S_{n} \mod M(p) \mid n \in \mb{R} has a cycle period of 2^{p-1} + 1 but does not have such a period for all other values of p including non primes at least up to p = 26.

 

[matt grime]

Erm, and at which point do you prove that the probability is 1/2 at each stage? None as far as I can see.

 

[ramsey2879]

Erm, and at which point do you prove that the probability is 1/2 at each stage? None as far as I can see.

The period for the cycle in which M(p) = 2^{p} -1 is prime is p-2. That is that you start with a 1 and you don't get to back to 1 again until after p-1 iterations. When M(p) is not prime you never get to 1 again as the period doesn't start until you reached S_{2^n} for some n > 0. This reminds me of a continued fraction. It would be interesting to compute the continued fraction using numbers the generated by this algorithm of mine. I.E. where the numbers are S_{2^n} mod M(p). starting with S_{1}= 1. As for a proof, I am working on it.
Since there are only 2 choicies either 1 appears in the period and it first appears at S_{2^{p-1}} or 1 does not reappear again. I think my statement of the probability is correct. Remember the same algorithm is at work here for both cases and it answers true or false correctly for at least 160 times in sucession.

 

[matt grime]

Nope, I'm still looking for the bit where you state:

we know that if the behaviour were truly random then this would happen with probability 1/2.

Just explain that, nothing else. Having two possible outcomes is not a justification. You need to show that each possible outcome is equally likely if it were just 'at random'.

Incidentally, is there a formula for the 'n'th square triangular number'? Or some recurrence relation perhaps?

 

[ramsey2879]

Incidentally, is there a formula for the 'n'th square triangular number'? Or some recurrence relation perhaps?

ST = (S_n)^{2} = (6*S_{n-1} - S_{n-2})^{2}
ST(n) = (((1+\sqrt{2})^{2n} - (1-\sqrt{2})^{2n})/4\sqrt{2})^{2}
ST_{2^{n}} = 4ST_{2^{n-1}}*(8ST_{2^{n-1}} +1)

I think my last post was pretty specific to what the situation is. I guess that one with a knowledge of probability looking at it could figure out what the chances of this occurring at random is.

 

[matt grime]

I guess that one with a knowledge of probability looking at it could figure out what the chances of this occurring at random is.

But you claimed it was true, presumably for some reason: what was it?

 

[ramsey2879]

Where did I claimed it to be true? I only said it was a conjecture. It appears to be a very strong conjecture through.

 

[matt grime]

ST = (S_n)^{2} = (6*S_{n-1} - S_{n-2})^{2}
ST(n) = (((1+\sqrt{2})^{2n} - (1-\sqrt{2})^{2n})/4\sqrt{2})^{2}
ST_{2^{n}} = 4ST_{2^{n-1}}*(8ST_{2^{n-1}} +1)

What's what in here? S_n is the n'th square triangular number, right? What do you do with the ST?

 

[matt grime]

Right, using those above expressions it is straight forward (if you know one small fact) to prove that n an odd prime implies S_n congruent to 1 mod n as long as 2 is a square mod n.

Use the formula for ST(n), or more accurately its square root. For now let t be a symbol (we will replace it with sqrt(2) in a second).

If n is an odd prime then (1+t)^2n = 1+2t^n+t^{2n} which is the common fact you meet probably for the first time when you do galois theory: it just states that modulo a prime p (x+y)^p=x^p+y^p which is what too many students think is true in characteristic 0, too.

Anyway, (1+t)^2n - (1-t)^2n = 4t^n mod n, so dividing by 4t (remember we will think of t as sqrt(2) in a second) we get t^{n-1} mod n if n is an odd prime. Now, we can put sqrt(2) in for 2 to get
2^{(n-1)/2} so as long as 2 is a square mod n this is 1 mod n.

By quadratic reciprocity 2 is a square mod n iff n is congruent to 1 or 7 mod 8 which is certainly true for the Mersenne primes: 2^p - 1 is congruent to 7 mod 8 for p=>3.

Of course the interesting bit is now trying to prove the converse.

 

[erszega]

I am just asking for help:

I can't see what I think needs to be proved (most probably because of my inexperience - I started reading number theory texbooks just recently):

((1+t)^2n - (1-t)^2n) / (4t) = 1 mod M(p),

with t = sqrt(2), n = 2^(p-1), and M(p) = 2^p-1.

Regards

 

[matt grime]

What is to be proven is that that is true if and only if 2^p - 1 is a prime. The 'if' direction I did above, but I'm not sure about the 'only if' direction.

 

[erszega]

Let me try and do this in smaller steps:

I understand your proof as far as (1+t)^2n - (1-t)^2n = 4t^n mod n, although by n you mean a Mersenne prime. Then you divide both sides by 4t, to get
((1+t)^2n - (1-t)^2n) / (4t) = t^(n-1) mod n,
and then you prove that substituting sqrt(2) for t we get
t^(n-1) = 1 mod n, that is,

((1+t)^2n - (1-t)^2n) / (4t) = 1 mod n.

That is true, but then you say that ST(2^p-1) = 1 mod 2^p-1, where 2^p-1 is a Mersenne prime.
The assertion was that ST(2^(p-1)) = 1 mod 2^p-1

Regards

 

[matt grime]

We have a formula for the n'th square tringular number. Post 8.

 

[erszega]

For an amateur like I am, your style is sort of condensed, but it does make me try harder!

Was my logic right in concluding that what was proven was

((1+t)^2n - (1-t)^2n) / (4t) = 1 mod n ?

Let S(n) = ((1+t)^2n - (1-t)^2n) / (4t), then
ST(n) = (S(n))^2.

Also, if S(n) = 1 mod n, then ST(n) = 1 mod n, probably that's why you said "Use the formula for ST(n), or more accurately its square root".

I still understand the proof as saying that ST(2^p-1) = 1 mod 2^p-1, if 2^p-1 is a Mersenne prime, rather than ST(2^(p-1)) = 1 mod 2^p-1, which was the original conjecture.

If I missed something, please point it out for me, I am keen to find out.

Cheers

 

[matt grime]

You are indeed missing something, You do not have the conjecture correct, at least as far as I understand the conjecture. The conjecture was, I believe, that on reduction mod 2^p - 1 we get a) 1 if 2^p-1 is prime

b) not 1 if 2^p-1 is composite.

I showed that if 2^p-1 is prime, you do indeed get 1 on reduction mod 2^p-1, but the second part, that if 2^p -1 is composite the reduction mod 2^p-1 is not 1, is not something I even begin to see to show.here is Ramsey's conjecture verbatim:"My conjecture that if p is odd then M(p) is prime if and only if S_{2^{p-1}} \equiv 1 \mod M(p)"

I proved the 'if' direction. I don't see how to prove the 'only if' direction.

 

[erszega]

Well, post 1 says this:

"My conjecture that if p is odd then M(p) is prime if and only if S_{2^{p-1}} == 1 \mod M(p) proved correct for each of these 160 odd primes. p = 2 is excluded from my conjecture since M(p) = 3 is a factor in my recursive formula for S_{2^{p-1}} where S_{n} squared is the nth square triangular number&quot;.<br /> <br /> However, if the task is to prove<br /> <br /> (i) ((1+t)^2n - (1-t)^2n) / (4t) = 1 (mod n), if n is a Mersenne prime &gt;3, and t = sqrt(2),<br /> <br /> then I also know of a proof!<br /> <br /> (i) is the explicit formula for this recurrence relation:<br /> <br /> (ii) G(n) = aG(n-1) + bG(n-2), a=6, b=-1, n&gt;1, G(0)=0, G(1)=1<br /> <br /> (ii) is a Fibonacci type sequence. According to an article at http://www.damtp.cam.ac.uk/user/dv211/mathgaz06.pdf . all Fibonacci type sequences are cyclic when reduced modulo p a prime, that is for c denoting the cycle length, G(n+kc)=G(n) mod p, k a nonnegative integer.<br /> According to Theorem 6 of the article, <br /> <br /> if a^2 + 4b (in the generalised Fibonacci sequence G(n)=aG(n-1)+bG(n-2) ) is a quadratic residue modulo p, then the cycle length of the Fibonacci sequence reduced modulo p divides p-1.<br /> <br /> In (ii), a^2+4b = 32, which is a quadratic residue modulo any Mersenne prime, therefore the cycle length of (ii) reduced modulo prime 2^p-1 divides 2^p-2. This means that G(1 + 2^p - 2) = G(1) = 1 mod 2^p-1 !<br /> <br /> So can somebody calculate the cycle length of (ii) reduced modulo a Mersenne prime?<br /> <br /> Regards

 

[matt grime]

It's called a recurrence relation, or difference equation, normally.

I think you should try calculating what you need to: you're doing a good job so far, though please remember that it is the only if part that is going to be hard to prove even if it is true. I have no intuition in this area, so I don't know if it is even a reasonable conjecture. Even if it is, and even if it is true, I suspect it will be a very hard proof.

 

[erszega]

Thanks.

Just to say that my proof is not perfect because I said 32 is a quadratic residue modulo any Mersenne prime. I should have said any Mersenne prime >3.

I guess this would do as a proof for the statement of 32 being a quadratic residue:

if 32 is a quadratic residue mod 2^p-1, then there is a nonnegative k for which k(2^p-1)+32 is square. Choose k= 32, then 2^(p+5) is a square whenever p is odd. p is odd if 2^p-1 is a Mersenne prime >3.

 

[erszega]

I suggest that we make the conjecture more general, as not only Mersenne primes seem to have the described property, but "primes = +-1 mod 8", or "primes p such that 2 is a quadratic residue mod p", see http://www.research.att.com/~njas/sequences/A001132 .

For instance, 17 is not a Mersenne prime, and yet:

G(17) = 1 (mod 17), where G(n) = 6G(n-1) - G(n-2), G(0)=0, G(1)=1.

Also, it appears that for prime p = +-1 mod 8,

G(p) = 1 (mod p) and also G((p-1)/2+1) = 1 (mod p).

G(p) and G((p-1)/2+1) reminds me of the debate whether Ramsey meant ST(2^n-1) or ST(2^(n-1)): with p = 2^n-1, ST((p-1)/2+1) = ST(2^(n-1)).

 

[matt grime]

I suggest that we make the conjecture more general, as not only Mersenne primes seem to have the described property, but "primes = +-1 mod 8", or "primes p such that 2 is a quadratic residue mod p", see http://www.research.att.com/~njas/sequences/A001132 .

or you could just see what I proved above where it only required 2 a residue.

 

[erszega]

Thanks.
I think I have a proof for this:

G((p+1)/2) = 1 (mod p) if p is a prime such that 2 is a quadratic residue modulo p, where G(n) = 6G(n-1) - G(n-2), G(0)=0, G(1)=1.

Let bin(a,b) denote the binomial coefficient a! / ( b! (a - b)! ).

Then, if n is odd,
G(n) = bin(2n,1)2^-1 + bin(2n,3)2^0 + bin(2n,5)2^1 + ... + bin(2n,2n-1)2^(n-2), that is (hope my notation is ok):
G(n) = SUM[i=1 to n]( bin(2n,2i-1) * 2^(i-2) ).

When n = (p+1)/2, we will have

(i) G((p+1)/2) = SUM[i=1 to (p+1)/2]( bin(p+1,2i-1) * 2^(i-2) ).

As p is prime, there are only two addends in (i) without the factor p :
bin(p+1,1)2^-1 and bin(p+1,p)2^((p+1)/2-2). All the other addends have the factor p, and so they are congruent to zero modulo p. Therefore we can reduce (i) modulo p and say:

G((p+1)/2) = bin(p+1,1)2^-1 + bin(p+1,p)2^((p+1)/2-2) (mod p), that is

(ii) G((p+1)/2) = (p+1)/2 * ( 1 + 2^((p-1)/2) ) (mod p).

Now I found the following theorem in an algebra textbook:
"The necessary and sufficient condition for a number a to be a quadratic residue of a prime number p is that

a^((p-1)/2) = 1 (mod p)."

In this case, a=2 is a residue of p by definition, therefore (ii) becomes

G((p+1)/2) = (p+1)/2 * ( 1 + 1 ) (mod p), that is

G((p+1)/2) = p +1 = 1 (mod p).

When p = 2^q-1, (p+1)/2 = 2^(q-1), therefore I think that this proves the if part of Ramsey's conjecture even if Ramsey meant ST(2^(q-1)) = 1 (mod q).

 

[matt grime]

I think you have just rewritten what I put down using more words and symbols:

(1+t)^{2p} = 1+2t^p+t^{2p} mod p for p a prime, repeat for 1-t, add and we're done, which is the proof I offered a while ago now.

 

[erszega]

But I need to see it more detailed so I can understand, and besides it was fun doing the proof.
Just in case there are more people interested in this topic, I found another article related to the topic:

http://www.math.dartmouth.edu/~erik/GAC-Thesis.pdf

It helps make the if part of Ramsey's conjecture even more general:

From the generalised Fibonacci sequence
G(n) = aG(n-1) + b(Gn-2), G(0)=0, G(1)=1,

the article arrives at the following formula in easily understandable steps:

G(p) = (a^2 + 4b)^{(p-1)/2} (mod p) p a prime

What follows from this is that

G(p) = 1 (mod p) if (a^2 + 4b) is a quadratic residue of prime p.

 

[erszega]

In fact, http://www.damtp.cam.ac.uk/user/dv211/mathgaz06.pdf provides a more general guidance on cycle lengths.

I will use S(n) to denote the sequence S(n) = 6S(n-1) - S(n-2), S(0) = 0, S(1)=1

I first thought that Ramsey's conjecture may be generalised to this:
S((n-1)/2) = 1, mod n, if and only if n is prime, and 32 is a quadratic residue modulo n.
However, I found a counterexample for the only if part: S(17) = 1, mod 33.

So back to Ramsey's conjecture:

S(2^{n-1}) = 1, mod 2^n-1 if and only if 2^n - 1 is prime.

I am far from a proof, but I think that I found something that may be helpful:

Using the results in the article I referred to, the cycle length of S(n) modulo a prime p divides either p -1 (if 32 is a quadratic residue mod p) or p + 1 (if 32 is a non QR mod p). Let c(n) denote the cycle length modulo n, that is c(n) is the smallest positive integer z for which S(i) = S(i+z), mod n, for any integer i . My proposition (the issue is also dealt with at http://www.research.att.com/~njas/sequences/A001175 , http://www.mathpages.com/home/kmath078.htm , and probably elsewhere) is that if n = m * p^k, where p is prime, k and m are any positive integers, and p does not divide m, then

c(n) = lcm( p^{k-1} * c(p), c(m) ), where lcm is the least common multiple.
c(p), with p prime, however, has to be calculated first, separately.

For instance, 18375 = 3 * 5^3 * 7^2, and so
c(18375) = lcm( c(3), lcm( c(5)*5^2, c(7)*7 ) ) = lcm( 4, lcm( 6*25, 3*7 ) ) = 2100.
That is, S(k + 2100) = S(k), mod 18375.
I think this works for all Fibonacci sequences, including the classic f(n) = f(n-1) + f(n-2), f(0)=0, f(1)=1.

Now for S(n) = 1, mod n, we need c(n) | n-1 (because S(1)=1, so S(1 + n - 1) = 1, mod n).
Can we have c(n) | n-1 if n is composite?

We would be quite close to a proof of the only if if we could also prove that
if S(2^{n-1}) = 1, mod 2^n-1, then s(2^{n-1}-1) = 0, mod 2^n-1, because then 2^{n-1}-1 would have to be the length of a cycle.
Based on a reasoning using the Cassini relationship:
S(n-1)S(n+1) - S(n)^2 = -1,
I thought it was obvious that whenever S(n) = 1, mod n, then either S(n-1) = 0, mod n, or S(n+1) = 0, mod n, but then I found S(9) = 1, mod 9, and S(8) = 3, mod 9, S(10) = 3, mod 9 !