Opened 9 years ago
Closed 8 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: |
Description (last modified by )
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)
Change History (12)
comment:1 Changed 9 years ago by
- Cc malb added
comment:2 Changed 9 years ago by
- Summary changed from resultant over GF(2)[t][x] is plain wrong!!! to resultant over GF(q)[t][x] is plain wrong!!!
comment:3 Changed 9 years ago by
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
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
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
- 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 8 years ago by
- 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 ofpolynomial_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 8 years ago by
- Status changed from new to needs_review
Changed 8 years ago by
comment:9 Changed 8 years ago by
- 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 8 years ago by
- Milestone changed from sage-5.6 to sage-5.7
comment:11 Changed 8 years ago by
- Merged in set to sage-5.7.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
with the modified
check
routine below: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