-- Exercise illustrating the existence of pairs of polynomials
-- with GCD having uncommonly large coefficients.

-- The absolute value of the largest coefficient in a polynomial
-- is called the height of the polynomial.  The height and the
-- degree are two common measure of the size of a univariate polynomial.
-- Here is a CoCoA function for computing the height.
Define Height(F)
  C := Coefficients(F);
  Return Max(Max(C), -Min(C));
EndDefine; -- Height

-- This function produces a list of all irreducible polynomials
-- which divide F.
Define IrredFacs(F)
  Return [FacPow[1] | FacPow In Factor(F) And Deg(FacPow) > 0];
EndDefine; -- IrredFacs


-- Using CoCoA (and the functions above) find a polynomial of height 4
-- which divides x^20-1.  I suggest you use these commands/functions:
-- Foreach, Subsets, Product.


-- Prove that for any integer n and positive integer r there is a
-- polynomial f (in Z[x]) of height at most 1 such that f = n x^r mod x^20-1.
-- For example, x^23+x^3 = 2x^3 mod x^20-1.

-- Write down a polynomial g of height 1 such that GCD(g, x^20-1)
-- has height 4.  Verify your answer with CoCoA.
-- This is an example of two polynomials whose GCD is "much bigger"
-- than either of the original polynomials.

-- Knowing that x^60-1 has a factor of height 54, use CoCoA to determine two
-- polynomials of height 1 whose GCD has height 54.  Can you get CoCoA to
-- compute the GCD?

-- If you are patient and have a fast computer, you might like to find
-- the degree 57 factor of x^120-1 which has height 192.  This would enable
-- you write down two polynomials of height 1 having GCD of height 192.

-- Hard research exercise (well, I do not know how to tackle it):
-- study the maximal heights of factors of x^N-1 as N varies.
-- For which N does x^N-1 have factors of especially great height?
-- x^N-1 is a product of cyclotomic factors; which cyclotomic factors
-- should be multiplied together to produce the factor of greatest height?
-- How does the greatest height increase with N? [this may be known]