Re: polredabs failure

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

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.

So, in fact, polredabs output only depends on the underlying field, not on the
initial polynomial anymore [ provided the field discriminant can be factored.
If the maximal order can't be computed nothing can be said ].

So one gets a completely canonical defining polynomial now !

So in the case where disc(p1) and disc(p2) can be factored,
nfisisom(p1, p2) can be emulated by polredabs(p1) == polredabs(p2)

> I have another regression caused by this change:
>
> ? polredabs(x^32+12*x^30+72*x^28-1812*x^26+13982*x^24-46404*x^22+78120*x^20-5868*x^18-71487*x^16+11736*x^14+312480*x^12+371232*x^10+223712*x^8+57984*x^6+4608*x^4-1536*x^2+256)
>   ***   bug in GP (Segmentation Fault), please report

GC was very delicate indeed. Fixed.

Cheers,

    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]