How to obtain $n$ maximally different binary vectors with equal number of zeros and ones?

Question

Imagine the set of all binary vectors of length $2m$ where each of the vectors has $m$ ones and $m$ zeros.
I want to select some $n$ of these vectors such that the shortest distance among all pairs of vectors from this set of $n$ vectors is maximized. In other words I want a set of vectors which are maximally distant from each other.
I define distance by the number of positions at which the corresponding digits are different. For example distance between vectors $[1,0,0,1,1,0]$ and $[1,1,0,0,0,1]$ is $4$.

For example for $m=4$ and $n=2$ the solution can be $[1,1,1,1,0,0,0,0]$ and $[0,0,0,0,1,1,1,1]$.

How can I find a solution for arbitrary $m$ and $n$?

Answer 1

As Gerry Myerson observed, this is a relatively extensively studied open problem in coding theory. The topic is known as constant-weight codes.

Brouwer has a table of upper bounds for the sizes of constant-weight codes (among other things). In my experience his tables are well maintained, often cited, frequently updated and reflect the current state of research. Wikipedia also gives a link Agrell's table of lower bounds.

Answer 2

Unfortunately I solved the problem of minimizing distances

Let $A$ be a set of $2m$ elements, given a vector of length $2m$ with $m$ ones transform it into a subset of $A$ with $m$ elements where the elements are the positions that have a $1$. given vectors $v$ and $u$ transform them into subsets $v'$ and $u'$. Then the distance between $v$ and $u$ is equal to $2m-|u'\cap v'|$. Then what we want is to find the minimum $t$ so that there is a $t$-intersecting family $\mathcal F\subset \binom{A}{m}$ of size $n$.

You can use Erdős Ko Rado (see result 1.6) which tells you the maximum size of a $t$-intersecting family of subsets of $2m$ of size $m$ is $\binom{2m-t}{m-t}$ when $(m-t+1)(t+1)\geq 2m$, which in this case is for all $t$.

Therefore given $n$ find the largest $t$ so that $\binom{2m-t}{m-t}\geq n$, this is going to be the largest $t$ so that you can find a $t$ intersecting family of size $t$. when you convert the family into vectors you get a family of vectors such that the minimum distance between vectors is $2m-2t$.

---

The Problem of Maximizing Distances:

For this problem you can do the same translation, only this time you want a family of subsets that have small intersection, apparently this is open. The question has been asked before here and it includes an algorithm for constructing such sets.