# Maximum number of vectors in a hypercube satisfying given conditions

$\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.

• link.springer.com/article/10.1007%2FBF02579389 might help (maybe you already used their result). – Hao Chen Nov 12 '14 at 12:33
• Is this binary or Euclidean inner product? Meaning, is it $\ne0$ or $\ne0\bmod 2$? – Alex Degtyarev Nov 12 '14 at 12:35
• @HaoChen Thank you. I haven't read the paper yet. – SGC Nov 12 '14 at 13:57
• @AlexDegtyarev It is Euclidean inner-product. – SGC Nov 12 '14 at 14:00
• Would you please share your proof of upper bound $c2^{n/2}$, if it is not secret? – Fedor Petrov Sep 25 '15 at 8:59

The condition implies that $\mathcal{C}$ is 2-Sperner : that is, there are no subsets $A,B,C \in \mathcal{C}$ with $A \subseteq B \subseteq C$. For otherwise, $C - B$ is supported on the complement of $B$ and $A - B$ is supported on B, so they are orthogonal.
By a result of Erdős, $|\mathcal{C}|$ is at most the sum of the two largest binomial coefficients of order $n$ i.e. typically much smaller than $2^{n/2}$.
However, there are only one or two 2-Sperner families of this size, and neither of them has the the orthogonal property you want, so while this answers the question of whether there is a family of size $2^{n/2}$, it does not find the largest family.
• The growth of the largest binomial coefficient(s) $n \choose m$ is $\sim 2^n / \sqrt{n}$. How do you get "much smaller than $2^{n/2}$"? – Noam D. Elkies Aug 26 '15 at 4:35
• Noam D. Elkies' comment is correct. Also, the statement $A-B$ is supported on $B$ in the answer is incorrect. – kodlu Aug 26 '15 at 5:25
• @NoamD.Elkies, I read the problem too hastily. I kept interpreting $2^{n/2}$ as $2^{n - 1}$. With that in mind, my answer is clearly unhelpful. – Josh Brown Kramer Aug 26 '15 at 16:47
• @kodlu, the support of $A - B$ is $B \setminus A$, which is a subset of $B$. Maybe it's not right to say it supported on $B$, but at any rate, the fact that $\mathcal{C}$ is 2-Sperner still holds. – Josh Brown Kramer Aug 26 '15 at 16:48