Skip to main content
2 of 2
Added additional material from the comments.; deleted 1 characters in body
Gil Kalai
  • 24.7k
  • 38
  • 235
  • 327

There cannot be more than $n$ such words. To see this, consider the words as elements of $\{-1,1\}^n$. If two such words have Hamming distance $\Delta$, then their scalar product in $\mathbb R^n$ is $n-2\Delta$. In particular, if they all have distance $n/2$, then they are orthogonal, hence linearly independent, hence there are at most $n$ many.

An array of $n$ $\pm 1$ vectors such that every two are orthogonal is called a Hadamard matrix. Such a matrix does not exist unless n=1,2 or n is a multiple of 4. The famous Hadamard conjecture asserts that when $n$ is a multiple of 4, there exists a Hadamard matric of order $n$, This is known to be true in many cases and, in particular, when $n<668$.

An important special case is when $n=2^k$ is a power of two. Then you can construct a set of $n$ such words as follows. We identify bits with elements of the field $\mathbb F_2$, and coordinates $x< n$ with elements of $\mathbb F_2^k$, and thus consider words as functions $f\colon\mathbb F_2^k\to\mathbb F_2$. For any $x,y\in\mathbb F_2^k$, let $f_x(y)=\langle x,y\rangle:=\bigoplus_{i< k}x_iy_i$, where $\oplus$ denotes addition in $\mathbb F_2$ (i.e., modulo $2$). Then $\{f_x:x\in\mathbb F_2^k\}$ is a set of words of size $2^k$, and pairwise Hamming distance $2^{k-1}$, as for any distinct $x,x'$, we have $f_x(y)=f_{x'}(y)$ iff $\langle x\oplus x',y\rangle=0$, which holds for exactly one half of all $y$’s.

Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208