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

20197Unique Lehmer primes

Expand Messages
  • David Broadhurst
    May 1, 2009
    • 0 Attachment
      Unique Lehmer primes

      1) Definition of a unique Lehmer prime:

      If, for a given integer P > 2 and choice of sign, the
      Lehmer sequence U(P,1,n+1) +/- U(P,1,n) with n > 0 contains
      precisely one prime N, then I shall say that N is a
      "unique" Lehmer prime, of type U or V, with parameter P
      and index 2*m + 1, where m is the value of n that yields N.

      2) SSSR construction of unique Lehmer primes:

      With p > 2 and a prime index 2*m + 1, let
      P = V(p,1,2*m+1) and N = U(P,1,m+1) +/- U(P,1,m).
      If N is prime, then N is a unique Lehmer prime
      with parameter P and index 2*m + 1, as I now prove.

      3) Proof of construction:

      Denote U(p,1,n+1) +/- U(p,1,n) by L(p,n). We know from
      C. L. Stewart, "On divisors of Fermat, Fibonacci, Lucas and
      Lehmer numbers", Proc. London Math. Soc., 35 (1977), 425-447,
      that L(p,n) is composite if its index 2*n + 1 is composite
      and, most importantly, we know that L(p,n) is coprime to
      L(p,m) when the indices 2*n + 1 and 2*m + 1 are coprime.

      Let P = V(p,1,2*m+1), with 2*m + 1 prime, and
      let M = V(p,1,2*n+1), for any n > 0. I show that the identity
      L(p,m)*L(P,n) = L(p,n)*L(M,m) implies that L(P,n) cannot be
      prime unless n = m. Suppose, on the contrary, that L(P,n) is
      prime with n different from m. Then 2*n + 1 is prime and
      hence coprime to the different prime 2*m + 1. Thus
      gcd(L(p,n),L(p,m)) = 1, L(p,m)|L(M,m) and L(p,n)|L(P,n).
      But that is impossible, since L(P,n) was supposed to be prime
      and is not equal to L(p,n). Hence, when N = L(P,m) is prime,
      it is indeed a unique Lehmer prime, as claimed above.

      Note to rash claimants: this crucially depends on Stewart's
      result, without which we could not yet conclude that N is
      unique. For example, the partial factorization of 91*137
      as 13*959 assuredly does not prove that 137 is composite.

      4) SSSR conjecture:

      I conjecture that the SSSR construction generates
      all unique Lehmer primes.

      5) Comments:

      To disprove the SSSR conjecture one would need to show that
      there exists an integer P, not of the form V(p,1,2*m+1),
      and that L(P,n) is prime precisely once for all n > 0.

      That seems to be rather hard to do, since the only other
      situation where I know of explicit factorization is
      Mike Oakes' case, with P = 4*(k^2 - 1)^2 - 2 and k > 1,
      which we may reduce to p = 2*(k^2 - 1) obtaining
      U(P,1,n+1) - U(P,1,n) = A(2*n+1,k)*A(2*n+1,-k), where
      A(2*n+1,k) = (k*U(P,1,n+1)-k*U(P,1,n)-(-1)^(n*(n+1)/2))/(k-1)
      with the vital inclusion of a Kronecker symbol on the right
      hand side, to ensure that A(2*n+1,k) is an integer.
      In this case, the Lehmer sequence contains no prime,
      since neither A(2*n+1,k) nor A(2*n+1,-k) is a unit for n > 0.

      Note to rash claimants: this crucially depends on the
      Kronecker symbol, without which we could not yet conclude
      that the target is composite, although in this case that may
      be remedied, as I have shown, by careful use of inequalities.

      6) Statistics with P < 10^20:

      With parameters P < 10^20, the SSSR construction generates
      323670 probably unique Lehmer primes of type U and
      323260 of type V, if one demands that neither of P +/- 2
      is a square, so as to avoid Lucas primitive parts.

      7) Titanic unique Lehmer primes:

      Unique Lehmer primes from the SSSR construction with
      p < 5*(2*m+1)^2 are archivable at the Prime Pages, with
      a current entrance barrier of 8478 digits, under the
      description "Lehmer primitive part", since that it precisely
      what they are: L(P,m) = L(p,s)/L(p,m) with s = 2*m*(m+1)
      giving a composite index 2*s + 1 = (2*m + 1)^2 whose sole
      prime divisor is 2*m + 1, making the Moebius transformation
      rather simple. They are unique Lehmer primes in a sequence
      that might vastly fail to satisfy P < 5*(2*m + 1) precisely
      because they are well fitted to satisfy p < 5*(2*m + 1)^2,
      in their roles as primitive parts of simpler Lehmer numbers.
      Moreover, their presentations as Lehmer primitive parts:
      ( U(p,1,s+1) +/- U(p,1,s) )/( U(p,1,m+1) +/- U(p,1,m) )
      is easily parsable by both PFGW and the Prime Pages.

      To achieve an archivable proof without using ECPP on the
      main target, one needs favourable cyclotomy, some ECM
      factoring, APR-CL or ECPP on the helpers, and good luck.

      The index 31 seemed a good place for a proof of principle,
      since 31^2 - 1 is 5-smooth. Observing Chris Caldwell's
      bible-belt limit p < 5*31^2, I found 26 probably unique
      Lehmer primes with between 1422 and 1695 decimal digits.
      Choosing 4 of these, at random, I quickly found BLS proofs:

      Calling N+1 BLS with factored part 29.39%
      and helper 23.99% (112.22% proof)
      (lucasU(1142,1,16)+lucasU(1142,1,15)) is prime!

      Calling N+1 BLS with factored part 31.61%
      and helper 25.93% (120.80% proof)
      (lucasU(2128,1,16)+lucasU(2128,1,15)) is prime!

      Calling N-1 BLS with factored part 38.39%
      and helper 10.88% (126.05% proof)
      (lucasU(3196,1,16)-lucasU(3196,1,15)) is prime!

      Calling N-1 BLS with factored part 39.02%
      and helper 5.33% (122.41% proof)
      (lucasU(4404,1,16)-lucasU(4404,1,15)) is prime!

      at 1422, 1548, 1630 and 1695 decimal digits.

      It is a long way from 1695 digits to Bouk de Water's
      threshold of 8478 digits, but my impression is that
      there might be enough unique PRPs to strike lucky.
      However, the cyclotomy would be much less favourable
      than for non-unique indices such as 3375 = 15^3, as in

      David Broadhurst, per proxy SSSR,
      Society for Suppression of Square Roots,
      May Day, 2009
    • Show all 69 messages in this topic