Bug in Hilbert series computation

[simon-king-jena]

As reported on sage devel, there appear to be errors in the current default algorithm for the computation of Hilbert series/polynomials:

sage: P.<x,y,z> = PolynomialRing(QQ)
....: I = Ideal([x^3, x*y^2, y^4, x^2*y*z, y^3*z, x^2*z^2, x*y*z^2, x*z^3])
....: I.hilbert_polynomial()
....: 
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-1-8603fe52d058> in <module>()
      1 P = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
      2 I = Ideal([x**Integer(3), x*y**Integer(2), y**Integer(4), x**Integer(2)*y*z, y**Integer(3)*z, x**Integer(2)*z**Integer(2), x*y*z**Integer(2), x*z**Integer(3)])
----> 3 I.hilbert_polynomial()

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.pyc in __call__(self, *args, **kwds)
    295         if not R.base_ring().is_field():
    296             raise ValueError("Coefficient ring must be a field for function '%s'."%(self.f.__name__))
--> 297         return self.f(self._instance, *args, **kwds)
    298 
    299 require_field = RequireField

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.pyc in hilbert_polynomial(self, algorithm)
   2516             out = sum(c / denom * prod(s - 1 - n - nu + t for nu in range(s-1))
   2517                       for n,c in enumerate(second_hilbert)) + t.parent().zero()
-> 2518             assert out.leading_coefficient() >= 0
   2519             return out
   2520         elif algorithm == 'singular':

AssertionError: 

Singular can solve this example.

Component: algebra

Keywords: Hilbert polynomial

Author: Grayson Jorgenson

Branch/Commit: 37f3c75

Reviewer: Frédéric Chapoton

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

[simon-king-jena]

comment:1

After removing the assertion, I get

sage: P.<x,y,z> = PolynomialRing(QQ)
....: I = Ideal([x^3, x*y^2, y^4, x^2*y*z, y^3*z, x^2*z^2, x*y*z^2, x*z^3])
....: I.hilbert_polynomial(algorithm='singular')
....: 
3
sage: P.<x,y,z> = PolynomialRing(QQ)
....: I = Ideal([x^3, x*y^2, y^4, x^2*y*z, y^3*z, x^2*z^2, x*y*z^2, x*z^3])
....: I.hilbert_polynomial()
....: 
-3

So, for a reason that I do not understand yet, there is a negative count.

[vbraun]

comment:2

I think thats just because our numerator of the hilbert series is not normalized to be monic:

sage: P.ideal(x^2, x*y^2, y^2, z*x).hilbert_series()
(t^3 - 2*t - 1)/(t - 1)
sage: P.ideal(x^2, x*y^2, y^2).hilbert_series()
(t^2 + 2*t + 1)/(-t + 1)

[sagetrac-gjorgenson]

comment:3

I made an attempt at fixing this. If I understand correctly, the Sage algorithm for computing the Hilbert polynomial is working by expanding out the Hilbert series. Past the term of index the Hilbert regularity, the expression for the coefficients becomes the Hilbert polynomial. It seems the line managing the combinatorics of this expansion

sum(c / denom * prod(s - 1 - n - nu + t for nu in range(s-1)) for n,c in enumerate(second_hilbert))

is assuming the denominator of the series is of the form (1 - t)^s. I've added a check to ensure this is the case, scaling if needed. Note this issue was only a problem when the denominator of the series had odd degree.

---

New commits:

7938a74

28110: fix bug with Hilbert polynomial computation

[sagetrac-gjorgenson]

Author: Grayson Jorgenson

[sagetrac-gjorgenson]

Branch: u/gjorgenson/28110_hilbert_poly

[sagetrac-gjorgenson]

Commit: 7938a74

[fchapoton]

comment:4

no space after :trac:

[sagetrac-git]

Changed commit from 7938a74 to 37f3c75

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

37f3c75

28110: remove extra space

[fchapoton]

comment:6

ok, then

[fchapoton]

Reviewer: Frédéric Chapoton

[vbraun]

Changed branch from u/gjorgenson/28110_hilbert_poly to 37f3c75