----------------------------------------------------------------------
-- Hilbert Functions 2
-- from "Computation of Hilbert-Poincare' Series"
-- Journal of Pure and Applied Algebra 119 (1997)
----------------------------------------------------------------------

-- INTRODUCTION

-- This exact sequence is the core of many algorithms for
-- computing the Hilbert function of P/I (I monomial Ideal)
--       0 ----> P/(I:(F)) --(*F)--> P/I --(pr)--> P/(I+(F)) ----> 0

-- Standard grading:
-- Using the notation HPNum(J)/HPDen(P) for the HilbertPoincare series of P/J
-- where HPDen(P) = 1/(1-t)^NumIndets(P)
-- we have that
--   HPNum(I) = HPNum(I+(F)) + t^deg(F) * HPNum(I:(F))   (@)

-- Positive(-type) grading:
-- This formula generalizes to any positive grading:
--   HPDen(P) = product([ 1/(1-t^wdeg(x[i])) | i in 1..NumIndets(P)])
--   HPNum(I) = HPNum(I+(F)) + t^wdeg(F) * HPNum(I:(F))
-- where t^wd := t[1]^wd[1]*...*t[s]^wd[s]

----------------------------------------------------------------------

-- BASE CASE

-- Standard grading and positive grading:
-- HPNum( (0) ) = 1  because  HP(P) = HP(P/(0)) = 1/HPDen(P)
Use P ::= QQ[t,w,x,y,z];
I := ideal(zero(P));
HilbertSeries(P/I);
untagged(It).num;

-- SOME EASY CASES

-- HPNum( (G) ) = 1-t^deg(G):
-- in (@) choose I = (0) and F = G
I := ideal(x^3*y^4);
HilbertSeries(P/I);
untagged(It).num;

-- HPNum( (x^a, y^b) ) = (1-t^a)*(1-t^b):
-- in (@) choose I = (x^a) and F = y^b
--   HPNum(x^a, y^b) = HPNum(x^a) - t^deg(b) * HPNum(x^a) =
--                   = HPNum(x^a) * (1-t^b) = (1-t^a)*(1-t^b)
I := ideal(x^3,y^4);
HilbertSeries(P/I);
untagged(It).num;

-- NB: In CoCoA-4 $hp.Num(HilbertSeries(P/I)) is a funny object: try
indent(untagged(HilbertSeries(P/I)), 2);

-- EXERCISE
-- Find the formula of HPNum for a monomial ideal generated by
-- powers of the indeterminates
I := ideal(t^6, w^2, x^3, y^2, z^5);

-- EXERCISE (implementation)
-- Here is the function HPNumIndetPowers for a monomial ideal generated by
-- powers of the indeterminates

Define HPNumIndetPowers(I, T)
  G := interreduced(gens(I));
  Foreach F In G Do
    If not(IsIndetPosPower(F)) Then error("Not an indet power!!"); EndIf;
  EndForeach;
  Return product([ 1-T^deg(F) | F In G ]);
EndDefine; -- HPNumIndetPowers
 
-- (try it on these examples)
I := ideal(x^3, y^4);
HPNumIndetPowers(I, t);

I := ideal(t^6, w^2, x^3, y^2, z^5);
I := ideal(x^3*y);
I := ideal(zero(CurrentRing));

-- EXERCISE
-- Find the formula of HPNum for a monomial ideal generated by
-- powers of the indeterminates and one power-product
I := ideal(x^3, y^4, x*z);

-- EXERCISE (implementation)
-- Write the function HPNumIndetPowers1PP for a monomial ideal generated by
-- powers of the indeterminates and one power-product

----------------------------------------------------------------------
-- CHOOSING THE PIVOT

-- Consider this example:
I := ideal(x*y, y^2*z^2, y^3*z);

-- There are several ways to choose the pivot F in
-- HPNum(I) = HPNum(I+(F)) + t^deg(F) * HPNum(I:(F))   (@)

----------------------------------------
-- Generator pivot:  choose a generator
F := y^3*z;
J := ideal(x*y, y^2*z^2);
--> HPNum(I) = HPNum(J) - t^deg(F) * HPNum(J:(F))
J : ideal(F);  --> ideal(z, x)

--> = HPNum(J) - t^4 * HPNum(ideal(z,x))
F := y^2*z^2;
J2 := ideal(x*y);
--> HPNum(J) = HPNum(J2) - t^deg(F) * HPNum(J2:(F))
J2 : ideal(F);  --> ideal(x)

-- so HPNum(I) is .... (check with CoCoA)

-- Why does this procedure terminate?

----------------------------------------
-- Indeterminate pivot:  choose an indeterminate

-- HPNum(I) = HPNum(I+(F)) + t^deg(F) * HPNum(I:(F))
I := ideal(x*y, y^2*z^2, y^3*z);
F := y;
ideal(interreduced(gens(I + ideal(F))));
I : ideal(F);

-- HPNum(J) = HPNum(J+(F)) + t^deg(F) * HPNum(J:(F))
J := ideal(x, y^2*z, y*z^2);
F := z;
ideal(interreduced(gens(J + ideal(F))));
J:ideal(F);

-- so HPNum(I) is .... (check with CoCoA)

-- Why does this procedure terminate?

----------------------------------------
-- GCD pivot:  choose the gcd of 2 or 3 power-products (not coprime!)

-- HPNum(I) = HPNum(I+(F)) + t^deg(F) * HPNum(I:(F))
I := ideal(x*y, y^2*z^2, y^3*z);
F := y^2*z;
ideal(interreduced(gens(I + ideal(F))));
I:ideal(F);

-- HPNum(J) = HPNum(J+(F)) + t^deg(F) * HPNum(J:(F))
J := ideal(x*y, y^2*z);
F := y;
ideal(interreduced(gens(I + ideal(F))));
J:ideal(F);

-- so HPNum(I) is .... (check with CoCoA)

-- Why does this procedure terminate?

----------------------------------------
-- IndetPower pivot:  choose a (small)power of a "frequent" indeterminate

--> HPNum(I) = HPNum(I+(F)) + t^deg(F) * HPNum(I:(F))
I := ideal(x*y, y^2*z^2, y^3*z);
F := y^2;
ideal(interreduced(gens(I + ideal(F))));
I:ideal(F);

-- so HPNum(I) is .... (check with CoCoA)

-- Why does this procedure terminate?

----------------------------------------------------------------------

-- COMPLEXITY

-- The computational cost is mainly in these two operations:
-- (1) the arithmetic on the polynomials.
-- (2) the interreduction of  I:ideal(F)  quadratic in len(gens(I))

----------------------------------------------------------------------
-- from 1st lecture

-- EXERCISE
-- Consider P/I, where
Use P ::= QQ[x,y,z];
I := ideal(x^3, x*y, y^4, y*z^2, y^3*z, z^3);
-- Compute HPNum(I)

-- EXERCISE
-- Consider P/I, where
P := NewPolyRing(QQ, ["x","y","z"], CompleteToOrd(W2St), NumRows(W2St));
I := ideal(x^3, x*y, y^4, y*z^2, y^3*z, z^3);
-- Compute HPNum(I)

