From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math.research Subject: Re: On resultants Date: 5 Nov 1996 21:50:20 GMT In article <55n5m3$acm@rzsun02.rrz.uni-hamburg.de>, Hauke Reddmann wrote: >Yes, I have some symbolic coefficients in my computation. >I better give an (longish) example: > >I have u=(x^8+44x^6+192x^5+646x^4-1344x^3+2156x^2+2401)/ >(8x(x^6+4x^5-19x^4-133x^2-196x+343)) and > >v=(-x^8+4x^7+28x^6+412x^5+746x^4-2884x^3+1372x^2-1372x-2401)/ >(16x(x^6+6x^5+7x^4+84x^3-49x^2+294x-343)) > >and want to write polynome(u,v)=0 by eliminating x. >So p=x^8+...-u*8*x*(...) etc. and the resultant >is some number*(32u^4v-16u^4-...)^2. I conclude that >I can write y=(x^2+...)/(f*x^2+...) and u,v will be >rational functions of y too. How do I find y? I'm not quite sure I agree with everything you're saying here, but I think I can answer the final question. So you have two rational functions u(x) and v(x) and wish to find a rational function y(x) for which it is possible to express u = u' o y v = v' o y for some rational functions u' and v'. That is, you are looking for a common right-factor to u and v in the semigroup of all rational functions (where the product is composition). Of course one could take y to be any invertible element in this semigroup, that is, you could take y to be a Moebius transformation, but I expect you mean you want a nontrivial factorization. Indeed, you have suggested taking y to be a quotient of quadratics. I'd like to point out first that this is essentially the only way to factorize your u and v. Define the _degree_ of a rational function to be the maximum of the degrees of its numerator and denominator. It's easily seen to be the same as the degree of that function viewed topologically as a map f: S^2 -> S^2, that is, it's the cardinality of the inverse image of a generic point (here S^2 is the Riemann sphere). Since your u and v are of degree 8, and since degree of composites multiply, the only nontrivial factorizations u = u' o y which would be possible would have {degree u', degree y} = {2,4}. Next let me observe that given any factorization one could adjust it to u = (u' o h^(-1)) o (h o y) where h is any unit, i.e., any Moebius transformation. If we had such a factorization, then, we could choose h to send y(0) to 0, y(1) to 1, and y(\infty) to \infty, so that y can be assumed to have the simpler forms y = x ( 1 + a(x-1) )/( 1 + b(x-1) ). (One must be careful here: such an h can be found assuming y(0), y(1), and y(\infty) are distinct. The exceptional cases can likewise be reduced to the special forms y = x(x-1)/(x-a), x/(x-1)/(x-a), or (x-1)/x/(x-a).) Thus in general if you wish to factor a rational function you can reduce the size of your search by normalizing the choices. Next I will show how to identify possible factors. Consider the effect of a composite u = u' o y on the Riemann sphere. As I noted, the inverse images of most points under this map will have 8 points, as can be seen by clearing denominators in the equation u(x) = c. There are values of c for which u^(-1)(c) has fewer points; these require that the previous polynomial equation have a common solution with its derivative. Eliminating x from this equation shows precisely which values of c are singular: these c's are the roots of a certain degree-8 rational polynomial. (Actually it's a polynomial in c^2, and has (c^2-625/56) as a factor). Eliminating c between this equation and u(x)=c gives a necessary condition on x that it be a singular point; another condition comes from eliminating c from the derivative. The GCD of these equations is then the minimal polynomial of the singular points: it factors as (x^2+14x-7)* (x^12 -6 x^11 + ... 117649). Computing roots gives the singular points: -14.483, -3.72, -0.693, 0.4833, 1.88, 10.09, -1.88 +- 5.46 I, -1.26 +- 1.70I, .395+- 1.145 I, 1.97+-2.66I Now, the point of all this computation is that the degree-2 map y _also_ has two singular points, which it must share with any composite u' o y. Moreover, the other singular points of u should be the points y^(-1)(y0),where y0 is one of the singular points of u'. Suppose for example there was a factor of the form y(x)=x(x-1)/(x-a). Its two singular points must be among the singular points listed above. For each of the 14 values of x listed above, we can determine what a must be. As it turns out, each of the values of x yields a different a (contradicting the statement that _both_ critical points of y(x) are to be on the above list) unless a=-7; thus this is the only possible choice for a factor. Checking further, we see that the other 12 points x fall into pairs for which x(x-1)/(x+7) has the same value. Thus this function y(x) passes the critical-point test. Indeed, we then eliminate x from the equations u(x)=u and y(x)=y, we find that 2 3 4 1 + 4 y + 22 y + 4 y + y u = --------------------------- 8 y (y - 1) (y + 1) so that, yes, u does have y as a factor in this semigroup. Now, you had hoped to find a _common_ factor with v. As luck would have it, one can similarly eliminate x from the defining formula for v and deduce 2 2 (y + 6 y + 1) (y - 6 y + 1) y = - ----------------------------- 2 16 y (y + 1) Thus a choice for the substitution you seek is y(x) = x (x+1) / (x+7). Notice that the method I have proposed for finding a common factor of two rational functions requires actually factoring one of them first. By comparison with the factorization in Euclidean domains, one might hope for something quicker; I'm not sure how this would be possible, although it does save some time by reducing the collection of candidates for the singular points of y and so on. Surely someone has previously considered the question of factorization in this semigroup, but I have no idea where to find such algorithms. dave ============================================================================== To: rusin@vesuvius.math.niu.edu Subject: Re: On resultants Newsgroups: sci.math.research Date: Sat, 09 Nov 1996 10:07:37 -0500 From: MCKAY john Nice analysis: Have a look at a paper of mine: Ideal decompositions and subfields in Journal Symbolic Computation ? Spring 1996 and keep an eye out for another algorithm - faster - from Klu"ners and Pohst - to come out in the same journal soon. Also there is a paper by Hulpke in a recent ? Dec 1994 ? issue of Experimental Mathematics. You can email him: klueners@math.tu-berlin.de for a copy. Best, John McKay -- Deep ideas are simple. Odd groups are even. Even simples are not; and Gal/F2(t)(x^24-x-t) = Mathieu group, M24.