# Find the largest subset of all binary arrays of length $n$ with $r$ ones which have pairwise distance greater than $m$

Let $$\Omega = \left\lbrace x : |x| = r \, \text{for} \, x \in \mathbb{Z}_2^n \right\rbrace$$ for $$r \in \mathbb{N}$$. We want to find the the biggest subset of $$\Omega$$, $$\Gamma = \left\lbrace x \in \Omega : |x - y| \geq m ,\, \forall x, y \in \Gamma \right\rbrace$$ for a given value of $$m \in \mathbb{N}$$.

New contributor
Bartosz Bartmanski is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Where does this problem originate? Is this not saying to find the biggest subset of $\Omega$ which is an $(m-1)$-error detecting code? – Carl-Fredrik Nyberg Brodda Feb 12 at 13:44
• This problem was given to me by biologists who were interested in improving experimental design. It's about organising samples and getting the most out of a single run of experiments – Bartosz Bartmanski Feb 12 at 13:56
• I don't know whether there is an "explicit" solution in terms of the size of $\Gamma$ in full generality, but depending on how much information you have about $\Omega$, you may be able to deduce some bounds on the size of $\Gamma$ by using the packing radius (and the associated sphere packing). – Carl-Fredrik Nyberg Brodda Feb 12 at 14:17
• – gyashfe Feb 12 at 18:09

What you are looking for is precisely the optimal (largest cardinality) constant weight (this weight is $$r$$ in your case) binary code with length $$n$$ and distance $$m$$, which is a well-researched and very difficult problem in general.
Let this quantity be denoted $$A(n,m,r)$$ in your terminology. In fact normally, this is denoted $$A(n,d,w)$$ with $$d$$ the minimum distance and $$w$$ the constant weight. There are tables of upper (see here) and lower (see here) bounds for small values of the parameters.
Let $$A(n,d)$$ be the largest possible number of codewords in such an unrestricted binary code with length $$n$$ and minimum distance $$d.$$ Then by the fact that $$r-$$spheres around codewords must be disjoint where $$r=\lfloor (d-1)/2\rfloor,$$ such a code $$\Omega$$ must obey $$\#\Omega\leq \frac{2^n}{\sum_{k=0}^r \binom{n}{k}}$$ where the denominator is the volume of the Hamming sphere of radius $$r.$$