{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 }{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 "" {MPLTEXT 1 0 23 "f:=add(a.i*x^i,i=0.. 3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "g:=add(b.i*x^i,i=0.. 3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "R:=resultant(f,g,x); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "factor(R); # irreducibl e" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 101 "Lets think of f and g as po lynomials of degree three, so they have both have. Say, the roots of f are" }}{PARA 0 "" 0 "" {TEXT -1 67 "alpha1, alpha2, alpha3 (not nece ssarily different from each other)" }}{PARA 0 "" 0 "" {TEXT -1 23 "and the roots of g are:" }}{PARA 0 "" 0 "" {TEXT -1 22 "beta1, beta2, b eta3." }}{PARA 0 "" 0 "" {TEXT -1 401 "Of course, when the leading coe fficient a3 of f equals zero then degree(f,x)<3, so then f has less th an 3 roots. In that case we will pretend that f still has three roots, and degree(f,x) of them (counting with multiplicity) are finite, the \+ other 3-degree(f,x) we think of those as infinity. So when degree(f,x) <3 and degree(g,x)<3 then we'll think of f and g as having a common ro ot, namely infinity." }}{PARA 0 "" 0 "" {TEXT -1 72 "With this interpr etation of \"f and g have a common root\", it is so that:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 137 "the values for a. i and b.i for which f and g have a common root are precisely the solut ions (a0,a1,a2,a3,b0,b1,b2,b3) of the resultant R." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 551 "We will show how we can \+ obtain this polynomial R by a modification of the Euclidean Algorithm. Basically the idea is to just do the Euclidean Algorithm, but you don 't reduce the ideal all the way to one generator (f,g)=(d), you stop o ne step before you get there. When f and g are polynomials like above \+ with generic coefficients (i.e. the coefficients are variables for whi ch you can still substitute any number) then at the end you have (f,g) = (1) but just before that last step you have (f,g) = (polynomial of \+ degree >0, polynomial R of degree 0)." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 164 "Now when the coefficients a.i and b. i are such that that R vanishes, well, then you see that at that point you do have a non-trivial gcd. Let's do this computation." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "f,g;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "f := factor(rem(f,g,x));" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "g := fa ctor(rem(g,remainder,x));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 154 "We \+ would like to avoid denominators in this computation. This is done by \+ not taking the remainder but the so-called PSEUDO-REMAINDER. The idea \+ is that if:" }}{PARA 0 "" 0 "" {TEXT -1 30 " degree(f,x) >= degree( g,x)" }}{PARA 0 "" 0 "" {TEXT -1 14 "and if you do:" }}{PARA 0 "" 0 " " {TEXT -1 14 " rem(f,g,x)" }}{PARA 0 "" 0 "" {TEXT -1 195 "and the coefficients of f and g are in some ring R (in our case R=Z[a0,a1,a2, a3,b0,b1,b2,b3]) hen the worst what you can get in the denominator of \+ rem(f,g,x) is lcoeff(g,x) to some power, namely:" }}{PARA 0 "" 0 "" {TEXT -1 41 " lcoeff(g,x)^(1+degree(f,x)-degree(g,x))." }}{PARA 0 "" 0 "" {TEXT -1 91 "So, if we multiply rem(f,g,x) by that amount, we are certain that we'll avoid denominators." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 86 "Now, if degree(f,x) >= degree(g,x) t hen the pseudo-remainder of f and g is defined as:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "prem(f,g,x) = lcoeff(g,x) ^(1 + degree(f,x) - degree(g,x);" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 101 "And it is easy to see that if the coeffi cients of f and g are in some ring R, then so is prem(f,g,x)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 57 "So let's \+ start over again, now using prem instead of rem." }}}{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 32 "remainder1, remainder 2 := f, g; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 108 "k:=1; while remainder.(k+1)<>0 do remainder.(k+2) := factor(prem(remainder.k,rema inder.(k+1),x)); k:=k+1 od;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 116 "Such a sequence of polyno mials f=remainder1, g=remainder2, remainder3, remainder4, ... , remain der.(k+1) = 0 where:" }}{PARA 0 "" 0 "" {TEXT -1 216 " remainder.(n+ 2) is a constant times the remainder of remainder.n and remainder.(n+1 ) (in our case: it's the pseudo-remainder, which is the same as the r emainder up to some constant factor lcoeff(..) to some power)" }} {PARA 0 "" 0 "" {TEXT -1 55 "is called a \"polynomial remainder sequen ce of f and g\"." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 15 "We notice that:" }}{PARA 0 "" 0 "" {TEXT -1 130 " degree (remainder.(n+1) , x) = degree(remainder.n , x) -1 except of course fo r remainder1 and remainder2 which were just f and g." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 456 "Note that: remainder.( n+2) is always some linear combination of remainder.(n+1) and remainde r.n. Therefore, every remainder.n is an element of the ideal (f,g). In the Euclidean Algorithm we keep on computing those remainders until w e hit zero, and then the last remainder before that, that's then the g cd. So here we find that the last non-zero element is remainder5. Sinc e this is a constant, not equal to 0, the polynomials f and g have no \+ common factor." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 235 "Now whenever you have 2 polynomials f and g, then in the polynomial remainder sequence (except the first two polynomials which are f and g) the degree will go down by at least 1 in every step. The refore, if f and g have degree 3, then:" }}{PARA 0 "" 0 "" {TEXT -1 23 "degree(remainder3) <= 2" }}{PARA 0 "" 0 "" {TEXT -1 23 "degree(rem ainder4) <= 1" }}{PARA 0 "" 0 "" {TEXT -1 24 "degree(remainder5) <= 0. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 240 "So i f f and g are polynomials of degree 3, and if remainder5 <> 0, then th e ideal (f,g) contains remainder5<>0 which is a constant because the d egree is <= 0. And if the ideal (f,g) contains a constant then f and g have no factor in common." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "Hence: if f and g have degree 3, then:" }}{PARA 0 "" 0 "" {TEXT -1 78 " remainder5 <> 0 implies: f and g have no \+ common root (no common factor)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 308 "The converse is not true. If f and g hav e no common root, it is still possible for remainder5 to be 0. But thi s can only happen when the degree drops by more than 1 at some point i n the polynomial remainder sequence. This happens whenever the leading coefficient of one of the remainders happens to become 0." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "lcoeff(remainder2,x);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 83 "If lcoeff(remainder2,x)=0 then degree(rem ainder2,x) would not be 3 but would be <3." }}{PARA 0 "" 0 "" {TEXT -1 90 "The consequence of that would be that degree(remainder3,x) woul d not be 2 but would be <2." }}{PARA 0 "" 0 "" {TEXT -1 90 "The conseq uence of that would be that degree(remainder4,x) would not be 1 but wo uld be <1." }}{PARA 0 "" 0 "" {TEXT -1 126 "The consequence of that wo uld be that remainder5=0, even though f and g need not necessarily hav e common factors. For example:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "v:=subs(b3=0, [f,g]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "rema1, rema2 := op(subs(seq(i=rand(-100..100)(), i=indets(v) min us \{x\}),v));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "k:=1; whi le rema.(k+1)<>0 do rema.(k+2) := factor(prem(rema.k,rema.(k+1),x)); k :=k+1 od;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "gcd(rema1, rem a2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 45 "We see that rema5=0 even \+ though the gcd is 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 73 "A similar thing can happen when accidentally the follow ing would be zero:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "lcoef f(remainder3,x);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "If this polyn omial happens to vanish, then that would have the following consequenc es:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 51 "de gree(remainder3,x) would not be 2 but would be <2" }}{PARA 0 "" 0 "" {TEXT -1 51 "degree(remainder4,x) would not be 1 but would be <1" }} {PARA 0 "" 0 "" {TEXT -1 89 "Hence: remainder5 would be 0, whether f a nd g have a common root or not. See for example:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "v:=subs(b3=12,a2=4,a3=16,b2=3,[f,g]); # Now b 3*a2-a3*b2=0." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "rema1, rem a2 := op(subs(seq(i=rand(-100..100)(), i=indets(v) minus \{x\}),v));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "k:=1; while rema.(k+1)<>0 do rema.(k+2) := factor(prem(rema.k,rema.(k+1),x)); k:=k+1 od;" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 85 "Again we see that remainder5 vanis hes, even though these f and g have no common root." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 36 "The conclusion is now t he following:" }}{PARA 0 "" 0 "" {TEXT -1 81 "If the coefficients a.i \+ and b.i of polynomials f and g of degree 3 are such that:" }}{PARA 0 " " 0 "" {TEXT -1 58 "1) the lcoeff of the intermediate remainders do no t vanish" }}{PARA 0 "" 0 "" {TEXT -1 26 "2) remainder5 does vanish." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "Then: f \+ and g will have a common root." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "lcoeff(remainder2,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "lcoeff(remainder3,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "lcoeff(remainder4,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "remainder5;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "Now, if we rem ove the factors in those lcoeffs from remainder5 we get:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "remainder5/b3^2/(b3*a2-a3*b2)^2;" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(%);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 242 "So using the Euclidean algorithm we've c omputed this irreducible polynomial. Now this polynomial will be zero \+ if and only if f and g have a common root. This polynomial in the a.i \+ and b.i is the same (up to a factor -1 here) as the resultant." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "R:=resultant(f,g,x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "normal(%%/R);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 64 "Subresultant PRS algorithm. (PRS=polynomi al remainder sequence)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 400 "The subresultant PRS algorithm computes a polynomia l remainder, but it uses a clever theorem that tells you which factors you will always get in the content of remainder3, remainder4, ... S o this algorithm will divide out those factors out of the content that the theorem predicts will be there. The consequence of that is that y ou won't get these factors like b3 and b3*a2-a3*b2 in the end result. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 284 "So t he subresultant PRS algorithm computes a PRS (a PRS is basically the s equence of remainders in the Euclidean algorithm, up to some constant \+ factors). The last entry of this PRS is the resultant, and the resulta nt will be zero if and only if the two polynomials have a common root. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "f:=x^3+a*x+a;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "g:=x^3-a*x+2*a;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 61 "Question: what should a be for f and g to have a common root?" }}{PARA 0 "" 0 "" {TEXT -1 7 "Answer:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "resultant(f,g,x);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "solve(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "subs(a=0,[f,g]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "subs(a=-1/12,[f,g]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "gcd(op(%));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "f:=a*x^4+a*x^3+x^2 +b*x+b;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "g:=x^5-x;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "factor( resultant(f,g,x) ); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "v:=[solve(%,b)];" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "gcd(f,g);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "for i in v do i; gcd(op(subs(b=i, [f,g]))) od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "Substitute anything else \+ for b and the gcd will be 1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "a:=17;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "v;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "gcd(f,g);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "subs(b=123,f);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 9 "gcd(%,g);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "for i in v do i; gcd(subs(b=i,f) , g) od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 125 "Now we will address the same problem (for which value s of the coefficients do f and g have a common root) in a different wa y." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "Let s assume that f and g 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 only when s is divible by g." }}{PARA 0 "" 0 "" {TEXT -1 59 "And: t*g is divisi ble 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 constan t. 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=degree(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 dimension 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 th at: kernel(L) = 0 if and only if f and g have no common factor. Now th e transpose of the matrix of this map is called the Sylvester matrix. \+ 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 r esultant of f and g is defined as the determinant of the Sylvester mat rix of f and g." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "restart; 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 10 "factor(R);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "alias( r=RootOf(R) );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "gr := subs(b1=r,g);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "gcd(f,gr);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "sylvester(f,gr,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "de t(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "r;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "op(r);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {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: =numer(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]); # Co mmon root 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 "What 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 theref ore 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 inf inity should be interpreted as that for a=1 both degrees of f and g ha ve decreased." }}{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 w e're looking 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(resul tant(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 numbe r, the polynomials 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 resultant is 0 modulo 5, and ther e is a common root (infinity), but no common factor. For all prime num bers 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 ig cd( 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 "plot( [Xt, Yt, t=-100..100] \+ );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 288 "We have two rational funct ions Xt and Yt in Q(t). Here Q(t) stands for all rational functions in t with rational numbers as coefficients. From the picture we can clea rly see that Xt and Yt are algebraically dependent. This means that th ere exist a polynomial P in two variables such 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 this 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 could we have computed that? Well, w hen we substitute x=Xt and y=Yt then the x^2+y^2-1 should become 0." } }{PARA 0 "" 0 "" {TEXT -1 205 "Another way to say that is when: x-Xt a nd y-Yt have a common root t=some number then x^2+y^2-1 = 0. So we're \+ searching for some expression x^2+y^2-1 that vanishes whenever x-Xt an d 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 "re sultant(%,%%,t);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 122 "The sylveste r 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) (numer=numerator)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "numer(x-Xt);" }}}{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 "Anot her 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-X t), numer(y-Yt), t);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "sub s(t=17,[Xt,Yt]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "subs(x= %[1], y=%[2], P);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}} {MARK "130" 0 }{VIEWOPTS 1 1 0 1 1 1803 }