Skip to main content
added 123 characters in body
Source Link
Yoav Kallus
  • 6k
  • 3
  • 41
  • 57

The problem of obtaining the largest set $X$ under the condition that its largest pairwise distance is bounded from above is known as the anticode problem, since it is naturally dual to the problem of finding an optimal error correcting code, where the smallest pairwise distance is bounded from below. It is apparently a theorem of Kleitman (http://dx.doi.org/10.1016/S0021-9800(66)80027-3) that the best binary anticode of diameter $2k$ and length $m$ is simply constructed by taking all strings of length $m$ with at most $k$ 1s (that is, a Hamming ball of radius $k$). If you let $k=\lceil m/2\rceil-1$$k=\lfloor(\lceil m/2\rceil-1)/2\rfloor$ (I hope I got this right now), then you will find that the size of this anticode exceeds the bound you give in your question, and so the statement you cited is false, as already noted by Robert and Christian. It can be corrected by increasing $0.8$ to a slightly higher number, as they note.

Some more on Hamming anticodes: http://dx.doi.org/10.1006/aama.1998.0588

The problem of obtaining the largest set $X$ under the condition that its largest pairwise distance is bounded from above is known as the anticode problem, since it is naturally dual to the problem of finding an optimal error correcting code, where the smallest pairwise distance is bounded from below. It is apparently a theorem of Kleitman (http://dx.doi.org/10.1016/S0021-9800(66)80027-3) that the best binary anticode of diameter $2k$ and length $m$ is simply constructed by taking all strings of length $m$ with at most $k$ 1s (that is, a Hamming ball of radius $k$). If you let $k=\lceil m/2\rceil-1$, then you will find that the size of this anticode exceeds the bound you give in your question, and so the statement you cited is false, as already noted by Robert and Christian. It can be corrected by increasing $0.8$ to a slightly higher number, as they note.

Some more on Hamming anticodes: http://dx.doi.org/10.1006/aama.1998.0588

The problem of obtaining the largest set $X$ under the condition that its largest pairwise distance is bounded from above is known as the anticode problem, since it is naturally dual to the problem of finding an optimal error correcting code, where the smallest pairwise distance is bounded from below. It is apparently a theorem of Kleitman (http://dx.doi.org/10.1016/S0021-9800(66)80027-3) that the best binary anticode of diameter $2k$ and length $m$ is simply constructed by taking all strings of length $m$ with at most $k$ 1s (that is, a Hamming ball of radius $k$). If you let $k=\lfloor(\lceil m/2\rceil-1)/2\rfloor$ (I hope I got this right now), then you will find that the size of this anticode exceeds the bound you give in your question, and so the statement you cited is false, as already noted by Robert and Christian. It can be corrected by increasing $0.8$ to a slightly higher number, as they note.

Some more on Hamming anticodes: http://dx.doi.org/10.1006/aama.1998.0588

added 123 characters in body
Source Link
Yoav Kallus
  • 6k
  • 3
  • 41
  • 57

The problem of obtaining the largest set $X$ under the condition that its largest pairwise distance is bounded from above is known as the anticode problem, since it is naturally dual to the problem of finding an optimal error correcting code, where the smallest pairwise distance is bounded from below. It is apparently a theorem of Kleitman (http://dx.doi.org/10.1016/S0021-9800(66)80027-3) that the best binary anticode of diameter $2k$ and length $m$ is simply constructed by taking all strings of length $m$ with at most $k$ 1s (that is, a Hamming ball of radius $k$). If you let $k=\lceil m/2\rceil-1$, then you will find that the size of this anticode exceeds the bound you give in your question, and so the statement you cited is false, as already noted by Robert and Christian. It can be corrected by increasing $0.8$ to a slightly higher number, as they note.

Some more on Hamming anticodes: http://dx.doi.org/10.1006/aama.1998.0588

The problem of obtaining the largest set $X$ under the condition that its largest pairwise distance is bounded from above is known as the anticode problem, since it is naturally dual to the problem of finding an optimal error correcting code, where the smallest pairwise distance is bounded from below. It is apparently a theorem of Kleitman (http://dx.doi.org/10.1016/S0021-9800(66)80027-3) that the best binary anticode of diameter $2k$ and length $m$ is simply constructed by taking all strings of length $m$ with at most $k$ 1s. If you let $k=\lceil m/2\rceil-1$, then you will find that the size of this anticode exceeds the bound you give in your question, and so the statement you cited is false, as already noted by Robert and Christian.

Some more on Hamming anticodes: http://dx.doi.org/10.1006/aama.1998.0588

The problem of obtaining the largest set $X$ under the condition that its largest pairwise distance is bounded from above is known as the anticode problem, since it is naturally dual to the problem of finding an optimal error correcting code, where the smallest pairwise distance is bounded from below. It is apparently a theorem of Kleitman (http://dx.doi.org/10.1016/S0021-9800(66)80027-3) that the best binary anticode of diameter $2k$ and length $m$ is simply constructed by taking all strings of length $m$ with at most $k$ 1s (that is, a Hamming ball of radius $k$). If you let $k=\lceil m/2\rceil-1$, then you will find that the size of this anticode exceeds the bound you give in your question, and so the statement you cited is false, as already noted by Robert and Christian. It can be corrected by increasing $0.8$ to a slightly higher number, as they note.

Some more on Hamming anticodes: http://dx.doi.org/10.1006/aama.1998.0588

Source Link
Yoav Kallus
  • 6k
  • 3
  • 41
  • 57

The problem of obtaining the largest set $X$ under the condition that its largest pairwise distance is bounded from above is known as the anticode problem, since it is naturally dual to the problem of finding an optimal error correcting code, where the smallest pairwise distance is bounded from below. It is apparently a theorem of Kleitman (http://dx.doi.org/10.1016/S0021-9800(66)80027-3) that the best binary anticode of diameter $2k$ and length $m$ is simply constructed by taking all strings of length $m$ with at most $k$ 1s. If you let $k=\lceil m/2\rceil-1$, then you will find that the size of this anticode exceeds the bound you give in your question, and so the statement you cited is false, as already noted by Robert and Christian.

Some more on Hamming anticodes: http://dx.doi.org/10.1006/aama.1998.0588