Dear Forum,

Lewis McCarthy asked:

I'm new to GAP (v3r4) and I have a couple of initial questions which I
haven't been able to answer with the manual thus far:

Unfortunately the manual is (yet) very short-spoken about these subjects,
particularly, since the part about algebraic extensions of fields is missing
(see my mail in the forum two weeks ago).

(1) Is there any built-in way to compute the resultant of two polynomials ?
Judging from the manual, there doesn't appear to be, but I just want to
make sure I haven't missed something. Otherwise I'll be coding my own.

There is a command 'Resultant' that computes the resultant of two
polynomials in the same polynomial ring by eliminating the indeterminate of
this ring. I.e.:

Resultant(f,g) is res_x(f(x),g(x)).

For computing resultants of multivariate polynomials, one can use iteraded
polynomial ring extensions, however (at the moment) the indeterminate to
eliminate must be the "topmost" indeterminate. Also computations in multiple
polynomial rings tend to be quite slow.

(2) What algorithms are used to factor polynomials over number fields in GAP ?

Since you asked this question, I suppose, you are familiar with the
algorithms. Therefore I will keep this description rather short. Feel free
to contaxct me personally, if you have further questions, that might be too
special for the general audience.

Let f be the minimal polynomial for the number field Q(alpha) and g\in
Q(alpha)[x] the polynomial to factor.
If deg f<=4 and degf*deg g<=20, then Trager's method will be used
(factoring the norm).
otherwise a Hensel approach is used. For tehse, the methods of Weinberger
and Lenstra (the '82 article which is in practice preferable to the method
suggested in the '83 article though theoretical complexity bounds might tell
something else) are used:
If a prime can be found (so far, 6 proimes are tested), modulo which f
remains irreducible, then Weinberger's method is used.
If not, and the coefficients coefficient bound is less then 10^400, then
Lenstras Approach is used. However, if coefficients become even larger, then
the LLL will choke on the coefficients (note that Lenstra requires a
significant higher bound than ~Weinberger); so Weinbergers methos is used
then again (i.e. simultaneous Henmsel lifting for all factors of f and final
recombination by Chinese Remainder methods).
I have not yet found much references in the literature about how to decide,
which methods to use (or how many primes to check). As computations become
extremely hard if f will split for al primes it is possibly worth event to
try to compute the galois group of f partially to see, whether there is a
chance to find a prime, modulo which f will remain irreducible.
Th heuristics are based on observations I made with polynomial
factorizations needed for identification of galois groups. Those
factorizations seem to be quite nasty in general, thus I think the algorithm
used should not perform too worse, however I have not yet made sufficient
observations to give even a hint, whether these heuristics are well chosen.
If you have specific problems on which GAPs algorithmm fails, I can send you
some further internal information on how to change the algorithm selection.

This text has been written over a rather slow telnet line, so please excuse
any typos.

Thanks for your help

You're welcome.

Alexander Hulpke

-- Lehrstuhl D fuer Mathematik, RWTH, Templergraben 64, 52056 Aachen, Germany,
eMail: Alexander.Hulpke@math.rwth-aachen.de