resultant over GF(q)[t][x] is plain wrong!!!

[zimmermann6]

Consider the following:

sage: R.<t> = GF(2)[]; S.<x> = R[]
sage: f=(t^2 + t)*x + t^2 + t; g=(t + 1)*x + t^2
sage: f.resultant(g)
t^3 + t

This is wrong: the resultant of f and g is t^4+t.

Plenty of failures can be found with the following code which computes the resultant as the determinant of the Sylvester matrix:

def Resultant(f,g):
   df = f.degree()
   dg = g.degree()
   K = f.base_ring()
   M = matrix(K,df+dg,df+dg)
   for i in range(dg):
      for j in range(df+1):
         M[i,i+j] = f.coeffs()[df-j]
   for i in range(df):
      for j in range(dg+1):
         M[dg+i,i+j] = g.coeffs()[dg-j]
   return M.det()

def check(df,dg):
   f = S.random_element(degree=df)
   g = S.random_element(degree=dg)
   r1 = f.resultant(g)
   r2 = Resultant(f,g)
   if r1 <> r2:
      print f, g, r1, r2
      raise ValueError

Apply 13672_pari_resultant.patch

CC: @JohnCremona @williamstein @malb @robertwb @miguelmarco @simon-king-jena @saraedum

Component: commutative algebra

Author: Jeroen Demeyer

Reviewer: Paul Zimmermann

Merged: sage-5.7.beta0

Issue created by migration from https://trac.sagemath.org/ticket/13672

[zimmermann6]

comment:2

with the modified check routine below:

def check(df,dg,S):
   f = S.random_element(degree=df)
   while f.degree() < df:
      f = S.random_element(degree=df)
   g = S.random_element(degree=dg)
   while g.degree() < dg:
      g = S.random_element(degree=dg)
   r1 = f.resultant(g)
   r2 = Resultant(f,g)
   return r1 == r2

def foo(df,dg,F,K):
   R.<t> = F[]
   S.<x> = R[]
   err = 0
   for k in range(K):
      if check(df,dg,S) == False:
         err += 1
   return err

then foo(1,1,GF(2),1000) gives 788 failures out of 1000 tries, with GF(3) I get 969
errors out of 1000, with GF(11) 1000 errors. Thus all finite fields are concerned.

Paul

[malb]

comment:3

This seems to be a bug in Pari or our conversion to Pari:

sage: R.<t> = GF(2)[]; S.<x> = R[]
sage: f=(t^2 + t)*x + t^2 + t; g=(t + 1)*x + t^2
sage: f.resultant(g)
t^3 + t
sage: f._pari_().polresultant(g._pari_(), x._pari_(), 0)              
Mod(1, 2)*x^3 + Mod(1, 2)*x

sage: Q = PolynomialRing(GF(2), f.parent().variable_names_recursive())
sage: Q(f).resultant(Q(g),variable=Q(x))
t^4 + t

Note that resultant() has this logic:

variable = self.parent().gen()
if str(variable)<>'x' and self.parent()._mpoly_base_ring()<>self.parent().base_ring():
    # use multivariate instead

and this works:

sage: R.<t> = GF(2)[]; S.<y> = R[]
sage: f=(t^2 + t)*y + t^2 + t; g=(t + 1)*y + t^2
sage: f.resultant(g)
t^4 + t

I don't understand why this str(variable)<>'x' check is there.

[zimmermann6]

comment:4

Martin, indeed the documentation says that x is special:

sage: f.resultant?
...
       We can also compute resultants over univariate and multivariate
       polynomial rings, provided that PARI's variable ordering
       requirements are respected. Usually, your resultants will work if
       you always ask for them in the variable "x":

In the contrary it seems that using x as main variable gives wrong resultants...

Paul

[malb]

comment:5

Paul,

I guess that means we should ask on [sage-devel] whether anyone objects to using Singular always in this case? Or even better to explain why Pari fails here (?)

[zimmermann6]

comment:6

Martin, it would be better to understand why x is special first. I'll add the authors of
polynomial_element.pyx in cc.

Paul

[jdemeyer]

comment:7

Replying to @zimmermann6:

Martin, it would be better to understand why x is special first. I'll add the authors of
polynomial_element.pyx in cc.

x is special because PARI has a concept of "variable" priority, where x has highest priority.

But it seems that PARI/GP can compute resultants w.r.t. a different variable:

gp> ?polresultant
polresultant(x,y,{v},{flag=0}): resultant of the polynomials x and y, with respect to the main variables of x and y if v is omitted, with
respect to the variable v otherwise. flag is optional, and can be 0: default, uses either the subresultant algorithm, a modular algorithm
or Sylvester's matrix, depending on the inputs; 1 uses Sylvester's matrix (should always be slower than the default).

[jdemeyer]

Author: Jeroen Demeyer

[jdemeyer]

Attachment: 13672_pari_resultant.patch.gz

[zimmermann6]

comment:9

thank you Jeroen for fixing this!

Paul

[zimmermann6]

Reviewer: Paul Zimmermann

[jdemeyer]

Merged: sage-5.7.beta0