4
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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: mathoverflow.net/questions/15611/… $\endgroup$
    – François G. Dorais
    Commented Apr 8, 2010 at 16:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – Uri Andrews
    Commented Apr 8, 2010 at 23:18
  • $\begingroup$ 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". :) $\endgroup$
    – Pete L. Clark
    Commented Apr 9, 2010 at 3:23
  • $\begingroup$ @PLC: While you are correct, I gave the reference as it appears in Hrushovski's paper "Expansions of Algebraically Closed Fields". $\endgroup$
    – Uri Andrews
    Commented Apr 9, 2010 at 3:58
  • $\begingroup$ (Pete is correct, but "Lau" is a common misspelling and it is phonetically correct.) $\endgroup$
    – François G. Dorais
    Commented Apr 9, 2010 at 3:58

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Uri Andrews
    Commented Apr 15, 2010 at 20:47
  • $\begingroup$ 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. $\endgroup$
    – François G. Dorais
    Commented Apr 15, 2010 at 21:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .