Igor Schein on Thu, 3 Apr 2003 17:44:24 -0500 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polredabs() again |
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