# Number of pairs of Binary Strings of Length n with Hamming Distance b

What is the maximum number of pairs of $k\geq2$ distinct binary strings of length $n$, such that the strings in each pair are at Hamming distance $b$? In other words, given $k$ points on the $n$-dimensional Boolean hypercube, how many of these can possibly be at distance $b$ of each other?

I have a trivial upper bound given by $k \min\{\binom{n}{b},k\}$ simply because each string can have at most $\binom{n}{b}$ neighbors at distance $b$. Does anybody know how to better upper bound this quantity?

• Do you want all the strings to be pairwise at distance $b$? So for $n=5, b=2$ an answer would be $\{10000,11100,11010,10110\}$? This may not be maximal. – Ross Millikan Sep 11 '13 at 15:28
• I think it might not always be possible to have all $k$ strings at pairwise distance $b$ like in your example, because e.g. you cannot have more than $n$ neighbors at distance 1. So I would like to have as many as possible at pairwise distance $b$ – adrianomeis Sep 11 '13 at 15:41
• I was trying to understand the question. If I read the first sentence literally, I could split the $2^n$ strings into pairs, with each string at distance $b$ from its mate, and get $2^{n-1} pairs. I don't know for sure this is possible, but I think so. Is that what you are after? – Ross Millikan Sep 11 '13 at 15:48 • @Ross' suggestion is easy to make work. Take a fixed string$w$of weight$b$, and pair up the strings$u$and$u+b$for all$u$. Here$u+b\$ is the componentwise modulo 2 sum (=bitwise XOR). – Jyrki Lahtonen Sep 16 '13 at 8:46