Reasons to prefer one large prime over another to approximate characteristic zero

Question

Background: In running algebraic geometry computations using software such as Macaulay2, it is often easier and faster to work over $\mathbb F_p = \mathbb Z / p\mathbb Z$ for a large prime $p$, rather than over $\mathbb Q$. (Note that working directly over $\mathbb C$ is not really possible for exact computations.) Some basic model theory implies (more or less) that if you have a question that is capable of being answered by an algorithm, and the question has the same answer for $k$ as for $\bar{k}$, then its answer over $\mathbb Q$ will be the same as its answer over $\mathbb F_p$ for all but finitely many primes $p$. The accepted wisdom is that with virtually no exceptions, if you want to answer an algebro-geometric question over $\mathbb Q$, you can get a reliable answer by picking a large prime such as $p=32003$ and doing your computations over $\mathbb F_p$.

I think people generally pick a prime near the top of the range their software can handle, which is relatively easy to remember; $32003$ and $31667$, for instance, both fit the bill when using Macaulay2. However, I was wondering whether there are other mathematical characteristics of a prime that can affect how well it approximates characteristic zero. For instance, does some special pathology arise if $p$ is (or is not) a Mersenne prime, or if $(p-1)/2$ is (or is not) prime, or...?

Note that I only am asking about behavior that affects how well characteristic $p$ approximates characteristic $0$. Questions that one would only ever ask in finite characteristic are not relevant. Also irrelevant are questions that cannot be answered by an algorithm; for instance, "is $n\cdot1=0$ for some positive integer $n$" cannot be asked unless you include a bound on $n$.

The Question: Are there valid mathematical reasons for preferring one large prime over another to approximate characteristic $0$, other than the assumption that larger primes are generally better?

Answer 1

On the theme of how large a prime has to be for computations modulo that prime to be assured of approximating characteristic 0, an example that looks quite striking is offered in the first three sentences of Ruppert's paper "Reducibility of polynomials $f(x,y)$ modulo $p$" in Journal of Number Theory 77 (1999), 62-70, which is available online here. The start of the paper is also quoted in the review of this paper on MathSciNet (MR1695700). Here is how it starts:

"It is well known that the reduction $f \bmod p$ of an absolutely irreducible polynomial $f \in {\mathbf Z}[x,y]$ is also absolutely irreducible if the prime $p$ is large enough, e.g. $f = x^9y-9x^9-2x+9y+2$ is absolutely irreducible over $\mathbf Q$ but reducible modulo $p = 186940255267545011$, where $x - 93470127633772547$ divides $f \bmod p$. It is natural to ask how large $p$ has to be to be sure that $f \bmod p$ is absolutely irreducible."

When I first saw that I was shocked. How does anyone discover such stuff? The example is actually less surprising than it appears at first glance if you use resultants. View $f(x,y)$ as a linear polynomial in $y$ with $y$-coefficient $x^9 + 9$ and constant term $-9x^9-2x+2$: the resultant of $x^9 + 9$ and $-9x^9-2x+2$ is that 18-digit prime $p=186940255267545011$, so those two polynomials in $x$ have a common root $a$ in $\mathbf F_p$ for that 18-digit prime $p$, and in fact their unique root mod $p$ is $a \bmod p$ where $a = 93470127633772547$. You can check $f(a,y) \bmod p$ is $0$ in $\mathbf F_p[y]$. Therefore in $\mathbf F_p[x,y]$, $f(x,y) \bmod p$ is reducible with factor $x - a \bmod p$.

Resultants come up in other problems where first instances of phenomena can be incredibly large compared to the sizes of the coefficients. For example, the polynomials $x^{19}+6$ and $(x+1)^{19}+6$ are relatively prime in characteristic 0. For any prime $p$ not dividing the resultant of these polynomials, $x^{19}+6 \bmod p$ and $(x+1)^{19}+6 \bmod p$ are relatively prime. What about primes that divide the resultant? The resultant of $x^{19}+6$ and $(x+1)^{19}+6$ is $5299875888670549565548724808121659894902032916925752559262837 $, a 61-digit prime number. Modulo this prime, the reductions of $x^{19}+6$ and $(x+1)^{19}+6$ share one common root: $1578270389554680057141787800241971645032008710129107338825798$. This number has 61 digits. For all positive integers less than this, so in particular for all positive integers $n < 10^{50}$, $n^{19}+6$ and $(n+1)^{19}+6$ are relatively prime. That patterns breaks for the first time at $n = 1578270389554680057141787800241971645032008710129107338825798$, where the gcd of $n^{19}+6$ and $(n+1)^{19}+6$ is the 61-digit prime 5299...837 listed above.

Answer 2

You will find more information about this in the textbook Modern Computer Algebra by von zur Gathen and Gerhard.

I will illustrate my answer using one particular application of this: zero testing of arbitrary expressions. The foundational papers here are

1. Determining equivalence of expressions in random polynomial time by G.H. Gonnet, STOC '84
2. New results for random determination of equivalence of expressions also by G.H. Gonnet, SYMSAC '86

For that particular problem, things really get interesting when one needs algebraic and even transcendental extensions of the base field (aka $\mathbb{Q}$). For example, if one needs both $i$ and $\sqrt{3}$ to have good properties in $\mathbb{Z}_p$, that is much harder to arrange. Even worse, if one needs $e^{ix}$, then the properties of $\frac{p-1}{2}$ in $\mathbb{Z}_p$ start to matter too. Wanting to have both $i$ and $e^{ix}$ simultaneously have good properties is almost impossible.

The way random probabilistic testing works is that all the indeterminates are replaced by random integers (usually chosen to have long orbits); but one needs to do the same for all the extensions of the ground field. So $\sqrt{2}$ needs to be replaced by some $z$ which is both random and satisfies $z^2-1$, which seriously stresses whatever concept of randomness one has. And so on; this tends to eliminate a lot of primes which do not have the right properties.

This is why Maple's testeq routine uses a collection of largish primes (now chosen near the 64-bit boundary rather than 32 bit). There are two reasons: one is to find good primes, the other is to use multiple good primes as the compromises needed to arrange that the random choices have "good" properties drive up the probability that things might be equal by chance/bad luck. So to drive the overall probability of such accidents back down to below random-bit-flip-by-cosmic-ray range, more primes are needed.

But basically, in this one application, checking that arbitrary expressions are equivalent (over $\mathbb{C}$), one does need a lot more structure from the chosen primes, namely that they reflect the properties of the extensions used in the expression.

Answer 3

I prefer primes like 1000003 and 1000000007 because it is easy to recognize small integers and rational numbers with small denominators in the output. For instance, modulo 1000003 we have 1/3=666669, -1/3=333334, 1/5=600002. I know that's not what you are asking from the mathematical point of view, but from practical point of view it is very helpful.

EDIT: To answer the OP question, my answer is no. There is no mathematical reason one prime can behave better than another one in an algebraic computation. Of course, larger primes are better because there are less coincidences when you ask if $x=0$. But that's it. I am happy to be proven wrong.