chap2.txt

  
  2 Cones and semigroups
  
  
  2.1 Cones
  
  This section introduces the toric commands which deal with cones and related
  combinatorial-geometric  objects.  Recall,  a  cone  is  a  strongly  convex
  polyhedral cone ([Ful93], page 4).
  
  2.1-1 InsideCone
  
  InsideCone( v, L )  function
  
  This  command  returns `true` if the vector v belongs to the interior of the
  (strongly convex polyhedral) cone generated by the vectors in L.
  
  This  procedure  does  not check if L generates a strongly convex polyhedral
  cone.
  
    Example  
    gap> L:=[[1,0,0],[1,1,0],[1,1,1],[1,0,1]];; v:=[0,0,1];;
    gap> InsideCone(v,L);
    false
    gap> L:=[[1,0],[3,4]];;
    gap> v:=[1,-7]; InsideCone(v,L);
    [ 1, -7 ]
    false
    gap> v:=[4,-3]; InsideCone(v,L);
    [ 4, -3 ]
    false
    gap> v:=[4,-4]; InsideCone(v,L);
    [ 4, -4 ]
    false
    gap> v:=[4,1]; InsideCone(v,L);
    [ 4, 1 ]
    true
  
  
  2.1-2 InDualCone
  
  InDualCone( v, L )  function
  
  This  command  returns `true` if v belongs to the dual of the cone generated
  by the vectors in L.
  
    Example  
    gap> L:=[[1,0,0],[1,1,0],[1,1,1],[1,0,1]];; v:=[0,0,1];;
    gap> InDualCone(v,L);
    true
    gap> L:=[[1,0],[3,4]];
    [ [ 1, 0 ], [ 3, 4 ] ]
    gap> v:=[1,-7]; InDualCone(v,L);
    [ 1, -7 ]
    false
    gap> v:=[4,-3]; InDualCone(v,L);
    [ 4, -3 ]
    true
    gap> v:=[4,-4]; InDualCone(v,L);
    [ 4, -4 ]
    false
    gap> v:=[4,1]; InDualCone(v,L);
    [ 4, 1 ]
    true
  
  
  2.1-3 PolytopeLatticePoints
  
  PolytopeLatticePoints( A, Perps )  function
  
  Input:   Perps=[v_1,...,v_k]   is  the  list  of  ``inward  normal"  vectors
  perpendicular to the walls of a polytope P in the vector space L_0^*⊗ Q,
  A=[a_1,...,a_k]  is  a k-tuple of integers, where a_i denotes the amount the
  i-th  ``wall"  (defined  by the normal v_i) is shifted from the origin (each
  a_i is assumed non-negative).
  For   example,   the  polytope  P  with  faces  [x=0,  x=a,  y=0,  y=b]  has
  Perps=[[1,0],[-1,0],[0,1],[0,-1]] and A=[0,a,0,b].
  Output: the list of points in P ∩ L_0^*.
  
    Example  
    gap> Perps:=[[1,0],[-1,0],[0,1],[0,-1]];
    [ [ 1, 0 ], [ -1, 0 ], [ 0, 1 ], [ 0, -1 ] ]
    gap> A:=[0,4,0,3];
    [ 0, 4, 0, 3 ]
    gap> PolytopeLatticePoints(A,Perps);
    [ [ 0, 0 ], [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 1, 0 ], [ 1, 1 ], [ 1, 2 ],
      [ 1, 3 ], [ 2, 0 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 0 ], [ 3, 1 ],
      [ 3, 2 ], [ 3, 3 ], [ 4, 0 ], [ 4, 1 ], [ 4, 2 ], [ 4, 3 ] ]
    gap> Length(last);
    20
  
  
  2.1-4 Faces
  
  Faces( Rays )  function
  
  Input: Rays is a list of rays for the fan ∆
  Output: All the normals to the faces (hyperplanes of the cone).
  
    Example  
    gap> Cones1:=[[[2,-1],[-1,2]],[[-1,2],[-1,-1]],[[-1,-1],[2,-1]]];;
    gap> Faces(Cones1[1]);
    [ [ 1/2, 1 ], [ 2, 1 ] ]
    gap> Faces(Cones1[2]);
    [ [ -2, -1 ], [ -1, 1 ] ]
    gap> Cones2:=[[[ 2,0,0],[0,2,0],[0,0,2]], [[2,0,0], [0,2,0], [2,-2,1],[1,2,-2]]];;
    gap> Faces(Cones2[1]);
    [ [ 0, 0, 1 ], [ 0, 1, 0 ], [ 1, 0, 0 ] ]
    gap> Faces(Cones2[2]);
    [ [ 1/3, 5/6, 1 ], [ 1/2, 0, -1 ], [ 2, 0, 1 ] ]
  
  
  2.1-5 ConesOfFan
  
  ConesOfFan( Delta, k )  function
  
  Input: Delta is the fan of cones,
  k is the dimension of the cones desired.
  Output: The k-dimensional cones in the fan.
  
  2.1-6 NumberOfConesOfFan
  
  NumberOfConesOfFan( Delta, k )  function
  
  Input: Delta is the fan of cones in V=Q^n,
  k is the dimension of the cones counted.
  Output: The number of k-dimensional cones in the fan.
  
  Idea:  The  fan  Delta  is  represented  as a set of maximal cones. For each
  maximal  cone, look at the k-dimensional faces obtained by taking n choose k
  subsets  of  the  rays describing the cone. Certain of these k-subsets yield
  the desired cones.
  
    Example  
    gap> Delta0:=[ [ [2,0,0],[0,2,0],[0,0,2] ], [ [2,0,0],[0,2,0],[2,-2,1],[1,2,-2] ] ];;
    gap> NumberOfConesOfFan(Delta0,2);
    6
    gap> ConesOfFan(Delta0,2);
    [ [ [ 0, 0, 2 ], [ 0, 2, 0 ] ], [ [ 0, 0, 2 ], [ 2, 0, 0 ] ], 
      [ [ 0, 2, 0 ], [ 1, 2, -2 ] ], [ [ 0, 2, 0 ], [ 2, -2, 1 ] ],
      [ [ 0, 2, 0 ], [ 2, 0, 0 ] ], [ [ 1, 2, -2 ], [ 2, -2, 1 ] ] ]
    gap> ConesOfFan(Delta0,1);
    [ [ [ 0, 0, 2 ] ], [ [ 0, 2, 0 ] ], [ [ 1, 2, -2 ] ], 
      [ [ 2, -2, 1 ] ], [ [ 2, 0, 0 ] ] ]
    gap> NumberOfConesOfFan(Delta0,1);
    5
  
  
  2.1-7 ToricStar
  
  ToricStar( sigma, Delta )  function
  
  Input:  sigma is a cone in the fan, represented by its set of maximal (i.e.,
  highest dimensional) cones.
  Delta is the fan of cones in V=Q^n.
  Output:  The  star  of the cone sigma in Delta, i.e., the cones τ which have
  sigma as a face.
  
    Example  
    gap> MaxCones:=[ [ [2,0,0],[0,2,0],[0,0,2] ], 
    >                 [ [2,0,0],[0,2,0],[2,-2,1],[1,2,-2] ] ];;
    gap> #this is the set of maximal cones in the fan Delta
    gap> ToricStar([[1,0]],MaxCones);
    [  ]
    gap> ToricStar([[2,0,0],[0,2,0]],MaxCones);
    [ [ [ 0, 2, 0 ], [ 2, 0, 0 ] ], [ [ 2, 0, 0 ], [ 0, 2, 0 ], [ 0, 0, 2 ] ],
      [ [ 2, 0, 0 ], [ 0, 2, 0 ], [ 2, -2, 1 ], [ 1, 2, -2 ] ] ]
    gap> MaxCones:=[ [ [2,0,0],[0,2,0],[0,0,2] ], [ [2,0,0],[0,2,0],[1,1,-2] ] ];;
    gap> ToricStar([[2,0,0],[0,2,0]],MaxCones);
    [ [ [ 0, 2, 0 ], [ 2, 0, 0 ] ], [ [ 2, 0, 0 ], [ 0, 2, 0 ], [ 0, 0, 2 ] ],
      [ [ 2, 0, 0 ], [ 0, 2, 0 ], [ 1, 1, -2 ] ] ]
    gap> ToricStar([[1,0]],MaxCones);
    [  ]
  
  
  
  2.2 Semigroups
  
  2.2-1 DualSemigroupGenerators
  
  DualSemigroupGenerators( L )  function
  
  Input: L is a list of integral n-vectors generating a cone σ.
  Output: the generators of S_σ,
  
  Idea:  let M be the maximum of the absolute values of the coordinates of the
  L[i]'s, for each vector v in [1..M]^n, test if v is in the dual cone σ^*. If
  so,  add  v  to list of possible generators. Once this for loop is finished,
  one  can  check  this  list for redundant generators. The trick is to simply
  omit  those  elements  which  are of the form d_1+d_2, where d_1 and d_2 are
  ``small" elements in the integral dual cone.
  
  This  program  is  not  very  efficient  and  should  not be used in ``large
  examples''  involving  semigroups  with ``many'' generators. For example, if
  you       take       L:=[[1,2,3,4],[0,1,0,7],[3,1,0,2],[0,0,1,0]];      then
  DualSemigroupGenerators(L); can exhaust GAP's memory allocation.
  
    Example  
    gap> L:=[[1,0],[3,4]];; DualSemigroupGenerators([[1,0],[3,4]]);
    [ [ 0, 0 ], [ 0, 1 ], [ 1, 0 ], [ 2, -1 ], [ 3, -2 ], [ 4, -3 ] ]
    gap> L:=[[1,0,0],[1,1,0],[1,1,1],[1,0,1]];;
    gap> DualSemigroupGenerators(L);
    [ [ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 1, 0 ], [ 1, -1, 0 ], [ 1, 0, -1 ] ]