Covering codes for the fixed length Levenshtein metric

A covering code, or a covering, is a set of codewords such that the union of balls centered at these codewords covers the entire space. As a rule, the problem consists in finding the minimum cardinality of a covering code. For the classical Hamming metric, the size of the smallest covering code of a fixed radius $R$ is known up to a constant factor. A similar result has recently been obtained for codes with $R$ insertions and for codes with $R$ deletions. In the present paper we study coverings of a space for the fixed length Levenshtein metric, i.e., for $R$ insertions and $R$ deletions. For $R = 1$ and $2$, we prove new lower and upper bounds on the minimum cardinality of a covering code, which differ by a constant factor only.