Long distance string problem

Question

We are considering length n strings over the alphabet S.

The goal is to compute a set of string, M, such that for any string, x, in S^n there exists a string, y, in M such that the hamming distance between x and y is at least r.

A way of thinking of this is that we want to guarantee that for any string, we have a string in our solution M which is far away from the given string.

For a given S (with size at least 3), n and r (which may be a funciton of n, for example n/2) for many strings a needed to include in M to guarantee that for any string in S^n, we have a string in M which has a hamming distance to it of at least r.

I have a feeling this is well studied and might be related to covering designs. Can someone give me a good reference (or insight)? I would be very grateful.

Answer 1

Look up the concept of anticodes. Some bounds exist.

Also if you have a linear $t-$error correcting code over $GF(q)$ with length $n$ and covering radius $r$ and use homogeneity under translations by adding vectors $n-d=n-2t-1$ would seem to be your answer but I haven't checked carefully. Cohen and Litsyn have a book on covering codes.

A Simple Construction

Fix $k\geq 1$ and let $v=\lceil n/k \rceil$ and consider the strings as $GF(q)^n.$ Generate all $k-$tuples over $GF(q)$ to obtain $M=q^k$ codewords. Map these codewords to $GF(q)^n$ by expanding by $v$ for the first $k-1$ coordinates and expanding by $n-(k-1)v$ for the last coordinate. For example, let $q=3,$ $n=5$ and $k=2.$ Your codewords are $$ \begin{array}{cc} 0&0\\ 0&1\\ 0&2\\ 1&0\\ 1&1\\ 1&2\\ 2&0\\ 2&1\\ 2&2\\ \end{array} $$

which become upon expansion with $v=4$

$$ \begin{array}{c} 0000~000\\ 0000~111\\ 0000~222\\ 1111~000\\ 1111~111\\ 1111~222\\ 2222~000\\ 2222~111\\ 2222~222\\ \end{array} $$ Now, for any possible vector in $GF(3)^7$ there is a codeword which is quite far from it. Namely, if there are fewer than 2 symbols for that vector in a block, there is a codeword which is at Hamming distance $v$ from it. If all 3 symbols occur, there is a codeword at Hamming distance $\geq \lfloor 2v/3 \rfloor$ from it. Since all possible constant blocks occur, for any possible vector in $GF(3)^7$ there is a codeword in this code of only $M=9$ codewords which is at Hamming distance $\geq k \lfloor (q-1)v/q \rfloor \approx n(1-\frac{1}{q}).$ Choosing $v$ a multiple of $q$ will make this more efficient.