4 Presentations of graded algebras
  
  A  graded  algebra A is a an algebra that has additional structure, called a
  grading  (see Section 3). Graded algebras of the type found in HAPprime have
  a presentation as a quotient of a polynomial ring
  
  
       H^*(G, F) = F[x_1, x_2, ..., x_n] / <I_1, I_2, ..., I_m>
  
  
  where  the polynomial ring indeterminates x_i each have an associated degree
  d_i and the I_j are relations which together generate an ideal in the ring.
  
  
  4.1 The GradedAlgebraPresentation datatype
  
  For  algebras  that  have a presentation as a quotient of a polynomial ring,
  the GradedAlgebraPresentation datatype stores a quotient R/I where:
  
  --    R is a polynomial ring
  
  --    I is a set of relations in R that generate an ideal
  
  and it also stores a grading in the form of
  
  --    the degree of each indeterminate of R
  
  
  4.2 Construction function
  
  
  4.2-1 GradedAlgebraPresentation construction functions
  
  > GradedAlgebraPresentation( R, I, degs ) _________________________operation
  > GradedAlgebraPresentationNC( R, I, degs ) _______________________operation
  Returns:  GradedAlgebraPresentation
  
  Construct  a GradedAlgebraPresentation object representing a presentation of
  a graded algebra as the quotient of a polynomial ring R by the ideal I (as a
  list  of  relations  in  R)  where  the  indeterminates of R (as returned by
  IndeterminatesOfGradedAlgebraPresentation    (4.3-3)   have   degrees   degs
  respectively.
  
  The   function  GradedAlgebraPresentation  checks  that  the  arguments  are
  compatible, while the NC method performs no checks.
  
  
  4.3 Data access functions
  
  4.3-1 BaseRing
  
  > BaseRing( A ) ___________________________________________________attribute
  Returns:  Polynomial ring
  
  Returns the base ring of the graded algebra presentation A.
  
  4.3-2 CoefficientsRing
  
  > CoefficientsRing( A ) ___________________________________________attribute
  Returns:  Ring
  
  Returns the ring of coefficients of the graded algebra presentation A.
  
  4.3-3 IndeterminatesOfGradedAlgebraPresentation
  
  > IndeterminatesOfGradedAlgebraPresentation( A ) __________________attribute
  Returns:  List
  
  Returns the indeterminates used in the graded algebra presentation A.
  
  4.3-4 GeneratorsOfPresentationIdeal
  
  > GeneratorsOfPresentationIdeal( A ) ______________________________attribute
  Returns:  List
  
  Returns the relations in the ring presentation for the graded algebra A. The
  relations  are  returned  sorted  in  order  of  increasing  degree,  and by
  indeterminate within each degree.
  
  4.3-5 PresentationIdeal
  
  > PresentationIdeal( A ) __________________________________________attribute
  Returns:  Ideal
  
  Returns  the  ideal  in  the  graded  algebra  presentation A as a GAP ideal
  'Reference: Ideal'.
  
  4.3-6 IndeterminateDegrees
  
  > IndeterminateDegrees( A ) _______________________________________attribute
  Returns:  List
  
  Returns  the  degrees  of  the  polynomial ring indeterminates in the graded
  algebra  presentation  A.  The ordering corresponds to the order of the ring
  indeterminates    returned    by   IndeterminatesOfGradedAlgebraPresentation
  (4.3-3).
  
  
  4.3-7     Example:     Constructing     and     accessing    data    of    a
  GradedAlgebraPresentation
  
  We  demonstrate creating a GradedAlgebraPresentation object and reading back
  its  data  by  creating the graded algebra A with presentation F_2[x_1, x_2,
  x_3]  /  (x_1x_2,  x_1^3+x_2^3)  where x_1 and x_2 have degree 1 and x_3 has
  degree 4
  
  ---------------------------  Example  ----------------------------
    gap> R := PolynomialRing(GF(2), 3);;
    gap> A := GradedAlgebraPresentation(R, [R.1*R.2, R.1^3+R.2^3], [1,1,4]);
    Graded algebra GF(2)[ x_1, x_2, x_3 ] / [ x_1*x_2, x_1^3+x_2^3
     ] with indeterminate degrees [ 1, 1, 4 ]
    gap> CoefficientsRing(A);
    GF(2)
    gap> IndeterminatesOfGradedAlgebraPresentation(A);
    [ x_1, x_2, x_3 ]
    gap> GeneratorsOfPresentationIdeal(A);
    [ x_1*x_2, x_1^3+x_2^3 ]
    gap> IndeterminateDegrees(A);
    [ 1, 1, 4 ]
  ------------------------------------------------------------------
  
  
  4.4 Other functions
  
  
  4.4-1 TensorProduct
  
  > TensorProduct( A, B ) ___________________________________________operation
  > TensorProduct( coll ) ___________________________________________operation
  Returns:  GradedAlgebraPresentation
  
  Returns  a presentation for the graded algebra that is the tensor product of
  two graded algebras presented by A and B, or of a list of graded algebras.
  
  4.4-2 IsIsomorphicGradedAlgebra
  
  > IsIsomorphicGradedAlgebra( A, B ) _______________________________operation
  
  Returns  true  if  the  graded  algebras  A  and  B are isomorphic, or false
  otherwise. This function tries all possible ring isomorphisms, so may take a
  considerable  length  of  time  for  graded  algebras with a large number of
  dimensions in each degree.
  
  4.4-3 IsAssociatedGradedRing
  
  > IsAssociatedGradedRing( A, B ) __________________________________operation
  
  Returns true if the algebra A is an associated graded ring of the algebra B.
  This  is  the  case  if  the  additive  structure  is  the  same  (i.e.  the
  Hilbert-Poincaré  series  is  the same), and the generators for A (and their
  degrees) are included in the generators for B.
  
  4.4-4 DegreeOfRepresentative
  
  > DegreeOfRepresentative( A, p ) __________________________________operation
  Returns:  Integer
  
  Returns  the  degree  of  a polynomial representative p from the graded ring
  presentation A.
  
  4.4-5 MaximumDegreeForPresentation
  
  > MaximumDegreeForPresentation( A ) _______________________________attribute
  Returns:  Integer
  
  Returns  the  maximum  degree  in  generators or relations that is needed to
  generate the graded algebra presentation A. This is not necessarily the same
  as  the  largest  degree  in  any  of  the  relations  and generators - some
  relations  may  be redundant (for example due to being a Groebner basis), so
  this  routine  checks  for  the  largest degree of a required generator, and
  returns the maximum of this and the generator degrees.
  
  
  4.4-6 SubspaceDimensionDegree
  
  > SubspaceDimensionDegree( A, d ) _________________________________operation
  > SubspaceDimensionDegree( A, degs ) ______________________________operation
  Returns:  Integer or list
  
  Returns  the  dimension  of  degree  d of the graded algebra A, or a list of
  dimensions corresponding to the list of degrees degs.
  
  
  4.4-7 SubspaceBasisRepsByDegree
  
  > SubspaceBasisRepsByDegree( A, d ) _______________________________operation
  > SubspaceBasisRepsByDegree( A, degs ) ____________________________operation
  Returns:  List or list of lists
  
  Returns a basis for degree d of the graded algebra A, or a list of bases for
  the   list   of   degrees  degs.  Each  basis  is  returned  as  a  list  of
  representatives.
  
  4.4-8 CoefficientsOfPoincareSeries
  
  > CoefficientsOfPoincareSeries( A, n ) ____________________________operation
  Returns:  List
  
  Returns  the  first  n  coefficients  of  the Poincaré series for the graded
  algebra with A. These are equal to the dimensions of degrees 0 to n-1 of the
  algebra  (a  fact  that  is  used  in  the  function SubspaceDimensionDegree
  (4.4-6)).
  
  This function uses the singular package.
  
  4.4-9 HilbertPoincareSeries
  
  > HilbertPoincareSeries( A ) ______________________________________attribute
  Returns:  Rational function
  
  Returns  the  Poincaré  series  for the graded algebra A. This is a rational
  function  P(t)/Q(t)  which  is  a is a polynomial whose coefficients are the
  dimensions of each degree of the algebra.
  
  This function uses the singular package.
  
  4.4-10 LHSSpectralSequence
  
  > LHSSpectralSequence( G[, N], n ) ________________________________operation
  > LHSSpectralSequenceLastSheet( G[, N] ) __________________________operation
  Returns:  GradedAlgebraPresentation or list
  
  Computes the Lyndon-Hoschild-Serre spectral sequence for the group extension
  N  ->  G  ->  G/N.  If a normal suggroup N is not provided, then the largest
  central subgroup of G is used, or (if the order of the centre is larger than
  sqrt|G|)  then the central subgroup that leads to the smallest initial sheet
  size is chosen.
  
  The  function LHSSpectralSequence returns the first n sheets of the spectral
  sequence,  or  all  of the sequence up to convergence, if that occurs before
  the (n+1)th sheet. The Lyndon-Hoschild-Serre spectral sequence starts at the
  E_2  sheet, so the first element in returned list will always be empty. If n
  is set to infinity then the length of the returned list equals the number of
  sheets  for  convergence,  and  the  last  sheet in the list is the limiting
  sheet.
  
  The function LHSSpectralSequenceLastSheet returns only the limiting sheet of
  the  spectral  sequence.  This  ring  is an associated graded algebra of the
  mod-p  cohomology  ring  of  G,  with  the same additive structure while not
  necessarily being isomorphic to it.
  
  There are four options 'Reference: Options Stack' which can be used to guide
  this algorithm:
  
  --    InitialLHSBicomplexSize can be used to specify the initial size of the
        bicomplex  (the  default  is  5).  If, in the process of computing the
        spectral  sequence,  this  is found to be too small then the algorithm
        restarts  with  a  larger  value. Specifying a larger initial value in
        these cases can save time.
  
  --    LargerLHSBicomplexBreak  if  set to true will force the calculation to
        enter  a  break loop before restarting with a larger bicomplex, should
        the  bicomplex  be found to be too small. The user user is prompted to
        type  return;  before continuing. The default behaviour is false, i.e.
        no prompt.
  
  --    LargerLHSBicomplexFail  if  set  to  true  will return fail should the
        bicomplex  be  found  to be too small. The default behaviour is false,
        i.e.  to  either  restart  or  prompt, depending on the setting of the
        previous option.
  
  --    NoInductiveProof  if  set  to  true will not check that the cohomology
        rings  for  N  and  G/N  are  correct.  Instead,  it  will compute the
        cohomology  rings  only up to the degree needed for the bicomplex size
        (5 by default, or specified by the InitialLHSBicomplexSize option).
  
  
  4.5 Example: Computing the Lyndon-Hoschild-Serre spectral sequence and mod-p
  cohomology ring for a small p-group
  
  The Lyndon-Hoschild-Serre spectral sequence is relates the cohomologies of a
  normal  subgroup  N  and a quotient group G/N to the cohomology of the total
  group  G: the limiting sheet of the sequence is an associated graded ring of
  the cohomology of G.
  
  In this example we calculate the Lyndon-Hoschild-Serre spectral sequence for
  a  group of order 16 using the centre of G as our normal subgroup. By asking
  for an infinite number of terms, this function calculates enough terms to be
  sure that the sequence has converged. We compare the dimensions in the first
  (E_2)  and last (E_infty) sheet, we demonstrate that the limiting sheet (the
  last  in  the list) is a graded algebra by multiplying some elements, and we
  calculate the Poincaré series of the last sheet.
  
  ---------------------------  Example  ----------------------------
    gap> G := SmallGroup(16, 4);;
    gap> SS := LHSSpectralSequence(G, Centre(G), infinity);
    [ , Graded algebra GF(2)[ x_1, x_2, x_3, x_4 ] /
        [  ] with indeterminate degrees [ 1, 1, 1, 1 ],
      Graded algebra GF(2)[ x_1, x_2, x_3, x_4 ] / [ x_2^2, x_1^2+x_1*x_2
         ] with indeterminate degrees [ 1, 1, 2, 2 ],
      Graded algebra GF(2)[ x_1, x_2, x_3, x_4 ] / [ x_2^2, x_1^2+x_1*x_2
         ] with indeterminate degrees [ 1, 1, 2, 2 ] ]
    gap> # i.e. we identify convergence after 3 terms
    gap> #
    gap> # Compare the dimensions of the first and last sheet
    gap> SubspaceDimensionDegree(SS[2], [1..10]);
    [ 4, 10, 20, 35, 56, 84, 120, 165, 220, 286 ]
    gap> SubspaceDimensionDegree(SS[3], [1..10]);
    [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
    gap> #
    gap> # Take the two basis elements from degree 1 and check that the
    gap> # product is in degree two
    gap> B := SubspaceBasisRepsByDegree(SS[3], 1);
    [ x_1, x_2 ]
    gap> DegreeOfRepresentative(SS[3], B[1]*B[2]);
    2
    gap> #
    gap> # And find the Poincare series
    gap> HilbertPoincareSeries(SS[3]);
    (1)/(x_1^2-2*x_1+1)
  ------------------------------------------------------------------
  
  The  largest  degree  in  the  presentation  for  the  limiting sheet in the
  Lyndon-Hoschild-Serre  spectral  sequence  for  G is the same as the largest
  degree  in  the presentation for the mod-p cohomology ring of G. We continue
  this example by calculating this maximum degree, n, for our group G and then
  computing  the mod-p cohomology ring. We confirm that the cohomology ring is
  an  associated  graded  ring of the limiting sheet of the spectral sequence,
  and check whether in this case it is in fact also isomorphic.
  
  ---------------------------  Example  ----------------------------
    gap> G := SmallGroup(16, 4);;
    gap> Einf := LHSSpectralSequenceLastSheet(G, Centre(G));
    Graded algebra GF(2)[ x_1, x_2, x_3, x_4 ] / [ x_2^2, x_1^2+x_1*x_2
     ] with indeterminate degrees [ 1, 1, 2, 2 ]
    gap> #
    gap> # Find the maximum degree
    gap> n := MaximumDegreeForPresentation(Einf);
    2
    gap> #
    gap> # And calculate the cohomology ring
    gap> H := ModPCohomologyRingPresentation(G, n);
    Graded algebra GF(2)[ x_1, x_2, x_3, x_4 ] / [ x_1*x_2+x_2^2, x_1^2
     ] with indeterminate degrees [ 1, 1, 2, 2 ]
    gap> #
    gap> # Check for an associated graded ring, and isomorphism
    gap> IsAssociatedGradedRing(H, Einf);
    true
    gap> IsIsomorphicGradedAlgebra(H, Einf);
    true
  ------------------------------------------------------------------