Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability Question

  1. May 29, 2006 #1
    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 [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.

    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. jcsd
  3. May 29, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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
  4. May 29, 2006 #3

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Subject to your showing that the probability of each incidence being true is 1/2, this probability is about 10^{-48}
     
  5. May 29, 2006 #4
    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)[/tex] or M(p) is not prime, i.e. [tex]S_{2^{p-1}} \neq 1 \mod M(p)[/tex] 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 [tex]S_{2^{p-1}} == 1 \mod M(p)[/tex]. 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 [tex]S_{2^{n}} \mod M(p) \mid 0 \leq n < i[/tex] 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 [tex]S_{n} \mod M(p) \mid n \in \mb{R}[/tex] 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.
     
  6. May 29, 2006 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Erm, and at which point do you prove that the probability is 1/2 at each stage? None as far as I can see.
     
  7. May 31, 2006 #6
    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.
     
  8. May 31, 2006 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  9. May 31, 2006 #8
    [tex]ST = (S_n)^{2} = (6*S_{n-1} - S_{n-2})^{2}[/tex]
    [tex]ST(n) = (((1+\sqrt{2})^{2n} - (1-\sqrt{2})^{2n})/4\sqrt{2})^{2}[/tex]
    [tex]ST_{2^{n}} = 4ST_{2^{n-1}}*(8ST_{2^{n-1}} +1)[/tex]

    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.
     
  10. May 31, 2006 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    But you claimed it was true, presumably for some reason: what was it?
     
  11. May 31, 2006 #10
    Where did I claimed it to be true? I only said it was a conjecture. It appears to be a very strong conjecture through.
     
  12. Jun 1, 2006 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    What's what in here? S_n is the n'th square triangular number, right? What do you do with the ST?
     
  13. Jun 1, 2006 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  14. Jun 6, 2006 #13
    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
     
  15. Jun 6, 2006 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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
  16. Jun 6, 2006 #15
    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
     
  17. Jun 6, 2006 #16

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    We have a formula for the n'th square tringular number. Post 8.
     
  18. Jun 6, 2006 #17
    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
     
  19. Jun 6, 2006 #18

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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 [tex]S_{2^{p-1}} \equiv 1 \mod M(p) [/tex]"

    I proved the 'if' direction. I don't see how to prove the 'only if' direction.
     
    Last edited: Jun 6, 2006
  20. Jun 6, 2006 #19
    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
     
  21. Jun 6, 2006 #20

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Probability Question
  1. Dependent probability (Replies: 4)

Loading...