Karim Belabas on Thu, 24 Jan 2013 10:20:22 +0100

 Re: Field inclusion problem

```* Ewan Delanoy [2013-01-24 09:28]:
> Hello all,
>
>  I would like to have the PARI-GP expertsâs advice about the feasibility of the following computation.
>  I have two polynomials A and B, given below, with A of degree 9 and B of degree 72. I know that if b is a root of B, then Q(b) is the decomposition field of A, so that there are three polynomials A_1,A_2,A_3 in b, each of degree at most 72, such that A factorizes as (X-A1(b))(X-A2(b))(X-A3(b)).

I don't understand what "X" is, if A has degree 9 :-)

>  The goal is to compute exactly the (ugly & complicated) coefficients
>  of A1,A2,A3. Would that be considered a reasonable computation in
>  PARi-GP ?

Quite a simple computation in principle (e.g. definitely polynomial time).

> Perhaps there are other methods than using lindep ?

nffactor(B, A) would factor A(X) over the number field Q[b] / (B(b)).

( a few seconds on such small inputs )

Unfortunately, it seems the result is irreducible in this case. So either
- we have a bug in PARI; it would not be the first one in this area: non
monic defining polynomials are hardly ever tested.

- or there's a mistake in your input.

>  Note that the B polynomial is quite complicated, Iâd be quite happy
>  to replace it with a simpler polynomial that still corresponds to the
>  decomposition field of A.

In principle

B = polredbest(B);

This is more complicated than just nffactor above, a few hours in this
case and you'll probably get no improvement. It might be better to start
from T = polredbest(A) [ will be monic ], and iterate polcompositum(T,T)
and polredbest() to obtain a "simple" (monic) polynomial.

Cheers,

K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`

```