Resultant for nonexact fields

[alexjbest]

Can anything be done to make the following work?

julia> using AbstractAlgebra, Nemo

Welcome to Nemo version 0.22.0

Nemo comes with absolutely no warranty whatsoever

julia> R,x= PolynomialRing(PadicField(853,2),"x")
(Univariate Polynomial Ring in x over Field of 853-adic numbers, x)

julia> discriminant(4*x^5 + x^4 + 256*x^3 + 192*x^2 + 48*x + 4)
O(853^2)

It seems this happens because there are two versions of resultant, one for rings which takes resultant_sylvester for inexact rings, and one for fields which tries resultant_euclidean, if the version for fields always used sylvester might that fix this?

julia> using AbstractAlgebra, Nemo

Welcome to Nemo version 0.22.0

Nemo comes with absolutely no warranty whatsoever

julia> R,x= PolynomialRing(PadicField(853,2),"x")
(Univariate Polynomial Ring in x over Field of 853-adic numbers, x)

julia> a = (4*x^5 + x^4 + 256*x^3 + 192*x^2 + 48*x + 4)
(4*853^0 + O(853^2))*x^5 + x^4 + (256*853^0 + O(853^2))*x^3 + (192*853^0 + O(853^2))*x^2 + (48*853^0 + O(853^2))*x +
4*853^0 + O(853^2)

julia>    d = derivative(a)
(20*853^0 + O(853^2))*x^4 + (4*853^0 + O(853^2))*x^3 + (768*853^0 + O(853^2))*x^2 + (384*853^0 + O(853^2))*x + 48*853
^0 + O(853^2)

julia> resultant_sylvester(d,a)
811*853^0 + 728*853^1 + O(853^2)

julia> resultant_euclidean(d,a)
O(853^2)

[fieker]

On Sat, Mar 27, 2021 at 04:59:16PM -0700, Alex J Best wrote:

Can anything be done to make the following work? Yes/no/maybe:

• the reason this fails is

  julia> Qx, x = QQ["x"]
  julia> a = (4*x^5 + x^4 + 256*x^3 + 192*x^2 + 48*x + 4)
  julia> divrem(a, derivative(a))
  julia> factor(fmpz(2559))
  1 * 853 * 3

So in the polynomial remainder sequence we need to divide by 853 - it is a bad prime.

• Options (in Hecke)

  julia> R,x= PolynomialRing(MaximalOrder(PadicField(853,2)),"x")
  julia> a = (4*x^5 + x^4 + 256*x^3 + 192*x^2 + 48*x + 4)
  julia> discriminant(a)
  416*853^0 + 395*853^1 + O(853^2)

  using a different method altogether...

  in Nemo: increase the precision of the input

unfortunately, this is a hard problem

• resultants and gcds in general over imprecise rings
• algorithm selection in the generic. Here we'd probably best using the euc version as p-adic intergers are euclidean (and move to the ring is possible) For the reals this is not good....

julia> using AbstractAlgebra, Nemo

Welcome to Nemo version 0.22.0

Nemo comes with absolutely no warranty whatsoever

julia> R,x= PolynomialRing(PadicField(853,2),"x")
(Univariate Polynomial Ring in x over Field of 853-adic numbers, x)

julia> discriminant(4*x^5 + x^4 + 256*x^3 + 192*x^2 + 48*x + 4)
O(853^2)

It seems this happens because there are two versions of resultant, one for rings which takes resultant_sylvester for inexact rings, and one for fields which tries resultant_euclidean, if the version for fields always used sylvester might that fix this?

julia> using AbstractAlgebra, Nemo

Welcome to Nemo version 0.22.0

Nemo comes with absolutely no warranty whatsoever

julia> R,x= PolynomialRing(PadicField(853,2),"x")
(Univariate Polynomial Ring in x over Field of 853-adic numbers, x)

julia> a = (4*x^5 + x^4 + 256*x^3 + 192*x^2 + 48*x + 4)
(4*853^0 + O(853^2))*x^5 + x^4 + (256*853^0 + O(853^2))*x^3 + (192*853^0 + O(853^2))*x^2 + (48*853^0 + O(853^2))*x +
4*853^0 + O(853^2)

julia>    d = derivative(a)
(20*853^0 + O(853^2))*x^4 + (4*853^0 + O(853^2))*x^3 + (768*853^0 + O(853^2))*x^2 + (384*853^0 + O(853^2))*x + 48*853
^0 + O(853^2)

julia> resultant_sylvester(d,a)
811*853^0 + 728*853^1 + O(853^2)

julia> resultant_euclidean(d,a)
O(853^2)

-- You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/issues/827

[wbhart]

The resultant_sylvester has substantially worse complexity than the other algorithm. It is pretty unfortunate that it is the only one which has good "numerical" behaviour for padics.

It would be possible to have a special method just for resultant over the padics which just calls resultant_sylvester though.

I'm sure there is a better algorithm entirely, in Hecke though.

[fieker]

On Mon, Mar 29, 2021 at 02:03:56AM -0700, wbhart wrote:

The resultant_sylvester has substantially worse complexity than the other algorithm. It is pretty unfortunate that it is the only one which has good "numerical" behaviour for padics.

It would be possible to have a special method just for resultant over the padics which just calls resultant_sylvester though.

I'm sure there is a better algorithm entirely, in Hecke though.

The famous Sircana-Resultant algorithm.... TODO: implement it carefully in Flint... -- You are receiving this because you commented. Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/issues/827#issuecomment-809207041

[alexjbest]

Thanks to you both, I can use Hecke for now (over the ring of integers, which is what I was missing!)

This definitely sounds like a tricky problem to get something generic.

And yes sorry I didn't mean to suggest always using Sylvester! Just for the padics, but I don't know what the way to test if a ring is the padics in AbstractAlgebra would be.

[wbhart]

The method would have to be added to Nemo. It's just a method, so it would replace the generic method for that ring.