PRIMALITY PROOF for Wagstaff numbers! - Page 2

AntonVrba · 2008-10-05, 13:50

Another update of the my presentation, noticed further mistakes all typos or forgot to remove earlier mistakes throughout the document.

Possibly administrator can change the the files in the root thread and delete the files in 5 and here.

AntonVrba · 2008-10-05, 14:49

Quote:

Originally Posted by R. Gerbicz

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

Ok, I misunderstood your earlier post, sorry.

Actually, I did computational checks all along while developing the theory and found delta = x sqrt(2) mod W_p, now remains to prove x != 0.

Lets take that to be true what about the rest?

reagrds

T.Rex · 2008-10-05, 15:16

Quote:

Originally Posted by R. Gerbicz

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

You take 7 for the modulo, and 0 == 0.
Since we do not know yet if Wp is prime, let's take a composite as another example:
2*7=14 == 2 (mod 6)
2*4= 8 == 2 (mod 6)
But: 2*7 + 2*4 = 2*(7+4) == 2+2 == 4 == 2*(2) (mod 6) does not entail: 7+4 == 2 (mod 6) dividing by 2. Because gcd(2,6) != 1.

In our case: $\delta = (b+12)sqrt{2}$ . delta does not divide Wp, for sure. But what do we know about b+12 ? ( $\omega^{2^{p-1}} = a + b sqrt{2}$ ).

Using $\ \pmod{N_p = 2^p+1}$ could help, since $2^{p-1} = (N_p-1)/2$ .

And maybe the Legendre symbol could help there: $\omega^{2^{p-1}} \equiv \omega^{(legendre(2,N_p)} \pmod{N_p}$ ?

Also, when moving from (17) to (18), there are 2 possibilities: $i \overline{\omega} \text{ and } - i \overline{\omega}$ ). Why choosing the first one ?

In the line before (19), it should be: ORDg(omega) = ..... = 2^p

T.

T.Rex · 2008-10-05, 15:57

Quote:

Originally Posted by AntonVrba

just remember s^2-2 = (-s)^2-2

?? Let say $S_{p-1} \equiv S_1 \ \pmod{W_p}$ . Then we have: $S_{p} =S_{p-1}^2-2 \equiv S_1^2-2 = S_2 \ \pmod{W_p}$ .
So why choosing -S_1 in (9) ?

Quote:

Comment to say that S_0 and S_1 will never repeat in the iteration.

In which part are you talking about the proof for that point ?

Quote:

You have not studied the digraphs as you claim you have.

Not those of Wagstaff or 2^q+1 numbers yes. But those of Mersennes and Fermats, yes.

Quote:

Please note I have not named the test but I am presenting the proof.

yes.

Quote:

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.

The initial work from Lucas and the proof by Ribenboim and others made use of "Lucas sequences" and was based on a "law of apparition". Modern proofs are simpler, but they lack the basic ideas, I think.

The LLT for Mersenne makes use of a very small part of the properties of a Digraph under x^2-2 modulo a prime. Proofs can use any way for proving the LLT. But I think that they are too "technical" and that they hide underlying facts. Proving the LLT for Mersenne with modern means could not have lead to use Cycles of the Digraph (and they CAN be used for building a proof, for sure...).

The main question about the idea of conjectures 2 and 4 is:
Would you have had the idea of building this conjecture of "primality test for Wagstaff numbers" if:
1) Lucas had not the idea of using the properties of the "lucas sequence" and then simplifying his first impractical sequence in the S^2-2 iteration and testing that the q-2 iteration leads to 0 ? and
2) I studied the Digraph under x^2-2 modulo a Mersenne and imagined to use cycles rather than the tree (before I read Shanks' book or Shallit&Vasiga paper), encouraged by the proofs from Shallit&Vasiga ?

Note that Lifchitz built a conjecture for Wagstaffs based on cycles without knowing that they were using a cycle of the Digraph under x^2 modulo a 2^q+1 . So they were not able to generalize and try to find other (more appropriate for a full proof) seeds, like you did.

We are fighting together about nuts... I have to work my songs and learn a new poem by Aragon...

Anyway, I wish you to succeed in answering the comments ! so that your proof becomes accepted and valid !
My goal is to see a proof that cycles of the Digraph can be used as the basis for primality testing the same way we can use a branch of the tree for Mersenne and Fermat. If you succeed in proving the Conjecture for Wagstaff numbers, then other people will be encouraged and look at a proof for Mersennes and Fermats, and then look at less simpler numbers.
So, go on !!

Tony

T.Rex · 2008-10-05, 15:59

Quote:

Originally Posted by Mini-Geek

It seems that since both $S_{q}$ and $S_2$ are already $\pmod{W_q}$ it is completely unnecessary.

Yes. Correct. But it is simply a detail.
T.

AntonVrba · 2008-10-05, 16:29

Quote:

Originally Posted by AntonVrba

Actually, I did computational checks all along while developing the theory and found delta = x sqrt(2) mod W_p, now remains to prove x != 0.

And here is the proof by a bit of numeric expansion:

$S_0 = (3+2\sqrt2 )+(w-2\sqrt2)$

$S_1 = (17+12\sqrt2)+(17-12\sqrt2)$

$S_2 = (577+408\sqrt2)+(577-408\sqrt2)$

Now we have S_1 = -S_(p-1) and the spliting of the
$\omega^{2^{p-1}}+{\bar\omega}^{2^{p-1}}<br /> +{\omega}^{2}+{\bar\omega}^{2}\equiv 0\;\pmod{W_p}$
into
$\omega^{2^{(p-1)}} +{\omega}^{2}\equiv \delta\;\pmod{W_p}$
and
$\bar\omega^{2^{(p-1)}} +{\bar\omega}^{2}\equiv -\delta\;\pmod{W_p}$
and lets asume $\delta=0$ the case that R. Gerbicz pointed out that the theorem is possibly void. if delta zero then S_(P-1) has the form

$S_{(p-1)}={(\frac{x W_p-17}{2} +(z W_p -12)\sqrt2) + (\frac{x W_p-17}{2} -(z W_p -12)\sqrt2)$

thus
$S_{p}={(\frac{x W_p-17}{2} +(z W_p -12)\sqrt2)^2 + (\frac{x W_p-17}{2} -(z W_p -12)\sqrt2)^2$
and this evaluates to
$S_p \equiv (\frac{1441}{4}+104\sqrt2)+(\frac{1441}{4}-104\sqrt2) \pmod W_p$

but $S_2 = S_p$ therefor the initial assumption is wrong as the $\sqrt2\text{coefficent}$ can never be zero, thus my proof holds.

I will ammend the paper accordingly - thankyou Robert for pointing this out and once again appologies for my earlier mis understanding and cheaky reply.

AntonVrba · 2008-10-05, 16:58

Quote:

Originally Posted by T.Rex

?? Let say $S_{p-1} \equiv S_1 \ \pmod{W_p}$ . Then we have: $S_{p} =S_{p-1}^2-2 \equiv S_1^2-2 = S_2 \ \pmod{W_p}$ .
So why choosing -S_1 in (9) ?

Tony

Look at the attached digraph of 43 = (1/3)(2^7+1)
and trace S_0=6,34,36...9=(43-34), I hope this explains it to you
as you can see 6, 37 and 34 can never repeat in the cycle.
and similarely for S0=-3/2 = 20

My proof always start working from the outside and including the what Shallit terms the tail or inverted trees.

I believe these numbers have to be included in any primality test that uses the iteration s->s^2-2. The Lucas Lehmer test works as it has cycle length 0 as there are no odd factors of M_p+1.

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

Quote:

Originally Posted by AntonVrba

Look at the attached digraph of 43 = (1/3)(2^7+1)
and trace S_0=6,34,36...9=(43-34), I hope this explains it to you
as you can see 6, 37 and 34 can never repeat in the cycle.
and similarely for S0=-3/2 = 20

Yes, I can see ! Sure ! But this is the Digraph of a prime Wagstaff !
So, are you saying that you are using the property of a prime Wagstaff to prove that a Wagstaff we know nothing about is prime ?
And a drawing of an example p=7 does not make a proof for all p...
Drawing a Digraph is a way to see nice properties and to imagine how to prove them and then use them.
So, I still think that some proof is missing there around (9). Maybe assuming Wp is composite would lead to some proof of contradiction of this point...
Or am I wrong ?
T.

AntonVrba · 2008-10-06, 03:28

Quote:

Originally Posted by T.Rex

So, I still think that some proof is missing there around (9). Maybe assuming Wp is composite would lead to some proof of contradiction of this point...
Or am I wrong ?
T.

Ok, I finally see your point. What I thought was obvious is not so and the condition of the primality test need to be expanded to either S_0 and S_1 unique or S_1==-S_q_1. (which I initially included in my original handwritten notes but then discarded when type setting - that is the reason why I had written (9) in the first place and allowed me to develop this proof - this whole proof took about 6 hours from concept to first posting and here in Dubai I have no sparring partners to check so I am grateful for your and others constructing and relentless arguments!)

$\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{ AND } S_1 \equiv -S_{q-1}\pmod{W_q} \text{ , where: } S_0=6 \text{ , and } \ S_{i+1}=S_i^2-2 \ \pmod{W_q} \ .$

ixfd64 · 2008-10-06, 08:49

Good luck on your proof. You might become famous if it turns out to be correct!

T.Rex · 2008-10-06, 09:03

Quote:

Originally Posted by AntonVrba

Ok, I finally see your point. ...this whole proof took about 6 hours from concept to first posting and here in Dubai I have no sparring partners to check so I am grateful for your and others constructing and relentless arguments!) ...

Seems better now !
I'll look when back home.

However, did you see the comments of David Broadhurst and Phil Carmody on [openpfgw] mailing list ?

Comments of David Broadhurst:

Quote:

1) As Phil noted, there is horrific garbling of the meaning of "order".

2) The use of "i" for sqrt(-1) is meaningless, since W_p = 3 mod 4.

3) Anton has not yet proven that he did not divide by 0, when "using (12a) and (12b) to cancel the delta".

4) His group of "all the numbers (a+b*sqrt(2)) + (a-b*sqrt(2)) modulo q which are invertible" is not Z_q[sqrt(2)]*.

5) The fundamental unit is u=1+sqrt(2), with norm -1.
So by working only with u^2, with norm +1, Anton misses out on some of the content of the theorems in Section 4.2 of Crandall and Pomerance.

6) We are left with nothing beyond CP Theorem 4.2.8, which requires us to factorize at least 1/3 of the digits of W_p+1, as in PFGW.

And the comments of Phil Carmody:

Quote:

"Consider an element w ... that has no solution w^k == 1" is meaningless.

Skipping everything before it, (19) seems to be obviously false, as the order you've specified does not divide the order of the group.

Sure that their comments are based on more solid Maths than mines...
But I hope you'll be able to answer their comments and fix the proof.

I wish you to succeed !

Bob did not say a word... Maybe he will provide us with another proof soon !

Regards,

Tony

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Prime numbers test primality - with proof written in invisible ink	Godzilla	Miscellaneous Math	40	2018-10-17 00:11
APR-CL as primality proof	f1pokerspeed	FactorDB	14	2014-01-09 21:06
500€ Reward for a proof for the Wagstaff primality test conjecture	Tony Reix	Wagstaff PRP Search	7	2013-10-10 01:23
Proof of Primality Test for Fermat Numbers	princeps	Math	15	2012-04-02 21:49
Wagstaff number primality test?	ixfd64	Math	12	2010-01-05 16:36

2008-10-06, 08:49	#21
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 2×5×239 Posts	Good luck on your proof. You might become famous if it turns out to be correct!