Opened 9 years ago

Closed 9 years 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 sage-5.7.beta0 Jeroen Demeyer Paul Zimmermann N/A

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`

### 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():
```

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: ↓ 7 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

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

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