MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $f_1,\ldots f_m \in k[X]$ have degrees bounded by $l$. and $I(\bar{f})$ be the ideal generated by $\bar{f}$. If $I(\bar{f})$ is not a prime ideal then its non-primeness is witnessed by polynomials of degree below $h(m,l)$ for some $h$ dependent only on $m$ and $l$. Hrushovski gives two references for the truth of this statement, but the reference is at least for me unreadable (one due to unavailability and one due to length and my laziness).

Question: Is it known that the function $h$ is bounded by a recursive function of (m,l)? A reference for a bounding of $h$ would be great.

share|cite|improve this question
Could you give the two references? Maybe someone can post a distilled proof from one or the other. I'm not aware of the specific result, but the flavor reminds me of the Effective Nullstellensatz, see my answer here:… – François G. Dorais Apr 8 '10 at 16:29
The two references that Hrushovski gives are: 1) Lau Van den Dries, Model theory of fields: decidability, and bounds for polynomial ideals, Doctoral Thesis, Univ. Utrecht, 1978 2) A Seidenberg, Constructions in algebra, Trans. Amer. Math. Soc. 197 (1974), 273-313. – Uri Andrews Apr 8 '10 at 23:18
Given that there is a Lou van den Dries working in the area of model theory and algebra, I somehow doubt there is also a "Lau Van den Dries". :) – Pete L. Clark Apr 9 '10 at 3:23
@PLC: While you are correct, I gave the reference as it appears in Hrushovski's paper "Expansions of Algebraically Closed Fields". – Uri Andrews Apr 9 '10 at 3:58
(Pete is correct, but "Lau" is a common misspelling and it is phonetically correct.) – François G. Dorais Apr 9 '10 at 3:58
up vote 1 down vote accepted

In his paper Constructions in algebra (MR349648), Seidenberg fixes some errors in Grete Hermann's classic paper Die Frage der endlich vielen Schritte in der Theorie der Polynomideale (MR1512302). Most of the work concentrates on two problems:

  1. Effectively compute the primary decomposition of an ideal.
  2. Effectively compute the associated prime of a primary ideal.

Together, these do give a primality test: first check that the ideal is primary by computing its primary decomposition and then check that it equals its associated prime.

Seidenberg's paper is very well written, but he obviously has a very limited audience in mind. He does prove along the way the existence of primitive recursive degree bounds, but the task to put them together into a precise form would require a fair amount of time. Seidenberg's constructivist point of view gets in the way of pragmatism from time to time.

There has been a lot of water under the bridge since 1974 and much of the contents of Seidenberg's paper must have been redone for practical use in modern computer algebra systems. Since working out the bounds from Seidenberg's paper looks impractical, I would consider looking at the computer algebra literature to see which algorithms are currently used to carry out the two steps above and derive effective degree bounds from these.

I am not very knowledgeable in such practical matters, but there are probably computer algebra experts lurking around here. If they don't see this post, then I suggest you ask another question for algorithms or degree bounds for steps 1 and 2 specifically.

share|cite|improve this answer
You say that he proves primitive recursive degree bounds? Certainly primitive recursive is recursive. I'm not particularly interested in a presentation, more that bounds exists. – Uri Andrews Apr 15 '10 at 20:47
As I said, the paper is a pain to read. He puts a lot of emphasis on the presentation of the base field which is not necessarily relevant in your case. The big workhorse is the theorem on page 306, which is an effective version of the Hilbert Basis Theorem. With that result, you should be able to make a lot of classical arguments effective. – François G. Dorais Apr 15 '10 at 21:37

Your Answer


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.