Opened 3 years ago

Closed 3 years ago

# Bug in Hilbert series computation

Reported by: Owned by: Simon King major sage-8.9 algebra Hilbert polynomial Grayson Jorgenson Frédéric Chapoton N/A 37f3c75 37f3c75798a21b096e49b3756529457dd62f9e45

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

### 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 → u/gjorgenson/28110_hilbert_poly → 7938a7413243b208ba7f6370806a202d512cd61a new → needs_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:

 ​7938a74 `28110: 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: 7938a7413243b208ba7f6370806a202d512cd61a → 37f3c75798a21b096e49b3756529457dd62f9e45

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

 ​37f3c75 `28110: remove extra space`

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

Reviewers: → Frédéric Chapoton needs_review → positive_review

ok, then

### comment:7 Changed 3 years ago by Volker Braun

Branch: u/gjorgenson/28110_hilbert_poly → 37f3c75798a21b096e49b3756529457dd62f9e45 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.