Recently, I’ve been studying the 2003 paper of Chen and Greene “Some Comments on Baillie-PSW Pseudoprimes” published in the Fibonnacci Quarterly in 2003. I wish to make a record of my thinking about this problem, which is occasionally discussed online, for instance in this Mathematics Stack Exchange discssion thread: https://math.stackexchange.com/questions/2902592/isnt-the-estimate-for-the-smallest-counterexample-of-the-bpsw-test-far-too-opti .
The problem studied by Chen and Greene is the construction of sets of primes of moderate size such that, on heuristic grounds, there is a likelihood that some subset of these has a product that is a Baillie-PSW pseudoprime. They define a Baillie-PSW pseudoprime as a number n that is composite such that n= 2 or 3 (mod 5), n is a Fermat base 2 pseudoprime, and F_{n+1} == 0 (mod n). These conditions are notable because there is a $620 bounty offered by Pomerance, Selfridge and Wagstaff for finding such a number.
For an odd, squarefree composite number n to be a Fermat base 2 pseudoprime, it is sufficient that for every prime p dividing n, the order of 2 mod p, denoted ord_p(2), divides n-1. Under the same conditions, for n to be Fibonacci pseudoprime, it is sufficient that for every prime p dividing n, alpha(p) | n – (5/n), where alpha(p) is the Fibonacci sequence rank of apparition of p.
The strategy to construct a Baillie-PSW pseudoprime is an extension of the Erdos method to construct many Carmichael numbers. One first carefully selects moderate-sized highly composite numbers M and N with many small prime factors such that gcd(M,N)=2.
Secondly, one searches for so-called admissible primes p, i.e. odd primes such that
(1) ord_p(2) | M and
(2) alpha(p) | N.
(3) p coprime to M and N.
To give an idea, this search is conducted up to some bound such as 10^8 or 10^15. The set of all admissible primes found during a search is denoted P and can contain hundreds of primes or more.
Given a non-empty subset A of P, the product of all the elements of A is denoted f(A).
Thirdly, one searches for a non-empty, non-singleton subset A of P such that
(a) f(A) == 1 (mod M) and
(b) f(A) == -1 (mod N).
(c) f(A) == 2 or 3 (mod 5).
A solution to (a), (b), and (c) will be denoted n.
For an odd prime p dividing n, ord_p(2) | M | (n-1) and
alpha(p) | N | (n+1).
Because of (c), n – (5/n) = n+1. One concludes that n is both a Fermat base 2 pseudoprime and a Fibonacci pseudoprime.
On his web page, Greene gives two sets of values for M, N, and P at https://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html.
I have done my own study of the second, larger, set. I count 4816 elements of P. All of them are prime. All of them sattisfy condition (1) on admissible primes for the M and N in the second set of values. Of the 4816 elements of P, 4797 satisfy condition (2) on admissible primes. Finally, all of them are coprime to M and N. Therefore, they are a bona fide instance of a set of admissible primes for M and N.
The third step is the hardest to accomplish. Modulo MN/2, there are phi(MN/2) or about 2^1836 residue classes of numbers coprime to MN/2.
Assuming the subset products of P are reasonnably uniformly distributed mod MN/2, one would expect ~= 2^2980 products per coprime residue class mod MN/2, so an excellent chance of some subsets of P satisfying (a) and (b) and plenty of room to satisfy (c) also.
One can make a case that some subset A with 400 elements satisfies (a), (b), and (c). Indeed, C(4797, 400) ~= 2^1980 so one can expect about 2^144 products per coprime residue class modulo MN/2. Moreover, base 10 logs of elements of P are bounded above by 19.09.
Additionally, one can formulate (a), (b), and (c) in additive terms by working with primitive roots modulo primes and prime powers. In this new framework, with a tip from Chat-GPT, I calculated the exact distribution of subset products of P modulo some small primes p using generating functions. For p=1223, uniformity over the 1222 classes in (Z/pZ)* held to within 1 part in 10^300. For p=103, uniformity over the 102 classes in (Z/103Z)* held to within 1 part in 10^250. Finally, in the case p=3, there was perfect equidistribution of the 2^4816 subset products over the two residue classes in (Z/3Z)*.
In conclusion, my view is that, very probably, there is a Baillie-PSW pseudoprime in the sense of Chen and Greene with fewer than 7700 digits.
