## Elimination and Extension Theorems

Last time we talked about Groebner bases and Buchberger’s algorithm, so today we’ll do an application of them. In fact, a few, because the Elimination Theorem and the Extension Theorem are extremely useful results, and we’ll talk a bit about their geometric consequences. But first, the algebra:

Take an ideal $I$ in $k[x_1,\ldots,x_n]$. We call the $\ell$th elimination ideal the ideal $I\cap k[x_{\ell+1},\ldots,x_n]$ in $k[x_{\ell+1},\ldots,x_n]$. Note that if $\ell=0$, we just get $I$. Now, here’s the theorem: if $G$ is a Groebner basis for $I$ with respect to lexicographic order with $x_1>x_2>\ldots>x_n$, then for all $0\leq \ell\leq n$, we have $G_\ell=G\cap k[x_{\ell+1},\ldots,x_n]$ is a Groebner basis for the $\ell$th elimination ideal.

Note that this is NOT the Elimination Theory mentioned in Hartshorne, as theorem 5.7A in chapter 1. I want to say that Hartshorne’s Elmination Theory has more to do with resultants directly (now, resultants do tie in to this Elimination theory, but we’re not there just yet.)

So, perhaps an example would be good. Look at the ideal $I=(x^2+y+z-1,x+y^2+z-1,x+y+z^2-1)$. Now I go behind the curtain, plug things into Macaulay2, and wait for a Groebner basis to pop out, and it’s $\{x+y+z^2-1,y^2-y-z^2+z,2yz^2+z^4-z^2,z^6-4z^4+4z^3-z^2)$. So this tells us that $I_1$ is generated by all but the first, and that $I_2$ is generated by the last polynomial in the basis. So this just lets us eliminate variables and find polynomials in fewer to work with. Here, we get a polynomial just in $z$ which we can use to work out all the possible $z$‘s that can appear. It happens that the variety defined by this ideal is zero dimension, ie, just a finite collection of points. Seeing the polynomial in just $z$, we immediately know that there are only finitely many values of $z$ that appear, so it is contained in the union of a finite number of parallel hyperplanes.

So once we have a collection of $z$‘s, we want to work out what the possible $y$‘s are. Well, what we as humans do is we try to plug the values of $z$ into the equations that are just $y$ and $z$. So then we get finitely many possible $y$‘s, which sticks us in the situation where we have finitely many lines that the variety is contained in. Then, we check each pair of $(y,z)$ with the first equation, and find that there are only finitely many (in fact 5) points.

So elimination was great at helping us solve this system, but the plugging things back in step required a human hand. Plus, to get the five points, we did quite a lot of work plugging things in and solving polynomials, and even low degree polynomials can be a pain to work with…after all, when was the last time you willingly broke out Cardano’s formula?

To help us now, we state the Extension Theorem. Let $I=(f_1,\ldots,f_s)$ be an ideal in $k[x_1,\ldots,x_n]$, and let $I_1$ be the first elimination ideal. Then for each $1\leq i\leq s$ write $f_i$ in the form $f_i=g_i(x_2,\ldots,x_n)x_1^{N_i}+$lower order terms in $x_1$ and the $g_i$ are nonzero. Then, if there exists $(a_2,\ldots,a_n)$ in $V(I_1)$, and not in $V(g_1,\ldots,g_s)$, then there exists $a_1$ such that $(a_1,\ldots,a_n)\in V(I)$.

Ok, so to translate that: suppose we have a partial solution to a system of equations. If we can write the system as polynomials in one of the variables we haven’t solved for yet such that the coefficients are polynomials in the ones we have solved for and such that the lead coefficient don’t vanish there, then we can find a full solution. Also, we note that we can use this on other elimination ideals by just looking for extensions one variable at a time. In our problem above, we solve for $z$ in $I_2$ and want to find the $y$ such that $(y,z)$ is a partial solution. Well, we then use Extension on $I_2$ to get solution to $I_1$, and then use Extension again to get to $I$.

So now for some geometry. We’ll start with elimination. As you may have guessed from the statement, it’s all about projections. Let $V\subset \mathbb{A}^n$ be an affine variety, and choose coordinates so that a projection map $\pi$ to $\mathbb{A}^{n-1}$ is projection onto the last $n-1$ coordinates. Then the first elimination ideal of $I(V)$ is the ideal of the closure of $\pi(V)$.

Now for my favorite application of the elimination theorem. Let $\phi:k[x_1,\ldots,x_n]\to k[t_1,\ldots,t_m]$ be a ring homomorphism. Then we define the ideal of the
map $\phi$ to be $I_\phi=(x_1-\phi(x_1),\ldots,x_n-\phi(x_n))$ in $k[x_1,\ldots,x_n,t_1,\ldots,t_m]$. Take an ordering that puts all the $t_i$ in front of any of the $x_i$. Then $I_m=I\cap k[x_1,\ldots,x_n]$, the $m$th elimination ideal is the kernel of $\phi$.

Now, this is huge. What it really gives is the closure of the image of a morphism $\mathbb{A}^m\to \mathbb{A}^n$. So this lets us write down all sorts of rational varieties. Any time we’re given something parametrically, we can use this to get equations for it. By projectivizing these ideas, we can work out the images of maps between projective spaces and products of projective spaces. In particular, these methods let us work out the equations for subvarieties of the Segre and Veronese embeddings, among others.

Charles Siegel is currently a postdoc at Kavli IPMU in Japan. He works on the geometry of the moduli space of curves.
This entry was posted in AG From the Beginning, Algebraic Geometry, Big Theorems, Computational Methods. Bookmark the permalink.

### 11 Responses to Elimination and Extension Theorems

1. Pingback: Resultants « Rigorous Trivialities

2. Matt says:

Just out of curiosity, if you don’t have M2 handy how difficult is it to do such computations by hand? For example if I want to compute the image of the Veronese $\mb{P}^2 \rightarrow \mb{P}^5$ projected into $\mp{P}^4$ (say $x_0 = 0$) is it already computationally difficult?

3. Charles says:

Well, it’s a pain, because you do have to do all the S-polynomials and such by hand to work out the Groebner basis first, but it’s doable there because of the low number of variables and the low degrees involved.

4. nguyenvinh says:

Hi Charles,
Let I is a bi-homogeneous ideal of a algebraic set in P^nxP^m, the question is “what is the n-th elimination ideal of I, call I_n?”.

5. Charles says:

I’m assuming what you’re after is the image of the projection onto $\mathbb{P}^m$. There are a couple of new tricks regarding projective elimination, but if we take $I$ a bihomogeneous ideal in $k[x_0,\ldots,x_n,y_0,\ldots,y_m]$, we can define $\hat{I}$ to be $\{f\in k[y_0,\ldots,y_m]|\forall i,\exists e_i\geq 0$ with $x_i^{e_i}f\in I\}$. We need to do this because we want to exclude the case $x_i=0$ for all $i$, which we didn’t need to do in the affine case. This turns out to be the right ideal, and it’s the ideal of the projection of $V(I)$ onto $\mathbb{P}^m$.

We can describe this ideal by $(I:\langle x_0^e,\ldots,x_n^e\rangle)\cap k[y_0,\ldots, y_m]$ for big enough $e$, and this we can compute with Groebner bases (but this comment is getting a bit long.) If you want, I can write up a full post on projective elimination theory, and include this.

6. nguyenvinh says:

I think that it is quite complicated to compute Groebner basis for this ideal. I’m interested in the way we extend Groebner method of affine case to projective case. That’s great if you write a full post for that. Thanks.

7. Charles says:

It’s not that complicated, actually. I’ll work on it, though it won’t be up for a few days, at least.

8. guven akyol says:

iyi oldu çok da güzel oldu tamam mı

9. I’m going to give the benefit of the doubt, and assume this isn’t spam (no links)…but I don’t know this language, nor do I recognize what language it is…

10. Afshin says:

The language is Turkish and Google translates it:

It was good was very nice, okay