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

Question

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

Answer 1

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

• R. Ahlswede and G. O. H. Katona, Contributions to the geometry of Hamming spaces, DM 17 1–22, 1977. doi:10.1016/0012-365X(77)90017-6