GAP programs

All my code linked to on this page is copylefted.

Some GAP programs I've written:
• putstform.gap GAP code for a program whose input is a matrix Mat (assumed to be kxn of full rank), and whose output is the product of elementary matrices needed to put Mat in row-reduced echelon form. It also returns a column permutation needed to make the left-most kxk block the identity. For examples, see putstform_examples.gap.
  

• golay12.gap.
  Decodes the Golay [12,6,6] code using the Steiner system S(5,6,12) and the MINIMOG. This package uses GUAVA.

  Example commands to start using this program:

  ##                Examples 
  RequirePackage("guava");
  Read("PATH/golay12.gap");  
  ##                The Golay code 12,6,6
  r1 :=[0, 0, 2, 2, 1, 1, 0, 0, 1, 1, 0, 0];;
  r2 :=[0, 0, 2, 1, 0, 0, 2, 1, 0, 0, 2, 1];;
  r3 :=[0, 2, 2, 0, 1, 0, 0, 1, 1, 0, 0, 1];;
  r4 :=[0, 2, 0, 2, 2, 0, 2, 2, 0, 0, 0, 1];;
  r5 :=[0, 0, 2, 0, 0, 1, 1, 0, 1, 0, 1, 1];;
  r6 :=[1, 0, 2, 0, 2, 0, 0, 2, 0, 0, 1, 1];;
  G:=[r1,r2,r3,r4,r5,r6];;
  C12:=GeneratorMatCode(G,GF(3));;
  wt6_codewords_wt( C12, 6);;
  wt9_codewords:=codewords_wt( C12, 9);;
  wt12_codewords_wt( C12, 12);;
  ##                 Examples
  ## decoding a random wt 12 codeword with 2 errors
  c:=Random(wt12_codewords);
  n1:=Random([1..12]);
  n2:=Random([1..12]);
  if n1=n2 and n1<12 then n2:=n1+1; fi;
  if n1=n2 and n1=12 then n2:=n1-1; fi;
  e:=[];
  for i in [1..12] do
   if i in [n1,n2] then e[i]:=1; else e[i]:=0; fi;
  od;
  r:=(e+c) mod 3;
  decode(r);
  ## decoding a random wt 9 codeword with 2 errors
  c:=Random(wt9_codewords);
  n1:=Random([1..12]);
  n2:=Random([1..12]);
  if n1=n2 and n1<12 then n2:=n1+1; fi;
  if n1=n2 and n1=12 then n2:=n1-1; fi;
  e:=[];
  for i in [1..12] do
   if i in [n1,n2] then e[i]:=1; else e[i]:=0; fi;
  od;
  r:=(e+c) mod 3;
  decode(r);
  ## decoding a random wt 6 codeword with 2 errors
  c:=Random(wt6_codewords);
  n1:=Random([1..12]);
  n2:=Random([1..12]);
  if n1=n2 and n1<12 then n2:=n1+1; fi;
  if n1=n2 and n1=12 then n2:=n1-1; fi;
  e:=[];
  for i in [1..12] do
   if i in [n1,n2] then e[i]:=1; else e[i]:=0; fi;
  od;
  r:=(e+c) mod 3;
  decode(r);
  

• comp_forms.gap.
  Computes a composition of the integral binary quadratic form [a1,b1,c1] with [a2,b2,c2]. The forms must have the same discriminant up to a perfect square factor. Synatx:

  composition([a1,b1,c1],[a2,b2,c2]);
  

  The algorithm used is that in D. Buell, Binary quadratic forms, Springer-Verlag, 1989.

• toric package (submitted for acceptance). It contains GAP functions to deal with toric varieties and cones in Qⁿ.
  Instead of installing, you can download the following file toric.gap
  to "PATH" on your computer and try out the following examples.

  ##                Examples 
  Read("PATH/toric.gap"); 
  dual_semigp_gens([[1,0],[3,4]]);
  J:=ideal_affine_toric_variety([[1,0],[3,4]]);
  GeneratorsOfIdeal(J);
  toric_points(2,GF(5));
  C:=toric_code([[1,0],[3,4]],GF(3));
  Display(GeneratorMat(C));
  divisor_polytope([6,6,0],[[2,-1],[-1,2],[-1,-1]]);
  Cones1:=[[[2,-1],[-1,2]],[[-1,2],[-1,-1]],[[-1,-1],[2,-1]]];Div:=[6,6,0];
  Rays1:=[[2,-1],[-1,2],[-1,-1]];
  riemann_roch(Div,Rays1); 
  P_Div:=divisor_polytope_lattice_points(Div,Rays1);
  Cones2:=[ [ [2,0,0],[0,2,0],[0,0,2] ], [ [2,0,0],[0,2,0],[2,-2,1],[1,2,-2] ] ];
  faces(Cones2[1]); 
  faces(Cones2[2]); 
  number_of_cones_dim(Cones2,1);  
  number_of_cones_dim(Cones2,2);  
  number_of_cones_dim(Cones2,3); 
  star([[1,0]],Cones2);
  Cones3:=[ [ [2,0,0],[0,2,0],[0,0,2] ], [ [2,0,0],[0,2,0],[1,1,-2] ] ];
  star([[2,0,0],[0,2,0]],Cones3);
  subcones_of_fan(Cones2,1);
  subcones_of_fan(Cones3,2); 
  betti_number(Cones1,1);
  cardinality_of_X(Cones1,3);
  euler_characteristic(Cones1);
  

  See the paper with H. Verrill for more details.

• poly2finite_field.gap.
  (Actually this was pieced together from several emails sent to me by Alexander Hulpke, so he is more of the author.) Assumes f is defined over GF(q) and returns f mod an irreducible polynomial of degree d in GF(q)[x], as a element of GF(q^d). This algorithm is deterministic.

  ##                Example
  Read("PATH//poly2finite_field.gap");
  x:=X(GF(9),"x");
  f:=x^7+x^3+x+1;
  DefaultField(CoefficientsOfUnivariatePolynomial(f));
  as:=RootsOfUPol(GF(3^7),f);
  a:=Minimum(as);
  pol:=x^2+x+1;
  Value(pol,a);
  HomToFF(pol,f);
  

• orbital_integral.gap.
  Very simple commands to compute orbital integrals and basis class functions for a finite group G. Examples are given in the *.gap file.

• schurindex.gap.
  The Schur index is a measure of the size of the smallest field a matrix representation can be defined over relative to the field generated by the character values of that representation. The GAP program here uses some theorems to give an upper bound only. (But when the Schur index is 1, this is often sufficient.) See the test in Corollary 31 of chapter 22 of Berkovich+Zhmud, Characters of Finite Groups, vol 2.

• shanks_babystep.gap.
  Shank's baby step giant step method for computing discrete logs in GAP. Also contains programs to return [average] number of steps the algorithm performs.

  ##Example
  n:=NextPrimeInt(10000);;
  a:=PrimitiveRootMod(n);;
  b:=Random([2..n-1]);;
  x:=DL_shanks(a,b,n);;
  b=a^x mod n;
  # true 
  

  Other examples are given in the *.gap file.

• lfsrs.gap.
  Programs dealing with linear feedback shift-register sequences.

• curves.gap.
  Some programs dealing with planar curves and divisors in GAP. For examples, see curves_examples.gap.

Last updated 12-20-2004.

This page is at the url: http://cadigweb.ew.usna.edu/~wdj/gap/gap_stuff.html