{VERSION 3 0 "SGI MIPS UNIX" "3.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0
1 0 0 0 0 }{CSTYLE "" -1 256 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 256 11 "Resultants." }}{PARA 0 "
" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 70 "Lets assume that f
and g are polynomials in x and have no common root." }}{PARA 0 "" 0 "
" {TEXT -1 27 "Let s and t be polynomials." }}{PARA 0 "" 0 "" {TEXT
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "Then: s*f is divisible by g o
nly when s is divible by g." }}{PARA 0 "" 0 "" {TEXT -1 59 "And: t*g
is divisible by f only when t is divisible by f." }}{PARA 0 "" 0 ""
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 11 "Now assume:" }}{PARA 0 "
" 0 "" {TEXT -1 29 "degree(s,x) < degree(g,x) and" }}{PARA 0 "" 0 ""
{TEXT -1 26 "degree(t.x) < degree(f,x)." }}{PARA 0 "" 0 "" {TEXT -1 0
"" }}{PARA 0 "" 0 "" {TEXT -1 45 "So then: s*f is divisible by g only \+
when s=0." }}{PARA 0 "" 0 "" {TEXT -1 47 "And : t*g is divisible \+
by f only when t=0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT -1 56 "Hence, with these degree conditions on s and t, we have
:" }}{PARA 0 "" 0 "" {TEXT -1 42 " (*) s*f + t*g = 0 if and only if \+
s=t=0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1
129 "It is easy to see that (*) will be false when gcd(f,g) is not con
stant. Because then just take s := g/gcd(f,g), t := -f/gcd(f,g)." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "Let n=deg
ree(f,x)" }}{PARA 0 "" 0 "" {TEXT -1 18 "and m=degree(g,x)." }}{PARA
0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 119 "Let V_n be the
vector space of all polynomials in x of degree less than n. The dimen
sion of this vector space equals n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }
}{PARA 0 "" 0 "" {TEXT -1 68 "Now (s,t) -> s*f + t*g is a linear map \+
L from V_m * V_n to V_(n+m)." }}{PARA 0 "" 0 "" {TEXT -1 286 "We have \+
seen that: kernel(L) = 0 if and only if f and g have no common factor.
Now the transpose of the matrix of this map is called the Sylvester m
atrix. So, the determinant of the Sylvester matrix is 0 if and only if
kernel(L)<>0, which happens if and only f and g have a common root."
}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 94 "Now the
resultant of f and g is defined as the determinant of the Sylvester m
atrix of f and g." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "restar
t; with(linalg):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "f:=add(
a.i*x^i,i=0..3); g:=add(b.i*x^i,i=0..3);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 17 "sylvester(f,g,x);" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 7 "det(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "
resultant(f,g,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "f:=17*
x^5+x^2+x+1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "g:=x^3+2*x^
2+b1*x+9;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "sylvester(f,g,
x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "det(%);" }}}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "R:=resultant(f,g,x);" }}}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21
"f:=(x-a/(a-1))*(x-1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "g
:=(x-1/(1-a))*x;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "f:=nume
r(f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "g:=numer(g);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "factor(resultant(f,g,x));" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "solve(%);" }}}{EXCHG {PARA
0 "> " 0 "" {MPLTEXT 1 0 36 "subs(a=0,[f,g]); # Two common roots." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "subs(a=-1,[f,g]); # Common r
oot x=1/2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "subs(a=1,[f,g]
); # Common root x=infinity" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "W
hat happened in this example is the following:" }}{PARA 0 "" 0 ""
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 382 "f has a root 1/(a-1) and
g has a root 1/(1-a) which both become infinity when a=1. So for a=1 \+
the polynomials f and g have a common root x=infinity, and therefore a
=1 is a root of the resultant. At a=1 the polynomials f and g are 1-x \+
and x, and don't have a non-trivial gcd. Having a common root infinity
should be interpreted as that for a=1 both degrees of f and g have de
creased." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1
30 "Lets look again at: s*f+t*g=0." }}{PARA 0 "" 0 "" {TEXT -1 15 "n:=
degree(f,x);" }}{PARA 0 "" 0 "" {TEXT -1 15 "m:=degree(g,x);" }}{PARA
0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 "and we're looki
ng for polynomials s,t of degree " 0 "" {MPLTEXT 1 0 15 "f:=randpoly(x);" }}}{EXCHG {PARA 0
"> " 0 "" {MPLTEXT 1 0 15 "g:=randpoly(x);" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 48 "readlib(ifactors): ifactors(resultant(f,g,x));" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "v:=%[2];" }}}{EXCHG {PARA
0 "> " 0 "" {MPLTEXT 1 0 19 "v:=[seq(i[1],i=v)];" }}}{EXCHG {PARA 0 ">
" 0 "" {MPLTEXT 1 0 32 "for p in v do Gcd(f,g) mod p od;" }}}{EXCHG
{PARA 0 "" 0 "" {TEXT -1 78 "For any other prime number, the polynomia
ls f and g will have no common root.." }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "f:=-80*
x^5+x^3+x+1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "g:=15*x^7+x
^6+x+9;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "resultant(f,g,x)
;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "v:=ifactors(%);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "v:=[seq(i[1],i=v[2])];" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "for p in v do Gcd(f,g) mod \+
p od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 141 "As we see, the resultan
t is 0 modulo 5, and there is a common root (infinity), but no common \+
factor. For all prime numbers that do not divide" }}{PARA 0 "" 0 ""
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 32 "igcd( lcoeff(f,x), lcoeff
(g,x) )" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1
81 "we have that Gcd(f,g) mod p is 1 if and only if p does not divide
the resultant." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 ""
{TEXT -1 102 "When p divides igcd( lcoeff(f,x), lcoeff(g,x) ) then we \+
can not be sure if Gcd(f,g) mod p is 1 or not." }}{PARA 0 "" 0 ""
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 25
"Elimination by resultant." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0
19 "Xt := -2*t/(1+t^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "
Yt := (1-t^2)/(1+t^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "p
lot( [Xt, Yt, t=-100..100] );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 288
"We have two rational functions Xt and Yt in Q(t). Here Q(t) stands fo
r all rational functions in t with rational numbers as coefficients. F
rom the picture we can clearly see that Xt and Yt are algebraically de
pendent. This means that there exist a polynomial P in two variables s
uch that:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1
13 "P(Xt,Yt) = 0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 ""
{TEXT -1 104 "In our example we can easily see in the picture that thi
s polynomial is (when we use variables x and y):" }}{PARA 0 "" 0 ""
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 19 "P(x,y) = x^2+y^2-1." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 107 "How coul
d we have computed that? Well, when we substitute x=Xt and y=Yt then t
he x^2+y^2-1 should become 0." }}{PARA 0 "" 0 "" {TEXT -1 205 "Another
way to say that is when: x-Xt and y-Yt have a common root t=some numb
er then x^2+y^2-1 = 0. So we're searching for some expression x^2+y^2-
1 that vanishes whenever x-Xt and y-Yt have a common root." }}}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "Xt;" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 3 "Yt;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "x-Xt;
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "y-Yt;" }}}{EXCHG {PARA
0 "> " 0 "" {MPLTEXT 1 0 18 "resultant(%,%%,t);" }}}{EXCHG {PARA 0 ""
0 "" {TEXT -1 122 "The sylvester matrix is defined for polynomials in \+
t, not for rational functions. But that's easy to handle, because when
:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "x-Xt
and y-Yt have a common root, then so do:" }}{PARA 0 "" 0 "" {TEXT
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "numer(x-Xt), numer(y-Yt) (num
er=numerator)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "numer(x-X
t);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "numer(y-Yt);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "resultant(%,%%,t);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "P:=sort(primpart(%));" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "Another example. Lets look at the \+
curve:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1
119 "\{ ( t^3+t-3/t , (t+1)/t^3) \} where t runs through the set of \+
all real numbers and infinity. What is the curve we get:" }}}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Xt := t^2+t-1/t;" }}}{EXCHG {PARA
0 "> " 0 "" {MPLTEXT 1 0 16 "Yt := (t+1)/t^3;" }}}{EXCHG {PARA 0 "> "
0 "" {MPLTEXT 1 0 43 "P:=resultant( numer(x-Xt), numer(y-Yt), t);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "57" 0 }
{VIEWOPTS 1 1 0 1 1 1803 }