65
$\begingroup$

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?

$\endgroup$
6
  • 4
    $\begingroup$ I think this is an interesting question, to which I do not have an answer. I will point out that in some sense no prime is better than any other: for any particular finite set of primes, certainly there are sentences that fail exactly on that set. So your question presupposes something about "interesting" questions that can be answered by an algorithm, or about questions that are "likely" to come up in "research". I doubt that pure model theory and pure number theory can give an absolute answer to things about "interesting" questions and "likely research", but conversely much work does ... $\endgroup$ May 16, 2013 at 2:17
  • 2
    $\begingroup$ ... go into developing precisely this type of heuristic. $\endgroup$ May 16, 2013 at 2:17
  • 8
    $\begingroup$ One kind of problem that can arise is that your polynomials of interest may include a univariate polynomial that "accidentally" splits modulo $p$. I'd be surprised if there were a uniform choice of $p$ that minimized such accidents; from a practical point of view, if you're worried about such things, it is probably better to repeat the calculation with a different choice of $p$ than to strain too hard to select the One True Value of $p$. $\endgroup$ May 16, 2013 at 18:46
  • 3
    $\begingroup$ Timothy: The sort of question for which this technique is applicable should have the same answer for $k$ as for $\bar{k}$. Thus, if the question you are asking has an answer that changes when a univariate polynomial splits, it's probably the wrong sort of question to begin with. $\endgroup$ May 19, 2013 at 15:32
  • 1
    $\begingroup$ @al-Hwarizmi: In principle, those computations are possible. In practice, the sort of question for which this method is useful will have the same answer for $\mathbb F_p$, $\mathbb F_{p^m}$, and $\overline{\mathbb F}_p$, so using $p^m$ instead of $p$ would incur additional computational cost for little or no benefit. $\endgroup$ Jun 27, 2013 at 4:10

3 Answers 3

41
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ This happens all the time when trying to factor multivariate polynomials (and the use Hensell lifting to recover the factors). Such cases are all over the computer algebra literature. It is surprising (to me) that this is not more widely known -- I guess one more example of how narrow the silos in academia are. $\endgroup$ May 4, 2014 at 16:21
  • 3
    $\begingroup$ I agree it would be a better situation if this phenomenon were more widely known. One reason it might not be is that you can learn the theory of resultants without computing them (which was the case for me when I first saw them). C'est la vie. $\endgroup$
    – KConrad
    May 4, 2014 at 16:38
  • 1
    $\begingroup$ A useful point that underscores the following comment: approximating characteristic 0 by characteristics like 31667 is useful because exceptions seem to be extremely rare--not because they are impossible. It's also why I'm looking for heuristics rather than theorems. $\endgroup$ May 4, 2014 at 17:42
  • $\begingroup$ It's not so surprising if you use the right heuristic. An irreducible polynomial with integer coefficients has (on average) $1$ root modulo $p$ by Chebotarev density theorem. Now if you have two polynomials $P, Q$ you can take that one root of $P$ and plug it into $Q$. It will be zero with probability $1/p$. What's the probability that it is not zero for all primes $p$? It's the product of $1-1/p$, but the series $\sum_p 1/p$ is divergent hence the product is zero. $\endgroup$ Apr 15, 2021 at 19:49
  • $\begingroup$ @AntonMellit you say it is not surprising that two irreducibles in $\mathbf Q[x]$ have a common root modulo some prime. Two relatively prime polynomials $f(x)$ and $g(x)$ in $\mathbf Q[x]$ are relatively prime mod $p$ for all but finitely many $p$, so the probabilistic heuristic you describe is modeling an event that can happen for each $f$ and $g$ only finitely many times. Thus it is not surprising that some polynomials fail the heuristic: $f(x) = x^3 - x + 1/3$ and $f'(x) = 3x^2 - 1$ are relatively prime and have resultant 1 (or $-1$), so they have no common root mod $p$ for all $p$. $\endgroup$
    – KConrad
    Apr 15, 2021 at 21:01
23
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.