- May 1, 2009Unique 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,481)+lucasU(1142,1,480))/

(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,481)+lucasU(2128,1,480))/

(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,481)-lucasU(3196,1,480))/

(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,481)-lucasU(4404,1,480))/

(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

http://primes.utm.edu/primes/page.php?id=76675

David Broadhurst, per proxy SSSR,

Society for Suppression of Square Roots,

May Day, 2009 - << Previous post in topic Next post in topic >>