# Separated sets of functions between finite sets

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)}$$

• 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. – Andreas Blass Sep 28 '16 at 19:47
• 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. – Fedor Petrov Sep 28 '16 at 19:49
• Thanks Adreas and Fedor. Now I see that d is called the Hamming distance. – Jairo Bochi Sep 28 '16 at 19:56
• 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. – Jairo Bochi Sep 28 '16 at 20:10

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$.