PRIMALITY PROOF for Wagstaff numbers!
 

At last I have found the proof! Needed some lateral thinking.

This is as per my [URL="http://http://www.mersenneforum.org/showpost.php?p=144241&postcount=41"]conjecture 4 [/URL] in a paralel thread but now hopefully we can upgrade to theorem once checked. I am inviting comment to the attached proof.


[tex]\blue \text{Let } q \text{ be a prime integer } > \ 3 \text{ , } W_q = \frac{1}{3}(2^q+1) \text{.} [/tex]

[tex]\blue W_q \text{ is prime } \Longleftrightarrow \ S_{q} \equiv S_2 \ \pmod{W_q} \text{ , where: } S_0=6 \text{ , and } \ S_{i+1}=S_i^2-2 \ \pmod{W_q} \ .[/tex]

best regards
Anton Vrba

I noticed a small typo, page 3 comment 2
(a+i)^(2k+1)=(a-i) (mod 2k+1) and not (mod (a+i)) as in the paper.

so please correct.

Another typo, page 3, comment 1: "The reasoning presented
may not be [b]k[/b]new and already documented somewhere and references
are kindly requested."

I guess this should read: "...may not be [b]new[/b]..."

Edit: Your link to conjecture 4 does not work - there is one "http" too much.

Waowwww !!!!
 

Hello Anton !
Congratulations to your work !!!

I have juste read the proof and I need some time to chew it... However, I see that Phil Carmody already has a comment about a part that seems wrong to him.
I hope that any unclear parts will be cleared asap, and that other people will approve your proof (Hey Bob ! Your comments ?) so that I can send my 100 Euro bank-note to you !

Some preliminary comments:
- In (2) and (4) and (6), it seems to me that you used q instead of p.
- In many places, you use = instead of \equiv
- About (9) { S(p-1)=-S(1) (Mod Wp) } , why ? It has been a question for the LLT when the "Penultimate Lucas-Lehmer step" is - or +. No proof. But I remember that I read that, when using LLT in another case, it is always + (can't remember more details...). What is your proof ?
- I do not see in the theorem the extra conditions saying that S2 must be reached at step p and never before step p. Is it no more useful ? With this p-2 iteration, is it impossible for a composite to reach S2 at step i<p ? Is it what your comment 2 is saying ?
- I'm surprised to see that there is a (p-2) cycle... but that works ! I've checked with different values. I should look again at these damned cycles for Wagstaff primes !
- about your comments dealing with the cost of operations, we really don't care about one step less, same about some small numbers at beginning of iterations. That's peanuts when you have millions of iterations to do with FFT.
- what's inefficient in your test for Wagstaff numbers is your use of (mod Wp). There are technics for that (see LLR test) but they have a cost at each iteration, I think. Using S^2-2 (mod Np) with N=1+2^p enables to use faster FFT with modulo, I think, meaning the Prime95 code can be used with nearly no change. Hey ! you other people experts in this (Crandall, Woltman, Penné, & others), do you agree ?
- and you say not a word about my idea to use cycles of a Digraph, nor you talk about Shallit&Vasiga work (they gave proofs about the cycles). Once checked, the proof is yours, but I'm not sure the idea is entirely yours. Like the LLT is named Lucas-Lehmer-Test, since Lehmer provided a complete proof though Lucas did not but he had the idea, we have to clarify who had the idea to use Cycles and thus to test Sp=S0 (or Si, since you can iterate in a tail before reaching a cycle). You had the idea to use cycles for Wagstaff numbers, for sure. But, as far as I know, based on the Mersenne forum, I was the first to propose to use Cycles of a Digraph as a primality test. Did you write on a forum before me ? I need this point to be clarified because I would like that all the time I've spent on these damned tree and cycles of the Digraph under x^2-2 or x^2 modulo a prime before my wife died is not lost and that my children can see that all the time I didn't spend with her was useful in some way (Maths never die).

Clarifying who had innovative ideas is one thing. Being able to build a proof is another thing. I'm VERY HAPPY you have made a big step !! Now, wait for other mathematicians to check and approve the proof !

What is important (once proof confirmed) is that now not only Mersenne numbers (and also the rare Fermats) can be verified proof or not in a very fast way. Other numbers are k*2^n-1 numbers, with LLR, but it is a little bit smaller. Maybe George will provide such a test for Wagstaffs ? like Jean already did.

Again, congratulations !!

Tony

AND, after a rest, I noticed a wild and false conclusion regarding the order of the group, this has been corrected as well as the equality (19) regarding the group order.

I also added the alternate cycle S_0 = -3/2

Tony thanks for your comments I shall work those in and address your queries separately.
I started of with q but then changewd to p so I must have skipped some. Editing in LaTex is not my strength and a complete new experience.

[QUOTE=AntonVrba;144516]At last I have found the proof! Needed some lateral thinking.

This is as per my [URL="http://http://www.mersenneforum.org/showpost.php?p=144241&postcount=41"]conjecture 4 [/URL] in a paralel thread but now hopefully we can upgrade to theorem once checked. I am inviting comment to the attached proof.
[/QUOTE]

Your proof is wrong. You can not do that step from (15) to (16), because if
a*c==b*c mod d, then you can't say that a==b mod d. You can do it only in that case, if you could prove that gcd(c,d)=1 is true in your ring (so if gcd(delta,W(p))=1 is true).

[quote=AntonVrba;144516][tex]\blue W_q \text{ is prime } \Longleftrightarrow \ S_{q} \equiv S_2 \ \pmod{W_q} \text{ , where: } S_0=6 \text{ , and } \ S_{i+1}=S_i^2-2 \ \pmod{W_q} \ .[/tex][/quote]
Is the [tex]\pmod{W_q}[/tex] in [tex]\blue \ S_{q} \equiv S_2 \ \pmod{W_q}[/tex] necessary? It seems that since both [tex]S_{q}[/tex] and [tex]S_2[/tex] are already [tex]\pmod{W_q}[/tex] it is completely unnecessary.

[QUOTE=T.Rex;144536]
Some preliminary comments:
- About (9) { S(p-1)=-S(1) (Mod Wp) } , why ? It has been a question for the LLT when the "Penultimate Lucas-Lehmer step" is - or +. No proof. But I remember that I read that, when using LLT in another case, it is always + (can't remember more details...). What is your proof ?
[/quote] just remember s^2-2 = (-s)^2-2


[QUOTE=T.Rex;144536]
- I do not see in the theorem the extra conditions saying that S2 must be reached at step p and never before step p. Is it no more useful ? With this p-2 iteration, is it impossible for a composite to reach S2 at step i<p ? Is it what your comment 2 is saying ?
[/quote] No, comment two says that S_0 and S_1 will never repeat in the iteration. Further, I believe that S_0=6,-6 and S_0=-3/2 are the only three numbers to guarantee cycles of p-2 and p-1 respectively and that all elemets of S_0 to S_(p-1) are unique for all prime W_p. I do not know what to call these numbers any suggestion.

[QUOTE=T.Rex;144536]
- I'm surprised to see that there is a (p-2) cycle... but that works !
[/quote] You have not studied the digraphs as you claim you have.


[QUOTE=T.Rex;144536]
- what's inefficient in your test for Wagstaff numbers is your use of (mod Wp). There are technics for that (see LLR test) but they have a cost at each iteration, I think. Using S^2-2 (mod Np) with N=1+2^p enables to use faster FFT with modulo, I think, meaning the Prime95 code can be used with nearly no change. Hey ! you other people experts in this (Crandall, Woltman, Penné, & others), do you agree ?
[/quote] I am sure that this is correct but I cannot prove it for now - somebody else can. The proof of sufficiency is not valid for 3W_p but the proof of necessity would be valid.


[QUOTE=T.Rex;144536]
- and you say not a word about my idea to use cycles of a Digraph, nor you talk about Shallit&Vasiga work (they gave proofs about the cycles).
[/quote] Please note I have not named the test but I am presenting the proof. I have not made use of any work of Shallit&Vasiga and thus no need to mention. We are not proofing the form of the diagraph, Shallit&Vasiga have done that, but the proof is making a statement regarding the possible divisors of W_p.

The Lucas-Lehmer test proves that 2^p-1 has no non-trivial factors smaller than 2^(p-1). A consequence of this is that the number is prime.

What this test does assert, is that there are no possible divisors smaller than sqrt(W_p), and as a consequence, W_p is prime - and thus it is very similar to the Lucas-Lehmer test.

[QUOTE=T.Rex;144536]
Again, congratulations !!

Tony[/QUOTE]
Thanks we now need to wait for the experts.

[QUOTE=Mini-Geek;144539]Is the [tex]\pmod{W_q}[/tex] in [tex]\blue \ S_{q} \equiv S_2 \ \pmod{W_q}[/tex] necessary? It seems that since both [tex]S_{q}[/tex] and [tex]S_2[/tex] are already [tex]\pmod{W_q}[/tex] it is completely unnecessary.[/QUOTE]

Thanks for the correction

[QUOTE=R. Gerbicz;144538]Your proof is wrong. You can not do that step from (15) to (16), because if
a*c==b*c mod d, then you can't say that a==b mod d. You can do it only in that case, if you could prove that gcd(c,d)=1 is true in your ring (so if gcd(delta,W(p))=1 is true).[/QUOTE]

My old number theory book from 1962 says:
(1) x = y(mod m)
and say that x is congruent to y modulo m. The quantity m is called the
modulus, and all numbers congruent (or equivalent) to x (mod m) are said
to constitute a congruence (or equivalence) class. Congruence classes are
preserved under the rational integral operations, addition, subtraction, and
multiplication.

Mathematica calculates that Mod[7,3x43]=7 and Mod[7*3,3*43]=21 so is it wrong? I think you can withdraw your statement.

For example:
14==21 mod 7 is true, but after dividing
2==3 mod 7 isn't true. And you've done this.