chap4.txt

  
  4 Resolutions of Crystallographic Groups
  
  
  4.1 Fundamental Domains
  
  Let  S  be a crystallographic group. A Fundamental domain is a closed convex
  set  containing  a  system  of  representatives  for  the Orbits of S in its
  natural action on euclidian space.
  There  are  two  algorithms for calculating fundamental domains in HAPcryst.
  One  uses the geometry and relies on having the standard rule for evaluating
  the  scalar product (i.e. the gramian matrix is the identity). The other one
  is  independent  of  the  gramian  matrix  but does only work for Bieberbach
  groups,   while  the  first  ("geometric")  algorithm  works  for  arbitrary
  crystallographic groups given a point with trivial stabilizer.
  
  4.1-1 FundamentalDomainStandardSpaceGroup
  
  > FundamentalDomainStandardSpaceGroup( [v, ]G ) ______________________method
  > FundamentalDomainStandardSpaceGroup( v, G ) ________________________method
  Returns:  a PolymakeObject
  
  Let  G  be  an  AffineCrystGroupOnRight and v a vector. A fundamental domain
  containing v is calculated and returned as a PolymakeObject. The vector v is
  used  as the starting point for a Dirichlet-Voronoi construction. If no v is
  given,  the  origin  is used as starting point if it has trivial stabiliser.
  Otherwise an error is cast.
  
  ---------------------------  Example  ----------------------------
    gap> fd:=FundamentalDomainStandardSpaceGroup([1/2,0,1/5],SpaceGroup(3,9));
    <polymake object>
    gap> Polymake(fd,"N_VERTICES");
    24
    gap> fd:=FundamentalDomainStandardSpaceGroup(SpaceGroup(3,9));
    <polymake object>
    gap> Polymake(fd,"N_VERTICES");
    8
  ------------------------------------------------------------------
  
  4.1-2 FundamentalDomainBieberbachGroup
  
  > FundamentalDomainBieberbachGroup( G ) ______________________________method
  > FundamentalDomainBieberbachGroup( v, G[, gram] ) ___________________method
  Returns:  a PolymakeObject
  
  Given  a  starting  vector v and a Bieberbach group G in standard form, this
  method  calculates  the  Dirichlet  domain with respect to v. If gram is not
  supplied,     the     average     gramian     matrix     is     used    (see
  GramianOfAverageScalarProductFromFiniteMatrixGroup   (2.3-1)).   It  is  not
  tested if gram is symmetric and positive definite. It is also not tested, if
  the product defined by gram is invariant under the point group of G.
  
  The  behaviour  of  this function is influenced by the option ineqThreshold.
  The   algorithm   calculates  approximations  to  a  fundamental  domain  by
  iteratively  adding  inequalities.  For  an  approximating polyhedron, every
  vertex  is  tested  to  find  new  inequalities. When all vertices have been
  considered or the number of new inequalities already found exceeds the value
  of  ineqThreshold, a new approximating polyhedron in calculated. The default
  for ineqThreshold is 200. Roughly speaking, a large threshold means shifting
  work  from  polymake  to GAP, a small one means more calls of (and work for)
  polymake.
  
  If  the  value  of InfoHAPcryst (1.3-1) is 2 or more, for each approximation
  the  number  of  vertices  of the approximation, the number of vertices that
  have  to be considered during the calculation, the number of facets, and new
  inequalities is shown.
  
  Note  that  the  algorithm  chooses vertices in random order and also writes
  inequalities for polymake in random order.
  
  ---------------------------  Example  ----------------------------
    gap> a0:=[[ 1, 0, 0, 0, 0, 0, 0 ], [ 0, -1, 0, 0, 0, 0, 0 ], 
    >     [ 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0 ], 
    >     [ 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, -1, -1, 0 ],
    >     [ -1/2, 0, 0, 1/6, 0, 0, 1 ] 
    >     ];;
    gap> a1:=[[ 0, -1, 0, 0, 0, 0, 0 ],[ 0, 0, -1, 0, 0, 0, 0 ],
    >         [ 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0 ], 
    >         [ 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0 ],
    >         [ 0, 0, 0, 0, 1/3, -1/3, 1 ] 
    >        ];;
    gap> trans:=List(Group((1,2,3,4,5,6)),g->
    >           TranslationOnRightFromVector(Permuted([1,0,0,0,0,0],g)));;
    gap> S:=AffineCrystGroupOnRight(Concatenation(trans,[a0,a1]));
    <matrix group with 8 generators>
    gap> SetInfoLevel(InfoHAPcryst,2);
    gap> FundamentalDomainBieberbachGroup(S:ineqThreshold:=10);
    #I  v: 104/104 f:15
    #I  new: 201
    #I  v: 961/961 f:58
    #I  new: 20
    #I  v: 1143/805 f:69
    #I  new: 12
    #I  v: 1059/555 f:64
    #I  new: 15
    #I  v: 328/109 f:33
    #I  new: 12
    #I  v: 336/58 f:32
    #I  new: 0
    <polymake object>
    gap> FundamentalDomainBieberbachGroup(S:ineqThreshold:=1000);
    #I  v: 104/104 f:15
    #I  new: 149
    #I  v: 635/635 f:41
    #I  new: 115
    #I  v: 336/183 f:32
    #I  new: 0
    #I  out of inequalities
    <polymake object>
  ------------------------------------------------------------------
  
  4.1-3 FundamentalDomainFromGeneralPointAndOrbitPartGeometric
  
  > FundamentalDomainFromGeneralPointAndOrbitPartGeometric( v, orbit ) _method
  Returns:  a PolymakeObject
  
  This  uses an alternative algorithm based on geometric considerations. It is
  not  used  in  any  of the high-level methods. Let v be a vector and orbit a
  sufficiently  large  part  of  the orbit of v under a crystallographic group
  with  standard-  orthogonal  point  group (satisfying A^t=A^-1). A geometric
  algorithm  is then used to calculate the Dirichlet domain with respect to v.
  This  also  works  for crystallographic groups which are not Bieberbach. The
  point v has to have trivial stabilizer.
  The  intersection  of  the  full  orbit  with  the  unit  cube  around  v is
  sufficiently large.
  
  ---------------------------  Example  ----------------------------
    gap> G:=SpaceGroup(3,9);;
    gap> v:=[0,0,0];
    [ 0, 0, 0 ]
    gap> orbit:=OrbitStabilizerInUnitCubeOnRight(G,v).orbit;
    [ [ 0, 0, 0 ], [ 0, 0, 1/2 ] ]
    gap> fd:=FundamentalDomainFromGeneralPointAndOrbitPartGeometric(v,orbit);
    <polymake object>
    gap> Polymake(fd,"N_VERTICES");
    8
  ------------------------------------------------------------------
  
  4.1-4 IsFundamentalDomainStandardSpaceGroup
  
  > IsFundamentalDomainStandardSpaceGroup( poly, G ) ___________________method
  Returns:  true or false
  
  This  tests  if a PolymakeObject poly is a fundamental domain for the affine
  crystallographic group G in standard form.
  The  function  tests  the  following: First, does the orbit of any vertex of
  poly  have  a  point  inside  poly (if this is the case, false is returned).
  Second:  Is every facet of poly the image of a different facet under a group
  element which does not fix poly. If this is satisfied, true is returned.
  
  4.1-5 IsFundamentalDomainBieberbachGroup
  
  > IsFundamentalDomainBieberbachGroup( poly, G ) ______________________method
  Returns:  true, false or fail
  
  This  tests  if a PolymakeObject poly is a fundamental domain for the affine
  crystallographic  group G in standard form and if this group is torsion free
  (ie a Bieberbach group)
  It returns true if G is torsion free and poly is a fundamental domain for G.
  If  poly  is  not  a fundamental domain, false is returned regardless of the
  structure  of G. And if G is not torsion free, the method returns fail. If G
  is  polycyclic,  torsion  freeness  is  tested using a representation as pcp
  group. Otherwise the stabilisers of the faces of the fundamental domain poly
  are  calculated  (G  is torsion free if and only if it all these stabilisers
  are trivial).
  
  
  4.2 Face Lattice and Resolution
  
  For  Bieberbach groups (torsion free crystallographic groups), the following
  functions  calcualte free resolutions. This calculation is done by finding a
  fundamental  domain  for  the  group. For a description of the HapResolution
  datatype, see the Hap data types documentation or the experimental datatypes
  documentation HAPprog: Resolutions in Hap
  
  4.2-1 ResolutionBieberbachGroup
  
  > ResolutionBieberbachGroup( G[, v] ) ________________________________method
  Returns:  a HAPresolution
  
  Let  G  be  a  Bieberbach  group given as an AffineCrystGroupOnRight and v a
  vector.  Then  a  Dirichlet  domain  with  respect  to v is calculated using
  FundamentalDomainBieberbachGroup  (4.1-2). From this domain, a resolution is
  calculated    using    FaceLatticeAndBoundaryBieberbachGroup   (4.2-2)   and
  ResolutionFromFLandBoundary (4.2-3). If v is not given, the origin is used.
  
  ---------------------------  Example  ----------------------------
    gap> R:=ResolutionBieberbachGroup(SpaceGroup(3,9));
    Resolution of length 3 in characteristic
    0 for SpaceGroupOnRightBBNWZ( 3, 2, 2, 2, 2 ) .
    No contracting homotopy available.
    
    gap> List([0..3],Dimension(R));
    [ 1, 3, 3, 1 ]
    gap> R:=ResolutionBieberbachGroup(SpaceGroup(3,9),[1/2,0,0]);
    Resolution of length 3 in characteristic
    0 for SpaceGroupOnRightBBNWZ( 3, 2, 2, 2, 2 ) .
    No contracting homotopy available.
    
    gap> List([0..3],Dimension(R));
    [ 6, 12, 7, 1 ]
    
  ------------------------------------------------------------------
  
  4.2-2 FaceLatticeAndBoundaryBieberbachGroup
  
  > FaceLatticeAndBoundaryBieberbachGroup( poly, group ) _______________method
  Returns:  Record  with  entries  .hasse and .elts representing a part of the
            hasse diagram and a lookup table of group elements
  
  Let  group  be a torsion free AffineCrystGroupOnRight (that is, a Bieberbach
  group).  Given  a  PolymakeObject poly representing a fundamental domain for
  group,  this  method  uses polymaking to calculate the face lattice of poly.
  From  the  set  of  faces,  a system of representatives for group- orbits is
  chosen.  For  each representative, the boundary is then calculated. The list
  .elts  contains elements of group (in fact, it is even a set). The structure
  of the returned list .hasse is as follows:
  
  --    The  i-th  entry  contains  a  system  of  representatives for the i-1
        dimensional faces of poly.
  
  --    Each  face  is represented by a pair of lists [vertices,boundary]. The
        list  of  integers  vertices represents the vertices of poly which are
        contained  in  this  face. The enumeration is chosen such that an i in
        the    list    represents    the    i-th    entry    of    the    list
        Polymake(poly,"VERTICES");
  
  --    The  list  boundary represents the boundary of the respective face. It
        is  a list of pairs of integers [j,g]. The first entry lies between -n
        and  n,  where  n  is the number of faces of dimension i-1. This entry
        represents  a  face  of  dimension  i-1  (or its additive inverse as a
        module generator). The second entry g is the position of the matrix in
        .elts.
  
  This  representation  is  compatible  with  the  representation  of free Z G
  modules  in  Hap and this method essentially calculates a free resolution of
  group.  If  the  value  of  InfoHAPcryst  (1.3-1)  is  2 or more, additional
  information  about  the  number of faces in every codimension, the number of
  orbits  of  the  group  on the free module generated by those faces, and the
  time it took to calculate the orbit decomposition is output.
  
  ---------------------------  Example  ----------------------------
    gap> SetInfoLevel(InfoHAPcryst,2);
    gap> G:=SpaceGroup(3,165);
    SpaceGroupOnRightBBNWZ( 3, 6, 1, 1, 4 )
    gap> fd:=FundamentalDomainBieberbachGroup(G);
    <polymake object>
    gap> fl:=FaceLatticeAndBoundaryBieberbachGroup(fd,G);;
    #I  1(4/8): 0:00:00.004
    #I  2(5/18): 0:00:00.000
    #I  3(2/12): 0:00:00.000
    #I  Face lattice done ( 0:00:00.004). Calculating boundary
    #I  done ( 0:00:00.004) Reformating...
    gap> RecNames(fl);
    [ "hasse", "elts", "groupring" ]
    gap> fl.groupring;
    <free left module over Integers, and ring-with-one, with 10 generators>
  ------------------------------------------------------------------
  
  4.2-3 ResolutionFromFLandBoundary
  
  > ResolutionFromFLandBoundary( fl, group ) ___________________________method
  Returns:  Free resolution
  
  If  fl is the record output by FaceLatticeAndBoundaryBieberbachGroup (4.2-2)
  and group is the corresponding group, this function returns a HapResolution.
  Of course, fl has to be generated from a fundamental domain for group
  
  ---------------------------  Example  ----------------------------
    gap> G:=SpaceGroup(3,165);
    SpaceGroupOnRightBBNWZ( 3, 6, 1, 1, 4 )
    gap> fd:=FundamentalDomainBieberbachGroup(G);
    <polymake object>
    gap> fl:=FaceLatticeAndBoundaryBieberbachGroup(fd,G);;
    gap> ResolutionFromFLandBoundary(fl,G);
    Resolution of length 3 in characteristic
    0 for SpaceGroupOnRightBBNWZ( 3, 6, 1, 1, 4 ) .
    No contracting homotopy available.
    
    gap> ResolutionFromFLandBoundary(fl,G);
    Resolution of length 3 in characteristic
    0 for SpaceGroupOnRightBBNWZ( 3, 6, 1, 1, 4 ) .
    No contracting homotopy available.
    
    gap> List([0..4],Dimension(last));
    [ 2, 5, 4, 1, 0 ]
  ------------------------------------------------------------------