Igor Schein on Sun, 12 Oct 2003 15:07:00 -0400


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: polredabs failure


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).

Thanks

Igor