# Ticket #13672(closed defect: fixed)

Opened 7 months ago

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

Reported by: Owned by: zimmerma malb critical sage-5.7 commutative algebra cremona, wstein, malb, robertwb, mmarco, SimonKing, saraedum N/A Paul Zimmermann Jeroen Demeyer sage-5.7.beta0

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

## Change History

### comment:2 Changed 7 months 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 7 months 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():
```

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 7 months 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 7 months 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: ↓ 7 Changed 7 months 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 6 months ago by jdemeyer

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

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 4 months ago by jdemeyer

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

### comment:9 Changed 4 months ago by zimmerma

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

thank you Jeroen for fixing this!

Paul

### comment:10 Changed 4 months ago by jdemeyer

• Milestone changed from sage-5.6 to sage-5.7

### comment:11 Changed 4 months ago by jdemeyer

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