Three conjectures looking for a proof 100Euro reward

[T.Rex]

Hi,

I've put on the http://mersenneforum.org/showthread.php?t=10670" the description of 3 conjectures that are waiting for a proof. I've already done half the proof for one of them (the easy part...).
I've provided PARI/gp code that exercises the 3 conjectures.

I'll give 100Euro for the guy/lady who will provide one proof out of the three.

These conjectures deal with properties of a Digraph under x^2-2 modulo a Mersenne, a Wagstaff or a Fermat prime, and they use cycles of length q-1 (Mersenne and Wagstaff) or 2^n-1 (Fermat).

The final idea/dream is to use cycles of length (q-1)/n for proving that such numbers are NOT prime, in order to speed up the search and proof.

The conjecture about Wagstaff numbers is already implemented as a "Vrba-Reix PRP" test in the LLR tool by Jean Penné, based on Prime95 library, which is usually used for looking at primes of the form: k*2^n+/-1 .

Come and have a look, have fun, and compete !

(And come look how big are the two new Prime Mersenne numbers we found at http://www.mersenne.org/" , and that I've verified.)

Tony

 

[T.Rex]

A .pdf summary of conjectures

I've summarized the information in this http://tony.reix.free.fr/Mersenne/SummaryOfThe3Conjectures.pdf" .
And here is a link to a http://www.cs.uwaterloo.ca/~tmjvasig/papers/newvasiga.pdf" r.
Tony

 

[dodo]

And now, the Voice of Ignorance speaks:

I believe Conjecture 1 (or half of it) would be easier if the sequence was indexed from 1 instead of 0. Then its closed form would be Sn = 3^(2^n) + 3^-(2^n) (mod Mq). (Just square S1 to convince yourself.)

Now, Sq = 3 . 3^Mq + 3^-1 . 3^-Mq;
if Mq is prime then, by Fermat's Little Theorem, Sq = 3^2 + 3^-2 (mod Mq) = S1.

 

[T.Rex]

2 proofs of the first part of Conjectures 2 & 3

Hi,

Mister Robert Gerbicz has provided a proof for the first (the easier, but not so easy !) part of Conjectures 2 and 3. See http://robert.gerbicz.googlepages.com/WagstaffAndFermat.pdf" .

Though this paper needs some cleaning and clarifications, 2 persons at least have read it. I've found no problem. Quite easy to understand. But guessing how he got the ideas. You are welcome to read it and make comments if you feel that some part is unclear or wrong.

This means that there is now a fast PRP test for Wagstaff numbers !
{Fast here means that this PRP test is about as fast as Prime95 is for Mersenne numbers.}

A first step forward.
Now, the converses (the hard part...).

Tony

 

[T.Rex]

INdex from 1 to q, instead of 0 to q-1.

I believe Conjecture 1 (or half of it) would be easier if the sequence was indexed from 1 instead of 0.

Good comment ! It is exactly what Mr Gerbicz did in his proof !

Notice that it is possible to use the same seed 1/4 for Conjectures 2 & 3.

Because all cycles are of length (q-1)/m, I prefer that the seed be named S0. So that the iterations are from 1 to q-1. But this is a detail...

Tony

 

[dodo]

You're welcome :)

About the other direction of the conjectures (the "only if" part), I presume you'd need an extra condition (perhaps that's your intention anyway).

For example, in conjecture 1, since the idea is to form a cycle when Mq is prime, I presume you mean "iff Sq = S0 (mod Mq) and for no other 0 < i < q is Si = S0 (mod Mi)"; that is, "and no smaller index closes the cycle first". I imagine you don't intend Mq to be prime on every loop of the cycle, just on the first.

(This is in the spirit of the http://mathworld.wolfram.com/FermatsLittleTheoremConverse.html" .)

 

[T.Rex]

About the other direction of the conjectures (the "only if" part), I presume you'd need an extra condition (perhaps that's your intention anyway).

For example, in conjecture 1, since the idea is to form a cycle when Mq is prime, I presume you mean "iff Sq = S0 (mod Mq) and for no other 0 < i < q is Si = S0 (mod Mi)"; that is, "and no smaller index closes the cycle first".

Yes ! You are perfectly right !

Clear that this problem you are talking about does not appear when using LLT with the Digraph-tree, since once you've reached Si=0 then the next steps are: -2, 2, 2, 2, ...

With cycles, yes there is the risk to be in a (q-1)/m cycle. So that, after q-1 steps, S0 is back, but it is not a proof that the number is prime since only (q-1)/m steps are different.

The number is prime if the Cycle is a "pure" one (not a multiple of a sub-cycle).

As you said, yes this is comparable to the "converse of Fermat's Little Theorem".

Good remark, again ! Thanks ! I'll modify the conjectures !

I imagine you don't intend Mq to be prime on every loop of the cycle, just on the first.

Sorry, I don't understand. Can you elaborate ?

Thanks,

Tony

 

[T.Rex]

Not only a matter of primality proving. More.

For those who are reading this thread, let me remind that this thread does not only deal with some new theorems helping to prove that some special numbers (Mersenne, Wagstaff, Fermat) are primes.

If it was only this, then it would only worth to prove Conjecture 2 about Wagstaff numbers, since there is no fast primality test yet for these numbers.

First, it may end with the possibility to use smaller cycles (q-1)/m with m>1 to prove that one of these numbers is NOT prime.
It would speed up the GIMPS project or it would help to know about $$F_{33}$$, the 33th Fermat number.

Second, the LLT iteration $$S_{i+1}=S_{i}^2-2 \pmod{p}$$ is a mean to explore the hidden internal structure of the number.
If the number is prime, then the "Digraph under the LLT modulo this prime p" has specific features: tree(s) and cycles of specific organizations. I've checked with numbers of other forms (like k*3^n+/-1 or k*5^n+/-1, if I remember well). If the number is NOT prime, then the Digraph is very different, still with trees and cycles, but with an organization which is based on the divisors of the numbers, and which does not obey to all the rules that a prime of the same form obey to. The problem is to find which rules (the seed where to start ! and the length of 1 or more cycles to cover) are fundamental to the primes of this form. That's quite easy for Mersenne, Wagstaff and Fermat numbers, which are very pure/simple numbers. It would be more difficult for other numbers, but we know very few about the properties of these Cycles. More to discover. A full domain of research.
Start by extending our knowledge about the Digraph under x^2-2 for these Mersenne, Wagstaff and Fermat numbers !

Regards,

Tony

 

[dodo]

Sorry, I don't understand. Can you elaborate ?

I think you got the idea already. If S{q-1} = S0 (mod Mq), then the sequence will repeat every q-1 steps, but you don't intend to speak about primality for every further repetition of some Sn = S0. No clarification needed, we're already talking about the same thing.

 

[T.Rex]

New version of the conjectures !

Hello,
I've produced a http://tony.reix.free.fr/Mersenne/SummaryOfThe3Conjectures.pdf" (thanks to "Dodo"), with more explanations, with new seeds, and with new PARI/gp code, and with information about the status of proof of the sufficiency, and who did what.
Hope it helps !
Only the necessity is now required !
(note that Lucas never provided a proof for the necessity of his theorems ! Then Lehmer came.)
Tony