Is there a "deep" reason that the first Perrin pseudoprime is large? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T05:23:23Z http://mathoverflow.net/feeds/question/49935 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49935/is-there-a-deep-reason-that-the-first-perrin-pseudoprime-is-large Is there a "deep" reason that the first Perrin pseudoprime is large? Qiaochu Yuan 2010-12-20T07:23:42Z 2010-12-20T14:46:25Z <p>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</p> <p>$$\alpha_1^p + ... + \alpha_k^p \equiv \alpha_1 + ... + \alpha_k \bmod p.$$</p> <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 <strong>pseudoprime</strong> 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 <a href="http://en.wikipedia.org/wiki/Frobenius_pseudoprime" rel="nofollow">Frobenius pseudoprime</a> with respect to $f$.) In particular, a <a href="http://en.wikipedia.org/wiki/Fermat_pseudoprime" rel="nofollow">Fermat pseudoprime</a> with base $a$ is an $(x-a)$-pseudoprime. If $f$ is quadratic one gets a notion of pseudoprime related to (equivalent to?) the <a href="http://en.wikipedia.org/wiki/Lucas_pseudoprime" rel="nofollow">Lucas / Fibonacci pseudoprimes</a>.</p> <p>A <a href="http://en.wikipedia.org/wiki/Perrin_number" rel="nofollow">Perrin pseudoprime</a> is an $(x^3 - x - 1)$-pseudoprime, and the smallest Perrin pseudoprime which is not prime is $271441 = 521^2$. In <a href="http://mathoverflow.net/questions/15444/the-phenomenon-of-eventual-counterexamples/27546#27546" rel="nofollow">another MO thread</a> 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). </p> <p>I'm not convinced this is a phenomenon requiring a deep explanation. Hence what I would like to see is</p> <ul> <li>A heuristic relating the size of the smallest $f$-pseudoprime which is not prime to the "complexity" of $f$ (to be defined freely)</li> </ul> <p>and either</p> <ul> <li><p>A computation showing that the result for $f = x^3 - x - 1$ is consistent with the heuristic, or</p></li> <li><p>A computation showing that the result for $f = x^3 - x - 1$ is <em>not</em> consistent with the heuristic, and some speculation about why this should be the case.</p></li> </ul> http://mathoverflow.net/questions/49935/is-there-a-deep-reason-that-the-first-perrin-pseudoprime-is-large/49966#49966 Answer by Jon Grantham for Is there a "deep" reason that the first Perrin pseudoprime is large? Jon Grantham 2010-12-20T14:37:59Z 2010-12-20T14:46:25Z <p>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$.</p> <p>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.</p>