  
  [1m[4m[31m2. Coding theory functions in [1mGAP[1m[4m[31m[0m
  
  This  chapter  will  recall  from the [1mGAP[0m4.4.5 manual some of the [1mGAP[0m 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
  
  --    [22m[32mAClosestVectorCombinationsMatFFEVecFFE[0m,
  
  --    [22m[32mAClosestVectorCombinationsMatFFEVecFFECoords[0m,
  
  --    [22m[32mCosetLeadersMatFFE[0m,
  
  --    [22m[32mDistancesDistributionMatFFEVecFFE[0m,
  
  --    [22m[32mDistancesDistributionVecFFEsVecFFE[0m,
  
  --    [22m[32mDistanceVecFFE[0m and [22m[32mWeightVecFFE[0m,
  
  --    [22m[32mConwayPolynomial[0m and [22m[32mIsCheapConwayPolynomial[0m,
  
  --    [22m[32mIsPrimitivePolynomial[0m, and [22m[32mRandomPrimitivePolynomial[0m.
  
  However,  the  [1mGAP[0m  command [22m[32mPrimitivePolynomial[0m returns an integer primitive
  polynomial not the finite field kind.
  
  
  [1m[4m[31m2.1 Distance functions[0m
  
  [1m[4m[31m2.1-1 AClosestVectorCombinationsMatFFEVecFFE[0m
  
  [1m[34m> AClosestVectorCombinationsMatFFEVecFFE( [0m[22m[34mmat, F, vec, r, st[0m[1m[34m ) _____[0mfunction
  
  This  command  runs  through the [22m[34mF[0m-linear combinations of the vectors in the
  rows of the matrix [22m[34mmat[0m that can be written as linear combinations of exactly
  [22m[34mr[0m  rows  (that  is without using zero as a coefficient) and returns a vector
  from  these that is closest to the vector [22m[34mvec[0m. The length of the rows of [22m[34mmat[0m
  and  the  length  of  [22m[34mvec[0m must be equal, and all elements must lie in [22m[34mF[0m. The
  rows  of  [22m[34mmat[0m must be linearly independent. If it finds a vector of distance
  at  most  [22m[34mst[0m, which must be a nonnegative integer, then it stops immediately
  and returns this vector.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> F:=GF(3);;[0m
    [22m[35mgap> x:= Indeterminate( F );; pol:= x^2+1;[0m
    [22m[35mx_1^2+Z(3)^0[0m
    [22m[35mgap> C := GeneratorPolCode(pol,8,F);[0m
    [22m[35ma cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)[0m
    [22m[35mgap> v:=Codeword("12101111");[0m
    [22m[35m[ 1 2 1 0 1 1 1 1 ][0m
    [22m[35mgap> v:=VectorCodeword(v);[0m
    [22m[35m[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ][0m
    [22m[35mgap> G:=GeneratorMat(C);[0m
    [22m[35m[ [ Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],[0m
    [22m[35m  [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],[0m
    [22m[35m  [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],[0m
    [22m[35m  [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],[0m
    [22m[35m  [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],[0m
    [22m[35m  [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ][0m
    [22m[35mgap> AClosestVectorCombinationsMatFFEVecFFE(G,F,v,1,1);[0m
    [22m[35m[ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ][0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.1-2 AClosestVectorComb..MatFFEVecFFECoords[0m
  
  [1m[34m> AClosestVectorComb..MatFFEVecFFECoords( [0m[22m[34mmat, F, vec, r, st[0m[1m[34m ) _____[0mfunction
  
  [22m[32mAClosestVectorCombinationsMatFFEVecFFECoords[0m  returns  a  two  element  list
  containing      (a)      the      same      closest     vector     as     in
  [22m[32mAClosestVectorCombinationsMatFFEVecFFE[0m,  and  (b)  a vector [22m[34mv[0m with exactly [22m[34mr[0m
  non-zero entries, such that v*mat is the closest vector.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> F:=GF(3);;[0m
    [22m[35mgap> x:= Indeterminate( F );; pol:= x^2+1;[0m
    [22m[35mx_1^2+Z(3)^0[0m
    [22m[35mgap> C := GeneratorPolCode(pol,8,F);[0m
    [22m[35ma cyclic [8,6,1..2]1..2 code defined by generator polynomial over GF(3)[0m
    [22m[35mgap> v:=Codeword("12101111"); v:=VectorCodeword(v);;[0m
    [22m[35m[ 1 2 1 0 1 1 1 1 ][0m
    [22m[35mgap> G:=GeneratorMat(C);;[0m
    [22m[35mgap> AClosestVectorCombinationsMatFFEVecFFECoords(G,F,v,1,1);[0m
    [22m[35m[ [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ],[0m
    [22m[35m  [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ] ][0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.1-3 DistancesDistributionMatFFEVecFFE[0m
  
  [1m[34m> DistancesDistributionMatFFEVecFFE( [0m[22m[34mvecs, vec[0m[1m[34m ) ___________________[0mfunction
  
  [22m[32mDistancesDistributionMatFFEVecFFE[0m  returns the distances distribution of the
  vector  [22m[34mvec[0m  to the vectors in the list [22m[34mvecs[0m. 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 [22m[34mvec[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;[0m
    [22m[35mgap> 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) ],[0m
    [22m[35m>   [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],[0m
    [22m[35m>   [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],[0m
    [22m[35m>   [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],[0m
    [22m[35m>   [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],[0m
    [22m[35m>   [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ];;[0m
    [22m[35mgap> DistancesDistributionMatFFEVecFFE(vecs,GF(3),v);[0m
    [22m[35m[ 0, 4, 6, 60, 109, 216, 192, 112, 30 ][0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.1-4 DistancesDistributionVecFFEsVecFFE[0m
  
  [1m[34m> DistancesDistributionVecFFEsVecFFE( [0m[22m[34mvecs, vec[0m[1m[34m ) __________________[0mfunction
  
  [22m[32mDistancesDistributionVecFFEsVecFFE[0m returns the distances distribution of the
  vector  [22m[34mvec[0m  to the vectors in the list [22m[34mvecs[0m. 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 [22m[34mvecs[0m that have distance i+1 to [22m[34mvec[0m.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;[0m
    [22m[35mgap> 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) ],[0m
    [22m[35m>   [ 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3) ],[0m
    [22m[35m>   [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],[0m
    [22m[35m>   [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],[0m
    [22m[35m>   [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0, 0*Z(3) ],[0m
    [22m[35m>   [ 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3), Z(3)^0 ] ];;[0m
    [22m[35mgap> DistancesDistributionVecFFEsVecFFE(vecs,v);[0m
    [22m[35m[ 0, 0, 0, 0, 0, 4, 0, 1, 1 ][0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.1-5 WeightVecFFE[0m
  
  [1m[34m> WeightVecFFE( [0m[22m[34mvec[0m[1m[34m ) ______________________________________________[0mfunction
  
  [22m[32mWeightVecFFE[0m  returns  the  weight  of the finite field vector [22m[34mvec[0m, i.e. the
  number of nonzero entries.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> v:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;[0m
    [22m[35mgap> WeightVecFFE(v);[0m
    [22m[35m7[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m2.1-6 DistanceVecFFE[0m
  
  [1m[34m> DistanceVecFFE( [0m[22m[34mvec1, vec2[0m[1m[34m ) _____________________________________[0mfunction
  
  The [22m[36mHamming metric[0m 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). [22m[32mDistanceVecFFE[0m returns the distance between the two vectors
  [22m[34mvec1[0m  and  [22m[34mvec2[0m, which must have the same length and whose elements must lie
  in  a common field. The distance is the number of places where [22m[34mvec1[0m and [22m[34mvec2[0m
  differ.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35mgap> v1:=[ Z(3)^0, Z(3), Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;[0m
    [22m[35mgap> v2:=[ Z(3), Z(3)^0, Z(3)^0, 0*Z(3), Z(3)^0, Z(3)^0, Z(3)^0, Z(3)^0 ];;[0m
    [22m[35mgap> DistanceVecFFE(v1,v2);[0m
    [22m[35m2[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m2.2 Other functions[0m
  
  We basically repeat, with minor variation, the material in the [1mGAP[0m manual or
  from                 Frank                 Luebeck's                 website
  [34mhttp://www.math.rwth-aachen.de:8001/~Frank.Luebeck/data/ConwayPol[0m  on Conway
  polynomials.  The  [1m[46mprime  fields[0m: If p>= 2 is a prime then GF(p) denotes the
  field Z}/pZ}, with addition and multiplication performed mod p.
  
  The  [1m[46mprime  power  fields[0m:  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 [1m[46mdefining polynomial[0m 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^times  is a cyclic group. An alphain F is called a [1m[46mprimitive element[0m if it
  is  a  generator  of  F^times. A defining polynomial f(x) of F is said to be
  [1m[46mprimitive[0m if it has a root in F which is a primitive element.
  
  [1m[4m[31m2.2-1 ConwayPolynomial[0m
  
  [1m[34m> ConwayPolynomial( [0m[22m[34mp, n[0m[1m[34m ) _________________________________________[0mfunction
  
  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  [1m[46mConway  polynomial[0m  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).
  
  [22m[32mConwayPolynomial(p,n)[0m returns the polynomial f_p,r(x) defined above.
  
  [22m[32mIsCheapConwayPolynomial(p,n)[0m  returns  true if [22m[32mConwayPolynomial( p, n )[0m 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.
  
  [1m[4m[31m2.2-2 RandomPrimitivePolynomial[0m
  
  [1m[34m> RandomPrimitivePolynomial( [0m[22m[34mF, n[0m[1m[34m ) ________________________________[0mfunction
  
  For  a  finite  field  [22m[34mF[0m  and  a  positive integer [22m[34mn[0m this function returns a
  primitive  polynomial  of degree [22m[34mn[0m over [22m[34mF[0m, that is a zero of this polynomial
  has maximal multiplicative order |F|^n-1.
  
  [22m[32mIsPrimitivePolynomial(f)[0m  can  be used to check if a univariate polynomial [22m[34mf[0m
  is primitive or not.
  
