2
$\begingroup$

I want to construct $n$ binary strings, each of the same length $m$ (to be determined), such that each pair of string has Hamming distance exactly $m/2$ (i.e. the strings disagree on $m/2$ positions).

I want to minimize the length $m$ of the constructed sequences.
I can do it with $m = 2^{n - 1}$ (I believe).

My question: is $m$ necessarily exponential in $n$?

Or is there some $c$ such that length $m \leq n^c$ is enough?

$\endgroup$
2
$\begingroup$

There's in fact a simple linear-size construction: Choose as $m$ the smallest power of two that is greater or equal to $n$. Then pick any $n$ rows of the $m\times m$ Hadamard matrix.

Here's an example image of a Hadamard matrix:

http://patentimages.storage.googleapis.com/EP1143651A1/00230001.png

$\endgroup$
  • $\begingroup$ Wow, thanks! I was way off track thinking it had to be exponential :) $\endgroup$ – Manuel Lafond May 27 '16 at 13:19

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.