[Math] Number of Binary Strings of Length $n$ with Hamming Distance $n/2$

combinatorics

Consider an Hadamard matrix of order $n$, which is a multiple of 4:

  • each element is either $1$ or $-1$,
  • every pair of distinct rows have hamming distance $n/2$; that is, two distinct $n$ bit strings (which correspond to rows of an Hadamard matrix) differ in exactly $n/2$ positions.

My question is: What can we say about the number of possible candidate rows in an Hadamard matrix of order $n$? Put another way,
$$\text{What is the largest number of $n$ bit strings whose hamming distance is $n/2$?}$$

Best Answer

Your formulation in terms of Hamming distance seems to be a good one for making progress.

The quantity you want then seems to be denoted $A_2(n,n/2)$. The Plotkin bound gives: if $n/2$ is even then $A_2(n,n/2) \le 2n$, otherwise $A_2(n,n/2) \le 2\lfloor n/2+1 \rfloor = n+1$.

A lower bound can be found by constructing an explicit set. For the special case $n=2^t$ for positive integer $t$, consider the strings $0^n, 0^{n/2}1^{n/2}, 0^{n/4}1^{n/4}0^{n/4}1^{n/4},\dots, 0^21^20^2\dots 0^21^2, 0101\dots 01$. This satisfies the conditions and has $t+1 = 1 + \log_2 n$ strings.

I suspect that better bounds are known, and would be interested in a more precise analysis. Perhaps someone like Peter Cameron might be able to provide pointers.


It is worth remarking that there is an interesting reformulation of your problem in terms of set systems.

Given a set of strings which are all distance $n/2$ from each other, first transform the coordinate system. Pick one string in the set and flip its 1 bits to make it the all-zero string. Applying the same permutation to each of the other strings retains the Hamming distances. This leads to every string other than $0^n$ having exactly $n/2$ bits set to 1.

Consider the set system of which these strings are the characteristic vectors of sets in the system, excluding the all-zero vector. Each set contains precisely $n/2$ elements. Observe that the pairwise intersections contain precisely $n/4$ elements.

Then your question can be rephrased as follows (equivalent up to the difference of 1 from excluding the $0^n$ string).

What is the largest possible set system of subsets of an $n$-element set, such that each contains precisely $n/2$ elements, and such that their pairwise intersections have precisely $n/4$ elements?

Again this sounds natural and I would expect this is known, but I did not find anything about this problem in the Lovász Combinatorial Problems and Exercises book or in the Deza/Frankl survey from 1983; it seems a bit tricky to find the right online search terms. The usual setup for Erdős–Ko–Rado style results is more relaxed, allowing intersections of at least some threshold; here all pairwise intersections are precisely $n/4$.

  • M. Deza and P. Frankl, Erdös–Ko–Rado Theorem—22 Years Later, SIAM J. Alg. Disc. Meth. 4 419–431, 1983. doi:10.1137/0604042

There is another potentially relevant paper but I have not been able to extract much from it (or at least from the scanned image of the paper).

Related Question