Re: polgalois()

[Igor Schein <igor@txc.com>]

On Thu, Jan 28, 1999 at 02:22:39PM -0500, Igor Schein wrote:
> On Tue, Jan 26, 1999 at 11:55:39AM -0500, Igor Schein wrote:
> > Hi,
> > 
> > polgalois(x^11+2) runs forever.  I haven't had patience to see if it'd
> > ever finish.  Is it expectable?
> > 
> > Thanks
> > 
> > Igor
> 
> Looks like it might finish after a very long time ( at least 2
> Ultra-60 CPU days, according to a very rough estimate ). 
> 
> Indeed, here's the loop:
> 
> galois.c:862:          for (nocos=1; nocos<=nbcos; nocos++)
> 
> For 11-degree polynomial nbcos is 11!, which is ~400M.
> 
> So it's one loooong loop.
> 
> polgalois() never gets inside this loop of all other polynomials I
> tried, including degree-8,9,10 and degree-11 polynomials.  So it's
> either a bug or bad coding.  For comparison, I tried an equivalent
> of polgalois() in GAP software, and it came back with an answer in a
> short time.
> 
> Igor

I thought I should follow up on this one.  There're a total of 8
Galois groups for degree-11 polynomials.  Juergen Klueren provided me
with representatives for each of them.  If you exclude A_11 and S_11,
there're 6 remaining.  4 of them are EVEN groups.  For those, the loop
above goes to nocos=2500, so the answer takes less than 20s on
Ultra-60.  The other 2 are the ones where PARI fails to give an answer
in reasonable time.  One has representatives of form x^11+k, where
abs(k)>1.  This is my original observation.  The other one is
represented by
p=x^11 - x^10 + 5*x^9 - 4*x^8 + 10*x^7 - 6*x^6 + 11*x^5 - 7*x^4 +\
9*x^3 - 4*x^2 + 2*x + 1;

nocos goes way beyond 2500.  It might not go all the way to 11!, like
I originally thought, but still...

Any ideas why PARI stumbles on ODD groups in particular?

Igor