2. Coding theory functions in GAP
  
  This  chapter  will  recall  from the GAP4.4.5 manual some of the GAP coding
  theory  and  finite  field functions useful for coding theory. Some of these
  functions are partially written in C for speed. The main functions are
  
  --    AClosestVectorCombinationsMatFFEVecFFE,
  
  --    AClosestVectorCombinationsMatFFEVecFFECoords,
  
  --    CosetLeadersMatFFE,
  
  --    DistancesDistributionMatFFEVecFFE,
  
  --    DistancesDistributionVecFFEsVecFFE,
  
  --    DistanceVecFFE and WeightVecFFE,
  
  --    ConwayPolynomial and IsCheapConwayPolynomial,
  
  --    IsPrimitivePolynomial, and RandomPrimitivePolynomial.
  
  However,  the  GAP  command PrimitivePolynomial returns an integer primitive
  polynomial not the finite field kind.
  
  
  2.1 Distance functions
  
  2.1-1 AClosestVectorCombinationsMatFFEVecFFE
  
  > AClosestVectorCombinationsMatFFEVecFFE( mat, F, vec, r, st ) _____function
  
  This  command  runs  through the F-linear combinations of the vectors in the
  rows of the matrix mat that can be written as linear combinations of exactly
  r  rows  (that  is without using zero as a coefficient) and returns a vector
  from  these that is closest to the vector vec. The length of the rows of mat
  and  the  length  of  vec must be equal, and all elements must lie in F. The
  rows  of  mat must be linearly independent. If it finds a vector of distance
  at  most  st, which must be a nonnegative integer, then it stops immediately
  and returns this vector.
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(3);;
    gap> x:= Indeterminate( F );; pol:= x^2+1;
    x_1^2+Z(3)^0
    gap> C := GeneratorPolCode(pol,8,F);
    a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)
    gap> v:=Codeword("12101111");
    [ 1 2 1 0 1 1 1 1 ]
    gap> v:=VectorCodeword(v);
    [ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ]
    gap> G:=GeneratorMat(C);
    [ [ Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],
      [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],
      [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],
      [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],
      [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],
      [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ]
    gap> AClosestVectorCombinationsMatFFEVecFFE(G,F,v,1,1);
    [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ]
  ------------------------------------------------------------------
  
  2.1-2 AClosestVectorComb..MatFFEVecFFECoords
  
  > AClosestVectorComb..MatFFEVecFFECoords( mat, F, vec, r, st ) _____function
  
  AClosestVectorCombinationsMatFFEVecFFECoords  returns  a  two  element  list
  containing      (a)      the      same      closest     vector     as     in
  AClosestVectorCombinationsMatFFEVecFFE,  and  (b)  a vector v with exactly r
  non-zero entries, such that v*mat is the closest vector.
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(3);;
    gap> x:= Indeterminate( F );; pol:= x^2+1;
    x_1^2+Z(3)^0
    gap> C := GeneratorPolCode(pol,8,F);
    a cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)
    gap> v:=Codeword("12101111"); v:=VectorCodeword(v);;
    [ 1 2 1 0 1 1 1 1 ]
    gap> G:=GeneratorMat(C);;
    gap> AClosestVectorCombinationsMatFFEVecFFECoords(G,F,v,1,1);
    [ [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ],
      [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ] ]
  ------------------------------------------------------------------
  
  2.1-3 DistancesDistributionMatFFEVecFFE
  
  > DistancesDistributionMatFFEVecFFE( mat, f, vec ) _________________function
  
  DistancesDistributionMatFFEVecFFE  returns the distances distribution of the
  vector  vec  to the vectors in the vector space generated by the rows of the
  matrix  mat  over the finite field f. All vectors must have the same length,
  and all elements must lie in a common field. The distances distribution is a
  list  d  of  length Length(vec)+1, such that the value d[i] is the number of
  vectors in vecs that have distance i+1 to vec.
  
  ---------------------------  Example  ----------------------------
    gap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;
    gap> vecs:=[ [ Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],
    >   [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],
    >   [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],
    >   [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],
    >   [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],
    >   [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ];;
    gap> DistancesDistributionMatFFEVecFFE(vecs,GF(3),v);
    [ 0, 4, 6, 60, 109, 216, 192, 112, 30 ]
  ------------------------------------------------------------------
  
  2.1-4 DistancesDistributionVecFFEsVecFFE
  
  > DistancesDistributionVecFFEsVecFFE( vecs, vec ) __________________function
  
  DistancesDistributionVecFFEsVecFFE returns the distances distribution of the
  vector  vec  to the vectors in the list vecs. All vectors must have the same
  length,  and  all  elements  must  lie  in  a  common  field.  The distances
  distribution  is  a list d of length Length(vec)+1, such that the value d[i]
  is the number of vectors in vecs that have distance i+1 to vec.
  
  ---------------------------  Example  ----------------------------
    gap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;
    gap> vecs:=[ [ Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],
    >   [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],
    >   [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],
    >   [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],
    >   [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],
    >   [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ];;
    gap> DistancesDistributionVecFFEsVecFFE(vecs,v);
    [ 0, 0, 0, 0, 0, 4, 0, 1, 1 ]
  ------------------------------------------------------------------
  
  2.1-5 WeightVecFFE
  
  > WeightVecFFE( vec ) ______________________________________________function
  
  WeightVecFFE  returns  the  weight  of the finite field vector vec, i.e. the
  number of nonzero entries.
  
  ---------------------------  Example  ----------------------------
    gap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;
    gap> WeightVecFFE(v);
    7
  ------------------------------------------------------------------
  
  2.1-6 DistanceVecFFE
  
  > DistanceVecFFE( vec1, vec2 ) _____________________________________function
  
  The Hamming metric on GF(q)^n is the function
  
  
       dist((v_1,...,v_n),(w_1,...,w_n)) =|\{i\in [1..n]\ |\ v_i\not=
       w_i\}|.
  
  
  This  is  also  called  the  (Hamming)  distance between v=(v_1,...,v_n) and
  w=(w_1,...,w_n). DistanceVecFFE returns the distance between the two vectors
  vec1  and  vec2, which must have the same length and whose elements must lie
  in  a common field. The distance is the number of places where vec1 and vec2
  differ.
  
  ---------------------------  Example  ----------------------------
    gap> v1:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;
    gap> v2:=[ Z(3), Z(3)^0, Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;
    gap> DistanceVecFFE(v1,v2);
    2
  ------------------------------------------------------------------
  
  
  2.2 Other functions
  
  We basically repeat, with minor variation, the material in the GAP manual or
  from                 Frank                 Luebeck's                 website
  http://www.math.rwth-aachen.de:8001/~Frank.Luebeck/data/ConwayPol  on Conway
  polynomials.  The  prime  fields: If p>= 2 is a prime then GF(p) denotes the
  field Z}/pZ}, with addition and multiplication performed mod p.
  
  The  prime  power  fields:  Suppose  q=p^r  is  a  prime power, r>1, and put
  F=GF(p).  Let  F[x]  denote  the ring of all polynomials over F and let f(x)
  denote  a monic irreducible polynomial in F[x] of degree r. The quotient E =
  F[x]/(f(x))=  F[x]/f(x)F[x]  is  a  field with q elements. If f(x) and E are
  related  in  this way, we say that f(x) is the defining polynomial of E. Any
  defining polynomial factors completely into distinct linear factors over the
  field it defines.
  
  For any finite field F, the multiplicative group of non-zero elements F^x is
  a  cyclic  group.  An  alpha  in  F is called a primitive element if it is a
  generator of F^x. A defining polynomial f(x) of F is said to be primitive if
  it has a root in F which is a primitive element.
  
  2.2-1 ConwayPolynomial
  
  > ConwayPolynomial( p, n ) _________________________________________function
  
  A   standard   notation   for  the  elements  of  GF(p)  is  given  via  the
  representatives  0, ..., p-1 of the cosets modulo p. We order these elements
  by  0  <  1  < 2 < ... < p-1. We introduce an ordering of the polynomials of
  degree r over GF(p). Let g(x) = g_rx^r + ... + g_0 and h(x) = h_rx^r + ... +
  h_0  (by  convention, g_i=h_i=0 for i > r). Then we define g < h if and only
  if  there is an index k with g_i = h_i for i > k and (-1)^r-k g_k < (-1)^r-k
  h_k.
  
  The  Conway  polynomial  f_p,r(x)  for GF(p^r) is the smallest polynomial of
  degree r with respect to this ordering such that:
  
  --    f_p,r(x) is monic,
  
  --    f_p,r(x)  is  primitive,  that  is,  any  zero  is  a generator of the
        (cyclic) multiplicative group of GF(p^r),
  
  --    for each proper divisor m of r we have that f_p,m(x^(p^r-1) / (p^m-1))
        = 0 mod f_p,r(x); that is, the (p^r-1) / (p^m-1)-th power of a zero of
        f_p,r(x) is a zero of f_p,m(x).
  
  ConwayPolynomial(p,n) returns the polynomial f_p,r(x) defined above.
  
  IsCheapConwayPolynomial(p,n)  returns  true if ConwayPolynomial( p, n ) will
  give  a  result  in  reasonable  time.  This  is  either  the case when this
  polynomial is pre-computed, or if n,p are not too big.
  
  2.2-2 RandomPrimitivePolynomial
  
  > RandomPrimitivePolynomial( F, n ) ________________________________function
  
  For  a  finite  field  F  and  a  positive integer n this function returns a
  primitive  polynomial  of degree n over F, that is a zero of this polynomial
  has maximal multiplicative order |F|^n-1.
  
  IsPrimitivePolynomial(f)  can  be used to check if a univariate polynomial f
  is primitive or not.