1
$\begingroup$

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

$\endgroup$
  • $\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 Brodda Feb 12 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 Bartmanski Feb 12 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 Brodda Feb 12 at 14:17
  • 2
    $\begingroup$ See en.wikipedia.org/wiki/Constant-weight_code $\endgroup$ – gyashfe Feb 12 at 18:09
2
$\begingroup$

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

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