PRIMALITY PROOF for Wagstaff numbers!

AntonVrba · 2008-10-05, 06:33

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

This is as per my conjecture 4 in a paralel thread but now hopefully we can upgrade to theorem once checked. I am inviting comment to the attached proof.

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

$\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} \ .$

best regards
Anton Vrba

AntonVrba · 2008-10-05, 08:02

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.

Andi47 · 2008-10-05, 08:31

Another typo, page 3, comment 1: "The reasoning presented
may not be knew and already documented somewhere and references
are kindly requested."

I guess this should read: "...may not be new..."

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

T.Rex · 2008-10-05, 10:55

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

AntonVrba · 2008-10-05, 11:53

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.

R. Gerbicz · 2008-10-05, 12:02

Quote:

Originally Posted by AntonVrba

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

This is as per my conjecture 4 in a paralel thread but now hopefully we can upgrade to theorem once checked. I am inviting comment to the attached proof.

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

TimSorbet · 2008-10-05, 12:07

Quote:

Originally Posted by AntonVrba

$\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} \ .$

Is the $\pmod{W_q}$ in $\blue \ S_{q} \equiv S_2 \ \pmod{W_q}$ necessary? It seems that since both $S_{q}$ and $S_2$ are already $\pmod{W_q}$ it is completely unnecessary.

AntonVrba · 2008-10-05, 13:00

Quote: