## Williams-Lenstra Cyclotomy

Expand Messages
• Some time ago, in another [*] place, I commented on the Williams-Lenstra proofs for the following primes: V(57724) 12063 Lucas primitive part
Message 1 of 6 , Sep 2, 2001
Some time ago, in another [*] place, I commented on
the Williams-Lenstra proofs for the following primes:

V(57724) 12063 Lucas primitive part
U(35999) 7523 Fibonacci number
U(30757) 6428 Fibonacci number
W(13339) 5106 NSW prime

Bouk de Water and I now add another 4 cyclotomic proofs:

lucasU(287,-1,3079) 7566 Generalized Lucas number
primV( 4, 1,7487) 4282 Generalized Lucas primitive part
primV( 4, 1,7451) 4261 Generalized Lucas primitive part
lucasU( 9,-1,3671) 3671 Generalized Lucas number

The common feature of these 8 was that neither
the Brillhart-Lehmer-Selfridge (BLS) nor
the Konyagin-Pomerance (KP) method sufficed.

Let F1 be the fraction of the digits of N-1
that is completely factorized into proven primes.
Let F2 be the corresponding fraction for N+1.
Finally, let Fmax=max(F1,F2) and Fmin=min(F1,F2).

Then BLS, as implemented by OpenPFGW, requires
3*Fmax + Fmin > 1
for completion of a proof.

My extension of the KP method improves this to
(10/3)*Fmax + Fmin > 1
which I have implemented in Pari.

However there are situations in which the KP
(and, a fortiori, the BLS) method is insufficient,
while the Williams-Lenstra (WL) condition
3*Fmax + 3*Fmin > 1
is satisfied. In such a case it is necessary
to test the Lenstra residue classes. For
this I have written dedicated Pari [*] code.

To give an idea of how much work was done by
the Elliptic Curve Method (ECM) and the
(PPSIQS) method, I give a table of Cmin, F1, F2,
KPneed, where Cmin is the number of decimal digits
in the smallest remaining composite factor of N^2-1,
and KPneed is the number of digits still needed for KP.

N Cmin F1 F2 KPneed
lucasU(287,-1,3079) 96 0.1912 0.1490 485
primV( 4, 1,7487) 172 0.2621 0.0818 57
primV( 4, 1,7451) 108 0.2275 0.1254 149
lucasU( 9,-1,3671) 93 0.2413 0.1074 94

More than 10 CPU-days of ECM and PPSIQS were expended to
attain these substantial factorizations, after systematic
exploitation of cyclotomic and Aurifeuillian theory.
a substantial amount of unsuccessful ECM effort.

Needless to say, all prime factors were
proven by Pfgw/Titanix/Primo, and all BLS
tests were passed, upon running Pfgw with
the resultant helper files.

At the end, only minutes of Pari work was
needed to test the Lenstra residue classes.

Clearly one should cease factorization when
less than an hour of WL work becomes sufficient,
yet KP or BLS theory is very likely to require
several days of further ECM or PPSIQS effort.

[*] http://groups.yahoo.com/group/primeform/message/2268
• PS: There was a typo in the first table, here corrected: lucasU(287,-1,3079) 7566 Generalized Lucas number primV( 4, 1,7487) 4282 Generalized Lucas
Message 2 of 6 , Sep 2, 2001
PS: There was a typo in the first table, here corrected:

lucasU(287,-1,3079) 7566 Generalized Lucas number
primV( 4, 1,7487) 4282 Generalized Lucas primitive part
primV( 4, 1,7451) 4261 Generalized Lucas primitive part
lucasU( 9,-1,3671) 3522 Generalized Lucas number

Apologies!

David
• ... Did someone mention 4,1 ?? Here s a few rules I worked out earlier! P=4, Q=1 U(n)^2=U(n-1)U(n+1) U(2n+1)-1=U(n)V(n+1) U(2n+1)+1=V(n)U(n+1)
Message 3 of 6 , Sep 2, 2001
> PS: There was a typo in the first table, here corrected:
>
> lucasU(287,-1,3079) 7566 Generalized Lucas number
> primV( 4, 1,7487) 4282 Generalized Lucas primitive part
> primV( 4, 1,7451) 4261 Generalized Lucas primitive part
> lucasU( 9,-1,3671) 3522 Generalized Lucas number
>
> Apologies!
>
> David

Did someone mention 4,1 ??

Here's a few rules I worked out earlier!

P=4, Q=1

U(n)^2=U(n-1)U(n+1)
U(2n+1)-1=U(n)V(n+1)
U(2n+1)+1=V(n)U(n+1)

V(2n+1)/4-1=3*U(n)U(n+1)
V(2n+1)/4+1=V(n)V(n+1)/4

V(2n)/2-1=6*U(n)^2
V(2n)/2+1=V(n)^2
------
2

U(2n+1)=[U(n+1)+U(n)]*[U(n+1)-U(n)]
15*U(2n+1)=[U(n+2)+U(n-1)]*[U(n+2)-U(n-1)]
U(2n)=U(n)V(n)=[U(n+1)+U(n-1)]*[U(n+1]-U(n-1)]
U(n+1)U(n-1)=[U(n)+1]*[U(n)-1]

12*U(2n+1)=[V(n+1)+V(n)]*[V(n+1)-V(n)]
48*U(2n)=[V(n+1)+V(n-1)]*[V(n+1]-V(n-1)]
180*U(2n+1)=[V(n+2)+V(n-1)]*[V(n+2)-V(n-1)]

Some of these last 7 might have analogies for the NSWs
(P=2, Q=-1), I'll check.
Its also PRP for lucasV(4,1,18869)
Following for n prime: (n>2)
For P=3, lucasU(3,-1,n) primes
lucasV(3,-1,n)/3 primes
lucasU(3,1,n) no primes
lucasV(3,1,n)/3 primes
P=4
lucasU(4,-1,n) no primes (only n=3)
lucasV(4,-1,n)/4 no primes (only n=3)
lucasU(4,1,n) no primes
lucasV(4,1,n)/4 primes

P=5
lucasU(5,-1,n) primes
lucasV(5,-1,n)/5 primes
lucasU(5,1,n) no primes
lucasV(5,1,n)/5 primes

I'd really like to be able to generalise some of these.

Andrew Walker
• ... Oops, lucasV(4,1,18869)/4 is PRP These also have factors of the form 12n+1 which is nice! Andrew
Message 4 of 6 , Sep 2, 2001

> Some of these last 7 might have analogies for the NSWs
> (P=2, Q=-1), I'll check.
> Its also PRP for lucasV(4,1,18869)

Oops, lucasV(4,1,18869)/4 is PRP

These also have factors of the form 12n+1 which is nice!

Andrew
• ... Yes, indeed! Bouk and I have already mined it deep. Recall we had discrim=12 in our sights a good way back:
Message 5 of 6 , Sep 2, 2001

> Did someone mention 4,1 ??

Yes, indeed! Bouk and I have already mined it deep.
Recall we had discrim=12 in our sights a good way back:

http://groups.yahoo.com/group/primeform/message/2214

The key points are these:

1) primU(4,1,n) is NOT truly primitive, for any odd n;
use 2+sqrt(3)=(sqrt(1/2)+sqrt(3/2))^2 to
further factorize it

2) primV(4,1,n) admits Aurifeuille for n=3 mod 6

3) N=primV(4,1,2^a*p) with prime p has N^2-1
factorizable by cyclotomy + (1) + (2)

4) N=primV(4,1,2^a*3^b*p) has N-1 factorizable
(but not N+1)

5) The following are PrPs

primV(4,1,1162)
primV(4,1,1312)
primV(4,1,1463)
primV(4,1,1554)
primV(4,1,2136)
primV(4,1,2315)
primV(4,1,2605)
primV(4,1,2722)
primV(4,1,3013)
primV(4,1,3049)
primV(4,1,3488)
primV(4,1,3940)
primV(4,1,4202)
primV(4,1,4553)
primV(4,1,4622)
primV(4,1,5020)
primV(4,1,6376)
primV(4,1,6558)
primV(4,1,6700)
primV(4,1,7098)
primV(4,1,7451)
primV(4,1,7487)
primV(4,1,8412)
primV(4,1,9148)
primV(4,1,9205)
primV(4,1,10566)
primV(4,1,10882)
primV(4,1,11465)
primV(4,1,11596)
primV(4,1,12124)
primV(4,1,14378)
primV(4,1,14592)
primV(4,1,16956)
primV(4,1,17664)
primV(4,1,18869)
primV(4,1,19817)
primV(4,1,20755)
primV(4,1,21380)

6) Of these, Bouk and I have proven 13 out
of the 16 titans with n=2^a*3^b*prime:

n digs Cmin F1 F2 status
2722 1556 106 0.3743 0.4295 BLS
3049 1744 324 0.6172 0.3344 BLS
3488 1977 189 0.6629 0.2177 BLS
4622 2643 112 0.6183 0.3069 BLS
6376 3643 147 0.3263 0.0734 BLS
7451 4261 108 0.2275 0.1254 WL
7487 4282 172 0.2621 0.0818 WL
9148 5230 168 0.3787 0.1211 BLS
10882 6223 131 0.3056 0.0466 KP

18869 10792 301 0.1063 0.1039 PrP: not yet WL

6558 2499 119 0.3691 BLS
8412 3203 223 0.6049 BLS
10566 4022 150 0.3849 BLS
16956 6425 121 0.3199 KP

14592 5272 143 0.2750 PrP: not yet KP
17664 6443 143 0.2441 PrP: not yet KP

7) Conclusion: This vein is more fertile than NSW;
almost as good proving territory as Luc/Fib!

David
• ... To understand those 4 blanks, simply factorize s=(p+sqrt(d))/2 with d=p^2-4*q p q d s 3 1 5 (3+sqrt(5))/2 = r^2 4 -1
Message 6 of 6 , Sep 3, 2001
Andrew Walker wrote:

> lucasU(3,1,n) no primes
> lucasV(4,-1,n)/4 no primes (only n=3)
> lucasU(4,1,n) no primes
> lucasU(5,1,n) no primes

To understand those 4 blanks,
simply factorize s=(p+sqrt(d))/2
with d=p^2-4*q

p q d s
3 1 5 (3+sqrt(5))/2 = r^2
4 -1 20 2+sqrt(5) = r^3
4 1 12 2+sqrt(3) = (1+sqrt(3))^2/2
5 1 21 (5+sqrt(21))/2 = (sqrt(3)+sqrt(7))^2/2

where r=(1+sqrt(5))/2. So, for example,

lucasU(3, 1,n)=lucasU(1,-1,2*n)
lucasV(4,-1,n)=lucasV(1,-1,3*n)

are clearly composite, for sufficiently large n.

> I'd really like to be able to generalise some of these.

Here's a pretty powerful generalization to chew on:

lucasU(lucasV(p,q,k),q^k,n) = lucasU(p,q,k*n)/lucasU(p,q,k)

So far you are only scratching the surface of this,
with q=+/-1.

Those guys Lucas (in 1878) and Carmichael (in 1913)
were pretty impressive!

David
Your message has been successfully submitted and would be delivered to recipients shortly.