Re: polredabs() again

[Igor Schein <igor@txc.com>]

On Fri, Apr 04, 2003 at 12:18:34AM +0200, Karim BELABAS wrote:
[deleted]
> On the other hand, the current specification of polredabs is quite useless.
> There's no application whatsoever for a "polynomial of absolute smallest
> T2-norm". It's not even guaranteed to have minimal discriminant, or to
> yield smallest coefficients. The only one I can see is to give a
> pseudo-canonical representative for the field (this helps table builders,
> less isomorphism tests...)

An appropriate observation.  Here's an example:

? p1=x^40-444796*x^30+91848351606*x^20-11536862712826396*x^10+672749994932560009201;
time = 0 ms.
? p2=polredabs(p1)
time = 10,160 ms.
%5 = x^40 - 45*x^38 + 1325*x^36 - 32390*x^34 + 714250*x^32 -
12409705*x^30 + 186413550*x^28 - 2499178250*x^26 + 29415089025*x^24 -
274143015750*x^22 + 2260522643650*x^20 - 16155295928625*x^18 +
89060060373750*x^16 - 251196632524250*x^14 + 670266070790625*x^12 -
1618446757085125*x^10 + 2840715854153125*x^8 - 389148315762500*x^6 +
53298286370000*x^4 - 7270708200000*x^2 + 922368160000 

Anybody in his right mind, I believe, would prefer p1 over p2 as a
representative for this field.  Yet, if you start with p2, there's no
way to obtain p1 using polredxxx() functions.  In fact, I have no
recollection how I was able to find p1 in the first place, it was a
few months back.  So as far as I'm concern, a *good* implementation of
polredabs() should be able to obtain p1 from p2 in the example above.   

> 
> In any case, there's an obvious solution: add a further optional argument to
> polredabs, to sample up to a certain recursion depth (e.g [N, B] would
> include at most N vectors in any linear combination, with coefficients < B in
> absolute value, or the standard computed bound, whichever is lowest). And
> return the best polynomial found [ possibly the original polynomial ]
> 
> Then, we'd have a guaranteed time limit on polredabs() operation,
> and a guarantee to get a "sensible" polynomial, if not a "canonical" one.

Yes, that's what I'm looking for.

Thanks

Igor