Opened 9 years ago

Closed 9 years ago

#13672 closed defect (fixed)

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

Reported by: zimmerma Owned by: malb
Priority: critical Milestone: sage-5.7
Component: commutative algebra Keywords:
Cc: cremona, wstein, malb, robertwb, mmarco, SimonKing, saraedum Merged in: sage-5.7.beta0
Authors: Jeroen Demeyer Reviewers: Paul Zimmermann
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by zimmerma)

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

Attachments (1)

13672_pari_resultant.patch (2.7 KB) - added by jdemeyer 9 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 9 years ago by zimmerma

  • Cc malb added

comment:2 Changed 9 years ago by zimmerma

  • Summary changed from resultant over GF(2)[t][x] is plain wrong!!! to resultant over GF(q)[t][x] is plain wrong!!!

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

comment:3 Changed 9 years ago by malb

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.

comment:4 Changed 9 years ago by zimmerma

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

comment:5 Changed 9 years ago by malb

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 (?)

comment:6 follow-up: Changed 9 years ago by zimmerma

  • Cc robertwb mmarco SimonKing saraedum added

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

Paul

comment:7 in reply to: ↑ 6 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.5 to sage-5.6
  • Priority changed from blocker to critical

Replying to zimmerma:

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).

comment:8 Changed 9 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Status changed from new to needs_review

Changed 9 years ago by jdemeyer

comment:9 Changed 9 years ago by zimmerma

  • Description modified (diff)
  • Reviewers set to Paul Zimmermann
  • Status changed from needs_review to positive_review

thank you Jeroen for fixing this!

Paul

comment:10 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.6 to sage-5.7

comment:11 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.7.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.