Bug in discriminant of polynomials over Z/nZ with n composite

[sagetrac-johanbosman]

The following behaviour is inconsistent:

sage: f = ZZ[x](2*x^3 + x^2 + x)
sage: f.discriminant()
-7
sage: GF(3)[x](f).discriminant()
2
sage: ZZ.quo(9)[x](f).discriminant()
0

And the following raises an error:

sage: ZZ.quo(9)[x](3*x^2 + 3*x + 3).discriminant()
...
ZeroDivisionError: Inverse does not exist.

---

Apply

1. attachment: 11782_use_sylvester.patch
2. attachment: 11782_review.patch

to the Sage library.

Component: algebra

Keywords: polynomial, discriminant, integer mod ring

Author: Johan Bosman

Reviewer: Julian Rueth

Merged: sage-4.8.alpha4

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

[sagetrac-johanbosman]

comment:1

The first problem is caused by the fact that FLINT doesn't compute resultants correctly. This is also mentioned in FLINT's documentation: see p. 58 of http://www.flintlib.org/flint-1.6.pdf: n must be prime to compute resultants correctly.

The second problem is of course caused by the fact that the leading coefficient is a zero divisor.

[sagetrac-johanbosman]

Attachment: 11782_use_sylvester.patch.gz

[saraedum]

comment:3

The docstring of discriminant() says

           Uses the identity `R_n(f) := (-1)^(n (n-1)/2) R(f,
           f') a_n^(n-k-2)`, where `n` is the degree of self,
           `a_n` is the leading coefficient of self, `f'`
           is the derivative of `f`, and `k` is the degree
           of `f'`.

So is it correct that if a_n is not invertible this should read

a_n^(2+k-n) R_n(f) = (-1)^(n (n-1)/2) R(f,f')

If I understand your patch correctly, you're assuming 2+k-n=1 in the lines

            mat[0, 0] = self.base_ring()(1)
            mat[n - 1, 0] = self.base_ring()(n)

since you're only dividing by a_n. But k could be different from n-1.

I don't know much about discriminants/resultants, especially if the polynomials are defined over rings with zerodivisors. So maybe I'm just misunderstanding the definition/implementation here.

[sagetrac-johanbosman]

comment:4

That code is reached whenever 

an = self[n]**(n - k - 2)

raises a ZeroDivisionError, which means n-k-2 < 0 thus n-k <= 1 (and thus n-1 <= k).
Now, since k is the degree of the derivative of f and n is the degree of f, we have k <= n-1. This two inequalities together yield k = n-1. ;).

[sagetrac-johanbosman]

Author: Johan Bosman

[sagetrac-johanbosman]

comment:5

"This" => "These" in the last sentence (is it possible to edit your own comments?)

[saraedum]

comment:6

I see. I had assumed that the catch block was a full alternative implementation of the try block. You're of course right, it doesn't have to be.

[saraedum]

comment:7

I'm a bit unhappy with catching a ZeroDivisionError. The error could be raised in the self.resultant(d) call and would then be silently ignored — and the result could be wrong in that case. So I made the check more explicit in my review patch.

Also I added some comments and an explicit test to the flint polynomials.

If you don't mind these changes, feel free to set it to positive review.

[saraedum]

Reviewer: Julian Rueth

[sagetrac-johanbosman]

comment:8

If a_n is not a unit, but also not a zero divisor, it still makes sense to invert it, so your "if" condition is too strict.

What do you think about the following solution?

try:         
    an = self[n]**(n - k - 2) 
except ZeroDivisionError: 
    mat = self.sylvester_matrix(d)            
    mat[0, 0] = self.base_ring()(1)
    mat[n - 1, 0] = self.base_ring()(n)
    return u * mat.determinant()
else:
    return self.base_ring()(u * self.resultant(d) * an)

[saraedum]

Attachment: 11782_review.patch.gz

review patch

[saraedum]

comment:9

You're right. I tried to follow your suggestion in the new review patch.

[sagetrac-johanbosman]

comment:10

Okäse!

[jdemeyer]

Merged: sage-4.8.alpha4