5
$\begingroup$

Let $I\subset k[x_1,\dots,x_n]$ be an ideal in a polynomial ring in commuting variables. Is there a procedure to decide if $I$ contains a monomial and possibly to find one?

Gröbner bases come to mind, but for example, $$I = \langle x-y-z, y^4z^2+2y^3z^3+y^2z^4 \rangle = \langle x-y-z,x^2y^2z^2\rangle$$ has $$\left\{x^4y^2-2x^3y^3+x^2y^4, y^4z^2+2y^3z^3+y^2z^4, x^4z^2-2x^3z^3+x^2z^4, x-y-z\right\} $$ as its universal Gröbner basis, which makes me pessimistic about Gröbner methods. In this example, the symmetry can be broken by computing a primary decomposition which reveals the monomials, but what can be said in general?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ The ideal $I$ contains a monomial if and only if $x_1 \ldots x_n$ belongs to the radical of $I$. This happens if and only if $(x_1 \ldots x_n)^e \in I$, where $e$ is the Noether exponent of $I$, that is the smallest exponent such that $(\sqrt I)^e \subset I$. The effective Nullstellensatz gives you an explicit bound for $e$, see e.g. Jelonek, On the effective Nullstellensatz, Invent. Math. 2005. MR2198324 Once you know $e$, there are only a finite number of monomials to check, which you can do using Gröbner bases. $\endgroup$
    – François Brunault
    Commented Apr 5, 2013 at 15:10

1 Answer 1

Reset to default
7
$\begingroup$

Computing colon ideals is pretty quick. You could colon out the variables in order. If the ideal changes, record the variable that worked, and go back to the beginning of the list. Either you get to the unit ideal, in which case you found the lex-first monomial that's in the ideal, or you make it to the end of the list, in which case there's no monomial in your ideal.

EDITS:

  1. There's no need to loop back to the beginning of the list. Do $x_1$ to completion, then $x_2$, and so on.

  2. Doing $x_i$ only requires a Gröbner basis for an elimination order for $x_i$, and the colon ideal will come with a Gröbner basis again, for free. So you don't even need a universal Gröbner basis, just $n$ elimination Gröbner bases.

  3. You could also do this by coloning out $x_1 x_2 \cdots x_n$, which is very close to François Brunault's answer comment. But my understanding is that colon ideals are computed using the elimination of a new variable, so I doubt this is actually faster than what I'm suggesting.

  4. You don't even need those full Gröbner bases, just ones that are Gröbner enough; see e.g. theorem 6.3 of http://arxiv.org/abs/dg-ga/9706003 where we use a criterion like this to compute a cohomology ring.

ANOTHER:

You could slice with random hyperplanes, and whenever you get isolated points, see if each of those points has some coordinate $=0$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I've always wondered if there is a faster way to get the $n$ ideals $I:x_i$ than computing $n$ elimination orders from scratch. There should be some Gröbner walk type technique that lets one modify the elimination order GB for one variable to get to the next. Is that what your reference is about? $\endgroup$
    – Thomas Kahle
    Commented Apr 6, 2013 at 8:34
  • $\begingroup$ I find it hard to imagine why one would help you much for the next, but I dunno. The theorem I had there was pretty specialized to the context we needed it for. Anyway you can see for yourself. $\endgroup$
    – Allen Knutson
    Commented Apr 6, 2013 at 8:45

You must log in to answer this question.

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