Re: polredabs failure

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

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]