Loading ...
Sorry, an error occurred while loading the content.

Williams-Lenstra Cyclotomy

Expand Messages
  • d.broadhurst@open.ac.uk
    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
    • 0 Attachment
      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
      Double-Large-Prime Self-Initiating Quadratic Sieve
      (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.
      All of the remaining composites had by then received
      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.

      David Broadhurst

      [*] http://groups.yahoo.com/group/primeform/message/2268
    • d.broadhurst@open.ac.uk
      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
      • 0 Attachment
        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
      • ajw01@uow.edu.au
        ... 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
        • 0 Attachment
          --- In primenumbers@y..., d.broadhurst@o... wrote:
          > 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.
          More rules to follow (eventually!)


          Andrew Walker
        • ajw01@uow.edu.au
          ... 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
          • 0 Attachment
            --- In primenumbers@y..., ajw01@u... wrote:

            > 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
          • d.broadhurst@open.ac.uk
            ... 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
            • 0 Attachment
              Andrew Walker asked:

              > 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
            • d.broadhurst@open.ac.uk
              ... 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
              • 0 Attachment
                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.