Opened 3 years ago

Closed 3 years ago

#28110 closed defect (fixed)

Bug in Hilbert series computation

Reported by: Simon King Owned by:
Priority: major Milestone: sage-8.9
Component: algebra Keywords: Hilbert polynomial
Cc: Merged in:
Authors: Grayson Jorgenson Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 37f3c75 (Commits, GitHub, GitLab) Commit: 37f3c75798a21b096e49b3756529457dd62f9e45
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (7)

comment:1 Changed 3 years ago by Simon King

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.

comment:2 Changed 3 years ago by Volker Braun

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)

comment:3 Changed 3 years ago by Grayson Jorgenson

Authors: Grayson Jorgenson
Branch: u/gjorgenson/28110_hilbert_poly
Commit: 7938a7413243b208ba7f6370806a202d512cd61a
Status: newneeds_review

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:

7938a7428110: fix bug with Hilbert polynomial computation

comment:4 Changed 3 years ago by Frédéric Chapoton

no space after :trac:

comment:5 Changed 3 years ago by git

Commit: 7938a7413243b208ba7f6370806a202d512cd61a37f3c75798a21b096e49b3756529457dd62f9e45

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

37f3c7528110: remove extra space

comment:6 Changed 3 years ago by Frédéric Chapoton

Reviewers: Frédéric Chapoton
Status: needs_reviewpositive_review

ok, then

comment:7 Changed 3 years ago by Volker Braun

Branch: u/gjorgenson/28110_hilbert_poly37f3c75798a21b096e49b3756529457dd62f9e45
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.