20197Unique Lehmer primes
- 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.
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
- << Previous post in topic Next post in topic >>