Re: polredabs failure

[Igor Schein <igor@txc.com>]

On Mon, Oct 13, 2003 at 05:42:38PM +0200, Karim BELABAS wrote:
> On Sun, 12 Oct 2003, Igor Schein wrote:
> > On Fri, Oct 10, 2003 at 08:08:00PM +0200, Karim BELABAS wrote:
> >> On Fri, 10 Oct 2003, Igor Schein wrote:
> > Latest changes broke it again:
> >
> > ? p=x^16-4*x^15+8*x^14-8*x^13+6*x^12-16*x^11+40*x^10-32*x^9-50*x^8+160*x^7-176*x^6+40*x^5+140*x^4-192*x^3+112*x^2-32*x+4;
> > ? v=polredabs(p,4);
> > ? vector(#v,k,#polredabs(v[k],4))
> > [22, 21, 24, 24, 24, 20, 24, 12, 20, 12, 20, 24]
> >
> > The correct answer is vector(24,x,24).
> 
> Couldn't reproduce this, since I had changed it again in the meantime... I
> rewrote the whole thing according to an age-old project of mine: enumerating
> points by (roughly) increasing norms. I did not try to be efficient, this
> time, only to get it right.

I don't know if it's too early to talk about efficiency yet, but for
the following polynomial

{
x^32 + 160*x^30 + 10592*x^28 + 380240*x^26 + 8223880*x^24 + 113613696*x^22 +
 1038843456*x^20 + 6414739680*x^18 + 26951021784*x^16 + 76644143232*x^14 + 1
44482787456*x^12 + 172572281280*x^10 + 118940935456*x^8 + 37693530112*x^6 + 
1869026048*x^4 + 31222400*x^2 + 169744
}

polredabs has slowed down considerable - used to take only 8s, now it
takes 40s if I start with at least 8MB stack, and much longer if I
start with 32bit-default 4MB stack - operating on a low stack with a
lot of GC?

> 
> It should fix long standing problems in small dimension like
> 
>   x^8-97418273277417164826810*x^4-97418273278115084139045*x^2
>   +97418273278115084139045
> 
> or
>   x^4+946461962680424656489*x^2+946461962680424656489
> 
> which ran forever. On the other hand, it won't help for polynomials of huge
> degrees with lots of subfields, if we're unlucky with the initial basis
> ordering. Especially when the fields contain lots of roots of 1. Like
> 
>   polcompositum(x^12-2*x^9+2*x^6+2*x^3+1, polsubcyclo(9,3))[1]
> 
> (in dimension 36). Just to see why, have a look at \g5, you'll see the
> (many) vectors of small L^2 norm that are being enumerated, but unfortunately
> do not generate the field. I do not see any obvious structure that would
> enable me to prune this. Essentially, as soon as one (small) generator is
> found, the show is over; but till then...
> 
> For these guys, you simply _have_ to use polred. One could time the polredabs
> run and abort it after some point, but since we simply do not find any
> generator, it is all a waste of time.
> 
> Igor, any glitches with the new algorithm ?

The testsuite runs OK, and I haven't found any new *fatal* cases this
far.  It's great to see the above bugs fixed.

Thanks

Igor