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.