# Is there a “deep” reason that the first Perrin pseudoprime is large?

Let $f(x) \in \mathbb{Z}[x]$ be a monic irreducible polynomial with roots $\alpha_1, ... \alpha_k$, and let $\Delta$ be the discriminant of $f$. For any prime $p \nmid \Delta$, the Frobenius morphism permutes the roots of $f$ in $\mathbb{F}_p$, hence in particular

$$\alpha_1^p + ... + \alpha_k^p \equiv \alpha_1 + ... + \alpha_k \bmod p.$$

(This result is also true for primes dividing the discriminant, but I don't know an algebraic argument, just a combinatorial one.) A positive integer $p \ge 2$ with this property is a kind of pseudoprime with respect to $f$, which I'll call an $f$-pseudoprime. (This is related to but weaker than the notion of a Szekeres pseudoprime or a Frobenius pseudoprime with respect to $f$.) In particular, a Fermat pseudoprime with base $a$ is an $(x-a)$-pseudoprime. If $f$ is quadratic one gets a notion of pseudoprime related to (equivalent to?) the Lucas / Fibonacci pseudoprimes.

A Perrin pseudoprime is an $(x^3 - x - 1)$-pseudoprime, and the smallest Perrin pseudoprime which is not prime is $271441 = 521^2$. In another MO thread Kevin O'Bryant mentioned that Freeman Dyson and others consider the size of this pseudoprime surprising and suspect there might be a good explanation of why it is larger than one might naively expect (akin to the explanation of why $e^{\pi \sqrt{163} }$ is close to an integer).

I'm not convinced this is a phenomenon requiring a deep explanation. Hence what I would like to see is

• A heuristic relating the size of the smallest $f$-pseudoprime which is not prime to the "complexity" of $f$ (to be defined freely)

and either

• A computation showing that the result for $f = x^3 - x - 1$ is consistent with the heuristic, or

• A computation showing that the result for $f = x^3 - x - 1$ is not consistent with the heuristic, and some speculation about why this should be the case.

-
I think this is an excellent question. I have given an informal talk on this property of Perrin numbers a few times (based partially on your comments at the above link—thanks!) and at the end exactly this question of finding such a heuristic always comes up. – Tom Church Dec 20 '10 at 7:59
I'd like to raise the following additional question: is there a heuristic that indicates that the number of composite $f$-pseudoprimes should be infinite? (Or even the existence of an $f$-pseudoprime?!)  I believe the infinitude of $f$-pseudoprimes is implied for any $f$ by Theorem 2.1 of Grantham, "There are infinitely many Perrin pseudoprimes", J. of Num. Th, 130 (5) 2010, 1117–28, pseudoprime.com/pseudo3.pdf. But it would be great to have an elementary heuristic (especially since this remained open for so many years). – Tom Church Dec 20 '10 at 8:14

A Carmichael number all of whose factors have $f$ splitting completely is an $f$-pseudoprime (sufficient, but not necessary). So if you take any heuristic that there are infinitely many Carmichael numbers (in particular with a fixed number of factors) and combine it with the idea that the probability of getting all factors splitting completely for a polynomial of degree $d$ is $(1/d!)^k$ (where $k$ is the number of factors), you can get a more elementary heuristic. My paper essentially followed that, but had to deal with the fact that we don't have infinitely many Carmichael numbers proven for any particular $k$.
As for the original question, has anyone computed the smallest $f$-pseudoprime with respect to a whole bunch of degree 3 irreducible polynomials and seen if the Perrin case is an outlier? That would be my first step.