Is there a "deep" reason that the first Perrin pseudoprime is large?

2010-12-20T07:23:42Z

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.

Answer by Jon Grantham for Is there a "deep" reason that the first Perrin pseudoprime is large?

2010-12-20T14:37:59Z

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.

Is there a "deep" reason that the first Perrin pseudoprime is large? - MathOverflow

Is there a "deep" reason that the first Perrin pseudoprime is large?

Answer by Jon Grantham for Is there a "deep" reason that the first Perrin pseudoprime is large?