-- This is a small collection of examples which illustrate why using
-- Hensel lifting directly is computationally a bad idea for sparse
-- multivariate polynomials.  These are intended as motivating examples
-- for the sparse reconstruction methods of Zippel and BenOr-Tiwari.

-----------------------------------------------------------------------------
-- First example: the polynomial to be reconstructed is F = (xyz)^3-1.
-- We suppose the evaluation point chosen is [1,2,3], so the
-- corresponding ideal is I = (x-1,y-2,z-3).  To be able to reconstruct
-- F we must lift to precision I^10 because F has degree 9.  The
-- problem is that F modulo lower powers of I becomes a dense polynomial
-- with many terms.

Use Q[x,y,z];
F := (x*y*z)^3-1;
I := Ideal(x-1, y-2, z-3);
FmodI9 := NF(F, I^9);
PrintLn "F modulo I^9 has ", Len(FmodI9), " terms.";
-- You can print out FmodI9 if you like.

-----------------------------------------------------------------------------
-- The problem aggravates rapidly as the number of indeterminates rises.
-- This time we use F = (abcde)^2-1 and the ideal I=(a-1,b-2,c-3,d-4,e-5).
-- Since F has degree 10, we would expect the biggest modular image to be
-- that modulo I^10 -- F remains unchanged modulo any higher power of I.

Use Q[a,b,c,d,e];
F := (a*b*c*d*e)^2-1;
I := Ideal(a-1, b-2, c-3, d-4, e-5);
FmodI10 := NF(F, I^10);
PrintLn "F modulo I^10 has ", Len(FmodI10), " terms.";
-- You can print out FmodI10 if you like.

-- Suppose instead F had been (abcde)^3-1.  How many terms would F modulo
-- I^15 have?  If you have a fast computer with lots of memory, you could
-- try running the example.
-----------------------------------------------------------------------------