# Probability Question

1. May 29, 2006

### ramsey2879

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. 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 2. If this probability is expressed as a decimal number, how many zeros come between the first non zero digit and the decimal point? 2. May 29, 2006 ### 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. Last edited: May 29, 2006 3. May 29, 2006 ### Gokul43201 Staff Emeritus Subject to your showing that the probability of each incidence being true is 1/2, this probability is about 10^{-48} 4. May 29, 2006 ### ramsey2879 I am saying that if My conjecture is true then it must choose correctly from either M(p) is prime i.e. [tex]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 < 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.

5. May 29, 2006

### 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.

6. May 31, 2006

### ramsey2879

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 dont 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.

7. May 31, 2006

### 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?

8. May 31, 2006

### ramsey2879

$$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 occuring at random is.

9. May 31, 2006

### matt grime

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

10. May 31, 2006

### 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.

11. Jun 1, 2006

### matt grime

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

12. Jun 1, 2006

### 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.

13. Jun 6, 2006

### 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

14. Jun 6, 2006

### 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.

Last edited: Jun 6, 2006
15. Jun 6, 2006

### 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

16. Jun 6, 2006

### matt grime

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

17. Jun 6, 2006

### 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

18. Jun 6, 2006

### 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.

Last edited: Jun 6, 2006
19. Jun 6, 2006

### erszega

Well, post 1 says this:

"My conjecture that if p is odd then M(p) is prime if and only if [tex]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".

However, if the task is to prove

(i) ((1+t)^2n - (1-t)^2n) / (4t) = 1 (mod n), if n is a Mersenne prime >3, and t = sqrt(2),

then I also know of a proof!

(i) is the explicit formula for this recurrence relation:

(ii) G(n) = aG(n-1) + bG(n-2), a=6, b=-1, n>1, G(0)=0, G(1)=1

(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.
According to Theorem 6 of the article,

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.

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 !

So can somebody calculate the cycle length of (ii) reduced modulo a Mersenne prime?

Regards

20. Jun 6, 2006

### 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.

21. Jun 6, 2006

### 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.

22. Jun 10, 2006

### 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 [Broken] .

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)).

Last edited by a moderator: May 2, 2017
23. Jun 11, 2006

### matt grime

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

Last edited by a moderator: May 2, 2017
24. Jun 11, 2006

### 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).

25. Jun 11, 2006

### 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.

Last edited: Jun 11, 2006