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.