Certain Groebner basis computations, when given homogeneous input, can run faster if the Hilbert function is know: the algorithm can use this information to bypass computing zero reductions in many cases.
In order to be able to use a Hilbert function hint, currently the object must be in a singly graded polynomial ring (or quotient of such), over a field, with all generators of positive degree, and it must be either commutative, or skew-commutative.
Given a ring, this function returns whether this holds for the ring. For a module, matrix or ideal, this function additionally checks whether the input is homogeneous.
i1 : R1 = ZZ/101[x,y,z, Degrees => {1,2,3}];
|
i2 : assert canUseHilbertHint R1
|
i3 : R2 = ZZ[x,y,z];
|
i4 : assert not canUseHilbertHint R2
|
i5 : R3 = (GF 8)[x,y,z]
o5 = R3
o5 : PolynomialRing
|
i6 : assert canUseHilbertHint R3
|
i7 : use R1
o7 = R1
o7 : PolynomialRing
|
i8 : R4 = R1[u,v, Join => false]/(x*u+y*v)
o8 = R4
o8 : QuotientRing
|
i9 : R5 = first flattenRing R4
o9 = R5
o9 : QuotientRing
|
i10 : canUseHilbertHint R4
o10 = false
|
i11 : canUseHilbertHint R5
o11 = true
|
Here is one way to use Hilbert hints. If one knows the Hilbert function, one can use it. If one computes a Hilbert function (via poincare), one can use that in a ring which is identical, except the monomial order is more computationally intensive (e.g. Lex).
i12 : R = ZZ/101[x,y,z,w]
o12 = R
o12 : PolynomialRing
|
i13 : I = ideal random(R^1, R^{-5,-5,-5})
5 4 3 2 2 3 4 5 4 3
o13 = ideal (24x - 36x y + 19x y - 29x y - 18x*y + 19y - 30x z + 19x y*z
-----------------------------------------------------------------------
2 2 3 4 3 2 2 2 2 2 3 2
- 24x y z - 13x*y z - 16y z - 29x z - 16x y*z - 15x*y z + 15y z +
-----------------------------------------------------------------------
2 3 3 2 3 4 4 5 4 3
34x z + 38x*y*z + 43y z + 45x*z + 36y*z + 40z - 29x w - 10x y*w -
-----------------------------------------------------------------------
2 2 3 4 3 2 2 3
38x y w - 43x*y w + 7y w - 8x z*w + 39x y*z*w - 28x*y z*w - 23y z*w +
-----------------------------------------------------------------------
2 2 2 2 2 3 3 4 3 2
19x z w + 2x*y*z w - 17y z w - 34x*z w + 35y*z w + 11z w - 22x w +
-----------------------------------------------------------------------
2 2 2 2 3 2 2 2 2 2 2
21x y*w - 47x*y w + 39y w - 47x z*w + 16x*y*z*w - 11y z*w -
-----------------------------------------------------------------------
2 2 2 2 3 2 2 3 3 2 3 3
48x*z w + 11y*z w + 46z w - 39x w + 22x*y*w + 48y w - 47x*z*w -
-----------------------------------------------------------------------
3 2 3 4 4 4 5 5 4 3 2
38y*z*w - 28z w + 47x*w + 33y*w + z*w - 3w , 22x - 47x y + 2x y
-----------------------------------------------------------------------
2 3 4 5 4 3 2 2 3 4
- 10x y + 24x*y + 9y - 23x z + 29x y*z + 30x y z - 30x*y z - 39y z +
-----------------------------------------------------------------------
3 2 2 2 2 2 3 2 2 3 3 2 3
15x z + 39x y*z - 15x*y z + 13y z + 32x z + 33x*y*z - 49y z +
-----------------------------------------------------------------------
4 4 5 4 3 2 2 3 4
17x*z - 8y*z + 41z - 7x w - 47x y*w - 18x y w - 48x*y w + 4y w -
-----------------------------------------------------------------------
3 2 2 3 2 2 2
37x z*w + 27x y*z*w + 39x*y z*w - 26y z*w - 9x z w - 49x*y*z w -
-----------------------------------------------------------------------
2 2 3 3 4 3 2 2 2 3 2
11y z w - 20x*z w + 36y*z w + 16z w - 13x w - 22x y*w + 22y w -
-----------------------------------------------------------------------
2 2 2 2 2 2 2 2 2 3 2 2 3
32x z*w - 33x*y*z*w - 8y z*w + 44x*z w - 3y*z w - 28z w - 20x w
-----------------------------------------------------------------------
3 2 3 3 3 2 3 4 4
- 19x*y*w + 43y w - 39x*z*w - 22y*z*w - 6z w + 36x*w - 30y*w +
-----------------------------------------------------------------------
4 5 5 4 3 2 2 3 4 5 4
35z*w - 9w , - 35x + 6x y - 31x y + 4x y - 48x*y + 30y + 40x z +
-----------------------------------------------------------------------
3 2 2 3 4 3 2 2 2 2 2
25x y*z + 30x y z - 29x*y z + 13y z - 41x z + 27x y*z + 30x*y z -
-----------------------------------------------------------------------
3 2 2 3 3 2 3 4 4 5 4
13y z - 35x z - 49x*y*z + 8y z + x*z - 46y*z - 28z + 3x w -
-----------------------------------------------------------------------
3 2 2 3 4 3 2 2
2x y*w - 47x y w - 48x*y w - 17y w - 49x z*w - 40x y*z*w - 37x*y z*w +
-----------------------------------------------------------------------
3 2 2 2 2 2 3 3 4
3y z*w - 31x z w + 28x*y*z w + 8y z w + 40x*z w + 49y*z w + 15z w -
-----------------------------------------------------------------------
3 2 2 2 2 2 3 2 2 2 2
13x w + 37x y*w + 47x*y w - 41y w - 39x z*w - 18x*y*z*w -
-----------------------------------------------------------------------
2 2 2 2 2 2 3 2 2 3 3 2 3
29y z*w - 22x*z w - 18y*z w + 18z w - 31x w + 46x*y*w + 30y w +
-----------------------------------------------------------------------
3 3 2 3 4 4 4 5
10x*z*w + 42y*z*w - 16z w + 7x*w + 23y*w - 46z*w + 12w )
o13 : Ideal of R
|
i14 : hf = poincare I
5 10 15
o14 = 1 - 3T + 3T - T
o14 : ZZ[T]
|
i15 : codim I == 3 -- a complete intersection
o15 = true
|
i16 : Rlex = newRing(R, MonomialOrder => Lex)
o16 = Rlex
o16 : PolynomialRing
|
i17 : Ilex = sub(I, Rlex)
5 4 4 4 3 2 3 3
o17 = ideal (24x - 36x y - 30x z - 29x w + 19x y + 19x y*z - 10x y*w -
-----------------------------------------------------------------------
3 2 3 3 2 2 3 2 2 2 2 2 2
29x z - 8x z*w - 22x w - 29x y - 24x y z - 38x y w - 16x y*z +
-----------------------------------------------------------------------
2 2 2 2 3 2 2 2 2 2 3 4
39x y*z*w + 21x y*w + 34x z + 19x z w - 47x z*w - 39x w - 18x*y -
-----------------------------------------------------------------------
3 3 2 2 2 2 2 3
13x*y z - 43x*y w - 15x*y z - 28x*y z*w - 47x*y w + 38x*y*z +
-----------------------------------------------------------------------
2 2 3 4 3 2 2
2x*y*z w + 16x*y*z*w + 22x*y*w + 45x*z - 34x*z w - 48x*z w -
-----------------------------------------------------------------------
3 4 5 4 4 3 2 3 3 2
47x*z*w + 47x*w + 19y - 16y z + 7y w + 15y z - 23y z*w + 39y w +
-----------------------------------------------------------------------
2 3 2 2 2 2 2 3 4 3 2 2
43y z - 17y z w - 11y z*w + 48y w + 36y*z + 35y*z w + 11y*z w -
-----------------------------------------------------------------------
3 4 5 4 3 2 2 3 4 5 5
38y*z*w + 33y*w + 40z + 11z w + 46z w - 28z w + z*w - 3w , 22x -
-----------------------------------------------------------------------
4 4 4 3 2 3 3 3 2 3
47x y - 23x z - 7x w + 2x y + 29x y*z - 47x y*w + 15x z - 37x z*w -
-----------------------------------------------------------------------
3 2 2 3 2 2 2 2 2 2 2 2 2
13x w - 10x y + 30x y z - 18x y w + 39x y*z + 27x y*z*w - 22x y*w +
-----------------------------------------------------------------------
2 3 2 2 2 2 2 3 4 3 3
32x z - 9x z w - 32x z*w - 20x w + 24x*y - 30x*y z - 48x*y w -
-----------------------------------------------------------------------
2 2 2 3 2 2 3
15x*y z + 39x*y z*w + 33x*y*z - 49x*y*z w - 33x*y*z*w - 19x*y*w +
-----------------------------------------------------------------------
4 3 2 2 3 4 5 4 4
17x*z - 20x*z w + 44x*z w - 39x*z*w + 36x*w + 9y - 39y z + 4y w +
-----------------------------------------------------------------------
3 2 3 3 2 2 3 2 2 2 2 2 3 4
13y z - 26y z*w + 22y w - 49y z - 11y z w - 8y z*w + 43y w - 8y*z
-----------------------------------------------------------------------
3 2 2 3 4 5 4 3 2 2 3
+ 36y*z w - 3y*z w - 22y*z*w - 30y*w + 41z + 16z w - 28z w - 6z w
-----------------------------------------------------------------------
4 5 5 4 4 4 3 2 3
+ 35z*w - 9w , - 35x + 6x y + 40x z + 3x w - 31x y + 25x y*z -
-----------------------------------------------------------------------
3 3 2 3 3 2 2 3 2 2 2 2
2x y*w - 41x z - 49x z*w - 13x w + 4x y + 30x y z - 47x y w +
-----------------------------------------------------------------------
2 2 2 2 2 2 3 2 2 2 2 2 3
27x y*z - 40x y*z*w + 37x y*w - 35x z - 31x z w - 39x z*w - 31x w
-----------------------------------------------------------------------
4 3 3 2 2 2 2 2
- 48x*y - 29x*y z - 48x*y w + 30x*y z - 37x*y z*w + 47x*y w -
-----------------------------------------------------------------------
3 2 2 3 4 3
49x*y*z + 28x*y*z w - 18x*y*z*w + 46x*y*w + x*z + 40x*z w -
-----------------------------------------------------------------------
2 2 3 4 5 4 4 3 2 3
22x*z w + 10x*z*w + 7x*w + 30y + 13y z - 17y w - 13y z + 3y z*w -
-----------------------------------------------------------------------
3 2 2 3 2 2 2 2 2 3 4 3
41y w + 8y z + 8y z w - 29y z*w + 30y w - 46y*z + 49y*z w -
-----------------------------------------------------------------------
2 2 3 4 5 4 3 2 2 3 4
18y*z w + 42y*z*w + 23y*w - 28z + 15z w + 18z w - 16z w - 46z*w
-----------------------------------------------------------------------
5
+ 12w )
o17 : Ideal of Rlex
|
i18 : elapsedTime g1 = gens gb Ilex;
-- 1.54095s elapsed
1 372
o18 : Matrix Rlex <-- Rlex
|
i19 : Ilex = ideal(Ilex_*) -- clear out the previous Groebner basis
5 4 4 4 3 2 3 3
o19 = ideal (24x - 36x y - 30x z - 29x w + 19x y + 19x y*z - 10x y*w -
-----------------------------------------------------------------------
3 2 3 3 2 2 3 2 2 2 2 2 2
29x z - 8x z*w - 22x w - 29x y - 24x y z - 38x y w - 16x y*z +
-----------------------------------------------------------------------
2 2 2 2 3 2 2 2 2 2 3 4
39x y*z*w + 21x y*w + 34x z + 19x z w - 47x z*w - 39x w - 18x*y -
-----------------------------------------------------------------------
3 3 2 2 2 2 2 3
13x*y z - 43x*y w - 15x*y z - 28x*y z*w - 47x*y w + 38x*y*z +
-----------------------------------------------------------------------
2 2 3 4 3 2 2
2x*y*z w + 16x*y*z*w + 22x*y*w + 45x*z - 34x*z w - 48x*z w -
-----------------------------------------------------------------------
3 4 5 4 4 3 2 3 3 2
47x*z*w + 47x*w + 19y - 16y z + 7y w + 15y z - 23y z*w + 39y w +
-----------------------------------------------------------------------
2 3 2 2 2 2 2 3 4 3 2 2
43y z - 17y z w - 11y z*w + 48y w + 36y*z + 35y*z w + 11y*z w -
-----------------------------------------------------------------------
3 4 5 4 3 2 2 3 4 5 5
38y*z*w + 33y*w + 40z + 11z w + 46z w - 28z w + z*w - 3w , 22x -
-----------------------------------------------------------------------
4 4 4 3 2 3 3 3 2 3
47x y - 23x z - 7x w + 2x y + 29x y*z - 47x y*w + 15x z - 37x z*w -
-----------------------------------------------------------------------
3 2 2 3 2 2 2 2 2 2 2 2 2
13x w - 10x y + 30x y z - 18x y w + 39x y*z + 27x y*z*w - 22x y*w +
-----------------------------------------------------------------------
2 3 2 2 2 2 2 3 4 3 3
32x z - 9x z w - 32x z*w - 20x w + 24x*y - 30x*y z - 48x*y w -
-----------------------------------------------------------------------
2 2 2 3 2 2 3
15x*y z + 39x*y z*w + 33x*y*z - 49x*y*z w - 33x*y*z*w - 19x*y*w +
-----------------------------------------------------------------------
4 3 2 2 3 4 5 4 4
17x*z - 20x*z w + 44x*z w - 39x*z*w + 36x*w + 9y - 39y z + 4y w +
-----------------------------------------------------------------------
3 2 3 3 2 2 3 2 2 2 2 2 3 4
13y z - 26y z*w + 22y w - 49y z - 11y z w - 8y z*w + 43y w - 8y*z
-----------------------------------------------------------------------
3 2 2 3 4 5 4 3 2 2 3
+ 36y*z w - 3y*z w - 22y*z*w - 30y*w + 41z + 16z w - 28z w - 6z w
-----------------------------------------------------------------------
4 5 5 4 4 4 3 2 3
+ 35z*w - 9w , - 35x + 6x y + 40x z + 3x w - 31x y + 25x y*z -
-----------------------------------------------------------------------
3 3 2 3 3 2 2 3 2 2 2 2
2x y*w - 41x z - 49x z*w - 13x w + 4x y + 30x y z - 47x y w +
-----------------------------------------------------------------------
2 2 2 2 2 2 3 2 2 2 2 2 3
27x y*z - 40x y*z*w + 37x y*w - 35x z - 31x z w - 39x z*w - 31x w
-----------------------------------------------------------------------
4 3 3 2 2 2 2 2
- 48x*y - 29x*y z - 48x*y w + 30x*y z - 37x*y z*w + 47x*y w -
-----------------------------------------------------------------------
3 2 2 3 4 3
49x*y*z + 28x*y*z w - 18x*y*z*w + 46x*y*w + x*z + 40x*z w -
-----------------------------------------------------------------------
2 2 3 4 5 4 4 3 2 3
22x*z w + 10x*z*w + 7x*w + 30y + 13y z - 17y w - 13y z + 3y z*w -
-----------------------------------------------------------------------
3 2 2 3 2 2 2 2 2 3 4 3
41y w + 8y z + 8y z w - 29y z*w + 30y w - 46y*z + 49y*z w -
-----------------------------------------------------------------------
2 2 3 4 5 4 3 2 2 3 4
18y*z w + 42y*z*w + 23y*w - 28z + 15z w + 18z w - 16z w - 46z*w
-----------------------------------------------------------------------
5
+ 12w )
o19 : Ideal of Rlex
|
i20 : elapsedTime g2 = gens gb(Ilex, Hilbert => hf);
-- .739907s elapsed
1 372
o20 : Matrix Rlex <-- Rlex
|
i21 : g1 == g2
o21 = true
|