# 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

## 1 Answer

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.

• Thanks for your reply! So given that the smallest Carmichael number is 561, one might expect that the smallest Carmichael number with this additional property is in the ballpark of 561 * (3!)^3 = 121176, which is within a factor of 3. Of course I should probably be applying this heuristic more carefully... – Qiaochu Yuan Dec 20 '10 at 18:01
• No, the heuristic says that about 1/(3!)^3 Carmichael numbers with 3 prime factors will have this property. So it would not be surprising if you had to go up into the hundreds on a list of Carmichael numbers to find one with this property. Of course, that gives you numbers much bigger than the first counterexample, which is not surprising given that the Carmichael condition is a fair bit stronger. I was just giving a heuristic for the infinitude in my earlier answer. – Jon Grantham Dec 20 '10 at 22:02