Bill Allombert on Fri, 21 May 2004 21:11:53 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: galoisinit() bug |
On Fri, May 21, 2004 at 07:44:48PM +0200, Bill Allombert wrote: > 2.2.0 and 2.2.3 work, but not 2.2.1, 2.2.2, nor 2.2.4. > > I will try to understand what is going on, but luck is > the primary factor here. Sheer luck indeed: Version 2.2.3 has a typo (a missing cast in a macro call) that lead to the use of a smaller prime (p=5) that what we normally allow (the smaller the prime is, the lesser the chance of a polynomial being squarefree mod p). Without the typo we get p=13 which is higher, but unfortunately does not work. For those of you more interested by the math , here an explanation: You have a field L defined as the splitting field of P=x^4+272*x^3+40256*x^2+1740800*x+25397248. (In fact, L is the eightth cyclotomic field). Gal(L/Q)=(Z/2Z)^2. We compute sigma=(13|L/Q) the frobenius of 13, of order 2, and we want to compute L^sigma. For that purpose we embed L in Q_17. (Q_17 contains a 8th root of unity, so it is possible), and we compute approximations of the roots of P in Q_17 to a suitable accuracy, and we compute the orbit of sigma on those roots. We get 2 orbits O1={a1,a2=sigma(a1)} and O2={b1,b2=sigma(b1)}. Now we need to pick up a symmetrical polynomial of two indeterminate S so that S(a1,a2)!=S(b1,b2) (that must exists, else we would have O1=O2.) and compute the polynomial R=(X-S(a1,a2))*(X-S(b1,b2)). There, everything is fine. Now, to be able to proceed with the next step of the algorithm without undue burden, we need to impose 2 conditions on R, and hence on S: 1) R squarefree modulo 17 2) R squarefree modulo 13 Unfortunately here, for S=X+Y, 1) is false and for S=X^2+Y^2, 2) is false. So we fail. In fact S=X*Y would work, but the algorithm try only linear combinations of Newton polynomials, so X*Y is not tried. What I plan to do is to add X*Y to the list of symmetrical polynomials to consider. It is not a very good fix. Cheers Bill.