<p>Look up the concept of anticodes. Some bounds exist.</p>

<p>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.</p>

<p><strong>A Simple Construction</strong></p>

<p>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&amp;0\\
0&amp;1\\
0&amp;2\\
1&amp;0\\
1&amp;1\\
1&amp;2\\
2&amp;0\\
2&amp;1\\
2&amp;2\\
\end{array}
$$</p>

<p>which become upon expansion with $v=4$</p>

<p>$$
\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.</p>

CC BY-SA 3.0
2015-05-13T02:29:29.387Z
2015-05-13T04:54:03.057Z
2015-05-13T04:54:03.057Z
kodlu
<p>We are considering length n strings over the alphabet S. </p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-05-11T21:50:44.910Z
Hmm... do you want to minimize set M? Actually, in your example you need only two strings $aa \cdots a$ and $bb \cdots b$ to get n/2 distance.
Vsevolod Oparin
CC BY-SA 3.0
2015-05-12T10:27:37.860Z
Yes I want to minimize the size of M. You are right, for n/2 distance you only need two, but what about other (bigger distances)? You may assume that the size of the alphabet is a constant.
user32149
CC BY-SA 3.0
2015-06-24T11:07:46.280Z
does the answer below go some way towards what you want?
kodlu
CC BY-SA 3.0
2015-07-02T09:08:52.700Z
yes, thanks. Anticodes was the magic word I was looking for.
user32149
<edit-distance><covering-problems>
Long distance string problem
user32149
# Long distance string problem

(Asked by: username_0 on 2015-05-11)

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.

**Tags:** edit-distance, covering-problems
> **Comments:**
> **username_1**: Hmm... do you want to minimize set M? Actually, in your example you need only two strings $aa \cdots a$ and $bb \cdots b$ to get n/2 distance.  
> **username_0**: Yes I want to minimize the size of M. You are right, for n/2 distance you only need two, but what about other (bigger distances)? You may assume that the size of the alphabet is a constant.  
> **username_2**: does the answer below go some way towards what you want?  
> **username_0**: yes, thanks. Anticodes was the magic word I was looking for.  

---

## 1 answers

### Answer by username_2 on 2015-05-13. Score: 2 | Accepted answer

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.


---

