3
$\begingroup$

Let $A$ and $B$ be nonempty finite sets of cardinalities $n$ and $m$, respectively. The distance between two functions $f, g : A \to B$ is defined as the number of disagreements between them, that is, $$ d(f,g) := \# \{x\in A : f(x) \neq g(x)\}. $$

Let $ 0 < k < n$. A set $F \subset B^A$ is called $k$-separated if $d(f,g) \ge k$ for every pair of distinct elements $f,g \in F$.

Main question: Is there an exact formula for the maximal cardinality $S(n,m,k)$ of a $k$-separated set?

Subsidiary question: Is there a simple combinatorial description of a $k$-separated set of maximal (or nearly maximal) cardinality?

It's easy to give bounds. The cardinality of a ``closed'' ball of radius $r$ is $$ B(n,m,r) := \sum_{j=0}^{r} \binom{n}{j} (m-1)^j. $$ If $M$ is a $k$-separated set of maximal cardinality (and therefore maximal) then the balls centered at points of $M$ and of radii $k-1$ (resp. $\lfloor k/2 \rfloor$) cover $B^A$ (resp. are disjoint), so: $$ \frac{m^n}{B(n,m,k-1)} \le S(n,m,k) \le \frac{m^n}{B(n,m,\lfloor k/2 \rfloor)} $$

$\endgroup$
  • 3
    $\begingroup$ I'm afraid a good answer to this question would be an exposition of a large part of coding theory. Since I'm not qualified to write that, let me just refer to the Wikipedia article en.wikipedia.org/wiki/Coding_theory, in particular the section on channel coding. $\endgroup$ – Andreas Blass Sep 28 '16 at 19:47
  • 3
    $\begingroup$ Already for $m=2$ this problem is famous: it is a central question in the coding theory, there are various estimates, and rarely exact values are known. $\endgroup$ – Fedor Petrov Sep 28 '16 at 19:49
  • $\begingroup$ Thanks Adreas and Fedor. Now I see that d is called the Hamming distance. $\endgroup$ – Jairo Bochi Sep 28 '16 at 19:56
  • $\begingroup$ This seems to be a good entry point in the theory: en.wikipedia.org/wiki/Hamming_bound It's seems clear that the short answers to my questions are "no"s. $\endgroup$ – Jairo Bochi Sep 28 '16 at 20:10
2
$\begingroup$

Expanding on the comments of Andreas and Fedor I will point out a resource where this data is kept track of. This will give some measure of how unknown these numbers are (and when they are actually known).

For $m=2$ you are looking for the largest binary code of length $n$ with minimum distance $k$. Which as Fedor says is a a famous problem. Let $A(n,d)$ denote the maximum number codewords in binary code of length $n$ with minimum distance $d$. We have $A(n-1,2d-1) = A(n, 2d)$ so we can restrict attention to even minimum distance. There was a table for $A(n,d)$ in the paper Bounds for Binary Codes of Length Less than 25 by Best, Brouwer, MacWilliams, Odlyzko, and Sloane from 1978.

Brouwer has a table on his webpage with updates to the table from the article above. On the Andries E. Brouwer's homepage you can find links to tables (with references) for $m=2,3,4,5$ (i.e. binary, ternary, etc.) and small $n$. The tables should be up to date, I see references as recent as 2016 on the pages for $m =3,4,5$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.