Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
3  
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 ... –  Theo Johnson-Freyd May 16 '13 at 2:17
2  
... go into developing precisely this type of heuristic. –  Theo Johnson-Freyd May 16 '13 at 2:17
7  
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$. –  Timothy Chow May 16 '13 at 18:46
3  
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. –  Charles Staats May 19 '13 at 15:32
1  
@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. –  Charles Staats Jun 27 '13 at 4:10

2 Answers 2

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 at http://arxiv.org/pdf/math/9808021.pdf. 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. The polynomial is linear in $y$, so its $y$-partial derivative is a polynomial in $x$: $f_y = x^9 + 9$. The resultant of $f$ and $f_y$ is $-186940255267545011 = -p$. Therefore $f(x,y) \bmod p$ and $f_y(x,y) \bmod p$ have resultant $0$, so by the theory of resultants they share a common factor mod $p$. The reduction $f_y \bmod p$ has a single linear factor, namely $x+93470127633772547 \bmod p$. Notice the sign here is $+$ rather than $-$, so Ruppert's paper has a typographical error. Indeed, setting $a =93470127633772547$, you can check $f(-a,y) \equiv 0 \bmod p$ while $f(a,y) \not\equiv 0 \bmod p$, so $f(x,y) \bmod p$ is divisible by $x + a \bmod p$ and not $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.

share|improve this answer
    
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. –  Jacques Carette May 4 at 16:21
2  
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. –  KConrad May 4 at 16:38
    
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. –  Charles Staats May 4 at 17:42

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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