Karim Belabas on Thu, 24 Jan 2013 10:20:22 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
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] `