Maximizing the mutual Hamming distance in $\big[{\cal P}([n])\big]^n$

Question

If $X$ is a set and $A,B\subseteq X$ we let the Hamming distance of $A,B$ be defined as $d_H(A,B) = \big|(A\setminus B)\cup(B\setminus A)\big|$. If $\newcommand{\S}{{\cal S}}\S\subseteq {\cal P}(X)$, let the discrepancy of ${\cal S}$ be definied by $\newcommand{\d}{\text{discr}}\d(\S)=\min\{d_H(A,B): A\neq B\in\S\}$.

For $n\in\mathbb{N}$, let $[n]=\{1,\ldots,n\}$. Let $X$ be a set and $n\in\mathbb{N}$. Then $[X]^n$ denotes the collection of subsets of $X$ having $n$ elements.

For $n\in\mathbb{N}$, let $M_n:= \max\{\d(\S):\S\in \big[{\cal P}([n])\big]^n\}$.

Experiments by Rob Pratt and Claude Chaunier as laid out in the comments below (cheers to Rob and Claude!) seem to point to the following hypothesis:

For all $k\in\mathbb{N}$ with $k\geq 2$ we have

• $M_{2k} = k$ , and
• $M_{2k+1} = k$ for $k$ even, and $M_{2k+1} = k+1$ for $k$ odd.

Question. Is the above hypothesis true?

Answer 1

Here is an elementary proof that $M_n\le \frac{n-1}{2}$ for any $n$ in $4\mathbb{N}+5\;$.

Lemma 1. For any odd $n\ge 3$ and any $n$ vectors $\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_n$ in $\{-1,1\}^n$, their pairwise Hamming distances satisfy either $$d_H(\mathbf{u}_i,\mathbf{u}_j) = \frac{n+1}{2}\quad \text{ for any }i\ne j\qquad(1)\;\;$$ or $$d_H(\mathbf{u}_i,\mathbf{u}_j) < \frac{n+1}{2}\quad \text{ for some }i\ne j\qquad(2)\;.$$

Proof of Lemma 1. For any odd $m\ge 3$ let us follow kodlu's insight with an additional twist about parity and assume there are some $d\in \mathbb{N}$ and $m$ vectors $\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_m$ in $\{-1,1\}^n$ with pairwise Hamming distances $d_H(\mathbf{u}_i,\mathbf{u}_j)$ $\ge d$ for any $i\ne j$. Their inner products satisfy $\langle\mathbf{u}_i|\mathbf{u}_j\rangle =$ $n-2d_H(\mathbf{u}_i,\mathbf{u}_j)\le$ $n-2d$. Since the sum of $m$ odd integers is an odd integer, the components $v_1, v_2, \dots, v_n$ of $\mathbf{v} = \sum_{i=1}^m \mathbf{u}_i$ are odd integers therefore

\begin{align}n \le \sum_{i=1}^n v_i^2 = |\mathbf{v}|^2 = \Big\langle\sum_{i=1}^m\mathbf{u}_i\Big|\sum_{j=1}^m\mathbf{u}_j\Big\rangle = \sum_{i=1}^m|\mathbf{u}_i|^2 + 2\!\!\!\!\sum_{1\le i<j\le m}\!\!\!\!\langle\mathbf{u}_i|\mathbf{u}_j\rangle&\\ \le mn + m(m-1)(n-2d)&\qquad(3)\;, \end{align}

which eventually yields $$d\leq \frac{n}{2}\frac{m+1}{m}\;\qquad\qquad$$

Letting $m=n$ we get $$d\leq \frac{n+1}{2}\qquad\qquad(4)\;.$$ Now suppose $(2)$ doesn't hold. In other words $d_H(\mathbf{u}_i,\mathbf{u}_j)\ge d$ for $d=\frac{n+1}{2}$ and any $i\ne j$. Suppose $(1)$ doesn't hold either. Then $d_H(\mathbf{u}_i,\mathbf{u}_j)> d$ for some $i\ne j$ and inequalities $(3)$ and $(4)$ become strict, contradicting $d=\frac{n+1}{2}$. Therefore either $(1)$ or $(2)$ must hold. $\blacksquare$

Lemma 2. For any odd $n\ge 3$, if the Hamming distances of three subsets $A,B,C$ of $\{1, 2, \dots,n\}$ satisfy $$d_H(A,B) = d_H(A,C) = d_H(B,C) = \frac{n+1}{2}$$ then $n\in 4\mathbb{N}+3\;$.

Proof of Lemma 2. Take any $a$ in $A$. Without changing any Hamming distance we can simultaneously remove $a$ from $A$ and switch whether $a$ is or is not in $B$ and whether $a$ is or is not in $C$. Therefore we can assume $A = \varnothing$ without loss of generality.

Then $$|B| = d_H(\varnothing,B) = d_H(A,B) = \frac{n+1}{2} = |C|$$ and $$\frac{n+1}{2} = d_H(B,C) = |B|+|C|-2|B\cap C| = n+1-2|B\cap C|$$ so that $n+1 = 4|B\cap C|$ and finally $n\in 4\mathbb{N}+3\;$. $\blacksquare$

Back to our main claim. We know $M_n\le \frac{n+1}{2}$ for any odd $n\ge 3$ from kodlu's result. Now suppose $M_n = \frac{n+1}{2}$ for some $n$ in $4\mathbb{N}+5$. Then $(1)$ would hold in Lemma 1 therefore Lemma 2 would apply and $n$ would be in $4\mathbb{N}+3$, a contradiction. Therefore $M_n < \frac{n+1}{2}$ for any $n$ in $4\mathbb{N}+5$. Dealing with integers, it means $M_n \le \frac{n-1}{2}$.