-- Example which illustrates the unpredictability of coefficient
-- size in a Groebner basis.  This unpredictability makes it difficult
-- to apply modular methods.

-- N is the number of indeterminates.
-- Later on you will be asked to vary this value.
N := 5;

-- We start with an ideal with small generators (which happen to
-- to be a lex Groebner basis).
Use Q[x[1..N]],Lex;
-- Fill the list L with the generators
L := [x[I]-x[I+1]^9 | I In 1..(N-1)];
Append(L,x[N]-2);
-- Build the ideal I from the list L
I := Ideal(L);
-- Compute a Groebner basis for I; this is trivial since the
-- given generators are already a lex Groebner basis.
Time GB := GBasis(I);
PrintLn GB;  -- Confirm that the G-basis comprises just the given generators.

-- Now compute a reduced G-basis; for larger N this will take some time.
Time RGB := ReducedGBasis(I);
-- The reduced G-basis contains some large polynomials...
PrintLn Last(RGB);

-----------------------------------------------------------------------------
-- It is well known that lex G-bases can be costly to compute because
-- they often contain polynomials with large coefficients.  In contrast,
-- DegRevLex G-bases tend to be less cantankerous: easier to compute
-- and containing smaller polynomials.  Let's see what happens In this
-- instance:

Use Q[x[1..N]]; -- DegRevLex is the default ordering in CoCoA
-- Same generators as before...
L := [x[I]-x[I+1]^9 | I In 1..(N-1)];
Append(L,x[N]-2);
I := Ideal(L);
Time GB := GBasis(I); -- Takes some time for larger N.
PrintLn Last(GB);     -- DegRevLex G-basis is not so small in this case.

-----------------------------------------------------------------------------
-- Try varying the value of N.  Can you derive an empirical estimate for
-- the size of the coefficients In the "large" G-bases?
-- Limit yourself to N < 10 unless you have a fast computer with lots
-- of memory.

-----------------------------------------------------------------------------
-- Hard research exercise: (I do not know how to tackle it)
-- Find a fairly general way of using modular methods to speed up the
-- computation of G-bases.  For instance:
-- * determine reasonable coefficient bounds for G-bases in a fairly
--   general setting (e.g. for zero-dimensional ideals, or for a fixed
--   number of indeterminates);
-- * find a cheap way of verifying that a set of polynomials is indeed
--   a G-basis;
-- * can Hensel lifting be used in any way?