Re: polredabs failure

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

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.

> Also...
> ? #polredabs(%1,4)
> %4 = 13
> ? #polredabs(%2,4)
> %5 = 22
> ? #polredabs(%3,4)
> %6 = 24
>
> What is causing discrepancy between the last 3 results, precision
> issues or probabilistic nature of algorithm?

The algorithm is not probabilistic, but changing the input yields a priori
different behaviour. What exactly occurs is that a fixed number of vectors of
minimal norm are stored, the rest being discarded. Since many of them have
the same characteristic polynomial, it may occur that some polynomial is not
represented in the end.

This does not follow the documented behaviour of the (,4) flag, and is rather
pointless. I have made the above buffersize dynamic, so that no minimal vector
should ever be discarded [ in polredabs. It's too dangerous in a general
situation... ]

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]