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}$.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Where does this problem originate? Is this not saying to find the biggest subset of $\Omega$ which is an $(m-1)$-error detecting code? $\endgroup$– Carl-Fredrik Nyberg BroddaCommented Feb 12, 2020 at 13:44
-
$\begingroup$ 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 $\endgroup$– Bartosz BartmanskiCommented Feb 12, 2020 at 13:56
-
$\begingroup$ 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). $\endgroup$– Carl-Fredrik Nyberg BroddaCommented Feb 12, 2020 at 14:17
-
2$\begingroup$ See en.wikipedia.org/wiki/Constant-weight_code $\endgroup$– Geva YashfeCommented Feb 12, 2020 at 18:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
Clearly, a constant weight code in general will have fewer codewords than an unrestricted code. So, general upper bounds on code cardinality will also upper bound a constant weight code.
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.$
