THERE ARE INFINITELY MANY PERRIN PSEUDOPRIMES

Jon Grantham

December 23, 1997

Abstract. This paper proves the existence of infinitely many Perrin pseudoprimes, as conjectured by Adams and Shanks in 1982. The theorem proven covers a general class of pseudoprimes based on recurrence sequences. The proof uses ingredients of the recent proof that are are infinitely many Carmichael numbers, along with zero-density estimates for Hecke L-functions.

§1 Background

In a 1982 paper [1], Adams and Shanks introduced a pseudoprimality test based on third order recurrence sequences and asked if there are infinitely many composites which pass it — Perrin pseudoprimes, as they have become known.

They answered the question, “Almost certainly yes, but we cannot prove it. Almost certainly, there are infinitely many [Carmichael numbers which are Perrin pseudoprimes], and yet it has never been proved that there are infinitely many Carmichael numbers.”

In 1994, Alford, Granville and Pomerance [2] proved that there are infinitely many Carmichael numbers. A simple modification of that proof shows that there are infinitely many Lucas and Lehmer pseudoprimes. (If the characteristic polynomial is f(x), require all prime divisors p of the Carmichael numbers to have p ≡ 1 mod 4 disc(f)).

In this paper, the techniques of that proof are combined with results about Hecke L-functions to show that there are infinitely many Perrin pseudoprimes.

In fact, a more general result can be proven.

Theorem 1.1. Let f(x) ∈ ℤ[x] be a monic, squarefree polynomial with splitting field K. There are infinitely many Frobenius pseudoprimes with respect to f(x). In fact, there are ≫ N^{c} Carmichael-Frobenius numbers with respect to K which are less than N, for some c = c(K) > 0.

We know from Corollary 3.7 and Theorem 3.10 of [7] that this theorem shows that there are infinitely many Perrin pseudoprimes, if we take f(x) = x^{3} − x − 1. (Note that all pseudoprimes constructed here have S-signatures and the quadratic forms portion of Adams and Shanks’ test does not apply.) From Theorems 3.11 and 3.12 of [7], we also have that there are infinitely many pseudoprimes in the senses of Gurak [8] and Szekeres [16].

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 11Y11 (11N13 11N25).