Re: polredabs suggestion

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Oct 09, 2019 at 03:19:07PM +0100, J E Cremona wrote:
> I have just spent a month applying polredabs to about 7 million polynomials
> of degree up to 21, with 100% success even though some took a long time
> (and I could be patient).

And you did not find a bug ? Great!

> Each of these polynomials (monic and integral) defines an extension of Q
> which I know to be unramified at primes > 500000 (these are the fields over
> which the torsion of an elliptic curve in my database acquires extra
> torsion, and were supplied by Enrique Gonzalez and Filip Najman), so I was
> able to help the process by dividing out from the polynomial discriminant
> all small primes, seeing that the quotient was a square, and taking its
> square root before factoring it (to give the factors to polredabs).

You can also try polredabs ([P,500000])

> But now although I have all the polredabs-ed polynomials (in about 92.5% of
> the cases the original polynomial was returned, in 7.5% of cases a new
> polynomial was returned), we want to add some or all of the fields to the
> LMFDB which will require doing many more computations with these number
> fields, starting with finding the maximal order.  It seems a pity that
> polredabs() has laready computed the maximal order and the field
> discriminant, but that has been discarded -- as far as I can tell there is
> no option to polredabs() to return anything other than the new polynomial
> and an expression giving its root in terms of the original (or vice
> versa).  And the integral basis for the field -- but not the factored
> discriminant.

Yes but it has computed it in the unreduced basis. So to get it in the
reduced basis, one need to compute the basis change (polredabs(...,1)
and apply it to the unreduced basis, which is usually more costly than
recomputing the integral basis from scratch, at least when polredabs
significantly reduce the polynomial.

> Please can we have an option to polredabs to return more?  At least: the
> output polynomial's factored discriminant.

You need to work backward! First compute the integral basis using
nfbasis and give the result to polredabs

B=nfbasis(P);
D=nfdisc([P,Q]);
Q=polredabs([P,B]);
So you get both Q B, and D.

> PS degree 16 was by far the worst

The main practical limitation of polredabs is not so much finding
short vectors, but the need to test all the short vectors to
find the best polynomial.
There are algebraic lattices with millions of short vectors in dim 16.

Cheers
Bill.