Karim BELABAS on Mon, 13 Oct 2003 17:42:38 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polredabs failure |
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: >>> On Fri, Oct 10, 2003 at 05:46:04PM +0200, Karim BELABAS wrote: >>>> On Thu, 9 Oct 2003, Igor Schein wrote: >>>>> Now, continuing the same topic: >>>>> >>>>> %1 = 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 >>>>> ? polredabs(%) >>>>> %2 = x^16 - 4*x^15 + 12*x^14 - 36*x^13 + 88*x^12 - 164*x^11 + 252*x^10 - 324*x^9 + 354*x^8 - 324*x^7 + 252*x^6 - 164*x^5 + 88*x^4 - 36*x^3 + 12*x^2 - 4*x + 1 >>>>> ? polredabs(%) >>>>> %3 = x^16 - 8*x^15 + 36*x^14 - 108*x^13 + 244*x^12 - 436*x^11 + 636*x^10 - 780*x^9 + 831*x^8 - 780*x^7 + 636*x^6 - 436*x^5 + 244*x^4 - 108*x^3 + 36*x^2 - 8*x + 1 >>>>> \\ Takes 2 iterations to stabilize >>>> >>>> These polynomials have the same norm. All are valid results, and there's no >>>> guarantee that iterating polredabs as above stabilizes at all. >>> >>> But now, after the change mentioned below, it indeed *stabilizes* >>> after 1 interation. And I suspect it won't be easy to find another >>> example of behavior above - I couldn't so far. >> >> Now it shouldn't be possible at all. After my change no minimal vector is >> ever discarded, and their characteristic polynomials are sorted so as to >> remove duplicates. > > 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. 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 ? Karim. -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathématiques, Bât. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud http://www.math.u-psud.fr/~belabas/ F-91405 Orsay (France) http://www.parigp-home.de/ [PARI/GP]