Given an algebraic plane curve f(x,y)=0f(x,y)=0, we've been looking at the problem of finding a rational parametrization (x(t),y(t))(x(t),y(t)) for it, where x(t)x(t) and y(t)y(t) are rational functions of tt. In several examples (and in a couple of general cases) we've been able to show that curves are rational and exhibit rational parametrizations.
It's natural to ask the reverse question as well: given a parametric rational curve (x(t),y(t))(x(t),y(t)), can we find a polynomial f(x,y)∈R[x,y]f(x,y)∈R[x,y] so that f(x(t),y(t))=0f(x(t),y(t))=0? (One of the homework problems asks you to do this for a non-rational parametrization of the cardioid.)
Proposition Given rational functions x(t)x(t) and y(t)y(t), there exists a polynomial f(x,y)∈R[x,y]f(x,y)∈R[x,y] such that f(x(t),y(t))≡0f(x(t),y(t))≡0.
We can write the given rational functions as x(t)=a(t)q(t)x(t)=a(t)q(t) and y(t)=b(t)q(t)y(t)=b(t)q(t) for some polynomials a(t),b(t),q(t)∈R[t]a(t),b(t),q(t)∈R[t]. For some large degree NN, we'll try to find a polynomial f(x,y)∈R[x,y]f(x,y)∈R[x,y] of degree NN so that f(x(t),y(t))≡0f(x(t),y(t))≡0, or equivalently so that
q
(
t
)
N
(
f
(
x
(
t
)
,
y
(
t
)
)
≡
0
.
q
(
t
)
N
(
f
(
x
(
t
)
,
y
(
t
)
)
≡
0
.
(30)Let n=degq(t)n=degq(t) and m=max{dega(t),degb(t)}m=max{dega(t),degb(t)}. Then q(t)Nf(x(t),y(t))q(t)Nf(x(t),y(t)) is a polynomial in tt of degree at most Nn+NmNn+Nm, whose coefficients are homogeneous linear functions of the coefficients of ff. Thus setting all of its coefficients equal to zero give at most Nn+Nm+1Nn+Nm+1 homogeneous linear equations for the coefficients of ff, and if we can pick NN so that there are at least as many variables as there are equations (i.e. ff has at least Nn+Nm+1Nn+Nm+1 coefficients), then we can solve the system and find an ff with q(t)Nf(x(t),y(t))≡0q(t)Nf(x(t),y(t))≡0, and we'll be done.
The degree kk part of ff is
f
k
(
x
,
y
)
=
c
k
,
0
x
k
+
c
k
-
1
,
1
x
k
-
1
y
+
⋯
+
c
0
,
k
y
k
,
f
k
(
x
,
y
)
=
c
k
,
0
x
k
+
c
k
-
1
,
1
x
k
-
1
y
+
⋯
+
c
0
,
k
y
k
,
(31)which has k+1k+1 coefficients. Overall then, ff has 1+2+⋯+(N+1)=N(N+1)21+2+⋯+(N+1)=N(N+1)2 coefficients, and since this is quadratic in NN and Nn+Nm+1Nn+Nm+1 is linear, for sufficiently large NN we have N(N+1)2≥Nn+Nm+1N(N+1)2≥Nn+Nm+1 as desired.
While this proves that it is always possible to find a polynomial vanishing on a rationally parametrized curve, there are a few things that we might not like so much about it. For one thing, NN may be bigger than it has to be; for example, in the parametrization 1-t21+t2,2t1+t21-t21+t2,2t1+t2 for the circle, the proof would use the value N=8N=8 to find a degree ≤8≤8 polynomial f(x,y)f(x,y) vanishing on the circle, i.e. the solutions to the system would be the f(x,y)=(x2+y2-1)g(x,y)f(x,y)=(x2+y2-1)g(x,y) for arbitrary polynomials g(x,y)g(x,y) of degree ≤6≤6. This isn't really a big problem though, since we could always try to solve the systems for lower degrees first.
The bigger complaint we might have is that even for small degree examples, this involves solving a big system of linear equations in a big number of variables. Of course, computers are pretty good at solving systems of linear equations, but this certainly isn't something we'd want to do by hand, and even computer algebra systems might have some trouble dealing with huge numbers of variables.
In fact, there is a nicer way to do the computation, and it involves thinking about the problem more geometrically. We can think of the graph of the rational function
(x(t),y(t))=a(t)p(t),b(t)q(t)(x(t),y(t))=a(t)p(t),b(t)q(t) in R3=R2×RR3=R2×R as being the common zeros of the two polynomials
g
(
x
,
y
,
t
)
=
a
(
t
)
-
x
p
(
t
)
and
h
(
x
,
y
,
t
)
=
b
(
t
)
-
y
q
(
t
)
g
(
x
,
y
,
t
)
=
a
(
t
)
-
x
p
(
t
)
and
h
(
x
,
y
,
t
)
=
b
(
t
)
-
y
q
(
t
)
(32)in R[x,y,t]R[x,y,t]. Our goal then is to find a polynomial f(x,y)f(x,y) in only the variables xx and yy so that whenever g(x0,y0,t)=h(x0,y0,t)=0g(x0,y0,t)=h(x0,y0,t)=0 for some value of tt, we have f(x0,y0)=0f(x0,y0)=0.
If we could write some polynomial f(x,y)∈R[x,y]f(x,y)∈R[x,y] in the form
f
(
x
,
y
)
=
a
(
x
,
y
,
t
)
f
(
x
,
y
,
t
)
+
b
(
x
,
y
,
t
)
g
(
x
,
y
,
t
)
,
f
(
x
,
y
)
=
a
(
x
,
y
,
t
)
f
(
x
,
y
,
t
)
+
b
(
x
,
y
,
t
)
g
(
x
,
y
,
t
)
,
(33)for polynomials a(x,y,t),b(x,y,t)∈R[x,y,t]a(x,y,t),b(x,y,t)∈R[x,y,t], then f(x,y)f(x,y) would certainly have this property, and thus be a polynomial vanishing on the parametrized curve. For example,
x
2
+
y
2
-
1
=
1
2
t
x
y
+
1
2
t
y
-
x
+
1
2
y
2
-
1
1
-
t
2
-
(
1
+
t
2
)
x
)
-
1
2
t
x
2
+
t
x
+
1
2
t
+
1
2
x
y
+
1
2
y
2
t
-
(
1
+
t
2
)
y
.
x
2
+
y
2
-
1
=
1
2
t
x
y
+
1
2
t
y
-
x
+
1
2
y
2
-
1
1
-
t
2
-
(
1
+
t
2
)
x
)
-
1
2
t
x
2
+
t
x
+
1
2
t
+
1
2
x
y
+
1
2
y
2
t
-
(
1
+
t
2
)
y
.
(34)Over the next few weeks, we'll start learning about a computational tool called Gröbner bases that will tell us how to find such an ff, and will more generally allow us to study the question of, given polynomials h1,...hk∈R[x1,...,xn]h1,...hk∈R[x1,...,xn], which polynomials f∈R[x1,...,xn]f∈R[x1,...,xn] can be written in the form
f
=
q
1
h
1
+
⋯
q
k
h
k
f
=
q
1
h
1
+
⋯
q
k
h
k
(35)for some q1,...,qk∈R[x,...,xn]q1,...,qk∈R[x,...,xn]?
We'll begin with some terminology. If f1,...,fk∈R[x1,...,xn]f1,...,fk∈R[x1,...,xn] are polynomials then the ideal generated byf1,...,fkf1,...,fk is the set
〈
f
1
,
...
,
f
k
〉
=
{
q
1
f
1
+
⋯
+
q
k
f
k
:
q
1
,
...
,
q
k
∈
R
[
x
1
,
...
,
x
n
]
}
.
〈
f
1
,
...
,
f
k
〉
=
{
q
1
f
1
+
⋯
+
q
k
f
k
:
q
1
,
...
,
q
k
∈
R
[
x
1
,
...
,
x
n
]
}
.
(36)More generally, a non-empty subset I⊆R[x1,...,xn]I⊆R[x1,...,xn] is defined to be an ideal if g1f1+g2f2∈Ig1f1+g2f2∈I for every f1,f2∈If1,f2∈I and g1,g2∈R[x1,...,xn]g1,g2∈R[x1,...,xn].
Theorem (Hilbert Basis Theorem) Every ideal I⊆R[x1,...,xn]I⊆R[x1,...,xn] is generated by finitely many polynomials, so that
I
=
〈
f
1
,
...
,
f
k
〉
I
=
〈
f
1
,
...
,
f
k
〉
(37)for some f1,...,fk∈If1,...,fk∈I.
We probably won't prove this. We should note that this theorem doesn't say anything about the size of the smallest generating set of II, so kk here could be much bigger than nn.
When dealing with polynomials in one variable, a polynomial always has a clear leading term, namely the term of highest degree. For polynomials in several variables, there are many different ways we might want to order the monomials. For convenience, if α=(a1,...,an)α=(a1,...,an) is an nn-tuple of non-negative integers, then we will write
x
α
=
x
1
a
1
x
2
a
2
⋯
x
n
a
n
x
α
=
x
1
a
1
x
2
a
2
⋯
x
n
a
n
(38)as an abbreviated notation for the corresponding monomial. Although there are many orderings on the monomials to choose from, we want them to respect the algebraic structure. For example if xαxα divides xβxβ, then we would like xαxα to be smaller than xβxβ.
A monomial order for R[x1,...,xn]R[x1,...,xn] is a total order on the monomials such that if xα<xβxα<xβ then
xγxα<xγxβxγxα<xγxβ for all monomials xγxγ which is a well-ordering.
Example: Lexicographic order
Probably the simplest monomial ordering is the lexicographic (or “dictionary”) ordering. In this ordering, the power of the first variable is used to determine the order, with powers of the second variable only looked at when the first variable appears to the same power in two monomials. Similarly, we only look at the third variable when the first two are tied, and so on. For example, in the lex order for R[x,y,z]R[x,y,z] with x>y>zx>y>z, we have
x
4
>
x
3
y
2
z
>
x
3
y
z
7
>
x
3
y
z
4
>
x
2
y
z
5
>
x
y
3
z
2
>
x
y
>
x
z
2
>
x
>
y
6
>
y
5
z
3
>
y
z
6
>
y
>
z
3
>
1
.
x
4
>
x
3
y
2
z
>
x
3
y
z
7
>
x
3
y
z
4
>
x
2
y
z
5
>
x
y
3
z
2
>
x
y
>
x
z
2
>
x
>
y
6
>
y
5
z
3
>
y
z
6
>
y
>
z
3
>
1
.
(39)More formally, given two monomials xαxα and xβxβ in R[x1,...,xn]R[x1,...,xn], we say that xα>lexxβxα>lexxβ if in the difference of vectors α-βα-β, the leftmost non-zero entry is positive. One can check that this does in fact define a monomial order.
Example: Graded lexicographic order
One thing we might not like about lex order is that it doesn't respect degrees (e.g. xy>y3z4xy>y3z4). We can define a new order, called graded lexicographic order by saying that higher degree monomials are bigger and using lex order to break ties. For example,
x
7
>
z
7
>
x
2
y
2
z
2
>
x
2
y
z
3
>
x
y
5
>
y
3
z
3
>
y
z
5
>
x
5
>
x
4
y
>
x
3
y
2
>
x
3
y
z
>
x
3
z
2
.
x
7
>
z
7
>
x
2
y
2
z
2
>
x
2
y
z
3
>
x
y
5
>
y
3
z
3
>
y
z
5
>
x
5
>
x
4
y
>
x
3
y
2
>
x
3
y
z
>
x
3
z
2
.
(40)More formally, we say that xα>grlexxβxα>grlexxβ if degxα>degxβdegxα>degxβ or if degxα=degxβdegxα=degxβ and xα>lexxβxα>lexxβ. Since the partial ordering by degree and the lexicographic ordering both have the property that
x
α
<
x
β
⇒
x
γ
x
α
<
x
γ
x
β
for
all
monomials
x
γ
,
x
α
<
x
β
⇒
x
γ
x
α
<
x
γ
x
β
for
all
monomials
x
γ
,
(41)the graded lexicographic order has this property as well. Since any graded order (an order in which degree is used first and then something else is used as a tie-breaker) satisfies well-ordering automatically (because there are only finitely many monomials of each degree), we see that grlex is a term order.
Example: Graded reverse lexicographic order
Perhaps one of the most frequently used term orders in practice (because it tends to result in faster computations) is graded reverse lexicographic or grevlex order. This one is perhaps a little more confusing. As the name suggests, graded reverse lexicographic order uses degree first, and uses “reverse lexicographic order” to break ties.
If we reverse the lexicographic order however, so that xα>revlexxβxα>revlexxβ if xα<lexxβxα<lexxβ, the result isn't a monomial ordering. It fails well-ordering, because there are infinite descending sequences, e.g. in revlex order we have
1
>
revlex
z
>
revlex
z
2
>
revlex
z
3
>
revlex
⋯
>
revlex
y
z
>
revlex
y
z
2
>
revlex
y
z
3
>
revlex
⋯
.
1
>
revlex
z
>
revlex
z
2
>
revlex
z
3
>
revlex
⋯
>
revlex
y
z
>
revlex
y
z
2
>
revlex
y
z
3
>
revlex
⋯
.
(42)However, the reverse of an order preserved under multiplication by xγxγ is at least still preserved under multiplication by xγxγ, so while reverse lexicographic order isn't a monomial order by itself, we can still use it to break ties in a graded order (for which well-ordering is automatic).
There's one final issue to defining grevlex: when we reverse the lex order, it reverses the order of the variables, but we still want to get an order with x1>x2>⋯>xnx1>x2>⋯>xn in the end. Thus we start with a lex order with xn>⋯>x1xn>⋯>x1, so that when we reverse it we get a reverse lexicographic order with x1>revlexx2>revlex⋯>revlexxnx1>revlexx2>revlex⋯>revlexxn. We then say that xα>grevlexxβxα>grevlexxβ if degxα>degxβdegxα>degxβ or if degxα=degxβdegxα=degxβ and xα>revlexxβxα>revlexxβ.
For example, in the graded reverse lexicographic order on R[x,y,z]R[x,y,z] with x>y>zx>y>z, we have
y
2
z
2
>
x
3
>
x
y
2
>
x
y
z
>
y
2
z
>
x
z
2
>
x
2
>
x
y
>
y
2
>
x
z
>
y
z
>
z
2
>
x
.
y
2
z
2
>
x
3
>
x
y
2
>
x
y
z
>
y
2
z
>
x
z
2
>
x
2
>
x
y
>
y
2
>
x
z
>
y
z
>
z
2
>
x
.
(43)Basically, we order by degree first, and break ties by saying a monomial is bigger if it has a smaller power of the least significant variable. More formally, we say that xα>xβxα>xβ if degxα>degxβdegxα>degxβ or if degxα=degxβdegxα=degxβ and in the vector difference α-βα-β, the rightmost non-zero entry is negative.
Exercises
- In each part, determine whether the polynomial f∈R[x]f∈R[x] is in the given ideal I⊆R[x]I⊆R[x]. Notice that determining if ff lies in the ideal 〈g〉〈g〉 is equivalent to determining if gg divides ff. How do we use the same idea in (c) and (d), where I=〈g1,g2〉I=〈g1,g2〉?
- f(x)=x2-3x+2f(x)=x2-3x+2, I=〈x-2〉I=〈x-2〉
- f(x)=x5-4x+1f(x)=x5-4x+1, I=〈x3-x2+x〉I=〈x3-x2+x〉
- f(x)=x2-4x+4f(x)=x2-4x+4, I=〈x4-6x2+12x-8,2x3-10x2+16x-8〉I=〈x4-6x2+12x-8,2x3-10x2+16x-8〉
- f(x)=x3-1f(x)=x3-1, I=〈x9-1,x5+x3-x2-1〉I=〈x9-1,x5+x3-x2-1〉
- Find an ideal I⊂R[x]I⊂R[x] in which every element f∈If∈I is divisible by xx, but such that x∉Ix∉I.
-
- Show that 〈x-y2,xy,y2〉=〈x,y2〉〈x-y2,xy,y2〉=〈x,y2〉.
- Is 〈x-y2,xy〉=〈x2,xy〉〈x-y2,xy〉=〈x2,xy〉?
- Rewrite each of the following polynomials, ordering the terms first with the lex order, then the graded lex order, and finally the graded reverse lex order, provided that x>y>zx>y>z.
- f(x,y,z)=2x+3y+z+x2-z2+x3f(x,y,z)=2x+3y+z+x2-z2+x3
- 2x2y8-3x5yz4+xyz3-xy42x2y8-3x5yz4+xyz3-xy4
- 7x2y4z-2xy6+x2y27x2y4z-2xy6+x2y2
- Ideals make sense in the ring of integers ZZ just as they do in polynomial rings like R[x]R[x]. For example, in ZZ the ideal I=〈a,b〉I=〈a,b〉 consists of all integers xa+ybxa+yb for x,y∈Zx,y∈Z.
- Is 10 in the ideal I=〈3〉I=〈3〉?
- Is 2 in the ideal I=〈5,8〉I=〈5,8〉?
- Is -6-6 in the ideal I=〈12,22〉I=〈12,22〉?
- Is 3 in the ideal I=〈68,173〉I=〈68,173〉?
