7. Bounds on codes, special matrices and miscellaneous functions
  
  In  this chapter we describe functions that determine bounds on the size and
  minimum  distance of codes (Section 7.1), functions that determine bounds on
  the  size  and  covering  radius of codes (Section 7.2), functions that work
  with  special  matrices GUAVA needs for several codes (see Section 7.3), and
  constructing codes or performing calculations with codes (see Section 7.5).
  
  
  7.1 Distance bounds on codes
  
  This  section  describes  the  functions  that calculate estimates for upper
  bounds  on  the  size  and minimum distance of codes. Several algorithms are
  known to compute a largest number of words a code can have with given length
  and  minimum  distance.  It  is important however to understand that in some
  cases  the  true upper bound is unknown. A code which has a size equalto the
  calculated  upper  bound may not have been found. However, codes that have a
  larger size do not exist.
  
  A  second  way  to obtain bounds is a table. In GUAVA, an extensive table is
  implemented for linear codes over GF(2), GF(3) and GF(4). It contains bounds
  on  the  minimum  distance  for given word length and dimension. It contains
  entries  for  word  lengths less than or equal to 257, 243 and 256 for codes
  over  GF(2),  GF(3) and GF(4) respectively. These entries were obtained from
  Brouwer's  tables  as of 11 May 2006. For the latest information, please see
  A. E. Brouwer's tables [Bro06] on the internet.
  
  Firstly,  we  describe  functions  that compute specific upper bounds on the
  code  size  (see  UpperBoundSingleton  (7.1-1),  UpperBoundHamming  (7.1-2),
  UpperBoundJohnson   (7.1-3),   UpperBoundPlotkin   (7.1-4),  UpperBoundElias
  (7.1-5) and UpperBoundGriesmer (7.1-6)).
  
  Next  we  describe  a function that computes GUAVA's best upper bound on the
  code size (see UpperBound (7.1-8)).
  
  Then  we  describe two functions that compute a lower and upper bound on the
  minimum  distance  of  a  code  (see  LowerBoundMinimumDistance  (7.1-9) and
  UpperBoundMinimumDistance (7.1-12)).
  
  Finally,  we describe a function that returns a lower and upper bound on the
  minimum  distance  with given parameters and a description of how the bounds
  were obtained (see BoundsMinimumDistance (7.1-13)).
  
  7.1-1 UpperBoundSingleton
  
  > UpperBoundSingleton( n, d, q ) ___________________________________function
  
  UpperBoundSingleton  returns  the  Singleton  bound  for a code of length n,
  minimum  distance  d  over  a  field  of  size q. This bound is based on the
  shortening  of  codes.  By  shortening  an  (n,  M,  d)  code  d-1 times, an
  (n-d+1,M,1)  code  results,  with  M <= q^n-d+1 (see ShortenedCode (6.1-9)).
  Thus
  
  
       M \leq q^{n-d+1}.
  
  
  Codes  that  meet  this  bound  are  called  maximum distance separable (see
  IsMDSCode (4.3-7)).
  
  ---------------------------  Example  ----------------------------
    gap> UpperBoundSingleton(4, 3, 5);
    25
    gap> C := ReedSolomonCode(4,3);; Size(C);
    25
    gap> IsMDSCode(C);
    true 
  ------------------------------------------------------------------
  
  7.1-2 UpperBoundHamming
  
  > UpperBoundHamming( n, d, q ) _____________________________________function
  
  The  Hamming bound (also known as the sphere packing bound) returns an upper
  bound on the size of a code of length n, minimum distance d, over a field of
  size q. The Hamming bound is obtained by dividing the contents of the entire
  space  GF(q)^n  by the contents of a ball with radius lfloor(d-1) / 2rfloor.
  As  all these balls are disjoint, they can never contain more than the whole
  vector space.
  
  
       M \leq {q^n \over V(n,e)},
  
  
  where  M  is  the  maxmimum  number  of codewords and V(n,e) is equal to the
  contents  of  a  ball of radius e (see SphereContent (7.5-5)). This bound is
  useful  for  small  values  of  d. Codes for which equality holds are called
  perfect (see IsPerfectCode (4.3-6)).
  
  ---------------------------  Example  ----------------------------
    gap> UpperBoundHamming( 15, 3, 2 );
    2048
    gap> C := HammingCode( 4, GF(2) );
    a linear [15,11,3]1 Hamming (4,2) code over GF(2)
    gap> Size( C );
    2048 
  ------------------------------------------------------------------
  
  7.1-3 UpperBoundJohnson
  
  > UpperBoundJohnson( n, d ) ________________________________________function
  
  The  Johnson  bound  is  an  improved  version  of  the  Hamming  bound (see
  UpperBoundHamming  (7.1-2)). In addition to the Hamming bound, it takes into
  account  the  elements of the space outside the balls of radius e around the
  elements of the code. The Johnson bound only works for binary codes.
  
  ---------------------------  Example  ----------------------------
    gap> UpperBoundJohnson( 13, 5 );
    77
    gap> UpperBoundHamming( 13, 5, 2);
    89   # in this case the Johnson bound is better 
  ------------------------------------------------------------------
  
  7.1-4 UpperBoundPlotkin
  
  > UpperBoundPlotkin( n, d, q ) _____________________________________function
  
  The  function  UpperBoundPlotkin  calculates the sum of the distances of all
  ordered  pairs  of  different  codewords.  It  is based on the fact that the
  minimum  distance  is  at  most  equal to the average distance. It is a good
  bound if the weights of the codewords do not differ much. It results in:
  
  
       M \leq {d \over {d-(1-1/q)n}},
  
  
  where  M  is the maximum number of codewords. In this case, d must be larger
  than (1-1/q)n, but by shortening the code, the case d < (1-1/q)n is covered.
  
  ---------------------------  Example  ----------------------------
    gap> UpperBoundPlotkin( 15, 7, 2 );
    32
    gap> C := BCHCode( 15, 7, GF(2) );
    a cyclic [15,5,7]5 BCH code, delta=7, b=1 over GF(2)
    gap> Size(C);
    32
    gap> WeightDistribution(C);
    [ 1, 0, 0, 0, 0, 0, 0, 15, 15, 0, 0, 0, 0, 0, 0, 1 ] 
  ------------------------------------------------------------------
  
  7.1-5 UpperBoundElias
  
  > UpperBoundElias( n, d, q ) _______________________________________function
  
  The   Elias   bound   is   an   improvement   of   the  Plotkin  bound  (see
  UpperBoundPlotkin  (7.1-4))  for  large codes. Subcodes are used to decrease
  the  size  of  the  code, in this case the subcode of all codewords within a
  certain  ball.  This  bound  is useful for large codes with relatively small
  minimum distances.
  
  ---------------------------  Example  ----------------------------
    gap> UpperBoundPlotkin( 16, 3, 2 );
    12288
    gap> UpperBoundElias( 16, 3, 2 );
    10280 
    gap> UpperBoundElias( 20, 10, 3 );
    16255
  ------------------------------------------------------------------
  
  7.1-6 UpperBoundGriesmer
  
  > UpperBoundGriesmer( n, d, q ) ____________________________________function
  
  The  Griesmer  bound  is  valid  only  for  linear  codes. It is obtained by
  counting  the number of equal symbols in each row of the generator matrix of
  the  code.  By  omitting  the  coordinates  in which all rows have a zero, a
  smaller  code  results.  The  Griesmer  bound  is obtained by repeating this
  proces until a trivial code is left in the end.
  
  ---------------------------  Example  ----------------------------
    gap> UpperBoundGriesmer( 13, 5, 2 );
    64
    gap> UpperBoundGriesmer( 18, 9, 2 );
    8        # the maximum number of words for a linear code is 8
    gap> Size( PuncturedCode( HadamardCode( 20, 1 ) ) );
    20       # this non-linear code has 20 elements 
  ------------------------------------------------------------------
  
  7.1-7 IsGriesmerCode
  
  > IsGriesmerCode( C ) ______________________________________________function
  
  IsGriesmerCode  returns  `true'  if  a linear code C is a Griesmer code, and
  `false' otherwise. A code is called Griesmer if its length satisfies
  
  
       n = g[k,d] = \sum_{i=0}^{k-1} \lceil \frac{d}{q^i} \rceil.
  
  
  ---------------------------  Example  ----------------------------
    gap> IsGriesmerCode( HammingCode( 3, GF(2) ) );
    true
    gap> IsGriesmerCode( BCHCode( 17, 2, GF(2) ) );
    false 
  ------------------------------------------------------------------
  
  7.1-8 UpperBound
  
  > UpperBound( n, d, q ) ____________________________________________function
  
  UpperBound  returns the best known upper bound A(n,d) for the size of a code
  of  length  n,  minimum  distance  d  over  a  field of size q. The function
  UpperBound  first  checks  for  trivial  cases (like d=1 or n=d), and if the
  value  is in the built-in table. Then it calculates the minimum value of the
  upper   bound  using  the  methods  of  Singleton  (see  UpperBoundSingleton
  (7.1-1)),    Hamming   (see   UpperBoundHamming   (7.1-2)),   Johnson   (see
  UpperBoundJohnson  (7.1-3)),  Plotkin  (see  UpperBoundPlotkin  (7.1-4)) and
  Elias (see UpperBoundElias (7.1-5)). If the code is binary, A(n, 2* ell-1) =
  A(n+1,2*  ell),  so  the UpperBound takes the minimum of the values obtained
  from all methods for the parameters (n, 2*ell-1) and (n+1, 2* ell).
  
  ---------------------------  Example  ----------------------------
    gap> UpperBound( 10, 3, 2 );
    85
    gap> UpperBound( 25, 9, 8 );
    1211778792827540 
  ------------------------------------------------------------------
  
  7.1-9 LowerBoundMinimumDistance
  
  > LowerBoundMinimumDistance( C ) ___________________________________function
  
  In  this  form,  LowerBoundMinimumDistance  returns  a  lower  bound for the
  minimum distance of code C.
  
  This  command can also be called using the syntax LowerBoundMinimumDistance(
  n, k, F ). In this form, LowerBoundMinimumDistance returns a lower bound for
  the  minimum distance of the best known linear code of length n, dimension k
  over field F. It uses the mechanism explained in section 7.1-13.
  
  ---------------------------  Example  ----------------------------
    gap> C := BCHCode( 45, 7 );
    a cyclic [45,23,7..9]6..16 BCH code, delta=7, b=1 over GF(2)
    gap> LowerBoundMinimumDistance( C );
    7     # designed distance is lower bound for minimum distance 
    gap> LowerBoundMinimumDistance( 45, 23, GF(2) );
    10 
  ------------------------------------------------------------------
  
  7.1-10 LowerBoundGilbertVarshamov
  
  > LowerBoundGilbertVarshamov( n, d, q ) ____________________________function
  
  This  is  the  lower  bound due (independently) to Gilbert and Varshamov. It
  says  that  for each n and d, there exists a linear code having length n and
  minimum distance d at least of size q^n-1/ SphereContent(n-1,d-2,GF(q)).
  
  ---------------------------  Example  ----------------------------
    gap> LowerBoundGilbertVarshamov(3,2,2);
    4
    gap> LowerBoundGilbertVarshamov(3,3,2);
    1
    gap> LowerBoundMinimumDistance(3,3,2);
    1
    gap> LowerBoundMinimumDistance(3,2,2);
    2
  ------------------------------------------------------------------
  
  7.1-11 LowerBoundSpherePacking
  
  > LowerBoundSpherePacking( n, d, q ) _______________________________function
  
  This  is  the  lower  bound due (independently) to Gilbert and Varshamov. It
  says  that  for  each n and r, there exists an unrestricted code at least of
  size q^n/ SphereContent(n,d,GF(q)) minimum distance d.
  
  ---------------------------  Example  ----------------------------
    gap> LowerBoundSpherePacking(3,2,2);
    2
    gap> LowerBoundSpherePacking(3,3,2);
    1
  ------------------------------------------------------------------
  
  7.1-12 UpperBoundMinimumDistance
  
  > UpperBoundMinimumDistance( C ) ___________________________________function
  
  In  this  form,  UpperBoundMinimumDistance  returns  an  upper bound for the
  minimum distance of code C. For unrestricted codes, it just returns the word
  length.  For  linear codes, it takes the minimum of the possibly known value
  from the method of construction, the weight of the generators, and the value
  from the table (see 7.1-13).
  
  This  command can also be called using the syntax UpperBoundMinimumDistance(
  n,  k,  F  ). In this form, UpperBoundMinimumDistance returns an upper bound
  for  the  minimum  distance  of  the  best  known  linear  code of length n,
  dimension k over field F. It uses the mechanism explained in section 7.1-13.
  
  ---------------------------  Example  ----------------------------
    gap> C := BCHCode( 45, 7 );;
    gap> UpperBoundMinimumDistance( C );
    9 
    gap> UpperBoundMinimumDistance( 45, 23, GF(2) );
    11 
  ------------------------------------------------------------------
  
  7.1-13 BoundsMinimumDistance
  
  > BoundsMinimumDistance( n, k, F ) _________________________________function
  
  The  function  BoundsMinimumDistance  calculates a lower and upper bound for
  the minimum distance of an optimal linear code with word length n, dimension
  k  over  field  F.  The function returns a record with the two bounds and an
  explanation  for  each  bound.  The function Display can be used to show the
  explanations.
  
  The  values  for  the lower and upper bound are obtained from a table. GUAVA
  has  tables  containing  lower  and upper bounds for q=2 (n <= 257), 3 (n <=
  243),  4  (n <= 256). (Current as of 11 May 2006.) These tables were derived
  from       the       table       of       Brouwer.       (See       [Bro06],
  http://www.win.tue.nl/~aeb/voorlincod.html  for  the  most recent data.) For
  codes  over  other  fields  and  for larger word lengths, trivial bounds are
  used.
  
  The  resulting  record  can be used in the function BestKnownLinearCode (see
  BestKnownLinearCode  (5.2-14))  to  construct  a  code with minimum distance
  equal to the lower bound.
  
  ---------------------------  Example  ----------------------------
    gap> bounds := BoundsMinimumDistance( 7, 3 );; DisplayBoundsInfo( bounds );
    an optimal linear [7,3,d] code over GF(2) has d=4
    ------------------------------------------------------------------------------
    Lb(7,3)=4, by shortening of:
    Lb(8,4)=4, u u+v construction of C1 and C2:
    Lb(4,3)=2, dual of the repetition code
    Lb(4,1)=4, repetition code
    ------------------------------------------------------------------------------
    Ub(7,3)=4, Griesmer bound
    # The lower bound is equal to the upper bound, so a code with
    # these parameters is optimal.
    gap> C := BestKnownLinearCode( bounds );; Display( C );
    a linear [7,3,4]2..3 shortened code of
    a linear [8,4,4]2 U U+V construction code of
    U: a cyclic [4,3,2]1 dual code of
       a cyclic [4,1,4]2 repetition code over GF(2)
    V: a cyclic [4,1,4]2 repetition code over GF(2)
  ------------------------------------------------------------------
  
  
  7.2 Covering radius bounds on codes
  
  7.2-1 BoundsCoveringRadius
  
  > BoundsCoveringRadius( C ) ________________________________________function
  
  BoundsCoveringRadius  returns  a  list  of integers. The first entry of this
  list  is  the maximum of some lower bounds for the covering radius of C, the
  last entry the minimum of some upper bounds of C.
  
  If  the  covering  radius  of  C  is  known, a list of length 1 is returned.
  BoundsCoveringRadius       makes       use       of       the      functions
  GeneralLowerBoundCoveringRadius and GeneralUpperBoundCoveringRadius.
  
  ---------------------------  Example  ----------------------------
    gap> BoundsCoveringRadius( BCHCode( 17, 3, GF(2) ) );
    [ 3 .. 4 ]
    gap> BoundsCoveringRadius( HammingCode( 5, GF(2) ) );
    [ 1 ] 
  ------------------------------------------------------------------
  
  7.2-2 IncreaseCoveringRadiusLowerBound
  
  > IncreaseCoveringRadiusLowerBound( C[, stopdist][, startword] ) ___function
  
  IncreaseCoveringRadiusLowerBound  tries  to  increase the lower bound of the
  covering  radius  of  C. It does this by means of a probabilistic algorithm.
  This  algorithm  takes  a  random  word  in  GF(q)^n  (or startword if it is
  specified),  and, by changing random coordinates, tries to get as far from C
  as  possible.  If  changing  a  coordinate  finds  a  word that has a larger
  distance  to  the  code than the previous one, the change is made permanent,
  and  the  algorithm starts all over again. If changing a coordinate does not
  find  a  coset leader that is further away from the code, then the change is
  made  permanent with a chance of 1 in 100, if it gets the word closer to the
  code,  or  with a chance of 1 in 10, if the word stays at the same distance.
  Otherwise, the algorithm starts again with the same word as before.
  
  If  the  algorithm  did  not allow changes that decrease the distance to the
  code,  it  might  get  stuck  in  a  sub-optimal situation (the coset leader
  corresponding  to such a situation - i.e. no coordinate of this coset leader
  can  be changed in such a way that we get at a larger distance from the code
  - is called an orphan).
  
  If  the  algorithm  finds  a word that has distance stopdist to the code, it
  ends and returns that word, which can be used for further investigations.
  
  The  variable  InfoCoveringRadius  can  be set to Print to print the maximum
  distance  reached  so  far every 1000 runs. The algorithm can be interrupted
  with  ctrl-C,  allowing the user to look at the word that is currently being
  examined  (called  `current'), or to change the chances that the new word is
  made  permanent  (these are called `staychance' and `downchance'). If one of
  these variables is i, then it corresponds with a i in 100 chance.
  
  At  the moment, the algorithm is only useful for codes with small dimension,
  where  small means that the elements of the code fit in the memory. It works
  with  larger  codes,  however,  but  when  you  use  it for codes with large
  dimension,  you  should  be very patient. If running the algorithm quits GAP
  (due  to memory problems), you can change the global variable CRMemSize to a
  lower  value.  This  might  cause  the  algorithm to run slower, but without
  quitting  GAP.  The  only  way to find out the best value of CRMemSize is by
  experimenting.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(10,5,GF(2));
    a  [10,5,?] randomly generated code over GF(2)
    gap> IncreaseCoveringRadiusLowerBound(C,10);
    Number of runs: 1000  best distance so far: 3
    Number of runs: 2000  best distance so far: 3
    Number of changes: 100
    Number of runs: 3000  best distance so far: 3
    Number of runs: 4000  best distance so far: 3
    Number of runs: 5000  best distance so far: 3
    Number of runs: 6000  best distance so far: 3
    Number of runs: 7000  best distance so far: 3
    Number of changes: 200
    Number of runs: 8000  best distance so far: 3
    Number of runs: 9000  best distance so far: 3
    Number of runs: 10000  best distance so far: 3
    Number of changes: 300
    Number of runs: 11000  best distance so far: 3
    Number of runs: 12000  best distance so far: 3
    Number of runs: 13000  best distance so far: 3
    Number of changes: 400
    Number of runs: 14000  best distance so far: 3
    user interrupt at... 
    #
    # used ctrl-c to break out of execution
    #
    ... called from 
    IncreaseCoveringRadiusLowerBound( code, -1, current ) called from
     function( arguments ) called from read-eval-loop
    Entering break read-eval-print loop ...
    you can 'quit;' to quit to outer loop, or
    you can 'return;' to continue
    brk> current;
    [ Z(2)^0, Z(2)^0, Z(2)^0, Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0, 0*Z(2), Z(2)^0 ]
    brk>
    gap> CoveringRadius(C);
    3
    
  ------------------------------------------------------------------
  
  7.2-3 ExhaustiveSearchCoveringRadius
  
  > ExhaustiveSearchCoveringRadius( C ) ______________________________function
  
  ExhaustiveSearchCoveringRadius   does  an  exhaustive  search  to  find  the
  covering  radius of C. Every time a coset leader of a coset with weight w is
  found, the function tries to find a coset leader of a coset with weight w+1.
  It  does this by enumerating all words of weight w+1, and checking whether a
  word is a coset leader. The start weight is the current known lower bound on
  the covering radius.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(10,5,GF(2));
    a  [10,5,?] randomly generated code over GF(2)
    gap> ExhaustiveSearchCoveringRadius(C);
    Trying 3 ...
    [ 3 .. 5 ]
    gap> CoveringRadius(C);
    3
    
  ------------------------------------------------------------------
  
  7.2-4 GeneralLowerBoundCoveringRadius
  
  > GeneralLowerBoundCoveringRadius( C ) _____________________________function
  
  GeneralLowerBoundCoveringRadius returns a lower bound on the covering radius
  of    C.    It   uses   as   many   functions   which   names   start   with
  LowerBoundCoveringRadius  as possible to find the best known lower bound (at
  least  that  GUAVA knows of) together with tables for the covering radius of
  binary linear codes with length not greater than 64.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(10,5,GF(2));
    a  [10,5,?] randomly generated code over GF(2)
    gap> GeneralLowerBoundCoveringRadius(C);
    2
    gap> CoveringRadius(C);
    3
    
  ------------------------------------------------------------------
  
  7.2-5 GeneralUpperBoundCoveringRadius
  
  > GeneralUpperBoundCoveringRadius( C ) _____________________________function
  
  GeneralUpperBoundCoveringRadius  returns  an  upper  bound  on  the covering
  radius   of   C.   It   uses  as  many  functions  which  names  start  with
  UpperBoundCoveringRadius  as possible to find the best known upper bound (at
  least that GUAVA knows of).
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(10,5,GF(2));
    a  [10,5,?] randomly generated code over GF(2)
    gap> GeneralUpperBoundCoveringRadius(C);
    4
    gap> CoveringRadius(C);
    3
    
  ------------------------------------------------------------------
  
  7.2-6 LowerBoundCoveringRadiusSphereCovering
  
  > LowerBoundCoveringRadiusSphereCovering( n, M[, F], false ) _______function
  
  This     command     can     also     be    called    using    the    syntax
  LowerBoundCoveringRadiusSphereCovering(  n,  r,  [F,]  true  ).  If the last
  argument of LowerBoundCoveringRadiusSphereCovering is false, then it returns
  a  lower  bound  for  the  covering radius of a code of size M and length n.
  Otherwise,  it  returns a lower bound for the size of a code of length n and
  covering radius r.
  
  F  is  the  field  over  which  the  code is defined. If F is omitted, it is
  assumed  that the code is over GF(2). The bound is computed according to the
  sphere covering bound:
  
  
       M \cdot V_q(n,r) \geq q^n
  
  
  where V_q(n,r) is the size of a sphere of radius r in GF(q)^n.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(10,5,GF(2));
    a  [10,5,?] randomly generated code over GF(2)
    gap> Size(C);
    32
    gap> CoveringRadius(C);
    3
    gap> LowerBoundCoveringRadiusSphereCovering(10,32,GF(2),false);
    2
    gap> LowerBoundCoveringRadiusSphereCovering(10,3,GF(2),true);
    6
    
  ------------------------------------------------------------------
  
  7.2-7 LowerBoundCoveringRadiusVanWee1
  
  > LowerBoundCoveringRadiusVanWee1( n, M[, F], false ) ______________function
  
  This     command     can     also     be    called    using    the    syntax
  LowerBoundCoveringRadiusVanWee1(  n, r, [F,] true ). If the last argument of
  LowerBoundCoveringRadiusVanWee1  is false, then it returns a lower bound for
  the  covering radius of a code of size M and length n. Otherwise, it returns
  a lower bound for the size of a code of length n and covering radius r.
  
  F  is  the  field  over  which  the  code is defined. If F is omitted, it is
  assumed that the code is over GF(2).
  
  The Van Wee bound is an improvement of the sphere covering bound:
  
  
       M \cdot \left\{ V_q(n,r) - \frac{{n \choose
       r}}{\lceil\frac{n-r}{r+1}\rceil}
       \left(\left\lceil\frac{n+1}{r+1}\right\rceil -
       \frac{n+1}{r+1}\right) \right\} \geq q^n
  
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(10,5,GF(2));
    a  [10,5,?] randomly generated code over GF(2)
    gap> Size(C);
    32
    gap> CoveringRadius(C);
    3
    gap> LowerBoundCoveringRadiusVanWee1(10,32,GF(2),false);
    2
    gap> LowerBoundCoveringRadiusVanWee1(10,3,GF(2),true);
    6
    
  ------------------------------------------------------------------
  
  7.2-8 LowerBoundCoveringRadiusVanWee2
  
  > LowerBoundCoveringRadiusVanWee2( n, M, false ) ___________________function
  
  This     command     can     also     be    called    using    the    syntax
  LowerBoundCoveringRadiusVanWee2(  n,  r  [,true]  ). If the last argument of
  LowerBoundCoveringRadiusVanWee2  is false, then it returns a lower bound for
  the  covering radius of a code of size M and length n. Otherwise, it returns
  a lower bound for the size of a code of length n and covering radius r.
  
  This  bound  only  works  for  binary  codes.  It  is based on the following
  inequality:
  
  
       M \cdot \frac{\left( \left( V_2(n,2) - \frac{1}{2}(r+2)(r-1)
       \right) V_2(n,r) + \varepsilon V_2(n,r-2) \right)} {(V_2(n,2) -
       \frac{1}{2}(r+2)(r-1) + \varepsilon)} \geq 2^n,
  
  
  where
  
  
       \varepsilon = {r+2 \choose 2} \left\lceil {n-r+1 \choose 2} / {r+2
       \choose 2} \right\rceil - {n-r+1 \choose 2}.
  
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(10,5,GF(2));
    a  [10,5,?] randomly generated code over GF(2)
    gap> Size(C);
    32
    gap> CoveringRadius(C);
    3
    gap> LowerBoundCoveringRadiusVanWee2(10,32,false);
    2
    gap> LowerBoundCoveringRadiusVanWee2(10,3,true);
    7
    
  ------------------------------------------------------------------
  
  7.2-9 LowerBoundCoveringRadiusCountingExcess
  
  > LowerBoundCoveringRadiusCountingExcess( n, M, false ) ____________function
  
  This command can also be called with LowerBoundCoveringRadiusCountingExcess(
  n,      r      [,true]      ).      If      the     last     argument     of
  LowerBoundCoveringRadiusCountingExcess  is  false,  then  it returns a lower
  bound  for  the covering radius of a code of size M and length n. Otherwise,
  it  returns  a  lower  bound for the size of a code of length n and covering
  radius r.
  
  This  bound  only  works  for  binary  codes.  It  is based on the following
  inequality:
  
  
       M \cdot \left( \rho V_2(n,r) + \varepsilon V_2(n,r-1) \right) \geq
       (\rho + \varepsilon) 2^n,
  
  
  where
  
  
       \varepsilon = (r+1) \left\lceil\frac{n+1}{r+1}\right\rceil - (n+1)
  
  
  and
  
  
       \rho = \left\{ \begin{array}{l} n-3+\frac{2}{n}, \ \ \ \ \ \ {\rm
       if}\ r = 2\\ n-r-1 , \ \ \ \ \ \ {\rm if}\ r \geq 3 . \end{array}
       \right.
  
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(10,5,GF(2));
    a  [10,5,?] randomly generated code over GF(2)
    gap> Size(C);
    32
    gap> CoveringRadius(C);
    3
    gap> LowerBoundCoveringRadiusCountingExcess(10,32,false);
    0
    gap> LowerBoundCoveringRadiusCountingExcess(10,3,true);
    7
    
  ------------------------------------------------------------------
  
  7.2-10 LowerBoundCoveringRadiusEmbedded1
  
  > LowerBoundCoveringRadiusEmbedded1( n, M, false ) _________________function
  
  This command can also be called with LowerBoundCoveringRadiusEmbedded1( n, r
  [,true]  ).  If  the  last  argument of LowerBoundCoveringRadiusEmbedded1 is
  'false',  then it returns a lower bound for the covering radius of a code of
  size  M  and length n. Otherwise, it returns a lower bound for the size of a
  code of length n and covering radius r.
  
  This  bound  only  works  for  binary  codes.  It  is based on the following
  inequality:
  
  
       M \cdot \left( V_2(n,r) - {2r \choose r} \right) \geq 2^n - A( n,
       2r+1 ) {2r \choose r},
  
  
  where  A(n,d) denotes the maximal cardinality of a (binary) code of length n
  and  minimum  distance  d.  The  function UpperBound is used to compute this
  value.
  
  Sometimes      LowerBoundCoveringRadiusEmbedded1      is     better     than
  LowerBoundCoveringRadiusEmbedded2, sometimes it is the other way around.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(10,5,GF(2));
    a  [10,5,?] randomly generated code over GF(2)
    gap> Size(C);
    32
    gap> CoveringRadius(C);
    3
    gap> LowerBoundCoveringRadiusEmbedded1(10,32,false);
    2
    gap> LowerBoundCoveringRadiusEmbedded1(10,3,true);
    7
    
  ------------------------------------------------------------------
  
  7.2-11 LowerBoundCoveringRadiusEmbedded2
  
  > LowerBoundCoveringRadiusEmbedded2( n, M, false ) _________________function
  
  This command can also be called with LowerBoundCoveringRadiusEmbedded2( n, r
  [,true]  ).  If  the  last  argument of LowerBoundCoveringRadiusEmbedded2 is
  'false',  then it returns a lower bound for the covering radius of a code of
  size  M  and length n. Otherwise, it returns a lower bound for the size of a
  code of length n and covering radius r.
  
  This  bound  only  works  for  binary  codes.  It  is based on the following
  inequality:
  
  
       M \cdot \left( V_2(n,r) - \frac{3}{2} {2r \choose r} \right) \geq
       2^n - 2A( n, 2r+1 ) {2r \choose r},
  
  
  where  A(n,d) denotes the maximal cardinality of a (binary) code of length n
  and  minimum  distance  d.  The  function UpperBound is used to compute this
  value.
  
  Sometimes      LowerBoundCoveringRadiusEmbedded1      is     better     than
  LowerBoundCoveringRadiusEmbedded2, sometimes it is the other way around.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(15,5,GF(2));
    a  [15,5,?] randomly generated code over GF(2)
    gap> Size(C);
    32
    gap> CoveringRadius(C);
    6
    gap> LowerBoundCoveringRadiusEmbedded2(10,32,false);
    2
    gap> LowerBoundCoveringRadiusEmbedded2(10,3,true);
    7
    
  ------------------------------------------------------------------
  
  7.2-12 LowerBoundCoveringRadiusInduction
  
  > LowerBoundCoveringRadiusInduction( n, r ) ________________________function
  
  LowerBoundCoveringRadiusInduction  returns  a  lower bound for the size of a
  code with length n and covering radius r.
  
  If n = 2r+2 and r >= 1, the returned value is 4.
  
  If n = 2r+3 and r >= 1, the returned value is 7.
  
  If n = 2r+4 and r >= 4, the returned value is 8.
  
  Otherwise, 0 is returned.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(15,5,GF(2));
    a  [15,5,?] randomly generated code over GF(2)
    gap> CoveringRadius(C);
    5
    gap> LowerBoundCoveringRadiusInduction(15,6);
    7
    
  ------------------------------------------------------------------
  
  7.2-13 UpperBoundCoveringRadiusRedundancy
  
  > UpperBoundCoveringRadiusRedundancy( C ) __________________________function
  
  UpperBoundCoveringRadiusRedundancy  returns  the redundancy of C as an upper
  bound for the covering radius of C. C must be a linear code.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(15,5,GF(2));
    a  [15,5,?] randomly generated code over GF(2)
    gap> CoveringRadius(C);
    5
    gap> UpperBoundCoveringRadiusRedundancy(C);
    10
    
  ------------------------------------------------------------------
  
  7.2-14 UpperBoundCoveringRadiusDelsarte
  
  > UpperBoundCoveringRadiusDelsarte( C ) ____________________________function
  
  UpperBoundCoveringRadiusDelsarte  returns  an  upper  bound for the covering
  radius  of  C. This upper bound is equal to the external distance of C, this
  is the minimum distance of the dual code, if C is a linear code.
  
  This is described in Theorem 11.3.3 of [HP03].
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(15,5,GF(2));
    a  [15,5,?] randomly generated code over GF(2)
    gap> CoveringRadius(C);
    5
    gap> UpperBoundCoveringRadiusDelsarte(C);
    13
  ------------------------------------------------------------------
  
  7.2-15 UpperBoundCoveringRadiusStrength
  
  > UpperBoundCoveringRadiusStrength( C ) ____________________________function
  
  UpperBoundCoveringRadiusStrength  returns  an  upper  bound for the covering
  radius of C.
  
  First  the  code  is punctured at the zero coordinates (i.e. the coordinates
  where all codewords have a zero). If the remaining code has strength 1 (i.e.
  each  coordinate  contains  each  element  of  the  field an equal number of
  times),  then it returns fracq-1qm + (n-m) (where q is the size of the field
  and  m  is the length of punctured code), otherwise it returns n. This bound
  works for all codes.
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(15,5,GF(2));
    a  [15,5,?] randomly generated code over GF(2)
    gap> CoveringRadius(C);
    5
    gap> UpperBoundCoveringRadiusStrength(C);
    7
  ------------------------------------------------------------------
  
  7.2-16 UpperBoundCoveringRadiusGriesmerLike
  
  > UpperBoundCoveringRadiusGriesmerLike( C ) ________________________function
  
  This  function  returns  an  upper bound for the covering radius of C, which
  must be linear, in a Griesmer-like fashion. It returns
  
  
       n - \sum_{i=1}^k \left\lceil \frac{d}{q^i} \right\rceil
  
  
  ---------------------------  Example  ----------------------------
    gap> C:=RandomLinearCode(15,5,GF(2));
    a  [15,5,?] randomly generated code over GF(2)
    gap> CoveringRadius(C);
    5
    gap> UpperBoundCoveringRadiusGriesmerLike(C);
    9
    
  ------------------------------------------------------------------
  
  7.2-17 UpperBoundCoveringRadiusCyclicCode
  
  > UpperBoundCoveringRadiusCyclicCode( C ) __________________________function
  
  This  function  returns  an  upper bound for the covering radius of C, which
  must be a cyclic code. It returns
  
  
       n - k + 1 - \left\lceil \frac{w(g(x))}{2} \right\rceil,
  
  
  where g(x) is the generator polynomial of C.
  
  ---------------------------  Example  ----------------------------
    gap> C:=CyclicCodes(15,GF(2))[3];
    a cyclic [15,12,1..2]1..3 enumerated code over GF(2)
    gap> CoveringRadius(C);
    3
    gap> UpperBoundCoveringRadiusCyclicCode(C);
    3
    
  ------------------------------------------------------------------
  
  
  7.3 Special matrices in GUAVA
  
  This  section explains functions that work with special matrices GUAVA needs
  for several codes.
  
  Firstly,  we  describe  some  matrix generating functions (see KrawtchoukMat
  (7.3-1), GrayMat (7.3-2), SylvesterMat (7.3-3), HadamardMat (7.3-4) and MOLS
  (7.3-11)).
  
  Next  we  describe  two functions regarding a standard form of matrices (see
  PutStandardForm (7.3-6) and IsInStandardForm (7.3-7)).
  
  Then  we  describe  functions that return a matrix after a manipulation (see
  PermutedCols     (7.3-8),     VerticalConversionFieldMat     (7.3-9)     and
  HorizontalConversionFieldMat (7.3-10)).
  
  Finally,  we  describe  functions  that  do  some  tests  on  matrices  (see
  IsLatinSquare (7.3-12) and AreMOLS (7.3-13)).
  
  7.3-1 KrawtchoukMat
  
  > KrawtchoukMat( n, q ) ____________________________________________function
  
  KrawtchoukMat  returns the n+1 by n+1 matrix K=(k_ij) defined by k_ij=K_i(j)
  for i,j=0,...,n. K_i(j) is the Krawtchouk number (see Krawtchouk (7.5-6)). n
  must  be  a  positive  integer and q a prime power. The Krawtchouk matrix is
  used in the MacWilliams identities, defining the relation between the weight
  distribution  of  a  code  of  length n over a field of size q, and its dual
  code.  Each  call  to  KrawtchoukMat  returns a new matrix, so it is safe to
  modify the result.
  
  ---------------------------  Example  ----------------------------
    gap> PrintArray( KrawtchoukMat( 3, 2 ) );
    [ [   1,   1,   1,   1 ],
      [   3,   1,  -1,  -3 ],
      [   3,  -1,  -1,   3 ],
      [   1,  -1,   1,  -1 ] ]
    gap> C := HammingCode( 3 );; a := WeightDistribution( C );
    [ 1, 0, 0, 7, 7, 0, 0, 1 ]
    gap> n := WordLength( C );; q := Size( LeftActingDomain( C ) );;
    gap> k := Dimension( C );;
    gap> q^( -k ) * KrawtchoukMat( n, q ) * a;
    [ 1, 0, 0, 0, 7, 0, 0, 0 ]
    gap> WeightDistribution( DualCode( C ) );
    [ 1, 0, 0, 0, 7, 0, 0, 0 ] 
  ------------------------------------------------------------------
  
  7.3-2 GrayMat
  
  > GrayMat( n, F ) __________________________________________________function
  
  GrayMat  returns a list of all different vectors (see GAP's Vectors command)
  of  length  n  over  the  field F, using Gray ordering. n must be a positive
  integer.  This  order  has  the  property  that subsequent vectors differ in
  exactly  one  coordinate.  The  first vector is always the null vector. Each
  call to GrayMat returns a new matrix, so it is safe to modify the result.
  
  ---------------------------  Example  ----------------------------
    gap> GrayMat(3);
    [ [ 0*Z(2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0 ],
      [ 0*Z(2), Z(2)^0, Z(2)^0 ], [ 0*Z(2), Z(2)^0, 0*Z(2) ],
      [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ Z(2)^0, Z(2)^0, Z(2)^0 ],
      [ Z(2)^0, 0*Z(2), Z(2)^0 ], [ Z(2)^0, 0*Z(2), 0*Z(2) ] ]
    gap> G := GrayMat( 4, GF(4) );; Length(G);
    256          # the length of a GrayMat is always q^n
    gap> G[101] - G[100];
    [ 0*Z(2), 0*Z(2), Z(2)^0, 0*Z(2) ] 
  ------------------------------------------------------------------
  
  7.3-3 SylvesterMat
  
  > SylvesterMat( n ) ________________________________________________function
  
  SylvesterMat returns the nx n Sylvester matrix of order n. This is a special
  case   of   the  Hadamard  matrices  (see  HadamardMat  (7.3-4)).  For  this
  construction,  n  must  be a power of 2. Each call to SylvesterMat returns a
  new matrix, so it is safe to modify the result.
  
  ---------------------------  Example  ----------------------------
    gap> PrintArray(SylvesterMat(2));
    [ [   1,   1 ],
      [   1,  -1 ] ]
    gap> PrintArray( SylvesterMat(4) );
    [ [   1,   1,   1,   1 ],
      [   1,  -1,   1,  -1 ],
      [   1,   1,  -1,  -1 ],
      [   1,  -1,  -1,   1 ] ] 
  ------------------------------------------------------------------
  
  7.3-4 HadamardMat
  
  > HadamardMat( n ) _________________________________________________function
  
  HadamardMat  returns  a  Hadamard  matrix of order n. This is an nx n matrix
  with  the  property  that  the  matrix multiplied by its transpose returns n
  times  the  identity  matrix. This is only possible for n=1, n=2 or in cases
  where n is a multiple of 4. If the matrix does not exist or is not known (as
  of  1998),  HadamardMat  returns  an  error.  A large number of construction
  methods  is known to create these matrices for different orders. HadamardMat
  makes   use   of   two  construction  methods  (the  Paley  Type  I  and  II
  constructions,  and the Sylvester construction -- see SylvesterMat (7.3-3)).
  These  methods  cover  most of the possible Hadamard matrices, although some
  special  algorithms have not been implemented yet. The following orders less
  than  100  do not yet have an implementation for a Hadamard matrix in GUAVA:
  52, 92.
  
  ---------------------------  Example  ----------------------------
    gap> C := HadamardMat(8);; PrintArray(C);
    [ [   1,   1,   1,   1,   1,   1,   1,   1 ],
      [   1,  -1,   1,  -1,   1,  -1,   1,  -1 ],
      [   1,   1,  -1,  -1,   1,   1,  -1,  -1 ],
      [   1,  -1,  -1,   1,   1,  -1,  -1,   1 ],
      [   1,   1,   1,   1,  -1,  -1,  -1,  -1 ],
      [   1,  -1,   1,  -1,  -1,   1,  -1,   1 ],
      [   1,   1,  -1,  -1,  -1,  -1,   1,   1 ],
      [   1,  -1,  -1,   1,  -1,   1,   1,  -1 ] ]
    gap> C * TransposedMat(C) = 8 * IdentityMat( 8, 8 );
    true 
  ------------------------------------------------------------------
  
  7.3-5 VandermondeMat
  
  > VandermondeMat( X, a ) ___________________________________________function
  
  The  function  VandermondeMat  returns  the  (a+1)x n matrix of powers x_i^j
  where  X  is  a  list  of  elements  of  a field, X= x_1,...,x_n, and a is a
  non-negative integer.
  
  ---------------------------  Example  ----------------------------
    gap> M:=VandermondeMat([Z(5),Z(5)^2,Z(5)^0,Z(5)^3],2);
    [ [ Z(5)^0, Z(5), Z(5)^2 ], [ Z(5)^0, Z(5)^2, Z(5)^0 ],
      [ Z(5)^0, Z(5)^0, Z(5)^0 ], [ Z(5)^0, Z(5)^3, Z(5)^2 ] ]
    gap> Display(M);
     1 2 4
     1 4 1
     1 1 1
     1 3 4
  ------------------------------------------------------------------
  
  7.3-6 PutStandardForm
  
  > PutStandardForm( M[, idleft] ) ___________________________________function
  
  We  say  that  a kx n matrix is in standard form if it is equal to the block
  matrix  (I | A), for some kx (n-k) matrix A and where I is the kx k identity
  matrix.  It  follows  from  a  basis  result in linear algebra that, after a
  possible  permutation of the columns, using elementary row operations, every
  matrix  can  be reduced to standard form. PutStandardForm puts a matrix M in
  standard  form,  and  returns  the  permutation needed to do so. idleft is a
  boolean that sets the position of the identity matrix in M. (The default for
  idleft is `true'.) If idleft is set to `true', the identity matrix is put on
  the  left side of M. Otherwise, it is put at the right side. (This option is
  useful  when  putting  a  check  matrix  of  a code into standard form.) The
  function  BaseMat  also  returns a similar standard form, but does not apply
  column permutations. The rows of the matrix still span the same vector space
  after  BaseMat,  but  after calling PutStandardForm, this is not necessarily
  true.
  
  ---------------------------  Example  ----------------------------
    gap> M := Z(2)*[[1,0,0,1],[0,0,1,1]];; PrintArray(M);
    [ [    Z(2),  0*Z(2),  0*Z(2),    Z(2) ],
      [  0*Z(2),  0*Z(2),    Z(2),    Z(2) ] ]
    gap> PutStandardForm(M);                   # identity at the left side
    (2,3)
    gap> PrintArray(M);
    [ [    Z(2),  0*Z(2),  0*Z(2),    Z(2) ],
      [  0*Z(2),    Z(2),  0*Z(2),    Z(2) ] ]
    gap> PutStandardForm(M, false);            # identity at the right side
    (1,4,3)
    gap> PrintArray(M);
    [ [  0*Z(2),    Z(2),    Z(2),  0*Z(2) ],
      [  0*Z(2),    Z(2),  0*Z(2),    Z(2) ] ]
    gap> C := BestKnownLinearCode( 23, 12, GF(2) );
    a linear [23,12,7]3 punctured code
    gap> G:=MutableCopyMat(GeneratorMat(C));;
    gap> PutStandardForm(G);
    ()
    gap> Display(G);
     1 . . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1
     . 1 . . . . . . . . . . 1 1 1 1 1 . . 1 . . .
     . . 1 . . . . . . . . . 1 1 . 1 . . 1 . 1 . 1
     . . . 1 . . . . . . . . 1 1 . . . 1 1 1 . 1 .
     . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 . 1
     . . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1 1
     . . . . . . 1 . . . . . . . 1 1 . . 1 1 . 1 1
     . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 . .
     . . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 1 .
     . . . . . . . . . 1 . . . . 1 . 1 1 . 1 1 1 .
     . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1 1
     . . . . . . . . . . . 1 . 1 . 1 1 1 . . . 1 1
    
  ------------------------------------------------------------------
  
  7.3-7 IsInStandardForm
  
  > IsInStandardForm( M[, idleft] ) __________________________________function
  
  IsInStandardForm  determines  if  M is in standard form. idleft is a boolean
  that   indicates   the   position  of  the  identity  matrix  in  M,  as  in
  PutStandardForm  (see  PutStandardForm  (7.3-6)). IsInStandardForm checks if
  the  identity  matrix  is  at  the left side of M, otherwise if it is at the
  right side. The elements of M may be elements of any field.
  
  ---------------------------  Example  ----------------------------
    gap> IsInStandardForm(IdentityMat(7, GF(2)));
    true
    gap> IsInStandardForm([[1, 1, 0], [1, 0, 1]], false);
    true
    gap> IsInStandardForm([[1, 3, 2, 7]]);
    true
    gap> IsInStandardForm(HadamardMat(4));
    false 
  ------------------------------------------------------------------
  
  7.3-8 PermutedCols
  
  > PermutedCols( M, P ) _____________________________________________function
  
  PermutedCols returns a matrix M with a permutation P applied to its columns.
  
  ---------------------------  Example  ----------------------------
    gap> M := [[1,2,3,4],[1,2,3,4]];; PrintArray(M);
    [ [  1,  2,  3,  4 ],
      [  1,  2,  3,  4 ] ]
    gap> PrintArray(PermutedCols(M, (1,2,3)));
    [ [  3,  1,  2,  4 ],
      [  3,  1,  2,  4 ] ] 
  ------------------------------------------------------------------
  
  7.3-9 VerticalConversionFieldMat
  
  > VerticalConversionFieldMat( M, F ) _______________________________function
  
  VerticalConversionFieldMat  returns the matrix M with its elements converted
  from  a field F=GF(q^m), q prime, to a field GF(q). Each element is replaced
  by  its  representation  over  the  latter  field,  placed vertically in the
  matrix, using the GF(p)-vector space isomorphism
  
  
       [...] : GF(q)\rightarrow GF(p)^m,
  
  
  with q=p^m.
  
  If M is a k by n matrix, the result is a k* m x n matrix, since each element
  of GF(q^m) can be represented in GF(q) using m elements.
  
  ---------------------------  Example  ----------------------------
    gap> M := Z(9)*[[1,2],[2,1]];; PrintArray(M);
    [ [    Z(3^2),  Z(3^2)^5 ],
      [  Z(3^2)^5,    Z(3^2) ] ]
    gap> DefaultField( Flat(M) );
    GF(3^2)
    gap> VCFM := VerticalConversionFieldMat( M, GF(9) );; PrintArray(VCFM);
    [ [  0*Z(3),  0*Z(3) ],
      [  Z(3)^0,    Z(3) ],
      [  0*Z(3),  0*Z(3) ],
      [    Z(3),  Z(3)^0 ] ]
    gap> DefaultField( Flat(VCFM) );
    GF(3) 
  ------------------------------------------------------------------
  
  A      similar     function     is     HorizontalConversionFieldMat     (see
  HorizontalConversionFieldMat (7.3-10)).
  
  7.3-10 HorizontalConversionFieldMat
  
  > HorizontalConversionFieldMat( M, F ) _____________________________function
  
  HorizontalConversionFieldMat   returns   the  matrix  M  with  its  elements
  converted from a field F=GF(q^m), q prime, to a field GF(q). Each element is
  replaced by its representation over the latter field, placed horizontally in
  the matrix.
  
  If  M  is  a  k  x n matrix, the result is a kx mx n* m matrix. The new word
  length  of  the  resulting  code  is  equal to n* m, because each element of
  GF(q^m)  can  be represented in GF(q) using m elements. The new dimension is
  equal  to  kx m because the new matrix should be a basis for the same number
  of vectors as the old one.
  
  ConversionFieldCode  uses  horizontal  conversion  to  convert  a  code (see
  ConversionFieldCode (6.1-15)).
  
  ---------------------------  Example  ----------------------------
    gap> M := Z(9)*[[1,2],[2,1]];; PrintArray(M);
    [ [    Z(3^2),  Z(3^2)^5 ],
      [  Z(3^2)^5,    Z(3^2) ] ]
    gap> DefaultField( Flat(M) );
    GF(3^2)
    gap> HCFM := HorizontalConversionFieldMat(M, GF(9));; PrintArray(HCFM);
    [ [  0*Z(3),  Z(3)^0,  0*Z(3),    Z(3) ],
      [  Z(3)^0,  Z(3)^0,    Z(3),    Z(3) ],
      [  0*Z(3),    Z(3),  0*Z(3),  Z(3)^0 ],
      [    Z(3),    Z(3),  Z(3)^0,  Z(3)^0 ] ]
    gap> DefaultField( Flat(HCFM) );
    GF(3) 
  ------------------------------------------------------------------
  
  A      similar      function      is     VerticalConversionFieldMat     (see
  VerticalConversionFieldMat (7.3-9)).
  
  7.3-11 MOLS
  
  > MOLS( q[, n] ) ___________________________________________________function
  
  MOLS  returns  a list of n Mutually Orthogonal Latin Squares (MOLS). A Latin
  square  of  order  q  is a qx q matrix whose entries are from a set F_q of q
  distinct  symbols  (GUAVA  uses the integers from 0 to q) such that each row
  and each column of the matrix contains each symbol exactly once.
  
  A  set  of  Latin  squares  is a set of MOLS if and only if for each pair of
  Latin  squares  in  this set, every ordered pair of elements that are in the
  same position in these matrices occurs exactly once.
  
  n must be less than q. If n is omitted, two MOLS are returned. If q is not a
  prime  power,  at most 2 MOLS can be created. For all values of q with q > 2
  and  q  <> 6, a list of MOLS can be constructed. However, GUAVA does not yet
  construct  MOLS  for  q= 2 mod 4. If it is not possible to construct n MOLS,
  the function returns `false'.
  
  MOLS are used to create q-ary codes (see MOLSCode (5.1-4)).
  
  ---------------------------  Example  ----------------------------
    gap> M := MOLS( 4, 3 );;PrintArray( M[1] );
    [ [  0,  1,  2,  3 ],
      [  1,  0,  3,  2 ],
      [  2,  3,  0,  1 ],
      [  3,  2,  1,  0 ] ]
    gap> PrintArray( M[2] );
    [ [  0,  2,  3,  1 ],
      [  1,  3,  2,  0 ],
      [  2,  0,  1,  3 ],
      [  3,  1,  0,  2 ] ]
    gap> PrintArray( M[3] );
    [ [  0,  3,  1,  2 ],
      [  1,  2,  0,  3 ],
      [  2,  1,  3,  0 ],
      [  3,  0,  2,  1 ] ]
    gap> MOLS( 12, 3 );
    false 
  ------------------------------------------------------------------
  
  7.3-12 IsLatinSquare
  
  > IsLatinSquare( M ) _______________________________________________function
  
  IsLatinSquare determines if a matrix M is a Latin square. For a Latin square
  of  size  nx  n, each row and each column contains all the integers 1,dots,n
  exactly once.
  
  ---------------------------  Example  ----------------------------
    gap> IsLatinSquare([[1,2],[2,1]]);
    true
    gap> IsLatinSquare([[1,2,3],[2,3,1],[1,3,2]]);
    false 
  ------------------------------------------------------------------
  
  7.3-13 AreMOLS
  
  > AreMOLS( L ) _____________________________________________________function
  
  AreMOLS  determines  if  L  is  a  list of mutually orthogonal Latin squares
  (MOLS).  For each pair of Latin squares in this list, the function checks if
  each  ordered  pair  of  elements  that  are  in  the same position in these
  matrices  occurs  exactly  once.  The  function  MOLS creates MOLS (see MOLS
  (7.3-11)).
  
  ---------------------------  Example  ----------------------------
    gap> M := MOLS(4,2);
    [ [ [ 0, 1, 2, 3 ], [ 1, 0, 3, 2 ], [ 2, 3, 0, 1 ], [ 3, 2, 1, 0 ] ],
      [ [ 0, 2, 3, 1 ], [ 1, 3, 2, 0 ], [ 2, 0, 1, 3 ], [ 3, 1, 0, 2 ] ] ]
    gap> AreMOLS(M);
    true 
  ------------------------------------------------------------------
  
  
  7.4 Some functions related to the norm of a code
  
  In  this  section,  some functions that can be used to compute the norm of a
  code  and  to  decide upon its normality are discussed. Typically, these are
  applied  to  binary  linear  codes.  The  definitions  of  this section were
  introduced in Graham and Sloane [GS85].
  
  7.4-1 CoordinateNorm
  
  > CoordinateNorm( C, coord ) _______________________________________function
  
  CoordinateNorm  returns  the  norm of C with respect to coordinate coord. If
  C_a  =  c  in  C  | c_coord = a, then the norm of C with respect to coord is
  defined as
  
  
       \max_{v \in GF(q)^n} \sum_{a=1}^q d(x,C_a),
  
  
  with the convention that d(x,C_a) = n if C_a is empty.
  
  ---------------------------  Example  ----------------------------
    gap> CoordinateNorm( HammingCode( 3, GF(2) ), 3 );
    3 
  ------------------------------------------------------------------
  
  7.4-2 CodeNorm
  
  > CodeNorm( C ) ____________________________________________________function
  
  CodeNorm returns the norm of C. The norm of a code is defined as the minimum
  of the norms for the respective coordinates of the code. In effect, for each
  coordinate  CoordinateNorm  is  called,  and  the  minimum of the calculated
  numbers is returned.
  
  ---------------------------  Example  ----------------------------
    gap> CodeNorm( HammingCode( 3, GF(2) ) );
    3 
  ------------------------------------------------------------------
  
  7.4-3 IsCoordinateAcceptable
  
  > IsCoordinateAcceptable( C, coord ) _______________________________function
  
  IsCoordinateAcceptable   returns   `true'   if  coordinate  coord  of  C  is
  acceptable.  A  coordinate is called acceptable if the norm of the code with
  respect to that coordinate is not more than two times the covering radius of
  the code plus one.
  
  ---------------------------  Example  ----------------------------
    gap> IsCoordinateAcceptable( HammingCode( 3, GF(2) ), 3 );
    true 
  ------------------------------------------------------------------
  
  7.4-4 GeneralizedCodeNorm
  
  > GeneralizedCodeNorm( C, subcode1, subscode2, ..., subcodek ) _____function
  
  GeneralizedCodeNorm returns the k-norm of C with respect to k subcodes.
  
  ---------------------------  Example  ----------------------------
    gap> c := RepetitionCode( 7, GF(2) );;
    gap> ham := HammingCode( 3, GF(2) );;
    gap> d := EvenWeightSubcode( ham );;
    gap> e := ConstantWeightSubcode( ham, 3 );;
    gap> GeneralizedCodeNorm( ham, c, d, e );
    4 
  ------------------------------------------------------------------
  
  7.4-5 IsNormalCode
  
  > IsNormalCode( C ) ________________________________________________function
  
  IsNormalCode  returns  `true' if C is normal. A code is called normal if the
  norm  of the code is not more than two times the covering radius of the code
  plus  one.  Almost  all codes are normal, however some (non-linear) abnormal
  codes have been found.
  
  Often,  it  is  difficult  to  find out whether a code is normal, because it
  involves  computing  the  covering  radius.  However, IsNormalCode uses much
  information  from the literature (in particular, [GS85]) about normality for
  certain code parameters.
  
  ---------------------------  Example  ----------------------------
    gap> IsNormalCode( HammingCode( 3, GF(2) ) );
    true 
  ------------------------------------------------------------------
  
  
  7.5 Miscellaneous functions
  
  In  this  section  we describe several vector space functions GUAVA uses for
  constructing codes or performing calculations with codes.
  
  In  this  section, some new miscellaneous functions are described, including
  weight  enumerators,  the  MacWilliams-transform  and  affinity  and  almost
  affinity of codes.
  
  7.5-1 CodeWeightEnumerator
  
  > CodeWeightEnumerator( C ) ________________________________________function
  
  CodeWeightEnumerator returns a polynomial of the following form:
  
  
       f(x) = \sum_{i=0}^{n} A_i x^i,
  
  
  where A_i is the number of codewords in C with weight i.
  
  ---------------------------  Example  ----------------------------
    gap> CodeWeightEnumerator( ElementsCode( [ [ 0,0,0 ], [ 0,0,1 ],
    > [ 0,1,1 ], [ 1,1,1 ] ], GF(2) ) );
    x^3 + x^2 + x + 1
    gap> CodeWeightEnumerator( HammingCode( 3, GF(2) ) );
    x^7 + 7*x^4 + 7*x^3 + 1 
  ------------------------------------------------------------------
  
  7.5-2 CodeDistanceEnumerator
  
  > CodeDistanceEnumerator( C, w ) ___________________________________function
  
  CodeDistanceEnumerator returns a polynomial of the following form:
  
  
       f(x) = \sum_{i=0}^{n} B_i x^i,
  
  
  where B_i is the number of codewords with distance i to w.
  
  If  w is a codeword, then CodeDistanceEnumerator returns the same polynomial
  as CodeWeightEnumerator.
  
  ---------------------------  Example  ----------------------------
    gap> CodeDistanceEnumerator( HammingCode( 3, GF(2) ),[0,0,0,0,0,0,1] );
    x^6 + 3*x^5 + 4*x^4 + 4*x^3 + 3*x^2 + x
    gap> CodeDistanceEnumerator( HammingCode( 3, GF(2) ),[1,1,1,1,1,1,1] );
    x^7 + 7*x^4 + 7*x^3 + 1 # `[1,1,1,1,1,1,1]' $\in$ `HammingCode( 3, GF(2 ) )'
  ------------------------------------------------------------------
  
  7.5-3 CodeMacWilliamsTransform
  
  > CodeMacWilliamsTransform( C ) ____________________________________function
  
  CodeMacWilliamsTransform returns a polynomial of the following form:
  
  
       f(x) = \sum_{i=0}^{n} C_i x^i,
  
  
  where C_i is the number of codewords with weight i in the dual code of C.
  
  ---------------------------  Example  ----------------------------
    gap> CodeMacWilliamsTransform( HammingCode( 3, GF(2) ) );
    7*x^4 + 1 
  ------------------------------------------------------------------
  
  7.5-4 CodeDensity
  
  > CodeDensity( C ) _________________________________________________function
  
  CodeDensity returns the density of C. The density of a code is defined as
  
  
       \frac{M \cdot V_q(n,t)}{q^n},
  
  
  where  M is the size of the code, V_q(n,t) is the size of a sphere of radius
  t  in GF(q^n) (which may be computed using SphereContent), t is the covering
  radius of the code and n is the length of the code.
  
  ---------------------------  Example  ----------------------------
    gap> CodeDensity( HammingCode( 3, GF(2) ) );
    1
    gap> CodeDensity( ReedMullerCode( 1, 4 ) );
    14893/2048 
  ------------------------------------------------------------------
  
  7.5-5 SphereContent
  
  > SphereContent( n, t, F ) _________________________________________function
  
  SphereContent  returns the content of a ball of radius t around an arbitrary
  element  of  the  vectorspace F^n. This is the cardinality of the set of all
  elements of F^n that are at distance (see DistanceCodeword (3.6-2) less than
  or equal to t from an element of F^n.
  
  In  the  context  of  codes,  the function is used to determine if a code is
  perfect.  A  code  is  perfect  if  spheres of radius t around all codewords
  partition  the  whole  ambient vector space, where t is the number of errors
  the code can correct.
  
  ---------------------------  Example  ----------------------------
    gap> SphereContent( 15, 0, GF(2) );
    1    # Only one word with distance 0, which is the word itself
    gap> SphereContent( 11, 3, GF(4) );
    4984
    gap> C := HammingCode(5);
    a linear [31,26,3]1 Hamming (5,2) code over GF(2)
    #the minimum distance is 3, so the code can correct one error
    gap> ( SphereContent( 31, 1, GF(2) ) * Size(C) ) = 2 ^ 31;
    true 
  ------------------------------------------------------------------
  
  7.5-6 Krawtchouk
  
  > Krawtchouk( k, i, n, q ) _________________________________________function
  
  Krawtchouk  returns the Krawtchouk number K_k(i). q must be a prime power, n
  must  be  a  positive integer, k must be a non-negative integer less then or
  equal  to  n  and  i  can  be any integer. (See KrawtchoukMat (7.3-1)). This
  number is the value at x=i of the polynomial
  
  
       K_k^{n,q}(x) =\sum_{j=0}^n (-1)^j(q-1)^{k-j}b(x,j)b(n-x,k-j),
  
  
  where  $b(v,u)=u!/(v!(v-u)!)$  is  the  binomial  coefficient  if  $u,v$ are
  integers. For more properties of these polynomials, see [MS83].
  
  ---------------------------  Example  ----------------------------
    gap> Krawtchouk( 2, 0, 3, 2);
    3 
  ------------------------------------------------------------------
  
  7.5-7 PrimitiveUnityRoot
  
  > PrimitiveUnityRoot( F, n ) _______________________________________function
  
  PrimitiveUnityRoot  returns  a  primitive n-th root of unity in an extension
  field  of  F. This is a finite field element a with the property a^n=1 in F,
  and n is the smallest integer such that this equality holds.
  
  ---------------------------  Example  ----------------------------
    gap> PrimitiveUnityRoot( GF(2), 15 );
    Z(2^4)
    gap> last^15;
    Z(2)^0
    gap> PrimitiveUnityRoot( GF(8), 21 );
    Z(2^6)^3 
  ------------------------------------------------------------------
  
  7.5-8 PrimitivePolynomialsNr
  
  > PrimitivePolynomialsNr( n, F ) ___________________________________function
  
  PrimitivePolynomialsNr  returns  the  number of irreducible polynomials over
  F=GF(q)  of degree n with (maximum) period q^n-1. (According to a theorem of
  S. Golomb, this is phi(p^n-1)/n.)
  
  See      also      the      GAP      function     RandomPrimitivePolynomial,
  RandomPrimitivePolynomial (2.2-2).
  
  ---------------------------  Example  ----------------------------
    gap> PrimitivePolynomialsNr(3,4);
    12
    
  ------------------------------------------------------------------
  
  7.5-9 IrreduciblePolynomialsNr
  
  > IrreduciblePolynomialsNr( n, F ) _________________________________function
  
  PrimitivePolynomialsNr  returns  the  number of irreducible polynomials over
  F=GF(q) of degree n.
  
  ---------------------------  Example  ----------------------------
    gap> IrreduciblePolynomialsNr(3,4);
    20
    
  ------------------------------------------------------------------
  
  7.5-10 MatrixRepresentationOfElement
  
  > MatrixRepresentationOfElement( a, F ) ____________________________function
  
  Here  F  is  either a finite extension of the ``base field'' GF(p) or of the
  rationals Q}, and ain F. The command MatrixRepresentationOfElement returns a
  matrix representation of a over the base field.
  
  If  the  element  a  is  defined  over  the  base  field then it returns the
  corresponding 1x 1 matrix.
  
  ---------------------------  Example  ----------------------------
    gap> a:=Random(GF(4));
    0*Z(2)
    gap> M:=MatrixRepresentationOfElement(a,GF(4));; Display(M);
     .
    gap> a:=Random(GF(4));
    Z(2^2)
    gap> M:=MatrixRepresentationOfElement(a,GF(4));; Display(M);
     . 1
     1 1
    gap>
    
  ------------------------------------------------------------------
  
  7.5-11 ReciprocalPolynomial
  
  > ReciprocalPolynomial( P ) ________________________________________function
  
  ReciprocalPolynomial  returns  the  reciprocal  of  polynomial  P. This is a
  polynomial  with coefficients of P in the reverse order. So if P=a_0 + a_1 X
  +  ...  + a_n X^n, the reciprocal polynomial is P'=a_n + a_n-1 X + ... + a_0
  X^n.
  
  This command can also be called using the syntax ReciprocalPolynomial( P , n
  ).  In this form, the number of coefficients of P is assumed to be less than
  or  equal  to  n+1  (with zero coefficients added in the highest degrees, if
  necessary). Therefore, the reciprocal polynomial also has degree n+1.
  
  ---------------------------  Example  ----------------------------
    gap> P := UnivariatePolynomial( GF(3), Z(3)^0 * [1,0,1,2] );
    Z(3)^0+x_1^2-x_1^3
    gap> RecP := ReciprocalPolynomial( P );
    -Z(3)^0+x_1+x_1^3
    gap> ReciprocalPolynomial( RecP ) = P;
    true 
    gap> P := UnivariatePolynomial( GF(3), Z(3)^0 * [1,0,1,2] );
    Z(3)^0+x_1^2-x_1^3
    gap> ReciprocalPolynomial( P, 6 );
    -x_1^3+x_1^4+x_1^6
  ------------------------------------------------------------------
  
  7.5-12 CyclotomicCosets
  
  > CyclotomicCosets( q, n ) _________________________________________function
  
  CyclotomicCosets  returns  the cyclotomic cosets of q mod n. q and n must be
  relatively  prime.  Each  of  the elements of the returned list is a list of
  integers  that belong to one cyclotomic coset. A q-cyclotomic coset of s mod
  n  is  a  set  of  the  form  s,sq,sq^2,...,sq^r-1,  where r is the smallest
  positive  integer  such  that  sq^r-s is 0 mod n. In other words, each coset
  contains  all  multiplications  of  the coset representative by q mod n. The
  coset  representative  is  the  smallest  integer that isn't in the previous
  cosets.
  
  ---------------------------  Example  ----------------------------
    gap> CyclotomicCosets( 2, 15 );
    [ [ 0 ], [ 1, 2, 4, 8 ], [ 3, 6, 12, 9 ], [ 5, 10 ],
      [ 7, 14, 13, 11 ] ]
    gap> CyclotomicCosets( 7, 6 );
    [ [ 0 ], [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ] 
  ------------------------------------------------------------------
  
  7.5-13 WeightHistogram
  
  > WeightHistogram( C[, h] ) ________________________________________function
  
  The  function  WeightHistogram  plots  a histogram of weights in code C. The
  maximum  length  of a column is h. Default value for h is 1/3 of the size of
  the  screen.  The  number  that  appears  at the top of the histogram is the
  maximum value of the list of weights.
  
  ---------------------------  Example  ----------------------------
    gap> H := HammingCode(2, GF(5));
    a linear [6,4,3]1 Hamming (2,5) code over GF(5)
    gap> WeightDistribution(H);
    [ 1, 0, 0, 80, 120, 264, 160 ]
    gap> WeightHistogram(H);
    264----------------
                   *
                   *
                   *
                   *
                   *  *
                *  *  *
             *  *  *  *
             *  *  *  *
    +--------+--+--+--+--
    0  1  2  3  4  5  6 
  ------------------------------------------------------------------
  
  7.5-14 MultiplicityInList
  
  > MultiplicityInList( L, a ) _______________________________________function
  
  This  is a very simple list command which returns how many times a occurs in
  L.  It returns 0 if a is not in L. (The GAP command Collected does not quite
  handle this "extreme" case.)
  
  ---------------------------  Example  ----------------------------
    gap> L:=[1,2,3,4,3,2,1,5,4,3,2,1];;
    gap> MultiplicityInList(L,1);
    3
    gap> MultiplicityInList(L,6);
    0
  ------------------------------------------------------------------
  
  7.5-15 MostCommonInList
  
  > MostCommonInList( L ) ____________________________________________function
  
  Input: a list L
  
  Output: an a in L which occurs at least as much as any other in L
  
  ---------------------------  Example  ----------------------------
    gap> L:=[1,2,3,4,3,2,1,5,4,3,2,1];;
    gap> MostCommonInList(L);
    1
  ------------------------------------------------------------------
  
  7.5-16 RotateList
  
  > RotateList( L ) __________________________________________________function
  
  Input: a list L
  
  Output: a list L' which is the cyclic rotation of L (to the right)
  
  ---------------------------  Example  ----------------------------
    gap> L:=[1,2,3,4];;
    gap> RotateList(L);
    [2,3,4,1]
  ------------------------------------------------------------------
  
  7.5-17 CirculantMatrix
  
  > CirculantMatrix( k, L ) __________________________________________function
  
  Input: integer k, a list L of length n
  
  Output: kxn matrix whose rows are cyclic rotations of the list L
  
  ---------------------------  Example  ----------------------------
    gap> k:=3; L:=[1,2,3,4];;
    gap> M:=CirculantMatrix(k,L);;
    gap> Display(M);
  ------------------------------------------------------------------
  
  
  7.6 Miscellaneous polynomial functions
  
  In  this  section  we describe several multivariate polynomial GAP functions
  GUAVA uses for constructing codes or performing calculations with codes.
  
  7.6-1 MatrixTransformationOnMultivariatePolynomial 
  
  > MatrixTransformationOnMultivariatePolynomial ( AfR ) _____________function
  
  A  is  an nx n matrix with entries in a field F, R is a polynomial ring of n
  variables,  say  F[x_1,...,x_n],  and  f  is  a polynomial in R. Returns the
  composition fcirc A.
  
  7.6-2 DegreeMultivariatePolynomial
  
  > DegreeMultivariatePolynomial( f, R ) _____________________________function
  
  This  command  takes  two  arguments,  f, a multivariate polynomial, and R a
  polynomial  ring  over a field F containing f, say R=F[x_1,x_2,...,x_n]. The
  output is simply the maximum degrees of all the monomials occurring in f.
  
  This command can be used to compute the degree of an affine plane curve.
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(11);;
    gap> R2:=PolynomialRing(F,2);
    PolynomialRing(..., [ x_1, x_2 ])
    gap> vars:=IndeterminatesOfPolynomialRing(R2);;
    gap> x:=vars[1];; y:=vars[2];;
    gap> poly:=y^2-x*(x^2-1);;
    gap> DegreeMultivariatePolynomial(poly,R2);
    3
    
  ------------------------------------------------------------------
  
  7.6-3 DegreesMultivariatePolynomial
  
  > DegreesMultivariatePolynomial( f, R ) ____________________________function
  
  Returns  a list of information about the multivariate polynomial f. Nice for
  other programs but mostly unreadable by GAP users.
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(11);;
    gap> R2:=PolynomialRing(F,2);
    PolynomialRing(..., [ x_1, x_2 ])
    gap> vars:=IndeterminatesOfPolynomialRing(R2);;
    gap> x:=vars[1];; y:=vars[2];;
    gap> poly:=y^2-x*(x^2-1);;
    gap> DegreesMultivariatePolynomial(poly,R2);
    [ [ [ x_1, x_1, 1 ], [ x_1, x_2, 0 ] ], [ [ x_2^2, x_1, 0 ], [ x_2^2, x_2, 2 ] ],
      [ [ x_1^3, x_1, 3 ], [ x_1^3, x_2, 0 ] ] ]
    gap>
    
  ------------------------------------------------------------------
  
  7.6-4 CoefficientMultivariatePolynomial
  
  > CoefficientMultivariatePolynomial( f, var, power, R ) ____________function
  
  The   command  CoefficientMultivariatePolynomial  takes  four  arguments:  a
  multivariant  polynomial  f,  a  variable  name var, an integer power, and a
  polynomial  ring  R  containing  f.  For  example,  if  f  is a multivariate
  polynomial  in  R  = F[x_1,x_2,...,x_n] then var must be one of the x_i. The
  output is the coefficient of x_i^power in f.
  
  (Not sure if F needs to be a field in fact ...)
  
  Related to the GAP command PolynomialCoefficientsPolynomial.
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(11);;
    gap> R2:=PolynomialRing(F,2);
    PolynomialRing(..., [ x_1, x_2 ])
    gap> vars:=IndeterminatesOfPolynomialRing(R2);;
    gap> x:=vars[1];; y:=vars[2];;
    gap> poly:=y^2-x*(x^2-1);;
    gap> PolynomialCoefficientsOfPolynomial(poly,x);
    [ x_2^2, Z(11)^0, 0*Z(11), -Z(11)^0 ]
    gap> PolynomialCoefficientsOfPolynomial(poly,y);
    [ -x_1^3+x_1, 0*Z(11), Z(11)^0 ]
    gap> CoefficientMultivariatePolynomial(poly,y,0,R2);
    -x_1^3+x_1
    gap> CoefficientMultivariatePolynomial(poly,y,1,R2);
    0*Z(11)
    gap> CoefficientMultivariatePolynomial(poly,y,2,R2);
    Z(11)^0
    gap> CoefficientMultivariatePolynomial(poly,x,0,R2);
    x_2^2
    gap> CoefficientMultivariatePolynomial(poly,x,1,R2);
    Z(11)^0
    gap> CoefficientMultivariatePolynomial(poly,x,2,R2);
    0*Z(11)
    gap> CoefficientMultivariatePolynomial(poly,x,3,R2);
    -Z(11)^0
    
  ------------------------------------------------------------------
  
  7.6-5 SolveLinearSystem
  
  > SolveLinearSystem( L, vars ) _____________________________________function
  
  Input: L is a list of linear forms in the variables vars.
  
  Output: the solution of the system, if its unique.
  
  The  procedure  is  straightforward:  Find the associated matrix A, find the
  "constant vector" b, and solve A*v=b. No error checking is performed.
  
  Related to the GAP command SolutionMat( A, b ).
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(11);;
    gap> R2:=PolynomialRing(F,2);
    PolynomialRing(..., [ x_1, x_2 ])
    gap> vars:=IndeterminatesOfPolynomialRing(R2);;
    gap> x:=vars[1];; y:=vars[2];;
    gap> f:=3*y-3*x+1;; g:=-5*y+2*x-7;;
    gap> soln:=SolveLinearSystem([f,g],[x,y]);
    [ Z(11)^3, Z(11)^2 ]
    gap> Value(f,[x,y],soln); # checking okay
    0*Z(11)
    gap> Value(g,[x,y],col); # checking okay
    0*Z(11)
    
  ------------------------------------------------------------------
  
  7.6-6 GuavaVersion
  
  > GuavaVersion(  ) _________________________________________________function
  
  Returns the current version of Guava. Same as guava\_version().
  
  ---------------------------  Example  ----------------------------
    gap> GuavaVersion();
    "2.7"
    
  ------------------------------------------------------------------
  
  7.6-7 ZechLog
  
  > ZechLog( x, b, F ) _______________________________________________function
  
  Returns  the  Zech  log  of  x  to  base b, ie the i such that $x+1=b^i$, so
  $y+z=y(1+z/y)=b^k$,   where   k=Log(y,b)+ZechLog(z/y,b)  and  b  must  be  a
  primitive element of F.
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(11);; l := One(F);;
    gap> ZechLog(2*l,8*l,F);
    -24
    gap> 8*l+l;(2*l)^(-24);
    Z(11)^6
    Z(11)^6
    
  ------------------------------------------------------------------
  
  7.6-8 CoefficientToPolynomial
  
  > CoefficientToPolynomial( coeffs, R ) _____________________________function
  
  The  function  CoefficientToPolynomial  returns  the  degree  d-1 polynomial
  c_0+c_1x+...+c_d-1x^d-1,  where  coeffs  is  a  list of elements of a field,
  coeffs= c_0,...,c_d-1, and R is a univariate polynomial ring.
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(11);
    GF(11)
    gap> R1:=PolynomialRing(F,["a"]);;
    gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
    gap> coeffs:=Z(11)^0*[1,2,3,4];
    [ Z(11)^0, Z(11), Z(11)^8, Z(11)^2 ]
    gap> CoefficientToPolynomial(coeffs,R1);
    Z(11)^2*a^3+Z(11)^8*a^2+Z(11)*a+Z(11)^0
  ------------------------------------------------------------------
  
  7.6-9 DegreesMonomialTerm
  
  > DegreesMonomialTerm( m, R ) ______________________________________function
  
  The  function  DegreesMonomialTerm returns the list of degrees to which each
  variable  in  the  multivariate  polynomial ring R occurs in the monomial m,
  where coeffs is a list of elements of a field.
  
  ---------------------------  Example  ----------------------------
    gap> F:=GF(11);
    GF(11)
    gap> R1:=PolynomialRing(F,["a"]);;
    gap> var1:=IndeterminatesOfPolynomialRing(R1);; a:=var1[1];;
    gap> b:=X(F,"b",var1);
    b
    gap> var2:=Concatenation(var1,[b]);
    [ a, b ]
    gap> R2:=PolynomialRing(F,var2);
    PolynomialRing(..., [ a, b ])
    gap> c:=X(F,"c",var2);
    c
    gap> var3:=Concatenation(var2,[c]);
    [ a, b, c ]
    gap> R3:=PolynomialRing(F,var3);
    PolynomialRing(..., [ a, b, c ])
    gap> m:=b^3*c^7;
    b^3*c^7
    gap> DegreesMonomialTerm(m,R3);
    [ 0, 3, 7 ]
  ------------------------------------------------------------------
  
  7.6-10 DivisorsMultivariatePolynomial
  
  > DivisorsMultivariatePolynomial( f, R ) ___________________________function
  
  The  function  DivisorsMultivariatePolynomial returns the list of polynomial
  divisors  of  f in the multivariate polynomial ring R with coefficients in a
  field.  This  program  uses a simple but slow algorithm (see Joachim von zur
  Gathen,  Jürgen  Gerhard,  [GG03],  exercise 16.10) which first converts the
  multivariate  polynomial  f to an associated univariate polynomial f^*, then
  Factors  f^*,  and  finally  converts these univariate factors back into the
  multivariate  polynomial  factors  of f. Since Factors is non-deterministic,
  DivisorsMultivariatePolynomial is non-deterministic as well.
  
  ---------------------------  Example  ----------------------------
    gap> R2:=PolynomialRing(GF(3),["x1","x2"]);
    PolynomialRing(..., [ x1, x2 ])
    gap> vars:=IndeterminatesOfPolynomialRing(R2);
    [ x1, x2 ]
    gap> x2:=vars[2];
    x2
    gap> x1:=vars[1];
    x1
    gap> f:=x1^3+x2^3;;
    gap> DivisorsMultivariatePolynomial(f,R2);
    [ x1+x2, x1+x2, x1+x2 ]
  ------------------------------------------------------------------
  
  
  7.7 GNU Free Documentation License
  
  GNU Free Documentation License Version 1.2, November 2002
  
  Copyright  (C) 2000,2001,2002 Free Software Foundation, Inc. 51 Franklin St,
  Fifth  Floor,  Boston,  MA  02110-1301 USA Everyone is permitted to copy and
  distribute  verbatim copies of this license document, but changing it is not
  allowed.
  
  0. PREAMBLE
  
  The  purpose  of  this  License  is  to  make  a  manual, textbook, or other
  functional  and  useful  document  "free" in the sense of freedom: to assure
  everyone  the effective freedom to copy and redistribute it, with or without
  modifying  it,  either  commercially  or  noncommercially. Secondarily, this
  License preserves for the author and publisher a way to get credit for their
  work,  while  not  being  considered  responsible  for modifications made by
  others.
  
  This  License  is a kind of "copyleft", which means that derivative works of
  the  document  must themselves be free in the same sense. It complements the
  GNU  General  Public  License, which is a copyleft license designed for free
  software.
  
  We  have  designed  this  License  in  order  to use it for manuals for free
  software,  because  free  software  needs free documentation: a free program
  should come with manuals providing the same freedoms that the software does.
  But  this License is not limited to software manuals; it can be used for any
  textual  work,  regardless of subject matter or whether it is published as a
  printed  book. We recommend this License principally for works whose purpose
  is instruction or reference.
  
  1. APPLICABILITY AND DEFINITIONS
  
  This  License  applies  to  any  manual  or  other work, in any medium, that
  contains  a  notice  placed  by  the  copyright  holder  saying  it  can  be
  distributed  under  the  terms  of  this  License.  Such  a  notice grants a
  world-wide,  royalty-free  license,  unlimited in duration, to use that work
  under  the  conditions  stated  herein. The "Document", below, refers to any
  such  manual  or  work.  Any  member  of  the  public  is a licensee, and is
  addressed as "you". You accept the license if you copy, modify or distribute
  the work in a way requiring permission under copyright law.
  
  A  "Modified Version" of the Document means any work containing the Document
  or  a  portion  of  it, either copied verbatim, or with modifications and/or
  translated into another language.
  
  A  "Secondary  Section" is a named appendix or a front-matter section of the
  Document  that  deals exclusively with the relationship of the publishers or
  authors  of  the  Document  to the Document's overall subject (or to related
  matters)  and  contains nothing that could fall directly within that overall
  subject.  (Thus,  if  the  Document  is in part a textbook of mathematics, a
  Secondary  Section  may not explain any mathematics.) The relationship could
  be  a  matter  of  historical  connection  with  the subject or with related
  matters,  or  of  legal,  commercial,  philosophical,  ethical  or political
  position regarding them.
  
  The  "Invariant  Sections"  are  certain Secondary Sections whose titles are
  designated,  as  being  those of Invariant Sections, in the notice that says
  that  the Document is released under this License. If a section does not fit
  the above definition of Secondary then it is not allowed to be designated as
  Invariant. The Document may contain zero Invariant Sections. If the Document
  does not identify any Invariant Sections then there are none.
  
  The  "Cover  Texts"  are  certain short passages of text that are listed, as
  Front-Cover  Texts  or  Back-Cover  Texts,  in the notice that says that the
  Document is released under this License. A Front-Cover Text may be at most 5
  words, and a Back-Cover Text may be at most 25 words.
  
  A  "Transparent"  copy  of  the  Document  means  a  machine-readable  copy,
  represented  in  a  format  whose  specification is available to the general
  public,  that  is  suitable for revising the document straightforwardly with
  generic  text  editors  or  (for  images  composed  of pixels) generic paint
  programs or (for drawings) some widely available drawing editor, and that is
  suitable  for  input  to  text  formatters or for automatic translation to a
  variety  of formats suitable for input to text formatters. A copy made in an
  otherwise  Transparent  file  format whose markup, or absence of markup, has
  been  arranged to thwart or discourage subsequent modification by readers is
  not  Transparent.  An  image  format  is  not  Transparent  if  used for any
  substantial  amount  of  text.  A  copy  that is not "Transparent" is called
  "Opaque".
  
  Examples  of  suitable  formats  for  Transparent copies include plain ASCII
  without  markup, Texinfo input format, LaTeX input format, SGML or XML using
  a publicly available DTD, and standard-conforming simple HTML, PostScript or
  PDF  designed  for human modification. Examples of transparent image formats
  include  PNG,  XCF  and JPG. Opaque formats include proprietary formats that
  can  be read and edited only by proprietary word processors, SGML or XML for
  which  the  DTD and/or processing tools are not generally available, and the
  machine-generated  HTML,  PostScript or PDF produced by some word processors
  for output purposes only.
  
  The "Title Page" means, for a printed book, the title page itself, plus such
  following  pages  as  are needed to hold, legibly, the material this License
  requires to appear in the title page. For works in formats which do not have
  any  title page as such, "Title Page" means the text near the most prominent
  appearance  of  the work's title, preceding the beginning of the body of the
  text.
  
  A  section  "Entitled XYZ" means a named subunit of the Document whose title
  either  is  precisely XYZ or contains XYZ in parentheses following text that
  translates  XYZ in another language. (Here XYZ stands for a specific section
  name   mentioned   below,   such   as   "Acknowledgements",   "Dedications",
  "Endorsements",  or  "History".)  To  "Preserve the Title" of such a section
  when  you modify the Document means that it remains a section "Entitled XYZ"
  according to this definition.
  
  The  Document  may  include  Warranty  Disclaimers  next to the notice which
  states that this License applies to the Document. These Warranty Disclaimers
  are  considered  to  be  included  by reference in this License, but only as
  regards  disclaiming  warranties:  any other implication that these Warranty
  Disclaimers  may  have  is  void  and  has  no effect on the meaning of this
  License.
  
  2. VERBATIM COPYING
  
  You  may copy and distribute the Document in any medium, either commercially
  or  noncommercially,  provided that this License, the copyright notices, and
  the  license  notice  saying  this  License  applies  to  the  Document  are
  reproduced in all copies, and that you add no other conditions whatsoever to
  those  of  this  License.  You may not use technical measures to obstruct or
  control the reading or further copying of the copies you make or distribute.
  However,  you  may  accept  compensation  in  exchange  for  copies.  If you
  distribute  a  large  enough  number  of  copies  you  must  also follow the
  conditions in section 3.
  
  You  may  also  lend copies, under the same conditions stated above, and you
  may publicly display copies.
  
  3. COPYING IN QUANTITY
  
  If you publish printed copies (or copies in media that commonly have printed
  covers) of the Document, numbering more than 100, and the Document's license
  notice  requires  Cover  Texts,  you  must enclose the copies in covers that
  carry,  clearly and legibly, all these Cover Texts: Front-Cover Texts on the
  front  cover,  and Back-Cover Texts on the back cover. Both covers must also
  clearly and legibly identify you as the publisher of these copies. The front
  cover  must  present  the  full  title  with  all words of the title equally
  prominent and visible. You may add other material on the covers in addition.
  Copying  with  changes  limited  to the covers, as long as they preserve the
  title  of  the  Document  and  satisfy  these  conditions, can be treated as
  verbatim copying in other respects.
  
  If  the  required  texts for either cover are too voluminous to fit legibly,
  you  should  put  the  first  ones listed (as many as fit reasonably) on the
  actual cover, and continue the rest onto adjacent pages.
  
  If  you  publish  or distribute Opaque copies of the Document numbering more
  than  100, you must either include a machine-readable Transparent copy along
  with   each   Opaque   copy,  or  state  in  or  with  each  Opaque  copy  a
  computer-network  location  from  which the general network-using public has
  access  to  download  using  public-standard  network  protocols  a complete
  Transparent  copy  of  the  Document, free of added material. If you use the
  latter  option,  you  must  take  reasonably  prudent  steps, when you begin
  distribution  of  Opaque copies in quantity, to ensure that this Transparent
  copy  will  remain thus accessible at the stated location until at least one
  year  after the last time you distribute an Opaque copy (directly or through
  your agents or retailers) of that edition to the public.
  
  It  is  requested,  but  not  required,  that you contact the authors of the
  Document well before redistributing any large number of copies, to give them
  a chance to provide you with an updated version of the Document.
  
  4. MODIFICATIONS
  
  You  may  copy  and  distribute a Modified Version of the Document under the
  conditions of sections 2 and 3 above, provided that you release the Modified
  Version  under precisely this License, with the Modified Version filling the
  role  of  the  Document, thus licensing distribution and modification of the
  Modified Version to whoever possesses a copy of it. In addition, you must do
  these things in the Modified Version:
  
  A.  Use  in the Title Page (and on the covers, if any) a title distinct from
  that  of the Document, and from those of previous versions (which should, if
  there  were  any, be listed in the History section of the Document). You may
  use  the  same title as a previous version if the original publisher of that
  version gives permission.
  
  B.  List  on  the  Title  Page,  as authors, one or more persons or entities
  responsible  for  authorship  of  the modifications in the Modified Version,
  together with at least five of the principal authors of the Document (all of
  its  principal  authors, if it has fewer than five), unless they release you
  from this requirement.
  
  C.  State  on  the  Title  page  the  name  of the publisher of the Modified
  Version, as the publisher.
  
  D. Preserve all the copyright notices of the Document.
  
  E.  Add  an  appropriate copyright notice for your modifications adjacent to
  the other copyright notices.
  
  F. Include, immediately after the copyright notices, a license notice giving
  the  public  permission  to use the Modified Version under the terms of this
  License, in the form shown in the Addendum below.
  
  G.  Preserve in that license notice the full lists of Invariant Sections and
  required Cover Texts given in the Document's license notice.
  
  H. Include an unaltered copy of this License.
  
  I.  Preserve  the section Entitled "History", Preserve its Title, and add to
  it  an  item stating at least the title, year, new authors, and publisher of
  the  Modified  Version  as  given  on the Title Page. If there is no section
  Entitled  "History"  in  the  Document,  create one stating the title, year,
  authors,  and publisher of the Document as given on its Title Page, then add
  an item describing the Modified Version as stated in the previous sentence.
  
  J.  Preserve  the network location, if any, given in the Document for public
  access  to  a  Transparent  copy  of  the Document, and likewise the network
  locations given in the Document for previous versions it was based on. These
  may  be placed in the "History" section. You may omit a network location for
  a work that was published at least four years before the Document itself, or
  if the original publisher of the version it refers to gives permission.
  
  K.  For  any  section Entitled "Acknowledgements" or "Dedications", Preserve
  the  Title of the section, and preserve in the section all the substance and
  tone  of  each  of the contributor acknowledgements and/or dedications given
  therein.
  
  L.  Preserve  all the Invariant Sections of the Document, unaltered in their
  text  and  in  their  titles.  Section  numbers  or  the  equivalent are not
  considered part of the section titles.
  
  M.  Delete  any  section  Entitled "Endorsements". Such a section may not be
  included in the Modified Version.
  
  N.  Do  not retitle any existing section to be Entitled "Endorsements" or to
  conflict in title with any Invariant Section.
  
  O. Preserve any Warranty Disclaimers.
  
  If  the  Modified  Version  includes new front-matter sections or appendices
  that  qualify  as Secondary Sections and contain no material copied from the
  Document,  you may at your option designate some or all of these sections as
  invariant. To do this, add their titles to the list of Invariant Sections in
  the  Modified  Version's  license notice. These titles must be distinct from
  any other section titles.
  
  You  may add a section Entitled "Endorsements", provided it contains nothing
  but  endorsements  of your Modified Version by various parties--for example,
  statements  of  peer  review  or  that  the  text  has  been  approved by an
  organization as the authoritative definition of a standard.
  
  You  may  add  a  passage  of  up to five words as a Front-Cover Text, and a
  passage  of  up  to 25 words as a Back-Cover Text, to the end of the list of
  Cover  Texts  in  the Modified Version. Only one passage of Front-Cover Text
  and one of Back-Cover Text may be added by (or through arrangements made by)
  any  one  entity. If the Document already includes a cover text for the same
  cover, previously added by you or by arrangement made by the same entity you
  are  acting  on  behalf of, you may not add another; but you may replace the
  old  one,  on explicit permission from the previous publisher that added the
  old one.
  
  The  author(s)  and publisher(s) of the Document do not by this License give
  permission  to  use  their  names  for  publicity  for or to assert or imply
  endorsement of any Modified Version.
  
  5. COMBINING DOCUMENTS
  
  You  may  combine  the  Document  with  other  documents released under this
  License,  under  the terms defined in section 4 above for modified versions,
  provided  that  you include in the combination all of the Invariant Sections
  of all of the original documents, unmodified, and list them all as Invariant
  Sections  of your combined work in its license notice, and that you preserve
  all their Warranty Disclaimers.
  
  The  combined  work need only contain one copy of this License, and multiple
  identical  Invariant  Sections  may be replaced with a single copy. If there
  are  multiple  Invariant Sections with the same name but different contents,
  make  the  title  of each such section unique by adding at the end of it, in
  parentheses, the name of the original author or publisher of that section if
  known,  or  else  a  unique  number. Make the same adjustment to the section
  titles  in  the  list  of  Invariant  Sections  in the license notice of the
  combined work.
  
  In  the combination, you must combine any sections Entitled "History" in the
  various original documents, forming one section Entitled "History"; likewise
  combine  any sections Entitled "Acknowledgements", and any sections Entitled
  "Dedications". You must delete all sections Entitled "Endorsements".
  
  6. COLLECTIONS OF DOCUMENTS
  
  You  may  make  a  collection consisting of the Document and other documents
  released  under  this  License,  and  replace  the individual copies of this
  License  in the various documents with a single copy that is included in the
  collection,  provided that you follow the rules of this License for verbatim
  copying of each of the documents in all other respects.
  
  You  may extract a single document from such a collection, and distribute it
  individually  under this License, provided you insert a copy of this License
  into  the  extracted document, and follow this License in all other respects
  regarding verbatim copying of that document.
  
  7. AGGREGATION WITH INDEPENDENT WORKS
  
  A  compilation  of  the  Document or its derivatives with other separate and
  independent  documents  or  works,  in  or  on  a  volume  of  a  storage or
  distribution  medium,  is  called  an "aggregate" if the copyright resulting
  from  the  compilation  is  not  used  to  limit  the  legal  rights  of the
  compilation's  users  beyond  what  the  individual  works  permit. When the
  Document  is  included  in  an aggregate, this License does not apply to the
  other  works  in  the aggregate which are not themselves derivative works of
  the Document.
  
  If  the Cover Text requirement of section 3 is applicable to these copies of
  the  Document,  then  if  the  Document  is less than one half of the entire
  aggregate,  the  Document's Cover Texts may be placed on covers that bracket
  the Document within the aggregate, or the electronic equivalent of covers if
  the  Document  is  in electronic form. Otherwise they must appear on printed
  covers that bracket the whole aggregate.
  
  8. TRANSLATION
  
  Translation  is  considered  a  kind  of modification, so you may distribute
  translations  of  the  Document  under  the  terms  of  section 4. Replacing
  Invariant  Sections with translations requires special permission from their
  copyright holders, but you may include translations of some or all Invariant
  Sections  in  addition to the original versions of these Invariant Sections.
  You  may  include a translation of this License, and all the license notices
  in  the  Document,  and  any  Warranty  Disclaimers,  provided that you also
  include  the  original  English  version  of  this  License and the original
  versions of those notices and disclaimers. In case of a disagreement between
  the  translation  and  the  original  version of this License or a notice or
  disclaimer, the original version will prevail.
  
  If  a section in the Document is Entitled "Acknowledgements", "Dedications",
  or  "History", the requirement (section 4) to Preserve its Title (section 1)
  will typically require changing the actual title.
  
  9. TERMINATION
  
  You  may  not copy, modify, sublicense, or distribute the Document except as
  expressly  provided  for  under  this  License.  Any  other attempt to copy,
  modify,   sublicense   or   distribute   the  Document  is  void,  and  will
  automatically terminate your rights under this License. However, parties who
  have  received  copies, or rights, from you under this License will not have
  their licenses terminated so long as such parties remain in full compliance.
  
  10. FUTURE REVISIONS OF THIS LICENSE
  
  The  Free  Software  Foundation may publish new, revised versions of the GNU
  Free  Documentation  License  from  time  to time. Such new versions will be
  similar  in  spirit  to  the  present  version,  but may differ in detail to
  address new problems or concerns. See http://www.gnu.org/copyleft/.
  
  Each version of the License is given a distinguishing version number. If the
  Document  specifies  that  a particular numbered version of this License "or
  any later version" applies to it, you have the option of following the terms
  and conditions either of that specified version or of any later version that
  has  been published (not as a draft) by the Free Software Foundation. If the
  Document  does  not specify a version number of this License, you may choose
  any version ever published (not as a draft) by the Free Software Foundation.