$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean inner-product $\langle x-z,y-z\rangle\neq0$. I want to evaluate the maximum cardinality of $\mathcal{C}$. If $\mathcal{C}$ fulfills the above condition, I can prove $|\mathcal{C}|\leq c2^{n/2}$, up to some constant $1<c<2$.

I am wondering whether one can construct such $\mathcal{C}$ with $|\mathcal{C}|\geq 2^{n/2}$ for arbitrary $n$.

For $n=2,3$, the optimal $\mathcal{C}$ has strong geometry structures. But I am not familiar with the stuff in hypercube. Do you have any suggestions?

This problem originally came from coding theory. The condition $\langle x-z,y-z\rangle\neq0$ (Euclidean) implies the Hamming distance $d(x,y)<d(x,z)+d(y,z)$, in other words, the vectors $x,y,z$ are not on a line in Hamming space.

The binary inner product case is also interesting. In this case, one can prove $|\mathcal{C}|\leq2^{\frac{n-1}{2}}$ by linear algebra method.

4more comments