# 65.142 Some functions for the covering radius

Together with the new code constructions, the new functions for computing (the bounds of) the covering radius are the most important additions to GUAVA.

These additions required a change in the fields of a code record. In previous versions of GUAVA, the covering radius field was an integer field, called `coveringRadius`. To allow the code-record to contain more information about the covering radius, this field has been replaced by a field called `boundsCoveringRadius`. This field contains a vector of possible values of the covering radius of the code. If the value of the covering radius is known, then the length of this vector is one.

This means that every instance of `coveringRadius` in the previous version had to be changed to `boundsCoveringRadius`. There is also an advantage to this: if bounds for a specific type of code are known, they can be implemented (and they have been). This has been especially useful for the Reed-Muller codes.

Of course, the main covering radius function dispatcher, `CoveringRadius`, had to be changed to incorporate these changes. Previously, this dispatcher called
`code.operations.CoveringRadius`. Problem with these functions is that they only work if the redundancy is not too large. Another problem is that the algorithm for linear and cyclic codes is written in `C` (in the kernel of GAP). This does not allow the user to interrupt the function, except by pressing `ctrl-C` twice, which exits GAP altogether. For more information, check the section on the (new) `CoveringRadius` (CoveringRadius) function.

Perhaps the most interesting new covering radius function is
`IncreaseCoveringRadiusLowerBound` (IncreaseCoveringRadiusLowerBound). It uses a probabilistic algorithm that tries to find better lower bounds of the covering radius of a code. It works best when the dimension is low, thereby giving a sort of complement function to `CoveringRadius`. When the dimension is about half the length of a code, neither algorithm will work, although `IncreaseCoveringRadiusLowerBound` is specifically designed to avoid memory problems, unlike `CoveringRadius`.

The function `ExhaustiveSearchCoveringRadius` (ExhaustiveSearchCoveringRadius) tries to find the covering radius of a code by exhaustively searching the space in which the code lies for coset leaders.

A number of bounds for the covering radius in general have been implemented, including some well known bounds like the sphere-covering bound, the redundancy bound and the Delsarte bound. These function all start with `LowerBoundCoveringRadius` (sections LowerBoundCoveringRadiusSphereCovering, LowerBoundCoveringRadiusVanWee1, LowerBoundCoveringRadiusVanWee2, LowerBoundCoveringRadiusCountingExcess, LowerBoundCoveringRadiusEmbedded1, LowerBoundCoveringRadiusEmbedded2, LowerBoundCoveringRadiusInduction, LowerBoundCoveringRadiusSphereCovering) or `UpperBoundCoveringRadius` (sections UpperBoundCoveringRadiusRedundancy, UpperBoundCoveringRadiusDelsarte, UpperBoundCoveringRadiusStrength, UpperBoundCoveringRadiusGriesmerLike, UpperBoundCoveringRadiusCyclicCode).

The functions `GeneralLowerBoundCoveringRadius` (GeneralLowerBoundCoveringRadius) and
`GeneralUpperBoundCoveringRadius` (GeneralUpperBoundCoveringRadius) try to find the best known bounds for a given code. `BoundsCoveringRadius` (BoundsCoveringRadius) uses these functions to return a vector of possible values for the covering radius.

To allow the user to enter values in the `.boundsCoveringRadius` record herself, the function `SetCoveringRadius` is provided.

GAP 3.4.4
April 1997