3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think there's a general theorem that the number of subsets of an $n$-set, each pair having exactly $k$ elements in common, is never more than $n$. In fact, I think I saw that very theorem stated here (or maybe on MathOverflow) very recently (in the last day or two). $\endgroup$ – Gerry Myerson Jul 1 '13 at 12:48
  • $\begingroup$ @GerryMyerson: I think this is (at least related to) the Frankl-Wilson theorem. Having difficulty tracking it down exactly. $\endgroup$ – Ben Millwood Jul 1 '13 at 12:59
  • $\begingroup$ @Ben, I think you're right. Type Frankl-Wilson site:math.stackexchange.com (or, Frankl-Wilson site:mathoverflow.net) into Google to see what comes up. $\endgroup$ – Gerry Myerson Jul 1 '13 at 13:08
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think the question in your blockquote is what Frankl-Wilson can be applied to – you get an upper bound of $n$ sets in your system, essentially by orthogonality. This is stronger than the Plotkin bound for the same reason that it's stronger than the EKR approach, I think. $\endgroup$ – Ben Millwood Jul 2 '13 at 10:40
  • $\begingroup$ @BenMillwood: Thanks, Frankl-Wilson does indeed give an upper bound of $n+1$ strings (or $n$ sets). It is not immediately obvious that its proof via containment matrices yields a better lower bound, though. $\endgroup$ – András Salamon Jul 2 '13 at 12:24
  • $\begingroup$ See also my follow-on question mathoverflow.net/questions/135509/… which led to the essentially optimal bounds, via results of Ryser and Sylvester. $\endgroup$ – András Salamon Jul 3 '13 at 2:03

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.